9.3 Cofinal chains in

9.3.1 Existence of a cofinal maximal chain of order type ω1

Definition 9.3.1. Given a partial ordering 〈P, <P〉, a set A ⊆ P is a cofinal chain if the members of A are linearly ordered under P and for any z ∈ P, there is an x ∈ A such that z ≤P x.

It is not difficult to see that under ZFC, there is a cofinal chain of Turing degrees if and only if CH holds. A natural question is whether there exists a cofinal maximal chain of order type ω1 in 〈, ≤〉 assuming ZFC + CH. The question is considered in this section.

The following fact is immediate.

Lemma 9.3.2. Assume ZF. There exist x0 and x1 of minimal degree such that

Lemma 9.3.3. Assume ZF. There is a maximal chain 0 = c0 < c1 < … < cω = 0'' in [0, 0''].

Proof. Fix an enumeration (dn : n ∈ ω) of degrees below 0''. Let c0 = 0.

Suppose that cn is defined with c''n = 0''. Relativize Lemma 9.3.2 to obtain degrees x0 and x1 minimal over cn such that x0 ∪ x1 = c''n = 0'' = x''0 = x''1. If dn < 0'' then there is an i < 2 with , and let cn+1 = xi. If dn = 0'', let cn+1 = x0.

Finally let cω = 0''.

Theorem 9.3.4. (Wang, Wu and Yu [168]). Assume ZFC. Then CH holds if and only if there is a cofinal maximal chain in D of order type ω1.

Proof. (⇒) Assume CH and let {dα | α < ω1} be an enumeration of the Turing degrees. We construct inductively a sequence {Cα}α<ω1 of chains such that

(1) For each β < α there is a c ∈ Cα with c ≥ dβ;

(2) Cα has order type α × ω + 1 if α = 0 or is a successor ordinal;

(3) Cα has order type α × ω if α is a limit ordinal, and

(4) Cβ ⊂ Cα if β < α.

Let C0 = {0}. Suppose that α = β + 1and Cβ is defined. Given dβ, we apply Lemma 8.3.1 to obtain a minimal cover a of Cβ with a'' ≥ dβ. Relativizing Lemma 9.3.3 yields a maximal chain a = a0 < a1 < … < aω = a'' in [a, a'']. Let Cα = Cβ ∪ {aγ : γ ≤ ω}. For α a limit ordinal, let Let It is straightforward to verify that the order type of C is ω1, C is a maximal chain, and that for each α < ω1 the (α × ω + ω + 1)-th element of C bounds dα.

(⇐) Since every degree bounds at most countably many degrees, CH follows immediately if there is a maximal chain as described.

9.3.2 CH without AC

To continue our tour of the ordering of Turing degrees, we recall some set-theoretic facts. CH is the statement that there is no set X with |ω| < |X| < |2ω|, where”|X| ≤ |Y|” means the existence of a surjective map from Y onto X. Hence ZF + CH does not obviously imply the existence of a well-ordering of reals. The same is true of GCH with regard to AC. It turns out that there is a link between these two hypotheses.

Theorem 9.3.5. (Sierpinski [136]). ZF ⊢ GCH → AC.

A question along this line is whether Theorem 9.3.5 holds level by level. For example, does CH imply the existence of a well-ordering of 2ω?

Theorem 9.3.6 (Kanamori and Pincus [62]). ZFC + “There exists an inaccessible cardinal” is consistent if and only if ZF + CH + “There is no well-ordering of 2ω” is consistent.

Proof. Assume that ZFC + “There exists an inaccessible cardinal” is consistent. By Solovay [150], there is a model M of ZF in which every uncountable set of reals contains a perfect subset. In other words, M ⊨ ZF + CH. Furthermore, there is no well-ordering of the set of reals in M.

Conversely, suppose that ZF + CH + “There is no well-ordering of 2ω” is consistent and let M be a transitive model of this theory. We claim that (ω1)M is inaccessible in L. Clearly (ω1)M is regular in L. It is sufficient to prove that for any α < (ω1)M, |(2α)L| < ω1. If not, there exists a countable α such that |(2α)L|=(ω1)M. Then (2α)L ∈ M and there is a well-ordering of (2α)L in M. Since |ω|<|(2α)L| ≤ |2ω|, we have |(2α)L|=|2ω|. In other words, there is a bijection between (2α)L and 2ω in M. It follows that there is a well-ordering of 2ω in M, which is a contradiction.

