Intuitively, we construct the natural numbers when we write down expressions $0$, $0+1$, $0+1+1$, and so on, and then consider the set of objects that can be written down with this recipe. This seems to contain a circularity, for the definition of our set of natural numbers would seem to be be the collection of all $0+1+\dots +1$ with a natural number of $1$s; fortunately there is a way round this problem.

Definition.

Choose $U$ to be some fixed infinite universe of objects, and
$f:U\to U$ be an injection which is not a surjection,
so $f\left(x\right)=f\left(y\right)$ implies $x=y$ for all $x,y\in U$
but some $u\in U$ is not equal to $f\left(x\right)$ for any $x$.
Fix some such $u\in U$ and call this $u$
zero

or $0$.
Now let $x+1$ be $f\left(x\right)$, and define the set of natural
numbers $\mathbb{N}=\left\{0,f\left(0\right),f\left(f\right(0\left)\right),f\left(f\right(f\left(0\right)\left)\right),\dots \right\}$
by

where the big $$ means to take the intersection of all sets inside the set of sets. For $x\in \mathbb{N}$ we define $x+1$ to be $f\left(x\right)$.

For particularly suspicious readers, we should give an example of a suitable $U$ and $f$. We can take $U$ to be the collection of all sets, and $f\left(A\right)=A\cup \left\{A\right\}$. Then $A\in f\left(A\right)$ for all $A$ so $\varnothing $ is not in the range of $f$, hence we may take $0$ to be $\varnothing $. (It is somewhat harder to prove that this $f$ is an injection.) Using this $f$ we have $1=f\left(0\right)=\varnothing \cup \left\{\varnothing \right\}=\left\{\varnothing \right\}=\left\{0\right\}$, $2=f\left(1\right)=\left\{\varnothing \right\}\cup \left\{\left\{\varnothing \right\}\right\}=\left\{\varnothing ,\left\{\varnothing \right\}\right\}=\left\{0,1\right\}$, $3=f\left(2\right)=\left\{\varnothing ,\left\{\varnothing \right\},\left\{\left\{\varnothing \right\}\right\}\right\}=\left\{0,1,2\right\}$ and so on.

Principle of Induction.

Suppose $P$ is a property such that $P\left(0\right)$, i.e., $0$ has property $P$, and $\forall x\in \mathbb{N}\left(P\right(x)\Rightarrow P(x\mathrm{+1}\left)\right)$. Then $\forall x\in \mathbb{N}P\left(x\right)$.

**Proof.**

Let $X$ be the set of elements of $U$ that have property $P$, i.e., $X=\{u\in U:P\left(u\right)\}$. Then $X$ is an example of a set with $0\in X\wedge \forall x\in Xf\left(x\right)\in X$ and so $X\supseteq \mathbb{N}$ since the definition of $\mathbb{N}$ is that it is the intersection of all such sets $X$ with this property. So every natural number $x$ is in $X$ and hence each $n\in \mathbb{N}$ has $P\left(n\right)$.

Principle of Inductive Definitions.

A definition of the following kind, $F\left(0\right)={F}_{0}\in \mathbb{N}$ and $F(x+1)=G(x,F(x\left)\right)\in \mathbb{N}$, defines a function $F$ on $\mathbb{N}$.

**Proof.**

Let $X$ be the set of natural numbers for which $F$ is well-defined. Then $0\in X$ as $F\left(0\right)={F}_{0}$ is well-defined and if $x\in X$ then is well-defined so is $G(x,F(x\left)\right)$ and hence so is $F(x+1)=G(x,F(x\left)\right)$ well-defined, so $x+1=f\left(x\right)\in X$. Therefore $X$ is an example of a set with $0\in X\wedge \forall x\in Xf\left(x\right)\in X$ and so $X=\mathbb{N}$ as (by definition of $\mathbb{N}$) every natural number $x$ is in any such set $X$. So $F$ is well-defined.

Definition.

