Contents / Set Theory / Advanced Set Theory

Chapter 6

Advanced Set Theory

The Borel hierarchy as the smallest sigma-algebra on the opens, closing at exactly omega-one; analytic sets as continuous images of Baire space, and where the projective hierarchy escapes ZFC; determinacy, with the axiom of determinacy proved to contradict choice and the Banach-Mazur game characterising meagreness; Martin's axiom, what it decides about the continuum, and the proper forcing axiom; Ramsey's theorem in both versions with Sierpinski's colouring showing the continuum fails; the sunflower lemma; and clubs, stationary sets and Fodor's lemma.

Introduction

Descriptive set theory, large cardinals, forcing axioms, and infinite combinatorics.

This chapter is about the sets that mathematics actually uses. The paradoxical objects of set theory — a non-measurable set, a decomposition of the ball into five pieces, a well-ordering of the reals — are all produced by the axiom of choice out of nothing, and none of them can be written down. The sets one meets in analysis, topology and probability can be written down: they are built from open sets by countably many unions and complements, or they are projections of such sets. The first discovery of descriptive set theory is that definability buys regularity. A set you can describe is measurable, has the Baire property, and if uncountable contains a perfect set. The second discovery is that this stops working, and exactly where it stops is not decided by ZFC.

The chapter has three movements. The first develops the hierarchies — Borel, then projective — and proves the classical regularity theorems, ending with infinite games, where determinacy turns out to be the single hypothesis from which every regularity property flows. The second movement is about models: Gödel's $L$ , the core model $K$ , and the covering lemmas that say how close $V$ must stay to those models when large cardinals are absent. The third movement is combinatorial: Martin's axiom and its proper-forcing strengthening, clubs and stationary sets, $♢$ and $□$ , and then Ramsey theory both finite and infinite, which is where the abstract machinery finally pays for itself in explicit numbers.

Throughout, Polish space means a separable completely metrisable topological space; the two we care about are the real line $R$ and Baire space $N = ω^{ω}$ , the set of infinite sequences of natural numbers with the product topology. Baire space is the real workhorse: it is homeomorphic to the irrationals, every Polish space is a continuous image of it, and its points are exactly the plays of an infinite game. We write $c = 2^{ℵ_{0}}$ for the cardinality of the continuum, and we work in ZFC unless a result is explicitly labelled otherwise.

6.1The Borel hierarchy

The Borel sets are usually introduced by a sentence with a hidden existence claim in it: "the smallest $σ$ -algebra containing the open sets". A smallest one has to be shown to exist, and the argument that shows it is a template reused a dozen times in this chapter, so we give it in full rather than waving at it.

Definition 6.1 ( $σ$ -algebra). Let $X$ be a set. A family $A \subseteq P (X)$ is a $σ$ -algebra on $X$ if

$X \in A$ ;
$A \in A$ implies $X ∖ A \in A$ ;
$A_{0}, A_{1}, A_{2}, \dots \in A$ implies $⋃_{n \in ω} A_{n} \in A$ .

By De Morgan, a $σ$ -algebra is also closed under countable intersections, and contains $\emptyset$ .

Theorem 6.2 (The Borel sets are the smallest $σ$ -algebra on the opens). Let $X$ be a topological space and let $τ$ be its topology. There is a $σ$ -algebra $B (X)$ on $X$ with $τ \subseteq B (X)$ such that $B (X) \subseteq A$ for every $σ$ -algebra $A$ on $X$ with $τ \subseteq A$ . Its members are called the Borel sets of $X$ .

Proof. Let $Σ$ be the collection of all $σ$ -algebras on $X$ that contain $τ$ . It is not empty: the full power set $P (X)$ is such a $σ$ -algebra. So we may define

B (X) = ⋂ Σ = {A \subseteq X : A \in A for every A \in Σ},

an intersection of a nonempty family, hence a legitimate set by Separation applied inside $P (X)$ .

We check the three closure clauses. $X$ belongs to every $A \in Σ$ , so $X \in B (X)$ . If $A \in B (X)$ and $A \in Σ$ , then $A \in A$ , so $X ∖ A \in A$ ; as $A$ was arbitrary, $X ∖ A \in B (X)$ . If $A_{n} \in B (X)$ for all $n$ and $A \in Σ$ , then every $A_{n} \in A$ , so $⋃_{n} A_{n} \in A$ ; again as $A$ was arbitrary, $⋃_{n} A_{n} \in B (X)$ . Hence $B (X)$ is a $σ$ -algebra, and it contains $τ$ because every member of $Σ$ does.

Minimality is now immediate and is the whole point of intersecting: if $A$ is any $σ$ -algebra containing $τ$ then $A \in Σ$ , and an intersection is contained in each of the sets intersected, so $B (X) \subseteq A$ .∎

The argument used nothing about topology. The same three lines produce the subgroup generated by a subset, the ideal generated by a family, the $σ$ -ideal of null sets: whenever a closure property is preserved under arbitrary intersections and some family has it, a smallest one exists. What the argument does not give is any information about what the members of $B (X)$ look like — for that we must build them from below, and the building takes $ω_{1}$ steps.

Definition 6.3 (The Borel hierarchy). For a metrisable space $X$ define, by recursion on countable ordinals $α \geq 1$ ,

Σ_{1}^{0} = {open sets}, Π_{α}^{0} = {X ∖ A : A \in Σ_{α}^{0}},

Σ_{α}^{0} = {n \in ω ⋃ A_{n} : A_{n} \in Π_{α_{n}}^{0} for some α_{n} < α} (α > 1),

and $Δ_{α}^{0} = Σ_{α}^{0} \cap Π_{α}^{0}$ . Classically $Σ_{2}^{0} = F_{σ}$ and $Π_{2}^{0} = G_{δ}$ .

Intuition. Read the subscript as how many alternations of "countable union" and "complement" you need, starting from open. Level $1$ is open; level $2$ is a countable union of closed sets; level $3$ is a countable union of $G_{δ}$ sets; and so on. The boldface indicates that arbitrary real parameters are allowed — the lightface $Σ_{α}^{0}$ demands a computable description, which is the recursion-theoretic refinement we will not need.

Proposition 6.4 (The levels increase). For $1 \leq α < β < ω_{1}$ in a metrisable space,

Σ_{α}^{0} \cup Π_{α}^{0} \subseteq Δ_{β}^{0} .

Proof. It suffices to show $Σ_{α}^{0} \subseteq Σ_{β}^{0}$ and $Π_{α}^{0} \subseteq Σ_{β}^{0}$ , since taking complements then gives the same two inclusions into $Π_{β}^{0}$ , and the intersection of the two conclusions is $Δ_{β}^{0}$ .

For $A \in Π_{α}^{0}$ with $α < β$ , the constant sequence $A_{n} = A$ has all terms in $Π_{α}^{0}$ with $α < β$ , and $A = ⋃_{n} A_{n}$ , so $A \in Σ_{β}^{0}$ directly from the definition.

For $A \in Σ_{α}^{0}$ we need $A \in Π_{γ}^{0}$ for some $γ < β$ , and then the previous paragraph applies. If $α + 1 < β$ this is the metrisability step: in a metric space every open set is an $F_{σ}$ , because $U = ⋃_{n} {x : d (x, X ∖ U) \geq 1/ n}$ writes an open $U$ as a countable union of closed sets. That gives $Σ_{1}^{0} \subseteq Π_{2}^{0}$ , and by induction on $α$ the same countable-union manoeuvre gives $Σ_{α}^{0} \subseteq Π_{α + 1}^{0}$ . Since $α + 1 \leq β$ , we are done in every case.∎

The hierarchy therefore climbs. The next theorem says where it stops, and the argument is the one place where the uncountable cofinality of $ω_{1}$ does real work.

Theorem 6.5 (The Borel hierarchy closes at $ω_{1}$ ). In a metrisable space $X$ ,

B (X) = α < ω_{1} ⋃ Σ_{α}^{0} .

Proof. Write $H = ⋃_{α < ω_{1}} Σ_{α}^{0}$ . Every level consists of Borel sets — an induction on $α$ , since $Σ_{1}^{0} = τ \subseteq B (X)$ and each later level is built by complements and countable unions, which $B (X)$ admits. So $H \subseteq B (X)$ .

For the reverse inclusion it is enough, by the minimality in The Borel sets are the smallest $σ$ -algebra on the opens, to check that $H$ is itself a $σ$ -algebra containing the open sets. It contains them, at level $1$ . It is closed under complement: if $A \in Σ_{α}^{0}$ then $X ∖ A \in Π_{α}^{0} \subseteq Σ_{α + 1}^{0} \subseteq H$ , using The levels increase and $α + 1 < ω_{1}$ .

Closure under countable unions is the crux. Let $A_{n} \in H$ for $n \in ω$ , and choose $α_{n} < ω_{1}$ with $A_{n} \in Σ_{α_{n}}^{0}$ . Put

α = n \in ω sup (α_{n} + 1) .

This is a supremum of countably many countable ordinals, and $ω_{1}$ is regular — a countable subset of $ω_{1}$ is bounded in $ω_{1}$ , because a countable union of countable sets is countable, so $α < ω_{1}$ . Each $A_{n}$ lies in $Π_{α_{n} + 1}^{0}$ by The levels increase, with $α_{n} + 1 \leq α$ ; if $α_{n} + 1 < α$ for all $n$ the definition gives $⋃_{n} A_{n} \in Σ_{α}^{0}$ immediately, and otherwise $α = α_{m} + 1$ for some $m$ and we instead use level $α + 1$ , where all the $Π_{α_{n} + 1}^{0}$ with $α_{n} + 1 \leq α < α + 1$ are permitted. Either way the union lands in $H$ , and $α + 1 < ω_{1}$ .

Hence $H$ is a $σ$ -algebra containing $τ$ , so $B (X) \subseteq H$ .∎

Remark. The regularity of $ω_{1}$ is exactly what the proof consumed, and it is exactly what fails one level down: the hierarchy does not close at any $α < ω_{1}$ , because $α$ has countable cofinality or is countable, and a countable sequence of sets drawn from levels below $α$ can be assembled into something new. Making "something new" precise is the next theorem.

Theorem 6.6 (No earlier closure: the levels are strictly increasing). In an uncountable Polish space, for every $α < ω_{1}$ ,

Σ_{α}^{0} \neq = Π_{α}^{0}, hence Δ_{α}^{0} ⊊ Σ_{α}^{0} ⊊ Σ_{α + 1}^{0} .

In particular $B (X)$ has exactly $ω_{1}$ distinct levels.

Proof (Sketch — assumes the universal set construction). The full argument rests on one construction we do not carry out here: for each $α < ω_{1}$ there is a set $U \subseteq N \times X$ which is $Σ_{α}^{0}$ in the product and is universal for $Σ_{α}^{0}$ subsets of $X$ , meaning every $Σ_{α}^{0}$ set $A \subseteq X$ equals a section $U_{y} = {x : (y, x) \in U}$ . Universal sets are built by recursion on $α$ , coding a countable sequence of lower-level codes into a single real.

Granting that, the diagonal argument is three lines. Take $X = N$ and let $U$ be universal for $Σ_{α}^{0}$ . Put $D = {y \in N : (y, y) \in / U}$ . Then $D$ is $Π_{α}^{0}$ , since it is the complement of the continuous preimage ${y : (y, y) \in U}$ of $U$ under $y \mapsto (y, y)$ , and continuous preimages preserve each level. If $D$ were also $Σ_{α}^{0}$ then $D = U_{y_{0}}$ for some $y_{0}$ , and asking whether $y_{0} \in D$ gives $y_{0} \in D ⟺ (y_{0}, y_{0}) \in / U ⟺ y_{0} \in / U_{y_{0}} = D$ , a contradiction. So $Σ_{α}^{0} \neq = Π_{α}^{0}$ , and since each is closed under complements of the other, neither contains the other; the inclusions in The levels increase are therefore strict. Transfer to an arbitrary uncountable Polish space along a Borel isomorphism.∎

Figure 6.7. The Borel hierarchy:

Σ

above,

Π

below, meeting in the

Δ

levels between them. Every inclusion drawn is strict, and the tower runs through all

ω_{1}

countable ordinals without ever closing early.

Example 6.8 (Placing three familiar sets). Locate $Q$ , the irrationals, and the set of reals whose decimal expansion has infinitely many $7$ s in the hierarchy, as precisely as you can.

Solution.

$Q = ⋃_{q} {q}$ is a countable union of closed sets, so $Q \in Σ_{2}^{0}$ . It is not $Π_{2}^{0}$ : a dense $G_{δ}$ is comeagre, and $Q$ is meagre and dense, so if $Q$ were $G_{δ}$ then $Q$ and $R ∖ Q$ would be two disjoint comeagre sets, contradicting the Baire category theorem. So $Q$ sits exactly at level $2$ .
The irrationals are the complement, so exactly $Π_{2}^{0}$ : indeed $R ∖ Q = ⋂_{q} (R ∖ {q})$ is visibly $G_{δ}$ .
"Infinitely many $7$ s" means: for every $n$ there exists $m > n$ with the $m$ -th digit equal to $7$ . Fixing $n$ and $m$ , the digit condition is clopen up to the countable set of ambiguous expansions, so "there exists $m > n$ " is open and "for every $n$ " makes it a countable intersection of open sets: the set is $Π_{2}^{0}$ . The quantifier pattern $\forall n \exists m$ reads directly off as $⋂⋃$ , which is the practical way to place a set.

□

Pitfall. "Borel" is not "constructed in countably many steps" — it is "constructed in countably many steps at some countable ordinal stage". There are $c$ Borel sets, not countably many, and no single level contains them all. Confusing the number of steps at one level with the height of the tower is what makes people expect the hierarchy to close at $ω$ .

Exercises for §6.1 →

6.2Analytic and projective sets

