Chapter 2

ZFC Axioms

The nine axioms and what each one buys: extensionality and the uniqueness of the empty set; separation blocking Russell and proving there is no universal set; intersection and difference needing no axioms of their own; the Kuratowski ordered pair with its degenerate case; Cartesian products from power set and separation; foundation forbidding membership cycles; the von Neumann naturals satisfying the Peano axioms; the cumulative hierarchy with the sizes of its finite stages; and replacement as a schema reaching sets separation cannot.

Introduction

Almost every other chapter in mathematics starts by assuming that some objects exist. Analysis assumes the real numbers; algebra assumes a group; geometry assumes a plane and its points. This chapter is the one that has nothing to assume. It begins with a formal language containing a single relation symbol, $\in$ , and a list of axioms saying which sets that language can be made to produce, and it ends with the natural numbers, the ordered pair, the Cartesian product, the power set tower and the cumulative hierarchy — every one of them constructed, not postulated.

The reason to do this at all is that the alternative failed, publicly and irreparably. Naive set theory took as its single principle that any property whatsoever determines a set: for each formula $φ (x)$ there is a set ${x : φ (x)}$ . In 1901 Russell pointed at $φ (x) \equiv x \in / x$ and the whole edifice fell over in two lines. The Zermelo–Fraenkel axioms are the repair. They are not a list of everything true about sets; they are a carefully rationed licence to build sets, restrictive enough that Russell's construction is simply not one of the permitted moves, and generous enough that the rest of mathematics still goes through unchanged.

Two habits of reading will help throughout. First, every axiom here is an existence statement or a uniqueness statement — it says either "given these sets, this further set exists" or "two sets agreeing in this way are the same set". Nothing else is on offer. Second, "proof" in this chapter almost always means derivation from the axioms: we will prove that intersections exist, that the ordered pair works, that no set is a member of itself, that $ω$ satisfies the Peano axioms. Those are theorems of ZF, and the pleasure of the subject is watching ordinary mathematical furniture appear from a list of nine sentences.

Throughout, lower-case letters $a, b, x, y, z$ range over sets — in ZF everything is a set, so there is no second sort of object to range over — and $φ$ denotes a formula of the first-order language of set theory. We write ZF for Zermelo–Fraenkel without the axiom of choice, and ZFC for ZF together with choice, and we will be careful to say which of the two a result needs.

2.1The point of an axiom system

The language of set theory is deliberately tiny. Its only non-logical symbol is the binary relation $\in$ ; the rest is the ordinary apparatus of first-order logic — variables, $\land, \lor, \neg, \to$ , the quantifiers $\forall$ and $\exists$ , and equality. There is no symbol for $\emptyset$ , none for $\cup$ , none for $P$ , none for $N$ . Every one of those is an abbreviation, introduced only after an axiom has been shown to guarantee that the object it names exists and a theorem has shown it to be unique.

Definition 2.1 (The language of set theory). The language $L_{\in}$ has variables $x, y, z, \dots$ , the logical connectives and quantifiers, the equality symbol $=$ , and one binary relation symbol $\in$ . Atomic formulas are exactly $x \in y$ and $x = y$ ; every other formula is built from these by connectives and quantifiers.

Notation. We use the standard abbreviations. $x \in / y$ means $\neg (x \in y)$ ; $x \subseteq y$ means $\forall z (z \in x \to z \in y)$ ; $\exists! x φ (x)$ means there is exactly one $x$ with $φ (x)$ . Note that $\subseteq$ is defined, not primitive: subsethood is a formula, whereas membership is a symbol.

Intuition. Think of the axioms as the rules of a construction kit. You are given a supply of pieces (at the start, essentially none) and a list of permitted operations: given two pieces you may staple them into a pair, given a box of boxes you may tip it out into one box, given a piece you may collect all of its sub-pieces. The question the axioms answer is never "is this collection real?" but "can this collection be reached from nothing by finitely many permitted moves?"

Three features of this setup are worth stating explicitly before anything else, because each one surprises students who meet it for the first time.

Everything is a set. There are no atoms, no "urelements", no numbers sitting outside the universe waiting to be gathered. When we build $3$ , it will be a set, with three members. When we build the ordered pair $(a, b)$ , it will be a set. This is an economy, not a philosophical claim: one sort of object means one relation to axiomatise.

The axioms are schematic in places. Two of the nine items on the list — Separation and Replacement — are not single sentences but infinite families, one sentence for each formula $φ$ of the language. First-order logic cannot quantify over formulas, so an infinite family is the only way to say what those axioms say. This costs nothing in practice and has a striking consequence taken up in the section on the schema nature of Replacement.

The axioms cannot prove their own consistency. By Gödel's second incompleteness theorem, if ZFC is consistent then ZFC cannot prove that it is. We work in ZFC because a century of hard use has not broken it, not because it comes with a certificate.

Remark. The system is also not complete: there are sentences, the continuum hypothesis being the famous one, that ZFC neither proves nor refutes. That is not a defect peculiar to set theory. Any consistent, effectively axiomatised theory strong enough to encode arithmetic has the same property.

Exercises for §2.1 →

2.2The nine axioms, listed once

Here is the whole list. Read it once now without trying to absorb it; the remaining sections unpack five of these items in detail, and the others are used constantly in the arguments along the way.

Definition 2.2 (The axioms of ZFC).

Extensionality. $\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y)$ — a set is determined by its members.
Pairing. $\forall a \forall b \exists p \forall z (z \in p \leftrightarrow (z = a \lor z = b))$ — the set ${a, b}$ exists.
Union. $\forall F \exists u \forall z (z \in u \leftrightarrow \exists y (y \in F \land z \in y))$ — the set $⋃ F$ exists.
Power set. $\forall a \exists p \forall z (z \in p \leftrightarrow z \subseteq a)$ — the set $P (a)$ exists.
Infinity. $\exists I (\emptyset \in I \land \forall x (x \in I \to x \cup {x} \in I))$ — an inductive set exists.
Separation (schema). For each formula $φ (z, \overset{p}{ˉ})$ : $\forall \overset{p}{ˉ} \forall a \exists s \forall z (z \in s \leftrightarrow (z \in a \land φ (z, \overset{p}{ˉ})))$ .
Replacement (schema). For each formula $φ (x, y, \overset{p}{ˉ})$ : if $φ$ defines a function on $a$ , then the image of $a$ under it is a set.
Regularity (Foundation). $\forall x (x \neq = \emptyset \to \exists y (y \in x \land y \cap x = \emptyset))$ — every nonempty set has an $\in$ -minimal member.
Choice. Every family of nonempty sets has a choice function. ZF is items 1–8; ZFC is all nine.

Counting these nine items is the standard bookkeeping, and it is worth fixing: of the nine, exactly two are schemas, namely Separation and Replacement, so the list is nine axioms in the informal sense but infinitely many sentences in the formal one. Some presentations shorten the list, because Pairing and Separation are both derivable from Replacement together with Power set; others lengthen it by splitting Infinity or by adding the existence of the empty set as a separate item. Nothing below depends on which bookkeeping you prefer, provided you say which one you are using.

Note (Where the empty set comes from). The list above does not include " $\emptyset$ exists". It does not need to. First-order logic assumes a nonempty domain, so some set $a$ exists; Separation applied to $a$ with the formula $φ (z) \equiv z \neq = z$ produces a set with no members at all. Extensionality then shows it is unique, and only at that point is the symbol $\emptyset$ legitimate.

Example 2.3 (Which axiom licenses which set). You have the sets $a$ and $b$ . Name the axiom that produces each of ${a}$ , ${a, b}$ , $a \cup b$ , and $P (a)$ .

Solution.

${a, b}$ is exactly Pairing applied to $a$ and $b$ .
${a}$ is Pairing applied to $a$ and $a$ : the axiom yields a set whose members are the $z$ with $z = a \lor z = a$ , that is, $z = a$ . No separate singleton axiom is needed.
$a \cup b$ takes two steps: Pairing gives ${a, b}$ , then Union applied to ${a, b}$ gives $⋃ {a, b}$ , whose members are the $z$ lying in $a$ or in $b$ .
$P (a)$ is Power set applied to $a$ , and no combination of the other axioms produces it — this is the one operation that genuinely increases size.

□

Pitfall. Union takes a set of sets and flattens it one level: $⋃ F = {z : \exists y \in F, z \in y}$ . It is not the binary $\cup$ . The binary operation is the two-step derived construction in the example above, which is why " $\cup$ " is an abbreviation and " $⋃$ " is the axiom.

Exercises for §2.2 →

2.3Why axioms at all: the paradoxes

The single principle the axioms replace is unrestricted comprehension: for every formula $φ$ , the collection ${x : φ (x)}$ is a set. It is an appealing principle, it is how most people think about sets before they are taught otherwise, and it is inconsistent.