For a natural number $a\in \mathbb{N}$ we define ${F}_{a}\left(x\right)=a+x$ inductively by $a+0={F}_{a}\left(0\right)=a$ and $a+(x+1)={F}_{a}(x+1)={F}_{a}\left(x\right)+1=(a+x)+1$. We write $a\u2a7db$ if there is a natural number $x\in \mathbb{N}$ such that $a+x=b$.

There follows a long sequence of propositions proving (by induction) that $+$ and $\u2a7d$ have the expected properties. Skip the proofs on first reading if you wish.

Proposition.

The following holds for all $x,y,z\in \mathbb{N}$: $(x+y)+z=x+(y+z)$.

**Proof.**

Induction on $z$. Base case: $(x+y)+0=x+y=x+(y+0)$. Induction step: $(x+y)+(z+1)=\left(\right(x+y)+z)+1=(x+(y+z\left)\right)+1$ by the induction hypothesis, so $(x+y)+(z+1)=x+\left(\right(y+z)+1)=x+(y+(z+1\left)\right)$.

Proposition.

The following holds for all $x\in \mathbb{N}$: $x=0+x$.

**Proof.**

Induction on $x$. Base case: $0+0=0$. Induction step: $x+1=(0+x)+1=0+(x+1)$.

Proposition.

The following holds for all $x,y\in \mathbb{N}$: $x+y=y+x$.

**Proof.**

Induction on $y$. Base case: $x+0=x=0+x$ using the previous proposition. Induction step: $x+(y+1)=(x+y)+1=(y+x)+1$ by the induction hypothesis, so $x+(y+1)=y+(x+1)$ as required.

Proposition.

The following holds for all $x\in \mathbb{N}$: $x\ne 0\Rightarrow \exists w\in \mathbb{N}x=w+1$.

**Proof.**

Induction on $x$: Base case: $0\ne 0\Rightarrow \exists w\in \mathbb{N}0=w+1$ is trivially true as $0\ne 0$ is false and any implication $0\ne 0\Rightarrow A$ is therefore true. Now assume $x\ne 0\Rightarrow \exists w\in \mathbb{N}x=w+1$ and consider $x+1$. Then either $x=0$ in which case $x+1=0+1$ and we are finished with $w=0$, or $x\ne 0$ so $x=v+1$ for some $v$ hence $x+1=(v+1)+1$ and we are done with $w=v+1$.

Proposition.

The following holds for all $x,y,z\in \mathbb{N}$: $x+z=y+z\Rightarrow x=y$.

**Proof.**

Induction on $z$. For $z=0$ note that if $x+0=y+0$ then $x=y$ as $x+0=x$ and $y+0=y$ by definition. Now assume $x+(z+1)=y+(z+1)$, so $(x+z)+1=(y+z)+1$ by definition of $+$. But the $+1$ operation on $\mathbb{N}$ is one-to-one so this implies $x+z=y+z$ which implies $x=y$ by the induction hypothesis.

Proposition.

The following holds for all $x,y\in \mathbb{N}$: $x+y=0\Rightarrow y=0$.

**Proof.**

If $y\ne 0$ then $y=w+1$ for some $w\in \mathbb{N}$ so $0=x+(w+1)=(x+w)+1$ which is impossible as $0$ is not in the image of the function $f$ on $U$, so $0$ cannot equal $v+1$ for any $v\in \mathbb{N}$.

Proposition.

The following holds for all $x,y\in \mathbb{N}$: $x+y=x\Rightarrow y=0$.

**Proof.**

Induction on $x$. The base case is that $0+y=0$ implies $y=0$, which is true as $0+y=y+0=y$ by previous propositions. If $(x+1)+y=x+1$ then $(x+y)+1=x+1$ and as the function taking $x+y$ to $(x+y)+1$ is one-to-one it follows that $x+y=x$ and hence by the induction hypothesis $y=0$.

Proposition.

The following holds for all $x,y,z\in \mathbb{N}$: $(x\u2a7dy\wedge y\u2a7dz)\Rightarrow x\u2a7dz$.

**Proof.**

If $x\u2a7dy\wedge y\u2a7dz$ then there are $u,v$ with $y=x+u$ and $z=y+v$. So $z=(x+u)+v=x+(u+v)$ by associativity, so $x\u2a7dz$.