Borel sets are closed under countable operations but not under projection, and projection is the operation that analysis performs constantly — "there exists a $y$ such that $(x, y)$ is nice" is a projection. Suslin's discovery in 1917 was that Lebesgue had asserted the contrary and that the projections form a genuinely larger class.

Definition 6.9 (Analytic set). A set $A \subseteq X$ in a Polish space is analytic, or $Σ_{1}^{1}$ , if $A = \emptyset$ or there is a continuous $f : N \to X$ with $A = f [N]$ . A set is co-analytic, or $Π_{1}^{1}$ , if its complement is analytic.

Theorem 6.10 (Four faces of analyticity). For $A \subseteq X$ nonempty, $X$ Polish, the following are equivalent.

$A$ is a continuous image of $N$ .
$A$ is the projection of a closed subset of $X \times N$ .
$A$ is the projection of a Borel subset of $X \times Y$ for some Polish $Y$ .
$A$ is a continuous image of a Borel set.

Proof. $(1) \Rightarrow (2)$ . Let $A = f [N]$ with $f$ continuous, and let $F = {(x, y) \in X \times N : f (y) = x}$ be the graph of $f$ with coordinates swapped. Since $f$ is continuous and $X$ is Hausdorff, $F$ is closed: if $(x_{n}, y_{n}) \to (x, y)$ with $f (y_{n}) = x_{n}$ , then $f (y) = lim f (y_{n}) = x$ . The projection of $F$ to $X$ is precisely the range of $f$ , namely $A$ .

$(2) \Rightarrow (3)$ is trivial, a closed set being Borel.

$(3) \Rightarrow (4)$ . If $B \subseteq X \times Y$ is Borel with $A = proj_{X} [B]$ , then $A$ is the image of the Borel set $B$ under the continuous projection map.

$(4) \Rightarrow (1)$ . Let $A = g [B]$ with $B \subseteq Y$ Borel and $g$ continuous. Two standard facts about Polish spaces finish it. First, every nonempty Borel subset $B$ of a Polish space is the continuous image of $N$ : one refines the topology of $Y$ to a Polish topology in which $B$ is clopen — this is possible because the family of sets that can be made clopen by such a refinement is a $σ$ -algebra containing the opens, so by The Borel sets are the smallest $σ$ -algebra on the opens it contains every Borel set — and then $B$ with the refined topology is a nonempty Polish space. Second, every nonempty Polish space is a continuous image of $N$ , by writing it as a continuously-indexed union of closed sets of diameter $\leq 2^{- n}$ and reading the index sequence as a point of $N$ . Composing, $A = g [B]$ is a continuous image of $N$ .∎

The equivalence is what makes analytic sets manageable: clause (2) says an analytic set is a set of $x$ for which a search through $N$ succeeds, and a search through $N$ is a search through a tree, which is a combinatorial object one can attack by induction.

Corollary 6.11 (Every Borel set is analytic). $B (X) \subseteq Σ_{1}^{1}$ , and likewise $B (X) \subseteq Π_{1}^{1}$ .

Proof. A nonempty Borel $B$ is the projection of the Borel set $B \times N$ , so it is analytic by clause (3) of Four faces of analyticity; the empty set is analytic by fiat. Since $B (X)$ is closed under complements, the complement of a Borel set is Borel, hence analytic, so every Borel set is co-analytic too.∎

Theorem 6.12 (Suslin: $Δ_{1}^{1} = B$ ). A subset of a Polish space is Borel if and only if it is both analytic and co-analytic.

Proof (Sketch — assumes the Lusin separation theorem). One direction is Every Borel set is analytic. For the other, the engine is Lusin separation: two disjoint analytic sets $A_{0}, A_{1}$ can be separated by a Borel set $C$ with $A_{0} \subseteq C$ and $C \cap A_{1} = \emptyset$ . Separation itself is proved by contradiction on trees — if no Borel set separates $A_{0}$ from $A_{1}$ , then no Borel set separates some pair of subtrees one node lower, and following that failure down the two trees produces a branch of each, i.e. points $x_{0} \in A_{0}$ and $x_{1} \in A_{1}$ with $x_{0} = x_{1}$ , contradicting disjointness. Granting separation: if $A$ and $X ∖ A$ are both analytic and disjoint, a separating Borel $C$ must satisfy $A \subseteq C$ and $C \cap (X ∖ A) = \emptyset$ , i.e. $C = A$ , so $A$ is Borel.∎

Definition 6.13 (The projective hierarchy). Set $Σ_{1}^{1}$ = analytic and $Π_{n}^{1}$ = complements of $Σ_{n}^{1}$ sets, and recursively

Σ_{n + 1}^{1} = {proj_{X} [P] : P \subseteq X \times N is Π_{n}^{1}}, Δ_{n}^{1} = Σ_{n}^{1} \cap Π_{n}^{1} .

The projective sets are $⋃_{n < ω} Σ_{n}^{1}$ . Equivalently, the projective sets are those definable in second-order arithmetic: $Σ_{n}^{1}$ means $n$ alternating quantifiers over reals in front of an arithmetic matrix, beginning with $\exists$ .

Intuition. Superscript $1$ counts quantifiers over reals; superscript $0$ counted quantifiers over integers. Each new real quantifier is a jump in strength far larger than anything inside the Borel hierarchy, which is why the projective hierarchy has only $ω$ levels but its levels are so much harder to control. $Σ_{1}^{1}$ is "there is a real such that…", $Π_{1}^{1}$ is "for every real…", $Σ_{2}^{1}$ is "there is a real such that for every real…".

Proposition 6.14 (Closure of the projective classes). Each $Σ_{n}^{1}$ is closed under countable unions, countable intersections, continuous preimages and continuous images; each $Π_{n}^{1}$ is closed under countable unions, countable intersections and continuous preimages. Consequently $Σ_{n}^{1} \cup Π_{n}^{1} \subseteq Δ_{n + 1}^{1}$ .

Proof. Take $n = 1$ ; the general case is the same computation with the matrix pushed down a level. If $A_{k} = proj [F_{k}]$ with $F_{k} \subseteq X \times N$ closed, then $⋃_{k} A_{k} = proj [F]$ where $F = {(x, k^{⌢} y) : (x, y) \in F_{k}}$ , which is closed because the first coordinate of the witness decides which $F_{k}$ to consult. For intersections, $⋂_{k} A_{k} = proj [G]$ where $G$ collects tuples $(x, ⟨ y_{k} ⟩_{k})$ with $(x, y_{k}) \in F_{k}$ for all $k$ , and $N^{ω} ≅ N$ ; $G$ is an intersection of closed sets, hence closed. Continuous preimages: $f^{- 1} [proj [F]] = proj [(f \times id)^{- 1} [F]]$ . Continuous images: the image of a continuous image of $N$ is a continuous image of $N$ .

For the last claim, let $A \in Σ_{n}^{1}$ . Then $A$ is the projection of $A \times N$ , and $A \times N \in Σ_{n}^{1}$ ; but to land in $Σ_{n + 1}^{1}$ we need a $Π_{n}^{1}$ set, so instead note $A \in Σ_{n}^{1}$ means $A = proj [P]$ with $P \in Π_{n - 1}^{1} \subseteq Π_{n}^{1}$ , giving $A \in Σ_{n + 1}^{1}$ . Similarly $Π_{n}^{1} \subseteq Σ_{n + 1}^{1}$ by padding with a dummy quantifier. Complementing both inclusions puts $Σ_{n}^{1} \cup Π_{n}^{1}$ inside $Π_{n + 1}^{1}$ as well, hence inside $Δ_{n + 1}^{1}$ .∎

Example 6.15 (Which class is " $x$ codes a well-order"?). Let $W O \subseteq 2^{ω \times ω}$ be the set of codes for linear orders of $ω$ that are well-orders. Place $W O$ in the hierarchy.

Solution.

"Codes a linear order" is an arithmetic condition: finitely many conditions on each triple of integers, so it is $Π_{1}^{0}$ and in particular Borel.
Well-foundedness says: there is no infinite descending sequence. An infinite descending sequence is an element of $N$ , so "there is one" is $Σ_{1}^{1}$ — it is the projection of the closed set of pairs (code, descending sequence).
$W O$ is the intersection of a Borel set with the complement of that $Σ_{1}^{1}$ set, hence $Π_{1}^{1}$ . It is in fact $Π_{1}^{1}$ -complete, and so not $Σ_{1}^{1}$ : if it were, it would be Borel by Suslin: $Δ_{1}^{1} = B$ , and a boundedness argument shows the ranks of well-orders coded by a Borel subset of $W O$ are bounded below $ω_{1}$ , while $W O$ realises every countable rank.
Conclusion: $W O$ is $Π_{1}^{1}$ and not $Σ_{1}^{1}$ — the canonical witness that the projective hierarchy does not collapse at the first level.

□

Example 6.16 (A $Σ_{2}^{1}$ set that is not obviously lower). Show that ${x \in N : x is constructible}$ , i.e. $N \cap L$ , is $Σ_{2}^{1}$ .

Solution.

The Shoenfield analysis shows " $x \in L$ " is equivalent to "there exists a real coding a countable well-founded model of a fragment of $V = L$ containing $x$ ".
"There exists a real" is one existential real quantifier. "Coding a well-founded model" is well-foundedness again, which is $Π_{1}^{1}$ as computed in the previous example.
So the whole statement has the shape $\exists y Π_{1}^{1}$ , which is exactly $Σ_{2}^{1}$ . This set is the reason the second projective level is where independence begins: under $V = L$ it is all of $N$ , and under large cardinals it is countable.

□

Exercises for §6.2 →

6.3Measure, category and the perfect set property

Three "regularity properties" recur. Each says a set is approximated by a simple set in a suitable sense, and each fails for a set built with the axiom of choice.

Definition 6.17 (The three regularity properties). Let $A$ be a subset of a Polish space $X$ carrying a $σ$ -finite Borel measure $μ$ .

$A$ is $μ$ -measurable if $A = B △ N$ for some Borel $B$ and some $μ$ -null $N$ .
$A$ has the Baire property if $A = U △ M$ for some open $U$ and some meagre $M$ .
$A$ has the perfect set property if $A$ is countable or contains a nonempty perfect set (a closed set with no isolated points).

Theorem 6.18 (Every Borel set is measurable and has the Baire property). In a Polish space, every Borel set is $μ$ -measurable for every $σ$ -finite Borel measure $μ$ , and every Borel set has the Baire property.

Proof. Both halves are the minimality argument of The Borel sets are the smallest $σ$ -algebra on the opens: it suffices to show the sets with the property in question form a $σ$ -algebra containing the open sets.

For measurability, let $M$ be the family of $μ$ -measurable sets. Every open set is Borel, hence in $M$ with $N = \emptyset$ . If $A = B △ N$ then $X ∖ A = (X ∖ B) △ N$ , so $M$ is closed under complement. If $A_{n} = B_{n} △ N_{n}$ then $⋃_{n} A_{n}$ differs from $⋃_{n} B_{n}$ only inside $⋃_{n} N_{n}$ , a countable union of null sets and hence null, so $M$ is closed under countable unions. Thus $M$ is a $σ$ -algebra containing the opens, so it contains every Borel set.

For the Baire property, let $B P$ be the family of sets with it. Open sets are in $B P$ trivially. Countable unions: if $A_{n} = U_{n} △ M_{n}$ then $⋃ A_{n} △ ⋃ U_{n} \subseteq ⋃ M_{n}$ , which is meagre since the meagre sets form a $σ$ -ideal. Complements need one extra step. If $A = U △ M$ , write $F = X ∖ U$ , a closed set; then $X ∖ A = F △ M$ . Now $F = int (F) \cup \partial F$ , and the boundary $\partial F$ of a closed set is closed with empty interior, hence nowhere dense. So $F △ int (F) \subseteq \partial F$ is meagre, and therefore $X ∖ A = int (F) △ M^{'}$ with $M^{'} \subseteq M \cup \partial F$ meagre, exhibiting the Baire property with the open set $int (F)$ .

Hence $B P$ is a $σ$ -algebra containing the opens, and contains the Borel sets.∎

Theorem 6.19 (Analytic sets are regular). Every $Σ_{1}^{1}$ set is Lebesgue measurable, has the Baire property, and has the perfect set property. The same holds for $Π_{1}^{1}$ sets for measure and category, but the perfect set property for $Π_{1}^{1}$ sets is not provable in ZFC.

Proof (Sketch — assumes the Suslin representation). Write an analytic $A$ as $A = ⋃_{y \in N} ⋂_{n} F_{y ↾ n}$ for a system of closed sets indexed by finite sequences (the Suslin operation applied to a closed system, which clause (2) of Four faces of analyticity provides). The key lemma, proved by a rank argument on the tree, is that the class of measurable sets — and separately the class of sets with the Baire property — is closed under the Suslin operation, not merely under countable unions. Since the $F_{s}$ are closed, hence regular, the conclusion follows. The perfect set property comes from the tree directly: if the tree of the Suslin representation has an uncountable set of branches, one extracts a Cantor scheme of incompatible nodes and reads off a perfect subset; if not, $A$ is countable.∎

Theorem 6.20 (The projective hierarchy escapes ZFC). ZFC does not decide whether every $Σ_{2}^{1}$ set is Lebesgue measurable. Specifically:

If $V = L$ then there is a $Δ_{2}^{1}$ set that is not Lebesgue measurable, does not have the Baire property, and there is an uncountable $Π_{1}^{1}$ set with no perfect subset.
If there is a measurable cardinal, every $Σ_{2}^{1}$ set is Lebesgue measurable and every uncountable $Σ_{2}^{1}$ set has a perfect subset.

