Large cardinals · The Lumenary

Lens

MotivationH

Climbing past ZFC

Gödel's second incompleteness theorem says that ZFC, if consistent, cannot prove its own consistency (see incompleteness). So there are true arithmetical statements — $\mathrm{Con}(\mathsf{ZFC})$ among them, if ZFC is consistent — that ZFC cannot reach. How can we strengthen ZFC in a principled way? One natural answer is to assert that the universe of sets is large: that there is a cardinal $\kappa$ so far beyond the cardinals below it that the sets of rank below $\kappa$ form a universe of their own, a model of all of ZFC. Such a $\kappa$ is an inaccessible cardinal, and the axiom "an inaccessible cardinal exists" proves $\mathrm{Con}(\mathsf{ZFC})$ .

A second road starts in analysis. In 1930 Stanisław Ulam, following a question of Stefan Banach, asked whether some set carries a countably additive measure defined on all of its subsets, vanishing on points. His analysis produced the measurable cardinals — cardinals $\kappa$ carrying a two-valued measure on all their subsets that is $\kappa$ -additive: a union of fewer than $\kappa$ null sets is null. Thirty years later Dana Scott showed that a measurable cardinal is incompatible with Gödel's constructible universe $L$ , and Jerome Keisler showed that measurability is equivalent to the existence of an elementary embedding of the universe into part of itself.

These axioms — and the much stronger ones that followed — are not about large numbers for their own sake. They form a hierarchy that calibrates the consistency strength of mathematical theories, and they settle questions about sets of real numbers that ZFC leaves open. This lesson builds on axiomatic set theory (the hierarchy $V_\alpha$ , cofinality, $L$ ) and forcing (relative consistency).

IntuitionH

Universes inside the universe

The cumulative hierarchy $V_0 = \varnothing$ , $V_{\alpha+1} = \mathcal P(V_\alpha)$ , $V_\lambda = \bigcup_{\alpha < \lambda} V_\alpha$ builds every set in stages. Look at the first infinite stage. $V_\omega$ , the set of hereditarily finite sets, is closed under every operation of finite set theory — pairs, unions, power sets, images under functions — because $\omega$ cannot be reached from below by them: finite unions of finite sets are finite, and power sets of finite sets are finite. $V_\omega$ satisfies every axiom of ZFC except Infinity.

An inaccessible cardinal is an uncountable $\kappa$ with the same two properties: a union of fewer than $\kappa$ sets each of size less than $\kappa$ has size less than $\kappa$ (regularity), and the power set of a set of size less than $\kappa$ has size less than $\kappa$ (strong limit). Then $V_\kappa$ is closed under all the operations of ZFC, and contains $\omega$ too: a universe inside the universe.

The cumulative hierarchy $V$, with ordinals (Ord) running up the middle. The stage $V_\omega$ of hereditarily finite sets satisfies ZFC without Infinity; if $\kappa$ is inaccessible, the stage $V_\kappa$ satisfies all of ZFC.

A measurable cardinal carries a notion of "almost all subsets of $\kappa$ " that is extraordinarily robust: every subset of $\kappa$ either contains almost all of $\kappa$ or misses almost all of it, and the intersection of fewer than $\kappa$ "large" sets is still large. Using it one can take an ultrapower of the whole universe and obtain an elementary embedding $j : V \to M$ — a map that preserves every statement of set theory — which moves $\kappa$ and nothing below it. The universe looks like a proper part of itself. Stronger large cardinals demand that $M$ be closer and closer to $V$ ; the limit, $M = V$ , is inconsistent with the axiom of choice (Kunen, 1971).

DefinitionsH

Definitions

Cardinals are initial ordinals, and $\operatorname{cf}(\kappa)$ is the least order type of a cofinal subset of $\kappa$ .

Definition— regular, singular, strong limit

An infinite cardinal $\kappa$ is regular if $\operatorname{cf}(\kappa) = \kappa$ , equivalently if $\kappa$ is not a union of fewer than $\kappa$ sets each of size less than $\kappa$ ; otherwise it is singular. It is a strong limit if $2^\lambda < \kappa$ for every cardinal $\lambda < \kappa$ .

Definition— inaccessible cardinal