Theorem 9.3.6 says that “ZF + CH + There is no well-ordering of 2ω”is such a strong theory that an inaccessible cardinal is required to guarantee its consistency. However, for forcing extensions, one has the following:

Proposition 9.3.7. Let M ⊨ ZFC. If N is an extension of M preserving (ω1)M such that N ⊨ ZF+”There is a cofinal chain of Turing degrees”, then N ⊨ ¬CH if and only if N ⊩ “There is no well-ordering of 2ω”.

Proof. If N ⊨ “There is a well-ordering of 2ω”, then N ⊨ CH since N ⊨ ZF+”There is a cofinal chain of Turing degrees”.

Now suppose that N ⊨ “There is no well-ordering of 2ω”. Take C ∈ M to be a subset of (2ω)M such that <T is a well-ordering of C of order type (ω1)M. Since N is an extension of M preserving (ω1)M, N ⊨ |ω|<|C|. Since there is no well-ordering of 2ω in N, we have N ⊨ |C|<|2ω|. So N ⊨ ¬CH.

9.3.3 Cofinal chains versus CH

Pursuing further the link between CH and Turing degrees, one asks if, under ZF, CH is equivalent to the existence of a cofinal maximal chain of Turing degrees of order type ω1. The answer is negative: By Solovay [150], there exists a model M of ZF in which every uncountable set of reals contains a perfect subset. Since it is a theorem of ZF that every perfect set contains two reals with incomparable Turing degrees, there is no chain of Turing degrees of order type ω1.

It is not known if ZF + “There exists a cofinal maximal chain of Turing degrees of order type ω1” implies CH. However, there is a partial answer:

Theorem 9.3.8. (Wang, Wu and Yu [168]). If ZFC is consistent, then so is ZF +¬CH + “There exists a cofinal chain in the Turing degrees of order type ω1”.

The rest of this section is devoted to a proof Theorem 9.3.8. We begin with the ground model 〈L, ∈ 〉. Let ℙ be the collection of Cohen forcing conditions. ℙℵ1 is the resulting product forcing with finite support of length ℵ1.

For α < ω1, let ℙ<α = 〈P<α, ≤〉, where p ∈ P<α if and only if p ∈ Pℵ1 and dom(p)⊆ α. The partial order on ℙ<α is the restriction of that on ℙℵ1 to P<α. Thus ℙℵ1 =ℙ<ℵ1. Let E be the set of limit ordinals less than ω1. For α < ω1, let ωα1 be the least admissible ordinal greater than α. Then

Lemma 9.3.9. There exist an uncountable set E1 ⊆ E in L and a sequence of binary relations {Rα}α∈E1 ∈ L such that for each α ∈E1,

–Rα ∈ L is a binary relation on {2n | n < ω} that is a well-ordering of order type α;

–for each β ≤ α, there is a function fβ ≤T Rα which is an isomorphism between Rβ and an initial segment of Rα.

Proof. We define E1 and {Rα}α∈E1 by induction on α < ω1. Let E1,0 =0.Atstage α + 1, suppose that E1,α and {Rγ}γ ∈ E1,α have been defined. Let R ∈ L be a well-ordering of {22n | n < ω} of order type a limit ordinal greater than that of Rγ for γ ∈ E1,α. Then for every γ ∈ E1,α, there is a function fγ which maps Rγ isomorphically onto an initial segment of R. Let x ∈ L be a real that computes all the fγ’s. Let E1,α+1 = E1,α ∪ {γ1} where γ1 = α + ω + ω. Let R1 be a binary relation on {22n+1 | n < ω} such that for any n (22n+1, 22m+1) ∈ R1 if and only if either n ∈ x and ∈ x,or n ∈ x ↔ m ∈ x and n < m. So R1 ≥T x in L and is a well-ordering of order type ω + ω on {22n+1 | n < ω}. Let

Rα+1 = R ∪ R1 ∪ {(22n, 22m+1) | n, m ∈ ω}.

If α is a limit ordinal, let and repeat the above upon replacing E1,α by E1,<α.

