Construction

Step 0. Define T0 = 2<ω and σ0 = .

Step n + 1. There are three substeps:

Substep 1 (Coding x). For each k, if x(n) = 0 then define = . Otherwise, let = . Define Tn+1,0,k = . Hence there is a recursive oracle functional Φik such that for each y ∈ Tn+1,0,k, Φyik = Tn+1,0,k. Note that the function k ↦ ik is recursive. It follows from the Recursion Theorem that there is a number k0 such that = for all y ∈ []. Fix this k0 and define = , and Tn+1,0 = Tn+1,0,k0.

Substep 2 (Coding xn). For each k, define

By the discussion above, there are recursive functions f, g so that = xn and = Tn+1,1,k for all y ∈ [Tn+1,1,k]. By the Recursion Theorem, there is a k1 such that = = Tn+1,1,k1 for all y ∈ [Tn+1,1,k1]. Define σn+1,1 = and Tn+1,1 = Tn+1,1,k1.

Substep 3 (Forcing a minimal cover). This is the only place where z″ is used.

Case 1. There exists a σ ∈ Tn+1,1 and a number iσ such that for all m > iσ, τ1, τ2 ⪰ σ, {τ1, τ2} ⊂ Tn+1,1 ∧ (m) ↓∧ (m)↓ implies (m) = (m). Choose the least such σ ∈ Tn+1,1 in the sense of the coding of strings. Define S = . For each k, define Sk = SR1(SLk(S)). By the Recursion Theorem again, there is a k2 so that = SR1(SLk2(S)) for all y ∈ [SR1(SLk2(S))]. Define σn+1 = R1(SLk2(S)) and Tn+1 = Sσn+1.

Case 2. Otherwise, for each k define Sk = . Then we can Sk-recursively find a subperfect tree Pk of Sk such that for all y ∈ [Pk], is total and for all τ0, τ1 ∈ Pk, if τ0|τ1 then there is an i such that for all reals z0 ≻ τ0 and z1 ≻ τ1, (i)↓ ≠ (i)↓. By the Recursion Theorem, there is a k2 such that = Pk2 for all y ∈ [Pk2]. Let Tn+1 = Pk2 and σn+1 = ∈ Tn+1.

Let en+1 = k3. Then +1 = Tn+1 for all y ∈ [Tn+1]. This completes the construction at step n + 1.

Note that by induction on n, Tn+1 ≤T ⊕i<n+1xi.

Finally, let z = n σn.

By the construction, Tn+1 ≤T ⊕i<n+1xi is a pointed tree for each n. Thus z ≥T xn for every n ∈ ω. If is total and ≰T ⊕i<n+1xi, then we have Case(2) at Substep 3 of Step n + 1. Then it is obvious that z ≤T . Hence z is a minimal cover of A.

We show that z″ ≥T x. This is proved by induction on n that x(n) may be z″-uniformly computed. To do this, we argue that the index en is uniformly computed from z″.

Suppose we are at step n + 1. By inductive hypothesis, assume that z″ recursively computes the index en. By the construction, we have = Tn for all y ∈ [Tn]. Use z to recursively find an initial segment of z which is R1() or L1() for some k0. In the first case, x(n) = 0. In the second case, x(n) = 1. Note that is the perfect tree in Substep 1 of the construction. Now z-recursively find k1 such that R1(()Lk1()) ⪯ z. Then = (R1(()Lk1()), xn, ) = Tn+1,1. Use z″ to decide which case is in. In Case 1, we z″-recursively find the least σ ∈ Tn+1,1 with the required property. Let S = . Then use z to compute the k2 such that = SR1(SLk2(S)). Then en+1 = k2 and Tn+1 = SR1(SLk2(S)) = . In Case 2, use z to compute the k2 such that ⪯ z. Then by the construction, en+1 = k2 and Tn+1 = .

Thus z″ ≥T x.

Theorem 8.3.2. (Chong and Yu [15]). Assume (ω1)L = ω1. There is a -maximal chain in the Turing degrees.

Proof. By Lemma 8.3.1, P is a -cofinally progressive relation. Hence by Theorem 8.2.4, there is a -set A as prescribed. (ii) implies that A is a maximal chain.

