6.2.5 Destroying the Axiom of Choice

In general there is no direct way of destroying the Axiom of Choice (AC) by a forcing extension of a transitive model of ZFC. One introduces an intermediate model to achieve this.

Definition 6.2.13.

–A set X is ordinal definable in M, written X ∈ ODM, if there is a formula φ(x, v0,…, vn) together with ordinals α0,…, αn, β in M such that a ∈ X ⇔ ⊨ φ(a, α0,…, αn), where is the collection of sets in M of rank less than β.

–X is hereditarily ordinal definable in M, written X ∈ HODM, if TC({X}) ⊂ ODM.

If M is a transitive model of ZFC, then 〈HODM, ∈〉 is a transitive model of ZFC (see [53]). The notion may be generalized to a wider class by defining OD(A)M and HOD(A)M. If M is a transitive model of ZFC and A ∈ M, then 〈HOD(A)M, ∈〉 is a transitive model of ZF (see [53]). We use HOD(A)M to obtain a model that destroys AC.

Definition 6.2.14. Let A ∈ M,

–A set X is ordinal definable relative to A in M, written X ∈ OD(A)M, if there exist ordinals α0,…, αn, elements a0,…, am ∈ A and a formula φ(x, α0,…, αn, a0,…, am, A) in the expanded language defining X in the structure 〈a0,…, am, ∈〉.

–A set X is in HOD(A)M if TC({X}) ⊂ OD(A)M.

Theorem 6.2.15. Suppose that M ⊨ V = L. Let ℙ = Πi∈ωℂ be a notion of product Cohen forcing with finite support and let G be a ℙ-generic filter. If A = {g |(∃i)(∀j)g(j) = p∈G p(i)(j)}, then there is no well-ordering of the reals in N = 〈HOD(TC({A}))M[G], ∈〉.

Proof. Suppose that there is a bijection F : 2ω → α in N for some α ∈ o(N). We may identify G with the ω-sequence of generic reals {(i, g)| g(j) = p∈G p(i)(j)}.

Let

where Gi = (∀j)(∃p)(p ∈ G ∧ Gi(j) =(p(i))(j)). Obviously val(Ȧ, G) = A. Then there is a formula φ0(x, ν, , , A) defining F(x) = ν via A, ordinals and ∈ A<ω. Let φ1(x, ν, , , A) be

x is the unique real such that φ0(x, ν, , , A).

Then for any real x ∈ M[G], there is a ν < ω1 such that

M[G] ⊨ φ1(x, ν, , , A).

Let n be the least number such that ∈ M[G<n] where G<n = {(i, j)| i < n ∧ (∀j)(∃p)(p ∈ G ∧(p(i))(j) = 1)}. Then Gn ∈ N, and hence

M[G]⊨ φ1(Gn, ν, , , A)

for some ν < α.

Thus there is a condition p ∈ G such that

Let m > n be the least number not in Dom(p). Set π : ω → ω to be a permutation of ω that only swaps m with n. Then π induces an automorphism of ℙ: For every p ∈ P,

Dom(p) = {π(i)| i ∈ Dom(p))})

and

(p)(π(i)) = p(i).

Obviously , , , and (Ȧ) = Ȧ. Moreover, p is compatible with (p). Hence there is a q ∈ ℙ such that q ≤ p, (p). Then

and

This implies that q ⊩ Gn ≠ Gm which is a contradiction.

6.2.6 Exercises

Exercise 6.2.1. Prove that if ZF is consistent, then so is ZF+ “There is an infinite set A of reals all of whose subsets are either finite or cofinite in A”.

Exercise 6.2.2. Prove that Sacks forcing does not satisfy c.c.c.

Exercise 6.2.3. Prove that if g is a real Cohen generic over M ⊨ ZFC, then for any real x ∈ M[g] M, there is a z ∈ M such that x ≤T g ⊕ z.

Exercise 6.2.4. Prove that if g is a real Cohen generic over M ⊨ ZFC, then every analytical real in M[g] is a member of M.

Exercise 6.2.5 (Levy [84]). Prove that if g is a real Cohen generic over L, then

(HOD)L[g] = L.

6.3 A cardinality characterization of -sets