Theorem 2.4 (Russell's paradox). Unrestricted comprehension is inconsistent: there is no set $R$ such that for all $x$ , $x \in R \leftrightarrow x \in / x$ .

Proof. Suppose such an $R$ existed. Instantiate the defining equivalence at $x = R$ , which is legitimate because $R$ is a set and the equivalence was asserted for all sets:

R \in R \leftrightarrow R \in / R .

If $R \in R$ , the right-hand side gives $R \in / R$ , a contradiction. If $R \in / R$ , the equivalence gives $R \in R$ , again a contradiction. Both cases are impossible and one of them must hold, so no such $R$ exists. Unrestricted comprehension asserts that $R$ exists for the formula $φ (x) \equiv x \in / x$ , so unrestricted comprehension is false.∎

The repair is to weaken comprehension so that a formula can only ever carve a subset out of a set already in hand. That is exactly Separation.

Definition 2.5 (Separation, in words). For each formula $φ (z, \overset{p}{ˉ})$ , and for every set $a$ and parameters $\overset{p}{ˉ}$ , there is a set

{z \in a : φ (z, \overset{p}{ˉ})}

whose members are precisely those members of

a

satisfying

φ

. The bounding set

a

is not optional: it is the entire content of the axiom.

With the bound in place, Russell's argument no longer produces a contradiction. It produces a theorem, and a strong one.

Theorem 2.6 (Separation blocks Russell, and proves there is no universal set). Work in ZF, indeed in Extensionality plus Separation alone. Then:

For every set $a$ , the set $R_{a} = {z \in a : z \in / z}$ exists and satisfies $R_{a} \in / a$ .
There is no set $V$ with $\forall x (x \in V)$ .

Proof. For (1), $R_{a}$ exists by Separation. Suppose, for contradiction, that $R_{a} \in a$ . Ask whether $R_{a} \in R_{a}$ . By the defining property of $R_{a}$ ,

R_{a} \in R_{a} \leftrightarrow (R_{a} \in a \land R_{a} \in / R_{a}) .

Since we have assumed $R_{a} \in a$ , the right-hand conjunct $R_{a} \in a$ is true, so the equivalence collapses to $R_{a} \in R_{a} \leftrightarrow R_{a} \in / R_{a}$ , which is a contradiction exactly as in Russell's paradox. Hence the assumption fails and $R_{a} \in / a$ .

For (2), suppose $V$ were a set containing every set. Apply (1) with $a = V$ : we obtain a set $R_{V}$ with $R_{V} \in / V$ . But $R_{V}$ is a set, and $V$ contains every set, so $R_{V} \in V$ — a contradiction. Therefore no such $V$ exists.∎

Read part (1) again: it says that from any set $a$ , Separation manufactures a set that is not a member of $a$ . So no set can be all-inclusive, and the paradox has been converted from a disaster into a diagonal argument. This is the pattern that repeats throughout the subject — Cantor's theorem later in this chapter has exactly the same shape.

Intuition. Unrestricted comprehension treats a property as a net that can be cast over the whole universe at once. Separation makes you first point at a bucket, then fish inside it. Russell's net came back holding a contradiction; Russell's bucket comes back holding a proof that the bucket was too small — which is a true and useful thing to learn.

Remark. The collection ${x : x \in / x}$ is not nothing; it is a proper class, a collection definable by a formula but too large to be a set. Classes are a convenience of the metalanguage in ZFC: writing $V$ or $Ord$ is shorthand for a formula, never a term. Von Neumann–Bernays–Gödel set theory (NBG) makes classes into official objects and is a conservative extension of ZFC, proving exactly the same theorems about sets.

Example 2.7 (Burali-Forti, the same trap in ordinal clothing). Explain why there is no set of all ordinals, given that any set of ordinals is itself well-ordered by $\in$ and that the ordinals are exactly the transitive sets well-ordered by $\in$ .

Solution.

Suppose $Ord$ were a set. Every member of an ordinal is an ordinal, so $Ord$ is transitive, and it is well-ordered by $\in$ because any set of ordinals is.
Therefore $Ord$ satisfies the definition of an ordinal, so $Ord \in Ord$ .
But no ordinal is a member of itself, since $\in$ well-orders it and a well-order is irreflexive. Contradiction, so $Ord$ is a proper class.
The moral matches the theorem Separation blocks Russell, and proves there is no universal set: the trouble is always a collection that would have to contain a diagonal object built from itself.

□

Pitfall. "Russell's paradox shows that some sets contain themselves" is backwards. It shows that the collection of non-self-membered sets is not a set. Whether any set contains itself is a separate question, settled negatively by Regularity later in this chapter, and ZF minus Regularity does not settle it at all.

Exercises for §2.3 →

2.4ZF, ZFC, and what choice is for

The ninth axiom stands apart from the first eight. Axioms 1–8 tell you how to build a specific set from specific ingredients, and in every case the set built is uniquely determined by the ingredients. Choice does not: it asserts that a selection exists without giving any rule for making it.

Definition 2.8 (Axiom of Choice). For every set $F$ of nonempty sets there is a function $f$ with domain $F$ such that $f (a) \in a$ for every $a \in F$ . Such an $f$ is a choice function for $F$ .

Intuition. Given infinitely many pairs of shoes you need no axiom: pick the left one from each pair, a rule anyone can state. Given infinitely many pairs of socks there is no rule, and Choice is precisely the assertion that a selection exists anyway. Russell's image is exact: Choice is needed only when the family is infinite and the members carry no distinguishing structure.

For finite families, no axiom is needed at all, and the proof shows precisely where the finiteness is used.

Proposition 2.9 (Finite choice is a theorem of ZF). Let $F$ be a finite set of nonempty sets. Then ZF proves that a choice function for $F$ exists.

Proof. Induct on $n = ∣ F ∣$ . If $n = 0$ then $F = \emptyset$ and the empty function is a choice function vacuously.

Suppose the claim holds for families of size $n$ and let $∣ F ∣ = n + 1$ . Pick any $a \in F$ — this is a single existential instantiation inside a proof, which first-order logic permits, not an appeal to Choice. Since $a \neq = \emptyset$ there is some $c \in a$ , again by a single instantiation. By the inductive hypothesis $F ∖ {a}$ has a choice function $g$ , and $g \cup {(a, c)}$ is a choice function for $F$ ; it is a set by Pairing and Union, and a function because $a \in / F ∖ {a}$ .

The induction makes $n + 1$ instantiations for a family of size $n + 1$ . That is the whole difference: a proof is a finite object, so it can make finitely many arbitrary picks and no more. An infinite family needs infinitely many simultaneous picks, and that is what Choice supplies.∎

Note (Equivalents and independence). Over ZF, the axiom of choice is equivalent to Zorn's lemma, to the well-ordering theorem (every set can be well-ordered), to the statement that every vector space has a basis, and to the statement that every surjection has a right inverse. Gödel (1938) showed ZF cannot refute Choice, and Cohen (1963) showed ZF cannot prove it; the same pair of results holds for the continuum hypothesis over ZFC. So Choice is genuinely independent, and citing it is a real hypothesis, not a formality.

Which results in this chapter need Choice? Almost none — and that is worth noticing. Everything about Extensionality, Pairing, Union, Separation, the Kuratowski pair, Cartesian products, Regularity, the von Neumann naturals, $ω$ , the Peano axioms, Cantor's theorem and the cumulative hierarchy below is proved in ZF alone. Choice enters when you want to compare arbitrary cardinals, to well-order the reals, or to choose from an infinite family with no canonical member.

Example 2.10 (Spotting a hidden use of Choice). A sequence of nonempty sets $A_{1}, A_{2}, A_{3}, \dots$ is given, and someone writes "choose $x_{n} \in A_{n}$ for each $n$ and form the sequence $(x_{n})$ ". Is that a theorem of ZF?

Solution.

No. The phrase "for each $n$ " asks for infinitely many simultaneous selections, which is exactly the countable axiom of choice, $AC_{ω}$ .
It becomes a theorem of ZF the moment the selection is definable: if each $A_{n}$ is a nonempty set of natural numbers, take $x_{n} = min A_{n}$ , and the sequence exists by Replacement with no choice at all.
The lesson is that Choice is invisible in the grammar of English. "Choose one from each" is either free or an axiom, depending entirely on whether a rule exists.

□

Pitfall. ZFC is not "ZF with more sets". Adding Choice adds no new sets; it adds a new assertion about functions that were already candidates for existence. A model of ZF failing Choice is not missing objects so much as missing the coordination between them.

Exercises for §2.4 →

2.5Extensionality: the statement

The first axiom is the only one on the list that is not an existence statement. It says what it means for two sets to be the same.

Definition 2.11 (Axiom of Extensionality). For all sets $x$ and $y$ ,

\forall z (z \in x \leftrightarrow z \in y) ⟶ x = y .

In words: if $x$ and $y$ have exactly the same members, they are equal.

The converse direction, that equal sets have the same members, is not part of the axiom — it is a consequence of the logical axioms for equality, which say that equals may be substituted for equals in any formula. Extensionality supplies only the direction that logic cannot: it turns agreement of members into identity.

Intuition. A set is a bag with no colour, no label, no date of manufacture and no memory of how it was filled. Two bags holding the same things are the same bag. Everything that distinguishes objects in ordinary life — a name, a construction, an ordering, a multiplicity — is invisible to a set, and Extensionality is the axiom that makes that invisibility official.

The immediate reformulation is the one used constantly in practice: it turns set equality into a pair of inclusions, which is why almost every proof that two sets are equal is written in two halves.

Proposition 2.12 (Equality by double inclusion). For all sets $x$ and $y$ , $x = y$ if and only if $x \subseteq y$ and $y \subseteq x$ .

Proof. ( $\Leftarrow$ ) Suppose $x \subseteq y$ and $y \subseteq x$ . Let $z$ be arbitrary. If $z \in x$ then $z \in y$ by the first inclusion; if $z \in y$ then $z \in x$ by the second. Hence $\forall z (z \in x \leftrightarrow z \in y)$ , and Extensionality gives $x = y$ .

( $\Rightarrow$ ) Suppose $x = y$ . By the substitution property of equality, $z \in x$ and $z \in y$ are the same statement for every $z$ , so each of $x \subseteq y$ and $y \subseteq x$ holds.∎

Remark. Extensionality is what makes $\subseteq$ a partial order rather than merely a preorder: reflexivity and transitivity are pure logic, but antisymmetry — the proposition Equality by double inclusion read from right to left — is exactly the axiom. Drop Extensionality and you may have distinct sets with identical members, and $\subseteq$ stops separating points.

Exercises for §2.5 →

2.6What extensionality forces

Three consequences follow immediately, and together they explain why set notation behaves the way it does: repetition is invisible, order is invisible, and the empty set is unique.

Proposition 2.13 (Repetition and order are invisible). For all sets $a$ and $b$ :

${a, a} = {a}$ .
${a, b} = {b, a}$ .
${a, b, a} = {a, b}$ .

Proof. For (1), Pairing applied to $a$ and $a$ gives a set $p$ with $z \in p \leftrightarrow (z = a \lor z = a)$ , and Pairing applied to $a$ and $a$ in the singleton reading gives $q$ with $z \in q \leftrightarrow z = a$ . The two right-hand conditions $z = a \lor z = a$ and $z = a$ are logically equivalent, so $\forall z (z \in p \leftrightarrow z \in q)$ , and Extensionality gives $p = q$ . Writing the left side as ${a, a}$ and the right as ${a}$ is exactly the claim.

For (2), the membership condition for ${a, b}$ is $z = a \lor z = b$ and for ${b, a}$ it is $z = b \lor z = a$ . Disjunction is commutative, so the conditions are equivalent and Extensionality applies.

For (3) the condition is $z = a \lor z = b \lor z = a$ , equivalent to $z = a \lor z = b$ by idempotence of $\lor$ ; apply Extensionality again.∎

Every part of that proof has the same two-step shape: reduce the two sets to their membership conditions, observe that the conditions are logically equivalent, then invoke Extensionality. The set-theoretic content is nil; the point is that all of the familiar informalities of brace notation are theorems, not conventions.

Corollary 2.14 (Uniqueness of the empty set). There is exactly one set with no members.

Proof. Existence was shown in the note Where the empty set comes from. For uniqueness, let $e_{1}$ and $e_{2}$ both have no members. Then for every $z$ , both $z \in e_{1}$ and $z \in e_{2}$ are false, so the biconditional $z \in e_{1} \leftrightarrow z \in e_{2}$ holds vacuously for every $z$ . Extensionality gives $e_{1} = e_{2}$ .∎

Corollary 2.15 (Cardinality of a listed set). The set ${a_{1}, \dots, a_{n}}$ has exactly $k$ members, where $k$ is the number of distinct sets among $a_{1}, \dots, a_{n}$ .

Proof. By the proposition Repetition and order are invisible applied repeatedly, any repeated entry may be deleted without changing the set, so ${a_{1}, \dots, a_{n}}$ equals the listing of the distinct entries, of which there are $k$ . Conversely those $k$ entries are pairwise distinct members, so the set has exactly $k$ members.∎

Pitfall. ${a}$ and $a$ are never interchangeable. ${\emptyset}$ has one member and $\emptyset$ has none, so by Extensionality they are different sets — indeed $\emptyset \in {\emptyset}$ and $\emptyset \subseteq {\emptyset}$ are both true while $\emptyset = {\emptyset}$ is false. A one-element set is a box containing a thing, not the thing.

Example 2.16 (Counting members through the braces). How many members does each of ${\emptyset}$ , ${\emptyset, {\emptyset}}$ , ${\emptyset, \emptyset}$ and ${{\emptyset, {\emptyset}}}$ have?

Solution.

${\emptyset}$ has one member, namely $\emptyset$ .
${\emptyset, {\emptyset}}$ has two members: $\emptyset$ and ${\emptyset}$ , which differ by the pitfall above.
${\emptyset, \emptyset} = {\emptyset}$ by the proposition Repetition and order are invisible, so it has one member.
${{\emptyset, {\emptyset}}}$ has exactly one member, namely the two-element set inside it. Braces at the outside always give a singleton however complicated the contents.

□

Exercises for §2.6 →

2.7Extensionality at work

The axiom earns its keep in proofs of the form "these two differently-described sets are the same". The recipe never varies.

Method 2.17 (Proving two sets equal). To show $X = Y$ :

Take an arbitrary $z \in X$ and derive $z \in Y$ , giving $X \subseteq Y$ .
Take an arbitrary $z \in Y$ and derive $z \in X$ , giving $Y \subseteq X$ .
Conclude $X = Y$ by the proposition Equality by double inclusion.

If the two membership conditions are visibly the same formula, steps 1 and 2 collapse into a single chain of biconditionals and you may quote Extensionality directly.

Example 2.18 (A distributive law by double inclusion). Prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .

Solution.

Let $z \in A \cap (B \cup C)$ . Then $z \in A$ , and $z \in B$ or $z \in C$ . In the first case $z \in A \cap B$ ; in the second $z \in A \cap C$ . Either way $z \in (A \cap B) \cup (A \cap C)$ .
Conversely let $z \in (A \cap B) \cup (A \cap C)$ . In either case $z \in A$ , and $z$ lies in $B$ or in $C$ , so $z \in B \cup C$ and hence $z \in A \cap (B \cup C)$ .
Both inclusions hold, so the sets are equal by the recipe Proving two sets equal. Notice that the argument is nothing but the distributivity of $\land$ over $\lor$ in the membership conditions; Extensionality is what converts that logical fact into a set identity.

□

Example 2.19 (Two descriptions of one set). Let $E = {n \in ω : n is even}$ and $F = {n \in ω : n = 2 k for some k \in ω}$ . Are $E$ and $F$ the same set, and does the answer depend on how they were built?

Solution.

A natural number is even precisely when it is twice another natural number, so the two membership conditions are equivalent formulas.
Hence $\forall z (z \in E \leftrightarrow z \in F)$ and Extensionality gives $E = F$ .
The construction route is irrelevant: both sets came from Separation applied to $ω$ , but even if one had been produced by Replacement the answer would be the same. A set has no memory of its derivation.

□

Example 2.20 (Extensionality failing). Suppose a theory allows two distinct "atoms" $a \neq = b$ , neither of which has any members. Which axiom does this violate, and what breaks?

Solution.

Both $a$ and $b$ have no members, so $\forall z (z \in a \leftrightarrow z \in b)$ holds vacuously and Extensionality would force $a = b$ . So such a theory rejects Extensionality — this is the theory ZFA, with urelements.
What breaks is the corollary Uniqueness of the empty set: there are now many memberless objects, and "the" empty set is no longer well defined.
The proposition Equality by double inclusion also fails, since $a \subseteq b$ and $b \subseteq a$ hold vacuously while $a \neq = b$ .

□

Exercises for §2.7 →

2.8Pairing, union and separation: what they give for free

Extensionality pins down identity; the constructive axioms then supply objects. A surprising amount of everyday set theory needs no new axiom at all, and this section proves it. Intersection, difference, the ordered pair and the Cartesian product all fall out of Pairing, Union, Separation and Power set.

Theorem 2.21 (Intersection and difference need no axiom of their own). Let $A$ and $B$ be sets. Then $A \cap B$ and $A ∖ B$ exist as sets, provably from Separation alone. Moreover, if $F$ is a nonempty set, then $⋂ F = {z : \forall y \in F, z \in y}$ exists.

Proof. For $A \cap B$ , apply Separation to the set $A$ with the formula $φ (z, B) \equiv z \in B$ , in which $B$ appears as a parameter. The resulting set ${z \in A : z \in B}$ has as members exactly those $z$ lying in both, which is the defining property of $A \cap B$ ; it is unique by Extensionality.

For $A ∖ B$ , apply Separation to $A$ with $φ (z, B) \equiv z \in / B$ .

For $⋂ F$ with $F \neq = \emptyset$ , choose any $a \in F$ — a single instantiation, not Choice — and apply Separation to $a$ with the formula $φ (z, F) \equiv \forall y (y \in F \to z \in y)$ . The result contains exactly those $z$ lying in every member of $F$ : such a $z$ lies in $a$ in particular, so nothing is lost by bounding the search inside $a$ .∎

Remark. The hypothesis $F \neq = \emptyset$ in the last part is essential. If $F = \emptyset$ the condition " $z$ lies in every member of $F$ " is vacuously true of every set, so $⋂ \emptyset$ would be the universal set, which the theorem Separation blocks Russell, and proves there is no universal set forbids. By contrast $⋃ \emptyset = \emptyset$ is perfectly well behaved, because Union is an existence axiom with no such bound needed.

The ordered pair is the next construction, and it is the one place in elementary set theory where a clever encoding does real work. An ordered pair must satisfy one property and only one: it must remember which component came first.

Definition 2.22 (Kuratowski ordered pair). For sets $a$ and $b$ define

(a, b) = {{a}, {a, b}} .

This is a set: ${a}$ and ${a, b}$ exist by Pairing, and then Pairing applied to those two sets gives $(a, b)$ .

Theorem 2.23 (The defining property of the ordered pair). For all sets $a, b, c, d$ ,

(a, b) = (c, d) ⟺ a = c and b = d .

Proof. ( $\Leftarrow$ ) If $a = c$ and $b = d$ then ${a} = {c}$ and ${a, b} = {c, d}$ by substitution, hence the two pairs are the same set.

( $\Rightarrow$ ) Assume ${{a}, {a, b}} = {{c}, {c, d}}$ . Split on whether $a = b$ .

Case 1: $a = b$ . Then ${a, b} = {a}$ by the proposition Repetition and order are invisible, so $(a, b) = {{a}, {a}} = {{a}}$ , a set with exactly one member. The right-hand side is therefore also a one-element set, so ${c} = {c, d}$ . Since $d \in {c, d} = {c}$ we get $d = c$ , and then the right side is ${{c}}$ . Equating the unique members, ${a} = {c}$ , so $a = c$ ; and $b = a = c = d$ . Both conclusions hold.

Case 2: $a \neq = b$ . Then ${a, b}$ has two members while ${a}$ has one, so ${a} \neq = {a, b}$ and the left-hand side has exactly two members. Now ${a} \in {{c}, {c, d}}$ , so either ${a} = {c}$ or ${a} = {c, d}$ .

If ${a} = {c, d}$ then $c = a$ and $d = a$ , so the right-hand side is ${{a}, {a}} = {{a}}$ , a one-element set, contradicting that the left has two members. Hence ${a} = {c}$ and therefore $a = c$ .

It remains to show $b = d$ . We have ${a, b} \in {{c}, {c, d}} = {{a}, {a, d}}$ . Since ${a, b} \neq = {a}$ (it has two members), we get ${a, b} = {a, d}$ . Now $b \in {a, d}$ , and $b \neq = a$ , so $b = d$ , as required.∎

Intuition. The encoding works by asymmetry. In ${{a}, {a, b}}$ the first coordinate appears in both inner sets while the second appears in only one, so the first coordinate is recoverable as the member of $⋂ (a, b)$ and the second as the member of $⋃ (a, b) ∖ ⋂ (a, b)$ when the coordinates differ. Any encoding with that asymmetry would do; Kuratowski's is simply the cheapest one that Pairing alone can build.

Pitfall. The degenerate case $a = b$ is where careless proofs of the characterisation fail. When $a = b$ the pair $(a, a) = {{a}}$ has one member, not two, and an argument that assumes " $(a, b)$ always has two members" is wrong on the diagonal. Case 1 of the proof above exists entirely to handle this.

Example 2.24 (Unwinding a Kuratowski pair). Write $(0, 1)$ as an explicit set of sets, using the von Neumann numerals $0 = \emptyset$ and $1 = {\emptyset}$ , and count its members and the members of its members.

Solution.

By definition $(0, 1) = {{0}, {0, 1}} = {{\emptyset}, {\emptyset, {\emptyset}}}$ .
Its two members are ${\emptyset}$ , which has one member, and ${\emptyset, {\emptyset}}$ , which has two. So $(0, 1)$ has $2$ members, carrying $1 + 2 = 3$ memberships between them.
Compare $(0, 0) = {{0}} = {{\emptyset}}$ , which has just $1$ member. The drop from $2$ to $1$ is exactly the degeneracy the pitfall warns about.

□

With pairs available, products follow — and here Power set does the work that Separation cannot do alone, because a product is not a subset of anything already in hand until you find the right ambient set.

Theorem 2.25 (Cartesian products exist). For all sets $A$ and $B$ there is a set

A \times B = {(a, b) : a \in A, b \in B} .

Proof. Let $a \in A$ and $b \in B$ . Then $a, b \in A \cup B$ , so ${a} \subseteq A \cup B$ and ${a, b} \subseteq A \cup B$ ; that is, ${a}$ and ${a, b}$ are both members of $P (A \cup B)$ . Consequently

(a, b) = {{a}, {a, b}} \subseteq P (A \cup B), so (a, b) \in P (P (A \cup B)) .

The set $P (P (A \cup B))$ exists: $A \cup B$ by Pairing and Union, then Power set twice. Now apply Separation to it with the formula

φ (z, A, B) \equiv \exists a \in A \exists b \in B (z = {{a}, {a, b}}),

which is a legitimate formula of $L_{\in}$ with parameters $A$ and $B$ . The resulting set contains exactly the Kuratowski pairs with first coordinate in $A$ and second in $B$ , which is $A \times B$ .∎

The pattern of that proof — find an ambient set large enough, then separate — is the standard method for proving existence in ZF, and it is why Power set is indispensable even for constructions that look as though they only need pairing.

Corollary 2.26 (Relations and functions are sets). For all sets $A$ and $B$ , the collection of all relations from $A$ to $B$ is a set, and so is the collection $B^{A}$ of all functions from $A$ to $B$ .

Proof. A relation from $A$ to $B$ is by definition a subset of $A \times B$ , so the collection of all of them is $P (A \times B)$ , a set by the theorem Cartesian products exist and Power set. A function from $A$ to $B$ is a relation with the extra first-order property of being total and single-valued, so $B^{A}$ is obtained from $P (A \times B)$ by Separation.∎

Example 2.27 (Sizes of products and function spaces). Let $∣ A ∣ = 3$ and $∣ B ∣ = 4$ . Compute the number of members of $A \times B$ , of the set of all relations from $A$ to $B$ , and of $B^{A}$ .

Solution.

$∣ A \times B ∣ = 3 \cdot 4 = 12$ , one pair for each choice of coordinates.
Relations are subsets of $A \times B$ , so there are $2^{12} = 4096$ of them.
A function assigns to each of the $3$ members of $A$ one of the $4$ members of $B$ , so $∣ B^{A} ∣ = 4^{3} = 64$ . Every one of these sets exists by the corollary Relations and functions are sets, with no appeal to Choice.

□

Exercises for §2.8 →

2.9Regularity: the statement

The eighth axiom is the one nobody misses until it is gone. It proves no theorem of ordinary mathematics and can be dropped without damaging analysis or algebra; what it does is impose a shape on the universe, and that shape is what makes induction and recursion available on all sets rather than only on the well-ordered ones.

Definition 2.28 (Axiom of Regularity (Foundation)). Every nonempty set has an $\in$ -minimal member:

\forall x (x \neq = \emptyset \to \exists y (y \in x \land y \cap x = \emptyset)) .

The member $y$ is minimal in the sense that no member of $y$ is also a member of $x$ .

Intuition. Read $y \cap x = \emptyset$ as " $y$ is a floor". The axiom says every nonempty set contains at least one member that shares nothing with it — you cannot keep descending through members of members of members forever, because at some point the box you open has nothing from the original collection inside. The universe rests on $\emptyset$ and is built upwards in layers; it has a bottom.

Pitfall. Regularity does not say "every set has a member that is empty", nor " $\emptyset$ is a member of every nonempty set". ${{1}, {2}}$ contains no empty set, but ${1}$ is $\in$ -minimal in it, because $1 = {0}$ and $0 \in / {{1}, {2}}$ . Minimality is relative to $x$ , not absolute.

Example 2.29 (Finding the minimal member). Identify an $\in$ -minimal member of $x = {1, 2, 3}$ and of $y = {{\emptyset}, {{\emptyset}}}$ , using the von Neumann numerals.

Solution.

In $x = {1, 2, 3}$ with $1 = {0}$ : the members of $1$ are just $0$ , and $0 \in / x$ , so $1 \cap x = \emptyset$ and $1$ is $\in$ -minimal. ( $2$ is not: $1 \in 2$ and $1 \in x$ .)
In $y$ , the member ${\emptyset}$ has only $\emptyset$ inside, and $\emptyset \in / y$ , so ${\emptyset}$ is $\in$ -minimal. The other member ${{\emptyset}}$ is not minimal, since ${\emptyset}$ lies in both it and $y$ .
In each case exactly the "lowest" member in the layering is the one the axiom promises.

□

Exercises for §2.9 →

2.10Well-foundedness: no loops anywhere

The advertised payoff of Regularity is the ban on membership cycles. Both proofs below have the same one-move structure: manufacture a set whose minimality contradicts the supposed cycle.

Theorem 2.30 (No set is a member of itself). In ZF, $x \in / x$ for every set $x$ .

Proof. Suppose $x \in x$ for some set $x$ . By Pairing, ${x}$ is a set, and it is nonempty, so Regularity supplies a member $y \in {x}$ with $y \cap {x} = \emptyset$ . The only member of ${x}$ is $x$ , so $y = x$ and therefore $x \cap {x} = \emptyset$ .

But $x \in x$ by assumption and $x \in {x}$ always, so $x \in x \cap {x}$ , making that intersection nonempty. This contradicts the previous line, so no such $x$ exists.∎

Theorem 2.31 (No membership cycles of any finite length). In ZF there are no sets $x_{0}, x_{1}, \dots, x_{n - 1}$ with $n \geq 1$ and

x_{0} \in x_{1} \in x_{2} \in \dots \in x_{n - 1} \in x_{0} .

Proof. Suppose such a cycle exists. Let $c = {x_{0}, x_{1}, \dots, x_{n - 1}}$ , which is a set: build it by $n - 1$ applications of Pairing and Union, or in one step by Separation from any set containing the $x_{i}$ . It is nonempty since $n \geq 1$ .

By Regularity there is $x_{i} \in c$ with $x_{i} \cap c = \emptyset$ . But the cycle provides a predecessor: reading indices modulo $n$ , we have $x_{i - 1} \in x_{i}$ , and $x_{i - 1} \in c$ by construction. Hence $x_{i - 1} \in x_{i} \cap c$ , so that intersection is nonempty — contradicting the choice of $x_{i}$ .

Since $i$ was an arbitrary index supplied by the axiom and every index has a predecessor in the cycle, no member of $c$ can be $\in$ -minimal, so $c$ violates Regularity. Therefore no cycle exists. Taking $n = 1$ recovers the theorem No set is a member of itself.∎

Figure 2.32. A membership cycle

a \in b \in c \in a

. Each arrow points from a set to a set containing it, so following the arrows returns to the start. Regularity forbids this: whichever of

a

b

c

were

\in

-minimal in

{a, b, c}

, its predecessor in the cycle lies in both it and

{a, b, c}

, so the intersection is never empty.

Corollary 2.33 (No descending chain reachable inside a set). There is no set $x$ together with a function $f : ω \to x$ such that $f (n + 1) \in f (n)$ for every $n \in ω$ .

Proof. Suppose such an $f$ existed. Its range $r = f [ω]$ is a set, by the corollary Relations and functions are sets and Replacement, and it is nonempty. By Regularity there is $y \in r$ with $y \cap r = \emptyset$ ; write $y = f (n)$ . Then $f (n + 1) \in f (n) = y$ and $f (n + 1) \in r$ , so $f (n + 1) \in y \cap r$ , contradicting emptiness.∎

Remark. The converse — that a universe with no infinite descending $\in$ -chain satisfies Regularity — needs the axiom of choice to produce the chain from a set with no minimal member, so "well-founded" and "satisfies Regularity" are equivalent in ZFC but not provably so in ZF alone. This is one of the few places in the chapter where Choice is genuinely required, and it is worth flagging because the two conditions are routinely treated as the same thing.

Exercises for §2.10 →

2.11The cumulative hierarchy

Regularity is best understood not as a prohibition but as a picture. The sets are stacked in levels indexed by the ordinals, each level containing all subsets of everything below it, and Regularity says that this stack is the whole universe.

Definition 2.34 (The von Neumann hierarchy). Define, by transfinite recursion on the ordinals,

V_{0} = \emptyset, V_{α + 1} = P (V_{α}), V_{λ} = α < λ ⋃ V_{α} (λ a limit) .

The rank of a set $x$ is the least ordinal $α$ with $x \subseteq V_{α}$ , equivalently the least $α$ with $x \in V_{α + 1}$ .

Theorem 2.35 (Every set has a rank). In ZF, every set belongs to some $V_{α}$ ; equivalently $V = ⋃_{α \in Ord} V_{α}$ . Moreover $rank (x) = sup {rank (y) + 1 : y \in x}$ .

Proof. The recursion defining $V_{α}$ is legitimate because Replacement licenses transfinite recursion and Power set supplies the successor step; the limit step is Union applied to the set ${V_{α} : α < λ}$ , which is a set by Replacement.

For the rank formula, suppose every $y \in x$ has a rank. Then ${rank (y) + 1 : y \in x}$ is a set of ordinals by Replacement, so it has a supremum $α$ , and $y \in V_{α}$ for every $y \in x$ ; hence $x \subseteq V_{α}$ and $x \in V_{α + 1}$ . Minimality of $α$ is immediate, since if $x \subseteq V_{β}$ then every $y \in x$ has $rank (y) < β$ .

That every set has a rank at all is exactly where Regularity is used: were some set rankless, the collection of rankless sets appearing inside it would, by Regularity applied to a suitable set built from its transitive closure, have an $\in$ -minimal member, all of whose members have ranks — and the displayed formula then assigns that member a rank, a contradiction.∎

The first few levels are small enough to write down, and their sizes grow at a rate that is worth seeing once.

Proposition 2.36 (The finite levels). $∣ V_{0} ∣ = 0$ , $∣ V_{1} ∣ = 1$ , $∣ V_{2} ∣ = 2$ , $∣ V_{3} ∣ = 4$ , $∣ V_{4} ∣ = 16$ , $∣ V_{5} ∣ = 65536$ , and in general $∣ V_{n + 1} ∣ = 2^{∣ V_{n} ∣}$ .

Proof. $V_{0} = \emptyset$ has $0$ members. Each successor level is a power set, so $∣ V_{n + 1} ∣ = ∣ P (V_{n}) ∣ = 2^{∣ V_{n} ∣}$ , which gives the recursion. Evaluating it: $2^{0} = 1$ , $2^{1} = 2$ , $2^{2} = 4$ , $2^{4} = 16$ , $2^{16} = 65536$ . The next value, $∣ V_{6} ∣ = 2^{65536}$ , has $19729$ decimal digits, and $∣ V_{7} ∣$ cannot be written down in this universe.∎

Figure 2.37. The cumulative hierarchy as a widening cone. Level

V_{n}

is drawn at height

n

with half-width proportional to

lo g_{2}

of its size, since the sizes themselves grow too fast to plot:

0, 1, 2, 4, 16, 65536

. Every set sits at a definite level — its rank — and Regularity says nothing lies outside the cone.

Example 2.38 (Computing ranks). Compute the rank of $\emptyset$ , of ${\emptyset}$ , of $3 = {0, 1, 2}$ , and of the ordered pair $(0, 1)$ .

Solution.

$rank (\emptyset) = 0$ , since $\emptyset \subseteq V_{0}$ and the supremum over an empty set of members is $0$ .
$rank ({\emptyset}) = rank (\emptyset) + 1 = 1$ .
For a von Neumann natural, $rank (n) = n$ : by the rank formula and induction, $rank (n + 1) = max_{k \leq n} (rank (k) + 1) = n + 1$ . So $rank (3) = 3$ .
$(0, 1) = {{0}, {0, 1}}$ . Here $rank ({0}) = 1$ and $rank ({0, 1}) = 2$ , so the rank of the pair is $max (1, 2) + 1 = 3$ . In general $rank ((a, b)) = max (rank a, rank b) + 2$ .

□

Exercises for §2.11 →

2.12What regularity rules out

It is instructive to see exactly which objects Regularity kills, and to notice how few of them anyone wanted.

Definition 2.39 (Transitive closure). The transitive closure $TC (x)$ of a set $x$ is the smallest transitive set containing $x$ as a subset, obtained as

TC (x) = x \cup ⋃ x \cup ⋃⋃ x \cup \dots,

the union of the iterated unions, which is a set by Replacement and Union. Its members are exactly the sets reachable from $x$ by descending through memberships.

Example 2.40 (Transitive closures of small sets). Compute $TC ({2})$ and $TC (3)$ with the von Neumann numerals, and count their members.

Solution.

$2 = {0, 1}$ and $1 = {0}$ and $0 = \emptyset$ . Starting from ${2}$ : the layers are ${2}$ , then $2 = {0, 1}$ contributing $0$ and $1$ , then $1$ contributing $0$ , then nothing new.
So $TC ({2}) = {2, 1, 0}$ , with $3$ members.
For $3 = {0, 1, 2}$ : the set itself contributes $0, 1, 2$ ; descending adds nothing new. So $TC (3) = {0, 1, 2} = 3$ itself, with $3$ members — as it must be, since a von Neumann natural is already transitive.

□

Example 2.41 (A Quine atom). A Quine atom is a set $q$ with $q = {q}$ . Show that Regularity forbids it, and say what survives without Regularity.

Solution.

If $q = {q}$ then $q \in {q} = q$ , so $q \in q$ , contradicting the theorem No set is a member of itself.
Without Regularity the existence of $q$ is consistent: Aczel's Anti-Foundation Axiom (AFA) replaces Regularity and asserts that every directed graph has a unique decoration, which produces exactly one Quine atom.
ZF minus Regularity plus AFA is equiconsistent with ZF, so neither theory is more dangerous than the other. Regularity is a choice of picture, not a safety requirement.

□

Remark. Non-well-founded sets are genuinely useful in computer science, where a stream or a process is naturally modelled by a circular structure. That is a reason to work in AFA-style set theory, not a reason to doubt ZF: the two are inter-interpretable, and mainstream mathematics has never needed a set that contains itself.

Example 2.42 (Why Regularity proves nothing about numbers). Does removing Regularity from ZFC change which statements about real numbers are provable?

Solution.

No. Every object of ordinary mathematics — $N$ , $R$ , function spaces, manifolds — is built by the constructive axioms, and each lands in $V_{α}$ for a definite $α$ well below the first inaccessible.
Formally, if ZF minus Regularity is consistent, then $V$ , the class of well-founded sets, forms a model of full ZF inside it, and that model contains a copy of every ordinary structure.
Regularity earns its place by simplifying arguments, chiefly $\in$ -induction and the rank function, not by extending the reach of the theory.

□

Exercises for §2.12 →

2.13Infinity: the statement

Nothing so far produces an infinite set. Pairing, Union, Power set and Separation each take sets in and give a set out, and starting from $\emptyset$ they only ever reach finite sets. The fifth axiom is the one that breaks out, and it does so in the most economical possible way: it asserts the existence of one set that is closed under a single successor operation.

Definition 2.43 (Successor and inductive sets). The successor of a set $x$ is $S (x) = x \cup {x}$ , a set by Pairing and Union. A set $I$ is inductive if

\emptyset \in I and \forall x (x \in I \to S (x) \in I) .

Definition 2.44 (Axiom of Infinity). There exists an inductive set.

Intuition. $S (x) = x \cup {x}$ says: to move on from $x$ , keep everything you had and add the box holding all of it. Starting at $\emptyset$ this generates $\emptyset$ , ${\emptyset}$ , ${\emptyset, {\emptyset}}$ , … — each numeral is literally the set of all its predecessors, so " $n$ has $n$ members" is true on the nose rather than by counting.

Pitfall. Infinity does not assert that $N$ exists. It asserts that some inductive set exists, and an inductive set may be much larger than $N$ — $V_{ω + ω}$ is inductive, for instance. Cutting the promised set down to the smallest inductive one is a separate step, and it is Separation that does it.

Exercises for §2.13 →

2.14Building the natural numbers

Definition 2.45 (Von Neumann naturals). Define

0 = \emptyset, 1 = S (0) = {\emptyset}, 2 = S (1) = {\emptyset, {\emptyset}}, 3 = S (2) = {0, 1, 2}, \dots

so that each numeral is the set of all smaller numerals:

n = {0, 1, \dots, n - 1}

, and consequently

n

has exactly

n

members.

Figure 2.46. The first four von Neumann naturals as nested boxes. Each numeral is the set of all its predecessors, so the box for

n

contains exactly

n

boxes:

0

is empty,

1

holds

0

2

holds

0

and

1

3

holds

0

1

and

2

. The nesting depth of the outermost box is the rank, which for

n

equals

n

The definition above is a schema of abbreviations, one per numeral; to have the set of all of them we need one more step, and this is where Infinity and Separation combine.

Theorem 2.47 (Omega is well defined). There is a unique smallest inductive set

ω = ⋂ {J \subseteq I : J is inductive},

where

I

is any inductive set given by Infinity. It is inductive, it is contained in every inductive set, and it does not depend on the choice of

I

Proof. Let $I$ be inductive, given by Infinity. The collection $J = {J \in P (I) : J is inductive}$ is a set, by Power set and Separation with the first-order formula expressing inductiveness. It is nonempty, since $I \in J$ , so $ω = ⋂ J$ exists by the theorem Intersection and difference need no axiom of their own.

$ω$ is inductive: $\emptyset$ lies in every $J \in J$ , hence in the intersection; and if $x \in ω$ then $x \in J$ for every such $J$ , so $S (x) \in J$ for every such $J$ , so $S (x) \in ω$ .

$ω$ is contained in every inductive set: let $K$ be inductive. Then $K \cap I$ is inductive (both conditions are inherited by the intersection of two inductive sets) and is a subset of $I$ , so $K \cap I \in J$ and therefore $ω \subseteq K \cap I \subseteq K$ .

Independence of $I$ and uniqueness follow: if $ω^{'}$ were built from another inductive set $I^{'}$ , each of $ω, ω^{'}$ is inductive and each is contained in every inductive set, so $ω \subseteq ω^{'}$ and $ω^{'} \subseteq ω$ , whence $ω = ω^{'}$ by the proposition Equality by double inclusion.∎

Theorem 2.48 (The Peano axioms hold in omega). With $0 = \emptyset$ and successor $S (x) = x \cup {x}$ , the structure $(ω, 0, S)$ satisfies:

$0 \in ω$ ;
$S (n) \in ω$ for every $n \in ω$ ;
$S (n) \neq = 0$ for every $n \in ω$ ;
$S$ is injective on $ω$ ;
(Induction) if $A \subseteq ω$ contains $0$ and is closed under $S$ , then $A = ω$ .

Proof. (1) and (2) are the statement that $ω$ is inductive, proved in the theorem Omega is well defined.

(3): $n \in S (n)$ always, so $S (n)$ is nonempty and hence differs from $\emptyset = 0$ .

(5): such an $A$ is an inductive set, so $ω \subseteq A$ by minimality; with $A \subseteq ω$ given, double inclusion gives $A = ω$ . Induction is thus not an extra assumption — it is minimality.

(4): first note that every $n \in ω$ is transitive, i.e. $m \in n \to m \subseteq n$ . This holds by induction using (5): $0$ is vacuously transitive, and if $n$ is transitive and $m \in S (n) = n \cup {n}$ then either $m \in n$ , so $m \subseteq n \subseteq S (n)$ , or $m = n \subseteq S (n)$ . Now suppose $S (m) = S (n)$ . Then $m \in S (m) = S (n) = n \cup {n}$ , so $m \in n$ or $m = n$ ; symmetrically $n \in m$ or $n = m$ . If $m \neq = n$ we would get $m \in n$ and $n \in m$ , a $2$ -cycle forbidden by the theorem No membership cycles of any finite length. Hence $m = n$ .∎

Remark. Part (4) is the only place in the chapter where the Peano axioms lean on Regularity, and it can be proved without it by an induction on transitivity instead. It is included in this form because it shows the two axioms cooperating: Infinity supplies the objects, Regularity supplies their rigidity.

Example 2.49 (Members, subsets and the successor). Compute the number of members of $4$ , the number of subsets of $4$ , and write $S (3)$ explicitly.

Solution.

$4 = {0, 1, 2, 3}$ , so $4$ has exactly $4$ members — the defining feature of the von Neumann encoding.
The subsets of a $4$ -element set number $2^{4} = 16$ , so $∣ P (4) ∣ = 16$ . (This matches $∣ V_{4} ∣ = 16$ , and not by accident: $V_{4} = P (V_{3})$ and $∣ V_{3} ∣ = 4$ .)
$S (3) = 3 \cup {3} = {0, 1, 2} \cup {3} = {0, 1, 2, 3} = 4$ .

□

Exercises for §2.14 →

2.15Why the axiom cannot be dropped

It is tempting to think that since we can build $0, 1, 2, 3, \dots$ one at a time without Infinity, the axiom only tidies up. It does not. Each numeral is a separate theorem; there is no theorem of ZF minus Infinity that produces a set containing all of them.

Theorem 2.50 (ZF minus Infinity does not prove Infinity). The set $V_{ω}$ of hereditarily finite sets satisfies every axiom of ZFC except Infinity, and satisfies the negation of Infinity. Consequently, if ZF is consistent, Infinity is not provable from the other axioms.

Proof. Every member of $V_{ω} = ⋃_{n < ω} V_{n}$ is finite and has all of its members in $V_{ω}$ , so $V_{ω}$ is transitive and Extensionality and Regularity hold in it automatically.

Pairing: if $a, b \in V_{n}$ then ${a, b} \in V_{n + 1} \subseteq V_{ω}$ . Union: if $a \in V_{n}$ then $⋃ a \subseteq V_{n - 1}$ , so $⋃ a \in V_{n}$ . Power set: if $a \in V_{n}$ then every subset of $a$ lies in $V_{n}$ , so $P (a) \in V_{n + 1}$ . Separation and Replacement: a subset of a finite set is finite, and the image of a finite set under a function is finite, so both stay inside $V_{ω}$ — with Replacement using that any level-bounded finite family is bounded by a single $V_{n}$ . Choice holds because every member is finite, by the proposition Finite choice is a theorem of ZF.

Infinity fails: an inductive set contains $0, 1, 2, \dots$ and so is infinite, while every member of $V_{ω}$ is finite. So $V_{ω} ⊨ \neg Infinity$ , and a theory cannot prove a sentence false in one of its models.∎

Intuition. Without Infinity you can walk as far along the numerals as you like and you can never turn round and pick up the road behind you. Each step is a finite construction; the collection of all steps is not the result of any finite construction, so it has to be asserted.

Example 2.51 (What survives without Infinity). Which of the following are available in ZF minus Infinity: the number $2^{100}$ , the set ${0, 1, \dots, 999}$ , the set $ω$ , the set $Q$ ?

Solution.

$2^{100}$ as a von Neumann numeral is a hereditarily finite set, so yes — it lives in $V_{ω}$ , indeed with rank $2^{100}$ .
${0, 1, \dots, 999} = 1000$ is again a single numeral, so yes.
$ω$ is infinite, so no; by the theorem ZF minus Infinity does not prove Infinity it fails in $V_{ω}$ .
$Q$ is infinite, so no. Arbitrarily large finite objects are cheap; a single infinite one is an axiom.

□

Exercises for §2.15 →

2.16What infinity unlocks

Definition 2.52 (Limit and successor ordinals). An ordinal $α$ is a successor if $α = S (β)$ for some ordinal $β$ , and a limit if $α \neq = 0$ and $α$ is not a successor. Equivalently, $α$ is a limit exactly when $α \neq = 0$ and $α = ⋃ α$ .

Theorem 2.53 (Omega is the least limit ordinal). $ω$ is an ordinal, it is a limit ordinal, and every ordinal smaller than $ω$ is either $0$ or a successor. Hence $ω$ is the least limit ordinal.

Proof. $ω$ is transitive: if $n \in ω$ then $n \subseteq ω$ , proved by induction using part (5) of the theorem The Peano axioms hold in omega, since $0 \subseteq ω$ vacuously and $n \subseteq ω$ with $n \in ω$ gives $S (n) = n \cup {n} \subseteq ω$ . It is well-ordered by $\in$ by the same induction, so it is an ordinal.

$ω \neq = 0$ since $0 \in ω$ . If $ω = S (β)$ then $β \in ω$ , so $S (β) \in ω$ by inductiveness, i.e. $ω \in ω$ , contradicting the theorem No set is a member of itself. So $ω$ is a limit.

Every $n \in ω$ is $0$ or a successor: by induction, $0$ is $0$ , and any $S (n)$ is a successor. Hence no member of $ω$ is a limit, so $ω$ is the least one.∎

Remark. After $ω$ the ordinals continue: $ω + 1 = S (ω)$ , $ω + 2$ , …, then $ω + ω = ω \cdot 2$ , $ω^{2}$ , $ω^{ω}$ , $ε_{0}$ , and far beyond. Every one of these is a set, and producing them in bulk needs Replacement, which is the subject of the last part of this chapter.

Example 2.54 (Successor or limit). Classify $0$ , $7$ , $ω$ , $ω + 1$ and $ω \cdot 2$ as zero, successor or limit, and compute $⋃ α$ for $α = 7$ and for $α = ω$ .

Solution.

$0$ is zero; $7 = S (6)$ is a successor; $ω$ is a limit by the theorem Omega is the least limit ordinal; $ω + 1 = S (ω)$ is a successor; $ω \cdot 2 = sup {ω + n : n < ω}$ is a limit.
$⋃ 7 = ⋃ {0, \dots, 6} = {0, \dots, 5} = 6$ : for a successor ordinal $S (β)$ the union is $β$ .
$⋃ ω = ω$ , since every $n \in ω$ has $S (n) \in ω$ and $n \in S (n)$ . This is the criterion for a limit stated in the definition Limit and successor ordinals.

□

Exercises for §2.16 →

2.17Power set: the statement

Definition 2.55 (Axiom of Power Set). For every set $a$ there is a set whose members are exactly the subsets of $a$ :

\forall a \exists p \forall z (z \in p \leftrightarrow z \subseteq a) .

By Extensionality this $p$ is unique; we write it $P (a)$ .

Strictly, the axiom as usually stated only asserts a set $p$ containing every subset of $a$ ; Separation then trims it to exactly the subsets. That weaker form is preferred in careful treatments because it is easier to verify in models, and the two versions are equivalent over the rest of ZF.

Proposition 2.56 (Elementary facts about the power set). For all sets $a$ and $b$ :

$\emptyset \in P (a)$ and $a \in P (a)$ , so $P (a) \neq = \emptyset$ for every $a$ ;
$a \subseteq b$ if and only if $P (a) \subseteq P (b)$ ;
if $a$ is transitive then so is $P (a)$ .

Proof. (1) $\emptyset \subseteq a$ and $a \subseteq a$ , so both are members of $P (a)$ . In particular $P (\emptyset) = {\emptyset}$ has one member.

(2) If $a \subseteq b$ and $z \in P (a)$ then $z \subseteq a \subseteq b$ , so $z \in P (b)$ . Conversely if $P (a) \subseteq P (b)$ then $a \in P (a) \subseteq P (b)$ by (1), so $a \subseteq b$ .

(3) Let $z \in P (a)$ , so $z \subseteq a$ , and let $y \in z$ . Then $y \in a$ , and transitivity of $a$ gives $y \subseteq a$ , i.e. $y \in P (a)$ . Hence every member of a member of $P (a)$ is a member of $P (a)$ .∎

Pitfall. $\in$ and $\subseteq$ swap roles across the power set. $z \in P (a)$ and $z \subseteq a$ say the same thing, but $z \subseteq P (a)$ and $z \in a$ do not. Writing ${1} \in P ({1, 2})$ is correct; writing $1 \in P ({1, 2})$ is not, unless $1$ happens to be a subset — which, in the von Neumann encoding, it is, and that coincidence has confused generations of students.

Exercises for §2.17 →

2.18Why power set is the strong axiom

Every other constructive axiom is size-preserving in a rough sense: Pairing produces a two-element set, Union produces something no larger than the sum of the pieces, Separation produces a subset. Power set is the only one that leaps, and Cantor's theorem measures the leap.

Proposition 2.57 (Counting the subsets of a finite set). If $∣ a ∣ = n$ then $∣ P (a) ∣ = 2^{n}$ .

Proof. A subset of $a$ is determined by an independent in-or-out decision for each of the $n$ members, so subsets correspond bijectively to functions $a \to {0, 1}$ , of which there are $2^{n}$ . Formally, induct on $n$ : for $n = 0$ the only subset is $\emptyset$ and $2^{0} = 1$ ; and adding one new member $x$ to $a$ doubles the count, since each subset of $a$ yields exactly two subsets of $a \cup {x}$ , one containing $x$ and one not.∎

Theorem 2.58 (Cantor's theorem). For every set $a$ there is no surjection $f : a \to P (a)$ . Hence $∣ a ∣ < ∣ P (a) ∣$ .

Proof. Let $f : a \to P (a)$ be any function, and put

D = {x \in a : x \in / f (x)},

which is a set by Separation and is a subset of $a$ , so $D \in P (a)$ . Suppose $D = f (c)$ for some $c \in a$ . Ask whether $c \in D$ . By the definition of $D$ ,

c \in D ⟺ c \in / f (c) = D,

a contradiction either way. So $D$ is not in the range of $f$ and $f$ is not surjective. Since $x \mapsto {x}$ is an injection $a \to P (a)$ , the strict inequality of cardinalities follows.∎

Intuition. This is Russell's diagonal again, domesticated. Where Russell's set produced a contradiction from an unbounded comprehension, Cantor's set is a perfectly legitimate subset of $a$ — and the contradiction falls on the assumption that $f$ is onto instead of on the theory. The same three lines, aimed at a bounded target, become a theorem.

Corollary 2.59 (The power set of omega is uncountable). $P (ω)$ is not countable; that is, there is no surjection $ω \to P (ω)$ . The same holds for $R$ , which is in bijection with $P (ω)$ .

Proof. Immediate from the theorem Cantor's theorem with $a = ω$ . For the second claim, binary expansions give an injection $P (ω) \to R$ and Dedekind cuts give an injection $R \to P (Q) ≅ P (ω)$ ; Cantor–Schröder–Bernstein, a theorem of ZF requiring no choice, converts the two injections into a bijection.∎

Note (The continuum hypothesis). $∣ P (ω) ∣ = 2^{ℵ_{0}}$ , and CH is the assertion $2^{ℵ_{0}} = ℵ_{1}$ — that no cardinality lies strictly between $ω$ and its power set. Gödel showed ZFC cannot refute CH and Cohen showed ZFC cannot prove it. Power set is thus an axiom whose output size the axioms do not pin down.

Exercises for §2.18 →

2.19What power set builds

Theorem 2.60 (The standard structures of mathematics are sets). Given $ω$ , the following exist as sets in ZF: the Cartesian products $ω \times ω$ and $R \times R$ , the set $Z$ of integers, the set $Q$ of rationals, the set $R$ of reals, and for any sets $A, B$ the function space $B^{A}$ and the set of all topologies on $A$ .

Proof. Products exist by the theorem Cartesian products exist, which used Power set twice. $Z$ is a set of equivalence classes of $ω \times ω$ , hence a subset of $P (ω \times ω)$ , obtained by Separation; $Q$ likewise from $Z \times Z$ . $R$ as Dedekind cuts is a set of subsets of $Q$ , so a subset of $P (Q)$ , again by Separation. Function spaces are the corollary Relations and functions are sets. A topology on $A$ is a subset of $P (A)$ with first-order closure properties, so the collection of topologies is obtained by Separation from $P (P (A))$ .∎

Each line of that proof is the same move: locate the object inside an iterated power set, then separate. Power set is what makes "the set of all things of this kind over $A$ " a legitimate construction rather than a wish.

Example 2.61 (How many power sets deep?). The real line is built from $ω$ . How many applications of $P$ are needed to reach a set containing $R$ , and how many to reach a set containing the collection of all topologies on $R$ ?

Solution.

$Q$ is (a subset of a set obtained from) $P (ω \times ω)$ -level material, and up to coding we may take $Q \subseteq P (ω)$ -level. A real is a subset of $Q$ , so $R \subseteq P (Q)$ and $R \in P (P (Q))$ : two further applications beyond $Q$ .
A topology on $R$ is a subset of $P (R)$ , so the set of all of them is a subset of $P (P (R))$ : two more applications beyond $R$ .
All of it is comfortably inside $V_{ω + ω}$ , which is why ordinary analysis never needs Replacement.

□

Exercises for §2.19 →

2.20Power set towers

Proposition 2.62 (Iterated power sets of a finite set). Write $P^{0} (A) = A$ and $P^{k + 1} (A) = P (P^{k} (A))$ . If $∣ A ∣ = n$ then $∣ P^{1} (A) ∣ = 2^{n}$ , $∣ P^{2} (A) ∣ = 2^{2^{n}}$ , and in general the size is a tower of $k$ twos capped by $n$ .

Proof. Induct on $k$ using the proposition Counting the subsets of a finite set: each application replaces the current size $m$ by $2^{m}$ . Starting at $n$ the sizes are $n, 2^{n}, 2^{2^{n}}, 2^{2^{2^{n}}}, \dots$ ∎

Example 2.63 (A tower computed). Let $A = {a, b}$ . Compute $∣ P (A) ∣$ , $∣ P^{2} (A) ∣$ and $∣ P^{3} (A) ∣$ , and say which $V_{n}$ first contains $P^{2} (\emptyset)$ .

Solution.

$∣ A ∣ = 2$ , so $∣ P (A) ∣ = 2^{2} = 4$ .
$∣ P^{2} (A) ∣ = 2^{4} = 16$ and $∣ P^{3} (A) ∣ = 2^{16} = 65536$ .
$P^{0} (\emptyset) = \emptyset = V_{0}$ , and $P^{k} (\emptyset) = V_{k}$ by the definition The von Neumann hierarchy. So $P^{2} (\emptyset) = V_{2}$ , which is a member of $V_{3}$ . The tower of power sets over $\emptyset$ is exactly the finite cumulative hierarchy.

□

Example 2.64 (Subsets with a constraint). How many subsets does a $5$ -element set have, how many of them contain a fixed element $x$ , and how many have exactly $2$ members?

Solution.

$2^{5} = 32$ subsets in total, by the proposition Counting the subsets of a finite set.
Those containing $x$ correspond to arbitrary subsets of the other $4$ elements: $2^{4} = 16$ .
Two-element subsets number $(2 5) = 10$ . Each of these three collections is a set by Separation applied to $P (A)$ — counting is combinatorics, but existence is Power set plus Separation.

□

Exercises for §2.20 →

2.21Replacement: the statement

Definition 2.65 (Axiom schema of Replacement). Let $φ (x, y, \overset{p}{ˉ})$ be a formula of $L_{\in}$ . The corresponding instance of Replacement says: if $φ$ is functional on $a$ , meaning

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

then there is a set $b$ containing exactly the corresponding values,

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

Informally: the image of a set under a definable class function is a set.

Intuition. Separation shrinks: it hands back part of a set you already had. Replacement relabels: it keeps the index set and swaps each member for whatever the formula names, however much larger that is. The size of the output is the size of $a$ — no more — but its rank can be enormously higher, and rank, not size, is what the other axioms cannot climb.

Theorem 2.66 (Separation follows from Replacement). Every instance of Separation is derivable from the corresponding instance of Replacement (together with the existence of some set).

Proof. Fix $a$ and a formula $ψ (z, \overset{p}{ˉ})$ . Define $φ (x, y, \overset{p}{ˉ}) \equiv (ψ (x, \overset{p}{ˉ}) \land y = x) \lor (\neg ψ (x, \overset{p}{ˉ}) \land y = c)$ for a fixed $c$ chosen as follows. If no member of $a$ satisfies $ψ$ , then ${z \in a : ψ} = \emptyset$ , which exists. Otherwise pick $c \in a$ with $ψ (c, \overset{p}{ˉ})$ . Then $φ$ is functional on $a$ : each $x \in a$ is sent to itself if it satisfies $ψ$ , and to $c$ otherwise. By Replacement the image is a set, and that image is exactly ${z \in a : ψ (z, \overset{p}{ˉ})}$ , since $c$ itself satisfies $ψ$ .∎

Remark. So the official list of nine axioms is redundant: Separation is a consequence of Replacement, and Pairing is a consequence of Replacement plus Power set (replace the two members of $P (P (\emptyset))$ , a two-element set, by $a$ and $b$ ). The redundant items are kept because Zermelo set theory Z — ZF without Replacement — is a natural and much-used weaker system in which Separation must be assumed outright.

Exercises for §2.21 →

2.22Replacement is a schema

Replacement is not one axiom. There is no way, in first-order logic, to say "for every formula $φ$ …", because quantification ranges over sets and not over formulas of the language. What we have instead is a recipe that emits one axiom for each formula, and the collection of emitted axioms is infinite.

Definition 2.67 (Axiom schema). An axiom schema is a decidable set of axioms given by a template with a syntactic parameter — here, the formula $φ$ — so that the theory has infinitely many axioms although only finitely many templates. Separation and Replacement are the two schemas of ZFC; every other axiom on the list is a single sentence.

Note (ZFC is not finitely axiomatisable). If ZFC is consistent, then no finite set of sentences has exactly the same consequences as ZFC. The reason is the reflection theorem: for each finite fragment $T$ of ZFC, ZFC proves that some level $V_{α}$ is a model of $T$ . If a finite $T$ axiomatised all of ZFC, then ZFC would prove that some set is a model of ZFC, hence prove $Con (ZFC)$ , contradicting Gödel's second incompleteness theorem. So the infinitude of the schemas is essential, not a presentational convenience. By contrast, the class theory NBG is finitely axiomatisable, because it can quantify over classes and so state Replacement in one sentence.

Example 2.68 (Writing one instance). State the instance of Replacement used to prove that ${P (x) : x \in a}$ is a set.

Solution.

Take $φ (x, y) \equiv \forall z (z \in y \leftrightarrow z \subseteq x)$ , which says " $y$ is the power set of $x$ ".
Power set gives existence of such a $y$ and Extensionality gives uniqueness, so $\forall x \in a \exists! y φ (x, y)$ : the formula is functional on $a$ .
That instance of Replacement then yields the set $b = {P (x) : x \in a}$ . Note that a different formula would be a different axiom; nothing in the theory quantifies over $φ$ .

□

Pitfall. Replacement requires $φ$ to be functional — exactly one $y$ per $x$ . If several $y$ can answer to one $x$ , the instance does not apply, and the corresponding principle (Collection, which asks only for a set containing at least one witness for each $x$ ) is a separate axiom, equivalent to Replacement over ZF but not over weaker systems.

Exercises for §2.22 →

2.23What replacement is for

Replacement earns its place in three ways: it licenses transfinite recursion, it produces ordinals beyond the reach of Zermelo set theory, and it makes rank a total function. All three are the same fact wearing different clothes — Replacement is the axiom that lets you climb.

Theorem 2.69 (Transfinite recursion). Let $G$ be a definable class function. Then there is a unique definable class function $F$ on the ordinals with $F (α) = G (F ↾ α)$ for every $α$ , and for each ordinal $δ$ the restriction $F ↾ δ$ is a set.

Proof. Call $f$ an $α$ -approximation if $f$ is a function with domain $α$ satisfying $f (β) = G (f ↾ β)$ for all $β < α$ . By $\in$ -induction on $α$ , any two approximations agree on the intersection of their domains, so approximations are unique where defined; and an $α$ -approximation exists for every $α$ , since at a successor one appends $G (f)$ and at a limit one takes the union of the earlier approximations — and that union is a set precisely because Replacement turns the set of indices $β < λ$ into the set of approximations indexed by them. Defining $F (α)$ to be the common value gives the result.∎

Without Replacement the limit step fails: you can form each approximation but not the set of them, so the recursion stalls at the first limit stage that needs collecting. That is exactly what goes wrong in Zermelo set theory.

Note (Where Zermelo set theory stops). $V_{ω + ω}$ satisfies every axiom of ZFC except Replacement. It contains $ω$ , $R$ , every function space over $R$ , and all of ordinary analysis — which is why Replacement is invisible to most mathematicians. What it does not contain is the set ${V_{ω}, V_{ω + 1}, V_{ω + 2}, \dots}$ or the ordinal $ω + ω$ , both of which exist in ZF. So Replacement is not decorative; it is what distinguishes ZF from Z, and it fails to be provable in Z for exactly this reason.

Example 2.70 (The ordinal that Zermelo cannot reach). Show that ZF proves the existence of $ω + ω = sup {ω + n : n \in ω}$ , naming the axioms used.

Solution.

The map $n \mapsto ω + n$ is definable by a formula and is functional on $ω$ , since ordinal addition is defined by transfinite recursion and is single-valued.
Replacement applied to $ω$ with that formula yields the set ${ω + n : n \in ω}$ .
Union applied to that set gives its supremum $ω + ω$ , an ordinal. Infinity supplied $ω$ , Replacement supplied the family, Union supplied the limit — three axioms, and Separation and Power set were not needed.

□

Exercises for §2.23 →

2.24Replacement in action

The cleanest demonstration of what Replacement adds is a set that Separation provably cannot produce, because Separation can only ever cut a subset out of something already available, and here nothing available is large enough.

Theorem 2.71 (The power set tower over omega is a set). ZF proves the existence of the set

{ω, P (ω), P^{2} (ω), P^{3} (ω), \dots} = {P^{n} (ω) : n \in ω} .

Proof. Let $φ (n, y)$ be a formula expressing " $y = P^{n} (ω)$ ". This is first-order expressible: $φ (n, y)$ says that there exists a function $f$ with domain $S (n)$ such that $f (0) = ω$ , $f (k + 1) = P (f (k))$ for $k < n$ , and $f (n) = y$ . Such an $f$ is a finite sequence, hence a set, and Power set plus Extensionality make it unique, so $\forall n \in ω \exists! y φ (n, y)$ .

Replacement applied to $ω$ with $φ$ now delivers the image ${P^{n} (ω) : n \in ω}$ as a set. Union then gives $⋃_{n} P^{n} (ω)$ , a set of rank at least $ω + ω$ .∎

Remark. Separation alone cannot reach this set. Each $P^{n} (ω)$ has rank roughly $ω + n$ , so any set containing all of them has rank at least $ω + ω$ — and by the note Where Zermelo set theory stops, $V_{ω + ω}$ is a model of Zermelo set theory in which no such set exists. Separation could only carve this collection out of a set already containing every member of it, and Z proves no such set exists.

Example 2.72 (Replacement versus Separation on the same target). You want the set ${P^{n} (ω) : n \leq 5}$ . Can Separation do it, and does the answer change for $n \in ω$ ?

Solution.

For $n \leq 5$ , yes: $P^{5} (ω)$ exists by five applications of Power set, and all six sets are members of $P^{6} (ω)$ up to the usual coding, so Separation carves them out of that single ambient set.
For all $n \in ω$ there is no such ambient set to carve from — that is precisely the content of the remark above — so Separation cannot do it and Replacement is required.
The general lesson: finitely many steps of any construction stay inside the reach of the other axioms; assembling all the steps into one set is Replacement's job.

□

Example 2.73 (A definable image that is small but high). Let $a = {0, 1, 2}$ and let $φ (n, y)$ say $y = V_{ω + n}$ . What does Replacement produce, and how many members does it have?

Solution.

$φ$ is functional on $a$ , so Replacement yields $b = {V_{ω}, V_{ω + 1}, V_{ω + 2}}$ .
It has exactly $3$ members — Replacement never increases cardinality, since the image of a $3$ -element set has at most $3$ members and here the three values are distinct.
But its rank is $ω + 3$ , far above the rank $3$ of $a$ . Small and high: that is the signature of Replacement, and the reason it cannot be replaced by Separation.

□

Pitfall. "Replacement lets you build bigger sets" is only half right and misleads. $∣ b ∣ \leq ∣ a ∣$ always. What grows is rank, not cardinality — and what makes that possible is that the values may live arbitrarily far up the hierarchy even though there are few of them.

Exercises for §2.24 →

Common Mistakes

Using unrestricted comprehension. Writing ${x : φ (x)}$ with no bounding set is the move ZF exists to forbid. Always write ${x \in a : φ (x)}$ , and if no such $a$ is available, you need Replacement or you need to admit you are describing a proper class.
Thinking Russell's paradox is about self-membership. It is about the non-existence of a set of all non-self-membered sets. That no set contains itself is a different fact, proved from Regularity.
Confusing $\in$ with $\subseteq$ . $\emptyset \subseteq a$ for every $a$ , but $\emptyset \in a$ only for some. ${a} \subseteq P (a)$ is generally false; ${a} \in P (P (a))$ is not the same claim as either.
Forgetting the degenerate case of the ordered pair. $(a, a) = {{a}}$ has one member, not two. Any proof of the pair characterisation that does not split on $a = b$ is incomplete.
Believing Infinity gives you $N$ directly. It gives an inductive set. $ω$ is the intersection of all inductive subsets of it, and that intersection step is Separation.
Reading $⋃$ as $\cup$ . Union is unary and flattens a set of sets; the binary $\cup$ is derived from Pairing plus Union.
Claiming $⋂ \emptyset$ exists. It would be the universal set, which the theorem Separation blocks Russell, and proves there is no universal set forbids. The hypothesis $F \neq = \emptyset$ is not decoration.
Treating Replacement as one axiom. It is a schema, one axiom per formula, and that infinitude is why ZFC is not finitely axiomatisable.
Applying Replacement to a non-functional formula. Exactly one $y$ per $x$ is required; otherwise you are using Collection, which is a different principle.
Invoking Choice without noticing. "Pick one from each" is free for finite families and for families with a definable selection, and is an axiom otherwise. Conversely, over-citing Choice is its own error: Cantor's theorem, Cantor–Schröder–Bernstein and everything about $ω$ in this chapter are theorems of ZF alone.
Expecting the axioms to settle everything. CH and the existence of large cardinals are independent of ZFC. Independence is the normal condition of a strong theory, not a sign that something is broken.

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