1.5 Where $\mathbb{N}$ Comes From

Section 1.1 assumed one thing: that a Peano system exists (Axiom 1.1.1). Why should we believe it? Inside the real numbers there is one, the set $\mathbb{N}_{\mathbb{R}}$ of Sets and Functions (Corollary 1.4.3 (a)); but that answer presupposes $\mathbb{R}$ , an object far richer than the one it is meant to support. Axiomatic Set Theory gives a better answer: it builds a Peano system out of sets alone. This section describes that construction, without proofs. Nothing later in the book depends on it.

1.5.1. Sets as the raw material

Sets and Functions used sets as a working language. Its Section 1.2 stated a short list of working rules (W1)–(W6) that say which sets exist: a set may be cut out of a given set by a property (Sets and Functions, Definition 1.2.3), finitely many objects may be listed, sets have unions, the subsets of a set form a set (Sets and Functions, Definition 1.3.2), pairs from two sets form a product, and the number sets are sets. It did not derive these rules from more basic principles, and it took numbers and pairs as given objects. Two questions were left open: where these rules come from, and whether everything else, numbers and pairs included, is a set too.

Set theory answers both questions with a list of axioms. The construction below uses seven of them, each of which can be said in one line:

Extensionality. Two sets with the same elements are equal (Sets and Functions, Definition 1.2.1, now an axiom).
Empty set. There is a set with no elements, written $\emptyset$ .
Pairing. For any sets $a$ , $b$ there is a set $\{a, b\}$ whose elements are exactly $a$ and $b$ .
Union. For any set $\mathcal{S}$ of sets there is a set $\bigcup \mathcal{S}$ of the elements of its members; with pairing it gives $a \cup b$ .
Power set. For any set $X$ there is a set $\mathcal{P}\left( X \right)$ of all its subsets.
Specification. For any set $A$ and any property, the elements of $A$ with that property form a set.
Infinity. Some set contains $\emptyset$ and is closed under one particular step, the successor below.

Axiomatic Set Theory states the rest of the list (replacement, foundation and choice) and proves everything this section only describes.

Two features of the list matter for us. First, every axiom but extensionality says that some set exists. All of them except the empty set and infinity build their set out of sets already given; infinity is the one axiom that hands us a set no finite chain of building steps reaches. Second, there is nothing on the list except sets: no numbers, no points, no pairs as separate objects. So if natural numbers are to exist in this world, they must be particular sets. The question is which ones.

The answer is a matter of choice, not discovery. We need a set $\omega$ , an element of it to call zero and a function on it to call the successor, such that the three satisfy (P3), (P4) and (P5) of Definition 1.1.1. By Theorem 1.4.1, any two such choices are copies of each other, so it does not matter much which one we make. It only has to be made from the empty set by the operations on the list.

1.5.2. Zero and the successor as sets

There is only one set we are given outright, so it plays zero. For the successor we need a step that always produces something new, and the axioms offer a natural one: add the set itself as a new element. From here through Exercise B2, $0$ and $\mathrm{S}$ stand for these sets, except in a sentence that names $\mathbb{N}$ , $\mathbb{N}_{\mathbb{R}}$ or $\mathbb{R}$ , where they keep their usual meanings; elsewhere in the section, and in the rest of the book, they mean what they meant before: $0 \mathrel{:=} \emptyset , \qquad \mathrm{S}(x) \mathrel{:=} x \cup \{x\} .$ The right-hand side is a set by pairing (with $a = b = x$ ) and union. The first few numerals then come out as follows: $\begin{aligned} 1 &= \mathrm{S}(0) = \emptyset \cup \{\emptyset\} = \{0\} , \\ 2 &= \mathrm{S}(1) = \{0\} \cup \{1\} = \{0, 1\} , \\ 3 &= \mathrm{S}(2) = \{0, 1\} \cup \{2\} = \{0, 1, 2\} . \end{aligned}$ The pattern is the point of the choice: each numeral is the set of the numerals before it. So $n$ has exactly $n$ elements, and “ $m$ comes before $n$ ” can be read as $m \in n$ . Thus $2 \in 3$ , and also $2 \subseteq 3$ , since every element of $2$ is an element of $3$ .

This reading is a feature of this construction, not of the natural numbers. In $\mathbb{N}_{\mathbb{R}}$ the question “is $2 \in 3$ ?” has no meaning, and a warning in Section 1.4 records that no theorem of this book asks it. These sets are called the von Neumann numerals.

Quick check. Write $3$ using only $\emptyset$ and braces. Is $1 \subseteq 3$ ? Is $3 \in 1$ ?

