7.3.2 A transfinite Posner–Robinson Theorem

Theorem 7.3.1 may be iterated into the transfinite in several different ways. Here is the first version.

Theorem 7.3.2. (Slaman and Steel [142]). Let 0 < and let z be a real such that (γ) <T z for each γ<β. Then there is a g such that g ⊕ z ≡T g(β).

The rest of the section is devoted to a proof of Theorem 7.3.2.

Let a ∈ . The first step is to introduce an enumeration of arithmetical predicates indexed by |a|. By Theorem 1.3.4, the set {b | b <o a} is r.e. Applying the Recursion Theorem, we may assume that there is a partial recursive function Φ : ω2 → ω such that for each b <o a, {Φ(b, i)}i<ω is an enumeration of the set of Gödel numbers of “-predicates”. To simplify notations, we identify a predicate with its Gödel number.

We introduce an enumeration of -predicates by induction. The enumeration of -predicates is standard. If b = 2c ∈ and b <o a, then a predicate P(x, n) is the i-th -predicate, or P(x, n) = PΦ(b,i)(x, n), if P(x, n) ⇔ (∃m)¬Q(x, 〈n, m〉) where Q(x, 〈n, m〉) is the i-th -predicate.

If b = 3 ⋅ 5e ∈ and b <o a, then a predicate P(x, n) is the i-th -predicate, or P(x, n) = PΦ(b,i)(x, n), if P(x, n) ⇔ PΦ(p(Φi(n)))(x, n), where p(Φi(n)) =(i0(n), i1(n)) so that i0(n)<o b for every n. The next lemma is proved by induction on the notation of b and is left to the reader.

Lemma 7.3.3. There exist recursive functions f : ω → ω and g : ω → ω2 such that for any b <o a,

(i)if b = 1 or 2c, then PΦ(b,f(b)) ≡T via g(b);

(ii)if b = 3 ⋅ 5e <o a, then PΦ(b,f(b)) ≡T via g(b).

We now define a notion of Cohen forcing over -predicates for b <o a. If P(x, n) is a -predicate, then there is a partial recursive function Φx(n) such that P(x, n) ⇔ Φx(n)↓. Define σ ⊩ P(x, n) if and only if Φσ(n)↓.

If b = 2c ∈ , b <o a, and P(x, n) is , then P(x, n) ⇔ (∃m)¬Q(x, 〈n, m〉). Define σ ⊩ P(x, n) ⇔ (∃m)(σ ⊩ Q(x, 〈n, m〉)).

If b = 3 ⋅ 5e ∈ , b <o a, and P(x, n) is a -predicate, then P(x, n) ⇔ PΦ(p(Φi(n)))(x, n) for some i. Define σ ⊩ P(x, n) ⇔ σ ⊩ PΦ(p(Φi(n)))(x, n).

Given b <o a, if P(x, n) is a -predicate, then σ ⊩¬P(x, n) ⇔ (∀τ ≻ σ)(τ ⊭ P(x, n)).

The verification of the following lemma is also left to the reader.

Lemma 7.3.4. There is a partial recursive function h : ω2 × 2 → ω such that for any b <o a,

(i)if b = 1 or 2c, then (∀n)(∀m)((σ ⊩ PΦ(b,n)(x, m) ↔ (σ, m) = 1) ∧ (σ ⊩¬PΦ(b,n)(x, m) ↔ (σ, m) = 0));

(ii)if b = 3 ⋅ 5e, then (∀n)(∀m)((σ ⊩ PΦ(b,n)(x, m) ↔ (σ, m) = 1) ∧ (σ ⊩¬PΦ(b,n)(x, m)↔ (σ, m) = 0)).

A real g is a-generic if for any b <o a and -predicate P(x, n) there is an m such that either g ↾ m ⊩ P(x, n) or g ↾ m ⊩¬P(x, n). This yields the following truth lemma:

Lemma 7.3.5. Suppose that g is a-generic. For any m, n and b <o a, PΦ(b,n)(g, m) if and only if there is a k such that g ↾ k ⊩ PΦ(b,n)(x, m), and ¬PΦ(b,n)(g, m) if and only if there is a k such that g ↾ k ⊩¬PΦ(b,n)(x, m).

Lemma 7.3.6. If g is a-generic, then there is a partial recursive function r such that for any b <o a

