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 [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 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 [78]). 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 [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 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 [78] 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 [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 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 [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;

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 [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)(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 [78].

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 [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 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 [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, 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 [121]). 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)] ⊩ (ňσ) = ̌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 [6]).