Proposition.

The following holds for all $x,y,z\in \mathbb{N}$: $(x\u2a7dy\wedge y\u2a7dx)\Rightarrow x=y$.

**Proof.**

If $x\u2a7dy\wedge y\u2a7dx$ then $x+u=y$ and $y+v=x$ for some $u,v\in \mathbb{N}$. Thus $y=(y+v)+u=y+(v+u)$ and so $v+u=0$, $u=v=0$ and hence $x=y$ by previous parts.

Proposition.

The following holds for all $x,y\in \mathbb{N}$: $x\u2a7dy\vee y\u2a7dx$.

**Proof.**

Induction on $x$. For $x=0$ note that $0\u2a7dy$ as $0+y=y$ by a previous proposition. Now assume $x\u2a7dy$. Then $y=x+u$ for some $u\in \mathbb{N}$. If $u=0$ then $x=y$ and $y\u2a7dx+1$ as $y=x+1$. On the other hand, if $u\ne 0$ and $y=x+u$ then $u=w+1$ for some $w$, by a previous proposition, so $y=x+u=x+(w+1)=(x+1)+w$ by commutativity and associativity, hence $x\u2a7dy$. Finally, assume $y\u2a7dx$, so $y+u=x$ for some $u$. Then $y+(u+1)=(y+u)+1=x+1$ so $y\u2a7d(x+1)$.

Theorem.

If $x,y\in \mathbb{N}$ and $x\u2a7dy$ then there is a unique $z\in \mathbb{N}$ such that $x+z=y$.

**Proof.**

Existence is by induction on $x$. If $x=0$ then $0+y=y$ so we may take $z=y$. For the induction step, given $x+z=y$ and $x+1\u2a7dy$ then $z\ne 0$ (for else $x=y$ and so $x+1=x+0$ hence $1=0$ which is impossible as it would mean $0$ is in the range of the $+1$ function). Then $z=u+1$ for some $u$ and $x+(u+1)=y$, so $u$ satisfies $(x+1)+u=y$, as required.

For uniqueness suppose, $x+z=x+w=y$. Then $z+x=w+x$ so $z=w$ by a previous proposition.

Definition.

If $x\u2a7dy$ we write $y-x$ for the unique $z$ such that $x+z=y$.

We also make the usual definitions concerning $\u2a7d$:
we say $x\u2a7ey$ if $x\u2a7dy$ and $x<y$ or $y>x$
if $x\u2a7dy$ and $x\ne y$ and can also justify the
*least number principle*.

Least number principle.

Suppose there is some $n\in \mathbb{N}$ with a property $P$. Then there is a least ${n}_{0}$ in $\mathbb{N}$ with $P$.

**Proof.**

Let $X=\{x\in \mathbb{N}:\forall y<x\neg P\left(y\right)\}$, the set of $x$ such that every smaller $y$ fails to have $P$. We use $X$ to show that there is a least number satisfying $P$.

**Subproof.**

Suppose there is some $n\in \mathbb{N}$ satisfying $P\left(n\right)$.

**Subproof.**

Suppose there is no least $x\in \mathbb{N}$ satisfying $P\left(x\right)$.

Then $0\in X$ since $\forall y\in \mathbb{N}y0\Rightarrow \neg P\left(y\right)$ since $y<0\Rightarrow \neg P\left(y\right)$ holds because $y<0$ is false.

Also if $x\in !math\; X$ then if $P\left(x\right)$ hold it would mean that $x$ is the least element satisfying $P\left(x\right)$, since all $y<x$ have $\neg P\left(y\right)$ because $x\in X$. This is impossible by our assumption, so therefore $\neg P\left(x\right)$, and hence $x+1$ is in $X$.

It follows by induction that $\forall y\in \mathbb{N}y\in X$, and this clearly implies that $\forall y\in \mathbb{N}\neg P\left(y\right)$, contradicting our assumption that there is some $n$ with $P\left(n\right)$.

This proves by contradiction, that there is a least $x\in \mathbb{N}$ with $P\left(x\right)$.