Solution. $3 = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$ . Yes, $1 \subseteq 3$ : the only element of $1 = \{0\}$ is $0$ , and $0 \in 3$ . No, $3 \notin 1$ : the only element of $1$ is $\emptyset$ , and $3 \ne \emptyset$ , since $3$ has elements.

1.5.3. The least inductive set

We now want a set holding all the numerals and nothing else. The other axioms build $0$ , then $1$ , then $2$ , one at a time, each in finitely many steps. A set holding all of them at once is what the axiom of infinity is for, and its “particular step” is $\mathrm{S}$ .

A set $I$ is inductive if $\emptyset \in I$ and $\mathrm{S}(x) \in I$ whenever $x \in I$ . The axiom of infinity says that an inductive set exists. It says nothing more, and in particular it does not say that its inductive set holds only numerals.

The cure is the move of Sets and Functions, Proposition 1.3.2, with $I$ as the ambient set, $\emptyset$ as the starting element and $\mathrm{S}$ as the step. The inductive subsets of $I$ form a set, cut out of $\mathcal{P}\left( I \right)$ by specification, and their intersection is the smallest inductive subset of $I$ . Axiomatic Set Theory checks that it lies inside every inductive set, not only inside those contained in $I$ , and so does not depend on which $I$ the axiom supplied. This least inductive set is called $\omega$ .

Is $(\omega, \emptyset, \mathrm{S})$ a Peano system? The three axioms fare differently.

(P5) is leastness itself. A subset of $\omega$ that contains $\emptyset$ and is closed under $\mathrm{S}$ is inductive, so it contains the least inductive set $\omega$ ; hence it is $\omega$ .
(P3) is immediate. Every $\mathrm{S}(x)$ has $x$ as an element, and $\emptyset$ has none, so $\mathrm{S}(x) \ne \emptyset$ .
(P4) is the real work. From $x \cup \{x\} = y \cup \{y\}$ we want $x = y$ , and for arbitrary sets this needs care. For elements of $\omega$ it holds because each $n \in \omega$ has two properties that the pattern above suggests: an element of an element of $n$ is an element of $n$ , and $n \notin n$ . Axiomatic Set Theory proves both by induction on $\omega$ , and (P4) follows from them.

With all three in hand, $(\omega, \emptyset, \mathrm{S})$ is a Peano system. By Theorem 1.4.1 it is a copy of $(\mathbb{N}, 0, \mathrm{S})$ , by exactly one isomorphism, which carries the von Neumann numeral $n$ to the natural number $n$ . So the assumption Axiom 1.1.1 is not a new article of faith: it follows from the axioms for sets. A reader who trusts them may read Axiom 1.1.1 as a theorem.

Warning. An inductive set need not be $\omega$ . The axiom of infinity supplies some inductive set, which may hold much else. In the same way, $\mathbb{R}$ contains $0$ and is closed under $x \mapsto x + 1$ , and $\mathbb{R}$ is not $\mathbb{N}_{\mathbb{R}}$ . Arguments about natural numbers use leastness, that is (P5), and never closure alone.

1.5.4. Pairs as sets

One more object from Sets and Functions has to be found among the sets: the ordered pair. Sets and Functions, Definition 1.4.1 took $(a, b)$ as a new kind of object and asked only for its characteristic property, that $(a, b) = (c, d)$ exactly when $a = c$ and $b = d$ . Set theory has no new kinds of objects, so a pair must be a set built from $a$ and $b$ .

The first idea, $\{a, b\}$ , fails at once: $\{a, b\} = \{b, a\}$ , so it cannot record which coordinate came first. The standard repair marks the first coordinate by giving it a set of its own: $(a, b) \mathrel{:=} \bigl\{ \{a\}, \{a, b\} \bigr\} .$ This is the Kuratowski pair. The singleton $\{a\}$ names the first coordinate; the other member adds the second. When $a = b$ , both members are $\{a\}$ , and $(a, a) = \{\{a\}\}$ has a single element. Axiomatic Set Theory proves the characteristic property for this definition, by comparing the members of two such sets case by case.

Once pairs are sets, so is everything built from them. The product $A \times B$ is a set of pairs, cut out of $\mathcal{P}\left( \mathcal{P}\left( A \cup B \right) \right)$ by specification. A function is a set of pairs (Sets and Functions, Definition 2.1.1), so $\mathbb{N} \times \mathbb{N}$ , the operations $+$ and $\cdot$ of Section 1.2, and the isomorphisms of Section 1.4 are all sets. Chapter 2 of this volume needs none of this: it uses pairs only through the characteristic property of Sets and Functions, Definition 1.4.1.

Quick check. Is $\{\{0\}\}$ an ordered pair? If so, of what?