8.3.2 Antichains in the Turing degrees

Given a partial ordering (P, <P), a set A ⊆ P is an antichain if any distinct x, y ∈ A are <P-incomparable. A is maximal if it is not a proper subset of an antichain.

Define a binary relation P(x, y) to hold if either (1) or (2) below is satisfied:

(1)There exist n ≠ = m such that (x)n ≠ (x)m but (x)n is Turing comparable with (x)m;

(2){(x)n | n ∈ ω} ∪ {y} is an antichain such that

(2a)x ⊕(y)0 ∈ ,

(2b){(x)n | n ∈ ω} ∪ {(y)0} is an antichain, and

(2c)for every r <L (y)0, {(x)n | n ∈ ω} ∪ {r} is not an antichain.

Lemma 8.3.3. If 2ω = (2ω)L, then P is a cofinally progressive relation.

Proof. Fix y0. Given x, let X = {(x)n | n ∈ ω}. Assume that the set X ∪ {y0} is an antichain of Turing degrees. We show that for any y1 ≥(x ⊕ y0)″, there is a z such that

(1)z″ ≥T y1,

(2)y0 ≤T z ≤T y1,

(3)X ∪ {z} is an antichain.

Then given a constructible y−1 and a countable antichain X ∪ {y0} such that for every r <L y0, X ∪ {r} is not an antichain, by Proposition 4.3.4, there is a y1 ≥T (y−1 ⊕ X ⊕ y0)″ such that y1 ∈ . Then by (1)–(3) above, there is a z such that z ≡h y1 (and hence y0 ⊕ z ∈ ) and X ∪ {z} is an antichain. Thus {z | P(x, y0 ⊕ z)} is cofinally progressive.

We construct a real z such that (z ⊕ x0)″ ≥T y1 and the following requirements are satisfied:

Then X ∪ {z ⊕ y0} is an antichain. The real z is obtained as the union of a sequence of finite strings σ0 ≺ σ1 ≺ ….

Construction

Step 0. Let σ0 = .

Step n + 1 = 〈e, i〉.

Substep 1 (Satisfying Ne,i). Consider the following statement:

If the statement is true, then find the (lexicographically) least such τ and define = τ. Then for every real z ≻ , is total implies ≤T y0. Thus ≠ (x)i since X ∪ {y0} is an antichain. If the statement is false, then find the least τ0 ⪰ σn for which there exists a (least) τ1 ⪰ σn such that Φτ0⊕y0(m) ↓ ≠ Φτ1⊕y0(m)↓ for some m. Define = τk for the k < 2 where Φτk⊕y0(m) ≠ (x)i(m).

Substep 2 (Coding y1). Define σn+1 = ()⌢(y1(n)).

Finally, let z = n σn.

Since y0 ≰T (x)i for all i, the same conclusion holds for z ⊕ y0. By the construction, z ⊕ y0 ≱T (x)i for all i, and so X ∪ {z ⊕ y0} is an antichain.

To see that (z ⊕ y0)″ ≥T y1, consider the statement in Substep 1. The statement is decidable by . If it is true, then we can -recursively find the least such τ. Then τ = . Otherwise, wecan -recursively find both τ0 and τ1. In this case we use z to decide which string is the . Thus y1(n) = 0ifand only if z(||+ 1) = 0. Moreover, σn+1 = z ↾(||+ 1). Hence the sequence {σn}n can be computed from z ⊕ . Therefore (z ⊕ y0)″ ≥T z ⊕ ≥T y1.

Clearly the entire construction can be decoded by y1. Thus y1 ≥T z.

Theorem 8.3.4. (Chong and Yu [16]). Assume (2ω)L = 2ω. There exists a -thin maximal antichain in the Turing degrees.

Proof. By Lemma 8.3.3, P is a cofinally progressive relation. Note that (2c) is equivalent to

Thus P is . Hence by Theorem 8.2.4, there is a set A with the prescribed properties. Using (ii), we show by induction on <L that A is an antichain.