–if b = 1 or 2c, then = ;

–if b = 3 ⋅ 5e, then = .

Proof. We give the proof for the case when the notation of b is a successor, and leave the limit case to the reader.

If b = 1, then by Lemma 7.3.3, n ∈ if and only if PΦ(1,n)(g, n). By Lemma 7.3.5, there exists a k such that either g ↾ k ⊩ PΦ(1,n)(g, n) or g ↾ k ⊩¬PΦ(1,n)(g, n). By Lemma 7.3.4, this is decidable by (g ↾ k, n). Hence = for some i. Let r(1) = i.

If b = 2c, then by Lemma 7.3.3, n ∈ if and only if PΦ(b,n)(g, n). By Lemma 7.3.5, there exists a k such that either g ↾ k ⊩ PΦ(b,n)(g, n) or g ↾ k ⊩¬PΦ(b,n)(g, n). Since PΦ(b,n)(g, n) ⇔ (∃m)PΦ(c,n)(g, n, m), we have

(∃m)(g ↾ k ⊩ PΦ(c,n)(g, n, m))) ∨ (∀τ ≻ g ↾ k)(∀m)(τ ⊭¬PΦ(c,n)(g, n, m))).

By Lemma 7.3.4, this is decidable by either g ⊕ = g ⊕ H2b (c = 2d for some d) or g ⊕ ≤T g ⊕ H2b (c = 3 ⋅ 5e for some e). Hence = for some i, a number which may be effectively computed from b. Let r(b) = i.

We are now ready to prove Theorem 7.3.2. We establish the case where β is a successor ordinal and leave the limit case to the reader.

Let a ∈ so that |a|= β. Fix z >T Hb for all b <o a. We may assume that z is not r.e. in Hb for any b <o a. Given b <o a and i, j<ω, consider the following statement:

Since z is not r.e. in Hb for b <o a, by Lemma 7.3.4, (♯b,n) is true for every b <o a and n<ω. We construct g in stages as the union of the sequence {gs}s<ω ⊆ 2<ω with g0 ≺ g1 ≺ g2 ≺ ….

Let {〈bs, 〈is, js〉〉}s<ω be an enumeration of {b | b <o a} × ω2.

Stage 0: Let g0 = .

Stage s + 1:

Substage 1. Define g(s, 1) = gs⌢z(s)⌢Ha(s).

Substage 2. Define g(s, 2) = g(s, 1)⌢0〈b s ,〈is ,js〉〉1.

Substage 3.

Case (i): 2bs ≠ a. Define g(s, 3) = g(s, 2)⌢0es 1 where es is an index so that = (bs = 2c for some c) or = (bs = 3 ⋅ 5e for some e).

Case (ii): 2bs = a. Let g(s, 3) = g(s, 2)⌢0es 1 where es is an index such that = (bs = 2c for some c) or = (bs = 3 ⋅ 5e for some e).

Substage 4. Find the least n such that either

n ∈ z ∧ g(s, 3)⌢0n1 ⊩¬PΦ(bs,is)(x, js)

or

n ∉ z ∧ (∃τ ⪰ g(s, 3)⌢0n1)(τ ⊩ PΦ(bs,is)(x, js)).

By (♯bs,〈is,js〉), such a number n exists. If it satisfies the first half of the disjunction, define gs+1 = g(s, 3)⌢0n1. Otherwise, select the lexicographically least τ such that τ ⪰ g(s, 3)⌢0n1 and τ ⊩ PΦ(bs,is)(x, js)). Define gs+1 = g(s, 3)⌢τ.

Let g = s<ω g.

It is clear that g is a-generic. By Lemma 7.3.6, ≡T g ⊕ Ha. By Lemma 7.3.4, the construction can be decoded by g ⊕ Ha. So z ⊕ g ≤T g ⊕ Ha ≡T .

To prove that z ⊕ g ≥T , it is sufficient to decode the construction by z ⊕ g and compute Ha. To do this, we go through the same steps as in the proof of Theorem 7.3.1. Suppose we know gs. Then z(s + 1) = g(|gs| + 1) and Ha(s) = g(|gs|2). Then one obtains (bs, is, js) by calculating g(s, 2). By calculating g(s, 3), we find an es such that computes the set {(σ, is, js)| σ ⊩ PΦ(bs,is)(x, js)}. To compute gs+1, search for the unique number n such that (g ↾|g(s, 3)|)⌢0n1 ≺ g. By the construction, either