Solution. Yes: $(0, 0) = \{\{0\}, \{0, 0\}\} = \{\{0\}\}$ , since $\{0, 0\} = \{0\}$ . As a set, it is also $\{1\}$ , because $1 = \{0\}$ .

1.5.5. Exercises

A. Check your understanding

Exercise (A1)

(a) List the elements of $\mathrm{S}(3)$ .
(b) True or false: $2 \in 3$ and $2 \subseteq 3$ , for the von Neumann numerals.
(c) Why can the set $\{a, b\}$ not serve as the ordered pair $(a, b)$ ?
(d) Which Peano axiom is “ $\omega$ is the least inductive set” in disguise?

Solution.

(a) $\mathrm{S}(3) = 3 \cup \{3\}$ has the elements $0$ , $1$ , $2$ , $3$ ; it is the numeral $4$ .
(b) Both are true: $3 = \{0, 1, 2\}$ has $2$ as an element, and the elements $0$ , $1$ of $2$ are elements of $3$ .
(c) It forgets the order: $\{1, 2\} = \{2, 1\}$ , while the pairs $(1, 2)$ and $(2, 1)$ must differ, by the characteristic property, since $1 \ne 2$ .
(d) (P5): a subset of $\omega$ containing $\emptyset$ and closed under $\mathrm{S}$ is inductive, so by leastness it is all of $\omega$ .

B. Practice

Exercise (B1: Numerals by hand)

(a) Write $\mathrm{S}(4)$ as a set of numerals. How many elements does the numeral $n$ have, for $n \le 5$ ?
(b) Compute $2 \cup 3$ and $2 \cap 3$ .
(c) Is $\{1\} \subseteq 3$ ? Is $\{1\}$ one of the numerals $0, 1, \dots, 5$ ?

Solution.

(a) $\mathrm{S}(4) = \{0, 1, 2, 3\} \cup \{4\} = \{0, 1, 2, 3, 4\}$ , the numeral $5$ . The numeral $n$ is $\{0, 1, \dots, n - 1\}$ , and it has $n$ elements: $0 = \emptyset$ has none, $1 = \{0\}$ has one, and so on, going up one numeral at a time. The step $\mathrm{S}(k) = k \cup \{k\}$ gives one more element than $k$ has, because $k \notin k$ : the elements of $k$ are earlier numerals, which have fewer elements than $k$ , so none of them is $k$ . So $0, 1, \dots, 5$ have $0, 1, \dots, 5$ elements, and in particular they are all different.
(b) $2 = \{0, 1\}$ and $3 = \{0, 1, 2\}$ , so $2 \cup 3 = \{0, 1, 2\} = 3$ and $2 \cap 3 = \{0, 1\} = 2$ : the union is the larger numeral and the intersection the smaller.
(c) Yes, $\{1\} \subseteq 3$ , since $1 \in 3$ . But $\{1\}$ is none of the numerals $0, \dots, 5$ . It has one element, so by (a) the only candidate is $1 = \{0\}$ ; and $\{1\} \ne \{0\}$ , since their only elements $1$ and $0$ differ ( $1$ has an element, $0$ has none).

Exercise (B2: Pairs as sets)

Write $(0, 1)$ , $(1, 0)$ and $(1, 1)$ as Kuratowski pairs, using numerals where you can. Show directly that $(0, 1) \ne (1, 0)$ . How many elements does $(a, b)$ have when $a \ne b$ , and when $a = b$ ?

Solution. $(0, 1) = \{\{0\}, \{0, 1\}\} = \{1, 2\}$ , since $\{0\} = 1$ and $\{0, 1\} = 2$ . Next, $(1, 0) = \{\{1\}, \{1, 0\}\} = \{\{1\}, 2\}$ , and $(1, 1) = \{\{1\}, \{1, 1\}\} = \{\{1\}\}$ .

The set $1$ is an element of $(0, 1)$ . It is not an element of $(1, 0)$ : it is not $\{1\}$ , since $0 \in 1$ while the only element of $\{1\}$ is $1 \ne 0$ ; and it is not $2$ , since $1 \in 2$ while $1 \notin 1 = \{0\}$ . So the two sets have different elements, and $(0, 1) \ne (1, 0)$ .

If $a \ne b$ , then $\{a\} \ne \{a, b\}$ , because $b$ lies in the second and not in the first; so $(a, b)$ has two elements. If $a = b$ , then $(a, a) = \{\{a\}\}$ has one. (Note also that $(0, 1) = \{1, 2\}$ is not a numeral, although both its elements are: it is not $0 = \emptyset$ , since it has elements, and every other numeral $\{0, 1, \dots, n - 1\}$ contains $0$ , which $\{1, 2\}$ does not, since $1$ and $2$ have elements and $0$ has none.)