Suppose x ∈ A and {y | y ∈ A ∧ y <L x} is an antichain. By I(ii), there is a z coding {y | y ∈ A∧y <L x} so that P(z, y) holds. Then by (2), {(z)n | n ∈ ω} ∪ {y} is an antichain. So A is an antichain. Note that A ⊂ . This together with Lemma 4.3.1 implies that A is a thin set. By (2b) above, A is maximal.

8.3.3 Exercises

Exercise 8.3.1. Prove that there is no -maximal chain in the Turing degrees.

Exercise 8.3.2. Prove that ZFC+ “There is no -maximal chain in the Turing degrees” is consistent if and only if ZFC+ “There is an inaccessible cardinal” is consistent.

Exercise 8.3.3. Prove that there exists a thin maximal antichain in the Turing degrees.

Exercise 8.3.4. Prove that every maximal antichain in the Turing degrees is of size 2ℵ0.

Exercise 8.3.5. Prove that if there exists a -thin maximal antichain in the Turing degrees, then every real is constructible.

Exercise 8.3.6. Prove that there exists no -maximal chain of hyperdegrees.

*Exercise 8.3.7 (Harrington and Kechris [46]). Prove that every Turing degree ≥ deg()is a minimal cover.

8.4 Martin’s conjecture for -functions

8.4.1 -Martin’s conjecture in L

Since Borel determinacy is a theorem of ZF + DC [93], the results in Chapter 7 hold under ZF + DC for -functions. Since Chapter 7 is concerned with total functions, by Proposition 1.1.8 (iv) the results apply to total -functions as well. However, the situation changes when it comes to partial -functions. Throughout this section, a function F is said to be if its graph GF is . We prove that Martin’s conjecture fails for certain -functions under the assumption V = L. For a start, Lemma 7.2.1 says (under ZF + AD + DC) that ≤M is a linear ordering for increasing uniformly degree invariant functions. The conclusion fails if one assumes V = L.

Theorem 8.4.1. Assume V = L. There is a -uniformly degree invariant function F that is increasing and order preserving on a cone such that for all y, there exist reals x0, x1 ≥T y satisfying F(x0) ≡T x0 and F(x1)≥T x1.

Proof. Assume V = L. Define P(x, y) as

y ∈ ∧ = (y)0 ∧ (y)1 = x ∧ (y)2 is the <L-least real such that (y)2 ≰T (y0)

Since “ = (y)0” is , P is a -cofinally progressive relation. By Theorem 8.2.4, there is a -set A satisfying the prescribed properties in .

By the definition of P, every real is Turing below some real in A. Moreover, P ensures that <T is a well ordering and consistent with <L on A.

Define F(x) = y if

(1)y ∈ A;

(2)x ≤T y;

(3)x >T 0⇒(∀n)(x ≰T((y)1)n).

Roughly speaking, y is the <T-least real in A such that x ≤T y.

By (3)and the property of A, F is well defined. Furthermore, it is , increasing, order persevering and uniformly degree invariant (x ≡T y implies F(x) = F(y)). Moreover, since F(x) = x for every x ∈ A, we have F(x)≡T x cofinally.

For every real s, choose xs ∈ A such that xs ≥T s. Then for the <T-least real y ∈ A above xs, there is a z coding {x | x <L y ∧ x ∈ A} = {x | x <T y ∧ x ∈ A} so that P(z, y) holds. Obviously x′s ≤T z′ ≤T z. By the definition of P,

and (y)1 = z. Thus

{((y)1)n | n ∈ ω}={r | r ≤T x ∧ r ∈ A}.

Since ≰T r for all r ∈ A with r ≤T xs, we have ≰T ((y)1)n for all n ∈ ω. Hence F() = y. In other words, F() ≥T .

Thus the function F is M-incomparable with the function G where G(x) ≡T x′ for every x.

Assume ZF + DC + AD. By Lemma 7.1.4, if F is uniformly degree invariant and nonincreasing on a cone, then F(x) <T x on a cone C = {x | x ≥T z0} for some z0. We show that this also fails for -functions under V = L.

Theorem 8.4.2. Assume V = L. There is a uniform degree invariant, nonincreasing -function F such that F(x)|T x on a cone. In particular, F is not constant on a cone.