$\kappa$ is (strongly) inaccessible if it is uncountable, regular, and a strong limit. It is weakly inaccessible if it is uncountable, regular, and a limit cardinal ( $\lambda^+ < \kappa$ for all $\lambda < \kappa$ ). Under GCH the two notions coincide.

Definition— κ-complete ultrafilter, measurable cardinal

An ultrafilter $U$ on a set $X$ is $\kappa$ -complete if $\bigcap \mathcal S \in U$ whenever $\mathcal S \subseteq U$ and $|\mathcal S| < \kappa$ , and non-principal if it contains no singleton. An uncountable cardinal $\kappa$ is measurable if there is a $\kappa$ -complete non-principal ultrafilter on $\kappa$ . (The word "uncountable" matters: every ultrafilter is $\aleph_0$ -complete, since it is closed under finite intersections, and non-principal ultrafilters on $\omega$ exist by the ultrafilter lemma.)

Definition— elementary embedding, critical point

For classes $M, N$ , a map $j : M \to N$ is an elementary embedding if $M \models \varphi(a_1, \dots, a_n) \iff N \models \varphi(j(a_1), \dots, j(a_n))$ for every formula $\varphi$ and all $a_i \in M$ . If $j$ is not the identity on ordinals, its critical point $\operatorname{crit}(j)$ is the least ordinal $\alpha$ with $j(\alpha) \ne \alpha$ (then $j(\alpha) > \alpha$ ).

Definition— consistency strength

A theory $T$ has at least the consistency strength of $S$ if $\mathrm{Con}(T) \to \mathrm{Con}(S)$ is provable in a weak base theory (for instance Peano arithmetic, or ZFC); they are equiconsistent if each has at least the strength of the other, and $T$ is strictly stronger if moreover $\mathrm{Con}(S) \to \mathrm{Con}(T)$ is not provable.

Worked examplesH

Examples and non-examples

Example— Small cardinals that fail

$\omega$ is regular and a strong limit, but countable. It is the finite model of inaccessibility: $V_\omega \models \mathsf{ZFC} - \text{Infinity} + \neg\text{Infinity}$ .
$\aleph_1$ is regular (a countable union of countable sets is countable, using choice) but not a limit cardinal.
$\aleph_\omega = \sup_n \aleph_n$ is a limit cardinal but singular: $\operatorname{cf}(\aleph_\omega) = \omega$ . Likewise $\beth_\omega = \sup_n \beth_n$ is a singular strong limit.
Even the least cardinal $\kappa$ with $\kappa = \aleph_\kappa$ — the limit of $\omega, \aleph_\omega, \aleph_{\aleph_\omega}, \dots$ — is singular, of cofinality $\omega$ . Being "very big" is not the point; an inaccessible satisfies $\kappa = \aleph_\kappa = \beth_\kappa$ and is regular, and ZFC cannot prove that such a cardinal exists.

Example— Ultrafilters

For $a \in X$ , the principal ultrafilter $\{A \subseteq X : a \in A\}$ is $\kappa$ -complete for every $\kappa$ . On a finite set every ultrafilter is principal. On $\omega$ , a non-principal ultrafilter contains every cofinite set, hence each $\{n\}^c$ ; the intersection of these countably many sets is empty, so it is not countably complete. More generally (Lemma 4 below), a $\kappa$ -complete non-principal ultrafilter contains only sets of size at least $\kappa$ — so it can live only on a set of size at least $\kappa$ .

Example— Universes in Lean

In Lean's type theory, Type u is a type in Type (u+1), and Mathlib proves that its cardinality, Cardinal.univ.{u, u+1}, is inaccessible from the point of view of Type (u+1). So Lean's foundations prove the existence of inaccessible cardinals — which ZFC cannot do (Theorem 3). This is no paradox: Lean's type theory, with its hierarchy of universes, is a stronger theory than ZFC.

ProofH

Inaccessible cardinals: a model of ZFC, and why ZFC cannot find one

Theorem— Lemma 1

If $\kappa$ is inaccessible then $|V_\alpha| < \kappa$ for every $\alpha < \kappa$ , and $|V_\kappa| = \kappa$ .

Proof

