Density of PA degrees

Question

As suggested by Carl Mummert, I will ask a separate question (this question was posted but then deleted). The following letters $a, b, e,\ldots$ denote Turing degrees. We say $a\gg b$ if there exists a complete extension of degree a to the Peano Arithmetic augmented with axioms $\dot{n}\in \dot{B}$ whenever $n\in B$, and $\dot{n}\not \in \dot{B}$ whenever $n\not\in B$, where $\dot{n}$ are constant symbols for $n\in \omega$ and $B$ is any given set of degree b. Now in Volume 90, Pages ii-viii, 1-1165 (1977) HANDBOOK OF MATHEMATICAL LOGIC, Degrees of Unsolvability: A Survey of Results, Pages 631-652 by Stephen G. Simpson, Theorem 6.5 i), it is claimed that if $a\gg b$ then there exists another degree $e$ such that $a\gg e\gg b$. There was no proof there. I am wondering how to prove this?

Answer 1

The first key fact is that for every degree $a$ there is a $a$-computable infinite tree $T_a \subseteq 2^{<\omega}$ such that an arbitrary degree $c$ is PA over $a$ if and only if $c$ computes a path through $T_a$, that is, an element of $[T_a]$. This fact is mentioned relatively often in the literature.

The second key fact is that we can iterate finding paths in a certain way. There is another $a$-computable infinite tree $\tilde{T}_a \subseteq 2^{<\omega}$ such that any path through $\tilde{T}_a$ is of the form $f \oplus g$ where $f \in [T_a]$ and $g \in [T_f]$. (In the language of Reverse Mathematics, we might say that we can combine two successive applications of weak König's lemma into a single application.) This is well known to experts in the field, but perhaps not directly emphasized in the literature.

To see how to construct $\tilde{T}_a$, first note that $T_a$ is uniformly computable from $a$, which means there is a computable relation $R \subseteq \omega \times 2^{< \omega} \times 2^{\omega}$ such that, for all $\sigma \in 2^{<\omega}$ and $f \in 2^{\omega}$, $$ \sigma \in T_f \Leftrightarrow (\forall n) R(n, \sigma, f). $$

Next define a class $A \subseteq 2^{\omega}$ as follows. Given $f \in 2^{\omega}$, write $f = f_0 \oplus f_1$. Then we put $f \in A$ if and only if $f_0 \in [T_a]$ and, for all $k$ and $n$, $R(n,f_1[k], f_0)$. This is a $\Pi^{0,a}_1$ definition of $A$, so there is an $a$-computable infinite tree $\tilde{T}_a$ such that $A = [\tilde{T}_a]$, and the definition of $A$ ensures that $\tilde{T}$ has the desired property.

Now, because $\tilde{T}_a$ is computable from $a$, and $b\gg a$, there is a path $h = f \oplus g \in [\tilde{T}_a]$ computable from $b$. Let $c$ be the degree of $f$. Then $c \gg a$, because $f \in T_a$, and $b \gg c$, because $b$ computes $g$, which is a path through $T_f$.

We can extend this construction farther to show that, if $a \ll b$, then there is an $f$ computable from $b$ such that, if $f = \oplus_{i \in \omega} f_i$, then $a = f_0$ and $f_{i} \ll f_{i+1}$ for all $i$. So $b$ uniformly computes an entire increasing sequence above $a$ separated by $\ll$. In fact, $b$ computes a countable coded $\omega$-model of $\mathsf{WKL}_0$ containing $a$ (which is the same as a Scott set containing $a$).

The method in the previous paragraph, in turn, is one way to show that every countable coded $\omega$-model of $\mathsf{WKL}_0$ contains, as a single real, another countable coded $\omega$-model of $\mathsf{WKL}_0$. This is one of the more amazing and remarkable results of the field.