C. Going deeper

Exercise (C1: Closed is not least)

Each of the sets $\mathbb{R}$ , $[0, \infty)$ and $\mathbb{N}_{\mathbb{R}} \cup \{ n + \tfrac12 : n \in \mathbb{N}_{\mathbb{R}} \}$ contains $0$ and is closed under $x \mapsto x + 1$ . For each, with $e = 0$ and $s(x) = x + 1$ , decide which of (P3), (P4), (P5) hold. Then find the least subset of $\mathbb{R}$ that contains $0$ and is closed under $x \mapsto x + 1$ , and prove that it is least.

Solution. This exercise is about subsets of the real numbers of Sets and Functions, so it uses their arithmetic freely, as Corollary 1.4.3 (a) does; facts about $\mathbb{N}_{\mathbb{R}}$ itself come from Sets and Functions, Lemma 3.1.1.

(P4) holds in all three: $x + 1 = y + 1$ gives $x = y$ .

(P3) fails only in $\mathbb{R}$ , where $s(-1) = -1 + 1 = 0$ . In the other two sets, $x + 1 = 0$ would need $x = -1$ . But every $n \in \mathbb{N}_{\mathbb{R}}$ has $n \ge 0$ (Sets and Functions, Lemma 3.1.1 (a)), so $-1 \notin \mathbb{N}_{\mathbb{R}}$ , $-1 \notin [0, \infty)$ , and $n + \tfrac12 \ge \tfrac12 > -1$ .

(P5) fails in all three. The subset $\mathbb{N}_{\mathbb{R}}$ of each contains $0$ and is closed under $x \mapsto x + 1$ (it lies in $[0, \infty)$ by the same clause (a)), but it is not the whole set: it misses $-1 \in \mathbb{R}$ (as above), and $\tfrac12$ , which lies in $[0, \infty)$ and in the third set, by Sets and Functions, Lemma 3.1.1 (e) with $n = 0$ (no natural number lies strictly between $0$ and $1$ ).

The least such set is $\mathbb{N}_{\mathbb{R}}$ . It contains $0$ and is closed under $x \mapsto x + 1$ . Let $T \subseteq \mathbb{R}$ be any set with these two properties. Then $T \cap \mathbb{N}_{\mathbb{R}}$ contains $0$ , and it is closed: if $n \in T \cap \mathbb{N}_{\mathbb{R}}$ , then $n + 1 \in T$ and $n + 1 \in \mathbb{N}_{\mathbb{R}}$ . By the set form of Logic and Proof, Axiom 4.2.1 (the remark at the start of Sets and Functions, Section 3.1), the only such subset of $\mathbb{N}_{\mathbb{R}}$ is $\mathbb{N}_{\mathbb{R}}$ itself, so $T \cap \mathbb{N}_{\mathbb{R}} = \mathbb{N}_{\mathbb{R}}$ , that is, $\mathbb{N}_{\mathbb{R}} \subseteq T$ .

The three sets show the point of the warning above: closure under the step is cheap, and only the least closed set is the natural numbers.

R. Review

Exercise (R1)

Prove that $\mathbb{N} \setminus \{0\}$ is infinite.

Solution. We read Sets and Functions, Definition 4.1.3 and Sets and Functions, Theorem 4.1.9 on subsets of $\mathbb{N}$ , through the citing rule of Section 1.4 (group (i)). Write $A \mathrel{:=} \mathbb{N} \setminus \{0\}$ and $B \mathrel{:=} \mathbb{N} \setminus \{0, 1\}$ , where $1 = \mathrm{S}(0)$ (Definition 1.2.1 (c)). Consider $\mathrm{S}$ restricted to $A$ , with codomain $B$ . Its values lie in $B$ : for $n \in A$ , $\mathrm{S}(n) \ne 0$ by (P3) for $\mathbb{N}$ (Axiom 1.1.1), and $\mathrm{S}(n) \ne \mathrm{S}(0) = 1$ by (P4), since $n \ne 0$ . It is injective by (P4). It is onto $B$ : if $m \in B$ , then $m \ne 0$ , so $m = \mathrm{S}(k)$ for some $k \in \mathbb{N}$ by Proposition 1.1.3 (a), and $k \ne 0$ because $m \ne 1 = \mathrm{S}(0)$ ; so $k \in A$ . Hence it is a bijection $A \to B$ . The set $B$ is a proper subset of $A$ : $B \subseteq A$ is clear, and $1 \in A$ , since $1 = \mathrm{S}(0) \ne 0$ by (P3), while $1 \notin B$ . By Sets and Functions, Theorem 4.1.9, a finite set is not equinumerous with any proper subset; so $A$ is not finite, that is, it is infinite (Sets and Functions, Definition 4.1.3).

