We see, following the **text** how to axiomatize the natural numbers and define addition and multiplication from these. We elaborate on only one result, namely one allowing us to make recursive definitions.

**Theorem:** Let $X$ be a set, let $x_0\in X$ and let $g(n, x)$ be a function $g: \mathbb{N} \times X \to X$. There is a unique function $f: \mathbb{N}\to X$ such that $f(0)= x_0$ and $\forall n \in\mathbb{N}\ f(n++) = g(n, f(n))$.

**Proof:** The idea is to construct the graph of $f$ as the smallest set containing a specified starting point and closed under a shift.

Let $\mathcal{U} = \{S \subset \mathbb{N}\times X : (0, x_0)\in S,\ (n, x)\in S\Rightarrow (n++, g(n++, x))\in S\}$. Note that $\mathcal{U}$ is non-empty as $\mathbb{N}\times X \in \mathcal{U}$.

Consider the set

It is easy to see that $S_0\in \mathcal{U}$.

**Lemma:** For every $n\in \mathbb{N}$, there exist a unique $x_n\in X$ such that $(n, x_n) \in S_0$.

**Proof:** We prove this by induction on $n$. First, let $n=0$. Note that $(0, x_0)\in S$ for all $S\in \mathcal{U}$, and so $(0, x_0) \in S_0$. Now suppose $(0, x_0’)\in S_0$ with $x_0’\neq x_0$. Let $S = \{(n, x) \in S_0: (n, x) \neq (0, x_0’)$. We claim that $S\in \mathcal{U}$.

Firstly, as $(0, x_0) \in S_0$ and $x_0’ \neq x_0$, $(0, x_0)\in S$. Next, suppose $(n, x)\in S \subset S_0$, then $(n++, g(n++, x))\in S_0$. Further, as $n++ \neq 0$, we see that $(n++, g(n++, x)) \neq (0, x_0’)$. Hence $(n++, g(n++, x))\in S$. Thus $S\in \mathcal{U}$.

By definition of $S_0$, as $S\in \mathcal{U}$, $S_0 \subset S$. But $(0, x_0’)$ is in $S_0$ but not $S$, a contradiction. This shows that $x_0\in X$ is the unique point $x \in X$ such that $(0, x)\in S_0$.

The induction step is similar. Assume $(n, x_n)\in S_0$ and this is unique, i.e., $(n, x)\in S_0 \implies x = x_n$. Then $(n, x_n)\in S$ for all $S \in \mathcal{U}$, from which we deduce that $(n++, g(n++, x))\in S_0$. To show uniqueness, suppose $x_{n++}’\in X$ is a point with $(n++, x_{n++}’)\in S_0$ but $x_{n++}’ \neq x_{n++} := g(n++, x)$. Let $S = S_0 \setminus \{(n++, x_{n++}’)\}$. We again show that $S \in \mathcal{U}$ and obtain a contradiction to $S_0 \subset S$.

Namely, as $(0, x_0) \in S_0$ and $n++ \neq 0$, $(0, x_0)\in S$. Next, suppose $(m, x)\in S \subset S_0$, then $(m++, g(m++, x))\in S_0$. If $(m++, g(m++, x)) \notin S$, then we must have $(m++, g(m++, x)) = (n++, x_{n++}’)$. Hence $n = m$, so $x = x_n$. It follows that $x_{n++}’ = g(m++, x) = g(n++, x_n)$, a contradiction. Thus, if $(m, x)\in S$, $(m++, g(m++, x)) \in S$, completing the proof that $S\subset \mathcal{U}$, and contradicting $S_0 \subset S$.

This completes the proof of the lemma.

To prove the theorem, we define the function $f$ by $f(n) = x_n$. As we will see, in terms of set theory the function just corresponds to the set $S_0$. It is straightforward to show by induction than $f$ indeed has the desired properties, and is the unique such function.