(1)n ∈ z or

(2)n ∉ z and there is a τ ⪰ g(s, 3)⌢0n1(τ ⊩ PΦ(bs,is)(x, js)).

If (1) holds, then gs+1 = (g ↾|g(s, 3)|)⌢0n1. If (2) holds, then there is a unique τ ⪰ g(s, 3)⌢0n1such that τ ⊩ PΦ(bs,is)(x, js). We may use to find the τ. Then gs+1 = τ and we conclude that z ⊕ g ≥T Ha.

7.3.3 Further generalizations

Another generalization of the Posner–Robinson Theorem (7.3.1) into the transfinite is as follows:

Theorem 7.3.7. (Shore and Slaman [134]). For any recursive ordinal β, if x ≰T (γ) for γ < β, then there is a g such that x ⊕ g ≡T g(β).

Theorem 7.3.7 is proved by a forcing argument (Kumabe–Slaman forcing) different from Cohen forcing, and is used to show the definability of the complete Turing degree 0′ (see Exercise 7.3.3). On the other hand, it is possible to extend Theorem 7.3.1 beyond recursive ordinals. This was shown by Woodin using a set-theoretic argument:

Theorem 7.3.8. (Woodin [169]). If z is not hyperarithmetic, then there is a g such that z ⊕ g ≡T g.

7.3.4 Exercises

Exercise 7.3.1. Prove Lemma 7.3.3 and Lemma 7.3.4.

Exercise 7.3.2. Prove, without using Theorem 7.3.8, that if x >T (β) for β < , then there is a g such that x ⊕ g ≥T g(β) for all β < .

Exercise 7.3.3 (Shore and Slaman [134]). Using Theorem 7.3.7, prove that if for some n > 1, the function x ↦ x(n) is definable in 〈, ≤〉 where is the collection of Turing degrees, then the function x ↦ x′ is also definable in 〈, ≤〉.

7.4 Classifying order-preserving functions on 2ω

We say that f : 2ω → ω1 is degree invariant if x ≡T y implies f(x) = f(y).

Lemma 7.4.1. Suppose that f : 2ω → ω1 is degree invariant and f(x) < on a cone. Then f is a constant on a cone.

Proof. Suppose that f : 2ω → ω1 is Turing invariant and f(x) < on {x | x ≥T z0}. For any e, let Ae = {x | x ≥T z0 ∧ is a well-ordering of order type f(x)}. Then there is an e0 such that Ae0 is cofinal. By Proposition 6.6.5, there is a pointed tree T0 such that x ∈ Ae0 for x ∈ [T0]. We claim that there is a countable ordinal α0 such that f(x) < α0 for x ∈ [T0]. Otherwise for any x, x ∈ WO1 if and only if there exists a y ∈ [T0] and an order-preserving function f from x into . In other words, WO1 is (T0), a contradiction.

By Proposition 6.6.5 again, there is a pointed tree T1 ⊆ T0 and a countable ordinal α1 < α0 such that f(x) = α1 for any x ∈ [T1].

If F : 2ω → 2ω is degree invariant, then it is order preserving if for any x ≤T y, F(x) ≤T F(y).

Theorem 7.4.2. (Slaman and Steel [142]). Assume ZF+AD+DC. Suppose that F : 2ω → 2ω is order preserving and increasing on a cone. Then either

(i)there is an α<ω1 such that on a cone, F(x)≡T x(α), or

(ii)on a cone, F(x) <T x(α) for any α < .

Proof. Assume that F is increasing on the cone C. If (ii) is not true for F, then by Lemma 7.4.1 and Proposition 6.6.5, there exists an ordinal α < ω1 such that x(α) ≮T F(x) on a cone C1 ⊆ C. Let α0 be the least such ordinal. Then F(x)>T x(β) for any β < α0. We may assume that > α0.

Let x0 ∈ C1. By relativizing Theorem 7.3.2 to x0, there is a y ≥T x0 such that y ⊕ F(x0) ≡T y(α0). Since F is order preserving and increasing, F(y) ≥T y ⊕ F(x0) ≡T y(α0). Thus F(y) ≡T y(α0). It follows that the set {x | F(x)≡T x(α0)} is cofinal. By Proposition 6.6.5 again, F(x) ≡T x(α0) on a cone.

