6 Set theory

This chapter reviews results in set theory that have recursion-theoretic applications. Some of these will be stated without proof for future reference.

6.1 Set-theoretic forcing

The technique of forcing was discussed in the context of recursion theory in Chapter 5. The original version of the method as presented in Cohen [18] was very similar to that developed in § 5.2. Here we follow the approach of unramified forcing introduced by Shoenfield [130] (see Kunen [78] for an excellent exposition of the subject).

6.1.1 Forcing and genericity

Let M = 〈M, ∈〉 be a countable transitive model of ZFC and let ℙ = 〈P, ≤〉 be a partial ordering in M. An element p ∈ P is called a condition. Given two conditions p, q ∈ P, we say that q is stronger than p if q ≤ p. D ⊆ P is dense if for any p ∈ P, there is a q ∈ D such that q ≤ p.

A filter F ⊆ P is a nonempty set such that

–(∀p)(∀q)(q ≤ p ∧ q ∈ F → p ∈ F);

–(∀p)(∀q)(∃r)(p ∈ F ∧ q ∈ F → r ∈ F ∧ r ≤ p ∧ r ≤ q).

A generic set G ⊆ P is a filter that meets every dense set. In general, a generic set does not belong to M except for very special partial orderings. If G ∉ M, then there is a model M[G] = 〈M[G], ∈〉 of ZFC such that M ∪ {G} ⊆ M[G] and o(M) = o(M[G]). This is defined as follows.

First, a ℙ-name in M is defined by induction:

– is a ℙ-name;

–if τ ⊆ the set of ℙ-names × P, then τ is a ℙ-name.

We use Mℙ to denote the class of ℙ-names. Note that Mℙ ⊂ M and is not a member of M. Suppose G is generic. Define val(τ, G) by induction:

–if τ is not a ℙ-name, then val(τ, G) = τ;

–otherwise, val(τ, G)={val(σ, G)|(σ, p) ∈ τ ∧ p ∈ G}.

Let

M[G]={val(τ, G)| τ ∈ M}.

Thus every element x ∈ M[G] has a corresponding ℙ-name. We use ẋ to denote the ℙ-name of x. We use ǎ to denote {(, p)| b ∈ a ∧ p ∈ P} for any a ∈ M by induction on the rank of a. Since for any a ∈ M, val( ǎ, G) = a, we have M ⊆ M[G]. Moreover ̇G = {(, p)| p ∈ P} is a ℙ-name and val (Ġ, G) = G. Hence G ∈ M[G]. 〈M[G], ∈〉 is a transitive model of ZFC and o(M) = o(M[G]).

Definition 6.1.1. Given a condition p ∈ P and a formula φ(τ0,…, τn) with τ0,…, τn ∈ Mℙ, we say that p forces φ(τ0,…, τn), or p ⊩ φ(τ0,…, τn), if and only if for any generic set G with p ∈ G,

〈M[G], ∈〉 ⊨ φ(val(τ0, G),…, val(τn, G)).

Theorem 6.1.2.

(i)The class {(p, φ, (τ0,…, τn)) | p ⊩ φ(τ0,…, τn)} is definable in M;

(ii)for every generic G and formula φ(τ0,…, τn) with τ0,…, τn ∈ Mℙ,

〈M[G], ∈〉 ⊨ φ(val(τ0, G),…, val(τn, G)) ⇔ (∃p ∈ G)(p ⊩ φ(τ0,…, τn)).

Theorem 6.1.2 is not surprising when taken together with the definition of ⊩ in § 5.2 (see [78]). The following facts about the forcing relation are standard.

Proposition 6.1.3. For any formula φ, condition p and ℙ-names τ0,…, τn,

(i)q ≤ p ∧ p ⊩ φ ⇒ q ⊩ φ;

(ii)p ⊩ φ ∧ ψ if and only if p ⊩ φ and p ⊩ ψ;

(iii)p ⊩¬φ if and only if (∀q ≤ p)(q ⊮ φ);

