This chapter reviews results in set theory that have recursion-theoretic applications. Some of these will be stated without proof for future reference.
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).
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 ⊩ φ(τ).
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).
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 κ.
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.
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].
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),
Exercise 6.1.1. Prove Proposition 6.1.17.
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<ω.
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.
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.
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]).