Turing degrees that eventually jump to some $0^{(n)}$

36 Views Asked by At

Starting with any $A\subseteq \omega$, we can form a strictly increasing sequence of Turing degrees by taking iterated Turing jumps: $$A<_T A'<_T A'' <_T\dots.$$ By Post's theorem we also know that if $A$ is definable/arithmetic, there is some $n$ such that $0\leq_T A\leq_T 0^{(n)}$. This means that the jump sequences starting at $0$ and at $A$ are interleaved. My question is whether the two sequences eventually meet up:

Let $d$ be an arithmetic Turing degree (in other words $d\leq_T 0^{(n)}$ for some $n$). Are there some $k$ and $m$ such that $d^{(k)} \equiv_T 0^{(m)}$?

I suspect the answer is no. If we drop the definability assumption, I can prove that this fails by a forcing/absoluteness argument: if $c$ is a Cohen real over $L$ then no finite jump of $c$ (or even any reasonable infinitary jump) is in $L$ and cannot be equivalent to an iterated jump of $0$. By Shoenfield absoluteness, a degree with the same property must already exist in $L$.

1

There are 1 best solutions below

0
On BEST ANSWER

Your guess is correct: in fact, we can find a degree ${\bf d}$ between ${\bf 0}$ and ${\bf 0'}$ such that for all $n$, ${\bf d}^{(n)}$ is strictly between ${\bf 0}^{(n)}$ and ${\bf 0}^{(n+1)}$. This was first proved independently by Lachlan and Martin, but a simpler proof using the recursion theorem was found later by Sacks (thus coming nicely full circle since Sacks posed the question originally). Perhaps confusingly, such degrees are often called "intermediate" since they are neither low$_n$ nor high$_n$ for any $n$.