In this section, we present an application of Martin’s Axiom to the characterization of -sets due to Martin and Solovay [90].

6.3.1 Almost disjoint forcing

Definition 6.3.1. Aset A ⊆ 2ω of reals is almost disjoint if for any x ∈ A, |x| = ∞ and for any x ≠ y ∈ A, x ∩ y is finite.

The following notion of forcing was introduced by Silver.

Definition 6.3.2. Given an index set I, an almost disjoint set A = {xi}i∈I and X ⊂ I, ℙ = 〈P, ≤〉 is an almost disjoint forcing corresponding to A and X if every p ∈ P is a partial function from ω to 2 such that

–(∀i ∈ X)(|Dom(p) ∩ xi| < ∞); and

–|{n | p(n) = 1}| < ∞.

We write p ≤P q if p ⪰ q.

Lemma 6.3.3. Given an almost disjoint set A = {xi}i∈I on an index set I and X ⊂ I, the almost disjoint forcing corresponding to A and X is c.c.c.

Proof. Given two conditions p and q, p is incompatible with q if and only if {n | p(n) = 1} ≠ {n | q(n) = 1}. Since there are only countably many finite subset of ω, the lemma is immediate.

Lemma 6.3.4.

(i)For each i ∈ I X, D0,i = {p ∈ P | xi ⊆ Dom(p)} is dense.

(ii)For each i ∈ X and i ∈ ω, D1,i = {p ∈ P ||{n ∈ xi | p(n) = 1}| > i} is dense.

Proof. (i) is obvious. To see (ii), given any condition p, we have |Dom(p) ∩ xi| < ∞. Then simply extend p to a condition q such that |{n ∈ xi | q(n) = 1}| > i.

Theorem 6.3.5. If G is a generic set meeting all D0,i’s and D1,i ’s for all i ∈ I, then the generic set g = p∈G p is a real such that for any i ∈ I, i ∈ X if and only if g ∩ xi is infinite.

Proof. Let G be a generic set meeting all D0,i ’s and D1,i ’s for all i ∈ I. If i ∈ X, then by (ii) of Lemma 6.3.4, xi ∩ g is infinite. If i ∉ X, then by (i) of Lemma 6.3.4, xi ⊆ Dom(p) for some p ∈ G. But |{n | p(n) = 1}| < ∞, and so xi ∩ g is finite.

Hence almost disjoint forcing produces a real g which codes a large set X via an almost disjoint set A.

6.3.2 Martin–Solovay’s characterization

Lemma 6.3.6. Assume MAℵ1 and suppose that (ω1)L[x] = ω1 for some x ∈ 2ω. If B ⊆ 2ω has cardinality ℵ1, then B is .

Proof. We assume that x(0) = 1 for any x ∈ B.

Since (ω1)L[x] = ω1, let C = {z | z(0) = 0 ∧ z ∈ [z ⊕ x]}. Then C is a -set of cardinality ℵ1.

Let f : ω → 2<ω be a recursive bijection. Define

T = {σ ∈ 2<ω |(∃τ ∈ 2<ω)(∀n < |σ|)(σ(n) = 1 ↔ f(n) ⪯ τ))}.

Note that [T] is an almost disjoint set. Moreover T is a recursive perfect tree and there is a recursive homeomorphic h : 2ω → [T]. Also note that any x ∈[T] is recursive in each of its infinite subsets. Let C0 = {y |(∃x ∈ C)(h(x) = y)} and B0 = {y |(∃x ∈ B)(h(x) = y)}. Suppose p0, p1, … is a recursive enumeration of the prime numbers. Let

B0 = {xα}α<ℵ1,

C0 = {yα}α<ℵ1,

B1 = {xα,n |(∀i ∈ ω)(xα,n(i) = 1 ↔(∃j)(i is the -th element of xα))}

and

C1 = {yα,n |(∀i ∈ ω)(yα,n(i) = 1 ↔(∃j)(i is the -th element of yα))}.

Set A = B0 ∪ C0. Then A is almost disjoint, and x ∈ C1 if and only if

(i)there is a z ≤T x and an n ∈ ω such that z ∈ C0, and

