1.7 All Peano Systems Are Alike

Section 1.4 proved that $(\omega, 0, \mathrm{S})$ is a Peano system (Theorem 1.4.2, Definition 1.4.2), and Sections 1.5 and 1.6 built $+$ , $\cdot$ and $<$ on it. One question is left. Sets, Relations, and Cardinality, Chapter 2 worked with a set $\mathbb{N}$ inside the familiar real numbers, and this chapter has built a quite different set $\omega$ out of $\emptyset$ . In what sense are they the same? This section answers: any two Peano systems are copies of each other, by exactly one matching, which also carries $+$ , $\cdot$ and $<$ across. Then it says what the later chapters may take from Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2 when they write $\mathbb{N}$ for $\omega$ .

1.7.1. Two Peano systems, and what “alike” should mean

Here is a second Peano system, inside $\omega$ itself: $(\omega \setminus \{0\}, 1, \mathrm{S})$ , the natural numbers from $1$ on, with the same successor. Exercise C1 of Section 1.4 asked you to check it; the check is three lines.

$\mathrm{S}$ maps $\omega \setminus \{0\}$ into itself, since $\mathrm{S}(n) \ne 0$ by Theorem 1.4.2 (P3).
(P3) holds with $e = 1$ : if $\mathrm{S}(n) = 1 = \mathrm{S}(0)$ , then $n = 0$ by (P4) of Theorem 1.4.2, and $0 \notin \omega \setminus \{0\}$ . (P4) holds because $\mathrm{S}$ is injective on all of $\omega$ .
(P5) holds: if $A \subseteq \omega \setminus \{0\}$ contains $1$ and is closed under $\mathrm{S}$ , then $\{0\} \cup A$ contains $0$ and is closed under $\mathrm{S}$ (as $\mathrm{S}(0) = 1 \in A$ ), so it is $\omega$ by Theorem 1.3.3 (a), and $A = \omega \setminus \{0\}$ .

Its starting point is $1$ , not $\emptyset$ , yet it counts the same way: $n \mapsto \mathrm{S}(n)$ pairs $0, 1, 2, \dots$ with $1, 2, 3, \dots$ , sends start to start, and turns one step into one step.

