7 Classification of jump operators

The Turing jump operator x ↦ x′ is degree invariant, i.e. if x ≡T y then x′ ≡T y′. The property of degree invariance is a fundamental property of the operator that motivated the introduction of Martin’s conjecture (§ 6.6.5). In this chapter we discuss a stronger one called uniform degree invariance and give a classification of functions that satisfy this property.

7.1 Uniformly degree invariant functions

Definition 7.1.1.

–If e = 〈e0, e1〉, we say that x ≡T y via e if x = and y = ;

–a function F : 2ω → 2ω is uniformly degree invariant on a cone C = {x | x ≥T z} with base z if there is a function t : ω → ω such that for any x, y ≥T z with x ≡T y via e, we have F(x)≡T F(y) via t(e).

Note that in the definition above, the value of t(e) is independent of the reals x, y.

In 1967, Sacks made a conjecture on the existence of a degree invariant function x ↦ Wx for a general solution of Post’s problem. This conjecture contradicts Martin’s conjecture since the latter asserts that any such function must be at least as strong as the jump operator:

Conjecture 7.1.2 (Sacks[119]). There is a -predicate W ⊆ 2ω × ω such that, if Wx = {n | W(x, n)}, then x <T Wx < x′ and for any y ≡T x, Wx ≡T Wy.

In 1975, Lachlan [80] proved that this conjecture failed for uniformly degree invariant W.

7.1.1 Nonincreasing uniformly degree invariant functions

Uniformly degree invariant functions are well-behaved under ZF + DC + AD. The following theorem says that a uniformly degree invariant function is either a constant or increasing on a cone.

Theorem 7.1.3. (Slaman and Steel [142]). Assume ZF + DC + AD. If F is uniformly degree invariant and not increasing on a cone, then F is a constant on a cone.

We decompose the proof of Theorem 7.1.3 into a series of lemmas. Let F be uniformly degree invariant via t and not increasing on a cone.

Lemma 7.1.4. Assume ZF+DC+AD. If F is uniformly degree invariant and nonincreasing on a cone, then F(x) <T x on a cone.

Proof. Suppose that F is uniformly degree invariant and not increasing on a cone. Then the set {x | F(x) ≱T x} is cofinal in the Turing degrees. By Proposition 6.6.5, there is a pointed tree T such that F is uniformly degree invariant on T via a function t : ω → ω and F(x) ≱T x for any x ∈ [T].

Given x, let x+(i) = x(i + 1) for i < ω. Let A ⊆ ωω be such that x = x0 ⊕ x1 ∈ A if and only if either ∉ 2ω or

– ∈ 2ω;

–x0(0) = 〈e, n〉 for some e, n < ω;

–either x0 ≰T x1 or F()(n) = 0 ⇔ x1(x1(0)) ≠ 0 and

– ∈ [T] ∧ = x1.

Consider a two person game played by I and II, choosing numbers alternately as usual. By AD, either I or II has a winning strategy for . Suppose that I has a winning strategy . We show that x ≤T F(x) on the cone above T ⊕ , which will give a

Let z0 ≥t T ⊕ and = m⌢z0 for m < ω. Let be the real in [T] played by I in response to II playing , i.e. () = 〈e0, n0〉⌢, where 〈e0, n0〉 codes the pair of numbers e0, n0 and () = 〈e0, n0〉 is the first move dictated by . Since I wins, xm = ⊕ ∈ A for every m. As ≥T , we have ≥T . Then for every m,

F(()+)(n0) = 0 ⇔ (m) = 1.

