9 Independence results in recursion theory

9.1 Independent sets of Turing degrees

9.1.1 Locally countable partial ordering

Definition 9.1.1. A partially ordered set 〈P, ≤P〉 is locally countable if for any p ∈ P, |{q | q ≤P p}| ≤ ℵ0.

Definition 9.1.2. A function f : 〈P, ≤P〉 → 〈Q, ≤Q〉 is an embedding if (∀p0, p1 ∈ P) (p0 ≤ p1 ⇔ f(p0) ≤Q f(p1)).

Obviously 〈, ≤T〉, the partial ordering of the Turing degrees, is locally countable. Sacks made the following conjecture.

Conjecture 9.1.3 (Sacks [117]). Every locally countable partial ordering on 2ω is embeddable into 〈, ≤T〉.

A positive solution is known assuming the Continuum Hypothesis:

Theorem 9.1.4. (Sacks [117]). Assuming ZFC + CH. Every locally countable partially ordered set 〈2ω, ≤P〉 is embeddable into 〈, ≤T〉.

9.1.2 Independent sets of Turing degrees

As a “test question” for Conjecture 9.1.3, Sacks introduced the notion of independent sets and conjectured that every maximal independent set of Turing degrees has size 2ℵ0.

Definition 9.1.5. Let 〈P, ≤P〉 be a partial ordering. X ⊆ P is independent if for any finite subset Y of X and any p ∈ X Y, there is a q ∈ P such that

Theorem 9.1.6 (Sacks[117]). Assume ZFC + CH. Every maximal independent set of Turing degrees has size 2ℵ0.

However, the conclusion of Theorem 9.1.6 is independent of ZFC:

Theorem 9.1.7 (Groszek and Slaman [40]). There is a model with a maximal independent set of Turing degrees of size ℵ1.

The rest of this section is devoted to a proof of Theorem 9.1.7. We begin with a ground model be product Sacks forcing with countable support, where is Sacks forcing for α < ω1. Every ℙ-generic set G may be viewed as an (ω1)M-sequence of reals {Gα}α<(ω1)M where Gα = {i | (α, i) ∈ G}. It is not difficult to see that the Turing degrees of {Gα}α<(ω1)M form an independent set.

Lemma 9.1.8. (Baumgartner [5]). If G is ℙ-generic over M = 〈M, ∈〉, then every countable set of ordinals in M[G] is countable in M.

Proof. The proof is a fusion argument similar to that of Theorem 6.2.11 and is left to the reader.

Since is a notion of product forcing with countable support, we have |ℙ| ≤ (ℵ1)M. Thus ℙ satisfies (ℵ2)M-c.c. Together with Lemma 9.1.8, we have:

Lemma 9.1.9. ℙ preserves cardinals.

Lemma 9.1.10. For any real x ∈ M and countable ordinal β, there is a countable α > β such that x ≤T Gα.

Proof. We show that for any x ∈ M and β < (ω1)M, the set is dense. Given p ∈ P, there is a countable α > β such that p(α) is undefined. Choose any such ordinal α and let q ≤ p such that q(γ) = p(γ) for γ ≠ α and . Then q(α) is a pointed tree in which every infinite path Turing computes x. Hence q ∈ Dx, β.

For any countable ordinal α ∈ M, let Rα ⊆ ω × ω be a well-ordering of ω × ω in M of order type α. Let |n|Rα denote the order type of Rα restricted to the set of numbers less than n under Rα. Define ⊕Rα {Gβ}β<α = {(n, m) | Gβ(m) = 1 ∧ β < α ∧|n|Rα = β}.

Lemma 9.1.11 (Baumgartner [5]). For every real x ∈ M[G] M, there is a countable ordinal α such that x ≤T ⊕Rα {Gβ}β<α. Hence M[G] ⊨ CH.

Proof. The proof is again a fusion argument similar to that of Theorem 6.2.11.

Now let X ⊇ G be a set of reals whose Turing degrees are maximally independent in M[G]. We call such an X a maximally independent set.

The next step is to destroy GCH by adding reals to M[G] but keeping X as a maximally independent set. Let be a ℙ-name such that for any p ∈ P,

is a product Sacks forcing of length with countable support”

and

Hence is a two step iterated forcing. By Theorem 6.1.11 and the assumption that M[G] ⊨ CH for any ℙ-generic set G, we have the following lemma.

Lemma 9.1.12. For any

Lemma 9.1.13. preserves cardinals.

Proof. By Lemma 9.1.9, it is sufficient to prove that for any ℙ-generic set G over M,