By induction on $\alpha < \kappa$ . $|V_0| = 0$ . If $|V_\alpha| < \kappa$ then $|V_{\alpha+1}| = 2^{|V_\alpha|} < \kappa$ because $\kappa$ is a strong limit. If $\lambda < \kappa$ is a limit and $|V_\alpha| < \kappa$ for all $\alpha < \lambda$ , then $V_\lambda$ is a union of $|\lambda| < \kappa$ sets each of size less than $\kappa$ , so $|V_\lambda| < \kappa$ by regularity. Finally $V_\kappa = \bigcup_{\alpha < \kappa} V_\alpha$ has size at most $\kappa \cdot \kappa = \kappa$ , and at least $\kappa$ since it contains every ordinal $\alpha < \kappa$ .

∎

Theorem— Theorem 2 (Zermelo 1930)

If $\kappa$ is inaccessible, then $(V_\kappa, \in) \models \mathsf{ZFC}$ .

Proof

$V_\kappa$ is transitive, so $\Delta_0$ formulas are absolute between $V_\kappa$ and $V$ ; and if $x \in V_\kappa$ , every subset of $x$ is in $V_\kappa$ (if $x \in V_{\alpha+1}$ then $x \subseteq V_\alpha$ , so each $y \subseteq x$ is in $V_{\alpha+1}$ ). We check the axioms.

Extensionality and Foundation hold in every transitive class. Pairing, Union, Power Set: if $x, y \in V_\alpha$ with $\alpha < \kappa$ , then $\{x, y\} \in V_{\alpha+1}$ , $\bigcup x \in V_\alpha$ , and $\mathcal P(x) \in V_{\alpha+1}$ ; these lie in $V_\kappa$ because $\kappa$ is a limit ordinal, and by the remark above $V_\kappa$ computes $\mathcal P(x)$ correctly. Infinity: $\omega \in V_{\omega+1} \subseteq V_\kappa$ as $\kappa > \omega$ . Separation: for any formula $\varphi$ and parameters in $V_\kappa$ , $\{y \in x : V_\kappa \models \varphi(y)\}$ is a subset of $x \in V_\kappa$ , so it is in $V_\kappa$ . Choice: a well-ordering $R$ of $x \in V_\alpha$ exists in $V$ and is a subset of $x \times x \in V_{\alpha+3}$ ; being a well-ordering is absolute for $V_\kappa$ because every subset of $x$ is in $V_\kappa$ .

Replacement is where regularity enters. Suppose $V_\kappa \models$ " $F$ is a function with domain $x$ ", where $F$ is defined over $V_\kappa$ by a formula with parameters. Then $F[x] = \{F(y) : y \in x\} \subseteq V_\kappa$ , and $|x| < \kappa$ by Lemma 1. The ranks $\operatorname{rank}(F(y)) + 1$ , $y \in x$ , are fewer than $\kappa$ ordinals below $\kappa$ , so by regularity their supremum $\beta$ is below $\kappa$ , and $F[x] \subseteq V_\beta$ gives $F[x] \in V_{\beta+1} \subseteq V_\kappa$ .

∎

Both hypotheses are needed. For the singular strong limit $\beth_\omega$ (viewed as an ordinal), the map $n \mapsto \beth_n$ is definable in $V_{\beth_\omega}$ , which computes power sets and cardinalities correctly, but its range is cofinal in $\beth_\omega$ , so it is not an element: Replacement fails. And if $\kappa$ is regular but not a strong limit, then some $\mathcal P(\lambda)$ with $\lambda < \kappa$ has size at least $\kappa$ ; a well-ordering of $\mathcal P(\lambda)$ of length at least $\kappa$ lies in $V_\kappa$ , and Replacement, which would collapse it onto an ordinal of $V_\kappa$ , fails again.

Theorem— Theorem 3

If ZFC is consistent, then ZFC does not prove that an inaccessible cardinal exists. Moreover, if ZFC + "there is an inaccessible cardinal" is consistent, then ZFC does not even prove $\mathrm{Con}(\mathsf{ZFC}) \to \mathrm{Con}(\mathsf{ZFC} + \text{there is an inaccessible})$ .

Proof

Write IC for "there is an inaccessible cardinal". Theorem 2 is a theorem of ZFC, about the formalised satisfaction relation for set-sized structures: $\mathsf{ZFC} \vdash$ "if $\kappa$ is inaccessible then $V_\kappa \models \mathsf{ZFC}$ ". And ZFC proves that a theory with a set model is consistent. Hence $\mathsf{ZFC} + \mathrm{IC} \vdash \mathrm{Con}(\mathsf{ZFC})$ .

