8
$\begingroup$

Let $A\subseteq\mathbb{N}$ be the set of Gödel codes of theorems of Peano arithmetic, and $B\subseteq\mathbb{N}$ be the set of codes of antitheorems (i.e, refutable statements, statements whose negation is a theorem). It is a standard fact (see, e.g., Cooper, Computability Theory (1994), exercise 9.2.13) that $A$ and $B$ are computably inseparable: any $D\subseteq\mathbb{N}$ such that $A\subseteq D$ and $B\cap D=\varnothing$ (“separating $A$ and $B$”) is of Turing degree $>\mathbf{0}$. Clearly, we can find such a $D$ having degree $\mathbf{0'}$, since $A$ itself (or, if we prefer, the complement of $B$) is such.

Main question: Does there exist $D$ separating $A$ and $B$ having degree $<\mathbf{0'}$?

Bonus questions: What can be said about the set of possible degrees of $D$ separating $A$ and $B$? Does it have a lower bound? Also, if we take $D$ at random w.r.t. the obvious probability measure (take $A$ and add teach element of the complement of $B$ with probability $\frac{1}{2}$ independently), what is the probability that $D$ has degree $\not\geq\mathbf{0'}$?

$\endgroup$
1

2 Answers 2

13
$\begingroup$

The class of sets (or rather, degrees of sets) $D$ separating $A$ and $B$ is a well-studied class in computability theory called `PA degrees'. Indeed there PA degrees that are low (hence below $0'$), other that are hyperimmune-free (hence incomparable with $0'$), etc.

For the bonus part: it is known that for every PA degree $\mathbf{a}$ there is another PA-degree $\mathbf{b}$ stricly below $\mathbf{a}$ (via an easy adaptation of the argument given by Carl Mummert on this other forum). As to the last question: if you build a separator $D$ probabilistically as proposed, then with probability $1$ you'll have $D \geq 0'$. Indeed, suppose you have built a $D$ in such a manner. You want to know if some program $p$ halts. You can computably find countably many distinct arithmetical statements that express that $p$ halts. If $p$ really does halt, the corresponding bits of $D$ will all be equal to $1$. If $p$ does not halt, then the corresponding bits of $D$ will either all be $0$ (if PA proves that $p$ does not halt) or will be $0-1$ with probability $1/2-1/2$ (if PA cannot decide the halting status of $p$). It thus suffices to sample enough bits of $D$ and if you see a single $0$, you know that $p$ does not halt. Otherwise, you know that with high probability that $p$ does. And you can make the probability of success as high as you want, even across all programs. Thus $D$ computes $0'$ with probability $1$.

$\endgroup$
8
  • 2
    $\begingroup$ Is it clear that any separator of $A$ and $B$, which does not even need to be closed under logical equivalence, actually computes a completion of PA? $\endgroup$ Commented Sep 15, 2023 at 14:38
  • $\begingroup$ @EmilJeřábek Yes, because you can still use it as a consistency checker for greedily building a completion of PA (since PA is $\Sigma_1$-complete). $\endgroup$ Commented Sep 15, 2023 at 18:30
  • $\begingroup$ @NoahSchweber I tried to greedily build a completion before posting the comment as it is the obvious strategy, and failed. Can you provide the details of such a consistency checker? The separator will accept all true $\Sigma_1$ facts, but it will also accept some false $\Sigma_1$ facts, which ruins the consistency of the completion procedure (or the one I tried, anyway). $\endgroup$ Commented Sep 15, 2023 at 18:34
  • $\begingroup$ I mean, if at each step of the completion procedure, I add the sentence $\phi_n$ or its negation according to whether the conjuction of the sentences so far together with $\phi_n$ satisfies $D$, then the completion procedure may fail to be consistent. If I only add $\phi_n$ or nothing according to whether the conjunction satisfies $D$, then it will be consistent indeed, but it may fail to be complete. $\endgroup$ Commented Sep 15, 2023 at 18:52
  • 1
    $\begingroup$ @EmilJeřábek You also use Rosser's trick. E.g. in the first step of the construction, we want to decide whether to put $\varphi$ or $\neg\varphi$ into our completion. We ask whether the sentence $\xi\equiv$ "The shortest proof of a contradiction in $\mathsf{PA}+\neg\varphi$ is shorter than the shortest proof of a contradiction in $\mathsf{PA}+\varphi$" is in $E$ (with the convention that if no such proof of contradiction exists, the associated "length" is $\infty$, and we have $\infty<\infty$). $\endgroup$ Commented Sep 15, 2023 at 18:54
9
$\begingroup$

It is a standard consequence of the low basis theorem that $A$ and $B$ (or indeed, any disjoint pair of r.e. sets) have a separating set $D$ that is low, and therefore of Turing degree strictly below $0'$.

$\endgroup$
4
  • 1
    $\begingroup$ To provide a little more detail for Gro-Tsen: one can form a computable tree of attempts to find a separation of two disjoint c.e. sets (some parts of the tree die off when you find you had made a wrong guess lower down), but every computable tree has a low branch by the low basis theorem, and this branch provides a separating set. $\endgroup$ Commented Sep 15, 2023 at 12:12
  • $\begingroup$ Can you (or perhaps @JoelDavidHamkins) recommend a reference where I might learn more about the low basis theorem and especially its uses? For example one where this particular consequence is stated explicitly. $\endgroup$
    – Gro-Tsen
    Commented Sep 15, 2023 at 14:18
  • $\begingroup$ Oh never mind, I just found this in Cooper's Computability Theory: theorem 15.4.3 and corollary 15.4.5. $\endgroup$
    – Gro-Tsen
    Commented Sep 15, 2023 at 14:27
  • 3
    $\begingroup$ You could also look at §3.7 of Soare's 2016 book Turing Computability; the low basis theorem is theorem 3.7.2. A nice survey is also given by Diamondstone, Dzhafarov and Soare, '$\Pi^0_1$ classes, Peano arithmetic, randomness, and computable domination' (NDJFL 51(1):127–159, 2010). $\endgroup$ Commented Sep 15, 2023 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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