M[G] ⊨ ℚ preserves cardinals.

As in Lemma 9.1.8, M[G] ⊨ ℚ preserves ℵ1. By Lemma 9.1.12, M[G] ⊨ ℚ preserves κ for all κ ≥ ℵ2. Hence M[G] ⊨ ℚ preserves cardinals.

Let H be a ℚ-generic set over M[G]. Then H may be viewed as an ω2-sequence of reals {Hα}ω1≤α<ω2. Thus ℚ adds at least ℵ2-many reals to M[G] and we have the following:

Lemma 9.1.14. If (p, q̇)∈(P, Q̇), then (p, q̇)⊩¬CH.

Lemma 9.1.15. If (p0, q̇0) ∈ (P, Q̇),α < ω1 and (p0, q̇0) ⊩ “̇ẋ is not in M [Ġ]”, then there is a z ∈ M and a condition (p1, q̇1) ≤(p0, q̇0) such that

By Lemma 9.1.10 and Lemma 9.1.15, {Gα}α<ω1 is still a maximally independent set in M[G][H]. The rest of this section is devoted to a proof of Lemma 9.1.15.

Given a perfect tree T, we associate with it the natural homeomorphism tT : 2<ω → T such that tT() is a splitting node in T and for every or . Suppose that H is ℚ-generic over M[G]. Let (G, {(α, Hα)) | α < ω2}) be a ℙ∗ℚ-generic set and let p ∈ P be a condition such that

is a product Sacks forcing with countable support of length ω2”.

For any set A ⊆ ω2, we use ⊕α∈AHα to denote {(α, Hα) | α ∈ A}. Fix a condition (p0, q̇0) ∈ (G, Ḣ) such that p0 ≤ p and

We define a fusion sequence of conditions {(pσ, q̇σ)}σ∈2<ω below (p0, q̇0), a sequence of ordinals {αn}n<ω, and a sequence {νσ}σ∈2< ω ⊆ 2<ω with the following properteies:

(1)

(2)For all n,forall σ, τ ∈ 2n and all α,

and

(3)(∀α)((∃σ)(pσ(α) is defined∨pσ ⊩ “q̇σ(α) is defined”)) → (∀n)(∃m > n)(α = αm))); and

(4)(∀n)(∀σ ∈ 2n)(∀τ ∈ 2n)(∃m < n)(∃α < ω1)(α = αm ∧ σ(m) ≠ τ(m)) → νσ|ντ).

Now for n < ω and α < ω1, let

and

Suppose that pω ∈ G. Then for any n and m ≤ n, there is a σm ∈ 2n such that if αm < ω1, then Gαm ∈ [pσm (αm)]. Define τ ∈ 2n so that τ(m) = σm(m) for m ≤ n. By (2), for each such m, pτ(αm) = pσm (αm), and foreach σ ∈ 2n and every other α, pτ(α) = pσ(α). Thus Gα ∈ [pτ(α)] whenever pτ(α) is defined. Hence pτ ∈ G. We have the following lemma.

Lemma 9.1.16. If pω ∈ G, then for each n there is a σ ∈ 2n such that pσ ∈ G.

If α ≥ ω1, let q̇n be a name so that

By Lemma 9.1.16, q̇n is well defined. For α > ω1, let q̇ω be a name such that

Lemma 9.1.17.

Proof. By (1), for any generic set (G, H) with (pω, qω) ∈ (G, H) and x ↾|νσ|= νσ. By Lemma 9.1.16, there is a τ ∈ 2|σ| such that pτ ∈ G. By (2), σ(m) = τ(m) for any m with αm < ω1. By (2) again, pσ = pτ ∈ G.

Obviously . In fact, for any there is such a sequence below (p'0, q̇'0). Hence there is a (pω, q̇ω) such that (pω, qω) ∈ (G, H). Now for any α < ω1, let zα = {(pσ(α), νσ) | σ ∈ 2<ω}. Then zα may be viewed as a real in M. By Lemma 9.1.17, Gα ≤ x ⊕ zα, proving Lemma 9.1.15.

Next is the construction of the sequences satisfying (1)–(4), of which meeting condition (2) is the key. We need a technical lemma.

Lemma 9.1.18. If (p, q̇) ≤ (p0, q̇0), then there exist an n and a condition (p', q̇') ≤ (p, q̇) such that for any

