# Is there a computable and complete “probabilistic” theory of arithmetic?

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?

• Slightly related – PyRulez Feb 19 at 13:44
• "Given an oracle for $p_\mathbb{T}$" Given that $p_\mathbb{T}$ is a map from sentences to reals, we have to be careful with what this means. In particular, your claim that $p_\mathbb{T}\ge_T\mathbb{T}_{a,s}$ is not true for all such notions. – Noah Schweber Feb 19 at 14:27
• @NoahSchweber oh yeah, I forgot the subtleties of real numbers and computation. I deleted that paragraph. – PyRulez Feb 19 at 14:35
• Outsider question: is the set of theories of first order arithmetic countable? If not, how do you define a sigma algebra on it? – Jack M Feb 19 at 14:43
• It is easier to replace it by $P($ ZFC proves $\mathbb{T}$ is consistent $\land \mathbb{T} \vdash \phi)$ because you can then choose a distribution on an enumerable set of integers $S$, interpret the $s_j \in S$ as theories $T_j$, enumerate the theorems of ZFC trying to prove $T_j$ is consistent and proves $\phi$, return $\sum_{j=1}^J P(s_j) 1_{ZFC \vdash \text{ in J steps} (T_j \text{ is consistent} \land T_j \vdash \phi)}$ and ask if a bound for the remainder $\sum_{j > J} P(s_j) ...$ is computable – reuns Feb 19 at 15:07

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 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 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.

• So basically we start with PA, and add a statement or negation to PA based on which one has positive probability (together with the previous axioms), right? And do that for each statement in sequence. – PyRulez Feb 22 at 20:43
• @PyRulez Yup. The only issue is to make sure we know what to do in case both have positive probability - and that's easy, we just go with the "first" one. – Noah Schweber Feb 22 at 21:54
• I guess you'd technically get a lot of redundant axioms too (i.e. equivalent in PA), right? – PyRulez Feb 22 at 21:58
• @PyRulez Sure, but PA itself is extremely redundant (the induction scheme isn't minimal in any sense). – Noah Schweber Feb 22 at 22:00