Contents / Mathematical Logic / Set Theory

Chapter 4

Set Theory

Zermelo-Fraenkel set theory, axiom of choice, ordinals, cardinals, transfinite induction, and well-ordering.

Introduction

Every other chapter of this subject studies a logical apparatus — connectives, quantifiers, deduction, structures, computation — and tests it on small examples. This chapter turns that apparatus on the largest object it has: the axiom system that the rest of mathematics is written in.

The move is easy to describe and hard to absorb. ZFC is a list of sentences in a first-order language with one binary relation symbol, $\in$ . That is all it is. It is not a description of a universe of sets, any more than the group axioms are a description of a particular group; it is a constraint, and the things satisfying the constraint are its models. Once that reading is taken seriously, the questions of this chapter become ordinary model theory: which sentences follow from the list, what the models look like, when two models agree about a formula, and what a theory of this strength can prove about theories of this strength.

The payoff is that several facts that look mystical from inside mathematics become routine. A countable model of set theory contains a set it believes is uncountable, and no contradiction follows. The continuum hypothesis has no truth value determined by ZFC, for the same reason commutativity has none determined by the group axioms. ZFC needs infinitely many axioms and cannot be trimmed to finitely many. Each of these is a statement about a theory and its models, provable with the tools of the chapters Model Theory, Formal Systems and Incompleteness.

Note (Scope, and where the set theory itself lives). The mathematics of sets — the axioms one at a time and what each builds, ordinal and cardinal arithmetic, the alephs, Zorn's lemma and the other equivalents of choice, the construction of $L$ , forcing posets and generic filters — is the subject Set Theory, whose chapters Naive Set Theory, ZFC Axioms, Ordinals & Cardinals, The Axiom of Choice, Independence & Forcing and Advanced Set Theory treat it at length. This chapter assumes those results and studies ZFC as a theory: schemas, relativisation, absoluteness, reflection, models, and independence as a model-theoretic phenomenon. Where a set-theoretic fact is needed it is stated and attributed, not re-derived.

Throughout, $L_{\in}$ is the language of set theory, $V$ denotes the universe of all sets, $Ord$ the class of ordinals, $V_{α}$ the levels of the cumulative hierarchy, and $Con (T)$ the arithmetical sentence asserting that the theory $T$ proves no contradiction. Lower-case Greek $φ, ψ, χ$ always denote formulas; upper-case $M, N$ denote models or classes.

4.1ZFC as a List of Sentences

A first-order theory is a set of sentences in a fixed language, and everything a logician asks about ZFC is asked about that set of sentences. So the first job is to see the axioms written as formulas rather than described in English — because two of them are not formulas at all.

Definition 4.1 (The theory ZFC). $L_{\in}$ is the first-order language whose only non-logical symbol is the binary relation symbol $\in$ ; its atomic formulas are $x \in y$ and $x = y$ . ZFC is the $L_{\in}$ -theory consisting of the sentences

Extensionality, Pairing, Union, Power Set, Infinity, Foundation, Choice,

together with every instance of the Separation and Replacement schemas. ZF is ZFC without Choice, and $ZFC^{-}$ is ZFC without Power Set.

Written out, Extensionality and Foundation are single sentences of a few symbols each:

\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y),

\forall x (\exists y (y \in x) \to \exists y (y \in x \land \neg\exists z (z \in y \land z \in x))) .

There is no symbol for $\emptyset$ , $\cup$ , $P$ or $ω$ anywhere in the language. Each of those is an abbreviation licensed by an existence axiom together with a uniqueness theorem proved from Extensionality, exactly as the chapter ZFC Axioms sets out. For a logician the point of the austerity is that the syntax stays finite and checkable: one can ask whether a string is a formula, whether a finite list of formulas is a proof, and — crucially for Gödel's theorems — whether a string is an axiom.

Definition 4.2 (Axiom schema). An axiom schema is a template containing a syntactic parameter, together with the rule that every result of substituting an $L_{\in}$ -formula for that parameter is an axiom. Separation is the schema whose instance for a formula $φ (x, \overset{p}{ˉ})$ , in which $y$ is not free, is

\forall \overset{p}{ˉ} \forall a \exists y \forall x (x \in y \leftrightarrow (x \in a \land φ (x, \overset{p}{ˉ}))),

and Replacement is the schema whose instance for $φ (x, y, \overset{p}{ˉ})$ is

\forall \overset{p}{ˉ} \forall a (\forall x \in a \exists! y φ (x, y, \overset{p}{ˉ}) \to \exists b \forall x \in a \exists y \in b φ (x, y, \overset{p}{ˉ})) .

The parameters $\overset{p}{ˉ}$ are not decoration. Without them one could not separate ${x \in a : x \in p}$ for an arbitrary set $p$ , and the resulting theory would be far weaker than intended.

Intuition. A schema is a machine that emits axioms, not an axiom. The English sentence "for every property, the sub-collection of $a$ with that property is a set" quantifies over properties, and first-order logic has no variables ranging over formulas — its quantifiers range over the objects of the structure, which here are sets. So the quantification is pushed out of the object language into the metalanguage: instead of one sentence about all formulas, we take infinitely many sentences, one per formula, and the infinitude is managed by a rule anyone can check mechanically.

Pitfall. "Infinitely many axioms" does not mean "not a legitimate theory". What Gödel's theorems and every proof-theoretic argument require is that the axiom set be effectively axiomatised — that some algorithm decides whether a given sentence is an axiom. Separation and Replacement pass that test, since recognising an instance is a parsing problem. A theory axiomatised by all true arithmetic sentences is the kind that fails it.

Because the two schemas overlap, the list above is redundant, and seeing exactly how is a useful exercise in reading an instance.

Theorem 4.3 (Separation is derivable from Replacement). Over the remaining axioms of ZF, every instance of Separation follows from an instance of Replacement.

Proof. Fix $φ (x, \overset{p}{ˉ})$ and a set $a$ , and let

ψ (x, y, \overset{p}{ˉ}) \equiv (φ (x, \overset{p}{ˉ}) \land y = {x}) \lor (\neg φ (x, \overset{p}{ˉ}) \land y = \emptyset),

where $y = {x}$ and $y = \emptyset$ abbreviate their $Δ_{0}$ definitions, so that $ψ$ is a genuine $L_{\in}$ -formula. It is functional on $a$ : for each $x \in a$ exactly one $y$ answers to it, namely the singleton ${x}$ when $φ (x, \overset{p}{ˉ})$ holds and $\emptyset$ when it fails, and Pairing guarantees the singleton exists. The instance of Replacement for $ψ$ therefore yields a set

b = {{x} : x \in a, φ (x, \overset{p}{ˉ})} \cup {\emptyset}

— the second term present only if some $x \in a$ fails $φ$ . Applying Union to $b$ gives

⋃ b = {x \in a : φ (x, \overset{p}{ˉ})},

since each singleton contributes its one element and $\emptyset$ contributes nothing. That is the conclusion of the Separation instance for $φ$ , and the argument used only Pairing, Union and one instance of Replacement.∎

Separation is nevertheless listed, for two reasons a logician cares about. First, the subtheory of ZF with Replacement deleted and Separation retained — Zermelo set theory, written Z — is a genuinely different and strictly weaker theory, and one wants a name for it; the last section of this chapter exhibits a model of it. Second, keeping Separation separate lets one calibrate which instances an argument actually needs, which is what makes fine-grained results such as "this theorem uses only $Δ_{0}$ -Separation" statable.