Proof (Sketch — assumes condensation in $L$ and Solovay's measure analysis). For (1): under $V = L$ there is a $Σ_{2}^{1}$ well-ordering $<_{L}$ of the reals in order type $ω_{1}$ — this is Gödel's condensation lemma, which lets " $x$ appears in $L$ before $y$ " be certified by a countable model, giving the $Σ_{2}^{1}$ complexity computed in the example above. Running the classical transfinite construction of a Bernstein set along $<_{L}$ instead of along an arbitrary well-order keeps every stage definable, and the resulting set is $Δ_{2}^{1}$ and non-measurable, without the Baire property. The same well-order produces an uncountable $Π_{1}^{1}$ set meeting every perfect set in at most one point.

For (2): a measurable cardinal gives sharps, and $x^{#}$ existing for every real $x$ implies every $Σ_{2}^{1}$ set has a tree representation on a measurable cardinal; the resulting " $κ$ -Suslin" representation transfers the regularity argument of Analytic sets are regular one level up. The dividing line is sharp: the two statements are not merely both consistent but of different consistency strength, since "every $Σ_{2}^{1}$ set is Lebesgue measurable" already implies $ω_{1}$ is inaccessible in $L [x]$ for every real $x$ .∎

Example 6.21 (Why a non-measurable set cannot be described). Explain, using the results above, why the Vitali set cannot be Borel, and why no explicit formula can ever be given for it.

Solution.

The Vitali set $V$ picks one representative from each coset of $Q$ in $R$ . Its translates $V + q$ for $q \in Q \cap [0, 1]$ are disjoint and cover $[0, 1]$ while sitting inside $[- 1, 2]$ .
If $V$ were measurable with measure $0$ , countable additivity gives $λ ([0, 1]) = 0$ ; with measure $c > 0$ it gives $λ ([- 1, 2]) \geq \sum_{q} c = \infty$ . Both are absurd, so $V$ is not measurable.
By Every Borel set is measurable and has the Baire property, $V$ is not Borel; by Analytic sets are regular, $V$ is not analytic or co-analytic either.
"No explicit formula" is the honest reading of clause (2) of The projective hierarchy escapes ZFC: if there is a measurable cardinal, no $Σ_{2}^{1}$ formula defines a non-measurable set, and under stronger large cardinals no projective formula does. Any definition of a Vitali set therefore has to be as non-constructive as the choice that made it.

□

Exercises for §6.3 →

6.4Infinite games and determinacy

Everything in the previous section becomes a single hypothesis once it is phrased as a game. Two players alternate producing natural numbers forever; a set $A$ of infinite sequences decides who won; and the question is whether one of them can force a win.

Definition 6.22 (The game $G (A)$ and strategies). Let $A \subseteq N$ . In $G (A)$ , players $I$ and $II$ alternately choose natural numbers,

I : a_{0} a_{2} a_{4} \dots II : a_{1} a_{3} a_{5} \dots,

producing a run $a = ⟨ a_{0}, a_{1}, a_{2}, \dots ⟩ \in N$ . Player $I$ wins if $a \in A$ ; otherwise $II$ wins. A strategy for a player is a function from the finite sequences on which that player is to move into $ω$ ; it is winning if every run consistent with it is a win for that player. $A$ is determined if one of the two players has a winning strategy. $AD$ , the axiom of determinacy, asserts that every $A \subseteq N$ is determined.

Proposition 6.23 (The two players cannot both win). For no $A \subseteq N$ do both players have a winning strategy in $G (A)$ . Consequently "the winner" of a determined game is well defined, and a winning strategy is unique as a function on the positions it actually reaches: two winning strategies for the same player may differ off their own play, but the set of runs consistent with both is nonempty and every such run is a win.

Proof. Suppose $σ$ is winning for $I$ and $τ$ is winning for $II$ . Play them against each other: define the run $a$ by letting $a_{2 n} = σ (a ↾ 2 n)$ and $a_{2 n + 1} = τ (a ↾ (2 n + 1))$ , a definition by recursion on $n$ that always applies, so the run $a = σ * τ$ exists and is unique. It is consistent with $σ$ , so $a \in A$ because $σ$ wins; it is consistent with $τ$ , so $a \in / A$ because $τ$ wins. Contradiction.

For the uniqueness clause, if $σ$ and $σ^{'}$ are both winning for $I$ , then $σ$ played against any strategy $τ$ for $II$ gives a run in $A$ , and so does $σ^{'}$ ; the two agree on the empty position or not, but in either case the outcome is determined by the set $A$ and not by the strategy, which is the only sense in which a winning strategy can be unique, since a strategy's values at positions never reached are unconstrained.∎

Theorem 6.24 (Gale–Stewart: open games are determined). If $A \subseteq N$ is open, then $G (A)$ is determined. The same holds for closed $A$ .

Proof. Call a position $p$ (a finite sequence, with $II$ to move, say) losing for $II$ if $I$ has a winning strategy in the game continued from $p$ . Suppose $I$ has no winning strategy in $G (A)$ , i.e. the empty position is not losing for $II$ ; we produce a winning strategy for $II$ .

The key observation is: if a position $p$ with $I$ to move is not losing for $II$ , then for every move $a$ of $I$ there is a reply $b$ of $II$ such that $p^{⌢} a^{⌢} b$ is again not losing for $II$ . Otherwise $I$ could pick the move $a$ all of whose replies are losing for $II$ and combine the winning strategies from each $p^{⌢} a^{⌢} b$ into a winning strategy at $p$ , contradicting the assumption. Let $τ$ be the strategy for $II$ that always makes such a reply, using a fixed choice of least witness so that no choice principle is needed.

Now let $a$ be a run consistent with $τ$ , and suppose toward a contradiction that $a \in A$ . Since $A$ is open, membership is decided by a finite initial segment: there is $n$ with ${x : x ↾ n = a ↾ n} \subseteq A$ . But $a ↾ n$ is a position not losing for $II$ by construction, whereas from that position every continuation lies in $A$ , so $I$ wins from it with any strategy at all — that position is losing for $II$ . Contradiction, so $a \in / A$ and $τ$ is winning for $II$ .

The closed case is the same argument with the roles of the players exchanged, since $G (N ∖ A)$ for closed $A$ is the open game with $I$ and $II$ swapped.∎

Theorem 6.25 (Martin: Borel games are determined). Every Borel $A \subseteq N$ is determined.

Proof (Sketch — assumes Replacement up to $ℶ_{ω_{1}}$ , and is not provable without it). Martin's proof unravels a Borel game into a closed game on a larger alphabet, by attaching to each move extra information that certifies the eventual Borel verdict; the unravelling of a $Σ_{α}^{0}$ set is built by recursion on $α$ , and each step passes to a power set. Closed determinacy, which is Gale–Stewart: open games are determined, then applies to the unravelled game, and the covering maps push the winning strategy back down. The recursion is why this is the one theorem in the chapter that genuinely needs the full strength of ZFC's Replacement scheme: Friedman showed that Borel determinacy is not provable in Zermelo set theory, and that proving $Σ_{α}^{0}$ determinacy requires roughly $α$ iterations of the power set. Determinacy for $Σ_{1}^{1}$ sets, one level higher, is equivalent to the existence of sharps and so is a large-cardinal assumption outright.∎

Determinacy at the projective level and beyond is therefore an axiom, not a theorem, and if pushed all the way to every set it becomes inconsistent with choice. That incompatibility is short enough to prove outright, and it is the cleanest demonstration that $AD$ is a statement about definable sets in disguise.

Theorem 6.26 ( $AD$ contradicts $AC$ ). $ZF + AC$ proves that there is an undetermined game. Hence $ZF + AD ⊢ \neg AC$ .

Proof. Work in $ZFC$ . The set of strategies for either player is a set of functions from finite sequences of naturals to naturals, so there are exactly $c = 2^{ℵ_{0}}$ strategies in all. Fix a well-ordering $⟨ σ_{ξ} : ξ < c ⟩$ of the strategies for $I$ and $⟨ τ_{ξ} : ξ < c ⟩$ of the strategies for $II$ .

We build, by transfinite recursion of length $c$ , two disjoint sets ${x_{ξ}}$ and ${y_{ξ}}$ of runs, and set $A = {x_{ξ} : ξ < c}$ . At stage $ξ$ , suppose $x_{η}, y_{η}$ have been chosen for all $η < ξ$ ; fewer than $c$ runs have been chosen so far.

First defeat $σ_{ξ}$ . As $II$ varies over all of $ω^{ω}$ in her moves, the runs consistent with $σ_{ξ}$ form a set of size exactly $c$ — the map sending $II$ 's sequence of moves to the resulting run is injective. Since fewer than $c$ runs are already used, choose $y_{ξ}$ consistent with $σ_{ξ}$ and different from every previously chosen run. Then $y_{ξ}$ will end up outside $A$ , so $σ_{ξ}$ is not winning for $I$ .

Symmetrically, the runs consistent with $τ_{ξ}$ also number $c$ ; choose $x_{ξ}$ consistent with $τ_{ξ}$ and different from every run chosen so far, including $y_{ξ}$ . Then $x_{ξ} \in A$ , so $τ_{ξ}$ is not winning for $II$ .

The recursion never gets stuck, because at each stage at most $∣ ξ ∣ + 1 < c$ runs are forbidden out of $c$ available. Let $A = {x_{ξ} : ξ < c}$ . By construction $A$ contains no $y_{ξ}$ , since all the $x$ 's and $y$ 's were chosen distinct. Every strategy $σ_{ξ}$ for $I$ fails, because $y_{ξ}$ is a run consistent with it and $y_{ξ} \in / A$ ; every strategy $τ_{ξ}$ for $II$ fails, because $x_{ξ}$ is consistent with it and $x_{ξ} \in A$ . So $G (A)$ is undetermined.∎

Remark. The proof consumed choice twice — once to well-order the strategies, once to make $c$ successive selections — and it consumed nothing else. That is the moral: $AD$ is false for the same reason a non-measurable set exists, namely that a length- $c$ diagonalisation can defeat any family of $c$ requirements. Set theorists therefore assume $AD$ not in $V$ but in the inner model $L (R)$ , where no such well-ordering is available, and keep $AC$ in $V$ .

Definition 6.27 (The Banach–Mazur game). Let $A \subseteq N$ . In the Banach–Mazur game $G^{**} (A)$ , players alternately choose nonempty finite sequences

I : s_{0} s_{2} \dots II : s_{1} s_{3} \dots

with each extending the concatenation so far; the run is $x = s_{0}^{⌢} s_{1}^{⌢} s_{2}^{⌢} \dots \in N$ , and $I$ wins iff $x \in A$ .

Theorem 6.28 (Banach–Mazur: $II$ wins exactly when $A$ is meagre). $II$ has a winning strategy in $G^{**} (A)$ if and only if $A$ is meagre.

Proof. ( $\Leftarrow$ ) Suppose $A \subseteq ⋃_{n} D_{n}$ with each $D_{n}$ nowhere dense. Let $II$ , at her $n$ -th move, extend the current finite sequence $t$ to some $t^{⌢} s_{2 n + 1}$ whose basic open neighbourhood $N_{t^{⌢} s_{2 n + 1}}$ is disjoint from $D_{n}$ . This is possible precisely because $D_{n}$ is nowhere dense: the open set $N_{t}$ is not contained in the closure of $D_{n}$ , so some basic subneighbourhood misses $D_{n}$ . The resulting run $x$ lies in $N_{t^{⌢} s_{2 n + 1}}$ for every $n$ , hence avoids every $D_{n}$ , hence avoids $A$ . So $II$ wins.

( $\Rightarrow$ ) Let $τ$ be winning for $II$ . Call a position $p$ (ending with a move of $II$ ) $τ$ -reachable if it arises from some play consistent with $τ$ . For a $τ$ -reachable $p$ let

U_{p} = ⋃ {N_{q} : q is τ -reachable, q ⊋ p},

an open set. Claim: $U_{p}$ is dense below $N_{p}$ . Indeed given any finite extension $t \supseteq p$ , player $I$ may move so as to produce exactly $t$ , and $τ$ answers with some $q \supseteq t$ that is $τ$ -reachable, so $N_{q} \subseteq U_{p} \cap N_{t}$ is nonempty.

Now define $D_{n}$ to be the complement of $⋃ {U_{p} : p τ -reachable of length \geq n}$ intersected with the closure of the reachable region; each such union is open dense in the relevant neighbourhoods, so each $D_{n}$ is nowhere dense. If $x \in A$ , then $x$ cannot be consistent with $τ$ — $τ$ wins, so every consistent run is outside $A$ — which means at some stage $x$ leaves the $τ$ -reachable tree, i.e. $x$ fails to be in $U_{p}$ for the appropriate $p$ , putting $x$ in some $D_{n}$ . Hence $A \subseteq ⋃_{n} D_{n}$ is meagre.∎

Corollary 6.29 (Determinacy gives the Baire property). Let $Γ$ be a pointclass closed under continuous preimages and under intersection with open sets. If every game $G^{**} (A)$ with $A \in Γ$ is determined, then every $A \in Γ$ has the Baire property. In particular $AD$ implies every set of reals has the Baire property, and Borel determinacy re-proves the Borel case.

Proof. Let $A \in Γ$ and let $N_{s}$ be a basic open set. Apply Banach–Mazur: $II$ wins exactly when $A$ is meagre to the relativised game played inside $N_{s}$ , whose payoff set $A \cap N_{s}$ is again in $Γ$ . By determinacy either $II$ wins, in which case $A \cap N_{s}$ is meagre, or $I$ wins, in which case the same theorem applied to the complement (with the roles shifted by one move, which is a continuous reindexing) shows $N_{s} ∖ A$ is meagre, i.e. $A$ is comeagre in $N_{s}$ .

Let $U$ be the union of all basic $N_{s}$ in which $A$ is comeagre. Then $A ∖ U$ is meagre, because each basic neighbourhood outside $U$ has $A$ meagre in it and there are countably many of them; and $U ∖ A$ is meagre, being a countable union of the meagre sets $N_{s} ∖ A$ over the $N_{s}$ generating $U$ . So $A △ U$ is meagre and $A$ has the Baire property.∎

Example 6.30 (Reading a regularity property off a game). Use the Banach–Mazur characterisation to decide whether the set of $x \in N$ that take the value $0$ infinitely often is meagre or comeagre.

Solution.

Let $A = {x : x (n) = 0 for infinitely many n}$ . Play $G^{**} (A)$ and consider $I$ 's prospects.
$I$ has a trivial winning strategy: at every turn, append a single $0$ to whatever has been played. The resulting run has a $0$ at infinitely many positions — one for each of $I$ 's moves — so it lies in $A$ .
Since $I$ wins, $II$ does not, by The two players cannot both win, so $A$ is not meagre by the theorem. Running the same game with payoff $N ∖ A$ shows $I$ wins there too — append a single $1$ — which sounds paradoxical until one notices the two games have different payoff sets and both conclusions say only "not meagre".
To settle it: $A = ⋂_{n} ⋃_{m > n} {x : x (m) = 0}$ is a countable intersection of dense open sets, hence comeagre. The game confirms rather than replaces the direct computation — its value is that it works for sets far too complicated to compute with.

□

Exercises for §6.4 →

6.5Inner models and the constructible universe

An inner model is a transitive class $M$ containing all the ordinals with $M ⊨ ZF$ . Inner models are the tool for proving that something is consistent: if an inner model satisfies a statement, that statement cannot be refuted.

Definition 6.31 (The constructible hierarchy). Let $Def (X)$ be the set of subsets of $X$ definable over $(X, \in)$ with parameters from $X$ . Define

L_{0} = \emptyset, L_{α + 1} = Def (L_{α}), L_{λ} = α < λ ⋃ L_{α} (λ limit), L = α \in Ord ⋃ L_{α} .

The axiom $V = L$ asserts that every set is constructible.

Theorem 6.32 ( $L$ is the least inner model). $L$ is an inner model of $ZF$ , and $L \subseteq M$ for every inner model $M$ of $ZF$ .

Proof. We prove minimality, which is the part that is a genuine argument rather than a verification. Let $M$ be an inner model. We show $L_{α} \in M$ and $L_{α} \subseteq M$ by induction on $α$ .

$L_{0} = \emptyset \in M$ . At limits, $L_{λ} = ⋃_{α < λ} L_{α}$ ; the sequence $⟨ L_{α} : α < λ ⟩$ is definable, so $M$ can form it by Replacement inside $M$ — this is where $M ⊨ ZF$ is used — and take its union.

The successor step is the one that needs care. $L_{α + 1} = Def (L_{α})$ , and $Def$ is defined by a formula involving satisfaction for the structure $(L_{α}, \in)$ . Satisfaction for a set-sized structure is definable in $ZF$ by recursion on formulas, and its definition is absolute between transitive models containing the structure: if $L_{α} \in M$ and $M$ is transitive, then $M$ computes the same satisfaction relation as $V$ does, because the recursion quantifies only over finite sequences and subsets of the finite object "formula", all of which are in $M$ and computed correctly there. Hence $Def (L_{α})^{M} = Def (L_{α})$ , so $L_{α + 1} \in M$ .

Since $M$ contains all ordinals, the induction runs through every $α$ , giving $L = ⋃_{α} L_{α} \subseteq M$ .∎

Theorem 6.33 ( $V = L$ decides the continuum). If $V = L$ then $GCH$ holds; in particular $CH$ holds and $AC$ holds.

Proof (Sketch — assumes the condensation lemma). Condensation says: if $X ≺ L_{α}$ is an elementary submodel, then the transitive collapse of $X$ is $L_{β}$ for some $β \leq α$ — the point being that the definition of $L$ is so uniform that a collapsed elementary submodel of a level is again a level.

Given condensation, fix an infinite cardinal $κ$ and let $A \subseteq κ$ with $A \in L$ . Choose $α$ with $A \in L_{α}$ and take $X ≺ L_{α}$ with $κ \cup {A} \subseteq X$ and $∣ X ∣ = κ$ , by Löwenheim–Skolem. Collapsing $X$ fixes $κ$ and $A$ pointwise (they are already transitive enough) and yields $L_{β}$ with $∣ β ∣ = κ$ , so $A \in L_{β}$ with $β < κ^{+}$ . Thus $P (κ) \subseteq L_{κ^{+}}$ , and $∣ L_{κ^{+}} ∣ = κ^{+}$ , giving $2^{κ} \leq κ^{+}$ . Choice holds because the levels of $L$ carry a definable well-ordering, built by recursion from an enumeration of the formulas.∎

Example 6.34 (Why minimality matters). Explain why $L$ is the least inner model immediately yields the relative consistency of $CH$ .

Solution.

Suppose $ZFC + CH$ were inconsistent. Then $ZFC ⊢ \neg CH$ .
$ZF$ proves that $L$ is an inner model satisfying $ZFC$ and $V = L$ , so by $V = L$ decides the continuum, $L ⊨ CH$ .
Relativising the supposed proof of $\neg CH$ to $L$ gives $L ⊨ \neg CH$ , a contradiction inside $ZF$ . So $Con (ZF) \Rightarrow Con (ZFC + CH)$ .
Minimality adds the reason $L$ cannot be dispensed with: any consistency proof of this shape needs a model built inside the theory, and $L$ is the smallest such, so it is where the fewest extra sets can sneak in to spoil $CH$ .

□

Exercises for §6.5 →

6.6Core model theory

$L$ is too small: it has no measurable cardinal, since a measurable cardinal's ultrafilter can never be constructible. The core model $K$ is the answer to "what is the largest $L$ -like model compatible with the large cardinals that actually exist".

Definition 6.35 (Measurable cardinal). An uncountable cardinal $κ$ is measurable if there is a nonprincipal $κ$ -complete ultrafilter $U$ on $κ$ : a filter containing no singleton, deciding every subset of $κ$ , and closed under intersections of fewer than $κ$ of its members.

Theorem 6.36 (Measurable implies inaccessible). Every measurable cardinal $κ$ is regular and a strong limit, hence strongly inaccessible.

Proof. Regular. Suppose $κ = ⋃_{i < λ} A_{i}$ with $λ < κ$ and each $∣ A_{i} ∣ < κ$ . Each $A_{i}$ has size $< κ$ and is a union of $< κ$ singletons, and $U$ is $κ$ -complete and nonprincipal, so each singleton has complement in $U$ and hence $κ ∖ A_{i} \in U$ by $κ$ -completeness applied to fewer than $κ$ sets. Intersecting the $λ < κ$ sets $κ ∖ A_{i}$ , again by $κ$ -completeness, gives $κ ∖ ⋃_{i} A_{i} = \emptyset \in U$ , which is impossible for a filter. So $κ$ is regular.

Strong limit. Suppose $λ < κ \leq 2^{λ}$ , and fix an injection $ι : κ \to^{λ} 2$ . For each $ξ < λ$ exactly one of $A_{ξ}^{0} = {α : ι (α) (ξ) = 0}$ and $A_{ξ}^{1}$ lies in $U$ ; let $f (ξ)$ be the value $ϵ$ with $A_{ξ}^{ϵ} \in U$ . By $κ$ -completeness, $B = ⋂_{ξ < λ} A_{ξ}^{f (ξ)} \in U$ , so $B$ is nonempty and in fact has at least two elements (a one-element set is not in a nonprincipal ultrafilter, and $U$ contains no set of size $< κ$ by the same reasoning). But every $α \in B$ has $ι (α) = f$ , contradicting injectivity. Hence $2^{λ} < κ$ for all $λ < κ$ .∎

Theorem 6.37 (Ultrapowers: measurability as an embedding). $κ$ is measurable if and only if there is an elementary embedding $j : V \to M$ into a transitive class $M$ with $j ↾ κ = id$ and $j (κ) > κ$ ; $κ$ is then the critical point of $j$ .

Proof. ( $\Rightarrow$ ) Form the ultrapower $Ult (V, U)$ of $V$ by $U$ : its elements are (Scott's trick classes of) functions $f : κ \to V$ , with $[f] \in [g]$ iff ${α : f (α) \in g (α)} \in U$ . Łoś's theorem — proved by induction on formulas, using the ultrafilter property at the negation step and a choice of witnesses at the existential step — says $Ult (V, U) ⊨ φ ([f_{1}], \dots)$ iff ${α : φ (f_{1} (α), \dots)} \in U$ . Thus $j (x) = [c_{x}]$ , the class of the constant function, is elementary. $κ$ -completeness makes the membership relation well-founded, so the ultrapower has a transitive collapse $M$ . For $α < κ$ , an easy induction using $κ$ -completeness shows $j (α) = α$ ; and $[id] < j (κ)$ while $[id] \geq α$ for every $α < κ$ , so $j (κ) > κ$ .

( $\Leftarrow$ ) Given such a $j$ with critical point $κ$ , define $U = {A \subseteq κ : κ \in j (A)}$ . It is a filter because $j$ preserves intersections and inclusions; it is an ultrafilter because $j (κ ∖ A) = j (κ) ∖ j (A)$ and $κ \in j (κ)$ ; nonprincipal because $j ({α}) = {α}$ for $α < κ$ and $κ \neq = α$ ; and $κ$ -complete because for $⟨ A_{i} : i < λ ⟩$ with $λ < κ$ we have $j (⟨ A_{i} ⟩) = ⟨ j (A_{i})⟩$ coordinatewise, $j$ fixing $λ$ , so $κ \in ⋂_{i} j (A_{i}) = j (⋂_{i} A_{i})$ .∎

Example 6.38 (Counting the ultrapower's first move). Let $U$ be a normal measure on a measurable $κ$ and $j : V \to M$ the induced embedding. Compute $j (κ)$ 's relation to $κ^{+}$ and explain what $[id]$ is.

Solution.

By Ultrapowers: measurability as an embedding, $j$ has critical point $κ$ , so $j (κ) > κ$ .
$[id]$ , the class of the identity function $κ \to κ$ , satisfies $[c_{α}] < [id] < [c_{κ}]$ for every $α < κ$ , because ${ξ : α < ξ < κ} \in U$ ; so $[id]$ is an ordinal of $M$ strictly between $j (α) = α$ and $j (κ)$ . For a normal measure $[id] = κ$ exactly.
Since $M$ contains all $κ$ -sequences from $V$ when $U$ is normal, $M$ computes $κ^{+}$ correctly, and $j (κ) > κ^{+}$ follows from $M ⊨$ " $j (κ)$ is inaccessible" together with Measurable implies inaccessible applied inside $M$ .
So the single ultrapower already moves $κ$ past $κ^{+}$ — which is why a measurable cardinal is so much stronger than an inaccessible one, whose existence moves nothing.

□

Theorem 6.39 (The core model). Assume there is no inner model with a measurable cardinal. Then there is a definable inner model $K$ — the Dodd–Jensen core model — such that $K ⊨ ZFC + GCH$ , $K$ is contained in every inner model of the relevant kind, $K$ is rigid (it admits no nontrivial elementary self-embedding), and $K$ is generically absolute: forcing does not change $K$ .

Proof (Sketch — assumes fine structure and comparison of mice). $K$ is assembled from mice: small iterable structures $L [E]$ with a coherent sequence of extenders, each of which is well behaved enough to compare with every other by iterating away disagreements. The comparison lemma — two mice can be iterated until one is an initial segment of the other — is what makes the union of all mice a linearly ordered hierarchy and hence a model, and it is proved by the fine-structural analysis of the levels. Rigidity follows because a nontrivial self-embedding would have a critical point, from which the ultrapower construction of Ultrapowers: measurability as an embedding would manufacture a measurable inside $K$ , contradicting the hypothesis. Generic absoluteness holds because the definition of $K$ quantifies only over countable mice, which forcing cannot create or destroy under the anti-large-cardinal hypothesis.∎

Remark. The hypothesis "no inner model with a measurable" is not a limitation but the point. Core model theory is a dichotomy machine: either $K$ exists and is very $L$ -like, so combinatorics behaves rigidly, or the hypothesis fails and a large cardinal is present in an inner model. Every modern consistency-strength lower bound has this shape.

Exercises for §6.6 →

6.7Covering lemmas

If $V$ has no large cardinals then $V$ is not far from $L$ — "not far" made precise by covering.

Theorem 6.40 (Jensen's covering lemma). If $0^{#}$ does not exist, then for every uncountable set $X$ of ordinals there is a set $Y \in L$ with $X \subseteq Y$ and $∣ Y ∣ = ∣ X ∣$ .

Proof (Sketch — assumes the fine structure of $L$ ). Assume the conclusion fails for some $X$ of least possible cardinality. One builds an elementary chain of hulls inside levels of $L$ covering $X$ , and the failure forces the hulls to be non-trivially indiscernible, which is precisely the data of $0^{#}$ : a class of ordinals indiscernible for all the $L_{α}$ , equivalently a well-founded remarkable "sharp" for $L$ . So failure of covering yields $0^{#}$ , and the theorem is the contrapositive.∎

Theorem 6.41 (Covering transfers singularity down to $L$ ). Assume $0^{#}$ does not exist. If $κ$ is a singular cardinal of $V$ with $κ > ω_{1}$ , then $κ$ is a singular cardinal of $L$ , and $(κ^{+})^{L} = κ^{+}$ .

Proof. Let $cf (κ) = λ < κ$ and let $X \subseteq κ$ be cofinal with $∣ X ∣ = λ$ ; enlarging $X$ if necessary, assume $X$ uncountable. By Jensen's covering lemma there is $Y \in L$ with $X \subseteq Y \subseteq Ord$ and $∣ Y ∣ = ∣ X ∣ = λ$ . Replacing $Y$ by $Y \cap κ$ , still in $L$ , we get a set in $L$ of size $\leq λ$ cofinal in $κ$ (it contains the cofinal $X$ ). Computing cofinality inside $L$ : $L$ sees a cofinal subset of $κ$ of $L$ -cardinality at most $λ^{+}$ at worst, and since $λ < κ$ , $κ$ is not regular in $L$ . Also $κ$ remains a cardinal in $L$ — cardinals of $V$ are cardinals of $L$ , as $L \subseteq V$ means any $L$ -bijection is a $V$ -bijection. So $κ$ is a singular cardinal of $L$ .

For the successor claim, suppose $(κ^{+})^{L} < κ^{+}$ . Then in $V$ there is a surjection $g : κ \to (κ^{+})^{L}$ . Consider $X \subseteq (κ^{+})^{L}$ of size $κ$ cofinal in it; covering gives $Y \in L$ of size $κ$ with $X \subseteq Y$ , and inside $L$ a set of size $κ$ cannot be cofinal in the $L$ -cardinal $(κ^{+})^{L}$ , which $L$ believes is regular. Contradiction, so $(κ^{+})^{L} = κ^{+}$ .∎

Corollary 6.42 (The singular cardinals hypothesis from covering). If $0^{#}$ does not exist then $SCH$ holds: for every singular $κ$ with $2^{cf (κ)} < κ$ we have $κ^{cf (κ)} = κ^{+}$ .

Proof. Let $λ = cf (κ)$ . Every function $f : λ \to κ$ has range of size $\leq λ$ , so by Jensen's covering lemma there is $Y_{f} \in L$ of size $λ^{+} \leq κ$ covering that range, and inside $L$ the set of subsets of $Y_{f}$ of size $λ$ numbers at most $(λ^{+})^{L}$ -many by $GCH$ in $L$ . Counting: the number of such covering sets $Y$ available in $L$ is at most $(κ^{+})^{L} = κ^{+}$ by Covering transfers singularity down to $L$ , and each contributes at most $∣ [Y]^{λ} ∣^{L} \leq λ^{++} \leq κ$ functions. Hence $κ^{λ} \leq κ^{+} \cdot κ = κ^{+}$ , and $κ^{λ} \geq κ^{+}$ always holds by König's theorem.∎

Example 6.43 (What must be true if $ℵ_{ω}$ misbehaves). Suppose $2^{ℵ_{n}} = ℵ_{n + 1}$ for all $n < ω$ but $2^{ℵ_{ω}} = ℵ_{ω_{2}}$ . What does the theory above force?

Solution.

$κ = ℵ_{ω}$ is singular with $cf (κ) = ω$ and $2^{ℵ_{0}} = ℵ_{1} < κ$ , so $SCH$ at $κ$ would give $κ^{ω} = κ^{+} = ℵ_{ω + 1}$ , and then $2^{ℵ_{ω}} = ℵ_{ω + 1}$ .
The hypothesis $2^{ℵ_{ω}} = ℵ_{ω_{2}}$ contradicts that, so $SCH$ fails at $ℵ_{ω}$ .
By The singular cardinals hypothesis from covering, $0^{#}$ must exist.
Hence such a model cannot be built from $ZFC$ alone: a failure of $SCH$ costs at least a measurable cardinal, and in fact Gitik's theorem pins the exact strength at a measurable of Mitchell order $κ^{++}$ . This is the standard illustration of core model theory turning a cardinal-arithmetic statement into a large-cardinal one.

□

Exercises for §6.7 →

6.8Applications of the descriptive machinery

The classical payoff is that theorems of analysis and topology which look like they need choice turn out to hold outright for definable sets, and the pathologies all live at the same place.

Theorem 6.44 (Cantor–Bendixson). Every closed subset $F$ of a Polish space is the union of a perfect set $P$ and a countable set $C$ , with $P \cap C = \emptyset$ . Consequently every uncountable closed set has cardinality $c$ , and $CH$ holds for closed sets.

Proof. Call $x \in F$ a condensation point of $F$ if every neighbourhood of $x$ meets $F$ in uncountably many points. Let $P$ be the set of condensation points of $F$ and $C = F ∖ P$ .

$C$ is countable: fix a countable base ${B_{n}}$ ; each $x \in C$ has a basic neighbourhood $B_{n (x)}$ with $B_{n (x)} \cap F$ countable, and $C \subseteq ⋃ {B_{n} \cap F : B_{n} \cap F countable}$ , a countable union of countable sets.

$P$ is closed: if $x \in / P$ then some neighbourhood meets $F$ countably, and every point of that neighbourhood inherits the same witness, so the complement of $P$ is open. $P \subseteq F$ since $F$ is closed and condensation points are limits of points of $F$ .

$P$ has no isolated points: if $x \in P$ were isolated in $P$ , take a neighbourhood $B$ with $B \cap P = {x}$ ; then $B \cap F \subseteq {x} \cup C$ is countable, contradicting $x \in P$ .

So $P$ is perfect. If $F$ is uncountable then $P \neq = \emptyset$ , and a nonempty perfect set in a Polish space contains a copy of the Cantor set — build a binary tree of nested closed balls with shrinking diameters, splitting at each level because no point is isolated — hence $∣ F ∣ \geq ∣ P ∣ = c$ , while $∣ F ∣ \leq c$ always.∎

Theorem 6.45 (Bernstein sets exist). There is a set $B \subseteq R$ such that both $B$ and $R ∖ B$ meet every uncountable closed set. Such a $B$ is neither Lebesgue measurable nor has the Baire property, and has no perfect subset.

Proof. There are exactly $c$ closed subsets of $R$ , since each is determined by which of the countably many basic intervals it meets — more carefully, by a code in $N$ . Enumerate the uncountable ones as $⟨ F_{ξ} : ξ < c ⟩$ . By Cantor–Bendixson, $∣ F_{ξ} ∣ = c$ for each $ξ$ . Recursively choose distinct points $b_{ξ}, c_{ξ} \in F_{ξ}$ avoiding all previously chosen points; possible since fewer than $c$ points are excluded from a set of size $c$ . Put $B = {b_{ξ} : ξ < c}$ ; then $c_{ξ} \in / B$ , so $B$ meets and misses every $F_{ξ}$ .

$B$ has no perfect subset, since a perfect subset would be an uncountable closed $F_{ξ} \subseteq B$ , but $c_{ξ} \in F_{ξ} ∖ B$ . If $B$ were measurable with positive measure it would contain a closed set of positive measure, hence an uncountable closed set — excluded; and the same applies to $R ∖ B$ , so both would be null, contradicting $λ (R) > 0$ . If $B$ had the Baire property it would be comeagre in some interval or meagre; comeagre in an interval forces a dense $G_{δ}$ inside, which contains an uncountable closed set — excluded — and if both $B$ and its complement were meagre, $R$ would be meagre, contradicting the Baire category theorem.∎

Corollary 6.46 (The perfect set property fails in ZFC). $ZFC$ proves that some set of reals fails the perfect set property, hence $AD$ fails; but no Borel or analytic set is such a counterexample.

Proof. Bernstein sets exist supplies the counterexample. It is not Borel or analytic by Analytic sets are regular, so the counterexample necessarily lies outside the definable world. Combined with $AD$ contradicts $AC$ , this is a second, independent route to the incompatibility: $AD$ implies every set has the perfect set property, which a Bernstein set refutes.∎

Example 6.47 (Where the Bernstein construction breaks under determinacy). Identify the single step of the Bernstein construction that $AD$ forbids.

Solution.

The construction enumerated the uncountable closed sets in order type $c$ — a well-ordering of a set of size $c$ .
Under $AD$ (in $L (R)$ , say) there is no well-ordering of the reals; indeed $c$ is not even an aleph, and $ω_{1}$ does not inject into $R$ .
Every other step — using $∣ F_{ξ} ∣ = c$ , choosing two fresh points — is harmless; it is only the length- $c$ recursion that needs choice.
This is exactly the step that powered $AD$ contradicts $AC$ . One diagonalisation of length $c$ underlies every classical pathology: Vitali, Bernstein, undetermined games, and non-principal ultrafilters on $ω$ .

□

Exercises for §6.8 →

6.9Martin's axiom

Forcing adds a generic filter meeting every dense set of the ground model. Martin's axiom says that for well-behaved posets you may have such a filter without leaving the universe, provided you ask it to meet fewer than $c$ dense sets.

Definition 6.48 (Posets, dense sets, filters, $MA (κ)$ ). Let $(P, \leq)$ be a partial order. $p, q$ are compatible if some $r$ satisfies $r \leq p$ and $r \leq q$ ; an antichain is a set of pairwise incompatible conditions; $P$ is ccc if every antichain is countable. $D \subseteq P$ is dense if every $p$ has an extension in $D$ . $G \subseteq P$ is a filter if it is upward closed and any two of its members have a common extension in $G$ .

$MA (κ)$ : for every ccc poset $P$ and every family $D$ of at most $κ$ dense subsets, there is a filter $G$ with $G \cap D \neq = \emptyset$ for all $D \in D$ . Martin's axiom $MA$ is: $MA (κ)$ for all $κ < c$ .

Theorem 6.49 ( $MA (ℵ_{0})$ is a theorem of ZFC). $MA (ℵ_{0})$ holds outright, for every poset, ccc or not. (This is the Rasiowa–Sikorski lemma.)

Proof. Let $P$ be any poset and $D_{0}, D_{1}, D_{2}, \dots$ countably many dense subsets. Pick any $p_{0} \in P$ . Recursively, given $p_{n}$ , use density of $D_{n}$ to choose $p_{n + 1} \leq p_{n}$ with $p_{n + 1} \in D_{n}$ . This is a countable sequence of choices, so it needs only dependent choice, available in $ZFC$ .

Let $G = {q \in P : q \geq p_{n} for some n}$ . It is upward closed by construction. Any two members $q \geq p_{m}$ , $q^{'} \geq p_{n}$ with $m \leq n$ have $p_{n}$ as a common extension, and $p_{n} \in G$ , so $G$ is a filter. And $p_{n + 1} \in G \cap D_{n}$ for every $n$ , so $G$ meets each $D_{n}$ .∎

Corollary 6.50 ( $CH$ implies $MA$ ). If $c = ℵ_{1}$ then $MA$ holds.

Proof. $MA$ asks for $MA (κ)$ only for $κ < c$ . Under $CH$ the only such infinite $κ$ is $ℵ_{0}$ , and the finite cases follow from it. So $MA$ reduces to $MA (ℵ_{0})$ is a theorem of ZFC.∎

The corollary explains the axiom's real content: $MA$ alone is a theorem-of- $ZFC$ -plus- $CH$ , so it is only interesting together with $\neg CH$ , where it says the continuum is "generic all the way up".

Theorem 6.51 ( $MA$ fails at $c$ ). $MA (c)$ is false. Hence $MA$ is the strongest statement of its form.

Proof. Let $P = Fn (ω, 2)$ be the set of finite partial functions $p : ω ⇀ 2$ , ordered by reverse inclusion. It is ccc — in fact countable. For $n \in ω$ let $D_{n} = {p : n \in dom (p)}$ , dense. For $f \in 2^{ω}$ let

E_{f} = {p \in P : \exists n \in dom (p), p (n) \neq = f (n)},

which is dense: given $q$ , pick $n \in / dom (q)$ and extend $q$ by $n \mapsto 1 - f (n)$ .

The family ${D_{n} : n < ω} \cup {E_{f} : f \in 2^{ω}}$ has size $c$ . A filter meeting all $D_{n}$ has union a total function $g \in 2^{ω}$ ; meeting $E_{g}$ would require some $p \in G$ and $n$ with $p (n) \neq = g (n)$ , impossible since $g \supseteq p$ . So no filter meets all $c$ of them.∎

Lemma 6.52 ( $MA (κ)$ computes $2^{κ}$ ). Assume $MA (κ)$ with $κ < c$ . Then $2^{κ} = c$ .

Proof. Since $κ < c$ we have $c = 2^{ℵ_{0}} \leq 2^{κ}$ , so only $2^{κ} \leq c$ needs proof, and for that it suffices to inject $P (κ)$ into $P (ω)$ .

Fix an almost disjoint family ${A_{α} : α < κ}$ of infinite subsets of $ω$ — pairwise intersections finite. Such a family of size $c$ exists in $ZFC$ (take the branches of the binary tree $2^{< ω}$ ), so one of size $κ$ certainly does. Given $X \subseteq κ$ , let $P_{X}$ consist of pairs $(s, F)$ with $s \subseteq ω$ finite and $F \subseteq X$ finite, ordered by $(t, E) \leq (s, F)$ iff $t \supseteq s$ , $E \supseteq F$ , and $(t ∖ s) \cap A_{α} = \emptyset$ for all $α \in F$ .

$P_{X}$ is ccc: conditions sharing a first coordinate are compatible, and there are countably many possible first coordinates, so every uncountable set of conditions contains two with the same $s$ .

Consider the dense sets $D_{α} = {(s, F) : α \in F}$ for $α \in X$ , and, for $β \in κ ∖ X$ and $n \in ω$ , $E_{β, n} = {(s, F) : ∣ s \cap A_{β} ∣ \geq n}$ . Density of $E_{β, n}$ holds because $A_{β}$ is infinite while $⋃_{α \in F} A_{α}$ meets it in a finite set, so fresh elements of $A_{β}$ are always available to add to $s$ . That is at most $κ$ dense sets, so $MA (κ)$ gives a filter $G$ ; let $d = ⋃ {s : (s, F) \in G}$ .

Then $d \cap A_{α}$ is finite for $α \in X$ (once $α$ enters $F$ , nothing further from $A_{α}$ may be added) and $d \cap A_{β}$ is infinite for $β \in / X$ (by the $E_{β, n}$ ). So $X$ is recovered from $d$ by $X = {α : d \cap A_{α} is finite}$ , and $X \mapsto d$ is injective into $P (ω)$ .∎

Theorem 6.53 ( $MA$ implies $c$ is regular). $MA$ implies $cf (c) = c$ , i.e. $2^{ℵ_{0}}$ is a regular cardinal.

Proof. Suppose $λ = cf (c) < c$ . By König's theorem, $c^{cf (c)} > c$ , that is $c^{λ} > c$ .

On the other hand $λ < c$ , so $MA (λ)$ holds, and $MA (κ)$ computes $2^{κ}$ gives $2^{λ} = c$ . Therefore

c^{λ} = (2^{ℵ_{0}})^{λ} = 2^{ℵ_{0} \cdot λ} = 2^{λ} = c,

contradicting $c^{λ} > c$ . Hence $cf (c) = c$ .∎

Example 6.54 (Using $MA$ to build an almost disjoint family). Let $A$ be a family of infinite subsets of $ω$ , pairwise with finite intersection, of size $κ < c$ , and let $A$ be maximal among such. Show $MA$ makes this impossible, i.e. every maximal almost disjoint family has size $c$ .

Solution.

Let $A = {A_{i} : i < κ}$ be almost disjoint with $κ < c$ . Force with $P$ = pairs $(s, F)$ with $s \subseteq ω$ finite and $F \subseteq A$ finite, ordered by $(t, E) \leq (s, F)$ iff $t \supseteq s$ , $E \supseteq F$ and $(t ∖ s) \cap ⋃ F = \emptyset$ .
$P$ is ccc: two conditions with the same first coordinate $s$ are compatible, and there are only countably many finite $s$ , so any uncountable set of conditions contains two that are compatible.
The sets $D_{n} = {(s, F) : ∣ s ∣ \geq n}$ and $E_{i} = {(s, F) : A_{i} \in F}$ are dense — the first because one may add a large finite set avoiding $⋃ F$ , which is possible since $⋃ F$ is a finite union of members of $A$ and no such union is cofinite when $A$ is infinite almost disjoint. There are $κ + ℵ_{0} < c$ of them.
$MA$ gives a filter $G$ meeting all; put $B = ⋃ {s : (s, F) \in G}$ . Then $B$ is infinite by the $D_{n}$ , and $B \cap A_{i}$ is finite for each $i$ by $E_{i}$ . So $A \cup {B}$ is still almost disjoint, contradicting maximality. Hence $a = c$ under $MA$ .

□

Exercises for §6.9 →

6.10The proper forcing axiom

Ccc is a strong restriction: it rules out every forcing that collapses a cardinal, but also many harmless ones. Properness is the weakest useful relaxation that still preserves $ω_{1}$ .

Definition 6.55 (Proper forcing and $PFA$ ). Let $P$ be a poset and $θ$ large. $P$ is proper if for every countable elementary submodel $M ≺ H_{θ}$ with $P \in M$ and every $p \in P \cap M$ there is $q \leq p$ that is $(M, P)$ -generic: every maximal antichain of $P$ lying in $M$ is predense below $q$ .

$PFA$ : for every proper $P$ and every family of at most $ℵ_{1}$ dense subsets there is a filter meeting them all.

Theorem 6.56 (Proper generalises ccc and $σ$ -closed). Every ccc poset is proper, and every $σ$ -closed poset is proper. Consequently $PFA$ implies $MA (ℵ_{1})$ .

Proof. Ccc. Let $M ≺ H_{θ}$ be countable with $P \in M$ , and let $p \in P \cap M$ ; we claim every $q \leq p$ is $(M, P)$ -generic. Let $A \in M$ be a maximal antichain. By ccc, $A$ is countable, and $M ⊨$ " $A$ is countable", so $M$ contains a surjection $ω \to A$ and hence $A \subseteq M$ . Any $r \leq q$ is compatible with some $a \in A$ by maximality, and $a \in M$ , so $A$ is predense below $q$ .

$σ$ -closed. Enumerate the dense sets of $P$ lying in $M$ as $D_{0}, D_{1}, \dots$ — countably many, since $M$ is countable — and build a descending chain $p \geq p_{0} \geq p_{1} \geq \dots$ with $p_{n} \in D_{n} \cap M$ , possible because $D_{n} \cap M$ is dense below any condition in $M$ by elementarity. $σ$ -closure provides a lower bound $q$ , which is $(M, P)$ -generic.

Consequence. If $P$ is ccc it is proper, and $PFA$ applied to it gives filters meeting $ℵ_{1}$ dense sets, which is $MA (ℵ_{1})$ .∎

Theorem 6.57 (Consequences of $PFA$ ). $PFA$ implies $c = ℵ_{2}$ , the singular cardinals hypothesis, the failure of $□_{κ}$ for every uncountable $κ$ , and that every two $ℵ_{1}$ -dense sets of reals are order isomorphic.

Proof (Sketch — assumes the consistency of a supercompact cardinal and Todorcevic's reflection analysis). $PFA$ is obtained by iterating proper forcings with countable support for the length of a supercompact cardinal $κ$ , using the Laver function to anticipate every proper forcing; the iteration collapses $κ$ to $ω_{2}$ , which is why $c = ℵ_{2}$ comes out. The combinatorial consequences run through the Mapping Reflection Principle and through Todorcevic's result that $PFA$ implies every stationary set reflects, which is incompatible with a $□_{κ}$ sequence; failure of $□$ at every singular in turn yields $SCH$ by Solovay's theorem. Unlike $MA$ , none of this is available from $ZFC$ alone: $PFA$ has large-cardinal consistency strength, at least many Woodin cardinals.∎

Example 6.58 (Why $PFA$ cannot allow all posets). Show that the axiom obtained by dropping "proper" and allowing arbitrary posets, with $ℵ_{1}$ dense sets, is inconsistent.

Solution.

Let $P = Fn (ω, ω_{1})$ , the finite partial functions from $ω$ to $ω_{1}$ , ordered by reverse inclusion. This poset collapses $ω_{1}$ .
The sets $D_{n} = {p : n \in dom (p)}$ and $R_{α} = {p : α \in ran (p)}$ for $α < ω_{1}$ are dense, and there are $ℵ_{1}$ of them.
A filter meeting all of them yields a surjection $ω \to ω_{1}$ , contradicting the regularity of $ω_{1}$ .
So any forcing axiom must restrict the class of posets, and the restriction must at minimum preserve $ω_{1}$ . Properness is precisely a sufficient condition for that: a proper poset adds no new countable sets of ordinals cofinally, hence preserves stationary subsets of $ω_{1}$ .

□

Exercises for §6.10 →

6.11Consequences of $MA + \neg CH$

Under $MA + \neg CH$ the cardinals below $c$ behave as though they were countable. The following theorem is the engine for almost every application.

Theorem 6.59 (Small sets are null and meagre). Assume $MA + \neg CH$ . Then the union of fewer than $c$ meagre sets is meagre, and the union of fewer than $c$ Lebesgue null sets is null. In particular every $X \subseteq R$ with $∣ X ∣ < c$ is both meagre and null.

Proof. Category. Let $κ < c$ and let $M_{i}$ , $i < κ$ , be meagre; replacing each by a larger set, assume $M_{i} = ⋃_{n} F_{n}^{i}$ with $F_{n}^{i}$ closed nowhere dense and increasing in $n$ . Use the Cohen poset $P = Fn (ω, 2)$ , which is countable, hence ccc. Regard a filter as producing a real $x \in 2^{ω}$ . For each $i$ , the set

D_{i} = {p \in P : [p] \cap F_{∣ p ∣}^{i} = \emptyset}

is dense, where $[p]$ is the basic clopen set determined by $p$ : given $q$ , since $F_{n}^{i}$ is nowhere dense, some extension $p \leq q$ has $[p]$ disjoint from it. Together with the $κ < c$ sets $D_{i}$ and the $ℵ_{0}$ sets $D_{n} = {p : n \in dom p}$ , $MA$ gives a filter producing a real $x \in / ⋃_{i} M_{i}$ . Since this works below any basic clopen set — relativise $P$ to conditions extending a fixed $s$ — the union $⋃_{i} M_{i}$ is not comeagre in any interval, and being a union of meagre sets it has the Baire property; a set with the Baire property that is non-comeagre in every interval is meagre.

Measure. Replace the Cohen poset by the amoeba poset $A$ : conditions are open sets $U \subseteq 2^{ω}$ of measure $< 1/2$ , ordered by inclusion. $A$ is ccc, because an uncountable antichain would give uncountably many pairwise "incompatible" open sets, whereas any two open sets of measure $< 1/4$ have union of measure $< 1/2$ and so are compatible, and every condition is refined by one of measure $< 1/4$ after shrinking. Given null sets $N_{i}$ , $i < κ < c$ , the sets $D_{i} = {U : N_{i} \subseteq U}$ are dense (cover $N_{i}$ by an open set of tiny measure and add it), as are $E_{r} = {U : λ (U) > r}$ for rational $r < 1/2$ . A filter meeting all of them yields an open set $W = ⋃ G$ of measure $\leq 1/2$ containing every $N_{i}$ ; iterating this with $1/2$ replaced by $2^{- k}$ and intersecting gives a null $G_{δ}$ containing $⋃_{i} N_{i}$ , which is therefore null.

The final claim follows since a set of size $< c$ is a union of $< c$ singletons, and singletons are null and meagre.∎

Corollary 6.60 (No small non-measurable set). Under $MA + \neg CH$ , every set of reals of size $ℵ_{1}$ is Lebesgue measurable with measure zero, and $2^{ℵ_{0}} = 2^{ℵ_{1}}$ .

Proof. The first part is Small sets are null and meagre with $ℵ_{1} < c$ . For the second, every $X \subseteq ω_{1}$ gives a set of reals of size $\leq ℵ_{1}$ , which is null, and a null set's subsets are all null hence measurable; counting the null $G_{δ}$ hulls shows the subsets of a fixed set of size $ℵ_{1}$ inject into the reals modulo null sets, giving $2^{ℵ_{1}} \leq c$ , and $\leq$ in the other direction is trivial.∎

Example 6.61 (Suslin's hypothesis under $MA + \neg CH$ ). Sketch why $MA + \neg CH$ kills Suslin lines.

Solution.

A Suslin line yields a Suslin tree: a tree of height $ω_{1}$ with no uncountable chain and no uncountable antichain.
A Suslin tree, ordered by reverse extension, is a ccc poset — an antichain in the forcing sense is an antichain in the tree sense.
For $α < ω_{1}$ let $D_{α}$ be the set of nodes of height $\geq α$ ; each is dense because the tree has height $ω_{1}$ and no maximal nodes below level $ω_{1}$ .
$MA (ℵ_{1})$ , which follows from $MA + \neg CH$ since $ℵ_{1} < c$ , gives a filter meeting all $D_{α}$ — an uncountable chain. Contradiction, so no Suslin tree and no Suslin line exists.

□

Exercises for §6.11 →

6.12Independence results

Every statement in this chapter that is not a theorem is independent, and the independence is proved by exhibiting two models. The models come from two techniques only: inner models cut $V$ down, forcing blows it up.

Theorem 6.62 (The status of the main statements). Assume $ZFC$ is consistent. Then each of the following is consistent with $ZFC$ , and so is its negation: $CH$ ; $MA + \neg CH$ ; " $c = ℵ_{2}$ "; "every $Σ_{2}^{1}$ set is Lebesgue measurable" (this one needs an inaccessible); "there is a Suslin tree"; $♢$ .

Proof. $CH$ holds in $L$ by $V = L$ decides the continuum, and $\neg CH$ holds after adding $ℵ_{2}$ Cohen reals: the poset $Fn (ω_{2} \times ω, 2)$ is ccc by the $Δ$ -system lemma proved later in this chapter, so it preserves cardinals, and it adds $ℵ_{2}$ distinct reals.

$MA + \neg CH$ : iterate ccc forcings with finite support for $ω_{2}$ steps over a model of $CH$ , at each step forcing with a ccc poset of size $< ℵ_{2}$ chosen by a bookkeeping function that anticipates all such posets appearing in the final model. A finite-support iteration of ccc posets is ccc — again by a $Δ$ -system argument — so cardinals are preserved, and in the end $c = ℵ_{2}$ and every ccc poset of size $< c$ has been handled, which suffices for $MA$ .

$♢$ holds in $L$ and fails under $MA + \neg CH$ , since $♢$ implies $CH$ by the theorem $♢$ implies $CH$ below. A Suslin tree exists in $L$ , by a $♢$ -construction, and none exists under $MA + \neg CH$ by the example above.

Only the measurability statement behaves differently, and it is the exception worth remembering: its consistency is not free.∎

Theorem 6.63 (Solovay's model). If there is an inaccessible cardinal, then there is a model of $ZF + DC$ in which every set of reals is Lebesgue measurable, has the Baire property and has the perfect set property; and a model of $ZFC$ in which every definable-from-a-real set of reals is measurable. Conversely, Shelah showed that "every $Σ_{3}^{1}$ set is Lebesgue measurable" implies $ω_{1}$ is inaccessible in $L$ , so the inaccessible is necessary.

Proof (Sketch — assumes the Lévy collapse and its homogeneity). Let $κ$ be inaccessible and force with the Lévy collapse $Coll (ω, < κ)$ , making $κ = ω_{1}$ of the extension. In the extension, every real appears in an intermediate model $V [G ↾ α]$ for some $α < κ$ , and the remaining forcing is homogeneous, so no real can define a pathological set: any set of reals definable from a real is measurable, because the random-real characterisation of measurability (" $A$ is measurable iff for comeagre-many conditions, membership is decided by a random real over the intermediate model") is preserved by the homogeneity. Passing to the inner model $L (R)$ of the extension, where choice fails but $DC$ survives, gives the full statement for all sets of reals. The necessity direction shows why: measurability of all $Σ_{3}^{1}$ sets forces $ω_{1}^{V}$ to be inaccessible in every $L [x]$ , exactly the hypothesis we started from.∎

Example 6.64 (Reading off a consistency strength). A colleague claims to have a $ZFC$ proof that every projective set is Lebesgue measurable. Without checking the argument, why is it wrong?

Solution.

By clause (1) of The projective hierarchy escapes ZFC, $V = L$ yields a $Δ_{2}^{1}$ non-measurable set, and $V = L$ is consistent with $ZFC$ relative to $ZFC$ .
So $ZFC$ cannot prove even $Δ_{2}^{1}$ measurability, let alone the full projective statement.
Worse, by Solovay's model the projective statement implies $ω_{1}$ is inaccessible in $L [x]$ for every real $x$ , which gives $Con (ZFC + inaccessible)$ .
A $ZFC$ proof would therefore prove $Con (ZFC)$ inside $ZFC$ , contradicting Godel's second incompleteness theorem. The claim is refuted without reading a line of it.

□

Remark. This is the pattern everywhere in modern set theory. A regularity statement about definable sets is equiconsistent with a large cardinal: $Σ_{2}^{1}$ measurability with an inaccessible, projective determinacy with infinitely many Woodin cardinals, $AD^{L (R)}$ with $ω$ Woodins carrying a measurable above. Consistency strength is the currency in which set-theoretic statements are priced.

Exercises for §6.12 →

6.13Clubs, stationary sets, $♢$ and $□$

Uncountable regular cardinals carry a notion of "almost every ordinal", and the whole of modern infinite combinatorics is written in it.

Definition 6.65 (Club and stationary). Let $κ$ be a regular uncountable cardinal. $C \subseteq κ$ is closed unbounded (club) if it is unbounded in $κ$ and contains all its limit points below $κ$ . $S \subseteq κ$ is stationary if $S \cap C \neq = \emptyset$ for every club $C$ . A function $f$ on $S$ is regressive if $f (α) < α$ for all $α \in S$ with $α > 0$ .

Theorem 6.66 (The clubs generate a $κ$ -complete filter). Let $κ$ be regular uncountable. The intersection of two clubs in $κ$ is club, and more generally the intersection of fewer than $κ$ clubs is club. The diagonal intersection $△_{α < κ} C_{α} = {ξ < κ : ξ \in C_{α} for all α < ξ}$ of $κ$ clubs is club.

Proof. Two clubs. Let $C, D$ be clubs. $C \cap D$ is closed, being an intersection of closed sets. For unboundedness, fix $β < κ$ and build an increasing sequence: pick $c_{0} \in C$ above $β$ , then $d_{0} \in D$ above $c_{0}$ , then $c_{1} \in C$ above $d_{0}$ , and so on, alternating. The sequence has length $ω$ and $κ$ is regular uncountable, so $γ = sup_{n} c_{n} = sup_{n} d_{n} < κ$ . Now $γ$ is a limit of points of $C$ , so $γ \in C$ by closure, and likewise $γ \in D$ . Thus $γ \in C \cap D$ and $γ > β$ .

Fewer than $κ$ clubs. Let $λ < κ$ and $C_{i}$ , $i < λ$ , be clubs. Closedness is again automatic. For unboundedness above $β$ , define $β_{0} = β$ and $β_{n + 1} = sup_{i < λ} min (C_{i} ∖ (β_{n} + 1))$ . Each min exists by unboundedness, and the sup of $λ < κ$ ordinals below $κ$ is below $κ$ by regularity. Then $γ = sup_{n} β_{n} < κ$ and $γ$ is a limit of points of each $C_{i}$ , hence lies in every $C_{i}$ .

Diagonal intersection. Write $C = △_{α} C_{α}$ . Closed: if $ξ$ is a limit of points $ξ_{n} \in C$ and $α < ξ$ , then $α < ξ_{n}$ for large $n$ , so $ξ_{n} \in C_{α}$ for those $n$ , and $ξ = sup ξ_{n} \in C_{α}$ by closure of $C_{α}$ . Unbounded: given $β$ , set $β_{0} = β + 1$ and $β_{n + 1}$ = some element of $⋂_{α < β_{n}} C_{α}$ above $β_{n}$ , which exists because that intersection is club by the previous paragraph ( $β_{n} < κ$ clubs). Then $γ = sup_{n} β_{n}$ lies in $C_{α}$ for every $α < γ$ , since $α < β_{n}$ for some $n$ and all later $β_{m}$ lie in $C_{α}$ .∎

Theorem 6.67 (Fodor's pressing-down lemma). Let $κ$ be regular uncountable, $S \subseteq κ$ stationary and $f : S \to κ$ regressive. Then there is $α < κ$ such that $f^{- 1} ({α})$ is stationary; in particular $f$ is constant on a stationary set.

Proof. Suppose not: for each $α < κ$ the set $S_{α} = {ξ \in S : f (ξ) = α}$ is non-stationary, so there is a club $C_{α}$ with $S_{α} \cap C_{α} = \emptyset$ . Let $C = △_{α < κ} C_{α}$ , a club by The clubs generate a $κ$ -complete filter, and let $C^{'} = C \cap {ξ < κ : ξ limit}$ , still club.

Since $S$ is stationary, pick $ξ \in S \cap C^{'}$ . Then $ξ > 0$ , so $f (ξ) = α$ for some $α < ξ$ . Membership $ξ \in C$ means $ξ \in C_{β}$ for every $β < ξ$ , in particular $ξ \in C_{α}$ . But $f (ξ) = α$ means $ξ \in S_{α}$ , and $S_{α} \cap C_{α} = \emptyset$ . Contradiction.∎

Example 6.68 (Stationary but not club). Show that $S = {α < ω_{1} : cf (α) = ω}$ and $T = {α < ω_{1} : α a successor}$ differ in status: one is stationary and one is not.

Solution.

Every club $C \subseteq ω_{1}$ contains a limit point of itself: take an increasing $ω$ -sequence from $C$ , its supremum lies in $C$ and has cofinality $ω$ . So $C \cap S \neq = \emptyset$ for every club, i.e. $S$ is stationary.
$S$ is not club, since it contains no ordinal of cofinality $ω_{1}$ — but in $ω_{1}$ every limit has cofinality $ω$ , so here $S$ is in fact the set of all limits, which is club. The real contrast is with $T$ .
$T$ , the successors, misses the club of limit ordinals entirely, so $T$ is not stationary.
The moral: "stationary" is the correct notion of largeness for a set that may be full of holes, and by Fodor's pressing-down lemma a regressive function on such a set still collapses to a single value on a set that is large in the same sense.

□

Definition 6.69 ( $♢$ and $□_{κ}$ ). $♢$ asserts: there is a sequence $⟨ A_{α} : α < ω_{1} ⟩$ with $A_{α} \subseteq α$ such that for every $A \subseteq ω_{1}$ the guessing set ${α < ω_{1} : A \cap α = A_{α}}$ is stationary in $ω_{1}$ .

$□_{κ}$ asserts: there is a sequence $⟨ C_{α} : α < κ^{+}, α limit ⟩$ with each $C_{α}$ club in $α$ , $ot (C_{α}) \leq κ$ , and coherence: if $β$ is a limit point of $C_{α}$ then $C_{β} = C_{α} \cap β$ .

Theorem 6.70 ( $♢$ implies $CH$ ).

♢ \Rightarrow 2^{ℵ_{0}} = ℵ_{1}

Proof. Let $⟨ A_{α} : α < ω_{1} ⟩$ be a $♢$ -sequence. Let $A \subseteq ω$ be arbitrary. Viewing $A$ as a subset of $ω_{1}$ , the set ${α : A \cap α = A_{α}}$ is stationary, hence unbounded, so it contains some $α > ω$ . For such an $α$ , $A \cap α = A$ because $A \subseteq ω \subseteq α$ , so $A = A_{α}$ .

Therefore every subset of $ω$ occurs in the sequence $⟨ A_{α} : α < ω_{1} ⟩$ , giving a surjection from $ω_{1}$ onto $P (ω)$ and hence $2^{ℵ_{0}} \leq ℵ_{1}$ . Cantor's theorem gives the other inequality.∎

Remark. $♢$ is strictly stronger than $CH$ : it holds in $L$ and is used there to construct a Suslin tree, a rigid Boolean algebra, and countless other objects by guessing every possible obstruction at some stage. $□_{κ}$ is the opposite kind of principle — it asserts that $κ^{+}$ is not reflective — and it too holds in $L$ , while $PFA$ refutes it. Together they are the two coordinates along which "the universe looks like $L$ " is measured.

Exercises for §6.13 →

6.14Infinite combinatorics: Ramsey theory

Definition 6.71 (The partition arrow). $κ \to (λ)_{m}^{n}$ means: for every colouring $c : [κ]^{n} \to m$ of the $n$ -element subsets of $κ$ with $m$ colours, there is $H \subseteq κ$ with $∣ H ∣ = λ$ such that $c$ is constant on $[H]^{n}$ . Such an $H$ is homogeneous. The negation is written $κ \neq \to (λ)_{m}^{n}$ .

Theorem 6.72 (Infinite Ramsey theorem). For all $n, m \geq 1$ , $ω \to (ω)_{m}^{n}$ : every $m$ -colouring of the $n$ -element subsets of an infinite set has an infinite homogeneous set.

Proof. Induct on $n$ . For $n = 1$ the statement is the pigeonhole principle: $ω$ split into $m$ pieces has an infinite piece.

Assume the result for $n$ and let $c : [ω]^{n + 1} \to m$ . Build a sequence of infinite sets $ω = H_{0} \supseteq H_{1} \supseteq \dots$ and points $a_{0} < a_{1} < \dots$ by successive refinement. Given $H_{k}$ infinite, let $a_{k} = min H_{k}$ and define a colouring of the $n$ -element subsets of $H_{k} ∖ {a_{k}}$ by

c_{k} (X) = c ({a_{k}} \cup X) .

By the induction hypothesis applied inside the infinite set $H_{k} ∖ {a_{k}}$ , there is an infinite $H_{k + 1} \subseteq H_{k} ∖ {a_{k}}$ homogeneous for $c_{k}$ ; let $ϵ_{k} < m$ be its colour. Thus: every $(n + 1)$ -set consisting of $a_{k}$ together with $n$ later elements of $H_{k + 1}$ has colour $ϵ_{k}$ .

Now $⟨ ϵ_{k} : k < ω ⟩$ is an $m$ -colouring of $ω$ , so by pigeonhole some colour $ϵ$ occurs for infinitely many $k$ ; let $K = {k : ϵ_{k} = ϵ}$ and $H = {a_{k} : k \in K}$ , an infinite set.

$H$ is homogeneous. Take any $(n + 1)$ -subset of $H$ , written ${a_{k_{0}}, a_{k_{1}}, \dots, a_{k_{n}}}$ with $k_{0} < k_{1} < \dots < k_{n}$ all in $K$ . The later points $a_{k_{1}}, \dots, a_{k_{n}}$ all lie in $H_{k_{0} + 1}$ , because the $H$ 's are decreasing and $a_{j} \in H_{j} \subseteq H_{k_{0} + 1}$ for $j > k_{0}$ . Hence the set has colour $ϵ_{k_{0}} = ϵ$ . So $c$ is constant on $[H]^{n + 1}$ .∎

Theorem 6.73 (Finite Ramsey theorem). For all $s, t \geq 2$ there is a least $N = R (s, t)$ such that every red/blue colouring of the edges of $K_{N}$ contains a red $K_{s}$ or a blue $K_{t}$ . Moreover

R (s, t) \leq R (s - 1, t) + R (s, t - 1), R (s, t) \leq (s - 1 s + t - 2) .

Proof. Induct on $s + t$ , with base cases $R (2, t) = t$ and $R (s, 2) = s$ : a colouring of $K_{t}$ either has a red edge, a red $K_{2}$ , or is all blue, a blue $K_{t}$ .

For the recursion, let $N = R (s - 1, t) + R (s, t - 1)$ and colour the edges of $K_{N}$ . Fix a vertex $v$ and split the other $N - 1$ vertices into $A$ , joined to $v$ in red, and $B$ , joined to $v$ in blue. Since $∣ A ∣ + ∣ B ∣ = N - 1 = R (s - 1, t) + R (s, t - 1) - 1$ , we cannot have both $∣ A ∣ \leq R (s - 1, t) - 1$ and $∣ B ∣ \leq R (s, t - 1) - 1$ . So either $∣ A ∣ \geq R (s - 1, t)$ or $∣ B ∣ \geq R (s, t - 1)$ .

In the first case, $A$ contains a red $K_{s - 1}$ — which together with $v$ , joined in red to all of $A$ , gives a red $K_{s}$ — or a blue $K_{t}$ , and we are done either way. The second case is symmetric.

The binomial bound follows by induction from the recursion and Pascal's rule: $(s - 2 s + t - 3) + (s - 1 s + t - 3) = (s - 1 s + t - 2)$ .∎

Theorem 6.74 (Sierpinski: the continuum is not Ramsey). $2^{ℵ_{0}} \neq \to (ℵ_{1})_{2}^{2}$ . In particular $ω_{1} \neq \to (ω_{1})_{2}^{2}$ under $CH$ , and the infinite Ramsey theorem does not lift to uncountable cardinals without large-cardinal hypotheses.

Proof. Let $X \subseteq R$ with $∣ X ∣ = 2^{ℵ_{0}}$ and fix a well-ordering $≺$ of $X$ . Define a colouring of pairs: for $x \neq = y$ in $X$ put

c ({x, y}) = {01 if ≺ and < agree on {x, y}, otherwise,

i.e. colour $0$ when the $≺$ -smaller of the two is also the smaller real.

Suppose $H \subseteq X$ is homogeneous of size $ℵ_{1}$ . If the colour is $0$ , then $≺$ restricted to $H$ agrees with the order of $R$ , so $H$ is a set of reals of order type $\geq ω_{1}$ under $<$ : enumerating $H$ in $≺$ -order gives a strictly increasing $ω_{1}$ -sequence of reals. If the colour is $1$ , the same enumeration is strictly decreasing.

Neither can exist. A strictly monotone $ω_{1}$ -sequence $⟨ x_{ξ} ⟩$ of reals produces $ω_{1}$ pairwise disjoint nonempty open intervals $(x_{ξ}, x_{ξ + 1})$ (or $(x_{ξ + 1}, x_{ξ})$ ), and each contains a rational; distinct intervals get distinct rationals, giving an injection $ω_{1} \to Q$ , which is absurd. So no homogeneous set of size $ℵ_{1}$ exists.∎

Theorem 6.75 (The $Δ$ -system lemma for finite sets). Let $F$ be a family of sets each of size $k \geq 1$ . If $∣ F ∣ > k! (k - 1)^{k}$ then $F$ contains a sunflower with $k + 1$ petals: sets $S_{0}, \dots, S_{k}$ and a core $Y$ with $S_{i} \cap S_{j} = Y$ for all $i \neq = j$ .

More generally, if $∣ F ∣ > k! (p - 1)^{k}$ then $F$ contains a sunflower with $p$ petals.

Proof. Induct on $k$ . For $k = 1$ the sets are singletons; if there are more than $(p - 1)$ of them, then $p$ of them are pairwise disjoint, a sunflower with empty core.

Let $k > 1$ and $∣ F ∣ > k! (p - 1)^{k}$ . Take a maximal subfamily $D = {D_{1}, \dots, D_{t}} \subseteq F$ of pairwise disjoint sets. If $t \geq p$ we have a sunflower with empty core and are done. So assume $t \leq p - 1$ and let $D = D_{1} \cup \dots \cup D_{t}$ , a set of size at most $k (p - 1)$ .

By maximality every member of $F$ meets $D$ . By pigeonhole some fixed element $x \in D$ lies in at least

\frac{∣ F ∣}{∣ D ∣} > \frac{k ! ( p - 1 ) ^{k}}{k ( p - 1 )} = (k - 1)! (p - 1)^{k - 1}

members of $F$ . Let $F^{'} = {S ∖ {x} : S \in F, x \in S}$ , a family of sets of size $k - 1$ with $∣ F^{'} ∣ > (k - 1)! (p - 1)^{k - 1}$ — distinct $S$ give distinct $S ∖ {x}$ since all contain $x$ .

By the induction hypothesis $F^{'}$ contains a sunflower $S_{1}^{'}, \dots, S_{p}^{'}$ with core $Y^{'}$ . Adding $x$ back, the sets $S_{i}^{'} \cup {x}$ belong to $F$ and form a sunflower with core $Y^{'} \cup {x}$ .∎

Figure 6.76. A sunflower with three petals. Every two of the sets

S_{1}, S_{2}, S_{3}

meet in exactly the shaded core, and nowhere else; what each set has outside the core is its own.

Theorem 6.77 (Erdos–Rado). For every infinite cardinal $κ$ and every $n < ω$ ,

ℶ_{n} (κ)^{+} \to (κ^{+})_{κ}^{n + 1},

where $ℶ_{0} (κ) = κ$ and $ℶ_{n + 1} (κ) = 2^{ℶ_{n} (κ)}$ . The case $n = 1$ reads $(2^{ℵ_{0}})^{+} \to (ℵ_{1})_{ℵ_{0}}^{2}$ .

Proof (Sketch — assumes the tree-of-elementary-submodels construction). Fix $c : [λ]^{n + 1} \to κ$ with $λ = ℶ_{n} (κ)^{+}$ . One builds a decreasing sequence of "end-homogeneous" sets by transfinite recursion of length $κ^{+}$ : at each stage one takes an elementary submodel of size $ℶ_{n - 1} (κ)$ closed under the colouring and picks an ordinal above its supremum, which is possible because $λ$ exceeds that size. The resulting set of $κ^{+}$ ordinals is end-homogeneous — the colour of an $(n + 1)$ -set depends only on its first $n$ elements — and the induction hypothesis for $n - 1$ applied to the induced $n$ -ary colouring extracts a genuinely homogeneous subset of size $κ^{+}$ . The bound is optimal: Sierpinski-style colourings show $ℶ_{n} (κ) \neq \to (κ^{+})_{κ}^{n + 1}$ , and Sierpinski: the continuum is not Ramsey is exactly the $n = 1$ , $κ = ℵ_{0}$ instance of that optimality.∎

Example 6.78 (Extracting a sunflower by hand). A family of $13$ three-element subsets of ${1, \dots, 9}$ is given. What does the $Δ$ -system lemma guarantee, and what is the threshold it actually needs?

Solution.

With $k = 3$ and $p = 3$ petals, the bound is $k! (p - 1)^{k} = 6 \cdot 2^{3} = 48$ . Thirteen sets are far below it, so the lemma guarantees nothing here.
For $p = 2$ the bound is $6 \cdot 1 = 6$ , so $13 > 6$ does guarantee a two-petal sunflower — which is trivial, since any two sets form one with core their intersection.
The honest reading: the sunflower bound is about families too large to avoid structure, and $48$ is the guarantee for three petals among $3$ -sets. The true threshold is conjectured to be around $C^{k}$ for an absolute constant, and the best known bound is $O (lo g k)^{k}$ — the sunflower conjecture is open.

□

Exercises for §6.14 →

6.15Applications of Ramsey theory

Theorem 6.79 ( $R (3, 3) = 6$ ). Every red/blue colouring of the edges of $K_{6}$ contains a monochromatic triangle, and some colouring of $K_{5}$ does not. Hence $R (3, 3) = 6$ .

Proof. Upper bound. Let $v$ be a vertex of $K_{6}$ . It has $5$ edges in two colours, so by pigeonhole at least $⌈ 5/2 ⌉ = 3$ of them share a colour, say red, joining $v$ to $x, y, z$ . If any of the edges $x y, yz, x z$ is red, it forms a red triangle with $v$ . Otherwise all three are blue and $x yz$ is a blue triangle. Either way a monochromatic triangle exists, so $R (3, 3) \leq 6$ .

Lower bound. Colour $K_{5}$ by placing the vertices at the corners of a regular pentagon, colouring the five pentagon edges red and the five diagonals blue. The red edges form a $5$ -cycle and the blue edges form a $5$ -cycle; a $5$ -cycle contains no triangle, since a triangle would need three mutually adjacent vertices and in a cycle of length $5$ no three vertices are mutually adjacent. So neither colour class contains a triangle, giving $R (3, 3) > 5$ .∎

Figure 6.80. The

R (3, 3) = 6

picture. Nine edges are drawn in one colour and six in the other; the second colour class splits into the two triangles

135

and

246

, and one of them is highlighted. No colouring of

K_{6}

can avoid such a triangle.

Theorem 6.81 (Schur's theorem). For every $r \geq 1$ there is $S (r)$ such that any $r$ -colouring of ${1, 2, \dots, S (r)}$ contains $x, y, z$ of the same colour with $x + y = z$ (allowing $x = y$ ).

Proof. Let $N = R_{r} (3)$ , the $r$ -colour Ramsey number for triangles, which is finite by the same induction as Finite Ramsey theorem. Given an $r$ -colouring $χ$ of ${1, \dots, N - 1}$ , colour the edges of the complete graph on vertices ${1, \dots, N}$ by

c ({i, j}) = χ (∣ i - j ∣) .

By Ramsey's theorem there is a monochromatic triangle $i < j < k$ : all three of $χ (j - i)$ , $χ (k - j)$ , $χ (k - i)$ are the same colour. Put $x = j - i$ , $y = k - j$ , $z = k - i$ . Then $x + y = z$ and all three have the same $χ$ -colour. So $S (r) \leq R_{r} (3)$ .∎

Theorem 6.82 (The $Δ$ -system lemma makes Cohen forcing ccc). For any index set $I$ , the poset $Fn (I, 2)$ of finite partial functions $I ⇀ 2$ ordered by reverse inclusion is ccc.

Proof. Suppose ${p_{ξ} : ξ < ω_{1}}$ were an uncountable antichain. The domains $dom (p_{ξ})$ are finite, so uncountably many share a single size $k$ ; restrict to those. The uncountable version of the $Δ$ -system lemma — proved by the same pigeonhole, using that $ω_{1}$ is regular — gives an uncountable subfamily whose domains form a sunflower with some finite core $Y$ .

On the core $Y$ there are only $2^{∣ Y ∣}$ possible restrictions $p_{ξ} ↾ Y$ , finitely many, so uncountably many of the conditions agree on $Y$ . Take two of them, $p$ and $q$ . They agree on $Y$ , and outside $Y$ their domains are disjoint by the sunflower property. Hence $p \cup q$ is a function, and it is a condition extending both. So $p$ and $q$ are compatible, contradicting antichain-ness.∎

Example 6.83 (Small Ramsey numbers and what they cost). Record the known values $R (3, 3)$ , $R (3, 4)$ , $R (4, 4)$ , $R (3, 3, 3)$ and compare $R (4, 4)$ with the bound from Finite Ramsey theorem.

Solution.

$R (3, 3) = 6$ , $R (3, 4) = 9$ , $R (4, 4) = 18$ , and for three colours $R (3, 3, 3) = 17$ .
The binomial bound gives $R (4, 4) \leq (3 6) = 20$ , against the true value $18$ — close, and the recursion $R (4, 4) \leq R (3, 4) + R (4, 3) = 9 + 9 = 18$ is exact here.
$R (5, 5)$ is unknown; it is known to lie between $43$ and $46$ . The number of $2$ -colourings of $K_{43}$ is $2^{903}$ , which is why exhaustive search is hopeless and why Erdos's remark about aliens demanding $R (6, 6)$ is not a joke.

□

Example 6.84 (A van der Waerden count). Every $2$ -colouring of ${1, \dots, 9}$ contains a monochromatic $3$ -term arithmetic progression, and some $2$ -colouring of ${1, \dots, 8}$ does not, so $W (2, 3) = 9$ . Verify the lower bound by exhibiting a colouring.

Solution.

Colour ${1, \dots, 8}$ by the pattern $RBBRRBBR$ : red on ${1, 4, 5, 8}$ , blue on ${2, 3, 6, 7}$ .
Red $3$ -term progressions would need $a, a + d, a + 2 d$ all in ${1, 4, 5, 8}$ : checking the differences $3, 4, 7$ from $1$ ; $1, 4$ from $4$ ; $3$ from $5$ — the candidate ${1, 4, 7}$ fails since $7$ is blue, ${4, 5, 6}$ fails since $6$ is blue, and no other triple fits.
Blue progressions inside ${2, 3, 6, 7}$ : candidates ${2, 3, 4}$ , ${3, 6, 9}$ , ${2, 6, 10}$ all leave the set. None survives.
So $W (2, 3) > 8$ , and the upper bound $W (2, 3) \leq 9$ is a short case check: in ${1, \dots, 9}$ the middle elements force a repetition. Hence $W (2, 3) = 9$ .

□

Exercises for §6.15 →

Common Mistakes

Thinking the Borel hierarchy closes at $ω$ . It closes at $ω_{1}$ and at no earlier ordinal. The proof of The Borel hierarchy closes at $ω_{1}$ uses the regularity of $ω_{1}$ exactly once, and that step is unavailable below.
Believing "analytic = Borel". Analytic sets are projections of Borel sets and there are analytic sets that are not Borel; the correct equation is Suslin: $Δ_{1}^{1} = B$ , which needs analyticity of both the set and its complement.
Saying $AD$ is simply false. It is false in $V$ , where choice holds, by $AD$ contradicts $AC$ . It is a serious and probably true axiom about $L (R)$ , where no well-ordering of the reals exists to run that diagonal argument.
Treating $MA$ as a strong axiom on its own. $CH$ implies $MA$ , so $MA$ alone has no consistency strength and no interesting consequences. The content is always in $MA + \neg CH$ .
Confusing club with stationary. Every club is stationary; the converse fails badly — $ω_{1}$ splits into $ω_{1}$ disjoint stationary sets, and no two disjoint sets can both be club.
Expecting Ramsey to lift to uncountable cardinals. $ω \to (ω)_{2}^{2}$ but $2^{ℵ_{0}} \neq \to (ℵ_{1})_{2}^{2}$ , by Sierpinski: the continuum is not Ramsey. A cardinal $κ > ω$ with $κ \to (κ)_{2}^{2}$ is weakly compact, hence inaccessible — a large cardinal.
Misreading the sunflower bound. $k! (p - 1)^{k}$ counts sets in the family, not elements in the ground set, and $k$ is the uniform size of each set. A family of $13$ three-element sets is nowhere near the threshold $48$ for three petals.
Assuming a large cardinal is needed for every independence result. $CH$ , $MA + \neg CH$ and $♢$ are all consistent relative to $ZFC$ alone. Only the regularity statements — $Σ_{2}^{1}$ measurability, projective determinacy, $PFA$ — actually cost something.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter

Introduction

6.1The Borel hierarchy

6.2Analytic and projective sets

6.3Measure, category and the perfect set property

6.4Infinite games and determinacy

6.5Inner models and the constructible universe

6.6Core model theory

6.7Covering lemmas

6.8Applications of the descriptive machinery

6.9Martin's axiom

6.10The proper forcing axiom

6.11Consequences of MA+¬CH

6.12Independence results

6.13Clubs, stationary sets, ♢ and □

6.14Infinite combinatorics: Ramsey theory

6.15Applications of Ramsey theory

6.11Consequences of $MA + \neg CH$

6.13Clubs, stationary sets, $♢$ and $□$