7.4.1 Exercise

Exercise 7.4.1. Assume ZF + AD + DC. Suppose that F is order preserving and increasing on a cone. Then either

(i)(∃α<ω1)(F(x)≡T x(α)) on a cone, or

(ii)F(x) ≥T x on a cone.

7.5 Pressdown functions

A function F : 2ω → 2ω is pressdown on a cone C if F(x) <T x for x ∈ C. By Theorem 7.1.3, every uniformly degree invariant function that is pressdown on a cone is a constant on a cone. We prove in this section a stronger result.

Theorem 7.5.1. (Slaman and Steel [142]). Assume ZF+AD+DC. If F is a degree invariant pressdown function on a cone, then F is constant on a cone.

Proof of Theorem 7.5.1. Suppose that F is a degree invariant pressdown function on a cone C = {x | x ≥T z} for some z. By Proposition 6.6.5, there is an e0 and a pointed tree T such that F(x) = 0 for all x ∈ [T]. By Lemma 7.1.5, we may assume that Φe0 is a homeomorphism from [T] to a perfect set [S].

Without loss of generality, we may assume that for any splitting node σ ∈ T, is incompatible with . The plan is to find two reals x0, x1 ≤T T in [T] such that ⊕ ≥T T. Since F is degree invariant and T is pointed, F(x0 ⊕ x1) ≡T F(x0) ≡T F(x0) ⊕ F(x1) ≥T T ≡T x0 ⊕ x0. Then we have a contradiction to the assumption that F(x) <T x on C. The following lemma says that for x ∈ [T], the growth rate of any function h ≤T x is controlled by F(x).

Lemma 7.5.2. Suppose that x ∈ [T] and h ≤T x. For each e, let le be a function recursive in so that

le(0) = 0

and

Then there is an e such that le is total and (∃m)(∀n ≥ m)(h(le(n)) < le(n + 1)).

Proof. Without loss of generality, we may assume that h is increasing. Suppose that the lemma is false. We construct a real y ≤T x in [T] such that ≱T . By shrinking T if necessary, we may assume that x ≤T T. Since T is pointed, we have y ≡T x but ≱T , a contradiction.

The construction is by full approximation recursive in x. We shall construct an x-recursive sequence σ0 ≺ σ1 … and let y = s<ω σs. At any stage s, we may declare a number e to be discarded.

Let σ0 = .

At stage s + 1, let τ ≻ σs be the immediate splitting node in T so that (ks)↓ ≠ (ks)↓ for some ks. For i ≤ 1, let τi ≻ τ⌢i be the next immediate splitting node in T so that ≠ for some > ks.

Search for the least e ≤ s which has not been discarded and

If there exists such an e, then let σs+1 = τ⌢i where i is the least number such that

and discard e. Otherwise, let σs+1 = σs.

Clearly y ≤T x. Suppose that = for some e. By the assumption, for any m there exists an n ≥ m such that h(le(n)) ≥ le(n + 1). Let s0 be a stage large enough so that no e′ ≤ e is discarded after s0. Then there is a least n >|σs0|+ s0 such that h(le(n)) ≥ le(n + 1). Let s1 be the largest stage ≥ s0 so that ks1 ≤ le(n). Then at stage s1 + 1, either or is greater than le(n). Hence |τ0|+|τ1|> le(n). Since ks+1 ≤ le(n + 1), we have (ks)[h(|τ0| + |τ1|)] ↓. In other words, e is discarded at stage s1 + 1.

Let t be a T-recursive increasing function such that for any k and σ ∈ 2t(k)∩T, || = k. Let π : ω<ω → T be a function defined by induction as follows:

–π() = σ where σ is the splitting node in T such that every τ ∈ T is compatible with σ;

–(∀σ)(π(σ⌢i) = π(σ)⌢τ), where π(σ)⌢τ is a splitting node in T for which there is a finite sequence π(σ) = σ0 ≺ σ1 … σt(i) ≺ τ such that for each j ≤ t(i), σj is the immediate splitting node extending σj−1⌢0in T and τ is the next immediate splitting node in T extending σt(i)⌢1.