(iv)the set {p | p ⊩¬φ ∨ p ⊩ φ} is dense;

(v)p ⊩(∃x)φ(x) if and only if the set {q | q ≰ p ∨(∃τ ∈ Mℙ)(q ⊩ φ(τ))} is dense;

(vi)p ⊩(∃x)φ(x) if and only if there is a ℙ-name τ ∈ Mℙ such that p ⊩ φ(τ).

6.1.2 κ-chain condition and Martin’s Axiom

Given a partial ordering ℙ = (P, ≤), a set A ⊆ P is an antichain if for p ≠ q in A, there is no r satisfying r ≤ p and r ≤ q. ℙ has the κ-chain condition, or κ-c.c., if in M every antichain of ℙ has cardinality less than κ. In particular, ω1-c.c. is known as the countable chain condition, or c.c.c. A chain condition restricts the possible values of a function in a generic extension. In fact, chain conditions are used as basic tools for the preservation of cardinals in a generic extension. For example, if ℙ = 〈P, ≤〉 satisfies c. c. c. and f : ω → (ω1)M is a function in M[G] for some generic G, then for every n < ω, the set An = {α < (ω1)M |(∃p)(p ⊩ ḟ(ň) = )} ∈ M is countable in M so that nAn ∈ M is also countable in M. Thus ℙ does not collapse (ω1)M.

Lemma 6.1.4. If ℙ has the κ-chain condition, then for any generic set G, (κ)M = (κ)M[G].

Definition 6.1.5 (Martin’s Axiom [90]). Let κ be a cardinal. MAκ states that for any c.c.c. partial ordering ℙ = 〈P, ≤〉 and any κ-sequence of dense sets {Dα}α<κ, there is a filter G ⊆ P that meets every Dα. We use MA to denote (∀κ < 2ℵ0)MAκ.

Obviously MAω is a theorem of ZFC. It is known that if ZFC is consistent then so is ZFC + MA. The κ-chain condition is also used to compute the cardinality of a power set.

Lemma 6.1.6. Suppose that κ > ℵ0 is a regular cardinal and ℙ = 〈P, ≤〉 satisfies κ-c.c. in M with |P|= λ. Then for any regular cardinal η ∈ M and generic set G, M[G] ⊨ 2η ≤((λ<κ)η)M.

Proof (Sketch). Every x ∈ M[G] ∩ 2η corresponds to a ℙ-name ̇x ⊆ η × (P). Moreover, we may assume that for any γ < η, {p |(, p) ∈ ̇x} is an antichain. There are λ<κ-many antichains in M. Hence there are at most (λ<κ)η-many such ℙ-names. In other words, M[G] ⊨ 2η ≤ ((λ<κ)η)M (see [78] for a detailed proof).

6.1.3 κ-closedness

Two conditions p and q in ℙ are compatible if p ≤ q or q ≤ p. Given a cardinal κ, ℙ has the κ-closed property (in M) if for any sequence {pα}α < ν of compatible conditions of length ν < κ, there is a q such that q ≤ pα for each α < ν. Satisfying the κ-closed property is another basic tool for preserving cardinals.

Lemma 6.1.7. If ℙ has the κ-closed property and A ∈ Mwith |A| < κ, then any function f in a generic extension M[G] with domain A belongs to M.

It follows that κ-closed property preserves all cardinals not greater than κ.

6.1.4 Product forcing

Definition 6.1.8. Let I be an index set and let ℙi = 〈Pi, ≤i〉 be a notion of forcing for i ∈ I. Let C ⊆ (I). The C-product forcing ℙ=〈P, ≤〉 is a partial ordering satisfying the following for each p ∈ P:

–there is a J ∈ C such that p(i) is defined if and only if i ∈ J and p(i) ∈ Pi;

–q ≤ p in P if and only if for any i ∈ I, p(i) is defined implies q(i) is defined and q(i) ≤ i p(i).