Example 4.4 (Reading a single instance). Write the instance of Replacement that proves ${P (x) : x \in a}$ is a set, and say which instance of Separation the same formula gives.

Solution.

Let $φ (x, y)$ be $\forall z (z \in y \leftrightarrow \forall w (w \in z \to w \in x))$ , which says " $y$ is the set of all subsets of $x$ ".
Power Set gives existence of such a $y$ for each $x$ , and Extensionality gives uniqueness, so $\forall x \in a \exists! y φ (x, y)$ . That is the hypothesis of the Replacement instance for this $φ$ , and its conclusion hands us the set ${P (x) : x \in a}$ .
The Separation instance for the formula $\exists u \in a φ (u, x)$ carves the same collection out of any set already known to contain it.
A different $φ$ gives a different axiom. There is no single sentence of $L_{\in}$ from which both instances follow uniformly; the uniformity lives only in the template.

□

The schemas are not a presentational convenience that a cleverer axiomatisation could remove. That is a theorem, and one of the cleanest illustrations in mathematics of the second incompleteness theorem doing real work.

Theorem 4.5 (ZFC is not finitely axiomatisable). If ZFC is consistent, then there is no finite set $T$ of $L_{\in}$ -sentences with exactly the same consequences as ZFC.

Proof (Sketch). Suppose $T$ were such a finite set, and let $τ$ be the conjunction of its members, so that ZFC $⊢ τ$ and $τ ⊢ σ$ for every axiom $σ$ of ZFC. The Reflection Principle, proved in the section Reflecting the Universe in a Set, says that for each finite list of formulas ZFC proves some level $V_{α}$ agrees with $V$ about all of them; applied to the conjuncts of $τ$ it yields ZFC $⊢ \exists α (V_{α} ⊨ τ)$ . But $V_{α}$ is a set, so this says ZFC proves that $τ$ has a model, and the soundness theorem — formalisable in ZFC for set-sized structures — gives ZFC $⊢ Con (τ)$ . Since $τ$ axiomatises ZFC, ZFC proves $Con (τ) \to Con (ZFC)$ , so ZFC $⊢ Con (ZFC)$ , contradicting Gödel's second incompleteness theorem from the chapter Incompleteness. The argument rests on two imported results: reflection, proved below, and Gödel's second theorem, whose proof is not reproduced here.∎

Remark (NBG, and what is really going on). Von Neumann–Bernays–Gödel class theory is finitely axiomatisable, and it proves exactly the same $L_{\in}$ -sentences as ZFC — it is a conservative extension. There is no paradox: NBG has variables for classes, so the single sentence "for every class $F$ that is a function and every set $a$ , the image $F [a]$ is a set" does the work of the whole Replacement schema. The reflection argument fails for NBG because the reflecting object would have to satisfy the class quantifiers too. The lesson is that finite axiomatisability is a property of a presentation in a language, not of a body of mathematics.

Summary. ZFC is an effectively axiomatised, infinite set of $L_{\in}$ -sentences. Separation and Replacement are schemas because first-order quantifiers range over sets and not over formulas; Replacement subsumes Separation instance by instance; and the infinitude is unavoidable, since a finite axiomatisation would let ZFC prove its own consistency.

Exercises for §4.1 →

4.2Models of ZFC and the Skolem Paradox

A model of ZFC is nothing more exotic than a structure for a language with one binary relation, in the sense of the chapter Model Theory: a non-empty domain $M$ together with a binary relation $E \subseteq M \times M$ interpreting $\in$ , such that every axiom comes out true under the usual satisfaction clauses. The elements of $M$ need not be sets in any prior sense, and $E$ need not be real membership.

Definition 4.6 (Model, standard model, transitive model). An $L_{\in}$ -structure is a pair $(M, E)$ with $E$ a binary relation on the non-empty set $M$ . It is standard (or well-founded) if $E$ is genuine membership restricted to $M$ and is well-founded, and transitive if in addition $M$ is a transitive set: $x \in y \in M$ implies $x \in M$ . For transitive $M$ we write $M ⊨ φ$ with $E = \in$ understood.

Transitivity is the condition that makes a model honest about its elements: what $M$ believes are the members of one of its sets really are its members, all of them. Nearly every theorem in the rest of this chapter has "transitive" in its hypothesis for that reason, and the section Relativisation and Absoluteness says exactly which beliefs it protects.

The first thing to settle is whether there are any models at all, and here the metatheory is delicate.

Theorem 4.7 (ZFC cannot produce a model of itself). If ZFC is consistent, then ZFC does not prove the sentence "there exist a set $M$ and a relation $E$ on $M$ with $(M, E) ⊨ ZFC$ ".

Proof. Working in ZFC, satisfaction for a set-sized structure is definable: there is an $L_{\in}$ -formula $Sat (M, E, ┌ φ ┐)$ expressing the Tarski clauses by recursion on the coded formula, and ZFC proves the soundness theorem for it. So if ZFC proved that some $(M, E)$ satisfies every ZFC axiom, ZFC would prove that no contradiction is derivable from those axioms — that is, ZFC $⊢ Con (ZFC)$ . Gödel's second incompleteness theorem says a consistent, effectively axiomatised theory interpreting arithmetic does not prove its own consistency, and ZFC interprets arithmetic via the von Neumann naturals. Hence no such proof exists.∎

Pitfall. This is not the claim that ZFC has no models. If ZFC is consistent then by the completeness theorem it has one; what the theorem says is that the existence of one cannot be established inside ZFC. Every result below of the form "if there is a transitive model of ZFC then …" carries that hypothesis explicitly, and it is a genuine extra assumption — strictly stronger than $Con (ZFC)$ , since a transitive model would make $Con (ZFC)$ true rather than merely consistent.

Granting a model, model theory immediately produces a small one, and the result is the single most disorienting fact in the subject.

Theorem 4.8 (Downward Löwenheim–Skolem for ZFC). If ZFC has a model, it has a countable model. If ZFC has a transitive model, it has a countable transitive model.

Proof. $L_{\in}$ is countable, so the downward Löwenheim–Skolem theorem of the chapter Model Theory produces a countable elementary substructure $(N, E) ⪯ (M, \in)$ of any given model $M$ . For the second claim, take $M$ transitive and $N ⪯ M$ countable. Since $N$ is an elementary substructure of a structure whose relation is genuine membership, $E$ is membership restricted to $N$ and is therefore well-founded, and $N$ satisfies Extensionality because $M$ does and Extensionality is a sentence. The Mostowski collapse below replaces $(N, \in)$ by an isomorphic transitive set, which is countable because the collapse is a bijection, and which satisfies ZFC because it is isomorphic to a model of ZFC.∎

Theorem 4.9 (Mostowski collapse). Let $(N, E)$ be a well-founded structure satisfying Extensionality, with $E$ set-like. Then there are a unique transitive set $\overset{ˉ}{N}$ and a unique isomorphism $π : (N, E) \to (\overset{ˉ}{N}, \in)$ , given by the recursion

π (x) = {π (y) : y E x} .