Proof. Let A be the -set as constructed in Theorem 8.4.1. Define F(x) = y if and only if there is a real z ≡T y′ such that

(1)z ∈ A;

(2)the degree of y is minimal;

(3)y = for some e such that for all i<e, if the degree of is minimal then ()′ ≢T z, and

(4)x >T 0⇒(∀n)(x ≰T((z)1)n).

We leave it to the reader to verify that F is the desired counterexample.

By Lemma 7.2.4, ZF+AD+DC implies that ≤M is a well-ordering on the set of increasing uniformly degree invariant functions. This again fails under the assumption V = L.

Theorem 8.4.3. Assume V = L. There is a sequence of uniform degree invariant, increasing, -functions {fn}n<ω such that Fn+1 <M Fn for all n. Thus <M is not a prewellordering.

Proof. Define P(x, y) by

Clearly P(x, y) is a -cofinally progressive relation. By Theorem 8.2.4, there is a -set A with the property prescribed by P.

By the definition of P, every real is Turing below some element of A and <T is a well-ordering consistent with <L on A.

It is not difficult to see that there is an arithmetical set W ⊆ {(m, n, z)| m, n<ω ∧ z ∈ 2ω} such that {}n<ω, where = {m | (m, n, z) ∈ W}, is a sequence of z-r.e. sets satisfying z <T <T for each n.

Let Fn(x) = y if there exists a z <T y such that

(i)z ∈ A;

(ii)z ≥T x;

(iii)y = ;

(iv)x >T 0⇒(∀m)(x ≰T ((z)0)m).

Roughly speaking, y is +1 for the <T-least z in A with z ≥T x.

Clearly {fn}n<ω is a sequence of -functions. Note that for any x <T y in A, x′ ≤T y. Hence for every n, Fn is degree invariant and increasing.

By (iv) and the property of A, F is well defined. By the choice of {}n<ω, {fn}n<ω is a <M-descending sequence.

8.4.2 The consistency strength of -Martin’s conjecture

Given that the results in Chapter 7 are established under AD which is essentially a large cardinal assumption, one would expect a direct connection between Martin’s conjecture and large cardinals. The first level for such an investigation is clearly . We prove that if -Martin’s conjecture is true, then 0♯ exists.2

Define the Friedman set F* as

It is not difficult to see that F* is .

Lemma 8.4.4. F* is cofinal in the Turing degrees.

Proof. For any real z, let

Then F(z) is (z) and nonempty. By Gandy’s Basis Theorem (2.5.3) relativized to z, there is a x such that = and x ⊕ z ∈ F(z). Then x ⊕ z ∈ F.

We will use the following result due to Harrington. A sketch of the proof is given in Exercises 8.4.3 to 8.4.8.

Lemma 8.4.5 (Harrington [45]). If 0♯ does not exist, then = 2ω F is cofinal in the Turing degrees.