Exercise (R2)

Let $D \colon \mathbb{N} \to \mathbb{N}$ be $D(n) \mathrel{:=} \mathrm{S}(\mathrm{S}(n))$ . Show that $D$ has a left inverse and no right inverse. Write a left inverse down explicitly. Is it the only one?

Solution. No right inverse. A function with a right inverse is surjective (Sets and Functions, Proposition 2.4.2), and $D$ is not: $0$ is not a value, since $D(n) = \mathrm{S}(\mathrm{S}(n)) \ne 0$ by (P3) for $\mathbb{N}$ .

A left inverse. Write $1 = \mathrm{S}(0)$ (Definition 1.2.1 (c)). Let $L \colon \mathbb{N} \to \mathbb{N}$ have the graph $G \mathrel{:=} \bigl\{ (n, k) \in \mathbb{N} \times \mathbb{N} : (n \in \{0, 1\} \text{ and } k = 0) \text{ or } n = \mathrm{S}(\mathrm{S}(k)) \bigr\} .$ Each $n \in \mathbb{N}$ has exactly one partner. If $n = 0$ , the partner $k = 0$ works, and no $k$ has $0 = \mathrm{S}(\mathrm{S}(k))$ , by (P3). If $n = 1$ , the partner $k = 0$ works, and no $k$ has $\mathrm{S}(0) = \mathrm{S}(\mathrm{S}(k))$ : by (P4) that would give $0 = \mathrm{S}(k)$ , against (P3). If $n \notin \{0, 1\}$ , then $n \ne 0$ , so $n = \mathrm{S}(m)$ for exactly one $m$ , by Proposition 1.1.3 (a); this $m$ is not $0$ , since $n \ne \mathrm{S}(0)$ , so $m = \mathrm{S}(k)$ for exactly one $k$ , by Proposition 1.1.3 (a) again. Thus $n = \mathrm{S}(\mathrm{S}(k))$ for exactly one $k$ . So $L$ is a function (Sets and Functions, Definition 2.1.1) with $L(0) = L(1) = 0$ and $L(\mathrm{S}(\mathrm{S}(k))) = k$ . Hence $L(D(n)) = n$ for every $n \in \mathbb{N}$ , that is, $L \circ D = \operatorname{id}_{\mathbb{N}}$ : $L$ is a left inverse of $D$ (Sets and Functions, Definition 2.4.1 (a)). This matches Sets and Functions, Theorem 2.4.1: $D$ is injective, by (P4) applied twice, and $\mathbb{N} \ne \emptyset$ .

Not unique. The values of a left inverse at $0$ and $1$ are never used, since neither is of the form $D(n)$ ; setting $L'(0) \mathrel{:=} 5$ , $L'(1) \mathrel{:=} 0$ and $L'(\mathrm{S}(\mathrm{S}(k))) \mathrel{:=} k$ gives another left inverse.

Exercise (R3)

Let $M = \{0, 1\}$ , $e = 0$ and $s(0) = s(1) = 1$ . Show that there is no function $f \colon M \to \mathbb{N}$ with $f(0) = 0$ and $f(s(x)) = \mathrm{S}(f(x))$ for every $x \in M$ . Which of the Peano axioms play the part, for definitions on $\mathbb{N}$ , that a theorem about reading formulas plays for definitions on formulas?

Solution. Suppose $f$ exists. Taking $x = 1$ , $f(1) = f(s(1)) = \mathrm{S}(f(1))$ . But no $n \in \mathbb{N}$ has $n = \mathrm{S}(n)$ (Proposition 1.1.3 (b)). So no such $f$ exists. (Taking $x = 0$ instead gives $f(1) = \mathrm{S}(0) = 1$ , so the two equations at the input $1$ also contradict each other.)

The trouble is that $1$ is built in two ways, as $s(0)$ and as $s(1)$ , and the two ways ask for different values. In Logic and Proof, Chapter 4, Logic and Proof, Theorem 4.3.4 defines functions on formulas, and what makes it work is Logic and Proof, Theorem 4.3.3: each compound formula is built from its parts in exactly one way. On $\mathbb{N}$ the same job is done by (P3) and (P4): $0$ is not a successor, so its value is not asked for twice, and a successor is the successor of exactly one number, so the equation at $\mathrm{S}(n)$ asks for one thing. The structure $M$ fails (P4), since $s(0) = s(1)$ , though it satisfies (P5).