Sources and References
Primary textbook — Thomas Jech, Set Theory, 3rd ed., Springer, 2003.
Supplementary texts — Kenneth Kunen, Set Theory, 2nd ed., College Publications, 2011; Azriel Lévy, Basic Set Theory, Springer, 1979.
Online resources — Timothy Chow, A Beginner’s Guide to Forcing, AMS, 2008; Itay Neeman, UCLA Set Theory notes; Asger Törnquist, Copenhagen set theory notes; Yiannis Moschovakis, Notes on Set Theory, Springer.
Chapter 1: Axioms of Set Theory (ZFC)
Set theory serves as a universal foundation for mathematics. Every mathematical object — numbers, functions, topological spaces, groups — can be encoded as a set, and all of mathematics can in principle be derived from a small list of axioms about sets. The standard axiom system is Zermelo–Fraenkel set theory with the Axiom of Choice, abbreviated ZFC. It was assembled in its modern form during the first three decades of the twentieth century, with contributions from Ernst Zermelo (1908), Abraham Fraenkel, Thoralf Skolem, and John von Neumann.
The language of ZFC is first-order logic with a single binary predicate \(\in\) (membership). All variables range over sets. There are no “urelements” (non-set atoms) in the standard formulation. We write \(x \in y\) to mean “x is an element of y.”
The Axioms of ZFC
Extensionality
Axiom of Extensionality. Two sets are equal if and only if they have the same elements:
\[ \forall x \, \forall y \, \bigl( x = y \leftrightarrow \forall z\,(z \in x \leftrightarrow z \in y) \bigr). \]
This axiom makes sets purely extensional objects: a set is determined entirely by its members, not by how it is described or constructed.
Empty Set and Pairing
Axiom of Empty Set. There exists a set with no elements:
\[ \exists x \, \forall y \, (y \notin x). \]
By Extensionality, this set is unique; we denote it \(\emptyset\).
Axiom of Pairing. For any sets \(a\) and \(b\), there exists a set \(\{a, b\}\) whose elements are exactly \(a\) and \(b\):
\[ \forall a \, \forall b \, \exists c \, \forall x \, (x \in c \leftrightarrow x = a \lor x = b). \]
Taking \(a = b\) yields the singleton \(\{a\}\).
Union and Power Set
Axiom of Union. For any set \(F\), there exists a set \(\bigcup F\) consisting of all elements of elements of \(F\):
\[ \forall F \, \exists A \, \forall x \, \bigl(x \in A \leftrightarrow \exists y\,(x \in y \land y \in F)\bigr). \]
Axiom of Power Set. For any set \(X\), there exists the set \(\mathcal{P}(X)\) of all subsets of \(X\):
\[ \forall X \, \exists P \, \forall u \, \bigl(u \in P \leftrightarrow u \subseteq X\bigr). \]
Separation (Comprehension Schema)
Axiom Schema of Separation. For any set \(X\) and any formula \(\varphi(x)\) (with parameters), there exists the set of all elements of \(X\) satisfying \(\varphi\):
\[ \forall X \, \exists Y \, \forall x \, \bigl(x \in Y \leftrightarrow x \in X \land \varphi(x)\bigr). \]
This is a schema — one axiom for each formula \(\varphi\). It avoids Russell’s paradox: we cannot form \(\{x : x \notin x\}\) without already having a set \(X\) to draw elements from.
Replacement (Fraenkel’s Axiom Schema)
Axiom Schema of Replacement. If \(\varphi(x, y)\) defines a class-function (i.e., for every \(x\) there is at most one \(y\) with \(\varphi(x,y)\)), then the image of any set under this function is a set:
\[ \forall A \, \bigl[\forall x \in A \, \exists! y \, \varphi(x,y)\bigr] \to \exists B \, \forall x \in A \, \exists y \in B \, \varphi(x,y). \]
Replacement is strictly stronger than Separation and is needed to construct, for example, the set \(\{\omega, \mathcal{P}(\omega), \mathcal{P}(\mathcal{P}(\omega)), \ldots\}\).
Infinity
Axiom of Infinity. There exists an inductive set:
\[ \exists X \, \bigl(\emptyset \in X \land \forall y \in X \, (y \cup \{y\} \in X)\bigr). \]
The smallest inductive set is \(\omega = \{0, 1, 2, \ldots\}\) where \(0 = \emptyset\), \(1 = \{\emptyset\}\), \(2 = \{\emptyset, \{\emptyset\}\}\), etc. — the von Neumann natural numbers.
Regularity (Foundation)
Axiom of Regularity (Foundation). Every non-empty set has an \(\in\)-minimal element:
\[ \forall x \, \bigl(x \neq \emptyset \to \exists y \in x \, (y \cap x = \emptyset)\bigr). \]
Regularity forbids infinite descending \(\in\)-chains and, in particular, \(x \in x\). It implies the universe of sets is well-founded and stratified into the von Neumann hierarchy \(V = \bigcup_\alpha V_\alpha\).
Axiom of Choice
Axiom of Choice (AC). For every set \(X\) of non-empty pairwise disjoint sets, there is a set \(C\) (a choice set) that contains exactly one element from each member of \(X\):
\[ \forall X \, \bigl[\emptyset \notin X \to \exists f : X \to \bigcup X, \, \forall A \in X \, (f(A) \in A)\bigr]. \]
AC is independent of ZF (Zermelo–Fraenkel without choice), as shown by Cohen. It is equivalent to Zorn’s Lemma, the Well-Ordering Theorem, and Tychonoff’s Theorem for Hausdorff spaces.
Classes and the Cumulative Hierarchy
In ZFC, everything is a set, but it is useful to speak of proper classes — collections too large to be sets (like the class of all sets, \(V\), or the class of all ordinals, \(\mathbf{Ord}\)). These are formal abbreviations for formulas.
The
von Neumann hierarchy is defined by transfinite recursion:
- \(V_0 = \emptyset\)
- \(V_{\alpha+1} = \mathcal{P}(V_\alpha)\)
- \(V_\lambda = \bigcup_{\alpha < \lambda} V_\alpha\) for limit ordinals \(\lambda\)
The
rank of a set \(x\) is the least \(\alpha\) such that \(x \in V_{\alpha+1}\). The universe is \(V = \bigcup_\alpha V_\alpha\).
(ZFC) Every set has a rank. Equivalently, \(V = \bigcup_{\alpha \in \mathbf{Ord}} V_\alpha\).
This follows from the Axiom of Regularity by \(\in\)-induction: if every element of \(x\) has a rank, then \(x \in V_{\sup\{\text{rank}(y)+1 : y \in x\}+1}\).
Chapter 2: Ordinal Numbers
Ordinals are the backbone of transfinite mathematics. They generalize the natural numbers to the infinite, providing canonical representatives for well-ordered sets and a framework for transfinite induction and recursion.
Well-Orderings and Order Types
A well-ordering of a set \(A\) is a linear (total) order \(<\) on \(A\) such that every non-empty subset of \(A\) has a least element. A well-ordered set is a pair \((A, <)\) where \(<\) is a well-ordering.
Two well-ordered sets \((A, <_A)\) and \((B, <_B)\) are isomorphic (written \((A,<_A) \cong (B,<_B)\)) if there exists an order-preserving bijection between them.
Any two well-ordered sets are comparable: one is isomorphic to an initial segment of the other, or they are isomorphic to each other.
Von Neumann Ordinals
A set \(\alpha\) is an ordinal if it is transitive (\(x \in \alpha \Rightarrow x \subseteq \alpha\)) and well-ordered by \(\in\). Equivalently, \(\alpha\) is an ordinal if every element of \(\alpha\) is also a subset of \(\alpha\) and \(\alpha\) is linearly ordered by \(\in\).
The key insight of von Neumann’s definition is that each ordinal is the set of all smaller ordinals: \(\alpha = \{\beta : \beta < \alpha\}\).
- \(0 = \emptyset\)
- \(1 = \{0\} = \{\emptyset\}\)
- \(2 = \{0,1\} = \{\emptyset, \{\emptyset\}\}\)
- \(\omega = \{0, 1, 2, 3, \ldots\}\) — the first infinite ordinal
- \(\omega + 1 = \omega \cup \{\omega\} = \{0, 1, 2, \ldots, \omega\}\)
- \(\omega \cdot 2 = \omega + \omega\), \(\omega^2\), \(\omega^\omega\), \(\epsilon_0 = \omega^{\omega^{\omega^{\cdots}}}\) — the first fixed point of \(\alpha \mapsto \omega^\alpha\)
Successor and Limit Ordinals
An ordinal \(\alpha\) is a successor ordinal if \(\alpha = \beta + 1 = \beta \cup \{\beta\}\) for some ordinal \(\beta\). It is a limit ordinal if \(\alpha \neq 0\) and \(\alpha\) is not a successor; equivalently, \(\alpha = \sup_{\beta < \alpha} \beta = \bigcup \alpha\).
The ordinals \(0, \omega, \omega \cdot 2, \omega^2, \ldots\) are limit ordinals (with \(0\) sometimes treated separately). Every natural number \(n \geq 1\) is a successor ordinal.
Transfinite Induction and Recursion
Transfinite Induction. Let \(\Phi(\alpha)\) be a property of ordinals. If \(\Phi(0)\) holds, and whenever \(\Phi(\beta)\) holds for all \(\beta < \alpha\) then \(\Phi(\alpha)\) holds, then \(\Phi(\alpha)\) holds for all ordinals \(\alpha\).
Transfinite Recursion. Let \(G\) be a class function. Then there exists a unique class function \(F\) on \(\mathbf{Ord}\) such that \(F(\alpha) = G(F \restriction \alpha)\) for all ordinals \(\alpha\).
This theorem justifies defining functions by recursion over the ordinals, such as the von Neumann hierarchy, ordinal arithmetic, and the constructible universe.
Ordinal Arithmetic
Ordinal arithmetic is defined by transfinite recursion and differs from cardinal arithmetic in being non-commutative.
- Addition: \(\alpha + 0 = \alpha\); \(\alpha + (\beta+1) = (\alpha + \beta) + 1\); \(\alpha + \lambda = \sup_{\beta < \lambda}(\alpha + \beta)\) for limit \(\lambda\).
- Multiplication: \(\alpha \cdot 0 = 0\); \(\alpha \cdot (\beta+1) = \alpha \cdot \beta + \alpha\); \(\alpha \cdot \lambda = \sup_{\beta < \lambda}(\alpha \cdot \beta)\).
- Exponentiation: \(\alpha^0 = 1\); \(\alpha^{\beta+1} = \alpha^\beta \cdot \alpha\); \(\alpha^\lambda = \sup_{\beta < \lambda} \alpha^\beta\).
Cantor Normal Form. Every ordinal \(\alpha > 0\) can be written uniquely as
\[ \alpha = \omega^{\beta_1} \cdot k_1 + \omega^{\beta_2} \cdot k_2 + \cdots + \omega^{\beta_n} \cdot k_n \]
where \(\beta_1 > \beta_2 > \cdots > \beta_n \geq 0\) are ordinals and \(k_1, \ldots, k_n \geq 1\) are natural numbers.
Chapter 3: Cardinal Numbers
While ordinals measure the type of a well-ordering, cardinals measure size. Two sets have the same cardinality if there is a bijection between them, regardless of any ordering.
Cardinality and the Schröder–Bernstein Theorem
Two sets \(A\) and \(B\) are equinumerous (written \(|A| = |B|\) or \(A \sim B\)) if there exists a bijection \(f: A \to B\). We write \(|A| \leq |B|\) if there is an injection \(A \hookrightarrow B\).
Schröder–Bernstein Theorem. If \(|A| \leq |B|\) and \(|B| \leq |A|\), then \(|A| = |B|\).
Suppose \(f: A \hookrightarrow B\) and \(g: B \hookrightarrow A\) are injections. Define \(C_0 = A \setminus g(B)\) and \(C_{n+1} = g(f(C_n))\). Let \(C = \bigcup_n C_n\). Define \(h: A \to B\) by \(h(x) = f(x)\) if \(x \in C\), and \(h(x) = g^{-1}(x)\) if \(x \notin C\). One verifies that \(h\) is well-defined and is a bijection.
Infinite Cardinals and Alephs
A cardinal is an ordinal \(\kappa\) such that \(|\kappa| \neq |\alpha|\) for all \(\alpha < \kappa\). Equivalently (under AC), a cardinal is an ordinal that is not in bijection with any smaller ordinal.
The infinite cardinals are the alephs: \(\aleph_0 = \omega\), \(\aleph_1 = \omega_1\), \(\aleph_2 = \omega_2\), and so on. We also write \(\omega_\alpha\) for the \(\alpha\)-th infinite cardinal.
- \(\aleph_{\alpha+1} = \omega_{\alpha+1}\) is the least cardinal greater than \(\aleph_\alpha\).
- \(\aleph_\lambda = \bigcup_{\alpha < \lambda} \aleph_\alpha\) for limit ordinals \(\lambda\).
Cantor’s Theorem
Cantor's Theorem. For any set \(X\), \(|X| < |\mathcal{P}(X)|\).
The map \(x \mapsto \{x\}\) is an injection \(X \to \mathcal{P}(X)\), so \(|X| \leq |\mathcal{P}(X)|\). Suppose for contradiction that \(f: X \to \mathcal{P}(X)\) is a surjection. Define \(D = \{x \in X : x \notin f(x)\}\). Since \(f\) is surjective, \(D = f(d)\) for some \(d \in X\). Then \(d \in D \leftrightarrow d \notin f(d) = D\), a contradiction.
Cardinal Arithmetic
For cardinals \(\kappa\) and \(\lambda\):
- \(\kappa + \lambda = |\kappa \sqcup \lambda|\) (disjoint union)
- \(\kappa \cdot \lambda = |\kappa \times \lambda|\) (Cartesian product)
- \(\kappa^\lambda = |\kappa^\lambda|\) (set of all functions \(\lambda \to \kappa\))
For infinite cardinals \(\kappa\), \(\kappa + \kappa = \kappa \cdot \kappa = \kappa\). More generally, if \(\kappa\) is an infinite cardinal and \(\lambda \leq \kappa\), then \(\kappa + \lambda = \kappa \cdot \lambda = \kappa\).
The key step is showing \(\kappa \cdot \kappa = \kappa\) for all infinite \(\kappa\), proved by well-ordering \(\kappa \times \kappa\) by the canonical pair ordering and applying transfinite induction.
Cofinality
The cofinality \(\mathrm{cf}(\alpha)\) of a limit ordinal \(\alpha\) is the least ordinal \(\delta\) such that there exists an unbounded (cofinal) function \(f: \delta \to \alpha\). A cardinal \(\kappa\) is regular if \(\mathrm{cf}(\kappa) = \kappa\), and singular otherwise.
- \(\mathrm{cf}(\omega) = \omega\) — \(\omega\) is regular.
- \(\mathrm{cf}(\omega_1) = \omega_1\) — \(\omega_1\) is regular.
- \(\mathrm{cf}(\aleph_\omega) = \omega\) — \(\aleph_\omega\) is singular (it is the supremum of the sequence \(\aleph_0, \aleph_1, \aleph_2, \ldots\)).
König's Theorem. For any cardinals \(\kappa_i < \lambda_i\) (for \(i \in I\)):
\[ \sum_{i \in I} \kappa_i < \prod_{i \in I} \lambda_i. \]
In particular, \(\kappa < \kappa^{\mathrm{cf}(\kappa)}\) for any infinite cardinal \(\kappa\).
König’s Theorem immediately implies \(2^{\aleph_0} \neq \aleph_\omega\), since \(\mathrm{cf}(\aleph_\omega) = \omega\) and \(2^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} \geq \aleph_\omega^{\aleph_0} > \aleph_\omega\).
Chapter 4: Real Numbers
Set theory provides a rigorous construction of the real number system from the natural numbers. The key cardinality result is that \(|\mathbb{R}| = |\mathcal{P}(\omega)| = 2^{\aleph_0}\), the cardinality of the continuum.
The Continuum
The continuum is the cardinality \(\mathfrak{c} = 2^{\aleph_0} = |\mathbb{R}|\).
\(|\mathbb{R}| = |\mathcal{P}(\omega)| = 2^{\aleph_0}\). Moreover, \(|\mathbb{R}^n| = |\mathbb{R}|\) for all \(n \geq 1\), and \(|\mathbb{R}^\omega| = |\mathbb{R}|\).
The Continuum Hypothesis (CH) asserts that \(2^{\aleph_0} = \aleph_1\), i.e., there is no set of reals with cardinality strictly between \(\aleph_0\) and \(\mathfrak{c}\). The Generalized Continuum Hypothesis (GCH) asserts \(2^{\aleph_\alpha} = \aleph_{\alpha+1}\) for all \(\alpha\).
Cardinality of the Cantor Set and Descriptive Set Theory Preview
The Cantor set \(C \subseteq [0,1]\) has \(|C| = 2^{\aleph_0} = \mathfrak{c}\). Every closed subset of \(\mathbb{R}\) is either countable or of size \(\mathfrak{c}\) — this is the Cantor–Bendixson theorem. Chapter 11 will develop the descriptive set-theoretic hierarchy that extends this analysis.
Chapter 5: The Axiom of Choice and Cardinal Arithmetic
Equivalents of the Axiom of Choice
The following are equivalent over ZF:
- The Axiom of Choice.
- Zorn's Lemma: Every partially ordered set in which every chain has an upper bound has a maximal element.
- Well-Ordering Theorem: Every set can be well-ordered.
- Tychonoff's Theorem: Any product of compact Hausdorff spaces is compact.
- Every vector space has a basis (Hamel basis).
- Every surjection has a right inverse.
(Sketch) AC \(\Rightarrow\) Well-Ordering: Use AC to repeatedly pick the least element not yet ordered. Well-Ordering \(\Rightarrow\) Zorn: Given a chain-complete poset, well-order it and apply transfinite recursion to climb to a maximal element. Zorn \(\Rightarrow\) AC: Given a family of non-empty sets, form the poset of partial choice functions ordered by extension; a maximal element is a total choice function.
Cardinal Exponentiation and the GCH
Under GCH, all infinite cardinal arithmetic reduces to simple rules:
Assume GCH. For infinite cardinals \(\kappa \leq \lambda\):
\[ \kappa^\lambda = \begin{cases} \lambda^+ & \text{if } \kappa \leq \mathrm{cf}(\lambda), \\ \lambda & \text{if } \mathrm{cf}(\lambda) < \kappa \leq \lambda. \end{cases} \]
Without GCH, cardinal exponentiation is much harder to determine and is the subject of Shelah’s pcf theory.
Singular Cardinal Hypothesis
The Singular Cardinal Hypothesis (SCH) states: for every singular cardinal \(\kappa\), if \(2^{\mathrm{cf}(\kappa)} < \kappa\), then \(\kappa^{\mathrm{cf}(\kappa)} = \kappa^+\).
SCH follows from GCH and holds in many canonical inner models. Its failure (which requires large cardinal hypotheses) was demonstrated by Silver, Magidor, and others.
Chapter 6: The Axiom of Regularity
The Axiom of Regularity (Foundation) asserts that every non-empty set has an \(\in\)-minimal element. This has deep structural consequences.
Well-Foundedness
The following are equivalent over ZF \(-\) Foundation + \(\forall x\,(x \notin x)\):
- The Axiom of Regularity.
- There is no infinite descending \(\in\)-chain \(x_0 \ni x_1 \ni x_2 \ni \cdots\)
- The cumulative hierarchy \(V = \bigcup_\alpha V_\alpha\) covers all sets.
Consequences
(ZF + Foundation) The class \(\mathbf{Ord}\) of all ordinals is well-ordered by \(\in\), and every set \(x\) has a well-defined rank in the cumulative hierarchy.
In ordinary mathematics, Regularity is often used implicitly: for instance, to show that \(\in\)-induction is valid on the universe.
Chapter 7: Filters, Ultrafilters, and Boolean Algebras
Filters and ultrafilters are central to model theory, topology, and large cardinal theory. They provide the mechanism for the ultrapower construction of measurable cardinals and Cohen’s forcing via Boolean-valued models.
Filters
Let \(I\) be a non-empty set. A
filter on \(I\) is a non-empty family \(\mathcal{F} \subseteq \mathcal{P}(I)\) such that:
- \(I \in \mathcal{F}\) and \(\emptyset \notin \mathcal{F}\),
- If \(A \in \mathcal{F}\) and \(A \subseteq B\), then \(B \in \mathcal{F}\) (upward closure),
- If \(A, B \in \mathcal{F}\), then \(A \cap B \in \mathcal{F}\) (finite intersection property).
A
ultrafilter is a filter \(\mathcal{U}\) such that for every \(A \subseteq I\), either \(A \in \mathcal{U}\) or \(I \setminus A \in \mathcal{U}\).
A filter \(\mathcal{F}\) on \(I\) is \(\kappa\)-complete if it is closed under intersections of fewer than \(\kappa\) sets: for any family \(\{A_\alpha : \alpha < \lambda\} \subseteq \mathcal{F}\) with \(\lambda < \kappa\), we have \(\bigcap_\alpha A_\alpha \in \mathcal{F}\).
The Fréchet filter on \(\omega\) is \(\mathcal{F} = \{A \subseteq \omega : \omega \setminus A \text{ is finite}\}\) (the cofinite filter). It is \(\aleph_0\)-complete but not \(\aleph_1\)-complete.
Ultrafilters and the Ultrapower
(AC) Every filter can be extended to an ultrafilter. In particular, every set carries a non-principal ultrafilter.
Given a structure \(M\) and an ultrafilter \(\mathcal{U}\) on a set \(I\), the ultrapower \(M^I/\mathcal{U}\) consists of equivalence classes of functions \(f: I \to M\) under \(f \sim g \iff \{i \in I : f(i) = g(i)\} \in \mathcal{U}\), with operations defined pointwise.
Łoś's Theorem. Let \(M\) be a first-order structure and \(\mathcal{U}\) an ultrafilter on \(I\). For any first-order formula \(\varphi(x_1,\ldots,x_n)\) and functions \(f_1, \ldots, f_n: I \to M\):
\[ M^I/\mathcal{U} \models \varphi([f_1],\ldots,[f_n]) \iff \{i \in I : M \models \varphi(f_1(i),\ldots,f_n(i))\} \in \mathcal{U}. \]
This theorem is fundamental: the ultrapower satisfies the same first-order sentences as \(M\), and is used to construct elementary extensions and measurable cardinals.
Boolean Algebras
A Boolean algebra is a set \(B\) with operations \(\land, \lor, \lnot\) and constants \(0, 1\) satisfying the usual Boolean laws. A complete Boolean algebra is one where every subset has a supremum and infimum.
Complete Boolean algebras provide the algebraic foundation for forcing: a generic filter over a complete Boolean algebra \(\mathbb{B}\) gives rise to a generic extension \(V^\mathbb{B}\).
Chapter 8: Stationary Sets
Stationary sets form one of the most powerful tools in combinatorial set theory. They arise naturally in the analysis of uncountable cardinals and feature prominently in results about cardinal arithmetic, partition relations, and inner models.
Club Sets
Let \(\kappa\) be an uncountable regular cardinal and \(C \subseteq \kappa\). We say \(C\) is
closed unbounded (or a
club) in \(\kappa\) if:
- Unbounded: \(\sup C = \kappa\) (i.e., for every \(\alpha < \kappa\) there exists \(\gamma \in C\) with \(\gamma > \alpha\)),
- Closed: For every limit ordinal \(\alpha < \kappa\), if \(C \cap \alpha\) is unbounded in \(\alpha\), then \(\alpha \in C\).
- The set of all limit ordinals below \(\omega_1\) is a club in \(\omega_1\).
- For any increasing function \(f: \omega_1 \to \omega_1\), the set of fixed points \(\{\alpha < \omega_1 : f(\alpha) = \alpha\}\) is a club.
- The intersection of two clubs is again a club.
The collection of all clubs in \(\kappa\) is closed under intersections: if \(C_1, C_2\) are clubs, so is \(C_1 \cap C_2\). More generally, the intersection of fewer than \(\kappa\) clubs is a club.
Let \(C_1, C_2\) be clubs. Their intersection \(C_1 \cap C_2\) is unbounded: given \(\alpha_0 < \kappa\), alternately pick elements of \(C_1\) and \(C_2\) above each other, forming a sequence \(\alpha_0 < \beta_0 < \alpha_1 < \beta_1 < \cdots\) with \(\beta_n \in C_1\) and \(\alpha_{n+1} \in C_2\). Their common limit \(\gamma = \sup_n \alpha_n = \sup_n \beta_n\) lies in both \(C_1\) and \(C_2\). For more than 2 clubs of size \(< \kappa\), use the diagonalization argument.
The Club Filter
The club filter on a regular uncountable cardinal \(\kappa\) is the filter \(\mathcal{F}_\kappa\) generated by all club subsets of \(\kappa\):
\[ \mathcal{F}_\kappa = \{A \subseteq \kappa : C \subseteq A \text{ for some club } C \subseteq \kappa\}. \]
The club filter \(\mathcal{F}_\kappa\) is \(\kappa\)-complete (closed under intersections of fewer than \(\kappa\) sets) but is not an ultrafilter (it is not a prime filter).
Stationary Sets
A set \(S \subseteq \kappa\) is stationary if it intersects every club: for every club \(C \subseteq \kappa\), \(S \cap C \neq \emptyset\). Equivalently, \(S\) is stationary iff \(S \notin \mathcal{I}_\kappa\) where \(\mathcal{I}_\kappa = \{A \subseteq \kappa : \kappa \setminus A \in \mathcal{F}_\kappa\}\) is the non-stationary ideal.
- Every club is stationary.
- The set \(\{\alpha < \omega_1 : \alpha \text{ is a successor ordinal}\}\) is stationary in \(\omega_1\).
- The set \(\{\alpha < \omega_1 : \mathrm{cf}(\alpha) = \omega\}\) is a club (it is all limit ordinals \(< \omega_1\), since all limit ordinals \(< \omega_1\) have cofinality \(\omega\)).
- For a regular cardinal \(\kappa > \omega_1\), the set \(E^\kappa_\omega = \{\alpha < \kappa : \mathrm{cf}(\alpha) = \omega\}\) is stationary in \(\kappa\) but contains no club.
The Pressing-Down (Fodor) Lemma
Pressing-Down Lemma (Fodor's Lemma). Let \(\kappa\) be an uncountable regular cardinal. If \(S \subseteq \kappa\) is stationary and \(f: S \to \kappa\) is a regressive function (i.e., \(f(\alpha) < \alpha\) for all \(\alpha \in S\), \(\alpha > 0\)), then there exists \(\gamma < \kappa\) such that \(f^{-1}(\gamma) = \{\alpha \in S : f(\alpha) = \gamma\}\) is stationary.
Suppose for contradiction that for every \(\gamma < \kappa\), the set \(f^{-1}(\gamma)\) is non-stationary. Then for each \(\gamma < \kappa\), there is a club \(C_\gamma \subseteq \kappa \setminus f^{-1}(\gamma)\). Let \(C = \bigcap_{\gamma < \kappa} C_\gamma\). Since \(\kappa\) is regular, this intersection of \(\kappa\)-many clubs is itself a club (note: for \(\omega_1\) this is an \(\omega_1\)-intersection; we need \(\kappa\)-completeness of the club filter). Now pick \(\alpha \in S \cap C\) (non-empty since \(S\) is stationary). Let \(\gamma = f(\alpha) < \alpha\). Then \(\alpha \in C \subseteq C_\gamma \subseteq \kappa \setminus f^{-1}(\gamma)\), so \(f(\alpha) \neq \gamma\), a contradiction.
More carefully, we handle the \(\kappa = \omega_1\) case by induction: assume all fibers are non-stationary. Then for each \(\gamma < \kappa\), pick a club \(C_\gamma\) disjoint from \(f^{-1}(\gamma)\). By transfinite induction, build a “diagonal intersection”: the set \(\Delta_{\gamma < \kappa} C_\gamma = \{\alpha < \kappa : \alpha \in C_\gamma \text{ for all } \gamma < \alpha\}\) is a club. Any \(\alpha\) in \(S \cap \Delta C_\gamma\) satisfies \(\alpha \in C_{f(\alpha)}\) (since \(f(\alpha) < \alpha\)), but \(C_{f(\alpha)} \cap f^{-1}(f(\alpha)) = \emptyset\), meaning \(\alpha \notin f^{-1}(f(\alpha))\), i.e., \(f(\alpha) \neq f(\alpha)\), contradiction.
Normal Filters and Normality
A filter \(\mathcal{F}\) on \(\kappa\) is normal if it is \(\kappa\)-complete and closed under diagonal intersections: if \(A_\alpha \in \mathcal{F}\) for each \(\alpha < \kappa\), then
\[ \Delta_{\alpha < \kappa} A_\alpha = \{\xi < \kappa : \xi \in A_\alpha \text{ for all } \alpha < \xi\} \in \mathcal{F}. \]
The club filter on \(\kappa\) is a normal, \(\kappa\)-complete filter.
Chapter 9: Combinatorial Set Theory
Combinatorial set theory studies partition properties, trees, and combinatorial principles that hold (or consistently fail) at various uncountable cardinals.
Ramsey Theory: Partition Calculus
The partition symbol \(\kappa \to (\lambda)^n_m\) means: for every coloring \(f: [\kappa]^n \to m\) (coloring \(n\)-element subsets of \(\kappa\) with \(m\) colors), there exists a homogeneous set \(H \subseteq \kappa\) of size \(\lambda\) (all \(n\)-element subsets of \(H\) have the same color).
Ramsey's Theorem. \(\omega \to (\omega)^n_k\) for all finite \(n, k\). That is, any finite coloring of \(n\)-element subsets of \(\omega\) has an infinite homogeneous set.
Erdős–Rado Theorem. \(\beth_n^+ \to (\aleph_1)^{n+1}_2\), where \(\beth_0 = \aleph_0\) and \(\beth_{n+1} = 2^{\beth_n}\). In particular, \((2^{\aleph_0})^+ \to (\aleph_1)^2_2\).
Trees
A tree is a partially ordered set \((T, <_T)\) such that for each \(t \in T\), the set of predecessors \(\{s \in T : s <_T t\}\) is well-ordered by \(<_T\). The height of \(t\) is the order type of its predecessors. The \(\alpha\)-th level of \(T\) is \(T_\alpha = \{t \in T : \text{ht}(t) = \alpha\}\). A branch is a maximal linearly ordered subset of \(T\).
An Aronszajn tree is an \(\omega_1\)-tree (height \(\omega_1\), every level countable) with no uncountable branch. A Suslin tree is an \(\omega_1\)-tree with no uncountable antichain and no uncountable branch.
König's Infinity Lemma. Every finitely branching infinite tree has an infinite branch.
Aronszajn trees exist in ZFC. (An explicit construction uses a careful transfinite recursion to build an \(\omega_1\)-tree whose branches all terminate before reaching height \(\omega_1\).)
The existence of a Suslin tree is independent of ZFC: it follows from the Diamond Principle \(\Diamond\) (which holds in Gödel’s \(L\)) but is refuted by Martin’s Axiom plus \(\neg\)CH.
The Diamond Principle
The Diamond Principle \(\Diamond = \Diamond(\omega_1)\) asserts: there exists a sequence \(\langle A_\alpha : \alpha < \omega_1 \rangle\) with \(A_\alpha \subseteq \alpha\) such that for every \(A \subseteq \omega_1\), the set \(\{\alpha < \omega_1 : A \cap \alpha = A_\alpha\}\) is stationary.
\(\Diamond\) implies CH. \(\Diamond\) holds in \(L\) (Gödel's constructible universe). \(\Diamond\) implies the existence of a Suslin tree.
Martin’s Axiom
Martin's Axiom \(\mathsf{MA}(\kappa)\) states: for every ccc partial order \(\mathbb{P}\) and any family \(\mathcal{D}\) of \(\leq \kappa\) dense subsets of \(\mathbb{P}\), there exists a \(\mathcal{D}\)-generic filter. \(\mathsf{MA} = \mathsf{MA}(\aleph_1)\) is the strongest natural form, and \(\mathsf{MA}(\omega) = \mathsf{ZFC}\).
\(\mathsf{MA} + \neg\mathsf{CH}\) is consistent with ZFC (proved by Solovay and Tennenbaum). Under \(\mathsf{MA} + \neg\mathsf{CH}\), all Aronszajn trees are special (contain no Suslin subtree), and \(2^{\aleph_0}\) can be any regular cardinal.
Chapter 10: Measurable Cardinals
Large cardinal axioms assert the existence of cardinals with strong combinatorial or model-theoretic properties. They form a natural hierarchy extending beyond ZFC and serve as consistency strength benchmarks.
Measurable Cardinals via Ultrafilters
A cardinal \(\kappa\) is measurable if there exists a non-principal \(\kappa\)-complete ultrafilter on \(\kappa\). Equivalently, \(\kappa\) is measurable if there is a two-valued measure \(\mu: \mathcal{P}(\kappa) \to \{0,1\}\) that is \(\kappa\)-additive (additive for fewer than \(\kappa\) disjoint sets), assigns 0 to singletons, and assigns 1 to \(\kappa\).
Every measurable cardinal is inaccessible (hence much larger than anything provably existing in ZFC).
Let \(\kappa\) be measurable with witnessing ultrafilter \(\mathcal{U}\). Suppose \(\kappa = \lambda^+\) for some cardinal \(\lambda < \kappa\). Write \(\kappa = \bigcup_{\alpha < \lambda} A_\alpha\) as a union of \(\lambda < \kappa\) sets each of size \(\lambda\). Since \(\mathcal{U}\) is \(\kappa\)-complete, it is also \(\lambda^+\)-complete; taking the \(\lambda\)-fold intersection of complements, we get a contradiction. For strong limit: if \(2^\lambda < \kappa\) for all \(\lambda < \kappa$, this follows from the fact that every set of size \(< \kappa\) is measure 0.
The Ultrapower Construction and Scott’s Theorem
Given a measurable cardinal \(\kappa\) with a \(\kappa\)-complete ultrafilter \(\mathcal{U}\), we form the ultrapower \(\text{Ult}(V, \mathcal{U})\):
The ultrapower of the universe \(\text{Ult}(V, \mathcal{U})\) consists of equivalence classes of functions \(f: \kappa \to V\) under \(f \sim g \iff \{\alpha < \kappa : f(\alpha) = g(\alpha)\} \in \mathcal{U}\). By Łoś's Theorem, \(\text{Ult}(V, \mathcal{U})\) is an elementary extension of \(V\) (modulo the necessary modifications for proper class models).
The canonical embedding \(j: V \to \text{Ult}(V,\mathcal{U})\) defined by \(j(x) = [c_x]_\mathcal{U}\) (constant function) is an elementary embedding. This embedding is non-trivial: \(j(\kappa) > \kappa\). The least ordinal moved by \(j\) is the critical point of \(j\), which equals \(\kappa\).
Scott's Theorem (1961). If there exists a measurable cardinal, then \(V \neq L\). That is, the constructible universe does not contain all sets if a measurable cardinal exists.
Let \(\kappa\) be measurable with ultrafilter \(\mathcal{U}\) and let \(j: V \to M = \text{Ult}(V,\mathcal{U})\) be the ultrapower embedding. The key is that \(j\) is non-trivial and \(\kappa\)-complete implies \(j\) moves no ordinal below \(\kappa\). By a result in the theory of \(L\), if \(V = L\) then \(j\) would restrict to an embedding of \(L\) into itself, but Kunen showed this leads to a contradiction with the existence of a non-trivial measurable cardinal in \(L\). More precisely: Gödel showed \(L\) satisfies GCH; in particular, there exists in \(L\) a well-ordering of \(\mathcal{P}(\kappa)\) of order type \(\kappa^+\). But in the presence of a measurable cardinal, one can show that \(\mathcal{P}(\kappa)\) in \(V\) is not constructible, i.e., \(\mathcal{P}(\kappa)^V \neq \mathcal{P}(\kappa)^L\) (since a normal measure on \(\kappa\) is not in \(L\)).
0-Sharp (\(0^\#\))
Scott’s theorem initiates a fundamental dichotomy: either \(V = L\) (no large cardinals of measurable strength) or \(V \neq L\) (large cardinals exist). The canonical witness for \(V \neq L\) at the measurable cardinal level is \(0^\#\) (zero-sharp):
\(0^\#\) (zero-sharp) is, if it exists, the theory of the structure \((L, \in, \alpha)_{\alpha \in \text{On}}\) — i.e., a certain well-defined real number (or equivalently, a set of natural numbers) encoding indiscernibles for \(L\). Its existence is equivalent to: the existence of uncountably many Silver indiscernibles for \(L\).
Jensen's Covering Theorem. If \(0^\#\) does not exist, then for every uncountable set \(X\) of ordinals, there exists \(Y \in L\) with \(X \subseteq Y\) and \(|Y| = |X|\). In other words, \(L\) "covers" \(V\).
Chapter 11: Borel and Analytic Sets
Descriptive set theory studies the definability and structural properties of subsets of Polish spaces (complete separable metric spaces), chief among them \(\mathbb{R}\) and \(\omega^\omega\) (Baire space).
The Borel Hierarchy
The
Borel sets of a topological space \(X\) are the sets in the smallest \(\sigma\)-algebra containing the open sets. They are stratified into the Borel hierarchy:
- \(\mathbf{\Sigma}^0_1\) = open sets
- \(\mathbf{\Pi}^0_1\) = closed sets
- \(\mathbf{\Sigma}^0_{\alpha+1}\) = countable unions of \(\mathbf{\Pi}^0_\alpha\) sets
- \(\mathbf{\Pi}^0_{\alpha+1}\) = complements of \(\mathbf{\Sigma}^0_{\alpha+1}\) sets
- \(\mathbf{\Delta}^0_\alpha = \mathbf{\Sigma}^0_\alpha \cap \mathbf{\Pi}^0_\alpha\)
The Borel hierarchy has height \(\omega_1\).
Analytic and Coanalytic Sets
A subset \(A\) of a Polish space \(X\) is analytic (\(\mathbf{\Sigma}^1_1\)) if it is the continuous image of a Borel subset of another Polish space. Equivalently, \(A\) is a projection of a closed set in \(X \times \omega^\omega\). The complement of an analytic set is coanalytic (\(\mathbf{\Pi}^1_1\)).
Suslin's Theorem. A subset of a Polish space is Borel if and only if it is both analytic and coanalytic.
Lusin Separation Theorem. If \(A\) and \(B\) are disjoint analytic sets in a Polish space, then there is a Borel set \(C\) with \(A \subseteq C\) and \(B \cap C = \emptyset\).
The Perfect Set Property and the Cantor–Bendixson Theorem
A set \(A \subseteq \mathbb{R}\) has the perfect set property if it is either countable or contains a perfect subset (a non-empty closed set with no isolated points). Perfect sets have cardinality \(\mathfrak{c}\).
Cantor–Bendixson. Every closed set \(F \subseteq \mathbb{R}\) is a union \(F = P \cup C\) where \(P\) is perfect (possibly empty) and \(C\) is countable.
Every analytic set has the perfect set property. In particular, every uncountable analytic set contains a perfect subset, hence has cardinality \(2^{\aleph_0}\).
Chapter 12: Models of Set Theory
To understand the independence of CH and other statements, we must understand what it means for a set or class to be a model of ZFC, and how to build new models from existing ones.
Structures and Satisfaction
A model of ZFC is a pair \((M, E)\) where \(M\) is a class (or set) and \(E \subseteq M \times M\) is a binary relation satisfying all the ZFC axioms when the quantifiers are restricted to \(M\) and \(\in\) is interpreted by \(E\). We write \(M \models \varphi\) for "\(\varphi\) is true in \(M\)."
A model \((M, E)\) is well-founded if \(E\) is well-founded. By the Mostowski Collapse Lemma, every well-founded extensional structure is isomorphic to a unique transitive structure \((\bar{M}, \in)\) called its transitive collapse.
Relativization and Absoluteness
For a formula \(\varphi\) and a class \(M\), the relativization \(\varphi^M\) is obtained by restricting all quantifiers to \(M\). A formula \(\varphi\) is absolute for a class \(M\) (or between \(M\) and \(V\)) if \(\varphi^M \leftrightarrow \varphi\).
A formula is \(\Delta_0\) if all quantifiers are bounded (\(\forall x \in y\) and \(\exists x \in y\)). All \(\Delta_0\) formulas are absolute for transitive models. \(\Sigma_1\) formulas are upward absolute (if true in \(M\) they are true in any extension), while \(\Pi_1\) formulas are downward absolute.
Elementary Substructures and the Löwenheim–Skolem Theorem
\(M\) is an elementary substructure of \(N\) (written \(M \prec N\)) if \(M \subseteq N\) and for every formula \(\varphi(\vec{x})\) and \(\vec{a} \in M\): \(M \models \varphi(\vec{a}) \iff N \models \varphi(\vec{a})\).
Downward Löwenheim–Skolem–Tarski. Let \((M, \in)\) be a model of ZFC and \(A \subseteq M\) with \(|A| \leq \kappa\). Then there is an elementary substructure \(N \prec M\) with \(A \subseteq N\) and \(|N| = \kappa\).
Reflection Principle
The Reflection Principle is a fundamental metatheorem of ZFC, showing that any finite list of axioms is “reflected” down to a set-sized structure within \(V\).
Reflection Principle. For any formula \(\varphi(x_1, \ldots, x_n)\) and any ordinal \(\alpha\), there exists an ordinal \(\beta > \alpha\) such that for all \(a_1, \ldots, a_n \in V_\beta\):
\[ V \models \varphi(a_1, \ldots, a_n) \iff V_\beta \models \varphi(a_1, \ldots, a_n). \]
The proof proceeds by induction on the complexity of \(\varphi\). The key case is the existential quantifier: if \(\varphi = \exists x \, \psi(x, \vec{a})\) and \(V \models \exists x \, \psi(x, \vec{a})\), then pick a witness \(b\). By induction there is a \(\beta\) large enough that the witness \(b\) and all witnesses for subformulas land in \(V_\beta\). A rank argument using the replacement axiom ensures we can find a single \(\beta\) that works simultaneously for all \(a_1, \ldots, a_n \in V_\beta\).
Chapter 13: Constructible Sets (L)
Gödel’s constructible universe \(L\) is the smallest inner model of ZFC. Working in \(L\) allows proofs of the consistency of GCH and AC relative to ZF.
Definition of the Constructible Universe
The
definable power set of a set \(M\) is:
\[ \mathrm{Def}(M) = \{A \subseteq M : A = \{x \in M : M \models \varphi(x, a_1, \ldots, a_n)\} \text{ for some formula } \varphi \text{ and parameters } a_1, \ldots, a_n \in M\}. \]
The
constructible hierarchy \(L\) is defined by:
- \(L_0 = \emptyset\)
- \(L_{\alpha+1} = \mathrm{Def}(L_\alpha)\)
- \(L_\lambda = \bigcup_{\alpha < \lambda} L_\alpha\) for limit ordinals \(\lambda\)
The
constructible universe is \(L = \bigcup_{\alpha \in \mathbf{Ord}} L_\alpha\).
Properties of L
\((L, \in)\) is a model of ZFC. Moreover, \(L\) is an inner model: \(L\) is a transitive proper class containing all ordinals.
Condensation Lemma. If \(M \prec (L_\alpha, \in)\) for some ordinal \(\alpha\), then the Mostowski collapse of \(M\) is \(L_\beta\) for some \(\beta \leq \alpha\).
The Condensation Lemma is the key to proving GCH in \(L\):
Gödel's Theorem. \(L \models \mathsf{GCH}\). That is, in \(L\), for every infinite cardinal \(\kappa\), \(2^\kappa = \kappa^+\).
(Sketch) We show \(L \models 2^{\aleph_\alpha} = \aleph_{\alpha+1}\). Every subset of \(\aleph_\alpha\) in \(L\) is an element of some \(L_\beta\) with \(\beta < \aleph_{\alpha+1}\) (by the Condensation Lemma: any \(M \prec L_\beta\) of size \(\aleph_\alpha\) collapses to an \(L_\gamma\) with \(\gamma \leq \aleph_{\alpha+1}\)). Each \(L_\beta\) for \(\beta < \aleph_{\alpha+1}\) has \(|L_\beta| \leq \aleph_\alpha\) (by an inductive calculation). So \(|\mathcal{P}(\aleph_\alpha)^L| \leq |\aleph_{\alpha+1}| \cdot \aleph_\alpha = \aleph_{\alpha+1}\). Since \(\mathcal{P}(\aleph_\alpha)\) in \(L\) has size at least \(\aleph_{\alpha+1}\) (by Cantor's theorem), we get equality.
\(L \models \mathsf{AC}\). Specifically, in \(L\), every set has a canonical well-ordering definable in \(L\) (the canonical well-ordering of \(L\) orders elements of \(L_{\alpha+1} \setminus L_\alpha\) by the Gödel pairing of their defining formulas and parameters).
Ordinal Definable Sets (OD) and HOD
Beyond \(L\), there are other important inner models defined by definability conditions.
A set \(x\) is ordinal definable (written \(x \in \mathbf{OD}\)) if there exist a formula \(\varphi\) and ordinals \(\alpha_1, \ldots, \alpha_n\) such that \(x = \{y : V \models \varphi(y, \alpha_1, \ldots, \alpha_n)\}\). The class \(\mathbf{OD}\) of all ordinal-definable sets is a definable class.
The class \(\mathbf{HOD}\) (hereditarily ordinal definable sets) consists of all sets \(x\) such that every element of the transitive closure of \(x\) is ordinal definable:
\[ \mathbf{HOD} = \{x \in \mathbf{OD} : \mathrm{tc}(\{x\}) \subseteq \mathbf{OD}\}. \]
\(\mathbf{HOD}\) is an inner model of ZFC. It satisfies the Axiom of Choice (since OD sets can be canonically well-ordered using their defining formulas and ordinal parameters). Moreover, \(L \subseteq \mathbf{HOD} \subseteq V\).
\(\mathbf{HOD}\) is a model of ZF. Furthermore, \(\mathbf{HOD} \models \mathsf{AC}\).
The key point for AC in HOD is that every set in HOD has an ordinal-definable well-ordering: enumerate the defining formulas and parameters by ordinals, and order elements of an HOD set \(x\) by the least ordinal pair \((\varphi, \vec{\alpha})\) that defines them.
Jensen’s Fine Structure Theory
Jensen developed a systematic “fine structure” analysis of \(L\), introducing the Jense hierarchy \(J_\alpha\) (a variant of \(L_\alpha\)) and the \(\Sigma_n\) projecta and master codes. This machinery yields the combinatorial principles:
- \(\Diamond(\kappa)\): There exists a \(\Diamond\)-sequence at \(\kappa\) (holds for all regular uncountable \(\kappa\) in \(L\)).
- \(\square_\kappa\): There exists a coherent sequence of clubs (a global square). Also holds in \(L\).
These principles have major consequences: \(\Diamond \Rightarrow\) Suslin tree exists; \(\square_\kappa\) has implications for cardinal arithmetic and the structure of singular cardinals.
Chapter 14: Forcing and the Independence of CH
Forcing, invented by Paul Cohen in 1963, is the technique for proving that mathematical statements are unprovable from ZFC. It works by constructing new models of set theory — “generic extensions” — by adjoining new sets to an existing model.
The Basic Setup
Let \(M\) be a countable transitive model of ZFC (a ground model). A partial order (or forcing notion) is a set \(\mathbb{P} = (P, \leq)\) with a maximum element \(\mathbf{1}\). Elements of \(\mathbb{P}\) are conditions; we think of stronger conditions as providing more information.
Two conditions \(p, q \in \mathbb{P}\) are compatible if there exists \(r \leq p, q$; otherwise they are incompatible (written \(p \perp q\)). An antichain is a set of pairwise incompatible conditions. \(\mathbb{P}\) satisfies the countable chain condition (ccc) if every antichain is countable.
A set \(D \subseteq \mathbb{P}\) is dense if for every \(p \in \mathbb{P}\) there exists \(q \leq p\) with \(q \in D\). A filter \(G \subseteq \mathbb{P}\) is \(M\)-generic (or simply generic) if it meets every dense set that is an element of \(M\): for every \(D \in M\) that is dense in \(\mathbb{P}\), \(G \cap D \neq \emptyset\).
Rasiowa–Sikorski Lemma. For any countable family \(\{D_n\}_{n \in \omega}\) of dense subsets of \(\mathbb{P}\) and any \(p \in \mathbb{P}\), there exists a filter \(G\) with \(p \in G\) meeting all \(D_n\).
Since \(M\) is countable, \(M\) contains only countably many dense sets, so a generic filter \(G \notin M\) always exists (the generic filter is chosen “outside” \(M\)).
Names and the Generic Extension
A \(\mathbb{P}\)-name is a set \(\tau\) of pairs \((\sigma, p)\) where \(\sigma\) is a \(\mathbb{P}\)-name and \(p \in \mathbb{P}\), defined by \(\in\)-recursion. The generic extension \(M[G]\) is \(\{\tau_G : \tau \in M\}\) where the evaluation \(\tau_G\) is defined recursively: \(\tau_G = \{\sigma_G : \exists p \in G, (\sigma, p) \in \tau\}\).
\(M[G]\) is a transitive model of ZFC. Moreover:
- \(M \subseteq M[G]\) and \(G \in M[G]\).
- \(M[G]\) has the same ordinals as \(M\).
- \(M[G]\) is the smallest transitive model of ZFC containing \(M\) and \(G\).
The Forcing Relation
The
forcing relation \(p \Vdash \varphi\) (read "\(p\) forces \(\varphi\)") is defined in \(M\) for conditions \(p \in \mathbb{P}\) and formulas \(\varphi\) with \(\mathbb{P}\)-names as parameters:
- \(p \Vdash \tau \in \sigma\) iff for some \((\rho, q) \in \sigma\) with \(p \leq q\), \(p \Vdash \tau = \rho\).
- \(p \Vdash \varphi \land \psi\) iff \(p \Vdash \varphi\) and \(p \Vdash \psi\).
- \(p \Vdash \lnot\varphi\) iff no extension \(q \leq p\) forces \(\varphi\).
- \(p \Vdash \exists x \, \varphi(x)\) iff for some name \(\tau\) and some \(q \leq p\), \(q \Vdash \varphi(\tau)\).
Truth Lemma (Forcing Theorem). For any formula \(\varphi\) with \(\mathbb{P}\)-names as parameters and any \(M\)-generic \(G\):
\[ M[G] \models \varphi(\tau^G_1, \ldots, \tau^G_n) \iff \exists p \in G, \, p \Vdash \varphi(\tau_1, \ldots, \tau_n). \]
Moreover, the forcing relation \(\Vdash\) is definable in \(M\).
Cohen Forcing and the Independence of CH
Cohen’s original forcing adds \(\aleph_2\) (in \(M\)) many new subsets of \(\omega\), making \(2^{\aleph_0} \geq \aleph_2\) in the extension.
Cohen forcing \(\mathrm{Add}(\omega, \aleph_2)\) consists of all partial functions \(p: \aleph_2 \times \omega \to 2\) with finite domain, ordered by \(p \leq q\) iff \(p \supseteq q\) (i.e., \(p\) extends \(q\) as a function). The generic filter \(G\) determines a total function \(\bigcup G: \aleph_2 \times \omega \to 2\), i.e., a family of \(\aleph_2\) many subsets of \(\omega\).
Cohen's Independence of CH (1963). If ZFC is consistent, then so is ZFC \(+ \lnot\mathsf{CH}\). In fact, ZFC \(+ 2^{\aleph_0} \geq \aleph_2\) is consistent.
(Sketch) Let \(M\) be a countable transitive model of ZFC + GCH. Let \(\mathbb{P} = \mathrm{Add}(\omega, \aleph_2^M)\). One verifies:
\(\mathbb{P}\) is ccc: Any antichain in \(\mathbb{P}\) is countable. (Two conditions sharing the same finite domain part are compatible.)
Cardinals are preserved: Since \(\mathbb{P}\) is ccc, all cardinals and cofinalities of \(M\) are preserved in \(M[G]\). In particular, \(\aleph_1^{M[G]} = \aleph_1^M\) and \(\aleph_2^{M[G]} = \aleph_2^M\).
\(2^{\aleph_0} \geq \aleph_2\) in \(M[G]\): For each \(\alpha < \aleph_2^M\), the generic adds a new real \(r_\alpha = \{n \in \omega : G(\alpha, n) = 1\}\). These are distinct reals (they differ on the dense set of conditions forcing distinctness). So \(|{\{r_\alpha : \alpha < \aleph_2^M\}}| = \aleph_2\) in \(M[G]\).
Therefore \(M[G] \models \lnot\mathsf{CH}\).
Preserving Cardinals: ccc Forcing
If \(\mathbb{P}\) is ccc, then for any \(M\)-generic \(G\), \(M[G]\) has the same cardinals and cofinalities as \(M\).
Suppose \(\kappa\) is a cardinal in \(M\). If \(\kappa\) were collapsed in \(M[G]\), there would be a surjection \(f: \lambda \to \kappa\) in \(M[G]\) for some \(\lambda < \kappa\). By the Forcing Theorem, some \(p\) forces this; by ccc, we can find a "name" for such a surjection using only countably many antichains, allowing us to reconstruct an injection in \(M\), contradicting \(\kappa\)'s cardinality in \(M\).
Boolean-Valued Models
An alternative approach to forcing uses Boolean-valued models, which avoids the need for a countable ground model.
Let \(\mathbb{B}\) be a complete Boolean algebra. The Boolean-valued universe \(V^\mathbb{B}\) consists of all \(\mathbb{B}\)-valued sets (defined by \(\in\)-recursion analogously to \(\mathbb{P}\)-names). For each formula \(\varphi\), one defines a Boolean value \(\|\varphi\| \in \mathbb{B}\) such that the standard axioms of ZFC all have Boolean value \(\mathbf{1}_\mathbb{B}\).
For any complete Boolean algebra \(\mathbb{B}\), \(V^\mathbb{B} \models \mathsf{ZFC}\) in the sense that all ZFC axioms have Boolean value \(\mathbf{1}\). Moreover, if \(G\) is a generic ultrafilter over \(\mathbb{B}\) then the quotient \(V^\mathbb{B}/G \cong M[G]\).
Other Independence Results
Forcing is used to establish the independence of many statements:
- Suslin’s Hypothesis (SH): Consistent with ZFC (MA + ¬CH implies SH) and its negation is consistent (follows from \(\Diamond\), which holds in \(L\)).
- Souslin’s Problem: The question whether every dense, complete linear order without endpoints satisfying ccc is isomorphic to \(\mathbb{R}\). Independent of ZFC.
- Whitehead Problem: Is every Whitehead group free? Shelah showed it is independent of ZFC.
- The proper forcing axiom (PFA): A strong strengthening of MA, consistent relative to a supercompact cardinal.
Chapter 17: Large Cardinals
Large cardinal axioms assert the existence of cardinals with properties so strong that their existence cannot be proved (or even shown consistent) in ZFC alone. They form a natural well-ordered hierarchy of consistency strength, calibrating the “strength” of mathematical theories.
Inaccessible Cardinals
An uncountable cardinal \(\kappa\) is
strongly inaccessible if:
- \(\kappa\) is regular: \(\mathrm{cf}(\kappa) = \kappa\),
- \(\kappa\) is a strong limit: for all \(\lambda < \kappa\), \(2^\lambda < \kappa\).
A cardinal is
weakly inaccessible if it is regular and a weak limit (i.e., \(\lambda < \kappa \Rightarrow \lambda^+ < \kappa\), i.e., no predecessor).
If \(\kappa\) is strongly inaccessible, then \(V_\kappa \models \mathsf{ZFC}\). In particular, the existence of an inaccessible cardinal implies the consistency of ZFC, so by Gödel's incompleteness theorem, ZFC cannot prove the existence of an inaccessible cardinal.
\(V_\kappa\) is a transitive model of ZFC: regularity ensures replacement holds (images under class-functions don't exceed \(\kappa\)), and the strong limit property ensures power set is well-behaved. The axiom of infinity holds since \(\omega < \kappa\).
Mahlo Cardinals
An inaccessible cardinal \(\kappa\) is a Mahlo cardinal if the set of inaccessible cardinals below \(\kappa\) is stationary in \(\kappa\).
Every Mahlo cardinal \(\kappa\) has \(\kappa\) many inaccessible cardinals below it, and in fact \(V_\kappa \models \text{"there are proper class many inaccessibles."}\)
Weakly Compact Cardinals
An uncountable cardinal \(\kappa\) is weakly compact if for every coloring \(f: [\kappa]^2 \to 2\) there is a homogeneous set of size \(\kappa\). Equivalently, \(\kappa \to (\kappa)^2_2\) in the partition calculus.
The following are equivalent for an inaccessible cardinal \(\kappa\):
- \(\kappa\) is weakly compact.
- \(\kappa\) has the tree property: every \(\kappa\)-tree has a branch of length \(\kappa\).
- \(\kappa\) is \(\Pi^1_1\)-indescribable: for any \(R \subseteq V_\kappa\) and any \(\Pi^1_1\)-sentence \(\varphi\), if \((V_\kappa, \in, R) \models \varphi\), then there exists \(\alpha < \kappa\) with \((V_\alpha, \in, R \cap V_\alpha) \models \varphi\).
- There exists a \(\kappa\)-complete ultrafilter on each set of cardinality \(\kappa\) (the "extension property").
Measurable Cardinals (Revisited)
Every measurable cardinal is weakly compact, hence Mahlo, hence inaccessible. The hierarchy is:
\[ \text{inaccessible} \subset \text{Mahlo} \subset \text{weakly compact} \subset \text{measurable}. \]
Ulam's Theorem. The least measurable cardinal (if it exists) is not the least weakly compact cardinal.
Ramsey and Erdős Cardinals
A cardinal \(\kappa\) is an Erdős cardinal \(\eta(\alpha)\) if \(\kappa \to (\alpha)^{<\omega}_2\) (for every coloring of finite subsets of \(\kappa\) with 2 colors, there is a homogeneous set of order type \(\alpha\)). The cardinal \(\eta(\omega)\) is the least cardinal such that \(\eta(\omega) \to (\omega)^{<\omega}_2\).
The existence of \(\eta(\omega_1)\) implies \(0^\#\) exists, hence \(V \neq L\).
Supercompact Cardinals
A cardinal \(\kappa\) is \(\lambda\)-supercompact for \(\lambda \geq \kappa\) if there exists an elementary embedding \(j: V \to M\) with critical point \(\kappa\) such that \(j(\kappa) > \lambda\) and \(M^\lambda \subseteq M\) (all \(\lambda\)-sequences from \(M\) are in \(M\)). \(\kappa\) is supercompact if it is \(\lambda\)-supercompact for all \(\lambda \geq \kappa\).
Supercompact cardinals are much stronger than measurable: every supercompact cardinal is a limit of measurable cardinals (and in fact of Woodin cardinals, weakly compact cardinals, etc.). Their existence implies, among other things, the consistency of PFA.
Woodin Cardinals
An uncountable cardinal \(\delta\) is a Woodin cardinal if for every function \(f: \delta \to \delta\), there exists a cardinal \(\kappa < \delta\) that is closed under \(f\) and there is an elementary embedding \(j: V \to M\) with critical point \(\kappa\), \(j(f)(\kappa) = f(\kappa)\), and \(V_{j(f)(\kappa)} \subseteq M\).
The existence of infinitely many Woodin cardinals implies the consistency of all \(\mathbf{\Sigma}^1_2\) statements that are consistent, and more: it implies Projective Determinacy (PD), which asserts that all projective sets of reals are determined (every infinite two-player game on natural numbers where the winning condition is projective is determined).
The Large Cardinal Hierarchy
The following schematic shows the hierarchy of large cardinals in increasing order of consistency strength:
| Level | Large Cardinal |
|---|
| 1 | Inaccessible (\(V_\kappa \models \mathsf{ZFC}\)) |
| 2 | Mahlo (stationary many inaccessibles below) |
| 3 | Weakly Compact (\(\kappa \to (\kappa)^2_2\)) |
| 4 | Measurable (non-trivial \(\kappa\)-complete ultrafilter) |
| 5 | Strong (elementary embedding with critical point \(\kappa\)) |
| 6 | Woodin (for every function, many witnesses below \(\delta\)) |
| 7 | Supercompact (\(M^\lambda \subseteq M\)) |
| 8 | Extendible (\(V_{\kappa+\eta} \prec V_{j(\kappa)+\eta}\)) |
| 9 | Huge (\(M^{j(\kappa)} \subseteq M\)) |
| 10 | Rank-into-rank (\(j: V_\lambda \to V_\lambda\)) |
Each level is strictly stronger in consistency strength than all previous levels. At the top, Kunen showed (in ZFC) that there is no elementary embedding \(j: V \to V\) (Kunen’s Inconsistency), placing an absolute upper bound on the large cardinal hierarchy.
Determinacy and Inner Model Theory
Projective Determinacy. Assume infinitely many Woodin cardinals. Then every projective set of reals is determined: for any projective set \(A \subseteq \omega^\omega\), the game \(G_A\) (where two players alternate playing natural numbers and player I wins iff the resulting sequence is in \(A\)) is determined (one player has a winning strategy).
Martin–Steel Theorem. If there exist \(n\) Woodin cardinals with a measurable above them, then all \(\mathbf{\Sigma}^1_{n+1}\) games are determined.
The inner model program seeks to construct, for each large cardinal notion, a canonical model \(L[\vec{E}]\) (built from an extender sequence \(\vec{E}\)) that contains and in some sense “explains” that large cardinal. The program has been carried out through Woodin cardinals and is one of the central programs in contemporary set theory.
Summary and Interconnections
The major themes of graduate set theory are deeply intertwined:
Foundations and Axiomatics (Chapters 1, 6): ZFC provides a rigorous but rich foundation. Regularity stratifies the universe into the cumulative hierarchy.
Ordinals and Cardinals (Chapters 2, 3): The backbone of transfinite mathematics. Ordinals measure order types; cardinals measure sizes. Cofinality and König’s theorem govern cardinal arithmetic.
Combinatorics (Chapters 8, 9): Stationary sets, the club filter, Fodor’s Lemma, and the Diamond and Square principles are the central tools of infinitary combinatorics. They interact with forcing (which can add or destroy stationary sets) and large cardinals (which impose reflection principles that limit combinatorial pathology).
Descriptive Set Theory (Chapters 4, 11): The structure of subsets of the reals is governed by the Borel hierarchy and the projective hierarchy. Definability interacts with large cardinals: under projective determinacy (a consequence of Woodin cardinals), all projective sets enjoy regularity properties.
Inner Models (Chapter 13): \(L\) is the canonical inner model. HOD is the definability-based inner model. The inner model program extends these to accommodate large cardinals.
Forcing (Chapter 14): Forcing constructs outer models, proving independence results. Cohen’s forcing adds new reals, making \(\neg\)CH consistent. The interaction of forcing with stationary sets (preserving or collapsing them) and large cardinals is a central technical concern.
Large Cardinals (Chapters 10, 17): They calibrate consistency strength and impose structure on \(V\). They imply \(V \neq L\) and yield regularity properties for definable sets of reals. The large cardinal hierarchy is linearly ordered by consistency strength, a deep empirical fact about mathematics.
The independence results of Gödel (GCH consistent) and Cohen (CH independent), together with the large cardinal program, show that ZFC is both a powerful and genuinely incomplete foundation for mathematics — a theme that continues to drive research in set theory.
| Result | Statement |
|---|
| Cantor’s Theorem | \(\vert X \vert < \vert \mathcal{P}(X) \vert\) for any set \(X\) |
| Schröder–Bernstein | \(\vert A \vert \leq \vert B \vert\) and \(\vert B \vert \leq \vert A \vert\) implies \(\vert A \vert = \vert B \vert\) |
| König’s Theorem | \(\sum_i \kappa_i < \prod_i \lambda_i\) when \(\kappa_i < \lambda_i\) |
| Fodor’s Lemma | Regressive function on stationary set has stationary fiber |
| Łoś’s Theorem | Ultrapower satisfies same first-order sentences |
| Condensation Lemma | Elementary substructures of \(L_\alpha\) collapse to some \(L_\beta\) |
| Reflection Principle | Every formula true in \(V\) reflects to some \(V_\alpha\) |
| Forcing Theorem | \(M[G] \models \varphi\) iff some \(p \in G\) forces \(\varphi\) |
| Scott’s Theorem | Measurable cardinal implies \(V \neq L\) |
| GCH in L | \(L \models 2^{\aleph_\alpha} = \aleph_{\alpha+1}\) |
Chapter 18: Forcing Axioms
Forcing axioms arise from a simple but powerful idea: rather than adding a single generic object to the universe, we want a principle that guarantees the existence of generic filters for many forcings simultaneously. They are thus “axioms of richness,” asserting that the universe is in some sense saturated. The study of forcing axioms reveals deep connections between combinatorics, topology, and large cardinal strength.
Section 18.1: Martin’s Axiom
Motivation. Recall the Baire Category Theorem: if \(X\) is a compact Hausdorff space and \(\{D_n : n \in \omega\}\) is a countable family of dense open sets, then \(\bigcap_n D_n \neq \emptyset\). Martin’s Axiom (MA) generalizes this from countably many dense sets to fewer than \(2^{\aleph_0}\) many, while restricting to a class of forcing notions called ccc (the countable chain condition).
Definition (Martin's Axiom). A partial order \(\mathbb{P}\) satisfies the countable chain condition (ccc) if every antichain in \(\mathbb{P}\) is countable. Martin's Axiom (\(\text{MA}\)) states: for every ccc partial order \(\mathbb{P}\) and every family \(\mathcal{D}\) of fewer than \(2^{\aleph_0}\) dense subsets of \(\mathbb{P}\), there exists a filter \(G \subseteq \mathbb{P}\) meeting every member of \(\mathcal{D}\).
Note that MA at \(\aleph_0\) (i.e., when \(|\mathcal{D}| \leq \aleph_0\)) is provable in ZFC — this is the content of the Rasiowa–Sikorski lemma. The axiom becomes interesting and independent when we demand this for families of size \(\aleph_1, \aleph_2, \ldots\) up to \(2^{\aleph_0}\). We write \(\text{MA}_\kappa\) for the statement restricted to \(|\mathcal{D}| \leq \kappa\); then MA is \(\text{MA}_{<2^{\aleph_0}}\).
Theorem (Consequences of MA).- Under MA + ¬CH, every set of reals of cardinality less than \(2^{\aleph_0}\) has Lebesgue measure zero and is meager.
- MA implies Suslin's Hypothesis: there is no Suslin line.
- MA implies that any product of ccc topological spaces is ccc (a generalization of Knaster's lemma).
- MA + ¬CH is consistent relative to ZFC.
Proof sketch of (4). Starting from a model of ZFC + GCH, one performs an iterated ccc forcing of length \(\aleph_2\) using finite support iteration. At each stage, one codes a ccc forcing to meet a given family of dense sets. The ccc is preserved at limit stages because the finite support iteration of ccc forcings is ccc. The resulting model satisfies \(2^{\aleph_0} = \aleph_2\) and MA. The consistency of ¬CH is then immediate since \(\aleph_2 > \aleph_1\).
Section 18.2: The Proper Forcing Axiom
MA can be seen as a forcing axiom for ccc forcings. The natural question is: can we extend it to larger classes? The answer requires restricting to forcings that preserve stationary sets in a controlled way.
Definition (Proper forcing). A forcing \(\mathbb{P}\) is proper if for every uncountable regular cardinal \(\theta\), every countable elementary submodel \(M \prec H(\theta)\) with \(\mathbb{P} \in M\), and every \(p \in \mathbb{P} \cap M\), there exists a condition \(q \leq p\) that is \((M, \mathbb{P})\)-generic: for every dense \(D \in M\), the set \(D \cap M\) is predense below \(q\).
Every ccc forcing is proper, and so is every countably closed forcing. Proper forcings do not collapse \(\aleph_1\), making them the natural setting for extending MA.
Definition (PFA). The Proper Forcing Axiom (PFA) states: for every proper partial order \(\mathbb{P}\) and every family \(\mathcal{D}\) of at most \(\aleph_1\) dense subsets of \(\mathbb{P}\), there exists a filter \(G\) meeting every member of \(\mathcal{D}\).
Theorem (Baumgartner). PFA implies that all \(\aleph_1\)-dense sets of reals are order-isomorphic. (A set \(X \subseteq \mathbb{R}\) is \(\aleph_1\)-dense if every open interval meets \(X\) in exactly \(\aleph_1\) points.)
Theorem. PFA implies \(2^{\aleph_0} = \aleph_2\).
Proof sketch. Under PFA, one applies the axiom to a proper forcing that shoots an \(\omega_1\)-club through a stationary set. Combined with structural consequences about \(P_{\aleph_1}(\aleph_2)\) and the fact that PFA implies \(\aleph_2^{\aleph_0} = \aleph_2\), one deduces \(2^{\aleph_0} = \aleph_2\). The argument uses the fact that PFA settles the value of the continuum in a way MA does not.
PFA is consistent relative to the existence of a supercompact cardinal, via an iteration due to Baumgartner.
Section 18.3: Martin’s Maximum
Martin’s Maximum is the strongest possible forcing axiom in a precise sense.
Definition (MM). A forcing \(\mathbb{P}\) is stationary-set-preserving (SSP) if forcing with \(\mathbb{P}\) preserves every stationary subset of \(\omega_1\). Martin's Maximum (MM) states: for every SSP partial order \(\mathbb{P}\) and every family \(\mathcal{D}\) of at most \(\aleph_1\) dense subsets, there exists a filter meeting every member of \(\mathcal{D}\).
Every proper forcing is SSP, so MM implies PFA. Foreman, Magidor, and Shelah proved that MM is consistent relative to a supercompact cardinal (1988), and Woodin showed that a supercompact cardinal directly implies MM after a suitable forcing.
Theorem (Woodin). If there exists a supercompact cardinal, then MM holds in a forcing extension.
Theorem. MM implies \(2^{\aleph_0} = \aleph_2\).
MM is “maximal” in the sense that no forcing axiom for a strictly larger class of forcings is consistent: if \(\mathbb{P}\) does not preserve all stationary subsets of \(\omega_1\), then the forcing axiom for \(\{\mathbb{P}\}\) and \(\aleph_1\) many dense sets is already inconsistent.
Section 18.4: Comparison Table
| Axiom | Class of forcings | Implies \(2^{\aleph_0} = \aleph_2\)? | Consistency strength |
|---|
| MA | ccc | No (any regular \(> \aleph_1\) possible) | ZFC |
| PFA | Proper | Yes | Supercompact cardinal |
| MM | Stationary-set-preserving | Yes | Supercompact cardinal |
Chapter 19: Determinacy and Descriptive Set Theory
Descriptive set theory studies definable sets of reals — those arising through explicit operations starting from open sets. The projective hierarchy organizes these sets by complexity, and the theory of games provides an unexpected tool for their analysis.
Section 19.1: The Projective Hierarchy
Definition (Analytic and projective sets).- A set \(A \subseteq \mathbb{R}\) is analytic (\(\Sigma^1_1\)) if it is a continuous image of a Borel set (equivalently, a Borel image of \(\mathbb{N}^\mathbb{N}\)).
- A set is coanalytic (\(\Pi^1_1\)) if its complement is analytic.
- For \(n \geq 1\): \(\Sigma^1_{n+1}\) is the class of continuous images of \(\Pi^1_n\) sets; \(\Pi^1_{n+1}\) is the class of complements of \(\Sigma^1_{n+1}\) sets; \(\Delta^1_n = \Sigma^1_n \cap \Pi^1_n\).
The union \(\bigcup_n \Sigma^1_n\) is the class of
projective sets.
Theorem (Suslin). \(\Delta^1_1\) = the class of Borel sets.
This elegant characterization shows that Borel sets are precisely those that are both analytic and coanalytic. Every analytic set is Lebesgue measurable, has the Baire property, and has the perfect set property (Suslin, Luzin). The situation for \(\Sigma^1_2\) and beyond is undecidable in ZFC alone.
Theorem (Luzin Separation). If \(A\) and \(B\) are disjoint analytic sets, then there exists a Borel set \(C\) with \(A \subseteq C\) and \(C \cap B = \emptyset\).
Section 19.2: Games and Determinacy
Definition (Gale–Stewart Game). Given \(A \subseteq \omega^\omega\), the Gale–Stewart game \(G(A)\) is played as follows: Players I and II alternate choosing natural numbers \(x_0, x_1, x_2, \ldots\), producing an infinite sequence \(x = (x_0, x_1, \ldots) \in \omega^\omega\). Player I wins if \(x \in A\); Player II wins otherwise. A strategy for a player is a function from finite sequences to \(\omega\). A game is determined if one of the players has a winning strategy.
Definition (AD and Borel Determinacy). The Axiom of Determinacy (AD) states that every game \(G(A)\) for \(A \subseteq \omega^\omega\) is determined. Borel Determinacy (BD) is the restriction to Borel sets \(A\).
Theorem (Martin, 1975). Every Borel game is determined. More precisely, if \(A \subseteq \omega^\omega\) is Borel, then \(G(A)\) is determined.
Proof idea. Martin uses a transfinite "unraveling" argument. For an open set, Player I wins by playing into the open set at the first opportunity, or Player II wins by avoiding it — this is easy. For a set \(A\) at Borel rank \(\alpha\), one constructs an auxiliary game whose payoff set is simpler and whose winning strategies correspond to those for \(G(A)\). This requires the full power set axiom and transfinite induction up to \(\omega_1\).
Borel Determinacy is provable in ZFC. The axiom AD, however, contradicts the Axiom of Choice.
Section 19.3: Projective Determinacy
Definition (PD). Projective Determinacy (PD) states that \(G(A)\) is determined for every projective set \(A \subseteq \omega^\omega\).
While AD is inconsistent with AC (since AC implies the existence of a non-determined game), PD is consistent with ZFC.
Theorem (Martin–Steel, 1989). If there exist infinitely many Woodin cardinals, then PD holds.
Theorem (Consequences of PD). Assuming PD:
- Every projective set is Lebesgue measurable.
- Every projective set has the Baire property.
- Every projective set has the perfect set property (hence is either countable or has cardinality \(2^{\aleph_0}\)).
- The projective hierarchy does not collapse: \(\Sigma^1_n \neq \Pi^1_n\) for all \(n \geq 1\).
Thus, under PD, the projective sets behave as well as the Borel sets — they are measurable and structured. Without large cardinals, the behavior of \(\Sigma^1_2\) sets is already undecidable.
Section 19.4: The Full Axiom of Determinacy
Theorem (Consequences of AD). Assuming AD (in the context where AC fails):
- Every set of reals is Lebesgue measurable and has the Baire property.
- \(\aleph_1\) is a measurable cardinal.
- AD implies DC (Dependent Choice) but not full AC.
- The club filter on \(\omega_1\) is an ultrafilter.
Chapter 20: Cardinal Characteristics of the Continuum
Section 20.1: Motivation
We know that \(2^{\aleph_0}\) can be many things — \(\aleph_1\), \(\aleph_2\), \(\aleph_{\omega_1}\), and so on. But beyond asking what \(2^{\aleph_0}\) equals, we can ask finer questions: how complex is the combinatorial structure of \(\mathbb{R}\)? Cardinal characteristics of the continuum are cardinal numbers, definable from the reals, that measure specific aspects of this complexity. Each lies between \(\aleph_1\) and \(2^{\aleph_0}\) inclusive, and they can be separated from each other by forcing.
Section 20.2: Characteristics of Baire Space
We work in \(\omega^\omega\), ordered by eventual domination: \(f \leq^* g\) iff \(f(n) \leq g(n)\) for all but finitely many \(n\).
Definition.- The bounding number \(\mathfrak{b}\) is the smallest cardinality of a family \(\mathcal{F} \subseteq \omega^\omega\) that is unbounded: no single \(g \in \omega^\omega\) satisfies \(f \leq^* g\) for all \(f \in \mathcal{F}\).
- The dominating number \(\mathfrak{d}\) is the smallest cardinality of a dominating family \(\mathcal{F}\): for every \(g \in \omega^\omega\), there exists \(f \in \mathcal{F}\) with \(g \leq^* f\).
- The splitting number \(\mathfrak{s}\) is the smallest cardinality of a family \(\mathcal{S} \subseteq [\omega]^\omega\) such that for every \(A \in [\omega]^\omega\), some \(S \in \mathcal{S}\) splits \(A\): both \(A \cap S\) and \(A \setminus S\) are infinite.
- The reaping number \(\mathfrak{r}\) is the smallest cardinality of a family \(\mathcal{R} \subseteq [\omega]^\omega\) such that no single \(A \in [\omega]^\omega\) splits every member of \(\mathcal{R}\).
One can show \(\aleph_1 \leq \mathfrak{b} \leq \mathfrak{d} \leq 2^{\aleph_0}\) and \(\mathfrak{b} \leq \mathfrak{s}\) in ZFC.
Definition (\(\mathfrak{p}\) and \(\mathfrak{t}\)).- A family \(\mathcal{F} \subseteq [\omega]^\omega\) has the strong finite intersection property (sfip) if every finite subfamily has infinite intersection.
- A pseudo-intersection of \(\mathcal{F}\) is an \(A \in [\omega]^\omega\) with \(A \subseteq^* F\) for all \(F \in \mathcal{F}\).
- \(\mathfrak{p}\) is the smallest cardinality of a family with sfip but no pseudo-intersection.
- A tower is a \(\subseteq^*\)-decreasing sequence in \([\omega]^\omega\) with no pseudo-intersection. \(\mathfrak{t}\) is the smallest length of a tower.
Theorem. \(\aleph_1 \leq \mathfrak{p} \leq \mathfrak{t} \leq \mathfrak{b}\) in ZFC. Moreover (Malliaris–Shelah, 2016), \(\mathfrak{p} = \mathfrak{t}\).
Proof sketch (\(\mathfrak{p} \leq \mathfrak{t}\)). Every tower is a family with sfip but no pseudo-intersection (since the tower itself witnesses the failure). Thus the minimum tower length is at least the minimum size of an sfip family with no pseudo-intersection, giving \(\mathfrak{p} \leq \mathfrak{t}\). The equality \(\mathfrak{p} = \mathfrak{t}\), proved by Malliaris and Shelah using model-theoretic methods involving Keisler's order, resolved a decades-old open problem.
Section 20.3: Characteristics of the Null and Meager Ideals
Let \(\mathcal{N}\) be the ideal of Lebesgue null sets and \(\mathcal{M}\) the ideal of meager sets on \(\mathbb{R}\).
Definition (Cichoń characteristics). For an ideal \(\mathcal{I}\) on a set \(X\):
- \(\text{add}(\mathcal{I})\): smallest number of sets in \(\mathcal{I}\) whose union is not in \(\mathcal{I}\).
- \(\text{cov}(\mathcal{I})\): smallest number of sets in \(\mathcal{I}\) whose union is all of \(X\).
- \(\text{non}(\mathcal{I})\): smallest cardinality of a set not in \(\mathcal{I}\).
- \(\text{cof}(\mathcal{I})\): cofinality of \(\mathcal{I}\) under \(\subseteq\) (smallest cardinality of a cofinal subfamily).
These give four characteristics each for \(\mathcal{N}\) and \(\mathcal{M}\), plus \(\mathfrak{b}\) and \(\mathfrak{d}\), making ten in total in the Cichoń diagram.
Section 20.4: The Cichoń Diagram
The ten characteristics are related by the following inequalities, all provable in ZFC:
\[
\begin{array}{ccccc}
\text{add}(\mathcal{N}) & \leq & \text{cov}(\mathcal{N}) & \leq & \text{non}(\mathcal{M}) \\
\downarrow & & & & \downarrow \\
\mathfrak{b} & & & & \mathfrak{d} \\
\downarrow & & & & \downarrow \\
\text{add}(\mathcal{M}) & \leq & \text{cov}(\mathcal{M}) & \leq & \text{non}(\mathcal{N}) \\
\end{array}
\qquad \leq \quad \text{cof}(\mathcal{N}) \leq 2^{\aleph_0}
\]
More precisely, with \(\aleph_1\) on the left and \(2^{\aleph_0}\) on the right, all arrows go left-to-right or top-to-bottom, and in every model of ZFC all displayed inequalities hold. A key result is that \(\text{add}(\mathcal{M}) = \min(\mathfrak{b}, \text{cov}(\mathcal{M}))\) and \(\text{cof}(\mathcal{M}) = \max(\mathfrak{d}, \text{non}(\mathcal{M}))\).
Theorem (Consistency of separations). By forcing, one can produce models where:
- \(\mathfrak{b} < \mathfrak{d}\) (e.g., using a finite support iteration of Hechler forcing).
- \(\text{cov}(\mathcal{N}) < \text{non}(\mathcal{N})\) (random real forcing).
- All ten characteristics are pairwise distinct (Goldstern–Kellner–Shelah).
Chapter 21: PCF Theory and Singular Cardinal Arithmetic
Section 21.1: Motivation — Silver’s Theorem and Beyond
Cardinal arithmetic is wildly undecidable for regular cardinals: by Easton’s theorem, \(2^{\aleph_\alpha}\) can be almost anything for regular \(\aleph_\alpha\). But singular cardinals are different. A remarkable theorem of Silver shows that GCH cannot first fail at a singular cardinal of uncountable cofinality.
Theorem (Silver, 1974). If \(\kappa\) is a singular cardinal of uncountable cofinality, and \(2^\lambda = \lambda^+\) for all infinite cardinals \(\lambda < \kappa\), then \(2^\kappa = \kappa^+\).
The analogous result for cofinality \(\omega\) is false: Magidor showed that starting from a supercompact cardinal, GCH can fail at \(\aleph_\omega\). But even then, how large can \(2^{\aleph_\omega}\) be?
Section 21.2: Shelah’s Bound
Theorem (Shelah). If \(2^{\aleph_n} < \aleph_\omega\) for all \(n < \omega\), then \(2^{\aleph_\omega} < \aleph_{\omega_4}\). In particular, \(2^{\aleph_\omega} < \aleph_{\omega_4}\) is provable in ZFC (given GCH below \(\aleph_\omega\)).
This is a ZFC result — no large cardinals. It shows that even though \(2^{\aleph_\omega}\) can exceed \(\aleph_{\omega+1}\), it cannot be arbitrarily large: it is bounded below \(\aleph_{\omega_4}\). The proof uses Shelah’s PCF theory.
Section 21.3: PCF Theory
Let \(A\) be a set of regular cardinals with \(|A| < \min(A)\). The key object is the product \(\prod A = \prod_{\lambda \in A} \lambda\) ordered by eventual domination: \(f <^* g\) iff \(f(\lambda) < g(\lambda)\) for all but finitely many (or more generally, all but boundedly many) \(\lambda \in A\).
Definition (\(\text{pcf}(A)\)). The PCF (possible cofinalities) of \(A\) is
\[
\text{pcf}(A) = \left\{ \text{cf}\!\left(\prod A / D\right) : D \text{ is an ultrafilter on } A \right\}.
\]
Thus \(\text{pcf}(A)\) is the set of all regular cardinals that appear as the cofinality of some ultrapower of \(\prod A\).
Theorem (Basic PCF facts).- \(\min(A) \leq \text{pcf}(A) \subseteq \left[\min(A), \max\text{pcf}(A)\right]\) and \(\max\text{pcf}(A) = \text{cf}(\prod A, <^*)\).
- \(|\text{pcf}(A)| \leq 2^{|A|}\).
- For each \(\lambda \in \text{pcf}(A)\), there is a generator \(B_\lambda \subseteq A\) such that \(\lambda \in \text{pcf}(B_\lambda)\) and \(\lambda \notin \text{pcf}(B_\lambda \setminus \{b\})\) for all \(b \in B_\lambda\). The generators \(\{B_\lambda : \lambda \in \text{pcf}(A)\}\) form a basis for \(\text{pcf}(A)\).
Theorem (Shelah's compactness). If \(\lambda \in \text{pcf}(A)\) and \(B \subseteq A\) is such that \(\text{pcf}(B) \not\ni \lambda\) for every finite \(B' \subsetneq B\), then \(\lambda \in \text{pcf}(B)\). In other words, if \(\lambda\) is in \(\text{pcf}\) of a set, it is "witnessed compactly."
The key open question is whether \(|\text{pcf}(\{\aleph_1, \ldots, \aleph_\omega\})| \leq \aleph_4\). Shelah conjectures this is provable in ZFC; it follows from his bound on \(2^{\aleph_\omega}\).
Section 21.4: The Galvin–Hajnal Theorem and SCH
Theorem (Galvin–Hajnal). Let \(\kappa\) be a singular cardinal of uncountable cofinality. If \(2^\lambda < \kappa\) for all \(\lambda < \kappa\), then \(\kappa^{\text{cf}(\kappa)} < \aleph_{(|\kappa|^+)^+}\).
This bounds cardinal exponentiation at singular cardinals of uncountable cofinality in terms of smaller cardinals, generalizing Silver’s theorem.
Definition (SCH). The Singular Cardinal Hypothesis (SCH) states: for every singular cardinal \(\kappa\), if \(2^{\text{cf}(\kappa)} < \kappa\), then \(\kappa^{\text{cf}(\kappa)} = \kappa^+\).
SCH follows from GCH, and also from the existence of large cardinals in certain senses. However:
Theorem (Magidor). Starting from a supercompact cardinal, it is consistent that SCH fails at \(\aleph_\omega\): specifically, one can have \(2^{\aleph_n} = \aleph_{n+1}\) for all \(n\) but \(2^{\aleph_\omega} = \aleph_{\omega+2}\).
Theorem (Shelah–Woodin). If SCH fails, then there exist inner models with large cardinals. More precisely, the failure of SCH at any singular cardinal implies the existence of inner models with measurable cardinals of high Mitchell order.