If C is the collection of all finite subsets of I, then ℙ is known as product forcing with finite support. If C is the collection of all countable subsets of I, then ℙ is product forcing with countable support. I is often taken to be an ordinal.

Let I be an ordinal γ. If C = I, we call ℙ simply the product of {ℙα}α<γ. Then the C-product forcing ℙ = Πα<γℙα may be decomposed into Πα<βℙα × Πβ≤α<γℙα. In other words, ℙ ≅ Πα<βℙα × Πβ≤α<γℙα.

Theorem 6.1.9. Suppose that ℙ = 〈P, ≤P〉 and ℚ = 〈Q, ≤Q〉 are two notions of forcing. Let ℙ×ℚ be the product of ℙ and ℚ. Then for any set G ⊆ P × Q, G is generic over M if and only if G = G1 × G2 where G1 ⊆ P is generic over M and G2 is generic over M[G1]. Moreover, M[G] = M[G1][G2].

In general, the c.c.c. property is not preserved under product forcing. This limitation is addressed by the following stronger property.

Definition 6.1.10. A forcing notion has property (K) if every uncountable set of conditions has an uncountable subset of mutually compatible elements.

The next theorem is in Jech [53].

Theorem 6.1.11.

(i)Let γ ≥ ω be an ordinal and assume that for each α < γ, ℙα has property (K). Then the product forcing ℙ = Πα<γℙα with finite support has property (K);

(ii)Suppose that κ ≥ ℵ1, κℵ0 = κ and |Pi| ≤ κ for each i ∈ I. Then the product forcing Πi∈Iℙi with countable support satisfies κ+-c.c.

6.1.5 Iterated forcing

Product forcing is less amenable to fine tuning the construction of a model. The notion of iterated forcing, introduced by Solovay and Tennenbaum [147], offers more “flexibility” in this respect. Given an ordinal α, let I ⊆ (α) be an idealsuchthat {0} ∈ I. We define iterated forcing ℙβ = 〈Pβ, , γ ≤ β, I〉 on ordinals β ≤ α with support I by induction on β.

Definition 6.1.12. For β = 0, ℙ0 = 〈P0, , I〉 satisfies

–Q0 is a notion of forcing;

–p ∈ P0 if and only if p is a function such that Dom(p) = {0} and p(0) ∈ Q0.

For β = ξ + 1, a forcing condition p ∈ Pβ is a partial function whose domain belongs to I so that

–p ↾ ξ = {(η, r)| η < ξ ∧ p(η) = r} ∈ Pξ;

– is a Pξ -name;

–if β ∈ Dom(p), then p ↾ ξ ⊩ p(β) ∈ .

If q ∈ Pβ, define p ≤β q if p ↾ ξ ≤ q ↾ ξ and p ↾ ξ ⊩ p(β) ≤ q(β).

If β is a limit ordinal, then a forcing condition p ∈ Pβ is a partial function whose domain belongs to Iα so that

–for every ξ < β, p ↾ ξ = {(η, r)| η < ξ ∧ p(η) = r} ∈ Pξ;

–{ξ < β | ξ ∈ Dom(p)} ∈ I.

If q ∈ Pβ, define p ≤β q if and only if p ↾ ξ ≤ q ↾ ξ for every ξ < β.

The two most useful notions of iterated forcing are those defined in terms of finite and countable support.

Proposition 6.1.13. Let α be an infinite ordinal. Assume that M ⊨ ZFC ∧ “κ > ω is regular”, I = {s | s ⊆ α ∧|s| < ℵ0} and let ℙα = 〈Pα, , γ ≤ α, I〉. If for each p and β ≤ α, p ↾ β ⊩ “ satisfies κ-c.c.”, then for each β ≤ α, ℙβ satisfies κ-c.c. in M.

Remark 6.1.14. A similar statement holds for proper forcing in the case when I is countably supported. The proofs can be found in [53].

6.1.6 Embeddings and isomorphisms

