Axiomatic set theory: hierarchy, cardinal arithmetic and L

MotivationH

What does the universe of sets look like?

The axioms of ZFC were written down to avoid paradoxes and to support ordinary mathematics. Two questions remain once they are in place. Is there a picture behind the axioms — a structure they describe? And which natural questions do they settle? The most famous is Cantor's continuum problem: is $2^{\aleph_0} = \aleph_1$ ? It was the first of Hilbert's problems in 1900.

The answer to the first question is the cumulative hierarchy: start from nothing, form all subsets, and repeat transfinitely. The second question has a two-part answer. ZFC proves some striking restrictions on the function $\kappa \mapsto 2^\kappa$ — for instance $2^{\aleph_0} \neq \aleph_\omega$ — but Gödel (1938) built a model, the constructible universe $L$ , in which $2^\kappa = \kappa^+$ for every infinite $\kappa$ , and Cohen (1963) built models where $2^{\aleph_0}$ is as large as one likes, subject to König's restriction. This lesson develops the hierarchy, the cardinal arithmetic that ZFC does decide, the reflection principle, and Gödel's $L$ ; forcing supplies the other half.

IntuitionH

Building the universe in stages

At stage $0$ there is nothing. At each successor stage, form every subset of what exists so far. At limit stages, gather everything built so far. The sets are exactly the things that appear at some stage. Foundation says there is nothing else: no set is built from itself, and every chain $x_0 \ni x_1 \ni x_2 \ni \cdots$ ends.

Gödel's $L$ is a thinner universe built the same way, except that at each successor stage we keep only the subsets that are definable from what exists so far. It contains every ordinal — the "spine" of $V$ — but as few subsets as possible.

The cumulative hierarchy $V = \bigcup_\alpha V_\alpha$ grows upwards along the ordinals; each level $V_{\alpha+1}$ is the power set of $V_\alpha$. The constructible universe $L$ (shaded) has the same ordinals but keeps only definable subsets at each stage. Whether $V = L$ is not decided by ZFC.

DefinitionsH

Definitions

We work in ZF, adding choice where stated, and use von Neumann ordinals and cardinals as initial ordinals (see ordinals and cardinals and the axiom of choice). Recall transfinite recursion: for every class function $G$ there is a unique class function $F$ on the ordinals with $F(\alpha) = G(F \restriction \alpha)$ for all $\alpha$ .

Definition— cumulative hierarchy and rank

By transfinite recursion, $V_0 = \varnothing$ , $V_{\alpha+1} = \mathcal{P}(V_\alpha)$ , and $V_\lambda = \bigcup_{\alpha \lt \lambda} V_\alpha$ for limit $\lambda$ . The rank of a set $x$ that lies in some $V_\beta$ is the least $\alpha$ with $x \subseteq V_\alpha$ (equivalently $x \in V_{\alpha+1}$ ). One checks that $\operatorname{rank}(x) = \sup\{\operatorname{rank}(y) + 1 : y \in x\}$ .

Definition— cofinality; regular and singular

A subset $X$ of a limit ordinal $\alpha$ is cofinal if it is unbounded in $\alpha$ . The cofinality $\operatorname{cf}(\alpha)$ is the least order type of a cofinal subset of $\alpha$ ; it is always a regular cardinal. An infinite cardinal $\kappa$ is regular if $\operatorname{cf}(\kappa) = \kappa$ and singular otherwise.

Definition— cardinal exponentiation, GCH

For cardinals, $\kappa^\lambda = |{}^\lambda\kappa|$ , the number of functions $\lambda \to \kappa$ ; $\kappa^+$ is the least cardinal above $\kappa$ . The continuum hypothesis CH says $2^{\aleph_0} = \aleph_1$ ; the generalised continuum hypothesis GCH says $2^\kappa = \kappa^+$ for every infinite cardinal $\kappa$ .

Definition— relativisation and absoluteness