Since = and = m⌢z0, there is an i such that = ( for every m. Similarly, there is a j such that = ()+ for every m. Hence for each m, ()+ ≡T ( via 〈i, j〉, and so F(()+)≡T F(() via t(i, j) = 〈i′, j′〉. Since F is degree invariant and z0 ≡T ≡T ()+, we have = F(()+) for some k. Let lm = F(()+)(n0). Note that F(()+) = and F(() = . So {lm}m∈ω is F(z0)-recursive. Note that z0(m) = (m + 1) = 1 − lm+1. Thus z0 ≤T F(z0), a contradiction.

Hence II has a winning strategy . We show that F(x)<T x on the cone above T ⊕ . Fix a real x0 ∈ [T] so that x0 ≥T T ⊕ . By the Recursion Theorem relativized to x0, there is an e0 such that (〈e0, n〉⌢x0)(m) = (〈n, m〉) for every n, m. For each n, let = (〈e0, n〉⌢x0). Since II wins, it must be the case that x0 ≤T and F()(n) = ((0)). Then

F()(n) = ((0)) = (〈n, (〈n,0〉)〉)

and so F(x0) ≤T x0. Since F is degree invariant, we conclude that F(x) <T x on a cone.

By Lemma 7.1.4, fix x0 such that F(x) <T x on the cone {x | x ≥T x0}. Then there is an e0 such that the set C = {x | 0 = F(x) ∧ x ≥T x0} is cofinal. By Proposition 6.6.5, there is a perfect tree T0 and a number i such that [T0] ⊆ C and T0 = for every x ∈ [T0].

Lemma 7.1.5. There exists a perfect tree T1 ⊆ T0 such that T1 ≤T T0 and F is either injective or a constant on [T1].

Proof. If there exists a σ ∈ T0 such that 0 = for all x, y ∈ [T0] ∩ [σ], then let T1 = T0 ∩ {τ ∈ 2<ω | τ ≻ σ}. Obviously F is a constant on [T1]. Otherwise, T0-recursively finds a perfect subtree T1 ⊆ T0 such that F is injective on [T1].

By Lemma 7.1.5, we may assume that F is injective on T0.

Let

Then S0 is a T0-recursive perfect tree so that Φe0 is a homeomorphism from [T0] to [S0].

Since T0 is perfect, let p : 2<ω → T0 be an order-preserving, T0-recursive bijection. Then p may be viewed as a homeomorphism from 2ω to [T0]. Let π : 2<ω → 2<ω be a recursive function such that for any σ and i < 2, π(σ⌢i) = π(σ)⌢i if σ ≠ and σ(j) = 1 for some j <|σ|; else π(σ⌢i) = σ⌢(1 − i) . Then π can be viewed as a homeomorphism from 2ω to 2ω by letting π(x) = n π(x ↾ n). Let

p0 = p ∘ π ∘ p−1.

Then p0 is a homeomorphism from T0 to T0. We leave it to the reader to verify the following lemma.

Lemma 7.1.6. For any σ, {π(n)(σ)}n<2|σ| is a permutation of 2|σ|.

Let p1 = F∘p0∘F−1 be a homeomorphism from [S0] to [S0] and fix an x0 ∈ [T0]. Since T0 is uniformly pointed, there is a pair (i0, j0) such that for any n, (x0) ≡T (x0) via (i0, j0). Then F((x0)) ≡T F((x0)) via (i1, j1) = t(i0, j0). Note that for any n, F((x0)) = (F(x0)). So the real ⊕n<ω(F(x0)) is recursive in (x0) = F(x0).

Given a perfect tree T and a number n, we say that a finite tree S ⊆ T codes a 2n copy of T if

–S is isomorphic to 2n;

–for any τ ∈ T S, there exists an end node σ ∈ S such that τ ≻ σ.

Lemma 7.1.7. S0 is recursive in F(x0).

Proof. Note that we may view F : [T0] → [S0] as a homeomorphism. Hence for any σ, there is an m such that p−1(F−1((F(x0)↾ m))) is of length 2|σ|. By Lemma 7.1.6, {π(n)(p−1(F−1((F(x0)↾ m))))}n<2|σ| is a permutation of 2|σ|. Since both F and p are homeomorphisms, the finite tree

codes a 2|σ| copy of S0.

Thus σ ∈ S0 if and only if σ ∈ . Obviously can be effectively computed from {(F(x0))}n<2|σ|. Hence S0 ≤T F(x0).

This shows that S0 is a pointed tree. Then there exists an x1 ∈ [S0] such that T0 ⊕ S0 ≤T x1. Since Φe0 is a homeomorphism from T0 to S0, it is not difficult to see that the unique real y ∈ [T0] such that = x1 is recursive in x1. In other words, F(y) = x1 ≥T y, a contradiction.

7.1.2 Exercise

Exercise 7.1.1. Prove Lemma 7.1.6.

7.2 Martin’s conjecture for uniformly degree invariant functions

The results discussed in this section are due to Steel [159].

Lemma 7.2.1. Assume ZF + AD + DC. Then ≤M is a linear ordering on the collection of functions which are increasing and uniformly degree invariant.

Proof. Suppose that F and G are increasing uniformly degree invariant functions via t on a cone {x | x ≥T z0}. Define a set A ⊆ ωω so that x0 ⊕ x1 ∈ A if and only if either ∉ 2ω or

– ∈ 2ω;

– = where x0(0) = 〈e0, n0〉, and

–either ≠ or n0 ∈ F() ⇔ n1 ∉ G() where x1(0) = 〈e1, n1〉.

Consider a two person game played by I and II on A, with I playing 〈e0, n0〉 as the first move. Suppose that I has a winning strategy for . Fix areal y ≥T ⊕ z0 ⊕ t. By the Recursion Theorem relativized to y, for any number m, there is an such that = (())+ where = (〈, m〉)⌢y. Note that the function m ↦ is recursive. Let = () and (0) = 〈, 〉. Note that the function m ↦〈, 〉 is y-recursive (actually a constant function). Since is a winning strategy for I, = y and

Note that ()+ ≡T y via (, ), and so we have F(()+) ≡T F(y) via t(, ) = (, ). Since F(y) ≥T y, t ≤T y and m ↦ (, ) is y-recursive, the function m ↦ (, ) is F(y)-recursive. Then for any m, we may F(y)-recursively find and such that () = F(()+)() = 1 − G(y)(m). Hence G(y) ≤T F(y) and so G ≤M F.

If II has a winning strategy, then by a similar argument one shows that F ≤M G. Given x and y, we say that x ≡m y via (e0, e1) if there are two recursive functions Φe0 and Φe1 such that for any n,

–n ∈ y ⇔ Φe0(n) ∈ x; and

–n ∈ x ⇔ Φe1(n) ∈ y.

Lemma 7.2.2. Assume ZF+AD+DC. If F and G are increasing uniformly degree invariant functions via t such that F <M G, then F′ ≤M G.

Proof. Suppose that F <M G on the cone {x | x ≥T z0} but F′ ≰M G. Let p : 2<ω → ω be a recursive bijection and for any x, let G1(x) = y where

y = {n |(∀m)(p(G(x)↾ m) ≠ n)}.

Then for each x, G1(x) ≡T G(x). Moreover, since G is uniformly degree invariant, so is G1.

We apply the same method as that in Lemma 7.2.1. Define A ⊆ ωω such that x0 ⊕ x1 ∈ A if and only if either ∉ 2ω or

– ∈ 2ω

– = where x0(0) = 〈e0, n0〉, and

–either ≠ or n0 ∈ F′() ⇔ n1 ∉ G1(), where x1(0) = 〈e1, n1〉.

A game is played by the two players I and II. As in Lemma 7.2.1, if II has a winning strategy for , then F′ ≤M G1 which is a contradiction.

Hence I has a winning strategy for . Fix y ≥T ⊕ z0 ⊕ t. By the Recursion Theorem relativized to y, for each m there is an such that = (())+ where = 〈, m〉⌢y. Note that the function m ↦ is recursive. Let = () and (0) = 〈, 〉. The function m ↦〈, 〉 is y-recursive. Since is a winning strategy for I, = y and

Note that ()+ ≡T y via (, ). We then have F(()+) ≡T F(y) via t(, ) = (, ). Since t ≤T y and m ↦ (, ) is y-recursive, the function m ↦ (, ) is y-recursive as well. Hence there is a y-recursive function m ↦ (jm0, jm1) such that F′(()+) ≡m F′(y) via (, ). Thus for any m, one may y-recursively find and an such that

Since F(y) ≥T y, the set E1 = {m | F′(y)(()) = 1} is infinite and F(y)-r.e. Let E2 ⊆ E1 be infinite F(y)-recursive. Then for any m ∈ E2, there is an nm such that p−1(m) = G1(y)↾ nm. Thus G(y)≤T F(y) and so G ≤M F, contradicting the hypothesis. We conclude that F ′ ≤M G.

Now suppose that there is a ≤M-sequence {Fn}n<ω such that for each n,

(a)Fn is uniformly degree invariant via tn, and

(b)Fn+1 <M Fn on the cone {x | x ≥T zn}.

Let z = ⊕n<ωzn and t(n, e0, e1) = tn(e0, e1). For each n, we define sets An and Bn for the pair (Fn+1, Fn) to be the corresponding set A in Lemma 7.2.1 and Lemma 7.2.2 respectively. Then for every n, I has a winning strategy n for and II has a winning strategy n for . Let y = z ⊕ t ⊕ (⊕n<ω n) ⊕ (⊕n∈ω n). Then as in the proof of Lemma 7.2.1, there is a y-arithmetical relation P(x0, x1) such that for any n, Fn+1(y) is the unique real x for which P(x, Fn(y)) holds. Note that by Lemma 7.2.2, F ′n+1(y)≤T Fn(y) for every n.

Proposition 7.2.3. (Steel [157]). Let R ⊆ 2ω × 2ω be an arithmetical relation. If {xn}n<ω is a sequence of reals such that xn+1 is the unique y satisfying R(y, xn), then for some n, ≰T xn.

Proof. Suppose for the sake of contradiction that ≤T xn for each n. Define

By assumption on the sequence {xn}n<ω, for any n we have

(∀i)(∀j)(P(xn, i, j) ⇔ (∃k > j)(i ∉ (xn+k)(j+1))).

Since P is arithmetical, there exist m and e such that

Then for any n, i, j,

Setting j = m, there is an e0 such that for every i,

When i = e0, we have for any n,

Thus e0 ∈ (x0)(m+1) if and only if (∃k0 > m+1)(e0 ∉ (xk0)(m+1)), and e0 ∈(xk0)(m+1) if and only if(∃k1 > m + 1)(e0 ∉ (xk0+k1)(m+1)). Then e0 ∈ (x0)(m+1) if and only if e0 ∈ (xk0+k1)(m+1). By the equivalence above again, e0 ∈ (x0)(m+1) if and only if e0 ∉ (x0)(m+1), a contradiction.

Relativizing Proposition 7.2.3 to y, there is an n such that Fn+1(y)′ ≰T Fn(y), which contradicts our assumption on the sequence {Fn}n<ω and Lemma 7.2.2. We therefore have:

Lemma 7.2.4. Assume ZF+AD+DC, the partial order ≤M on increasing uniformly degree invariant functions is well-ordering.

In conclusion, we have the following theorem.

Theorem 7.2.5. (Steel [159], Slaman and Steel [142]). Assume ZF + AD + DC, Martin’s conjecture (6.6.9) holds for uniformly degree invariant functions.

Remark 7.2.6. H. Friedman [30] proved that there is a hyperarithmetic predicate R and a sequence {xn}n<ω such that ≤T xn and xn+1 is the unique y satisfying R(y, xn).

7.2.1 Exercises

Exercise 7.2.1. Prove that there exists an arithmetical predicate P such that for any n > 0, there exists a sequence {xj}i≤n satisfying: (i) for any i<n, ≤T xi, (ii) P(xi+1, xi) and (iii) if P(y, xi) then y = xi+1.

Exercise 7.2.2. Prove that there is an arithmetical predicate R and a <h-descending sequence {xn}n<ω such that for any n, xn+1 is the unique real y satisfying R(y, xn).

7.3 The Posner–Robinson Theorem

7.3.1 The original Posner–Robinson Theorem

Theorem 7.3.1. (Posner and Robinson [114]). For any nonrecursive x ≤T ′, there is a g such that x ⊕ g ≡T g′ ≡T ′.

Thus given a nonrecursive -real x, Theorem 7.3.1 says that there is a g relative to which x is its Turing jump.

Proof. To prove this, we use a method due to Jockusch and Shore [57]. Fix x >T to be . We may assume that x is not r.e. For every e, consider the following statement:

Since x is not r.e., (♯e) is true for every e. We construct g by induction.

Step 0: Define g0 = .

Step s + 1:

Substep 1. Define g(s, 1) = .

Substep 2. Find the least n such that either

or

By (♯s), such an n exists. In the first case, define gs+1 = g(s, 1)⌢0n1. In the second case, select the lexicographically least τ such that τ ⪰ g(s, 1)⌢0n1((s)[|τ|] ↓). Define gs+1 = g(s, 1)⌢τ.

Let g = s<ω gs. Note that the construction is uniformly x ⊕ ′-recursive. Hence ′ ≥T g ⊕ x. We show that ′(s) and gs are uniformly g ⊕ x-recursive. Suppose we have computed gs and ′(s). Then ′(s + 1) = g(|gs|+ 1). To compute gs+1, search for the unique n such that (g ↾|gs|+ 1)⌢0n1 ≺ g. By the construction, either

(1)n ∈ x or

(2)n ∉ x and there is a τ ⪰(g ↾|gs|+ 1)⌢0n1 such that τ ≺ g and (s)[|τ|] ↓.

If (1) holds, then g(s + 1) =(g ↾|gs|+ 1)⌢0n1. If (2) holds, then there is a unique τ ⪰ (g ↾|gs|+ 1)⌢0n1 such that τ ≺ g and (s)[|τ|] ↓. It follows that gs+1 = τ.

Thus ′ ≡T g ⊕ x.

To prove g′ ≤T g⊕′, observe that for every e there is an n such that either Φg↾ne(e)↓ or (e)↑ for any τ ≻ g ↾ n. Using this, one verifies immediately that g′ ≤T g ⊕ ′.