Let Then E1 and {Rα}α∈E1 are as required.

From now on, let E1 and {Rα}α∈E1 in L be as above. Let G be a ℙℵ1-generic set over L. Then G may be viewed as an ω1-sequence {Gα}α<ω1 such that for every α < ω1, is a real. Let G<α = {(β, Gβ) | β < α}.

Definition 9.3.10. For any γ < α ∈ E1 and any sequence {zβ}β<α of reals, define the join of {zβ}β<γ along Rα to be the set

The following lemma says that the join operator is order preserving.

Lemma 9.3.11. For any β1 ≤ β2 ≤ α1 ≤ α2 ∈ E1,

Proof. It is immediate that Rβ2 ≤T Rα2. Let f be an Rα2-recursive function which is an isomorphism between Rβ2 and an initial segment of Rα2. Then for any n, j,

Hence

The following lemma is used in the construction of a cofinal chain.

Lemma 9.3.12. For any real x and α ∈ E1, ifx ∈ L[G<α] then there is a β ≥ αinE1 such that

Proof. Note that for any since Rα ∈ L. Suppose that x ∈ L[G<α]. There is a β1 ≥ α in E such that By Lemma 9.3.11, Thus Since by relativizing Theorem 3.7.1 to we have x to be Hence there is a β2 ≥ β1 below ω such that By Lemma 9.3.11 again, Then β2 is the required β.

In L[G], if α ∈ E1 let xgα =(⊕Rα {Gγ}γ<α)(α), andlet τα be the canonical ℙℵ1-name of xgα. Let

Obviously A is a chain of Turing degrees in L[G].

Set

N =(HOD(TC({A}))L[G],

where TC({A}) ∈ L[G] is the transitive closure of {A}.

Lemma 9.3.13. For any α < ω1,

(i)ℙ<α preserves cardinals;

(ii)G<α is ℙ<α-generic over L;

(iii)A ∈ N is a cofinal chain of Turing degrees of order type ω1;

(iv)(2ω)L[G] =(2ω)N.

Proof. (i) follows from Theorem 6.1.11 and (ii) from Theorem 6.1.9, while (iv) is an immediate consequence of (iii). We prove (iii).

Given x ∈ L[G], there is an ordinal α < ω1 such that x ∈ L[G<α]. Then there is a countable ordinal α1 ≥ α such that x ∈ Lα1[G<α]. By Lemma 9.3.12, for any β ≥ α1 in

Hence N is a cardinal preserving extension of L satisfying ZF+”There exists a cofinal chain of Turing degrees”. If we take N' = HOD({Gα | α < ω1}), then in N' there is no well-ordering of 2ω by the proof of Theorem 6.2.15. However, to apply the argument for N, additional precaution is required to preserve the name of A. For this purpose, we work with a subset of permutations of ω1.

If π is a permutation of ω1, let spt(π) = {α < ω1 | π(α) ≠ α}. Let H0 be the set of all permutations π of ω1 with |spt(π) | < ω, and set

H = {π ∈ H0 | (∀α < ω1)(π(α)< α + ω)}.

For each π ∈ H, let ̄ π be the permutation of Lℙℵ1 induced by π.

Let B be the set of ℙℵ1-names of reals, and define

Lemma 9.3.14. If

Proof. Note that the canonical name ̌γ of γ is invariant under π, and Rγ is definable in γ as L is the minimal inner model. Then for any ℙℵ1-generic differ on at most finitely many columns, the lemma follows immediately.

Corollary 9.3.15. If π ∈ H, then

Hence the permutations in H are sufficient to show

N ⊨ “There is no well-ordering of 2ω”.

By Proposition 9.3.7, N ⊨ ¬CH and this completes the proof of Theorem 9.3.8.

9.3.4 Exercises

Exercise 9.3.1. Prove Lemma 9.3.2.

Exercise 9.3.2. (Kunen). Prove that if there is a well-ordering of the Turing degrees, then there is a well-ordering of 2ω.

Exercise 9.3.3. (Wang, Wu and Yu [168]). Prove that in the proof of Theorem 9.3.8, we may assume M ⊨ ZFC + CH + ω1 =(ω1)L.

Exercise 9.3.4. Prove that there is a model M of ZF in which no set of reals has exactly one representative from each Turing degree, and in which there is a thin set A where 2ω A is also thin.

9.4 ω-homogeneity of the Turing degrees

Definition 9.4.1. 〈, ≤〉 is ω-homogeneous if for any two n + 1-tuples (a0,…, an) and (b0, …, bn) in , if 〈, ≤, a0,…, an〉 ≡ 〈, ≤, b0,…, bn〉 then there is an automorphism π : → such that π(ai) = π(bi) for each i ≤ n.

Slaman and Woodin [144] showed:

Theorem 9.4.2. The ω-homogeneity of 〈, ≤〉 is independent of ZFC.

We say that a function f : 2ω → 2ω presents an automorphism π : 〈, ≤〉 → 〈, ≤〉 if for every Turing degree x and real x ∈ x, f(x) ∈ π(x). The next two results are needed for Theorem 9.4.2 and are stated without proof.

Theorem 9.4.3. Every automorphism π : 〈, ≤〉 → 〈, ≤〉 is presented by an arithmetical function f :2ω → 2ω.

If R is a degree invariant relation over (2ω)n+1 for some n, then it induces a relation R̃ on degrees such that xn ∈ xn ∧ (x0,…, xn) ∈ R). We identify R̃ with R for simplicity.

