11
$\begingroup$

I saw in Wikipedia the existence of an infinite sequence of Turing degrees $\bf{a_0}, \bf{a_1}, \dots$ such that $\bf{a}_{i+1}' \leq_T \bf{a}_i$ where $\bf{a}_{i+1}'$ is the Turing jump of $\bf{a}_i$.

However I couldn't find references for this result. Is it a trivial consequence of one of the well-known jump inversion theorems ?

$\endgroup$

1 Answer 1

12
$\begingroup$

There is surely a proof using only classical recursion theory, but the proof I know uses second-order arithmetic.

Take an $\omega$-model $M$ of $\mathsf{ATR}_0$ in which there is a countable linear order $L$ such that $M$ satisfies "$L$ is well founded", but such that $L$ is not actually well founded. Then $M$ believes that there is a set $H$ which is obtained by iterating the Turing jump along $L$ starting with $\emptyset$, because this is provable in $\mathsf{ATR}_0$.

Because $M$ is an $\omega$-model, it is absolute for statements of the form "$A' = B$" when $A,B \in M$. Thus, if we take an infinite descending sequence $(a_i : i \in \omega)$ in $L$, and let $(A_i : i \in \omega)$ be the corresponding sequence of sets in $H$, then $A_{i+1}' \leq_T A_i$ for all $i \in \omega$.

This method can be easily extended to stronger results -- for example we could make $A_{i+1}^{(\omega)} \leq_T A_i$.


The use of $\mathsf{ATR}_0$ is not really necessary here. The key point is that there is a linear ordering $L$ of $\omega$, that is not a well ordering, for which there is a set $H^L$ that satisfies the arithmetical definition of being the iteration of the Turing jump along $L$ starting with the empty set. This kind of set $H^L$ is known more generally as a "pseudohierarchy".

The existence of a suitable $L$ follows immediately from the standard fact that the set of well orderings of $\omega$ is not $\Sigma^1_1$ definable. The statement "$L$ is a linear order and $H(L)$ exists" is a $\Sigma^1_1$ formula with parameter $L$, which is satisfied by every well ordering of $\omega$, so it must also be satisfied by some other set $L$; this $L$ will satisfy the "key point" statement in the previous paragraph.

$\endgroup$
1
  • 2
    $\begingroup$ Very nice, Carl! So easy and clear, especially the method of the last paragraph. $\endgroup$ Commented Jul 9, 2014 at 19:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .