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?

  • $\begingroup$ Slightly related $\endgroup$ – PyRulez Feb 19 at 13:44
  • $\begingroup$ "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. $\endgroup$ – Noah Schweber Feb 19 at 14:27
  • $\begingroup$ @NoahSchweber oh yeah, I forgot the subtleties of real numbers and computation. I deleted that paragraph. $\endgroup$ – PyRulez Feb 19 at 14:35
  • $\begingroup$ Outsider question: is the set of theories of first order arithmetic countable? If not, how do you define a sigma algebra on it? $\endgroup$ – Jack M Feb 19 at 14:43
  • $\begingroup$ 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 $\endgroup$ – 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<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.

  • $\begingroup$ 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. $\endgroup$ – PyRulez Feb 22 at 20:43
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Feb 22 at 21:54
  • $\begingroup$ I guess you'd technically get a lot of redundant axioms too (i.e. equivalent in PA), right? $\endgroup$ – PyRulez Feb 22 at 21:58
  • 1
    $\begingroup$ @PyRulez Sure, but PA itself is extremely redundant (the induction scheme isn't minimal in any sense). $\endgroup$ – Noah Schweber Feb 22 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.