Turing Degrees of Hyperjumps

2021/01/21 by Jananthan, Hayden R., Simpson, Stephen G.
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2101.08818

Abstract

The Posner-Robinson Theorem states that for any reals Z and A such that Z ⊕ 0' ≤_T A and 0 <_T Z, there exists B such that A ≡_T B' ≡_T B ⊕ Z ≡_T B ⊕ 0'. Consequently, any nonzero Turing degree deg_T(Z) is a Turing jump relative to some B. Here we prove the hyperarithmetical analog, based on an unpublished proof of Slaman, namely that for any reals Z and A such that Z ⊕ O ≤_T A and 0 <_HYP Z, there exists B such that A ≡_T O^B ≡_T B ⊕ Z ≡_T B ⊕ O. As an analogous consequence, any nonhyperarithmetical Turing degree deg_T(Z) is a hyperjump relative to some B.

Related

• Post's problem for supertasks has both positive and negative solutions
• A fixed point for the jump operator on structures
• Determinacy and Fast-growing Sequences of Turing Degrees
• DNR and incomparable Turing degrees
• A computability theoretic equivalent to Vaught's conjecture