(ii)(∀i ∈ ω)(x(i) = 1 ↔(∃j)(i is the -th element of z)).

Then C1 is . By MAℵ1, Lemma 6.3.3 and Theorem 6.3.5, there is a real g such that for any α < ℵ1 and n ∈ ω,

(1)g ∩ xα,2n+1 is infinite if and only if n ∈ yα; and

(2)g ∩ yα,2n+2 is infinite if and only if n ∈ xα.

Let h0 be a function so that h0(x, n) = {i |(∃j)(i is the -th element of x)}. Note that h0(xα, n) = xα,n and h0(yα, n) = yα,n.

Set h1(x) = {n ||h0(x,2n + 1) ∩ g|=∞} and h2(x) = {n ||h0(x,2n + 2) ∩ g|=∞}. Then for any x ∈ 2ω,

x ∈ B0 ↔ h1(x) ∈ C0 ∧ h2(h1(x)) = x,

showing that B is .

Theorem 6.3.7 (Martin and Solovay [90]). Assume MAℵ1. Then (ω1)L[x] = ω1 for some x ∈ 2ω if and only if every subset of 2ω with cardinality ℵ1 is .

Proof. Suppose that (ω1)L[x] < ω1 for all x ∈ 2ω. Let A = {xα}α<ω1 be a maximal chain of Turing degrees. Then A has cardinality ℵ1 and contains no perfect subset. It follows that for any real x, A must contain a real not constructible in L[x]. If A is (x0) for some x0, then by Lemma 4.3.2, A contains a perfect subset which is a contradiction.

Conversely suppose that (ω1)L[x] = ω1 for some x ∈ 2ω. By Lemma 6.3.6, every subset of 2ω of cardinality ℵ1 is .

Remark 6.3.8. Theorem 6.3.7 may be viewed as a result that goes “beyond the limits” of recursion theory, in which typically a lightface version of a theorem is proved and then relativized to a boldface version. However, in this case there is no lightface version for Theorem 6.3.7.

An immediate consequence of Theorem 6.3.7 (see Exercise 6.3.3) is that if MAℵ1 holds, then (ω1)L[x] = ω1 for some x ∈ 2ω if and only if every union of ℵ1-many Borel sets is . In contrast to this, Harrington [44] proved that for any cardinal κ < 2ℵ0, there is a model of ZFC in which any union of κ-many Borel sets is .

6.3.3 Exercises

Exercise 6.3.1 (Martin and Solovay [90]). Assume MA. Prove that for any X ⊂ 2ℵ0 with |X| < 2ℵ0, there is a real g such that L[g] = L[X].

Exercise 6.3.2 (Martin and Solovay [90]). Assume MA. Prove that 2κ = 2ℵ0 for any κ < 2ℵ0.

Exercise 6.3.3 (Martin and Solovay [90]). Assume MAℵ1. Prove that (ω1)L[x] = ω1 for some x ∈ 2ω if and only if every union of ℵ1-many Borel sets is .

Exercise 6.3.4 (Harrington [44]). If M ⊨ ZFC + ω1 = and A ⊆ 2ω in M, then there is a c.c.c. extension N of M in which A is .

6.4 Large cardinals

Despite a fairly comprehensive set of axioms for a theory of sets, a considerable number of important mathematical problems are known to be independent of ZF. Additional assumptions have been introduced to study such problems, and among the assumptions are those involving the notion of a large cardinal. We discuss some of them here.

6.4.1 Inaccessible cardinals

Definition 6.4.1.

–A cardinal κ is inaccessible if κ is regular and for every cardinal ν < κ, 2ν < κ;

–A cardinal κ is weakly inaccessible if κ is a regular limit cardinal.

We only consider κ > ω here. The assumption that there is an inaccessible cardinal is the weakest large cardinal axiom. If κ is inaccessible, then ZFC ⊢ “〈Vκ, ∈〉 ⊨ ZFC”. In other words, ZFC +(∃κ)(κ is inaccessible) implies that ZFC is consistent. By Gödel’s second Incompleteness Theorem, ZFC + “ZFC is consistent” does not imply the consistency of “ZFC +(∃κ)(κ is inaccessible)”. This means that one is not able to construct a model of “ZFC +(∃κ)(κ is inaccessible)” by assuming that there is a model of ZFC.

