The ZF Fragment and the von Neumann Natural Numbers

Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2 took the natural numbers as a set $\mathbb{N}$ inside the familiar real line, with induction as an axiom (Logic and Proof, Axiom 4.2.1) and with their arithmetic and order borrowed from the real numbers. This volume builds the real numbers, so it cannot borrow from them: where, then, do the natural numbers come from? This chapter starts again from sets alone. Six axioms say how sets are made and when two are equal; with them we build ordered pairs, and so functions, out of sets. Then we build the natural numbers out of nothing but the empty set. Zero is $\emptyset$ , and “one further” is the step $x \mapsto x \cup \{x\}$ , so that $1 = \{0\}$ , $2 = \{0, 1\}$ , $3 = \{0, 1, 2\}$ : each number is the set of the numbers before it. A seventh axiom, Infinity, says that the steps can be completed into a set, and the least such set is $\omega$ . From there, everything that Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2 assumed about $\mathbb{N}$ becomes a theorem about $\omega$ : Peano’s axioms, induction, the recursion theorem, the laws of $+$ and $\cdot$ , and the order with its well-ordering. A final theorem says that any other system satisfying Peano’s axioms is a relabeling of this one, by exactly one matching, and the chapter closes with the rule by which the later chapters of this volume write $\mathbb{N}$ for $\omega$ and cite Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapters 2 and 3.

Two pictures. Sets, Relations, and Cardinality, Chapter 1 adopted two working conventions: numbers are not sets (Sets, Relations, and Cardinality, Section 1.1), and a pair is not a number, nor a triple a pair (the remark after Sets, Relations, and Cardinality, Definition 1.3.1). They belong to the picture of Sets, Relations, and Cardinality, Chapters 1 to 3, in which numbers are given objects. In this chapter every object is a set, so $0 \in 5$ and $2 \subseteq 3$ are true statements, and the pair $(0, 1)$ is the set $\{1, 2\}$ . The two pictures do not conflict. Sets, Relations, and Cardinality, Section 1.1 said that nothing in the main line depends on how numbers are made, and Sets, Relations, and Cardinality, Chapter 1 used nothing about pairs beyond their characteristic property and that convention; Section 1.2 proves the characteristic property for pairs built from sets. What survives of the conventions becomes a theorem: no pair is a natural number (Section 1.4), and no $n$ -tuple with $n \ge 3$ is a pair or a natural number (Section 1.6). Statements such as $0 \in 5$ are facts about this one construction; the matching of Section 1.7 carries $0$ , successor, $+$ , $\cdot$ and $<$ , and nothing else.

What you need. Logic and Proof, Chapters 1–8, and Sets, Relations, and Cardinality, Chapters 1–3, chiefly its Chapters 1 and 2. From Logic and Proof, Chapters 2, 5 and 6: the rules $\mathrm{\neg I}$ and RAA (Logic and Proof, Definition 2.2.1, Logic and Proof, Definition 2.5.1), the rules for equality (Logic and Proof, Definition 5.7.1), and first-order formulas (Logic and Proof, Definition 5.2.2), which are what a “property” in the axiom of Separation means; Section 1.3’s exercises also use De Morgan’s laws and negate quantifiers, bounded ones included (Logic and Proof, Proposition 2.5.5, Logic and Proof, Proposition 6.2.1, Logic and Proof, Proposition 6.2.3). From Logic and Proof, Chapter 4, the principle of induction (Logic and Proof, Axiom 4.2.1), which Section 1.3 proves as a theorem about $\omega$ and which is never used on $\omega$ ; and, for review exercise R3 of Section 1.7, structural recursion and unique readability (Logic and Proof, Theorem 4.3.4, Logic and Proof, Theorem 4.3.3). From Logic and Proof, Chapter 8, the catalogue of what a proof may not do (Logic and Proof, Example (What is not allowed)). From Sets, Relations, and Cardinality, Chapter 1: equality of sets, subsets and sets cut out by a property (Sets, Relations, and Cardinality, Definition 1.1.1, Sets, Relations, and Cardinality, Definition 1.1.2, Sets, Relations, and Cardinality, Definition 1.1.3), Russell’s theorem (Sets, Relations, and Cardinality, Theorem 1.1.4), unions and intersections, of two sets and of families (Sets, Relations, and Cardinality, Definition 1.2.1, Sets, Relations, and Cardinality, Definition 1.2.3, Sets, Relations, and Cardinality, Definition 1.2.4), the smallest closed set (Sets, Relations, and Cardinality, Proposition 1.2.2), ordered pairs, products and relations (Sets, Relations, and Cardinality, Definition 1.3.1, Sets, Relations, and Cardinality, Definition 1.3.2, Sets, Relations, and Cardinality, Definition 1.3.3), functions and when two are equal (Sets, Relations, and Cardinality, Definition 1.4.1, Sets, Relations, and Cardinality, Proposition 1.4.1), injective, surjective and bijective maps, composites and inverses (Sets, Relations, and Cardinality, Definition 1.4.3, Sets, Relations, and Cardinality, Definition 1.4.4, Sets, Relations, and Cardinality, Definition 1.4.5, Sets, Relations, and Cardinality, Definition 1.4.2, Sets, Relations, and Cardinality, Theorem 1.4.4, Sets, Relations, and Cardinality, Definition 1.5.2, Sets, Relations, and Cardinality, Theorem 1.5.4), images (Sets, Relations, and Cardinality, Definition 1.6.1), and, for review exercise R2 of Section 1.7, left and right inverses (Sets, Relations, and Cardinality, Definition 1.5.1, Sets, Relations, and Cardinality, Proposition 1.5.2, Sets, Relations, and Cardinality, Theorem 1.5.1). From Sets, Relations, and Cardinality, Chapter 2: the recursion theorem and its proof (Sets, Relations, and Cardinality, Theorem 2.3.1), which Section 1.5 repeats on $\omega$ ; and well-ordering (Sets, Relations, and Cardinality, Theorem 2.1.3), induction from a base (Sets, Relations, and Cardinality, Theorem 2.2.1) and the arithmetic of $\mathbb{N}$ (Sets, Relations, and Cardinality, Lemma 2.1.1), which Sections 1.6 and 1.7 prove again on $\omega$ and compare with. From Sets, Relations, and Cardinality, Chapter 3, the axiom of choice (Sets, Relations, and Cardinality, Axiom 3.3.1), only to say that this chapter never uses it; and, for review exercise R1 of Section 1.7, the definition of an infinite set and the theorem that a finite set is not equinumerous with a proper subset (Sets, Relations, and Cardinality, Definition 3.1.3, Sets, Relations, and Cardinality, Theorem 3.1.9, read on $\omega$ through Section 1.7’s dictionary), with Hilbert’s hotel (Sets, Relations, and Cardinality, Example (Hilbert’s Hotel)). Section 1.7 also names results of Sets, Relations, and Cardinality, Chapters 2 and 3 about finite and countable sets, to say how the later chapters of this volume read them on $\omega$ ; apart from R1, it does not use them.