For a class $M$ and formula $\varphi$ , the relativisation $\varphi^M$ is obtained by bounding every quantifier by $M$ . A formula $\varphi(\bar x)$ is absolute for $M$ if $\varphi^M(\bar a) \leftrightarrow \varphi(\bar a)$ for all $\bar a \in M$ . Every $\Delta_0$ formula (all quantifiers bounded, $\exists y \in z$ ) is absolute for every transitive class. " $x$ is an ordinal", " $x = \omega$ ", " $f$ is a function" are absolute for transitive models of ZF; " $x$ is uncountable" and " $y = \mathcal{P}(x)$ " are not.

Definition— the constructible universe

For a set $A$ , $\operatorname{Def}(A)$ is the set of $X \subseteq A$ definable over the structure $(A, \in)$ by a first-order formula with parameters from $A$ . Then $L_0 = \varnothing$ , $L_{\alpha+1} = \operatorname{Def}(L_\alpha)$ , $L_\lambda = \bigcup_{\alpha \lt \lambda} L_\alpha$ for limit $\lambda$ , and $L = \bigcup_\alpha L_\alpha$ . The axiom of constructibility is the statement $V = L$ , that is, $\forall x\, \exists \alpha\; x \in L_\alpha$ .

Worked examplesH

Examples

Example— The first stages

$|V_0|, |V_1|, |V_2|, |V_3|, |V_4|, |V_5| = 0, 1, 2, 4, 16, 65536$ , since $|V_{n+1}| = 2^{|V_n|}$ . The set $V_\omega$ consists of the hereditarily finite sets; with the inherited membership it satisfies every axiom of ZFC except infinity. $V_{\omega+\omega}$ satisfies Zermelo's axioms (ZC) but not replacement: the function $n \mapsto \omega + n$ on $\omega$ is definable there, but its range $\{\omega + n : n \in \omega\}$ has rank $\omega + \omega$ , so it is not in $V_{\omega+\omega}$ . All the usual objects of analysis — $\R$ , $\C$ , Lebesgue measure on $\R$ — have codings of rank below $\omega + \omega$ . If $\kappa$ is strongly inaccessible, $V_\kappa \models \mathsf{ZFC}$ (see large cardinals).

Example— Cofinalities

$\operatorname{cf}(\omega) = \operatorname{cf}(\omega + \omega) = \operatorname{cf}(\omega^2) = \omega$ . With choice, every successor cardinal $\aleph_{\alpha+1}$ is regular, since a union of at most $\aleph_\alpha$ sets each of size at most $\aleph_\alpha$ has size at most $\aleph_\alpha$ . But $\aleph_\omega = \sup_n \aleph_n$ is singular with $\operatorname{cf}(\aleph_\omega) = \omega$ , and $\operatorname{cf}(\aleph_{\omega_1}) = \omega_1$ . In general $\operatorname{cf}(\aleph_\lambda) = \operatorname{cf}(\lambda)$ for limit $\lambda$ .

Example— Ranks

Each ordinal has rank equal to itself; $\operatorname{rank}(\{\varnothing\}) = 1$ ; the Kuratowski pair $(a, b) = \{\{a\}, \{a, b\}\}$ has rank $\max(\operatorname{rank} a, \operatorname{rank} b) + 2$ . $L_n = V_n$ for all finite $n$ (every subset of a finite set is definable with parameters) and $L_\omega = V_\omega$ , but $L_{\omega+1}$ is countable — there are only countably many formulas and finite parameter lists — while $V_{\omega+1} = \mathcal{P}(V_\omega)$ is uncountable.

ProofH

Every set has a rank

Theorem— Theorem 1

(a) Each $V_\alpha$ is transitive, and $\beta \le \alpha$ implies $V_\beta \subseteq V_\alpha$ . (b) (ZF) Every set belongs to some $V_\alpha$ .

Proof