Definition 6.1.15. A function f from 〈P, ≤〉 into 〈Q, ≤〉 is a dense embedding if

–(∀p0)(∀p1)(p0 ≤ p1 → f(p0) ≤ f(p1));

–(∀p0)(∀p1)(p0|p1 → f(p0)|f(p1));

–Range(f) is a dense subset of Q.

A function f from 〈P, ≤〉 into 〈Q, ≤〉 is an isomorphism if f is a bijection such that (∀p0)(∀p1)(p0 ≤ p1 ↔ f(p0) ≤ f(p1)). Clearly every isomorphism is a dense embedding.

Definition 6.1.16. Suppose that f : ℙ→ℚ. For any τ ∈ Mℙ, recursively define the corresponding ℚ-name of τ induced by f as

This allows one to prove the following proposition.

Proposition 6.1.17. Let M ⊨ ZFC and let f : ℙ = 〈P, ≤〉 → ℚ = 〈Q, ≤〉 be a dense embedding.

(i)If H is ℚ-generic over M, then f −1(H) is ℙ-generic over M and M[f −1(H)] ⊆ M[H].

(ii)For any formula φ(v0,…, vn),

6.1.7 Exercise

Exercise 6.1.1. Prove Proposition 6.1.17.

6.2 Some examples of forcing

6.2.1 Cohen forcing

Definition 6.2.1. Cohen forcing ℂ = 〈2<ω, ≤〉 is the notion of forcing such that for any p, q ∈ 2<ω, q ≤ p if and only if q ⪰ p.

Since 2<ω is countable, the following implies that cardinals are preserved under a Cohen extension:

Proposition 6.2.2. Cohen forcing satisfies property (K).

Given a Cohen generic set G, the set g = is called a Cohen real. The next two results are proved in [78].

Proposition 6.2.3. Suppose that g = g1 ⊕ g2. Then g is a Cohen real over M if and only if g1 is a Cohen real over M and g2 is a Cohen real over M[g1].

Proposition 6.2.4. Suppose κ ≥ ω and S ∈ M. Let ℙ be a notion of product Cohen forcing of length κ and let G be generic. Then for any A ⊆ S in M[G], there is an α ≤ min{κ, |S|M} such that A ∈ M[G ∩ P < α] where P<α = Πγ<α2<ω.

6.2.2 Random forcing

Random forcing was introduced by Solovay [150] to construct a model of ZF + DC in which every set of reals is Lebesgue measurable.

Definition 6.2.5. Let μ denote the Lebesgue measure. Random forcing ℝ = 〈T, ≤〉 is a notion of forcing where

–every T ∈ T is a subtree of 2<ω such that μ([T]) > 0;

–T1 ≤ T2 if and only if T1 ⊆ T2.

Proposition 6.2.6. Random forcing satisfies c.c.c.

Proof. Suppose that there is an uncountable antichain {Tα}α<ω1. Then for α ≠ β < ω1, μ([Tα]∩[Tβ]) = 0. Let Sα = [Tα]β<α[Tβ]. Then {Sα}α<ω1 is an uncountable sequence of pairwise disjoint Borel sets with μ(Sα) > 0 for each α < ω1. Let n be such that the set Rn = {Sα | μ(Sα) > } is uncountable. Then 1 = μ(2ω) ≥ μ(Sα∈Rn Sα) = ∞, a contradiction.

A real x is random if it is ℝ-generic.

6.2.3 Collapsing cardinals

Let κ be a cardinal. There is a notion of forcing that collapses all cardinals below κ while preserving κ: Let ℙ(κ) = 〈κ<ω, ≤〉 and for p, q ∈ κ<ω, define q ≤ p if and only if q ⪰ p. Then ℙ(κ) satisfies κ+-c.c. Moreover, for any generic filter G, the function p maps ω onto κ. Thus we have

Proposition 6.2.7. Suppose that κ ≥ ω1 is a cardinal. Then