At first sight, the notion of an inaccessible cardinal appears to be disconnected from the structure of the set of reals. Rather surprisingly, the two are closely linked, as illustrated by the following example.

Proposition 6.4.2. (Solovay [149]). If there is no uncountable thin set, then ω1 is inaccessible in L.

Proof. Clearly ω1 is regular in L. Since 〈L, ∈〉 ⊨ GCH, it is sufficient to show that ω1 is a limit cardinal in L.

Suppose not. Then there is a countable ordinal γ < ω1 such that 〈L, ∈) ⊨ ω1 = γ+ = |2γ|. Since γ is countable, there is an x which computes a well-ordering of ω of order type γ. Then 〈L[x], ∈〉 ⊨ 2ω = ω1. Relativizing the proof of Corollary 4.3.6 to x, we have {z | z ∈ [x]} to be an uncountable (x)-thin set, a contradiction.

Proposition 6.4.2 is concerned with the classical topic in descriptive set theory of the existence of perfect subsets of an uncountable definable set of reals. It says that to require all -sets to be “well-behaved”, one would have to appeal at least to the existence of an inaccessible cardinal. This situation may be viewed from the perspective of reverse mathematics, a program which investigates set existence axioms that are necessary and sufficient to prove theorems in “ordinary mathematics”. In the present context, one is interested in set-theoretic axioms that are necessary and sufficient to establish the consistency of a statement in descriptive set theory, relative to the consistency of ZF or ZFC. More precisely, given such a statement φ in descriptive set theory, is there a large cardinal axiom ψ such that ZFC + φ (or ZF + φ) is consistent if and only if ZFC + ψ is consistent? When this holds, we say that φ is equiconsistent with ψ. The next result due to Solovay exemplifies this point.

Proposition 6.4.3. (Solovay [149]). The statement that every uncountable -set has a perfect subset is equiconsistent with the existence of an inaccessible cardinal.

Proof. By Proposition 6.4.2, the statement that every uncountable -set has a perfect subset implies ω1 is inaccessible in L. Hence over ZFC, the consistency of the statement implies the consistency of the existence of an inaccessible cardinal.

Now suppose that there exists an inaccessible cardinal κ in a transitive model M of ZFC. Fix an (κ)-generic set G over M. By Proposition 6.2.9, κ = (ω1)M[G]. Let x ∈ M[G]. Then there is a sequence of conditions … ≤ pn ≤ … ≤ p0 such that for any n, pn ∈ G forces the value of x(n). Since κ = (ω1)M[G], there is a regular cardinal η < κ such that pn ∈ L(η) for every n and hence x ∈ M[G ∩ L(η)]. Thus (ω1)L[x] ≤(ω1)M[G∩L(η)] < η+ < κ. In other words,

M[G]⊨ “(ω1)L[x] < ω1”.

Relativizing the proof of Corollary 4.3.6 to x, we conclude that the largest (x)-thin set {z | z ∈ [x]} is countable. Then

M[G] ⊨ “Every uncountable -set has a perfect subset”.

6.4.2 Measurable cardinals

For a given infinite cardinal κ, consider (κ) as a partially ordered set under ⊆.

Definition 6.4.4.

–A set A ⊆ (κ) is an ultrafilter over κ if it is a filter and for any a ⊆ κ, either a ∈ A or κ a ∈ A;

–a filter A is nonprincipal if for any a ∈ A, there exists a b ∈ A such that a ⊈ b;

–let η ≤ κ be a cardinal. A filter A is η-complete if for any β < η and any sequence {aα}α < β in A, α<β aα ∈ A.

A κ-complete nonprincipal ultrafilter A over κ induces a κ-additive zero-one measure μ on (κ) defined so that for any a ⊆ κ, μ(a) = 1 if and only if a ∈ A. It is not difficult to construct under ZFC an ω-complete nonprincipal ultrafilter A over ω. For κ > ω, however, no κ-complete nonprincipal ultrafilter A over κ can be proved to exist within the same axiom system.

