# 6 Set theory – Recursion Theory

## 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  was very similar to that developed in § 5.2. Here we follow the approach of unramified forcing introduced by Shoenfield  (see Kunen  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 pP is called a condition. Given two conditions p, qP, we say that q is stronger than p if qp. DP is dense if for any pP, there is a qD such that qp.

A filter FP is a nonempty set such that

(∀p)(∀q)(qpqFpF);

(∀p)(∀q)(∃r)(pFqFrFrprq).

A generic set GP 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 MM 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) ∈ τpG}.

Let

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

Thus every element xM[G] has a corresponding ℙ-name. We use to denote the ℙ-name of x. We use ǎ to denote {( , p)| bapP} for any aM by induction on the rank of a. Since for any aM, val( ǎ, G) = a, we have MM[G]. Moreover ̇G = {( , p)| pP} is a ℙ-name and val (Ġ, G) = G. Hence GM[G]. 〈M[G], ∈〉 is a transitive model of ZFC and o(M) = o(M[G]).

Definition 6.1.1. Given a condition pP 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 pG,

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)) ⇔ (∃pG)(pφ(τ0,…, τn)).

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

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

(i)qppφqφ;

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

(iii)p ⊩¬φ if and only if (∀qp)(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 AP is an antichain if for p ≠ q in A, there is no r satisfying rp and rq. ℙ 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 nAnM is also countable in M. Thus ℙ does not collapse (ω1)M.

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

Definition 6.1.5 (Martin’s Axiom ). 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 GP that meets every Dα. We use MA to denote (∀κ < 20)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 xM[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  for a detailed proof).

#### 6.1.3 κ-closedness

Two conditions p and q in ℙ are compatible if pq or qp. 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 qpα for each α < ν. Satisfying the κ-closed property is another basic tool for preserving cardinals.

Lemma 6.1.7. Ifhas the κ-closed property and AMwith |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 iI. Let C (I). The C-product forcing ℙ=〈P, ≤〉 is a partial ordering satisfying the following for each pP:

there is a JC such that p(i) is defined if and only if iJ and p(i) ∈ Pi;

qp in P if and only if for any iI, 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, ≤Pand ℚ = 〈Q, ≤Qare two notions of forcing. Let ℙ×ℚ be the product ofand ℚ. Then for any set GP × Q, G is generic over M if and only if G = G1 × G2 where G1P 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 .

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 iI. Then the product forcing ΠiIi 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 , 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;

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

For β = ξ + 1, a forcing condition pPβ 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 qPβ, define pβ q if pξqξ and pξp(β) ≤ q(β).

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

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

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

If qPβ, 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 .

#### 6.1.6 Embeddings and isomorphisms

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

(∀p0)(∀p1)(p0p1f(p0) ≤ f(p1));

(∀p0)(∀p1)(p0|p1f(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)(p0p1f(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<ω, qp if and only if qp.

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 .

Proposition 6.2.3. Suppose that g = g1g2. 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. Letbe a notion of product Cohen forcing of length κ and let G be generic. Then for any AS in M[G], there is an α ≤ min{κ, |S|M} such that A ∈ M[GP < α] where P<α = Πγ<α2<ω.

#### 6.2.2 Random forcing

Random forcing was introduced by Solovay  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 TT is a subtree of 2<ω such that μ([T]) > 0;

T1T2 if and only if T1T2.

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 qp if and only if qp. 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:

pLκ 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, qLκ, qp if and only if qp. (κ) 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<ω,pG p(α, n) maps ω onto α. Hence M[G] ⊨ κω1. We prove that (κ) satisfies κ-c.c.

Suppose that ALκ is an antichain of cardinality κ. Without loss of generality, we may assume that there is an n such that |Dom(p)| = n for every pA. We claim that there is an α < κ such that Aα = {pA | (∃n)(α, n) ∈ Dom(p)} has cardinality κ. Otherwise, there exist p, qA 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 = {pAα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, qBα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, qBα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α0Aα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α0Bα1 ⊇ … ⊇ Bαn* such that |Bαn* | = κ and for all pBα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  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  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, T2T, T1T2 if and only if T1T2.

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 ). Suppose that g is Sacks generic over a model M of ZFC and xM[g]\ M is a real. Then there are reals z0, z1M such that xz0T g and xT z1g.

Proof. Suppose that g is Sacks generic produced by a generic filter G and let xM[g]\ M. By Theorem 6.1.2, there is a condition T0 such that T0G (i.e. g ∈[T0])and Let T1T0. 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, T1Tσ ∩ [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 T2DG. 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)] ⊩ (ňσ) = ̌jT2 ∩[T(σ(1−i))] ⊩ nσ) = ̌1− ̌j)).

Let

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

Then z0M and may be coded as a real.

Note that g ∈[T2]. Since xM[g], to compute gn 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 = gn. Hence gT xz0.

To see that there is a real z1M such that gz1T x, assume that for some τ ∈ 2σ. Let z1 = {(σ, τ)| T2 ∩[T(σ)] ⊩ x ↾ ̌ |σ|= ̌ τ}. Then xz1g.

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 (20) .

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