Theorem 9.4.4. For any relation R over D which is induced by a degree invariant analytical relation over 2ω, if R is invariant under any automorphism of D, then R is definable in 〈, ≤〉.

We now prove Theorem 9.4.2.

Lemma 9.4.5. If V = L, then 〈, ≤〉 is ω-homogeneous.

Proof. By Proposition 4.4.2, <L is a well-ordering of 2ω. The lexicographic ordering of n + 1-tuples induced by <L implies that for each n there is a well-ordering <n+1 of (2ω)n+1.

For m < ω and k ≤ n, let Rm,k ⊆ (2ω)n+1 be such that

(x0,…, xn) ∈ Rm,k ⇔ k ≤ n ∧

(∃y0)…(∃yn)((y0,…, yn) is the <n+1 -least so that

(∃π)(∀i ≤ n)(π : 〈, ≤〉 → 〈, ≤〉 is an automorphism ∧ π(yi) = xi ∧ m ∈ yk)).

It is straightforward to verify that Rm,k is degree invariant and hence induces a relation on invariant under any automorphism. By Theorem 9.4.3, Rm,k is also analytical. Hence by Theorem 9.4.4, Rm,k is definable in 〈, ≤〉.

Suppose that 〈, ≤, a0,…, an〉≡〈, ≤, b0,…, bn〉. Then Rm,k (a0,…, an)⇔ Rm,k(b0,…, bn) for every m and k ≤ n. For such a k, define yk so that m ∈ yk if and only if Rm,k(a0,…, an). By the definition of Rm,k, there are automorphisms π0 and π1 such that for every k ≤ n, π0(yk) = ak and π1(yk) = bk. Then π1 ∘ π−10 is an automorphism between 〈, ≤〉 and 〈, ≤〉, and π1∘π−10(ak) = bk, implying that 〈, ≤〉 is ω-homogeneous.

We complete the proof of Theorem 9.4.2 with the following lemma.

Lemma 9.4.6. If V = L[g] where g is a Cohen generic real, then 〈, ≤〉 is not ω-homogeneous.

Proof. Let g = g0 ⊕ g1. We leave it to the reader to verify that (g0, g1) is a pair of generic reals over a product Cohen forcing ℂ×ℂ. Then by Theorem 9.4.3, there is no automorphism of 〈, ≤〉 sending g0 to g1.

Now let φ be a formula such that 〈L[g], ∈ 〉 = 〈L[(g0, g1)], ∈ 〉 ⊨ “〈, ≤〉 ⊨ φ(g0)”. Then there is a condition (p0, p1) ∈ 2<ω × 2<ω such that |p0|=|p1|, (p0, p1)≺(g0, g1) and Obviously there is an automorphism π : ℂ×ℂ → ℂ×ℂ so that π((p0, p1)) =(p1, p0) and π∗(ġ0) =ġ1. By Proposition 6.1.17, (p1, p0) ⊩ “〈 ̇ , ̇ ≤〉 ⊨ φ( ̇ g1)”. Then 〈L[(g1, g0)], ∈ 〉 ⊨ “〈, ≤〉 ⊨ φ(g1)”. However, L[(g1, g0)] = L[(g0, g1)] = L[g] and thus 〈L[g], ∈ 〉 ⊨ “〈, ≤〉 ⊨ φ(g1)”. Hence 〈, ≤〉 is not ω-homogeneous.