Theorem 8.4.6. (Chong, Wang and Yu [13]). If there is no uniformly order-preserving -function G such that {x | G(x) = } and {x | G(x) = are cofinal in the Turing degrees, then 0♯ exists.

Proof. If 0♯ does not exist, then by Lemmas 8.4.4 and 8.4.5, both F* and * are cofinal. Let P(x, y) be an arithmetical predicate defined as

x ∈ * ⇔ (∀y)P(x, y).

Claim 1. If x ≤T y are such that x ∈ F* and y ∈ *, then x ≤h y.

Proof. As y ∉ F*, thereare α < and a ⊆ α with a ∈ Lα+1[y]. Then a ∉ Lα+1[x] and ≤ α < . As x ≤T y, x ≤h y.

By Claim 1, if x ≤T y are such that x ∈ F* and y ∈ *, then ≤T y.

Now define G(x) = y as follows:

(1)(y)0 = 0⌢ ∧ x ∈ * or (y)0 = 1⌢∧(∃v ≤T (y)0)¬P(x, v),

(2)(y)1 = x,

(3) is partial ⇒(y)e+2 = ,

(4)u = is total ⇒

(i) (y)0(0) = 0 ∧ (∃v ≤T (y)1)¬P(u, v) ∧ (y)e+2 = 1⌢ where i is the least index so that = , or

(ii) (y)0(0) = 1 ∧ (∃v ≤T (y)1)¬P(u, v) ∧ (y)e+2 = 1⌢, or

(iii) (∀v ≤T (y)1)P(u, v) ∧ (y)e+2 = 0⌢.

It is straightforward to verify that G is .

Claim 2. If x ∈ F* then G(x)≡T .

Proof. Clearly x ∈ F* ⇒ ≤T G(x) and (G(x))0 ⊕(G(x))1 ≤T .

Given e < ω, can uniformly decide whether is total. Suppose that is total. To calculate (G(x))e+2(n) we need to check clauses (4 ii, 4 iii) above. Now the predicate (∀v ≤T (y)1)P(u, v) is (x), and hence recursive in . Once this predicate is decided, will be able to complete the calculation with the use of two recursive functions f, g such that u = → = and u = → = .

Claim 3. If x ∈ * then G(x)≡T

Proof. This is similar to the proof of Claim 2, except for he final step in the calculation of (G(x))e+2(n). Now can decide whether (4 i) or (4 iii) holds, as in the above claim. If (4 iii) holds, then the calculation is again similar to the above. Suppose that (4 i) holds. Then u ∈ F*. By Claim 1, u ≤h x and thus ≤T x = (G(x))1. Now the index i prescribed in (4 i) may be found uniformly via a (x) procedure. Hence computes (G(x))e+2(n) uniformly.

It follows from the last two claims that G is degree invariant. Moreover, G preserves ≤T by Claim 1.

To show that G is uniformly order preserving, let h be a recursive function such that (∀x, y, e)(x = → x = ). In addition, let s be another recursive function with

Suppose that x = . Then

(1)(G(x))0 = (G(y))e+2,

(2)(G(x))1 = , and

(3)(G(x))i+2 = (G(y))s(i)+2.

Hence G is as desired.

8.4.3 Exercises

Exercise 8.4.1. Use Theorem 6.5.6 to prove that if 0♯ exists, then Martin’s conjecture for -uniformly degree invariant functions is true.

Exercise 8.4.2. Prove that there is a sentence φ in the language of partial ordering of the Turing degrees such that {x |〈(≥ x), ≤〉 ⊨ φ} is cofinal and if it contains a cone, then 0♯ exists.

Exercise 8.4.3. Suppose that α > β > ω are countable admissible ordinals and g is a generic real produced by Steel forcing over Lα. Then for any ordinal γ < β and any set A ⊆ γ, if A ∈ Lα ∩ Lβ[g], then A ∈ Lβ.

Exercise 8.4.4. Suppose that the Friedman set F* contains a cone of Turing degrees. Then there is a real x such that for any y ≥T x, any α < and any A ⊆ α, if A ∈ L then A ∈ [y].

Exercise 8.4.5. Assume that the Friedman set F* contains a cone of Turing degrees. Show that there is a real x such that for any y ≥T x and countable ordinal α, if Lα[y] is admissible then α is a cardinal in L.

Exercise 8.4.6. Assume that the Friedman set F* contains a cone of Turing degrees. Show that there is a real x such that for any y ≥T x and ordinal α, if Lα[y] is admissible then α is a cardinal in L.

Exercise 8.4.7. Suppose that x is a real such that for any ordinal α, if Lα[x] is admissible then α is a cardinal in L. Furthermore, assume that V = L[x]. Then there is an ordinal α <ℵ2 and an elementary embedding π : Lα[x]→ Lℵ3[x] such that

–ℵ2 ∈ Range(π),

–there is an ordinal β < α such that π(β) > β, and

–(Range(π))ω ⊆ Range(π).

Exercise 8.4.8. As in Exercise 8.4.7, let β be the least ordinal such that π(β) > β. Then the set {X ∈ L | X ⊆ β ∧ β ∈ π(X)} is an ω-complete nonprincipal ultrafilter over L ∩ (β). Thus there is a nontrivial elementary embedding of L into L.