# Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)

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'}$$?

• Xref: a similar question was asked on cs.stackexchange, so I linked to this one while answering. Commented Jan 4 at 12:08

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

• 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? Commented Sep 15, 2023 at 14:38
• @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). Commented Sep 15, 2023 at 18:30
• @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). Commented Sep 15, 2023 at 18:34
• 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. Commented Sep 15, 2023 at 18:52
• @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$). Commented Sep 15, 2023 at 18:54

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

• 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. Commented Sep 15, 2023 at 12:12
• 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. Commented Sep 15, 2023 at 14:18
• Oh never mind, I just found this in Cooper's Computability Theory: theorem 15.4.3 and corollary 15.4.5. Commented Sep 15, 2023 at 14:27
• 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). Commented Sep 15, 2023 at 15:12