(a) By induction on $\alpha$ we show that $V_\alpha$ is transitive and contains every $V_\beta$ , $\beta \lt \alpha$ , as a subset. Limits are clear, since unions of transitive sets are transitive. For $V_{\alpha+1} = \mathcal{P}(V_\alpha)$ : transitivity of $V_\alpha$ means each $y \in V_\alpha$ satisfies $y \subseteq V_\alpha$ , i.e. $y \in V_{\alpha+1}$ ; so $V_\alpha \subseteq V_{\alpha+1}$ . And if $y \in x \in V_{\alpha+1}$ then $y \in V_\alpha \subseteq V_{\alpha+1}$ , so $V_{\alpha+1}$ is transitive.

(b) Suppose some set $x$ lies in no $V_\alpha$ . Let $T$ be the transitive closure of $\{x\}$ (it exists by replacement and union: $T = \bigcup_n T_n$ with $T_0 = \{x\}$ , $T_{n+1} = \bigcup T_n$ ). The set $B = \{y \in T : y \notin \bigcup_\alpha V_\alpha\}$ is non-empty, so by foundation it has an $\in$ -minimal element $y$ . Every $z \in y$ lies in $T$ (transitivity) and not in $B$ (minimality), so $z \in V_{\alpha_z}$ for a least ordinal $\alpha_z$ . By replacement, $\{\alpha_z : z \in y\}$ is a set, so $\alpha = \sup\{\alpha_z + 1 : z \in y\}$ is an ordinal. By (a), every $z \in y$ lies in $V_\alpha$ ; so $y \subseteq V_\alpha$ and $y \in V_{\alpha+1}$ — a contradiction.

∎

So $V = \bigcup_\alpha V_\alpha$ , and the rank function is defined everywhere. Since $y \in x$ implies $\operatorname{rank}(y) \lt \operatorname{rank}(x)$ , there are no $\in$ -cycles. Over the other axioms, foundation is in fact equivalent to $V = \bigcup_\alpha V_\alpha$ : (b) gives one direction, and for the other, an element of least rank in a non-empty set is $\in$ -minimal. Rank is the standard tool for proofs by $\in$ -induction and for cutting proper classes down to sets ("Scott's trick": replace an equivalence class by its elements of least rank).

ProofH

Cofinality and König's theorem

What does ZFC decide about $2^\kappa$ ? Cantor: $2^\kappa \gt \kappa$ . Monotonicity: $\kappa \le \lambda$ implies $2^\kappa \le 2^\lambda$ . And one more restriction, due to Julius König (1905).

Theorem— König's theorem

(ZFC) For every infinite cardinal $\kappa$ : (i) $\kappa \lt \kappa^{\operatorname{cf}(\kappa)}$ ; (ii) $\operatorname{cf}(2^\kappa) \gt \kappa$ . In particular $2^{\aleph_0} \neq \aleph_\omega$ .

Proof

(i) Let $\mu = \operatorname{cf}(\kappa)$ and fix an increasing sequence $(\alpha_i)_{i \lt \mu}$ cofinal in $\kappa$ . Then $\kappa = \bigcup_{i \lt \mu} \alpha_i$ with $|\alpha_i| \lt \kappa$ . Let $(f_\beta)_{\beta \lt \kappa}$ be any $\kappa$ -sequence of functions $\mu \to \kappa$ ; we find a function $g : \mu \to \kappa$ not in it. For each $i \lt \mu$ , the set $\{f_\beta(i) : \beta \lt \alpha_i\}$ has size at most $|\alpha_i| \lt \kappa$ , so let $g(i)$ be the least element of $\kappa$ not in it. If $\beta \lt \kappa$ , choose $i$ with $\beta \lt \alpha_i$ ; then $g(i) \neq f_\beta(i)$ . So no map $\kappa \to {}^\mu\kappa$ is onto, and $\kappa \lt \kappa^\mu$ (clearly $\kappa \le \kappa^\mu$ ).

(ii) Let $\lambda = 2^\kappa$ and suppose $\operatorname{cf}(\lambda) \le \kappa$ . By (i) applied to $\lambda$ ,

