Is there a computable and complete "probabilistic" theory of arithmetic?

128 Views Asked by At

Let $\mathbb T$ be a probability distribution over complete and consistent theories of first order arithmetic that contain $PA$. Additionally, we will require that for any sentence $\phi$ in the language of arithmetic, $P(\mathbb T \vdash \phi)$ is defined (that is, $\{T : T \in dom(\mathbb T), T \vdash \phi\}$ is a measurable set).

Is there any such $\mathbb T$ such that $p_{\mathbb T}(\phi) = P(\mathbb T \vdash \phi)$ is a computable function?

1

There are 1 best solutions below

4
On BEST ANSWER

Unless I'm missing something, there is not. The key observations are $(i)$ positive probability implies consistency and $(ii)$ we can't split our space into two measure-zero sets.

First, we need to settle on how we're representing such a $p_\mathbb{T}=p$ so that we can talk about its (non)computability. I'm going to do the following: we conflate $p$ with the set $$\{\langle \varphi,q\rangle\in Sent\times\mathbb{Q}_{>0}: p(\varphi)\ge q\}.$$

(But any reasonable representation should give the same result.)

Suppose I have such a $p$ as an oracle; I'll show how to use $p$ to compute a (consistent) completion of PA.

Fix an enumeration $(a_i)_{i\in\omega}$ of the positive rationals. We say that a sentence $\varphi$ is $p$-consistent iff there is some $i$ such that $\langle \varphi, a_i\rangle\in p$ and no $j<i$ has $\langle \neg\varphi,a_j\rangle\in p$. Note that we can have both $\varphi$ and $\neg\varphi$ be $p$-consistent; we could modify the definition to rule this out, but there's no need to.

The key points now are:

  • In order for $p$ to indeed come from a probability distribution, for every sentence $\varphi$ we must have at least one of $\varphi$ and $\neg\varphi$ be $p$-consistent. Otherwise $\mathbb{T}$ would assign probability $0$ to both $\{T: \varphi\in T\}$ and $\{T: \neg\varphi\in T\}$, hence to the whole space.

  • Given the previous bulletpoint, the set of $p$-consistent sentences is computable from $p$; to tell whether $\varphi$ is $p$-consistent, we just search through the positive rationals until you find the first positive rational witnessing $p$-consistency of at least one of $\varphi$ or $\neg\varphi$.

  • Finally, if $\varphi$ is $p$-consistent, then PA $\cup\{\varphi\}$ is consistent. (Otherwise $\{T: \varphi\in T\}$ isn't even a subset of our probability space!)

So now we just use the usual greedy algorithm:

  • Enumerate the sentences as $(\varphi_k)_{k\in\omega}$.

  • Define the sequence $(\psi_k)_{k\in\omega}$ of sentences recursively by setting $\psi_k=\varphi_k$ if $\varphi_k\wedge(\bigwedge_{l<k}\psi_l)$ is $p$-consistent, and $\psi_k=\neg\varphi_k$ otherwise.

  • The theory PA $\cup\{\psi_k:k\in\omega\}$ is then a consistent completion of PA which is $p$-computable.

In particular, any such $p$ is of PA degree - and conversely, given a PA degree $\bf d$ we can construct such a $p$ (just focus on some fixed completion of PA computed by $\bf d$). So in fact we've (unsurprisingly) characterized the degrees of such $p$s as precisely the PA degrees.