(i)ℙ(κ) satisfies κ+-c.c.;

(ii)if G is generic, then κ+ = (ω1)M[G].

Note that ℙ(κ) only preserves the successor cardinal κ+. The next notion of forcing allows one to preserve limit cardinals which are regular.

Definition 6.2.8. Let κ ≥ ω be a cardinal. Define Lévy forcing for κ, (κ) = 〈Lκ, ≤〉, as follows:

–p ∈ Lκ if and only if p is a finite function mapping a subset of κ × ω into κ such that for any α < κ and n < ω, if p(α, n) is defined, then p(α, n) < α.

–For any p, q ∈ Lκ, q ≤ p if and only if q ⪰ p.

(κ) may be considered as product forcing with finite support of length κ, where at each α < κ the forcing action collapses α onto ω.

Proposition 6.2.9. Let κ ≥ ω be a regular cardinal and let G be (κ)-generic. Then κ = (ω1)M[G].

Proof. It is clear that for any α < κ, G(α) = n<ω,p∈G p(α, n) maps ω onto α. Hence M[G] ⊨ κ ≤ ω1. We prove that (κ) satisfies κ-c.c.

Suppose that A ⊆ Lκ is an antichain of cardinality κ. Without loss of generality, we may assume that there is an n∗ such that |Dom(p)| = n∗ for every p ∈ A. We claim that there is an α < κ such that Aα = {p ∈ A | (∃n)(α, n) ∈ Dom(p)} has cardinality κ. Otherwise, there exist p, q ∈ A with disjoint domains such that p and q are compatible, which is a contradiction. Hence let α0 be the least α such that Aα has cardinality κ. Let Bα0 = {p ∈ Aα0 |(∀β < α0)(∀n)(β, n) ∉ Dom(p)}. By the assumption on α0, |Bα0| = κ.

Since |Bα0| = κ and |α0| < κ, we may assume that for any p, q ∈ Bα0, {(α0, n)| (α0, n) ∈ Dom(p)} = {(α0, n) | (α0, n) ∈ Dom(q)}. Furthermore since p(α, n) < α in general, we may even assume that for any p, q ∈ Bα0, (α0, n) ∈ Dom(p) implies p(α0, n) = q(α0, n).

Then by the same argument as that for α0, there is an α1 > α0 which is the least ordinal > α0 such that Bα0 ⊇ Aα1 and the latter has size κ. Let Bα1 = Aα1 ∩{p | (∀β)(∀n)(α0 < β < α1 → (β, n) ∉ Dom(p))}. Then |Bα1| = κ.

Thus as before we may define a sequence of ordinals α0 < α1 < … < αn* and a sequence of sets Bα0 ⊇ Bα1 ⊇ … ⊇ Bαn* such that |Bαn* | = κ and for all p ∈ Bαn*, Dom(p) = {α0,…, αn*}. Then |Bαn| ≤ |αn*≤n∗| < κ, a contradiction.

6.2.4 Sacks forcing

Forcing with perfect sets was introduced by Spector [154] in his construction of a set of minimal Turing degree. This method was generalized by Sacks and applied to the hyperarithmetic and set-theoretic setting to produce sets of minimal hyperdegree and minimal degree of constructibility [121] respectively.

Definition 6.2.10. Sacks forcing is a notion of forcing = (T, ≤), such that

–T is the collection of perfect trees ⊆ 2<ω;

–for any T1, T2 ∈ T, T1 ≤ T2 if and only if T1 ⊆ T2.

A Sacks generic real is one which meets every dense collection of perfect sets. The following theorem says that such a real has the “minimality property”.

Theorem 6.2.11 (Sacks [121]). Suppose that g is Sacks generic over a model M of ZFC and x ∈ M[g] M is a real. Then there are reals z0, z1 ∈ M such that x ⊕ z0 ≥T g and x ≤T z1 ⊕ g.