Proof (Sketch). Well-foundedness makes the displayed recursion legitimate, by the transfinite recursion theorem of the final section applied to the well-founded relation $E$ . Put $\overset{ˉ}{N} = π [N]$ . It is transitive, because every member of $π (x)$ is some $π (y)$ and hence lies in the range. Surjectivity is immediate. Injectivity follows from Extensionality in $N$ by $E$ -induction: if $π (x) = π (x^{'})$ then $x$ and $x^{'}$ have the same $E$ -members by the induction hypothesis, so $x = x^{'}$ . That $π$ is a homomorphism both ways is read off the recursion. Uniqueness follows because any two such isomorphisms agree by induction on $E$ . The routine part is the verification of the recursion's hypotheses; the substantive ones are exactly well-foundedness and extensionality, and the theorem fails without either.∎

Example 4.10 (Skolem's paradox). Let $M$ be a countable transitive model of ZFC. Inside $M$ , Cantor's theorem holds, so $M ⊨$ " $P (ω)$ is uncountable". Yet $M$ is countable, so the set $(P (ω))^{M}$ is countable in $V$ . Resolve the apparent contradiction.

Solution.

Unwind what "uncountable" abbreviates. The sentence $M$ satisfies is: there is no function $f$ with domain $ω$ whose range is all of $P (ω)$ — and the quantifier "there is no function" ranges over $M$ only.
In $V$ such a function does exist, because $(P (ω))^{M} \subseteq M$ is a countable set. But that function is not an element of $M$ .
So $M$ is right about every set it can see and wrong about nothing: " $M ⊨$ $(P (ω))^{M}$ is uncountable" and " $(P (ω))^{M}$ is countable" are claims about different quantifier ranges, and they are jointly consistent.
The moral is that "uncountable" is not absolute between transitive models: a model can lack the very bijection that would reveal a set's true size. The section Relativisation and Absoluteness turns this observation into a syntactic criterion, and the section on cardinals shows it is exactly the mechanism by which forcing changes cardinalities.

□

Intuition. A model of set theory is like a library that believes it holds every book. It is right that no catalogue on its own shelves lists its holdings in a single countable sequence — and it cannot see the catalogue in the city library across the street, which does exactly that. Nothing inside is false; the library simply has no access to the external enumeration.

Figure 4.11. A countable elementary submodel

N

of a level

V_{κ}

collapses to a countable transitive set. Height on the page is rank: the collapse preserves

\in

and squeezes the ordinals downward, so the tall thin

N

becomes a short model.

Summary. Models of ZFC are structures for a one-relation language; transitive ones are those that do not misreport membership. ZFC cannot prove it has a model, but if it has one it has a countable transitive one, and such a model necessarily misjudges cardinality from the outside — the Skolem paradox, which is a failure of absoluteness and not a contradiction.

Exercises for §4.2 →

4.3Relativisation and Absoluteness

Skolem's paradox showed that a model's verdict on a formula can differ from the truth in $V$ . Absoluteness theory is the syntax that predicts when this can happen. The device is relativisation: restricting every quantifier of a formula to a class.

Definition 4.12 (Relativisation). Let $M$ be a class or set. The relativisation $φ^{M}$ of an $L_{\in}$ -formula $φ$ is defined by recursion:

(x \in y)^{M} \equiv x \in y, (x = y)^{M} \equiv x = y,

(\neg ψ)^{M} \equiv \neg (ψ^{M}), (ψ \land χ)^{M} \equiv ψ^{M} \land χ^{M},

(\exists x ψ)^{M} \equiv \exists x (x \in M \land ψ^{M}), (\forall x ψ)^{M} \equiv \forall x (x \in M \to ψ^{M}) .

For a set $M$ and parameters in $M$ , $φ^{M}$ holds if and only if $M ⊨ φ$ .

Relativisation is what lets a theory talk about a model of itself without a satisfaction predicate. For a proper class $M$ there is no set-sized structure to apply Tarski's definition to, and indeed " $M ⊨ ZFC$ " is not a single sentence; but $φ^{M}$ is a perfectly good formula for each fixed $φ$ , so the assertion that $M$ satisfies ZFC becomes a schema of statements, one per axiom. That distinction is the whole reason the section on choice can speak of the inner model $L$ without contradicting the theorem ZFC cannot produce a model of itself.

Definition 4.13 (Absoluteness). Let $M \subseteq N$ be classes and $φ (\overset{x}{ˉ})$ a formula. Then $φ$ is upward absolute if $φ^{M} (\overset{a}{ˉ}) \to φ^{N} (\overset{a}{ˉ})$ for all $\overset{a}{ˉ} \in M$ , downward absolute if the converse implication holds, and absolute between $M$ and $N$ if both do. "Absolute for $M$ " with no second class named means absolute between $M$ and $V$ .

The syntactic criterion turns on how the quantifiers are bounded.

Definition 4.14 (Bounded quantifiers and the class $Δ_{0}$ ). $\exists x \in y ψ$ abbreviates $\exists x (x \in y \land ψ)$ and $\forall x \in y ψ$ abbreviates $\forall x (x \in y \to ψ)$ ; these are bounded quantifiers. A formula is $Δ_{0}$ if it is built from atomic formulas using connectives and bounded quantifiers only. A formula is $Σ_{1}$ if it has the form $\exists y ψ$ with $ψ \in Δ_{0}$ , and $Π_{1}$ if it has the form $\forall y ψ$ with $ψ \in Δ_{0}$ .

Theorem 4.15 ( $Δ_{0}$ formulas are absolute for transitive classes). Let $M$ be a transitive class and $φ (\overset{x}{ˉ})$ a $Δ_{0}$ formula. Then for all $\overset{a}{ˉ} \in M$ ,

φ^{M} (\overset{a}{ˉ}) \leftrightarrow φ (\overset{a}{ˉ}) .

Proof. Induction on the structure of $φ$ . Atomic formulas are unchanged by relativisation, so the base case is immediate, and the connective cases follow at once from the induction hypothesis, since relativisation commutes with $\neg$ and $\land$ . The only case with content is the bounded quantifier. Suppose $φ$ is $\exists x \in a ψ$ with $ψ$ a $Δ_{0}$ formula and $a \in M$ among the parameters. Then

φ^{M} \equiv \exists x (x \in M \land x \in a \land ψ^{M}) .

If $φ^{M}$ holds, a witness $x$ satisfies $x \in a$ and, by the induction hypothesis, $ψ (x)$ ; so $φ$ holds. Conversely if $φ$ holds, take a witness $x \in a$ . Transitivity of $M$ together with $a \in M$ gives $x \in M$ , and the induction hypothesis gives $ψ^{M} (x)$ ; so $φ^{M}$ holds. The bounded universal quantifier is the dual argument. Transitivity was used exactly once, and it is indispensable: it is what guarantees that the external witness is also available internally.∎

Corollary 4.16 (One unbounded quantifier: up and down). Let $M \subseteq N$ be transitive classes. Every $Σ_{1}$ formula is upward absolute from $M$ to $N$ , and every $Π_{1}$ formula is downward absolute from $N$ to $M$ .

Proof. Let $φ \equiv \exists y ψ$ with $ψ$ a $Δ_{0}$ formula, and suppose $φ^{M} (\overset{a}{ˉ})$ holds. Then some $y \in M \subseteq N$ has $ψ^{M} (y, \overset{a}{ˉ})$ , hence $ψ (y, \overset{a}{ˉ})$ by the theorem $Δ_{0}$ formulas are absolute for transitive classes applied to $M$ , hence $ψ^{N} (y, \overset{a}{ˉ})$ by the same theorem applied to $N$ . So $φ^{N} (\overset{a}{ˉ})$ . The $Π_{1}$ statement is this applied to the negation: $\neg φ$ is (equivalent to) $Σ_{1}$ , and contraposing upward absoluteness for it gives downward absoluteness for $φ$ .∎

Intuition. A bounded quantifier searches inside a set the model already possesses, and a transitive model possesses all of that set's members — so the search inside and the search outside comb through exactly the same objects. An unbounded quantifier searches the whole universe, where the model's shelves may be missing something. Hence the asymmetry: existential claims survive going up (a witness you have, a bigger world also has), and universal claims survive coming down (if nothing anywhere is a counterexample, nothing here is).

Example 4.17 (A stock of absolute notions). Show that " $x$ is empty", " $x \subseteq y$ ", " $x$ is transitive" and " $z = x \cup y$ " are $Δ_{0}$ , hence absolute for transitive classes.

Solution.

" $x$ is empty" is $\forall w \in x (w \neq = w)$ — bounded.
" $x \subseteq y$ " is $\forall w \in x (w \in y)$ — bounded.
" $x$ is transitive" is $\forall w \in x \forall u \in w (u \in x)$ — bounded.
" $z = x \cup y$ " is $\forall w \in z (w \in x \lor w \in y) \land \forall w \in x (w \in z) \land \forall w \in y (w \in z)$ — bounded.
Each is therefore absolute for every transitive class, with no hypothesis on which axioms the class satisfies. The same argument covers " $x$ is an ordered pair", " $r$ is a relation", " $f$ is a function", " $f$ is injective", " $z = x \cap y$ " and " $z = ⋃ x$ ", which is why elementary set-theoretic bookkeeping never causes trouble between models.

□

Example 4.18 (Power set is not absolute). Show that " $z = P (x)$ " is $Π_{1}$ but not absolute, and exhibit a transitive model that gets it wrong.

Solution.

The formula is $\forall w (w \in z \leftrightarrow w \subseteq x)$ . The inner " $w \subseteq x$ " is $Δ_{0}$ ; the outer $\forall w$ is unbounded, so the formula is $Π_{1}$ and by the corollary One unbounded quantifier: up and down it is downward absolute.
It is not upward absolute, and so not absolute. Let $M$ be a countable transitive model of ZFC and put $z = (P (ω))^{M}$ . Then $M ⊨$ " $z = P (ω)$ ", because $M$ contains every subset of $ω$ that it can see.
In $V$ , however, $z$ is a countable set while $P (ω)$ is uncountable, so $z \neq = P (ω)$ holds in $V$ .
The missing objects are precisely the subsets of $ω$ lying outside $M$ . This is Skolem's paradox again, now diagnosed by counting unbounded quantifiers rather than by inspecting the model.

□

Pitfall. Absoluteness always carries two hypotheses that are easy to drop: the classes must be transitive, and the smaller one must contain the parameters. For non-transitive models even $Δ_{0}$ formulas fail — take $M = {{0}}$ , in which the element ${0}$ satisfies " $x$ is empty", because $M$ contains no member of ${0}$ to witness otherwise.

Remark (The Lévy hierarchy). Continuing past $Σ_{1}$ and $Π_{1}$ by counting alternations of unbounded quantifiers gives the Lévy hierarchy $Σ_{n}, Π_{n}, Δ_{n}$ , the set-theoretic analogue of the arithmetical hierarchy from the chapter Computability. A formula provably equivalent to both a $Σ_{1}$ and a $Π_{1}$ formula is called $Δ_{1}$ and is absolute for transitive models of a modest fragment of ZF. Most of the notions used in ordinary mathematics turn out to be $Δ_{1}$ ; the exceptions — power set, cardinality, "constructible", "measurable" — are exactly the ones independence proofs manipulate.

Summary. Relativisation $φ^{M}$ restricts quantifiers to $M$ ; for a set $M$ it agrees with $M ⊨ φ$ , and for proper classes it is the only available formulation, one sentence at a time. $Δ_{0}$ formulas are absolute for transitive classes, $Σ_{1}$ formulas go up, $Π_{1}$ formulas come down. Notions defined by unbounded quantification over subsets are the ones models disagree about.

Exercises for §4.3 →

4.4Reflecting the Universe in a Set

The universe $V$ is not a set, so the sentence " $V ⊨ φ$ " cannot even be formed. What can be formed, for each fixed $φ$ , is $φ^{V}$ , which is just $φ$ itself; one may then ask whether some set agrees with $V$ about $φ$ . The Reflection Principle answers yes, for any finite list of formulas at once, and it is a theorem schema of ZF.

Definition 4.19 (Reflection for a list of formulas). Let $φ_{1}, \dots, φ_{n}$ be formulas and $M$ a set. Say $M$ reflects $φ_{1}, \dots, φ_{n}$ if for each $i$ and all parameters $\overset{a}{ˉ} \in M$ ,

φ_{i}^{M} (\overset{a}{ˉ}) \leftrightarrow φ_{i} (\overset{a}{ˉ}) .

Theorem 4.20 (Lévy–Montague Reflection Principle). For each finite list $φ_{1}, \dots, φ_{n}$ of $L_{\in}$ -formulas, ZF proves: for every ordinal $β$ there is a limit ordinal $α > β$ such that $V_{α}$ reflects $φ_{1}, \dots, φ_{n}$ .

Proof. Close the list under subformulas, so we may assume every subformula of each $φ_{i}$ is on the list, and rewrite $\forall$ as $\neg\exists\neg$ so that $\exists$ is the only quantifier. For each $φ_{i}$ of the form $\exists y ψ (y, \overset{x}{ˉ})$ define

F_{i} (\overset{a}{ˉ}) = the least γ with \exists y \in V_{γ} ψ (y, \overset{a}{ˉ}), and F_{i} (\overset{a}{ˉ}) = 0 if no such y exists .

This is a legitimate class function, because every set has a rank and the ordinals are well-ordered. Now set

G (ξ) = sup {F_{i} (\overset{a}{ˉ}) : i \leq n, \overset{a}{ˉ} \in V_{ξ}} + 1.

The collection being supped is the image of the set $V_{ξ}^{< ω}$ under finitely many definable functions, so Replacement makes it a set of ordinals and the supremum exists. Starting from $α_{0} = β + 1$ , put $α_{k + 1} = max (G (α_{k}), α_{k} + 1)$ and $α = sup_{k} α_{k}$ , a limit ordinal greater than $β$ .

We show $V_{α}$ reflects the list, by induction on the structure of the formulas. Atomic formulas and connectives are immediate. Let $φ_{i} \equiv \exists y ψ$ and $\overset{a}{ˉ} \in V_{α}$ . If $φ_{i}^{V_{α}} (\overset{a}{ˉ})$ holds, a witness in $V_{α}$ satisfies $ψ^{V_{α}}$ , hence $ψ$ by the induction hypothesis, so $φ_{i} (\overset{a}{ˉ})$ . Conversely suppose $φ_{i} (\overset{a}{ˉ})$ . Since $α$ is a limit and $V_{α} = ⋃_{k} V_{α_{k}}$ , we have $\overset{a}{ˉ} \in V_{α_{k}}$ for some $k$ ; by construction $F_{i} (\overset{a}{ˉ}) < G (α_{k}) \leq α_{k + 1} \leq α$ , so a witness $y$ lies in $V_{α}$ . The induction hypothesis converts $ψ (y, \overset{a}{ˉ})$ into $ψ^{V_{α}} (y, \overset{a}{ˉ})$ , giving $φ_{i}^{V_{α}} (\overset{a}{ˉ})$ .∎

The construction repays a second look, because the pattern recurs throughout set theory. Each $F_{i}$ is a Skolem function in disguise: it records how far up the hierarchy one must climb to find a witness. Closing an ordinal under finitely many such functions and iterating $ω$ times produces a closure point, and the closure points form a closed unbounded class. Reflection is the statement that closure points reflect — which is also why the $α$ produced is a limit, and why the theorem gives arbitrarily large such $α$ rather than one.

Pitfall. Reflection is a schema: one theorem per finite list. It does not say that some $V_{α}$ reflects all of ZFC — that would assert the existence of a set model of ZFC, contradicting the theorem ZFC cannot produce a model of itself. The quantifier "for each finite list" lives in the metatheory, outside the object language, and moving it inside is the commonest error in this area.

Corollary 4.21 (Every finite fragment has a transitive set model). For each finite $T \subseteq ZFC$ , ZFC proves that there are arbitrarily large $α$ with $V_{α} ⊨ T$ .

Proof. Apply the Reflection Principle to the sentences of $T$ together with all their subformulas, obtaining arbitrarily large limit $α$ with $V_{α}$ reflecting them. Each $τ \in T$ is an axiom of ZFC, hence true in $V$ , hence — being reflected — true in $V_{α}$ . Transitivity of $V_{α}$ is automatic, and $V_{α}$ is a set, so $(V_{α}, \in)$ is a transitive set model of $T$ .∎

This corollary is the workhorse of independence proofs. A forcing argument needs a ground model that is a set, so that one can form its extension; producing an outright model of ZFC is impossible, but every actual argument uses only finitely many axioms, and for those the corollary supplies a model. Combined with the theorem Downward Löwenheim–Skolem for ZFC and the Mostowski collapse, one obtains countable transitive models of any finite fragment — the standing hypothesis of the chapter Independence & Forcing.

Example 4.22 (Reflecting a single formula). Let $φ$ be $\forall x \exists y (x \in y)$ , which holds in $V$ . Trace the $α$ the proof of reflection produces from $β = 0$ , and check the reflection directly.

Solution.

The only unbounded existential is $\exists y (x \in y)$ , so there is one Skolem function: $F (a)$ is the least $γ$ with some $y \in V_{γ}$ containing $a$ . Taking $y = {a}$ , whose rank is $rank (a) + 1$ , gives $F (a) = rank (a) + 2$ .
Hence $G (ξ) = sup {rank (a) + 2 : a \in V_{ξ}} + 1 = ξ + 2$ for $ξ > 0$ , and iterating from $α_{0} = 1$ gives $α_{k} = 2 k + 1$ , so $α = sup_{k} α_{k} = ω$ .
Check directly: for $x \in V_{ω}$ we have ${x} \in V_{ω}$ , since $V_{ω}$ is closed under pairing. So $φ^{V_{ω}}$ holds, matching $φ$ .
Note the failure at a successor stage: $V_{5}$ does not reflect $φ$ , because $x = V_{4} \in V_{5}$ has no $y \in V_{5}$ containing it. The limit condition in the theorem is doing real work.

□

Example 4.23 (Reflection does not transfer to a single sentence). A student writes: "By reflection, ZFC proves $\exists α (V_{α} ⊨ ZFC)$ , so ZFC proves its own consistency." Diagnose precisely where this breaks, and say what ZFC does prove.

Solution.

The sentence $V_{α} ⊨ ZFC$ is expressible in ZFC, since satisfaction for set-sized structures is definable and ZFC is a definable set of codes. So the claimed conclusion is at least meaningful — the failure is not one of syntax.
But reflection never proves it. For each finite list, ZFC proves the corresponding instance; there is no instance whose list is all of ZFC, because the lists are finite.
What ZFC does prove, for each finite $T \subseteq ZFC$ , is $\exists α (V_{α} ⊨ T)$ , hence $Con (T)$ . So ZFC proves the consistency of each of its finite fragments — infinitely many theorems, one per fragment.
Gödel's second theorem is therefore not contradicted, and in fact this is a proof that ZFC is not finitely axiomatisable: a finite axiomatisation would let step 3 be applied to the whole theory at once.

□

Remark (Reflection as an axiom, and its strengthenings). Some presentations take reflection as a primitive schema and derive Infinity and Replacement from it over the remaining axioms — the Lévy reflection schema. Strengthening it by demanding that the reflecting $V_{α}$ be elementary in $V$ for all formulas at once is inconsistent, by the pitfall above; demanding second-order reflection instead yields large-cardinal axioms, which the chapter Advanced Set Theory treats.

Summary. For every finite list of formulas, ZF proves some level $V_{α}$ agrees with $V$ about all of them. This yields transitive set models of every finite fragment of ZFC, underwrites the non-finite-axiomatisability theorem, and must always be read as a schema — never as a single statement quantifying over all formulas.

Exercises for §4.4 →

4.5Choice as a Sentence, and Relative Consistency

For a logician the Axiom of Choice is interesting not for what it builds but for its status: a sentence that can be added to ZF, whose negation can equally be added, and neither of which ZF refutes. The equivalents — Zorn's lemma, the well-ordering theorem, every vector space has a basis, Tychonoff's theorem — are the business of the chapter The Axiom of Choice in the subject Set Theory. Here AC is an object of metamathematics.

Definition 4.24 (AC as an $L_{\in}$ -sentence). The Axiom of Choice is the sentence

\forall a (\forall x \in a \exists u (u \in x) \to \exists f (Fn (f) \land dom (f) = a \land \forall x \in a (f (x) \in x))),

where $Fn (f)$ , $dom (f) = a$ and $f (x) \in x$ abbreviate their $Δ_{0}$ definitions in terms of Kuratowski pairs. The quantifier $\exists f$ is unbounded, so AC as written is $Π_{2}$ in the Lévy hierarchy, and there is no reason to expect it to be absolute.

Proposition 4.25 (Finite choice is a schema of theorems of ZF). For each numeral $n$ , ZF proves: every family of exactly $n$ non-empty sets has a choice function.

Proof. Induct in the metatheory on $n$ . For $n = 0$ the empty function works. Suppose the claim proved for $n$ and let $a = {x_{1}, \dots, x_{n + 1}}$ have non-empty members. The hypothesis $\exists u (u \in x_{n + 1})$ is a single existential statement of the theory, so a proof may introduce a witness $u$ by existential instantiation — one witness, mentioned once, with no choice principle involved. The induction hypothesis gives a choice function $f$ for ${x_{1}, \dots, x_{n}}$ , and $f \cup {(x_{n + 1}, u)}$ is a set by Pairing and Union and is a choice function for $a$ .∎

Pitfall. That proposition is infinitely many theorems, one per numeral, proved by an induction in the metatheory. It is not the same statement as the single sentence "every finite family of non-empty sets has a choice function" — though that sentence is also a theorem of ZF, proved by induction inside the theory on the cardinality of the family. The distinction between a schema established in the metatheory and one sentence established internally runs through this whole chapter, and in the theorem ZFC is not finitely axiomatisable it is precisely what separates a theorem from a contradiction.

Everything provable about AC's status is relative. No argument establishes that ZFC is consistent, since that would entail $Con (ZF)$ , which is unprovable in ZF.

Definition 4.26 (Inner model). An inner model of ZF is a transitive class $M$ containing every ordinal such that $φ^{M}$ holds for every axiom $φ$ of ZF. As with relativisation generally, " $M$ is an inner model of ZF" abbreviates a schema of statements, one per axiom, and not a single sentence.

Theorem 4.27 (The inner-model method). Let $S$ and $T$ be theories in the same language and suppose there is a formula defining a class $M$ such that $S$ proves $M$ is non-empty and, for each axiom $τ$ of $T$ , $S ⊢ τ^{M}$ . Then $Con (S) \to Con (T)$ , and this implication is provable in a weak arithmetic.

Proof. Suppose $T$ were inconsistent, so there is a derivation of a contradiction from finitely many axioms $τ_{1}, \dots, τ_{k}$ of $T$ . Relativisation commutes with the rules of a first-order proof system: if $σ$ follows from $σ_{1}, \dots, σ_{m}$ by a rule, then $σ^{M}$ follows from $σ_{1}^{M}, \dots, σ_{m}^{M}$ — for the quantifier rules this uses that $M$ is non-empty, and for the propositional rules it is immediate, since relativisation commutes with the connectives. Relativising the derivation step by step therefore converts it into a derivation of a contradiction from $τ_{1}^{M}, \dots, τ_{k}^{M}$ , each of which $S$ proves. So $S$ is inconsistent. The whole transformation is a primitive recursive operation on proof codes, which is why the implication holds provably in arithmetic and not merely in the metatheory.∎

Theorem 4.28 (Gödel 1938, Cohen 1963). If ZF is consistent, then so are $ZF + AC$ and $ZF + \neg AC$ ; hence AC is independent of ZF. If ZFC is consistent, then so are $ZFC + CH$ and $ZFC + \neg CH$ ; hence CH is independent of ZFC.

Proof (Sketch). For the consistency of AC, Gödel defines the constructible hierarchy $L = ⋃_{α} L_{α}$ , where $L_{α + 1}$ is the set of subsets of $L_{α}$ definable over the structure $(L_{α}, \in)$ with parameters. One verifies that $L$ is an inner model of ZF and that ZF proves $AC^{L}$ — the well-ordering comes from the definability hierarchy itself, which orders each level canonically by the formulas and parameters defining its members. The inner-model method then yields $Con (ZF) \to Con (ZFC)$ ; the same model gives $Con (ZFC + CH)$ , since CH holds in $L$ . For the negations, Cohen's forcing starts from a countable transitive model of a sufficient finite fragment — supplied by the corollary Every finite fragment has a transitive set model — and adjoins generic sets, taking a symmetric submodel in the case of $\neg AC$ . Both constructions are carried out in the chapter Independence & Forcing; what is imported here is their shape, and the inner-model method above is the piece that converts a construction into a consistency statement.∎

Intuition. Consistency proofs of this kind never certify a theory. They trade: they show that if the trusted theory is safe, so is the doubted one. An inner model is a way of reinterpreting the doubted theory's vocabulary inside the trusted one, so that any proof of a contradiction would translate back into a contradiction we had already agreed was impossible.

Example 4.29 (Why "AC is independent" is not "AC is false"). A student argues: "Cohen produced a model of ZF in which choice fails, so choice is false." Locate the error.

Solution.

Independence is a property of a pair — a theory and a sentence — not of a sentence alone. AC is independent of ZF in exactly the sense that commutativity is independent of the group axioms.
A model of $ZF + \neg AC$ shows only that the axioms of ZF do not force AC. A model of $ZF + AC$ , namely $L$ , exists equally, and the two are on a level.
Whether AC is "true" is then a question about which structure, if any, mathematical practice intends — a question outside the theory. Mathematicians adopt AC because its consequences are indispensable and, given $Con (ZF)$ , no contradiction can arise from doing so.
Symmetrically, "ZFC $⊬$ CH" does not license asserting $\neg CH$ .

□

Example 4.30 (What a relative consistency statement costs). Explain why $Con (ZF) \to Con (ZFC)$ is provable but $Con (ZFC)$ is not, and why a transitive model of ZFC is a stronger assumption than $Con (ZFC)$ .

Solution.

The implication is proved by a syntactic transformation of proofs, as in the theorem The inner-model method; it never asserts that any proof-free situation obtains, so Gödel's second theorem does not apply to it.
$Con (ZFC)$ itself is an arithmetical sentence which, by Gödel's second theorem, ZFC does not prove if it is consistent.
A transitive model of ZFC is stronger still. If one exists, then ZFC is not merely consistent: its arithmetical consequences are true, since a transitive model computes $ω$ and the arithmetic on it correctly, by absoluteness of $Δ_{0}$ notions. So "there is a transitive model" implies $Con (ZFC)$ , implies $Con (ZFC + Con (ZFC))$ , and so on up.
This is why careful statements say "assume there is a countable transitive model of a sufficiently large finite fragment of ZFC" — by the corollary Every finite fragment has a transitive set model, that assumption costs nothing.

□

Summary. AC is a single $Π_{2}$ sentence of $L_{\in}$ , and ZF and ZFC are different theories. Relative consistency is established by the inner-model method, which relativises a hypothetical contradiction back into the base theory; $L$ gives $Con (ZF) \to Con (ZFC)$ and forcing gives the other direction. Independence is a statement about provability, never a truth value.

Exercises for §4.5 →

4.6Ordinals Are Absolute, Cardinals Are Not

Ordinals and cardinals are developed in the chapter Ordinals & Cardinals of the subject Set Theory: an ordinal is a transitive set well-ordered by $\in$ , a cardinal is an ordinal not in bijection with any smaller ordinal, and the alephs enumerate the infinite cardinals. What concerns us here is a single contrast with far-reaching consequences — the notion of ordinal is absolute for transitive models, and the notion of cardinal is not.

Theorem 4.31 (Being an ordinal is absolute). Over ZF, the formula " $x$ is an ordinal" is equivalent to a $Δ_{0}$ formula, hence is absolute for transitive classes. Consequently, for a transitive class $M$ one has $Ord^{M} = Ord \cap M$ , and this is either an ordinal or the whole class $Ord$ .

Proof. With Foundation available, every set is well-founded, so " $\in$ well-orders $x$ " reduces to " $\in$ linearly orders $x$ ". Hence " $x$ is an ordinal" is equivalent to

\forall u \in x \forall v \in u (v \in x) \land \forall u \in x \forall v \in x (u \in v \lor u = v \lor v \in u),

whose quantifiers are all bounded. By the theorem $Δ_{0}$ formulas are absolute for transitive classes, $M$ and $V$ agree about it for every $x \in M$ , which is the first claim. For the second: $Ord \cap M$ is transitive, since the members of an ordinal are ordinals and $M$ is transitive, and it is linearly ordered by $\in$ ; a transitive set of ordinals is an ordinal, and a transitive proper class of ordinals is $Ord$ .∎

Definition 4.32 (The height of a model). For a transitive set model $M$ , the ordinal $Ord \cap M$ is the height of $M$ . An inner model is exactly a transitive class model of height $Ord$ .

A countable transitive model therefore has countable height, and yet it satisfies "there are uncountably many ordinals". The mechanism is the failure of absoluteness one level up.

Theorem 4.33 (Cardinality is downward absolute only). Let $M$ be a transitive class. Then:

" $f$ is a bijection from $x$ onto $y$ " is $Δ_{0}$ , hence absolute.
" $κ$ is a cardinal" is $Π_{1}$ , hence downward absolute: if $κ \in M$ is a cardinal in $V$ , then $M ⊨$ " $κ$ is a cardinal".
The converse fails: there are a transitive $M$ and a $κ \in M$ with $M ⊨$ " $κ$ is a cardinal" while $κ$ is countable in $V$ .

Proof. (1) Being a set of ordered pairs, being single-valued, having domain $x$ and range $y$ , and injectivity are all expressible with quantifiers bounded by $f$ , $x$ and $y$ , using the $Δ_{0}$ definition of the Kuratowski pair.

(2) " $κ$ is a cardinal" says $κ$ is an ordinal and there is no pair $(β, f)$ with $β \in κ$ and $f$ a bijection from $β$ onto $κ$ . Pushing the negation inward puts it in the form $\forall w ψ$ with $ψ$ a $Δ_{0}$ formula, using part (1) and the absoluteness of "is an ordinal"; so it is $Π_{1}$ , and the corollary One unbounded quantifier: up and down makes it downward absolute. Concretely: a bijection witnessing failure inside $M$ is a genuine bijection in $V$ by part (1), so if $V$ has no such bijection, neither does $M$ .

(3) Let $M$ be a countable transitive model of ZFC and let $κ = (ω_{1})^{M}$ , the least ordinal $M$ believes is uncountable. By the theorem Being an ordinal is absolute, $κ$ is a genuine ordinal, and $κ \subseteq M$ by transitivity, so $κ$ is countable in $V$ and is not a cardinal there. Inside $M$ , no bijection from a smaller ordinal onto $κ$ exists, so $M ⊨$ " $κ$ is a cardinal".∎

Intuition. Cardinality asks for the non-existence of a bijection, and non-existence claims are exactly what a model can get wrong by being too small. Adding sets to a model can only destroy cardinals, never create them: a new bijection can collapse two cardinals into one, but no newly added set can un-do a bijection that was already present.

Corollary 4.34 (Inner models preserve cardinals downward). If $M$ is an inner model of ZF and $κ$ is a cardinal in $V$ , then $κ$ is a cardinal in $M$ . Hence $(ω_{1})^{M} \leq ω_{1}$ for every inner model $M$ . The converse fails in general.

Proof. The first claim is part (2) of the theorem Cardinality is downward absolute only, since an inner model is in particular a transitive class. For the second, $(ω_{1})^{M}$ is the least ordinal $M$ regards as uncountable; $ω_{1}$ is uncountable in $V$ , hence uncountable in $M$ by the first claim, hence at least the least such ordinal of $M$ . The converse fails because $M$ may simply lack a bijection that $V$ has: an ordinal $M$ believes to be a cardinal need not be one in $V$ , exactly as in part (3) above.∎

Example 4.35 (Counting inside and outside a countable model). Let $M$ be a countable transitive model of ZFC and $κ = (ω_{1})^{M}$ . Compute the cardinality of $κ$ as evaluated in $V$ , and decide whether $M ⊨$ " $κ$ is countable".

Solution.

$κ$ is an ordinal of $M$ and $M$ is transitive, so every element of $κ$ lies in $M$ ; since $M$ is countable, $κ$ is a countable set. It is infinite, since $ω \in κ$ . Hence $∣ κ ∣ = ℵ_{0}$ as computed in $V$ .
$M ⊨$ " $κ$ is uncountable", because $κ$ was chosen as the least ordinal of $M$ admitting no bijection with $ω$ inside $M$ . So the answer to the second question is no.
The two are compatible: the bijection $ω \to κ$ exists in $V$ but not in $M$ . The sentence " $κ$ is countable" is $Σ_{1}$ , hence upward absolute — true in $V$ , and there is no reason for it to be true in the smaller $M$ .

□

Remark (Cardinal collapse and preservation). This is exactly the phenomenon forcing exploits. A forcing extension $M [G]$ may contain a surjection $ω \to (ω_{1})^{M}$ , in which case $(ω_{1})^{M}$ is no longer a cardinal in $M [G]$ — the cardinal has been collapsed. Showing that a given forcing does not collapse cardinals is a standard proof obligation, usually discharged by the countable chain condition; the chapter Independence & Forcing gives the argument. Cohen's model for $\neg CH$ is designed so that the cardinals of $M$ survive while the continuum is pushed above $ℵ_{1}$ .

Pitfall. " $κ$ is a cardinal" and " $κ = ℵ_{1}$ " behave differently. The first is downward absolute; the second is absolute in neither direction, because $ℵ_{1}$ is defined as the least uncountable cardinal, and a model missing bijections will name the wrong ordinal. Always relativise the notation — write $(ω_{1})^{M}$ , never a bare $ω_{1}$ , when working inside a model.

Summary. Being an ordinal is $Δ_{0}$ and therefore absolute, so all transitive models agree about ordinals and each has a height. Being a cardinal is $Π_{1}$ and only downward absolute, so models overestimate cardinality; the gap between $(ω_{1})^{M}$ and $ω_{1}$ is the engine of the Skolem paradox, of $L$ 's slimness, and of cardinal collapse in forcing.

Exercises for §4.6 →

4.7Induction and Recursion as Theorem Schemas

Transfinite induction and transfinite recursion are usually presented as tools for building objects. Seen from logic they are results about the theory: the first is a theorem schema derived from Foundation, and the second is a theorem schema whose proof is the principal consumer of Replacement. Both are schemas for the same reason Separation is — they quantify over formulas.

Theorem 4.36 ( $\in$ -induction schema). For each formula $φ (x, \overset{p}{ˉ})$ , ZF proves

\forall x (\forall y \in x φ (y, \overset{p}{ˉ}) \to φ (x, \overset{p}{ˉ})) \to \forall x φ (x, \overset{p}{ˉ}) .

Proof. Assume the hypothesis and suppose some $a$ has $\neg φ (a, \overset{p}{ˉ})$ . Let $t$ be the transitive closure of ${a}$ , which exists by Replacement, Union and Infinity, and put $S = {x \in t : \neg φ (x, \overset{p}{ˉ})}$ , a set by Separation, with $a \in S$ so $S \neq = \emptyset$ . By Foundation there is an $\in$ -minimal $x \in S$ , that is, one with $x \cap S = \emptyset$ . Every $y \in x$ lies in $t$ , because $t$ is transitive and $x \in t$ , and $y \in / S$ by minimality; so $φ (y, \overset{p}{ˉ})$ holds for every $y \in x$ . The hypothesis then gives $φ (x, \overset{p}{ˉ})$ , contradicting $x \in S$ .∎

Corollary 4.37 (Transfinite induction on ordinals). For each formula $φ$ , ZF proves: if $φ (0)$ holds, and $φ (β) \to φ (β + 1)$ for every ordinal $β$ , and $φ (λ)$ holds whenever $λ$ is a limit ordinal with $φ (β)$ for all $β < λ$ , then $φ (α)$ holds for every ordinal $α$ .

Proof. Apply the $\in$ -induction schema to the formula " $x$ is an ordinal $\to φ (x)$ ". For an ordinal $α$ , the hypothesis $\forall y \in α φ (y)$ says exactly that $φ (β)$ holds for all $β < α$ , since the members of $α$ are precisely the ordinals below it. The three clauses then cover the trichotomy " $α = 0$ , $α$ a successor, $α$ a limit", which is itself a theorem of ZF.∎

Pitfall. The three-clause form is a convenience, not the content. What the $\in$ -induction schema gives is the single clause "if $φ$ holds below $x$ then $φ$ holds at $x$ "; the limit case is not an extra burden imposed by infinity but simply the case where "below" has no largest element. An argument that verifies a successor step and stops is not an incomplete induction — it is not an induction at all.

Theorem 4.38 (Transfinite recursion schema). Let $γ (x, y)$ be a formula with $\forall x \exists! y γ (x, y)$ , defining a class function $G$ . Then ZF proves there is a class function $F$ on $Ord$ , definable from $γ$ , with

F (α) = G (F ↾ α) for every ordinal α,

and $F$ is unique with this property. Here " $F$ is a class function" again abbreviates a formula, so the theorem is one statement per $γ$ .

Proof (Sketch). Call a set $h$ an $α$ -approximation if $h$ is a function with domain $α$ and $h (ξ) = G (h ↾ ξ)$ for every $ξ < α$ . Any two approximations agree on the intersection of their domains, by the corollary Transfinite induction on ordinals applied to " $h (ξ) = h^{'} (ξ)$ ", so an $α$ -approximation is unique if it exists. Existence for every $α$ is proved by transfinite induction: at $0$ take the empty function; at a successor $α + 1$ extend the $α$ -approximation by the single value $G (h)$ ; at a limit $λ$ take the union of the approximations below $λ$ , which is a function because they cohere. The essential step is that this union is a set: the assignment $ξ \mapsto$ (the unique $ξ$ -approximation) is a definable functional relation on the set $λ$ , so Replacement collects the approximations into a set and Union merges them. Finally define $F (α)$ to be $h (α)$ for any $(α + 1)$ -approximation $h$ ; coherence makes this well defined, and uniqueness of $F$ is another transfinite induction. The part not written out is the routine verification that the extended function at a successor is again an approximation.∎

Intuition. Replacement is what converts "for each $ξ$ there is a stage" into "the stages form a set". Without it one can still speak of each approximation individually, but never gather them, and a recursion that cannot gather its own history stalls at the first limit ordinal. That is the precise sense in which Replacement is the axiom of length: Power Set makes the universe wide, Replacement makes it tall.

Example 4.39 (Zermelo set theory cannot reach $V_{ω + ω}$ ). Zermelo set theory Z is ZFC with Replacement deleted and Separation retained. Show that $V_{ω + ω}$ is a model of Z, and deduce that Z does not prove the range of the recursion $F (0) = ω$ , $F (n + 1) = P (F (n))$ is a set.

Solution.

$V_{ω + ω}$ is transitive, and it satisfies Extensionality and Foundation because those are $Δ_{0}$ -style conditions inherited by transitive sets, and Separation because a subset of an element of $V_{ω + ω}$ has no greater rank.
It satisfies Pairing, Union and Power Set because $rank ({a, b})$ , $rank (⋃ a)$ and $rank (P (a))$ each exceed $max (rank (a), rank (b))$ by at most $2$ , and $ω + ω$ is a limit ordinal, so the results stay below it. Infinity holds since $ω \in V_{ω + 1}$ , and Choice holds relativised if it holds in $V$ .
Each $F (n)$ has rank $ω + n$ and so lies in $V_{ω + ω}$ . But ${F (n) : n \in ω}$ has rank $ω + ω$ and is therefore not an element of $V_{ω + ω}$ .
So $V_{ω + ω} ⊨ Z$ while refuting that instance of Replacement. By soundness, Z does not prove the range of this recursion is a set — the theorem Transfinite recursion schema genuinely needs Replacement, and Z is strictly weaker than ZF.

□

Example 4.40 (Why the recursion theorem must be a schema). Explain why transfinite recursion cannot be stated as a single sentence of $L_{\in}$ covering all class functions $G$ , and why the analogous statement for set functions is a single theorem.

Solution.

A class function $G$ is presented by a formula $γ$ , and no set-sized object in $V$ codes "all definable class functions"; by Tarski's undefinability theorem there is not even a definable truth predicate for $L_{\in}$ from which one could build such a coding.
So "for every class function $G$ there is $F$ with $F (α) = G (F ↾ α)$ " quantifies over formulas, which first-order syntax forbids — exactly the situation of Separation and Replacement.
The remedy is the same: one theorem per $γ$ , generated by a template that can be checked mechanically in the metatheory.
For a set function $g$ the obstacle vanishes, because $g$ is an object a first-order quantifier can range over. "For every set $A$ , every $a \in A$ and every $g : A^{< ω} \to A$ there is a unique $f : ω \to A$ with $f (0) = a$ and $f (n + 1) = g (f ↾ (n + 1))$ " is a single theorem of ZF. This is why ordinary recursion on $N$ raises none of these issues.

□

Remark (Where the ordinal arithmetic lives). The uses of these schemas — ordinal addition, multiplication and exponentiation, Cantor normal form, the hierarchies $V_{α}$ and $L_{α}$ , the rank function — are developed in the chapters Ordinals & Cardinals and ZFC Axioms of the subject Set Theory. The logical content isolated here is that every one of them is a definition by a schema instance, and that each needs Replacement precisely at its limit stages.

Summary. $\in$ -induction follows from Foundation by way of the transitive closure, and transfinite induction on ordinals is its restriction to $Ord$ . Transfinite recursion is a theorem schema, one instance per defining formula, whose proof uses Replacement to gather the approximations at limit stages — a use that $V_{ω + ω} ⊨ Z$ shows to be unavoidable.

Exercises for §4.7 →

Common Mistakes

Treating a schema as a sentence. "Separation says that for every property…" is metatheory. Inside $L_{\in}$ there is one axiom per formula, and no sentence quantifying over formulas exists. The same error turns the Reflection Principle into a claim that some $V_{α}$ models all of ZFC, which is false.
Thinking ZFC proves it has a model. If ZFC is consistent it has a model, by the completeness theorem applied in the metatheory — but ZFC cannot prove this, since it would then prove $Con (ZFC)$ . Every theorem about transitive models carries "if such a model exists" as a hypothesis.
Reading the Skolem paradox as a contradiction. A countable model satisfying " $P (ω)$ is uncountable" is consistent, because the bijection that would refute the model's belief lies outside it. Uncountability is not absolute.
Forgetting transitivity in an absoluteness argument. $Δ_{0}$ absoluteness fails badly for non-transitive models; the proof uses transitivity exactly to import an external witness of a bounded quantifier.
Blaming Foundation for Russell's paradox. It is Separation, replacing unrestricted comprehension, that blocks the paradoxical collection — Foundation rules out $x \in x$ and membership cycles, which is a different job, and ZF without Foundation is still free of Russell's contradiction.
Confusing independence with falsity. "ZF $⊬$ AC" and "ZFC $⊬$ CH" are statements about provability. Neither licenses asserting the negation, any more than the existence of a non-abelian group refutes commutativity for all groups.
Asserting absolute consistency. Gödel's construction of $L$ and Cohen's forcing both prove relative consistency: $Con (ZF) \to Con (ZFC)$ and so on. Dropping the hypothesis produces a claim that is provably unprovable.
Using $ω_{1}$ unrelativised inside a model. Write $(ω_{1})^{M}$ . Cardinality is only downward absolute, so a model's $ℵ_{1}$ is generally a countable ordinal when viewed from outside.
Stopping an induction at the successor step. In the $\in$ -induction schema there is only one step, "everything below implies here"; a limit ordinal is the case where "below" has no largest element, not an optional extra.

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

Practice this chapter