If $\mathsf{ZFC} \vdash \mathrm{IC}$ , then $\mathsf{ZFC} \vdash \mathrm{Con}(\mathsf{ZFC})$ , and by Gödel's second incompleteness theorem ZFC is inconsistent. If $\mathsf{ZFC} \vdash \mathrm{Con}(\mathsf{ZFC}) \to \mathrm{Con}(\mathsf{ZFC} + \mathrm{IC})$ , then $\mathsf{ZFC} + \mathrm{IC} \vdash \mathrm{Con}(\mathsf{ZFC} + \mathrm{IC})$ , and by the second incompleteness theorem, now for the theory $\mathsf{ZFC} + \mathrm{IC}$ , that theory is inconsistent.

∎

A second, more set-theoretic argument: if $\kappa$ is the least inaccessible, then $V_\kappa \models \mathsf{ZFC} + \neg\mathrm{IC}$ , because for $\lambda < \kappa$ , " $\lambda$ is inaccessible" is absolute between $V_\kappa$ and $V$ (all subsets of $\lambda$ and all functions from smaller ordinals into $\lambda$ lie in $V_\kappa$ ). So ZFC + IC proves that ZFC + $\neg$ IC has a model; and IC cannot be a theorem of ZFC, for then $V_\kappa$ , a model of ZFC, would satisfy both IC and $\neg$ IC. Theorem 3 also says that ZFC + IC is strictly stronger than ZFC in consistency strength (if it is consistent at all). Its consistency cannot be established by any proof that ZFC can formalise; belief in it rests on other evidence — the coherence of the theory that has grown from it, the absence of contradictions after a century of intense study, and the way it fits with everything else we know.

ProofH

Measurable cardinals, ultrapowers and embeddings

Theorem— Lemma 4

Let $U$ be a $\kappa$ -complete non-principal ultrafilter on a set $X$ . Then every $A \in U$ has $|A| \ge \kappa$ . In particular, a $\kappa$ -complete ultrafilter on a set of size less than $\kappa$ is principal.

Proof

Suppose $A \in U$ and $|A| < \kappa$ . For each $a \in A$ , $\{a\} \notin U$ , so $X \setminus \{a\} \in U$ . These fewer than $\kappa$ sets have intersection $X \setminus A$ , which is therefore in $U$ ; but then $\varnothing = A \cap (X \setminus A) \in U$ , which is impossible.

∎

Theorem— Theorem 5 (Ulam 1930)

Every measurable cardinal is inaccessible.

Proof

Let $U$ be a $\kappa$ -complete non-principal ultrafilter on $\kappa$ ; by definition $\kappa$ is uncountable.

Strong limit. Suppose $\lambda < \kappa \le 2^\lambda$ . Then there is an injection $g$ from $\kappa$ into $\mathcal P(\lambda)$ . For each $i < \lambda$ , exactly one of $\{\alpha : i \in g(\alpha)\}$ and its complement is in $U$ ; call it $Y_i$ . The intersection $Y = \bigcap_{i < \lambda} Y_i$ of these $\lambda < \kappa$ sets is in $U$ . If $\alpha, \beta \in Y$ then for every $i$ , $i \in g(\alpha) \iff i \in g(\beta)$ , so $g(\alpha) = g(\beta)$ and $\alpha = \beta$ . Thus $|Y| \le 1 < \kappa$ , contradicting Lemma 4.

Regular. If $\operatorname{cf}(\kappa) < \kappa$ , there is a cofinal set $C \subseteq \kappa$ with $|C| < \kappa$ , so $\kappa = \bigcup_{\gamma \in C} [0, \gamma]$ , a union of fewer than $\kappa$ sets each of size less than $\kappa$ . By Lemma 4 none of these sets is in $U$ , so all their complements are; by $\kappa$ -completeness so is the intersection of the complements, which is empty. Contradiction.

∎

Both proofs are formalised in Lean below. To go further we need the ultrapower of the universe.