Proof. Suppose that g is Sacks generic produced by a generic filter G and let x ∈ M[g] M. By Theorem 6.1.2, there is a condition T0 such that T0 ∈ G (i.e. g ∈[T0])and

Let T1 ≤ T0. Define a function T : 2<ω → T1 and a sequence of conditions {Tσ}σ ∈ 2<ω and numbers nσ by induction as follows:

Let T() = and T = T1.

Suppose σ ∈ 2<ω, T(σ) is defined and Tσ ⊆ T1. Then Tσ ⊩ ẋ ∉ ∧ ẋ ∈ ̇ 2ω, and there exist an nσ > |σ| as well as conditions T0, T1 ⊆ Tσ ∩ [T(σ)] such that T0 ⊩ ẋ(ňσ) = 0 and T1 ⊩ ẋ(ňσ) = 1, where [T(σ)] is the set of strings extending T(σ).

Then there is a τ ≻ T(σ) and an i ∈ {0, 1} such that τ ∈ Tσ, [τ⌢i]∩ T0 ≠ and [τ⌢(1−i)]∩T1 ≠ . Let T(σ⌢i) = τ⌢i, Tσ⌢ i = [τ⌢i]∩Ti for i ∈ {0, 1}. Then Tσ⌢ i ⊩ ẋ(nσ) = 0 and Tσ⌢(1−i) ⊩ ẋ(nσ) = 1.

Let T2 = {τ |(∃σ)(T(σ) ≻ τ)} ⊆ T1. Then for any σ, T2 ∩[T(σ)] ≤ Tσ. Thus

Let

It is clear that D is a dense set. Hence there is a T2 ∈ D ∩ G. Furthermore, there exist a sequence {nσ}σ∈2<ω and an order-preserving map T : 2<ω → 2<ω such that

–T2 = {τ |(∃σ)(τ ≺ T(σ))};

–(∀σ)(nσ >|σ|);

–(∀σ)(∀i < 2)(∃j < 2)(T2 ∩[T(σ⌢i)] ⊩ ẋ(ňσ) = ̌j∧T2 ∩[T(σ⌢(1−i))] ⊩ ẋ(̌ nσ) = ̌1− ̌j)).

Let

z0 = {(σ, T(σ⌢i), nσ, j)| σ ∈ 2<ω ∧ i ∈ 2 ∧ j ∈ 2 ∧ T2 ∩[T(σ⌢i)] ⊩ ẋ(σ) = ̌j}.

Then z0 ∈ M and may be coded as a real.

Note that g ∈[T2]. Since x ∈ M[g], to compute g ↾ n for a given n, search for a |τ|≥ n and a σ such that for any k ≤|σ|, there are unique nσ↾k and τk ≺ τ such that (σ ↾ k, τk, nσ↾k, j) ∈ z0 if and only if x(nσ↾k) = j. Then τ ↾ n = g ↾ n. Hence g ≤T x ⊕ z0.

To see that there is a real z1 ∈ M such that g ⊕ z1 ≥T x, assume that

for some τ ∈ 2σ. Let z1 = {(σ, τ)| T2 ∩[T(σ)] ⊩ x ↾ ̌ |σ|= ̌ τ}. Then x ≤ z1 ⊕ g.

The method in the proof of Theorem 6.2.11 is typical of what is known as a fusion construction. This line of construction allows one to find, in M, a fusion sequence {Tσ}σ∈2<ω for which there is a condition T2 in M that is an intersection of {Tσ}σ∈2<ω, such that (∀σ)(∀i < 2)(T2 ∩[T(σ⌢i)] ⊩ ẋ(σ) = ). This “splitting property” facilitates the decoding of G from x and the real z.

Corollary 6.2.12. If g is Sacks generic over M = 〈M, ∈〉, then every countable set of ordinals in M[g] is a subset of a countable set in M and (2ℵ0).

Hence Sacks forcing preserves ℵ1. It is known, however, that Sacks forcing may collapse cardinals (see [6]).