9.5 Some general independence results

For a general reference on the subject of Turing degrees, see Lerman [82]. Let L ( ≤ ) be the language of partial ordering. L ( ≤ ) is a set definable in the language of set theory. Furthermore, both 〈, ≤〉 and the relation “〈, ≤〉 ⊨ φ” may be viewed as definable sets in the language of set theory. We code each formula φ in L ( ≤ ) by a number ⌜φ⌝. Let

Th∃2〈, ≤〉 = {⌜φ⌝| φ is a Σ2-sentence in L ( ≤ ) ∧ 〈, ≤〉 ⊨ φ}.

Lerman and Shore [131] proved:

Theorem 9.5.1. The set Th∃2(, ≤ ) is recursive.

Hence the set Th∃2〈, ≤〉 is definable by a -formula ψ0 and a -formula ψ1. It follows that for any Σ2-sentence φ,

ZFC ⊢ “〈, ≤〉 ⊨ φ ⇔ ψ0(⌜φ⌝)”

and

ZFC ⊢ “〈, ≤〉 ⊨ ¬φ ⇔¬ψ1(⌜φ⌝)”.

Since for any -formula ψ(u) and natural number n,

ZFC ⊢ ψ(n)⇔〈ω, ≤, +, ⋅,0,1〉 ⊩ ψ(n),

(see [145]), for any Σ2-sentence φ either

ZFC ⊢ “〈, ≤〉 ⊨ φ”

or

ZFC ⊢ “〈, ≤〉) ⊨ ¬φ”.

Hence we have the following conclusion.

Corollary 9.5.2. For any Σ2-sentence φ in L ( ≤ ),either”〈, ≤〉 ⊨ φ” or “〈, ≤〉 ⊨ ¬φ” is provable in ZFC.

Clearly the set Pr = {⌜φ⌝| ZFC ⊢ “〈, ≤〉 ⊨ φ”} is r. E. The complexity of the theory of the Turing degrees was established by Simpson [139]:

Theorem 9.5.3. ZFC proves that there is a recursive bijection f : ω → ω such that for any n, n ∈ {⌜φ⌝|〈, ≤〉 ⊨ φ} if and only if f(n) ∈ {⌜ψ⌝|〈ω, 2ω, +, ⋅, ≤, ∈ 〉 ⊨ ψ}, where ψ is a formula in the language of second order arithmetic.

Thus ZFC proves that the set {⌜φ⌝|〈, ≤〉 ⊨ φ} is not analytical. It follows that for any M ⊨ ZFC, we have Pr ⊂ {⌜φ⌝| M ⊨ “〈, ≤〉 ⊨ φ”}. This leads to the following conclusion.

Corollary 9.5.4. For any M ⊨ ZFC, there is a sentence φ such that ⌜φ⌝ ∈ {⌜ψ⌝| “〈, ≤〉 ⊨ ψ”} Pr.

Let M ⊨ ZFC and φ be as above. Since ZFC ⊬ “〈, ≤〉 ⊨ φ”, there exists a model N ⊨ ZFC such that N ⊨ “〈, ≤〉 ⊨ ¬φ”. Hence the statement “〈, ≤〉 ⊨ φ” is independent of ZFC. This argument implies the existence of a sentence φ not provable in ZFC, but does not provide any information about φ. The following offers more information: By Corollary 4.4.1, the statement “every real is constructible” is Hence there is a sentence φ in L ( ≤ ) such that 〈, ≤〉 ⊨ φ if and only if every real is constructible. Thus the statement “〈, ≤〉 ⊨ φ” is independent of ZFC. However, a weakness in the argument is that the sentence φ is highly complicated, not necessarily considered “natural”, and heavily dependent on the coding scheme. It is not known if there is a “natural” sentence in that is independent of ZFC.