\lambda \lt \lambda^{\operatorname{cf}(\lambda)} \le \lambda^\kappa = (2^\kappa)^\kappa = 2^{\kappa \cdot \kappa} = 2^\kappa = \lambda,

a contradiction. Finally $\operatorname{cf}(\aleph_\omega) = \omega$ , while $\operatorname{cf}(2^{\aleph_0}) \gt \aleph_0$ .

∎

Remarkably, this is essentially all that ZFC proves about $2^\kappa$ for regular $\kappa$ : by Easton's theorem (1970), any class function $F$ on regular cardinals that is non-decreasing and satisfies $\operatorname{cf}(F(\kappa)) \gt \kappa$ can be the function $\kappa \mapsto 2^\kappa$ in some forcing extension. For singular cardinals ZFC proves much more — Silver's theorem (1974) that GCH cannot first fail at a singular cardinal of uncountable cofinality, and Shelah's pcf bound $2^{\aleph_\omega} \lt \aleph_{\omega_4}$ when $\aleph_\omega$ is a strong limit.

ProofH

Reflection

Theorem— Reflection principle (Montague 1961; Lévy 1960)

For any finitely many formulas $\varphi_1, \dots, \varphi_n$ , ZF proves: for every ordinal $\beta$ there is a limit ordinal $\alpha \gt \beta$ such that each $\varphi_i$ is absolute between $V_\alpha$ and $V$ .

Proof

Close the list under subformulas; it suffices to handle formulas built from atomic ones by $\neg$ , $\wedge$ and $\exists$ . For each formula $\exists y\, \psi(\bar x, y)$ in the list define a class function $F_\psi$ on finite tuples: $F_\psi(\bar x)$ is the least ordinal $\gamma$ such that, if some $y$ satisfies $\psi(\bar x, y)$ , then some $y \in V_\gamma$ does (it exists by Theorem 1). Put $\alpha_0 = \beta + 1$ and let $\alpha_{k+1}$ be greater than $\alpha_k$ and than every $F_\psi(\bar x)$ with $\bar x$ in $V_{\alpha_k}$ — a set of ordinals, by replacement. Let $\alpha = \sup_k \alpha_k$ , a limit ordinal. Now show by induction on formulas that each one is absolute for $V_\alpha$ : atomic formulas are absolute, the cases $\neg$ and $\wedge$ are immediate, and for $\exists y\, \psi$ : if $\bar x \in V_\alpha$ , then $\bar x \in V_{\alpha_k}$ for some $k$ , so if some $y$ satisfies $\psi(\bar x, y)$ then one lies in $V_{\alpha_{k+1}} \subseteq V_\alpha$ , and by the induction hypothesis $\psi^{V_\alpha}(\bar x, y)$ ; the converse direction is immediate from the induction hypothesis. (This is the Tarski–Vaught criterion.)

∎

Since $\varphi^{V_\alpha}$ is equivalent to " $(V_\alpha, \in) \models \varphi$ " for the formalised satisfaction relation of set-sized structures, reflection gives: for every finite set $\Phi$ of axioms of ZF, ZF proves " $\Phi$ has a model", hence $\mathrm{Con}(\Phi)$ . If ZF were finitely axiomatisable, it would prove its own consistency, contradicting Gödel's second theorem. So, if ZF is consistent, it is not finitely axiomatisable (Montague 1961). Reflection is also the key to showing that $L$ satisfies separation.

ProofH

Gödel's constructible universe

Theorem— Gödel (1938)

(ZF) $L$ is a transitive proper class containing all ordinals, and $L$ satisfies $\mathsf{ZF} + (V = L)$ . Moreover $\mathsf{ZF} + (V = L)$ proves AC and GCH. Consequently, if ZF is consistent, so is $\mathsf{ZFC} + \mathsf{GCH}$ .

We outline the proof; Jech (2003, chapter 13) and Kunen (1980, chapters V–VI) give it in full.