Definition 6.4.5. We say that κ > ω is measurable if there exists a κ-complete non-principal ultrafilter A over κ.

It can be proved that every measurable cardinal is inaccessible (see [53]). Existence of a measurable cardinal is a very strong large cardinal assumption. Although it is a major notion in set theory, none of the results proved in this book requires this assumption.

6.4.3 0♯

Compared to a measurable cardinal, 0♯ is a relatively small large cardinal. Nevertheless, it plays a significant role in the study of definability. According to Slaman (Gödel Lecture, 2001), “0♯ is the recursion theorist’s passport to set theory”. In a rather striking way, the definition of 0♯ is more involved than those of the large cardinals considered thus far.

Definition 6.4.6. Assume that

(i)for any pair of uncountable cardinals η < κ, 〈Lη, ∈〉 ≺ 〈Lκ, ∈〉;

(ii)there is a unique closed and unbounded class I of ordinals containing all uncountable cardinals such that for any cardinal κ > ω,

(a)|I ∩ κ|= κ;

(b)for any ψ(v0,…, vk), any two increasing sequences <, …, and <, … , in I ∩ κ, we have 〈Lκ, ∈〉 ⊨ ψ(, … , )⇔〈Lκ, ∈〉 ⊨ ψ(, … , );

(c)every element a ∈ Lκ is definable in 〈Lκ, ∈〉 with parameters in I ∩ κ.

Then n ∈ 0# if and only if n is the Gödel number of a formula φ such that 〈Lℵω , ∈〉 ⊨ φ(ℵ1,…, ℵm+1).

The term 0# was introduced by Solovay. Gaifman [32] proved that the existence of 0♯ follows from the existence of a measurable cardinal. Silver [137] derived the same conclusion assuming the existence of a Ramsey cardinal, known to be weaker than that of a measurable cardinal. Solovay [148] proved that 0# is a nonconstructible -set of integers. Since every -real belongs to L (Corollary 4.2.9 (ii)), this gives as the optimal bound for constructibility of reals under a large cardinal assumption.

Though the definition of 0♯ appears to be undefinable in the language of set theory, it can be reformulated model-theoretically. This enabled Silver to prove that 0♯ is a -singleton and is hence . 0♯ may well be the weakest large cardinal axiom that is incompatible with V = L.

Proposition 6.4.7. If 0♯ exists, then every constructible real is recursive in 0♯. Hence there are only countably many constructible reals.

Proof. Suppose that 0♯ exists and x is constructible. Since x ∈ Lω1, by Definition 6.4.6 (iic) there is a formula φx(v, u1,…, um) and an increasing sequence i1,…, im in I ∩ Lω1 such that for any n < ω, n ∈ x if and only if 〈Lω1 , ∈〉 ⊨ φx(n, i1,…, im).

For each n, let φn(v) be a formula defining n so that

(∃v0)…(∃vn)(∀v)(v ∉ v0 ∧ v1 = v0 ∪ {v0} ∧ v2 = v1 ∪ {v1} ∧ …∧

vn = vn−1 ∪ {vn−1} ∧ v = vn).

Then

n ∈ x ⇔〈Lω1, ∈〉 ⊨ (∃v)(φn(v) ∧ φx(v, i1,…, im)).

By Definition 6.4.6 (i) and (ii),

n ∈ x ⇔ 〈Lℵω, ∈〉 ⊨ (∃v)(φn(v) ∧ φx(v, ℵ1,…, ℵm)).

Clearly the set {⌜(∃v)(φn(v) ∧ φx(v, u1,…, um))⌝ | n < ω} is recursive and

n ∈ x ⇔⌜(∃v)(φn(v) ∧ φx(v, u1,…, um))⌝ ∈ 0♯.

Thus x ≤T 0♯.

Proposition 6.4.7 implies that 0♯ has extremely high computational power. Recursion-theoretically, one may view 0♯ as the “jump” of 0 under the #-operator.

While 0♯ collapses cardinals in L, its absence presents quite a different picture provided by Jensen’s remarkable Covering Lemma.

Theorem 6.4.8 (Jensen [21]). If 0♯ does not exist then every uncountable set of ordinals is contained in a constructible set of the same cardinality.