Hence π induces a T-recursive continuous injection from ωω to [T] so that for each h ∈ ωω, π(h) ≡T T ⊕ h.

By Lemma 7.5.2, for each h, there is a least eh for which one chooses the least mh such that

(∀n ≥ mh)(h(leh (n)) < leh (n + 1)).

Note that the function h ↦ (eh, mh) is (T). Thenforeachpair (e, m), the set

He,m = {h |(eh, mh) =(e, m)}

is a Borel set and therefore has the Baire property. Then there is a pair (e1, m1) such that He1,m1 is not meager. In other words, there is a u ∈ ω<ω such that for any τ ≻ u, there is an h ∈ He1,m1 with h ≻ τ. Now for any σ ∈ ω<ω, we T-recursively define a finite function lσ so that

lσ() = 0

and

For h ∈ ωω, let lh(n) = k if there exists an m such that lh↾m(n) = k. The proof of the following lemma is straightforward.

Lemma 7.5.3.

(i)(∀σ)(∀i)(∀k)(|σ|> k ∧ k = lσ(i) ⇒ lσ↾k(i) = k);

(ii)(∀τ ⪰ u)(∀n)(n ≥ m1 ∧ lτ(n)≥|τ| ⇒ n + 1 ∉ Dom(lτ)).

Proof. (i) If |σ|> k and k = lσ(i), then |π(σ)| ≥ t(|σ|) ≥ t(k). Then || = k. Thus lσ↾k(i) = k.

If (ii) is not true, then there exists a τ ≻ u and n ≥ m1 such that lτ(n)≥|τ| and lτ(n + 1) is defined. Then τ(lτ(n)) is undefined. By the assumption on u, there is an h ≻ τ in He1,m1 such that h(lh(n)) > lτ(n + 1) = lh(n + 1), a contradiction.

Let x ≡T T, m2 ≥ m1 and h ≻ u so that lh(m2) is defined. Let τ0 = τ1 = h ↾ lh(m2). By Lemma 7.5.3, lτ0(m2) is defined and |τ0| = lτ0(m2) (so lτ0(m2 + 1) is undefined). We T-recursively construct two sequences τ0 = ≺ … and τ1 = ≺ … as follows.

At stage s + 1, suppose that (m2 + s) is defined and || = (m2 + s) (hence (m2 + s + 1) is undefined) for i = 0, 1.

Case 1. x(s) = 0. Then by the assumption on u and Lemma 7.5.3, let ≻ so that (m2+s+1) is defined and || = (m2+s). Let τ = ()⌢((m2+s+1)+1). By the assumption on u and Lemma 7.5.3 again, let ≻ τ so that (m2 + s + 1) is defined and || = (m2 + s + 1). Note that by the assumption on u, there is an h ≻ in He1,m1. Hence by Lemma 7.5.3,

(m2 + s + 1) = lh(m2 + s + 1)≥ h(m2 + s + 1) = (m2 + s + 1)+ 1 > (m2 + s + 1).

Case 2. x(s) = 1. Do the same construction as in Case 1 but replace 0 by 1. We have

Let hi = s and xi = π(hi) ∈ [T] for i ≤ 1. Then x0 ≡T x1 ≡T T. Let li be le1 for xi as defined in Lemma 7.5.2. Then li ≤T for i ≤ 1. Moreover,

(∀i)((l1(m + i + 1)> l0(m + i + 1) ⇔ x(i) = 0) ∧ (l1(m + i + 1) < l0(m + i + 1) ⇔ x(i) = 1)).

Hence T ≡T x ≤T ⊕ .

The completes the proof of Theorem 7.5.1.

7.5.1 Exercises

Exercise 7.5.1. Prove that in Lemma 7.5.2 there is a pointed tree T1 ⊆ T such that for any x ∈ [T1], F(x)≥T (α) if α is recursive.

Exercise 7.5.2 (Slaman and Steel). Suppose that F : 2ω → 2ω is a pressdown degree invariant function. Then there exists a z0 such that for any z1, there is an x ≥T z1 such that F(x) ≱T z0.

Exercise 7.5.3 (Slaman). There is a continuous injection F : 2ω → 2ω such that for every x ≥T ′, F(x)′ ≡T x and for any x = ∗ y, F(x)≡T F(y), where =∗ denotes the finite difference relation.