Proof. Suppose not. Then there is a (p1, q̇1) ≤ (p0, q̇0) such that for any n and (p', q̇') ≤ (p1, q̇1), there exista (p'', q̇') ≤ (p', q̇') and an in ≤ 2 satisfying (p'', q̇') ⊩ ẋ(n) = in. Then the set

is an element of M and is dense in ℙ. Fix a generic set (G', H') such that p1 ∈ G'. Then val(ẋ, (G', H'))(n) = in if and only if there exists a p ∈ Dn ∩ G' such that (p, q̇1) ⊩ ẋ(n) = in. Thus val(ẋ, (G', H')) ∈ M[G'], a contradiction.

Let f : ω → ω3 be a recursive bijection such that if f(n) =(n0, n1, n2) and n > 0, then n > n0. The construction of the sequences proceeds as follows:

Stage 0. Let and ν0 = . Let {γi}i<ω be an enumeration of the countable set

{α < ω2 | p0(α) is defined ∨ p0 ⊩ “q̇0(α) is defined”}.

Let β(0,i,j) = γi for i, j < ω. Each γi occurs infinitely many times on the list to ensure that it is diagonized infinitely often.

Stage n + 1. We decompose this into 2n + 1-many substages.

At substage j ≤ 2n, define {νσj}σ ∈ 2n+1 and {(pσj, ̇qσj)}σ ∈ 2n+1 such that pσj⌢0(α) = pσj⌢1(α) for each ≠ βf(n) and σ ∈ 2n.

For σ ∈ 2n and i ∈ 2, let νσj⌢i = νσj. If βf(n) < ω1, then

Hence {pσ0}σ∈2n+1 satisfies (2). There are now two cases to consider.

Case 1. βf(n) ≥ ω1. Since (4) only concerns ordinals not less then ω1, let (pσ ⌢ i, q̇σ ⌢ i = for every σ ∈ 2n and i < 2, and go to the next stage.

Case 2. βf(n) < ω1. Fix an enumeration {σj}1 ≤ j ≤ 2n of 2n.

Substage j + 1. By Lemma 9.1.18, there exist an m >|νjσj | and a (p', q̇') ≤ (pjσj ⌢0, ̇qjσj⌢0) such that for any (p'', ̇q') ≤ (p', q̇'), we have Define

Note that pjσj⌢0(α) = pjσj ⌢1 (α) for any α ≠ βf(n). We Have (p'', ̇qjσj ⌢1) ≤ (pjσj ⌢1, ̇qjσj ⌢1).

Let so that for some and Define

Then Hence there is a (r0, ṡ0) ≤ (r'0, q̇') such that (r0, ṡ0) ⊩ ẋ(m) = 0 and for some Define

Then Now for and

Let be a name such that

This completes the construction at substage j + 1.

For σ ∈ 2n and i < 2, let be an enumeration of the countable set

{α < ω2 | (∃σ)(σ ∈ 2n+1 ∧ (pσ(α) is defined ∨ pσ ⊩ “q̇σ(α) is defined”))}.

Let βn+1,i,j = γi for i, j < ω. This ends the construction at stage n + 1. Finally let αn = βf(n) for each n.

It is immediate that the sequences defined satisfy conditions (1)–(4) and hence the proof of Theorem 9.1.7 is complete.

9.1.3 Exercises

Exercise 9.1.1. Prove that there is a partial ordering 〈2ω, ≤P〉 into which every locally countable partial ordering of size not greater than 2ℵ0 is embeddable.

Exercise 9.1.2. Prove Theorem 9.1.4.

Exercise 9.1.3. (Sacks [117]). A partial ordering 〈P, ≤P〉 is locally finite if for any p ∈ P, |{q | q ≤P p}| < ℵ0. Prove that every locally finite partial ordering in 〈2ω, ≤P〉 is embeddable into 〈, ≤〉.

Exercise 9.1.4. Prove that there is an independent set X of Turing degrees of size 2ℵ0 .

Exercise 9.1.5. Prove Theorem 9.1.6.

9.2 Embedding locally finite upper semilattices into 〈, ≤〉

9.2.1 Embedding an upper semilattice

Definition 9.2.1. A partial ordering 〈P, ≤〉 is an upper semilattice if for any p, q ∈ P, there is an r ∈ P such that r is the ≤ -least upper bound of p and q.

We use p ∪ q to denote the least upper bound of p and q. Clearly 〈, ≤〉 is an upper semilattice. The following strengthens Exercise 9.1.3 under an additional hypothesis.

Theorem 9.2.2. (Sacks[117]). Assume CH. Every locally finite upper semilattice 〈2ω, ≤, ∪〉 is embeddable into 〈, ≤〉.

In [117], Sacks asked whether the conclusion of Theorem 9.2.2 is a theorem of ZFC. Groszek and Slaman provided a negative answer to the question.

Theorem 9.2.3 (Groszek and Slaman [40]). There is a model N ⊨ ZFC + 2ℵ0 = ℵ2 in which there is a locally finite upper semilattice 〈ω2, ≤, ∪〉 not embeddable into 〈, ≤, ∪〉.

9.2.2 The proof of Theorem 9.2.3

Suppose that M ⊨ ZFC + GCH. Let {Xβ}β<ω2 be a one-one enumeration of (ω1) in M. be an upper semilattice in M such that

(1)|U|=ℵ2;

(2)ω2 ⊆ U, and

(3)(∀α < ω1)(∀β < ω2)(β > ω1 →(ω1 ≤u α ∪ β ↔ α ∈ Xβ)).

Let ℙ = Πα<ω2ℙα be an ω2-product with finite support of Cohen forcing conditions. By Theorem 6.1.11, we have the following:

Lemma 9.2.4. ℙ is c.c.c. and hence preserves cardinals.

Suppose G is ℙ-generic. Then G may be viewed as an ω2-sequence {Gα}α<ω2 of reals. By Lemma 6.1.6, we have

Lemma 9.2.5. For any ℙ-generic set

Suppose that there is a ℙ-generic set G, M[G] ⊩ (∃f)(“f is an embedding of Let p0 be such that

p0 ⊩ “ḟ is an embedding of into (, ≤ )”.

Then for α ≤ ω1 and n < ω, there is a condition pα, n ≤ p0 in G such that

for some i < 2.

Given a condition p, let αp = min{α | (∀β ≥ α)(p(α) is undefined)}. Set

α0 = sup{αpγ,n | γ < ω1}.

Then α0 < ω2. Let ℙ<α0 = Πβ<α0ℙβ and ℙ≥α0 = Πβ≥α0ℙβ. Then f(α) ∈ M[G<α0] where G<α0 = {(β, Gβ) | β < α0} is a ℙ<α0-generic set. Since ℙ=ℙ<α0 ×ℙ≥α0, by Theorem 6.1.9, G≥α0 = {(β, Gβ) | β ≥ α} is a ℙ≥α0-generic set over M[G<α0]. Obviously both ℙ<α0 and ℙ≥α0 preserve cardinals. Moreover, M[G<α0] ⊩ GCH. Thus without loss of generality, we may assume that M[G<α0] = M. In other words, forany α ≤ ω1, there is a real xα ∈ M such that p0 ⊩ ḟ(α) = xα.

Now for α < ω1 < β < ω2, we have

p0 ⊩ “xω1 ≤T ḟ(β)⊕ xα” ⇔ α ∈ Xβ.

By Proposition 6.1.17 and a rearrangement of p0 (if necessary), we may assume that p0 ∈ ℙ<ω1. Let αp0 = min{α | (∀β ≥ α)(p0(α) is undefined)}. Then αp0 is a countable ordinal. Since only at most countably many ordinals occur in ḟ (β),for β > ω1, if ḟ(β) is not a ℙ<ω1-name then there is a permutation iβ switching ordinals in f(β) to countable ordinals greater than αp0. Inother words, iβ induces an automorphism of ℙ so that iβ(p0) = p0 but iβ(ḟ(β)) ∈ ℙ<ω1. By Proposition 6.1.17 again,

Now in M, there are at most 2ℵ0 =ℵ1 many ℙ<ω1-names for reals. Thus there exist β0 ≠ β1 such that iβ( ḟ(β0)) = iβ(ḟ(β1)). Hence Xβ0 = Xβ1, contradicting the assumption.

Let N = M[G]. Then N ⊨ is not embeddable into 〈, ≤, ∪〉”. This completes the proof of Theorem 9.2.3.

Remark 9.2.6. Both the conclusions of Theorem 9.1.4 (see [4]) and Theorem 9.2.2 (see [167]) are provable under ZFC + MA +¬CH.

9.2.3 Exercises

Exercise 9.2.1. Prove that given a model M of ZFC, if both g1 and g2 are Cohen generic reals over M, then M[g1] ≡ M[g2], i. e. elementarily equivalent. Show that this is not true for forcing notions in general.

Exercise 9.2.2. (Simpson [4]). Assume ZFC + MA +¬CH. Prove that every locally countable partial ordering 〈2ω, ≤P〉 is embeddable into 〈, ≤〉.