That is the right meaning of “alike”. For Peano systems $(M, e, s)$ and $(M', e', s')$ , call a bijection $\psi \colon M \to M'$ an isomorphism if $\psi(e) = e' \quad \text{and} \quad \psi\bigl(s(x)\bigr) = s'\bigl(\psi(x)\bigr) \ \text{ for every } x \in M .$ In words: $\psi$ renames the elements, sends the starting point to the starting point, and it does not matter whether we first step and then rename, or first rename and then step.

Warning. Being equinumerous is not enough. The bijection $\tau \colon \omega \to \omega$ that exchanges $1$ and $2$ and fixes every other number satisfies $\tau(0) = 0$ , but $\tau(\mathrm{S}(0)) = \tau(1) = 2$ , while $\mathrm{S}(\tau(0)) = \mathrm{S}(0) = 1$ . So $\tau$ is a bijection from a Peano system to itself that is not an isomorphism: it does not respect the successor. Categoricity, below, is a statement about isomorphisms, and it says much more than “same size”.

1.7.2. The categoricity theorem

The theorem says that every Peano system is an isomorphic copy of $\omega$ , and so any two are copies of each other, in only one way.

Theorem 1.7.1 (Categoricity of the Peano Axioms)

Let $(M, e, s)$ be a Peano system.

(a) There is exactly one function $\varphi \colon \omega \to M$ with $\varphi(0) = e$ and $\varphi(\mathrm{S}(n)) = s(\varphi(n))$ for every $n \in \omega$ .
(b) This $\varphi$ is a bijection.
(c) For any two Peano systems $(M, e, s)$ and $(M', e', s')$ there is exactly one bijection $\psi \colon M \to M'$ with $\psi(e) = e'$ and $\psi(s(x)) = s'(\psi(x))$ for every $x \in M$ .

Try it first (ten minutes): given a Peano system $(M, e, s)$ , which map $\omega \to M$ would you build, with which theorem, and how would you show that it is onto?

Idea. The attempt meets three obstacles, one for each part.

① Which map. It is forced: $0$ must go to $e$ , then $1$ to $s(e)$ , then $2$ to $s(s(e))$ , and so on. But “and so on” is not a definition. Theorem 1.5.1 turns it into one, with $X = M$ , starting value $e$ and step $x \mapsto s(x)$ ; it gives existence and uniqueness at once.

② Onto. We know nothing about the elements of $M$ one by one, so we cannot show “each $x \in M$ is $s(\dots s(e))$ ” directly. What we have is (P5) for $M$ , which speaks about subsets. So look at the image of $\varphi$ : it contains $e$ and is closed under $s$ , and (P5) does the rest.

③ One-to-one. Prove “ $\varphi(m) = \varphi(n) \Rightarrow m = n$ ” by induction on $n$ . If $m$ is fixed before the induction, the hypothesis at $n$ speaks about that one $m$ , while the step needs it at the predecessor of $m$ . So “for every $m$ ” goes inside the property. The base and the step then use (P3) and (P4) for $M$ : a successor is never $e$ , and equal successors have equal predecessors.

For (c), compose: go back from $M$ to $\omega$ along $\varphi^{-1}$ , then forward to $M'$ along $\varphi'$ .

Before reading on: which axiom of $M$ gives surjectivity, and which give injectivity?

Proof. (a) Let $g \colon \omega \times M \to M$ be $g(n, x) \mathrel{:=} s(x)$ ; its graph $\{ ((n, x), y) \in (\omega \times M) \times M : y = s(x) \}$ is a set by (Z6) inside the product of Proposition 1.2.2, and each $(n, x)$ has exactly one partner $s(x)$ because $s$ is a function. By Theorem 1.5.1 with $X = M$ and $a = e$ , there is exactly one $\varphi \colon \omega \to M$ with $\varphi(0) = e$ and $\varphi(\mathrm{S}(n)) = g(n, \varphi(n)) = s(\varphi(n))$ for every $n \in \omega$ .

(b), onto. Let $B \mathrel{:=} \varphi(\omega) \subseteq M$ , the image of $\omega$ under $\varphi$ (Sets, Relations, and Cardinality, Definition 1.6.1). Then $e = \varphi(0) \in B$ . If $x \in B$ , say $x = \varphi(n)$ with $n \in \omega$ , then $\mathrm{S}(n) \in \omega$ by Theorem 1.4.2 (P2), and $s(x) = s(\varphi(n)) = \varphi(\mathrm{S}(n)) \in B$ . So $B$ contains $e$ and is closed under $s$ , and (P5) for $M$ gives $B = M$ . Hence $\varphi$ is surjective (Sets, Relations, and Cardinality, Definition 1.4.4).

(b), one-to-one. Let $Q(n)$ be “for every $m \in \omega$ , if $\varphi(m) = \varphi(n)$ , then $m = n$ ”. We prove $Q(n)$ for every $n \in \omega$ by Theorem 1.3.3 (b).

Base case. Let $m \in \omega$ with $\varphi(m) = \varphi(0) = e$ . Suppose $m \ne 0$ . Then $m = \mathrm{S}(k)$ for some $k \in \omega$ (Lemma 1.4.1 (d)), and $\varphi(m) = s(\varphi(k)) \ne e$ by (P3) for $M$ , a contradiction. So $m = 0$ .

Inductive step. Let $n \in \omega$ with $Q(n)$ , and let $m \in \omega$ with $\varphi(m) = \varphi(\mathrm{S}(n)) = s(\varphi(n))$ . If $m = 0$ , then $s(\varphi(n)) = \varphi(0) = e$ , against (P3) for $M$ . So $m \ne 0$ , and $m = \mathrm{S}(k)$ for some $k \in \omega$ (Lemma 1.4.1 (d)). Then $s(\varphi(k)) = \varphi(m) = s(\varphi(n))$ , so $\varphi(k) = \varphi(n)$ by (P4) for $M$ , and $k = n$ by $Q(n)$ , applied to $k$ in the place of $m$ . Hence $m = \mathrm{S}(k) = \mathrm{S}(n)$ , which is $Q(\mathrm{S}(n))$ .

So $\varphi$ is injective (Sets, Relations, and Cardinality, Definition 1.4.3), and with the first half it is a bijection (Sets, Relations, and Cardinality, Definition 1.4.5).

(c) Let $\varphi \colon \omega \to M$ and $\varphi' \colon \omega \to M'$ be the maps of (a) for the two systems; both are bijections by (b). By Sets, Relations, and Cardinality, Theorem 1.5.4, $\varphi$ has an inverse $\varphi^{-1} \colon M \to \omega$ , and we set $\psi \mathrel{:=} \varphi' \circ \varphi^{-1}$ (Sets, Relations, and Cardinality, Definition 1.4.2). The two equations $\varphi \circ \varphi^{-1} = \operatorname{id}_M$ and $\varphi^{-1} \circ \varphi = \operatorname{id}_\omega$ of Sets, Relations, and Cardinality, Definition 1.5.2 also say that $\varphi$ is an inverse of $\varphi^{-1}$ , so $\varphi^{-1}$ is a bijection by Sets, Relations, and Cardinality, Theorem 1.5.4. Hence $\psi$ is a bijection as a composite of bijections (Sets, Relations, and Cardinality, Theorem 1.4.4 (c)).

$\psi$ has the two properties. Since $\varphi(0) = e$ , we have $\varphi^{-1}(e) = 0$ , so $\psi(e) = \varphi'(0) = e'$ . Let $x \in M$ and $n \mathrel{:=} \varphi^{-1}(x)$ , so $x = \varphi(n)$ . Then $s(x) = \varphi(\mathrm{S}(n))$ , so $\varphi^{-1}(s(x)) = \mathrm{S}(n)$ , and $\psi\bigl(s(x)\bigr) = \varphi'\bigl(\mathrm{S}(n)\bigr) = s'\bigl(\varphi'(n)\bigr) = s'\bigl(\psi(x)\bigr) .$

Uniqueness. Let $\chi \colon M \to M'$ be any function with $\chi(e) = e'$ and $\chi(s(x)) = s'(\chi(x))$ for every $x \in M$ . Then $\chi \circ \varphi \colon \omega \to M'$ satisfies $(\chi \circ \varphi)(0) = \chi(e) = e'$ and $(\chi \circ \varphi)\bigl(\mathrm{S}(n)\bigr) = \chi\bigl(s(\varphi(n))\bigr) = s'\bigl((\chi \circ \varphi)(n)\bigr)$ for every $n \in \omega$ . By the uniqueness in (a), for the system $M'$ , $\chi \circ \varphi = \varphi'$ . So for every $x \in M$ , $\chi(x) = \chi(\varphi(\varphi^{-1}(x))) = \varphi'(\varphi^{-1}(x)) = \psi(x)$ , and $\chi = \psi$ by Sets, Relations, and Cardinality, Proposition 1.4.1. This proves the theorem.

The proof is the third named move of the chapter, build by recursion, compare by induction: the map out of $\omega$ came from the recursion theorem, and every fact about it (onto, one-to-one) came from an induction or from (P5). The uniqueness in (c) is stronger than stated: no function at all, bijective or not, other than $\psi$ respects $e$ and $s$ .

Each axiom of $M$ has a job in (b), and the structures of Example (Each axiom is needed) show each job failing. These are not Peano systems, so the theorem does not apply to them. But for each of them Theorem 1.5.1, with $X = M$ , $a = e$ and $g(n, x) = s(x)$ exactly as in the proof of (a), still gives exactly one $\varphi \colon \omega \to M$ with $\varphi(0) = e$ and $\varphi(\mathrm{S}(n)) = s(\varphi(n))$ .

In structure (i), $M = \{0\}$ with $s(0) = 0$ , which fails (P3) only, $\varphi$ is the constant map $0$ , not injective: $\varphi(1) = s(\varphi(0)) = 0 = \varphi(0)$ .
In structure (ii), $M = \{0, 1\}$ with $s(0) = s(1) = 1$ , which fails (P4) only, $\varphi(1) = \varphi(2) = 1$ , again not injective.
In the natural numbers beside a two-sided chain, structure (iii), which fails (P5) only, $\varphi$ is $n \mapsto (n, 0)$ (remark below), which is injective by Theorem 1.2.1, but not onto, as the remark below shows.

Remark. What induction buys. In structure (iii) of Example (Each axiom is needed), the natural numbers beside a two-sided chain (a copy of $\omega$ next to a copy of $\mathbb{Z}$ ), $M = \omega \times 3$ with $e = (0, 0)$ , the map $\varphi$ still exists, by Theorem 1.5.1 as above. It is $\varphi(n) = (n, 0)$ , by the uniqueness half of Theorem 1.5.1: $n \mapsto (n, 0)$ sends $0$ to $e$ and satisfies the recursion, as $s(n, 0) = (\mathrm{S}(n), 0)$ . Its image $\omega \times \{0\}$ misses $(0, 1)$ , so $\varphi$ is not onto. Exercise C2 asks the reverse question: is there a map $M \to \omega$ that respects the two structures?

Quick check. For the Peano system $(\omega \setminus \{0\}, 1, \mathrm{S})$ of the first subsection, what is the map $\varphi$ of Theorem 1.7.1 (a)? What is $\varphi(3)$ ?

Solution. $\varphi(n) = \mathrm{S}(n) = n + 1$ . Indeed $n \mapsto \mathrm{S}(n)$ maps $\omega$ into $\omega \setminus \{0\}$ by (P3), sends $0$ to $\mathrm{S}(0) = 1$ , and satisfies $\mathrm{S}(\mathrm{S}(n)) = \mathrm{S}(\varphi(n))$ ; by the uniqueness in (a), it is $\varphi$ . So $\varphi(3) = \mathrm{S}(3) = 4$ . Step by step: $\varphi(0) = 1$ , $\varphi(1) = \mathrm{S}(1) = 2$ , $\varphi(2) = 3$ , $\varphi(3) = 4$ .

1.7.3. Arithmetic and order travel along the isomorphism

An isomorphism matches $e$ and $s$ . Addition and multiplication on $\omega$ were built from $0$ and $\mathrm{S}$ alone, by recursion (Definition 1.5.1), and $<$ can be described by $+$ (Proposition 1.6.3 (a)). So we expect the matching to carry them across, as long as the other system has operations defined by the same equations.

Proposition 1.7.2 (Isomorphisms Preserve Arithmetic and Order)

Let $(M, e, s)$ be a Peano system, and let $\oplus, \otimes \colon M \times M \to M$ be functions such that, for all $x, y \in M$ , $\begin{aligned} x \oplus e &= x, & x \oplus s(y) &= s(x \oplus y), \\ x \otimes e &= e, & x \otimes s(y) &= (x \otimes y) \oplus x . \end{aligned}$ Let $\varphi \colon \omega \to M$ be the bijection of Theorem 1.7.1. Then for all $m, n \in \omega$ :

(a) $\varphi(m + n) = \varphi(m) \oplus \varphi(n)$ ;
(b) $\varphi(m n) = \varphi(m) \otimes \varphi(n)$ ;
(c) $m < n$ if and only if $\varphi(n) = \varphi(m) \oplus z$ for some $z \in M$ with $z \ne e$ .

Idea. For (a) and (b), fix $m$ and induct on $n$ , the variable the recursions run on: each side obeys the same two equations, the base from $0$ and the step from $\mathrm{S}$ , and $\varphi$ turns one set of equations into the other. For (c), translate Proposition 1.6.3 (a), “ $m < n$ iff $n = m + j$ with $j \ne 0$ ”, through (a), using that $\varphi$ is a bijection with $\varphi(0) = e$ .

Proof. (a) Fix $m \in \omega$ ; we induct on $n$ (Theorem 1.3.3 (b)). Base case: $\varphi(m + 0) = \varphi(m) = \varphi(m) \oplus e = \varphi(m) \oplus \varphi(0)$ , by Definition 1.5.1 (a) and the first equation for $\oplus$ . Step: if $\varphi(m + n) = \varphi(m) \oplus \varphi(n)$ , then $\begin{aligned} \varphi\bigl(m + \mathrm{S}(n)\bigr) &= \varphi\bigl(\mathrm{S}(m + n)\bigr) = s\bigl(\varphi(m + n)\bigr) \\ &= s\bigl(\varphi(m) \oplus \varphi(n)\bigr) = \varphi(m) \oplus s\bigl(\varphi(n)\bigr) = \varphi(m) \oplus \varphi\bigl(\mathrm{S}(n)\bigr) , \end{aligned}$ by Definition 1.5.1 (a), the equation of $\varphi$ , the hypothesis, the second equation for $\oplus$ , and the equation of $\varphi$ again.

(b) Fix $m \in \omega$ and induct on $n$ . Base case: $\varphi(m \cdot 0) = \varphi(0) = e = \varphi(m) \otimes e = \varphi(m) \otimes \varphi(0)$ , by Definition 1.5.1 (b) and the first equation for $\otimes$ . Step: if $\varphi(mn) = \varphi(m) \otimes \varphi(n)$ , then $\begin{aligned} \varphi\bigl(m \cdot \mathrm{S}(n)\bigr) &= \varphi(mn + m) = \varphi(mn) \oplus \varphi(m) \\ &= \bigl(\varphi(m) \otimes \varphi(n)\bigr) \oplus \varphi(m) = \varphi(m) \otimes s\bigl(\varphi(n)\bigr) = \varphi(m) \otimes \varphi\bigl(\mathrm{S}(n)\bigr) , \end{aligned}$ by Definition 1.5.1 (b), part (a) just proved, the hypothesis, the second equation for $\otimes$ , and the equation of $\varphi$ .

(c) By Proposition 1.6.3 (a), $m < n$ if and only if $n = m + j$ for some $j \in \omega$ with $j \ne 0$ .

$(\Rightarrow)$ Let $n = m + j$ with $j \ne 0$ . By (a), $\varphi(n) = \varphi(m) \oplus \varphi(j)$ . Put $z \mathrel{:=} \varphi(j)$ . Since $\varphi$ is injective (Theorem 1.7.1 (b)), $j \ne 0$ gives $z \ne \varphi(0) = e$ .

$(\Leftarrow)$ Let $z \in M$ with $z \ne e$ and $\varphi(n) = \varphi(m) \oplus z$ . Since $\varphi$ is onto (Theorem 1.7.1 (b)), $z = \varphi(j)$ for some $j \in \omega$ , and $j \ne 0$ because $\varphi(0) = e \ne z$ . By (a), $\varphi(n) = \varphi(m) \oplus \varphi(j) = \varphi(m + j)$ , so $n = m + j$ by injectivity. Hence $m < n$ . This proves the proposition.

So once a Peano system carries an addition and a multiplication obeying the recursive equations, $\varphi$ is an isomorphism for them too, and the order defined from $\oplus$ as in (c) is carried along as well. Nothing about $\oplus$ and $\otimes$ was assumed beyond the four equations.

1.7.4. Identifying the two sets of natural numbers

Now apply all this to the set $\mathbb{N}$ of Sets, Relations, and Cardinality, Chapter 2. Two different things are true, and it matters which one the later chapters lean on. One is a statement about Sets, Relations, and Cardinality, Chapter 2’s $\mathbb{N}$ , a subset of the familiar real numbers: it is a Peano system, so it is a copy of $\omega$ . The other is a statement about $\omega$ alone: the principles Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2 assumed or proved for $\mathbb{N}$ are theorems about $\omega$ , proved from the axioms (Z1)–(Z7).

Corollary 1.7.3 (ω Is the Natural Numbers)

(a) About Sets, Relations, and Cardinality, Chapter 2’s $\mathbb{N}$ . Let $\mathbb{N} \subseteq \mathbb{R}$ be the set of natural numbers as Sets, Relations, and Cardinality, Section 2.1 describes it, with (( )0), ( $\mathbb{N}$ S) and Logic and Proof, Axiom 4.2.1. With $e \mathrel{:=} 0$ and $s(n) \mathrel{:=} n + 1$ , it is a Peano system. There is exactly one bijection $\varphi \colon \omega \to \mathbb{N}$ with $\varphi(0) = 0$ and $\varphi(\mathrm{S}(n)) = \varphi(n) + 1$ for every $n \in \omega$ . For all $m, n \in \omega$ it satisfies $\varphi(m + n) = \varphi(m) + \varphi(n), \qquad \varphi(mn) = \varphi(m)\varphi(n),$ and $m < n$ if and only if $\varphi(m) < \varphi(n)$ ; and it sends each numeral of $\omega$ to the natural number of the same name.
(b) About $\omega$ , proved from (Z1)–(Z7). The statements of Logic and Proof, Axiom 4.2.1 and Sets, Relations, and Cardinality, Theorem 2.3.1, read with $\mathbb{N} \mathrel{:=} \omega$ and $n + 1 \mathrel{:=} \mathrm{S}(n)$ , are Theorem 1.3.3 (b) and Theorem 1.5.1. Induction started at a base $b \in \omega$ (the form of Sets, Relations, and Cardinality, Theorem 2.2.1 with base $n_0 = b$ ) is Proposition 1.6.3 (g).
(c) Each clause of Sets, Relations, and Cardinality, Lemma 2.1.1 holds on $\omega$ , with $n - m$ , for $m \le n$ , read as the unique $j \in \omega$ with $n = m + j$ of Proposition 1.6.3 (a).

Idea. For (a), check (P3)–(P5) for Sets, Relations, and Cardinality, Chapter 2’s $\mathbb{N}$ with the tools of Sets, Relations, and Cardinality, Section 2.1, and the equations of Proposition 1.7.2 with school arithmetic; then Theorem 1.7.1 and that proposition do the rest. Parts (b) and (c) are a matter of reading statements side by side and pointing to the label that proves each one on $\omega$ .

Before reading on: which clause do the later chapters actually use, when they build $\mathbb{Z}$ , $\mathbb{Q}$ and $\mathbb{R}$ ?

Proof. (a) The map $s$ sends $\mathbb{N}$ into $\mathbb{N}$ by ( $\mathbb{N}$ S). (P3): for $n \in \mathbb{N}$ , $n \ge 0$ by Sets, Relations, and Cardinality, Lemma 2.1.1 (a), so $n + 1 \ge 1 > 0$ and $n + 1 \ne 0$ . (P4): $m + 1 = n + 1$ gives $m = n$ , by subtracting $1$ in $\mathbb{R}$ . (P5): a subset of $\mathbb{N}$ that contains $0$ and is closed under $n \mapsto n + 1$ is $\mathbb{N}$ ; this is the set form of Logic and Proof, Axiom 4.2.1, the remark at the start of Sets, Relations, and Cardinality, Section 2.1. So $(\mathbb{N}, 0, s)$ is a Peano system (Definition 1.4.2), and Theorem 1.7.1 (a), (b) give exactly one $\varphi$ as stated, and it is a bijection.

For the operations, take $\oplus$ and $\otimes$ to be the addition and multiplication of $\mathbb{N}$ ; they are functions $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ by Sets, Relations, and Cardinality, Lemma 2.1.1 (b). The four equations of Proposition 1.7.2 read $x + 0 = x$ , $x + (y + 1) = (x + y) + 1$ , $x \cdot 0 = 0$ and $x(y + 1) = xy + x$ , which hold in $\mathbb{R}$ . That proposition gives $\varphi(m + n) = \varphi(m) + \varphi(n)$ and $\varphi(mn) = \varphi(m)\varphi(n)$ .

For the order we first show: for $x, y \in \mathbb{N}$ , $x < y$ if and only if $y = x + z$ for some $z \in \mathbb{N}$ with $z \ne 0$ . If $x < y$ , then $z \mathrel{:=} y - x \in \mathbb{N}$ by Sets, Relations, and Cardinality, Lemma 2.1.1 (d), and $z \ne 0$ since $y \ne x$ . Conversely, $z \ne 0$ gives $z \ge 1 > 0$ by Sets, Relations, and Cardinality, Lemma 2.1.1 (a), so $y = x + z > x$ . Now Proposition 1.7.2 (c), with $e = 0$ , says that $m < n$ if and only if $\varphi(n) = \varphi(m) + z$ for some $z \in \mathbb{N}$ with $z \ne 0$ , that is, if and only if $\varphi(m) < \varphi(n)$ .

Finally, $\varphi(0) = 0$ , and each numeral of $\omega$ is the successor of the one before (Definition 1.5.1 (c)), so $\varphi(1) = \varphi(\mathrm{S}(0)) = 0 + 1 = 1$ , $\varphi(2) = \varphi(\mathrm{S}(1)) = 1 + 1 = 2$ , and so on, one step for each numeral written.

(b) By the two equations of Definition 1.5.1 (a), $n + 1 = n + \mathrm{S}(0) = \mathrm{S}(n + 0) = \mathrm{S}(n)$ for every $n \in \omega$ (Section 1.5, “the successor is plus one”). With $\mathbb{N} \mathrel{:=} \omega$ , the statement of Logic and Proof, Axiom 4.2.1 becomes Theorem 1.3.3 (b), and the statement of Sets, Relations, and Cardinality, Theorem 2.3.1 is word for word Theorem 1.5.1. Induction from a base $b \in \omega$ is Proposition 1.6.3 (g).

(c) We take the clauses of Sets, Relations, and Cardinality, Lemma 2.1.1 in turn, for $m, n \in \omega$ .

- (a) “ $n \ge 0$ ; if $n \ne 0$ , then $n \ge 1$ ” is Theorem 1.6.1 (d).
- (b) “ $m + n \in \omega$ and $mn \in \omega$ ” holds because $+$ and $\cdot$ are functions $\omega \times \omega \to \omega$ (Definition 1.5.1).
- (c) If $n \ne 0$ , then $1 \le n$ by Theorem 1.6.1 (d), so $n = 1 + j$ for exactly one $j \in \omega$ by Proposition 1.6.3 (a); this $j$ is $n - 1$ , and it lies in $\omega$ .
- (d) If $m \le n$ , then $n - m \in \omega$ by Proposition 1.6.3 (a).
- (e) No $k \in \omega$ has $n < k < \mathrm{S}(n)$ , by Theorem 1.6.1 (b). For the second form, let $m < n$ . By trichotomy (Theorem 1.6.1 (a)), $\mathrm{S}(m) < n$ , $\mathrm{S}(m) = n$ or $n < \mathrm{S}(m)$ . The last gives $n \le m$ by Theorem 1.6.1 (b), and then $n \le m < n$ gives $n < n$ by transitivity, which (a) of that theorem rules out. So $m + 1 = \mathrm{S}(m) \le n$ .

This proves the corollary.

Clause (a) is the honest sense in which “ $\omega$ is $\mathbb{N}$ ”: the two are copies of each other by a unique isomorphism, which also matches $+$ , $\cdot$ and $<$ . But (a) is a theorem about Sets, Relations, and Cardinality, Chapter 2’s $\mathbb{N}$ , and its proof used the school arithmetic of $\mathbb{R}$ (in (P3), (P4), the four equations, the step describing $<$ by $+$ , and the numerals). The answer to the prompt is therefore (b), with (c): when a later chapter applies induction or recursion to $\omega$ , it uses a theorem proved here from the axioms for sets, and nothing about the school real numbers enters.

Warning. The isomorphism carries $0$ , successor, $+$ , $\cdot$ and $<$ , and nothing else. In $\omega$ , $0 \in 5$ and $2 \subseteq 3$ are true, because natural numbers here are sets (Example (The first natural numbers as sets)). In Sets, Relations, and Cardinality, Chapter 2’s picture numbers are not sets, and “ $0 \in 5$ ” has no meaning there. Such statements are facts about one particular construction, and no theorem of the later chapters asks them.

1.7.5. How later chapters cite Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2

In the rest of this volume, $\mathbb{N}$ means $\omega$ , with the $0$ , $+$ , $\cdot$ and $<$ of this chapter. The later chapters build $\mathbb{Z}$ , $\mathbb{Q}$ and finally $\mathbb{R}$ from it, and they cite results of Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapters 2 and 3 about $\mathbb{N}$ . This subsection says how such a citation is to be read, so that the construction of $\mathbb{R}$ never rests on the school $\mathbb{R}$ it is meant to replace.

The proofs in Sets, Relations, and Cardinality, Chapters 2 and 3 use the arithmetic of the real numbers freely: Sets, Relations, and Cardinality, Chapter 2’s “What you need” paragraph takes the arithmetic and order of $\mathbb{R}$ as school facts, Sets, Relations, and Cardinality, Section 2.1 says so for itself in “the rule for this section”, and Sets, Relations, and Cardinality, Chapter 3’s proofs do the same (Sets, Relations, and Cardinality, Theorem 3.4.1, for example, uses $1 - b$ ). So they do not rest only on (( )0), ( $\mathbb{N}$ S), Logic and Proof, Axiom 4.2.1, Sets, Relations, and Cardinality, Theorem 2.3.1 and Sets, Relations, and Cardinality, Lemma 2.1.1, and “they hold unchanged on $\omega$ ” would be false. What is true is a dictionary: each fact about $\mathbb{N}$ those proofs use has a counterpart proved on $\omega$ here.

used for $\mathbb{N}$ in Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapters 2, 3	read on $\omega$ as
Logic and Proof, Axiom 4.2.1; Sets, Relations, and Cardinality, Theorem 2.3.1	Corollary 1.7.3 (b): Theorem 1.3.3 (b); Theorem 1.5.1
Sets, Relations, and Cardinality, Theorem 2.2.1 with a base $n_0 = b \in \mathbb{N}$ , induction from a base	Proposition 1.6.3 (g)
Sets, Relations, and Cardinality, Theorem 2.1.3	Theorem 1.6.2
Sets, Relations, and Cardinality, Lemma 2.1.1	Corollary 1.7.3 (c)
other school arithmetic and order of natural numbers: closure under $+$ , $\cdot$ ; cancellation; trichotomy; $n - m$ for $m \le n$ ; “subtract $1$ from $m > n + 1$ ”	Theorem 1.5.3, Theorem 1.6.1, Proposition 1.6.3
powers $b^n$ of a natural number, Sets, Relations, and Cardinality, Definition 2.3.2, Sets, Relations, and Cardinality, Proposition 2.3.4 (a), (d), (e)	Proposition 1.6.4 (a)–(c); closure of $\omega$ under powers is the definition there
“no natural number is both even and odd”	Proposition 1.6.4 (d)

With the dictionary, the results of Sets, Relations, and Cardinality, Chapters 2 and 3 that later chapters cite fall into three groups.

(i) Results that run on $\omega$ through the dictionary. These are Sets, Relations, and Cardinality, Proposition 2.3.8 (for its $\mathbb{N}$ side, which is Sets, Relations, and Cardinality, Theorem 2.2.1 with base $1$ and Sets, Relations, and Cardinality, Lemma 2.1.1 (e)), Sets, Relations, and Cardinality, Definition 3.1.2, Sets, Relations, and Cardinality, Definition 3.1.3, Sets, Relations, and Cardinality, Corollary 3.1.3, Sets, Relations, and Cardinality, Theorem 3.1.9, Sets, Relations, and Cardinality, Lemma 3.2.1, Sets, Relations, and Cardinality, Theorem 3.2.2, Sets, Relations, and Cardinality, Proposition 3.2.3, Sets, Relations, and Cardinality, Proposition 3.2.4 and Sets, Relations, and Cardinality, Theorem 3.4.1 (where $\{0, 1\}^{\mathbb{N}}$ is indexed by $\omega$ , and $1 - b$ on $\{0, 1\}$ is read by Proposition 1.6.3 (a)), and Sets, Relations, and Cardinality, Exercise (C2: Counting products and functions) (a), cited later only from an exercise solution (its $\mathbb{N}$ side is an induction on $m$ , read by Corollary 1.7.3 (b), $mn \in \mathbb{N}$ , read by Corollary 1.7.3 (c), and $0 = 0 \cdot n$ and $mn + n = (m + 1)n$ , read by Theorem 1.5.3 (e)). Running a result on $\omega$ includes the results its proof cites: Sets, Relations, and Cardinality, Theorem 3.1.2, Sets, Relations, and Cardinality, Proposition 3.1.5, Sets, Relations, and Cardinality, Proposition 3.1.6, Sets, Relations, and Cardinality, Corollary 3.1.4, Sets, Relations, and Cardinality, Corollary 3.1.7 and the count “ $\{0, \dots, x\}$ has $x + 1$ elements” in the examples after Sets, Relations, and Cardinality, Definition 3.1.2 run through the same dictionary, and they belong to group (i) themselves. A later chapter may cite the results of group (i) anywhere.
(ii) Results that use school facts, and need Proposition 1.6.4 on $\omega$ . These are Sets, Relations, and Cardinality, Theorem 3.2.6 (powers by Sets, Relations, and Cardinality, Definition 2.3.2 and Sets, Relations, and Cardinality, Proposition 2.3.4 (a), (d), (e) over the school $\mathbb{R}$ , parity through Sets, Relations, and Cardinality, Theorem 2.2.3 on the school $\mathbb{Z}$ , and cancellation in $\mathbb{R}$ ), Sets, Relations, and Cardinality, Proposition 3.2.5 (parity through Sets, Relations, and Cardinality, Theorem 2.2.3), and through them Sets, Relations, and Cardinality, Corollary 3.2.7 (a). On $\omega$ , the powers are read as Proposition 1.6.4 (a)–(c), the parity claim as its (d), and cancellation as Proposition 1.6.3 (b), (f); with that, each of these proofs runs on $\omega$ . A later chapter may cite them only in a review (R) exercise; anywhere else, a construction that needs one of them proves it on $\omega$ first. Part (b) of Sets, Relations, and Cardinality, Corollary 3.2.7 is not in this group and is not checked on $\omega$ here: Sets, Relations, and Cardinality, Chapter 3 treats its list $A_1, \dots, A_k$ as a family in the everyday sense of Sets, Relations, and Cardinality, Definition 1.2.3, with no set holding it, and Section 1.2 left such families to the axiom of Replacement. A list given as a function on $\{1, \dots, k\}$ , with graph $G$ , does have an ambient set: each $A_i$ lies in $\bigcup \bigcup G$ by (Z4), so the union of the $A_i$ exists by (Z4) and (Z6), and the proof of (b) can then be run on $\omega$ , with its base case (a) read as above and its Sets, Relations, and Cardinality, Theorem 2.2.1 from base $2$ read by Proposition 1.6.3 (g). A later chapter that needs (b) proves it on $\omega$ first, in that form. Sets, Relations, and Cardinality, Theorem 3.2.8 is a statement about the school $\mathbb{Z}$ and $\mathbb{Q}$ , and is never applied to $\omega$ .
(iii) Templates. Sets, Relations, and Cardinality, Definition 2.3.1 and Sets, Relations, and Cardinality, Proposition 2.3.4 are used later only as patterns, with the school $\mathbb{R}$ replaced by an ordered field $F$ . Their $\mathbb{N}$ side is read through the dictionary, and their field side is proved again from the axioms of $F$ . The parts that need $\mathbb{Z}$ (Sets, Relations, and Cardinality, Proposition 2.3.4 (d) for an integer base, and the general index of Sets, Relations, and Cardinality, Definition 2.3.1, which uses Sets, Relations, and Cardinality, Proposition 2.1.2) are not part of the pattern.

Finally, the axiom of choice. Apart from Sets, Relations, and Cardinality, Chapter 2’s $\mathbb{N} \subseteq \mathbb{R}$ and its school operations, which Corollary 1.7.3 (a) takes as given, every set in Sections 1.1–1.7 is produced by one of (Z1)–(Z7). Every function is produced by Theorem 1.5.1, by (Z6) applied to a graph described by a property (as $g$ was in the proof of Theorem 1.7.1 (a)), or by Sets, Relations, and Cardinality, Chapter 1’s inverses and composites of such functions. Nothing is chosen from infinitely many sets, and Sets, Relations, and Cardinality, Axiom 3.3.1 is used nowhere in this chapter; it is mentioned only to say where it lives.

So everything that Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2 assumed about $\mathbb{N}$ (that $0$ is a natural number, that $n + 1$ is one whenever $n$ is, induction, recursion, and the arithmetic of Sets, Relations, and Cardinality, Lemma 2.1.1) is now proved, from seven axioms about sets. The set-theory volume returns to those axioms and adds the rest of the system. Chapter 2 builds $\mathbb{Z}$ and $\mathbb{Q}$ from $\omega$ by the same kind of construction as here: pairs, and classes of pairs.

1.7.6. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 1.7.1.

(a) Where in the proof is (P5) for $M$ used, and where are (P3) and (P4) for $M$ used?
(b) Where is (P4) for $\omega$ used? (It is not visible in the proof itself.)
(c) Run $\varphi$ of part (a) for the system $(\omega \setminus \{0\}, 1, \mathrm{S})$ on $0$ , $1$ and $2$ , from the two equations alone.
(d) State the idea of the proof of (a) and (b) in two sentences.

Solution.

(a) (P5) for $M$ is used once, for surjectivity: the image $\varphi(\omega)$ contains $e$ and is closed under $s$ , so it is $M$ . (P3) for $M$ is used for injectivity, in the base case ( $\varphi(\mathrm{S}(k)) = s(\varphi(k)) \ne e$ , so only $m = 0$ has $\varphi(m) = e$ ) and at the start of the inductive step (to exclude $m = 0$ ). (P4) for $M$ is used in the inductive step, to pass from $s(\varphi(k)) = s(\varphi(n))$ to $\varphi(k) = \varphi(n)$ .
(b) Inside part (a), through Theorem 1.5.1: its proof extends a partial solution by one new pair at $\mathrm{S}(n)$ , and (P4) for $\omega$ makes $\mathrm{S}(n)$ the successor of $n$ only, so the equation at $\mathrm{S}(n)$ asks for $g(n, h(n))$ and nothing else.
(c) $\varphi(0) = 1$ ; $\varphi(1) = \varphi(\mathrm{S}(0)) = \mathrm{S}(\varphi(0)) = \mathrm{S}(1) = 2$ ; $\varphi(2) = \varphi(\mathrm{S}(1)) = \mathrm{S}(2) = 3$ .
(d) The map is forced at $0$ and at each successor, so the recursion theorem builds it and makes it unique. It is onto because its image contains $e$ and is closed under $s$ , so (P5) for $M$ applies; it is one-to-one by an induction whose base and step are (P3) and (P4) for $M$ .

B. Practice

Exercise (B1: The even numbers)

Let $E \mathrel{:=} \{ 2n : n \in \omega \}$ , with $e \mathrel{:=} 0$ and $s(x) \mathrel{:=} x + 2$ for $x \in E$ . Show that $(E, 0, s)$ is a Peano system, and that the map $\varphi$ of Theorem 1.7.1 is $\varphi(n) = 2n$ .

Solution. $E$ is a set by (Z6) inside $\omega$ : it is $\{ x \in \omega : x = 2n \text{ for some } n \in \omega \}$ . By Definition 1.5.1 (b), $2 \cdot \mathrm{S}(n) = 2n + 2$ for every $n \in \omega$ . So $s$ maps $E$ into $E$ : $s(2n) = 2n + 2 = 2 \cdot \mathrm{S}(n) \in E$ .

(P3): $2n + 2 = 2n + \mathrm{S}(1) = \mathrm{S}(2n + 1)$ by Definition 1.5.1 (a), and a successor is never $0$ (Theorem 1.4.2 (P3)). (P4): if $x + 2 = y + 2$ , then $x = y$ by Proposition 1.6.3 (b). (P5): let $A \subseteq E$ with $0 \in A$ and $x + 2 \in A$ for every $x \in A$ . Let $B \mathrel{:=} \{ n \in \omega : 2n \in A \}$ . Then $0 \in B$ , since $2 \cdot 0 = 0 \in A$ ; and if $n \in B$ , then $2 \cdot \mathrm{S}(n) = 2n + 2 \in A$ , so $\mathrm{S}(n) \in B$ . By Theorem 1.3.3 (a), $B = \omega$ , so every $2n$ lies in $A$ , and $A = E$ .

The map $n \mapsto 2n$ from $\omega$ to $E$ sends $0$ to $2 \cdot 0 = 0 = e$ , and $2 \cdot \mathrm{S}(n) = 2n + 2 = s(2n)$ . By the uniqueness in Theorem 1.7.1 (a), it is $\varphi$ . In particular, by (b) of that theorem, $n \mapsto 2n$ is a bijection $\omega \to E$ .

Exercise (B2: The identification at work)

Let $\varphi \colon \omega \to \mathbb{N}$ be the bijection of Corollary 1.7.3 (a).

(a) Compute $\varphi(3)$ step by step from the two equations of $\varphi$ .
(b) Compute $\varphi(2 \cdot 3)$ in two ways: from (a) of the corollary, and by unwinding $2 \cdot 3$ in $\omega$ to a numeral first.

Solution.

(a) Using $\varphi(0) = 0$ and $\varphi(\mathrm{S}(n)) = \varphi(n) + 1$ , with $3 = \mathrm{S}(2)$ , $2 = \mathrm{S}(1)$ , $1 = \mathrm{S}(0)$ (Definition 1.5.1 (c)): $\varphi(3) = \varphi(2) + 1 = \bigl(\varphi(1) + 1\bigr) + 1 = \bigl((0 + 1) + 1\bigr) + 1 = 3 .$
(b) By the corollary, $\varphi(2 \cdot 3) = \varphi(2)\varphi(3) = 2 \cdot 3 = 6$ in $\mathbb{N}$ , where $\varphi(2) = 2$ as in (a). In $\omega$ , $2 \cdot 3 = 2 \cdot 2 + 2 = (2 \cdot 1 + 2) + 2 = ((2 \cdot 0 + 2) + 2) + 2 = 6$ , by Definition 1.5.1 (b) three times and then $2 \cdot 0 = 0$ , $0 + 2 = 2$ , $2 + 2 = 4$ , $4 + 2 = 6$ from the equations for $+$ . Then $\varphi(6) = 6$ by six steps as in (a). The two answers agree, as the corollary says they must.

C. Going deeper

Exercise (C1: Writing out categoricity)

Without looking at the text, prove part (b) of Theorem 1.7.1: for a Peano system $(M, e, s)$ , the map $\varphi \colon \omega \to M$ with $\varphi(0) = e$ and $\varphi(\mathrm{S}(n)) = s(\varphi(n))$ is a bijection.

Solution (Hint 1). For surjectivity, use (P5) for $M$ on a set built from $\varphi$ . For injectivity, induct on $n$ ; decide first where “for every $m$ ” goes.

Solution (Hint 2). The induction for injectivity starts: “Let $Q(n)$ be: for every $m \in \omega$ , $\varphi(m) = \varphi(n)$ implies $m = n$ .”

Solution. Onto. The image $B \mathrel{:=} \varphi(\omega)$ (Sets, Relations, and Cardinality, Definition 1.6.1) contains $e = \varphi(0)$ , and $x = \varphi(n) \in B$ gives $s(x) = \varphi(\mathrm{S}(n)) \in B$ . By (P5) for $M$ , $B = M$ .

One-to-one. By Theorem 1.3.3 (b) we prove, for every $n$ , $Q(n)$ : “for every $m \in \omega$ , $\varphi(m) = \varphi(n)$ implies $m = n$ ”. For $Q(0)$ , let $\varphi(m) = e$ ; an $m \ne 0$ is $\mathrm{S}(k)$ (Lemma 1.4.1 (d)), with $\varphi(m) = s(\varphi(k)) \ne e$ by (P3) for $M$ ; so $m = 0$ . For the step, assume $Q(n)$ and $\varphi(m) = s(\varphi(n))$ . Then $m \ne 0$ , as $e$ is not a value of $s$ (P3 for $M$ ); so $m = \mathrm{S}(k)$ , and $s(\varphi(k)) = s(\varphi(n))$ gives $\varphi(k) = \varphi(n)$ by (P4) for $M$ , hence $k = n$ by $Q(n)$ used at $k$ , and $m = \mathrm{S}(n)$ . So $\varphi$ is injective, and a bijection.

Marking scheme. (10 points) - 3: surjectivity: shows the image of $\varphi$ contains $e$ and is closed under $s$ , and cites (P5) for $M$ . - 2: sets up an induction (on either variable, or by least counterexample) whose hypothesis is strong enough to use at the predecessor, e.g. $Q(n)$ with “for every $m$ ” inside, or the difference $j \ne 0$ fixed and induction on $m$ . - 2: base case, via $m = \mathrm{S}(k)$ for $m \ne 0$ and (P3) for $M$ . - 3: inductive step, using (P3) for $M$ to get $m \ne 0$ , (P4) for $M$ to cancel $s$ , and the induction hypothesis at the predecessor $k$ . Fatal errors (0 for the part concerned): an induction whose hypothesis is then applied at a value it does not cover (typically: $m$ fixed outside $Q$ , then used at $k$ ); using injectivity of $\varphi$ to prove injectivity; using (P3), (P4) or (P5) for $\omega$ where the axiom for $M$ is needed. A proof of injectivity by Theorem 1.6.2 (a least $n$ with some $m \ne n$ , $\varphi(m) = \varphi(n)$ ) earns the same 7 points, mapped to base, step and hypothesis in the same way. So does the fixed-difference route (reducing to $\varphi(m + j) \ne \varphi(m)$ for $j \ne 0$ by Theorem 1.6.1 (a) and Proposition 1.6.3 (a), and inducting on $m$ ): its base uses (P3) for $M$ , its step (P4) for $M$ and the hypothesis at $m$ , and the points are mapped in the same way.

Exercise (C2: Without induction, no recursion)

Let $(M, e, s)$ be structure (iii) of Example (Each axiom is needed), the natural numbers beside a two-sided chain: $M = \omega \times 3$ , $e = (0, 0)$ , $s(n, 0) = (\mathrm{S}(n), 0)$ , $s(n, 1) = (\mathrm{S}(n), 1)$ , $s(0, 2) = (0, 1)$ and $s(\mathrm{S}(k), 2) = (k, 2)$ . Show that there is no function $f \colon M \to \omega$ with $f(e) = 0$ and $f(s(x)) = \mathrm{S}(f(x))$ for every $x \in M$ . Which Peano axiom, missing in $M$ , is responsible?

Solution. Suppose such an $f$ exists. For every $k \in \omega$ , $s(\mathrm{S}(k), 2) = (k, 2)$ , so $f\bigl((k, 2)\bigr) = \mathrm{S}\Bigl(f\bigl((\mathrm{S}(k), 2)\bigr)\Bigr) .$ Let $T \mathrel{:=} \{ f((k, 2)) : k \in \omega \} \subseteq \omega$ , a set by (Z6) inside $\omega$ ; it is non-empty, since it contains $f((0, 2))$ . By Theorem 1.6.2, $T$ has a least element $t = f((k_0, 2))$ . But $u \mathrel{:=} f((\mathrm{S}(k_0), 2)) \in T$ , and $t = \mathrm{S}(u)$ , so $u \in \mathrm{S}(u) = t$ , that is, $u < t$ (Definition 1.6.1). This contradicts the leastness of $t$ , since $t \le u$ and $u < t$ would give $u < u$ (Theorem 1.6.1 (a)). So no such $f$ exists. (The condition $f(e) = 0$ was not even used: no map at all turns $s$ into $\mathrm{S}$ .)

$M$ satisfies (P3) and (P4) and fails only (P5) (Example (Each axiom is needed)). So (P5) is what makes the recursion theorem possible: the downward chain $(0, 2), (1, 2), (2, 2), \dots$ , each element the successor of the next, would need values in $\omega$ that decrease forever.

R. Review

Exercise (R1)

Prove that $\omega$ is infinite.

Solution. We read Sets, Relations, and Cardinality, Definition 3.1.3 and Sets, Relations, and Cardinality, Theorem 3.1.9 on $\omega$ , through the dictionary of this section (group (i)). Consider $\mathrm{S}$ with codomain $\omega \setminus \{0\}$ ; its values lie there by Theorem 1.4.2 (P3). It is injective by (P4) of that theorem, and onto $\omega \setminus \{0\}$ by Lemma 1.4.1 (d): every $n \ne 0$ is $\mathrm{S}(k)$ for some $k \in \omega$ . So it is a bijection $\omega \to \omega \setminus \{0\}$ . The set $\omega \setminus \{0\}$ is a proper subset of $\omega$ , since $0 \in \omega$ and $0 \notin \omega \setminus \{0\}$ . By Sets, Relations, and Cardinality, Theorem 3.1.9, a finite set is not equinumerous with any proper subset; so $\omega$ is not finite, that is, it is infinite (Sets, Relations, and Cardinality, Definition 3.1.3). This is the Quick check after Sets, Relations, and Cardinality, Example (Hilbert’s Hotel) (every guest moves up one room), built from (P3) and (P4).

Exercise (R2)

Show that the successor function $\mathrm{S} \colon \omega \to \omega$ 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, Relations, and Cardinality, Proposition 1.5.2), and $\mathrm{S}$ is not: $0$ is not a value, by Theorem 1.4.2 (P3).

A left inverse. Let $L \colon \omega \to \omega$ have the graph $G \mathrel{:=} \bigl\{ (n, k) \in \omega \times \omega : (n = 0 \text{ and } k = 0) \text{ or } n = \mathrm{S}(k) \bigr\},$ a set by (Z6). Each $n \in \omega$ has exactly one partner. If $n = 0$ , the partner $k = 0$ works, and no $k$ has $0 = \mathrm{S}(k)$ , by (P3). If $n \ne 0$ , then $n = \mathrm{S}(k)$ for some $k$ (Lemma 1.4.1 (d)), and only one, by (P4). So $L$ is a function (Sets, Relations, and Cardinality, Definition 1.4.1) with $L(0) = 0$ and $L(\mathrm{S}(k)) = k$ . Hence $L(\mathrm{S}(n)) = n$ for every $n \in \omega$ , that is, $L \circ \mathrm{S} = \operatorname{id}_\omega$ : $L$ is a left inverse of $\mathrm{S}$ (Sets, Relations, and Cardinality, Definition 1.5.1 (a)). This matches Sets, Relations, and Cardinality, Theorem 1.5.1: $\mathrm{S}$ is injective and $\omega \ne \emptyset$ .

Not unique. The value of a left inverse at $0$ is never used, since $0$ is not of the form $\mathrm{S}(n)$ ; setting $L'(0) \mathrel{:=} 5$ and $L'(\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 \omega$ 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 $\omega$ , 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 \omega$ has $n = \mathrm{S}(n)$ : $n \in \mathrm{S}(n)$ (Definition 1.3.1), so $n = \mathrm{S}(n)$ would give $n \in n$ , against Lemma 1.4.1 (c). 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 $\omega$ 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).

Exercise (R4)

For $n \in \omega$ , compute $\bigcup \mathrm{S}(n)$ and $\bigcup n$ . Then find a set $x$ with $\bigcup \mathrm{S}(x) \ne x$ .

Solution. A formula for every set. For any set $x$ , $\bigcup \mathrm{S}(x) = \bigcup (x \cup \{x\}) = \bigcup x \cup x$ : an element of a member of $x \cup \{x\}$ is an element of a member of $x$ , or an element of $x$ itself.

For $n \in \omega$ . The tool is transitivity. By Lemma 1.4.1 (a), $n$ is transitive, so every element of a member of $n$ is a member of $n$ , that is, $\bigcup n \subseteq n$ . Hence $\bigcup \mathrm{S}(n) = \bigcup n \cup n = n$ . For $\bigcup n$ itself: $\bigcup 0 = \bigcup \emptyset = \emptyset = 0$ ; and if $n \ne 0$ , then $n = \mathrm{S}(k)$ (Lemma 1.4.1 (d)), and $\bigcup n = \bigcup \mathrm{S}(k) = k$ by what we just proved. So $\bigcup$ undoes the successor: it is the “predecessor” on $\omega$ , with $0$ sent to $0$ .

A set where it fails. Let $x \mathrel{:=} \{1\} = \{\{\emptyset\}\}$ . Then $\bigcup x = 1 = \{\emptyset\}$ , and $\bigcup \mathrm{S}(x) = \{\emptyset\} \cup \{\{\emptyset\}\} = \{0, 1\} = 2$ . This is not $x$ : $0 = \emptyset \in 2$ , but $\emptyset \notin x$ , since the only element of $x$ is $\{\emptyset\} \ne \emptyset$ .

Why the identity alone is not enough. The look-alike tool is the identity $\bigcup \mathrm{S}(x) = \bigcup x \cup x$ , which holds for every set. On its own it does not give $x$ : it gives $\bigcup \mathrm{S}(x) = x$ exactly when $\bigcup x \subseteq x$ , that is, when $x$ is transitive (Definition 1.4.1), and $\{1\}$ , which is not transitive, is a witness that this can fail. Nor is an induction on $n$ a route that avoids transitivity: its step $\bigcup \mathrm{S}(\mathrm{S}(n)) = \bigcup \mathrm{S}(n) \cup \mathrm{S}(n) = n \cup \mathrm{S}(n) = \mathrm{S}(n)$ proves $\bigcup \mathrm{S}(n) = n$ , which is equivalent to transitivity of $n$ , so it proves Lemma 1.4.1 (a) again along the way.