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

Question

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

Answer 1

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

Answer 2

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