Time. About 30 hours on the core track (all of A, one B and one C per section, the exit checks); about 40 hours for everything.

Roadmap

Axioms for Sets. Six axioms, (Z1)–(Z6), for making sets and telling them apart, why Separation needs a set to cut from, and the sets they name: the empty set, unordered pairs, unions, intersections and differences, each unique by Extensionality.
Ordered Pairs Built from Sets. Kuratowski’s pair $\{\{a\}, \{a, b\}\}$ , three shorter encodings that fail, the proof of the characteristic property with the case $a = b$ on its own, the product $A \times B$ as a set, and the working rules (W1)–(W5) of Sets, Relations, and Cardinality, Section 1.1 recovered from the axioms.
Successors, Inductive Sets and the Natural Numbers. The successor $\mathrm{S}(x) = x \cup \{x\}$ and the numerals $0 = \emptyset$ , $1 = \{0\}$ , $2 = \{0, 1\}$ , inductive sets and the axiom of infinity (Z7), $\omega$ as the least inductive set, and induction on $\omega$ proved as a theorem.
The Natural Numbers Satisfy Peano’s Axioms. Transitive sets, the facts that no natural number is an element of itself and that every non-zero one is a successor, Peano’s axioms (P1)–(P5) for $\omega$ , Peano systems with a structure for each of (P3)–(P5) that fails it alone, and the theorem that no pair is a natural number.
The Recursion Theorem; Addition and Multiplication. The recursion theorem proved on $\omega$ by gluing partial solutions on the sets $\mathrm{S}(n)$ , with no order needed; addition and multiplication defined by recursion, $n + 1 = \mathrm{S}(n)$ , and the laws of arithmetic, each by an induction on the variable the recursion runs on.
Order and Well-Ordering of the Natural Numbers. “Less than” defined as “element of” and proved a strict total order, each number the set of the numbers below it; well-ordering, by an induction on the numbers that contain no element of the set; order tied to arithmetic, with subtraction and induction from any base; powers and parity; and $n$ -tuples and lists of variable length as sets.
All Peano Systems Are Alike. Isomorphisms of Peano systems, the categoricity theorem (every Peano system is a copy of $\omega$ by exactly one isomorphism), addition, multiplication and order carried along it, the identification of $\omega$ with Sets, Relations, and Cardinality, Chapter 2’s $\mathbb{N}$ , and the dictionary by which the later chapters cite Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapters 2 and 3 on $\omega$ ; the review exercises reach back to Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapters 1 and 3.

Named moves

Show the set is inductive. To prove $P(n)$ for every $n \in \omega$ , form $\{ n \in \omega : P(n) \}$ and show that it contains $0$ and is closed under $\mathrm{S}$ . When the claim fails at $0$ , carry a disjunction “ $n = 0$ or …” instead.
Fix the others, induct on the recursion variable. In $m + n$ and $m \cdot n$ the recursion runs on the second argument $n$ ; fix $m$ (and any third variable) and induct on $n$ . A fact about the first argument, such as $0 + n = n$ , is a lemma to prove first, not a defining equation.
Build by recursion, compare by induction. A map out of $\omega$ comes from the recursion theorem; facts about it (one-to-one, onto, preserves $+$ ) are proved by induction, or by (P5) of the system it maps into.