Ultrapowers. Let $U$ be a countably complete ultrafilter on $\kappa$ . For functions $f, g$ with domain $\kappa$ (classes of them, cut down to sets by Scott's trick of taking only the elements of least rank) put $f =_U g$ iff $\{\alpha : f(\alpha) = g(\alpha)\} \in U$ and $f \in_U g$ iff $\{\alpha : f(\alpha) \in g(\alpha)\} \in U$ . Łoś's theorem says that the resulting structure $\mathrm{Ult}(V, U)$ satisfies $\varphi([f_1], \dots, [f_n])$ if and only if $\{\alpha : \varphi(f_1(\alpha), \dots, f_n(\alpha))\} \in U$ . Countable completeness makes $\in_U$ well-founded (a descending sequence $[f_{n+1}] \in_U [f_n]$ would give a single $\alpha$ in countably many $U$ -sets with $f_{n+1}(\alpha) \in f_n(\alpha)$ for all $n$ ), so $\mathrm{Ult}(V, U)$ collapses to a transitive class $M$ , and $j_U(x) = [\text{constant function } x]$ is an elementary embedding $j_U : V \to M$ , by Łoś's theorem. If $U$ is $\kappa$ -complete and non-principal, then $j_U(\alpha) = \alpha$ for $\alpha < \kappa$ and $j_U(\kappa) > \kappa$ .

Theorem— Theorem 6 (Keisler, Scott)

$\kappa$ is measurable if and only if there is an elementary embedding $j : V \to M$ , with $M$ a transitive class, whose critical point is $\kappa$ .

Proof

( $\Rightarrow$ ) is the ultrapower construction just described. ( $\Leftarrow$ ) Given $j$ , let $U = \{X \subseteq \kappa : \kappa \in j(X)\}$ . Since $j(\kappa) > \kappa$ , $\kappa \in j(\kappa)$ , so $\kappa \in U$ ; and for $X \subseteq \kappa$ , $j(X) \cup j(\kappa \setminus X) = j(\kappa)$ , so exactly one of $X$ , $\kappa \setminus X$ is in $U$ . Intersections: if $\gamma < \kappa$ and $\langle X_\xi : \xi < \gamma \rangle$ is a sequence of members of $U$ , then by elementarity $j(\langle X_\xi : \xi < \gamma \rangle)$ is a sequence of length $j(\gamma) = \gamma$ whose $\xi$ -th term is $j(X_\xi)$ (as $j(\xi) = \xi$ ), so $j(\bigcap_\xi X_\xi) = \bigcap_\xi j(X_\xi) \ni \kappa$ . Upward closure is similar, so $U$ is a $\kappa$ -complete ultrafilter. Finally, for $\alpha < \kappa$ , $j(\{\alpha\}) = \{j(\alpha)\} = \{\alpha\} \not\ni \kappa$ , so $U$ is non-principal.

∎

The two directions fit together. Given $j$ with critical point $\kappa$ and the derived ultrafilter $U$ , the map $k([f]_U) = j(f)(\kappa)$ is a well-defined elementary embedding of the ultrapower into $M$ , and $k \circ j_U = j$ : every embedding with critical point $\kappa$ factors through the ultrapower by its own derived measure.

An embedding

j

with critical point

\kappa

, its derived measure

U = \{X \subseteq \kappa : \kappa \in j(X)\}

, and the factor map

k([f]_U) = j(f)(\kappa)

: the triangle commutes,

k \circ j_U = j

Theorem— Theorem 7 (Scott 1961)

If there is a measurable cardinal, then $V \ne L$ .

Proof

Suppose $V = L$ and let $\kappa$ be the least measurable cardinal. Take $j : V \to M$ with critical point $\kappa$ . Since $j(\alpha) \ge \alpha$ for every ordinal, $M$ contains all ordinals; it is a transitive class model of ZF, and $L$ is the smallest such, so $L \subseteq M \subseteq V = L$ and $M = V$ . By elementarity, $M \models$ " $j(\kappa)$ is the least measurable cardinal", that is, $V$ believes it; so $j(\kappa) = \kappa$ , contradicting $j(\kappa) > \kappa$ .

∎

The same ultrapower shows that a measurable cardinal $\kappa$ is a limit of inaccessible cardinals: $M$ contains every subset of $\kappa$ and every function from a smaller ordinal into $\kappa$ , so $M \models$ " $\kappa$ is inaccessible"; if $U$ is chosen normal, $\kappa = [\mathrm{id}]_U$ , and Łoś's theorem gives $\{\alpha < \kappa : \alpha \text{ is inaccessible}\} \in U$ — a set of size $\kappa$ by Lemma 4. In particular, the least measurable is much larger than the least inaccessible, as Tarski, Keisler and Hanf showed in the early 1960s.

ExplanationH

The hierarchy, and what it decides

Large cardinal axioms are naturally ordered by consistency strength. Some landmarks, in increasing order of consistency strength:

Axiom	Definition, informally	Some consequences
inaccessible	uncountable regular strong limit	$V_\kappa \models \mathsf{ZFC}$ ; Grothendieck universes
Mahlo	the inaccessibles below $\kappa$ form a stationary set	reflection of inaccessibility
weakly compact	$\kappa \to (\kappa)^2_2$ : every 2-colouring of pairs has a homogeneous set of size $\kappa$	compactness for infinitary languages $L_{\kappa\kappa}$
measurable	$\kappa$ -complete non-principal ultrafilter; $j : V \to M$ with critical point $\kappa$	$V \ne L$ (Scott); analytic games determined (Martin 1970)
strong, Woodin	embeddings with $V_\lambda \subseteq M$ , for many $\lambda$	infinitely many Woodin cardinals give projective determinacy (Martin and Steel 1989)
supercompact	for every $\lambda$ , an embedding with $M$ closed under $\lambda$ -sequences	consistency of the proper forcing axiom (Baumgartner)
huge, rank-into-rank	$j : V_\lambda \to V_\lambda$ (axiom I3) and beyond	Laver's free left-distributive algebras

Beyond the top lies inconsistency: Kunen (1971) proved that, with the axiom of choice, there is no non-trivial elementary embedding $j : V \to V$ .

What is known. Large cardinals settle the theory of definable sets of reals level by level: a measurable cardinal implies that analytic games are determined (Martin, 1970) and that every $\boldsymbol\Sigma^1_2$ set is Lebesgue measurable (Solovay); infinitely many Woodin cardinals imply projective determinacy and with it the regularity of all projective sets (Martin–Steel; see descriptive set theory). Many natural statements turn out equiconsistent with a large cardinal: "every set of reals is Lebesgue measurable" (with dependent choice instead of choice) with an inaccessible (Solovay 1970; Shelah 1984); "there is a real-valued measurable cardinal" with a measurable (Solovay 1971); the axiom of determinacy with infinitely many Woodin cardinals (Woodin). On the other hand, large cardinals do not decide the continuum hypothesis: Lévy and Solovay (1967) showed that forcing with a poset smaller than $\kappa$ preserves the measurability of $\kappa$ (and similarly for the other large cardinals), and CH can be forced either way by such small posets.

An empirical phenomenon, not a theorem. Every natural theory studied so far has turned out to be comparable in consistency strength with the large cardinal hierarchy, and the hierarchy has turned out to be linearly ordered. There is no proof that this must happen — artificial incomparable theories can be built from self-referential sentences — and many set theorists regard the phenomenon as evidence that large cardinals measure something real.

What is open. Whether there are canonical inner models — analogues of $L$ — for supercompact cardinals is the subject of Woodin's "Ultimate $L$ " programme and is open. Whether a Reinhardt cardinal (a non-trivial $j : V \to V$ ) is consistent with ZF without choice is open. Whether the purely finite statement about Laver tables in the computation section can be proved without large cardinals is open. And for every large cardinal axiom, its consistency — relative to ZFC or anything weaker — is, by Gödel's theorem, beyond proof; it is a matter of evidence and judgement.

Formal mathematicsF

Inaccessible and measurable cardinals in Lean

Mathlib defines inaccessible cardinals, the von Neumann hierarchy ZFSet.vonNeumann inside its model ZFSet of ZFC, and the rank of a set. Its definition of inaccessibility agrees with ours:

inaccessible_iffLean 4Applies a library theoremFormally verified

/-- Mathlib's definition of a (strongly) inaccessible cardinal agrees with the lesson's: `κ` is
uncountable, regular, and a strong limit (`2^λ < κ` for all `λ < κ`). This is Mathlib's
`Cardinal.isInaccessible_def`. -/
theorem inaccessible_iff {κ : Cardinal.{u}} :
    IsInaccessible κ ↔ ℵ₀ < κ ∧ Cardinal.IsRegular κ ∧ IsStrongLimit κ :=
  isInaccessible_def