Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
2  
Very nice, Carl! So easy and clear, especially the method of the last paragraph. –  Joel David Hamkins Jul 9 at 19:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.