$L$ is a transitive class model. Each $L_\alpha$ is transitive, $L_\alpha \cap \mathrm{Ord} = \alpha$ , and $\alpha \in L_{\alpha+1}$ (the ordinals of $L_\alpha$ form a definable subset). Extensionality and foundation hold in any transitive class; pairing, union and infinity are routine.
Separation and replacement in $L$ use reflection: given $\varphi$ and $a \in L_\beta$ , reflect $\varphi^L$ to some $L_\alpha$ with $\alpha \gt \beta$ (the reflection principle holds for the hierarchy $L_\alpha$ as for $V_\alpha$ ); then $\{x \in a : \varphi^L(x)\} = \{x \in a : \varphi^{L_\alpha}(x)\}$ is definable over $L_\alpha$ , so it lies in $L_{\alpha+1}$ . Power set: for $a \in L$ , the set $\mathcal{P}(a) \cap L$ is contained in some $L_\gamma$ by replacement, and $\mathcal{P}(a) \cap L \in L_{\gamma+1}$ serves as the power set of $a$ inside $L$ .
Absoluteness. The operation $A \mapsto \operatorname{Def}(A)$ , and hence $\alpha \mapsto L_\alpha$ , is defined by a formula that is absolute for transitive models of ZF. So computing $L$ inside $L$ gives $L$ again: $L \models V = L$ .
$V = L$ implies AC. Define a well-order $\lt_L$ : $x \lt_L y$ if $x$ appears at an earlier stage $L_\alpha$ , or at the same stage via an earlier pair (formula, parameters), using the well-order of $L_\alpha$ already defined. It is a definable global well-order.
$V = L$ implies GCH. The heart is the condensation lemma: if $X \prec (L_\delta, \in)$ with $\delta$ a limit ordinal, the transitive (Mostowski) collapse of $X$ is some $L_\gamma$ with $\gamma \le \delta$ . Given $x \subseteq \kappa$ , pick a limit $\delta$ with $x \in L_\delta$ and, by Löwenheim–Skolem, $X \prec L_\delta$ of size $\kappa$ with $\kappa \cup \{x\} \subseteq X$ . The collapse fixes each element of $\kappa$ , hence fixes $x$ , and has the form $L_\gamma$ with $|\gamma| \le \kappa$ . So $x \in L_{\kappa^+}$ . Thus $\mathcal{P}(\kappa) \subseteq L_{\kappa^+}$ , which has cardinality $\kappa^+$ , and $2^\kappa = \kappa^+$ .
Relative consistency. Steps 1–5 are proofs in ZF of each axiom of $\mathsf{ZFC} + \mathsf{GCH}$ relativised to $L$ . So a proof of a contradiction from $\mathsf{ZFC} + \mathsf{GCH}$ would relativise to a proof of a contradiction from ZF. This argument is purely syntactic: it needs no set model of ZF.

Note

Relative versus absolute. Gödel's theorem proves $\mathrm{Con}(\mathsf{ZF}) \to \mathrm{Con}(\mathsf{ZFC} + \mathsf{GCH})$ , for instance in $\mathsf{PA}$ . It does not prove $\mathrm{Con}(\mathsf{ZFC} + \mathsf{GCH})$ outright — and nothing formalisable in ZFC can (by Gödel's second theorem), unless ZFC is inconsistent.

Formal mathematicsF

The hierarchy and König's theorem in Lean

Mathlib models ZFC sets as the type ZFSet, built from well-founded trees; foundation is therefore a theorem, and Mathlib defines the von Neumann hierarchy and the rank function. The recursion equations of the hierarchy:

vonNeumann_succLean 4Applies a library theoremFormally verified

/-- The successor step of the cumulative hierarchy: `V_{α+1} = 𝒫(V_α)`.
This applies Mathlib's `ZFSet.vonNeumann_add_one`. -/
theorem vonNeumann_succ (α : Ordinal) :
    ZFSet.vonNeumann (α + 1) = ZFSet.powerset (ZFSet.vonNeumann α) :=
  ZFSet.vonNeumann_add_one α