# Construction of the natural numbers

## 1. The idea

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 + … + 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 → U$ be an injection which is not a surjection, so $f ( x ) = f ( y )$ implies $x = y$ for all $x , y ∈ U$ but some $u ∈ U$ is not equal to $f ( x )$ for any $x$. Fix some such $u ∈ U$ and call this $u$ zero or $0$. Now let $x + 1$ be $f ( x )$, and define the set of natural numbers $ℕ = { 0 , f ( 0 ) , f ( f ( 0 ) ) , f ( f ( f ( 0 ) ) ) , … }$ by

where the big  means to take the intersection of all sets inside the set of sets. For $x ∈ ℕ$ we define $x + 1$ to be $f ( x )$.

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 ( A ) = A ∪ { A }$. Then $A ∈ f ( A )$ for all $A$ so $∅$ is not in the range of $f$, hence we may take $0$ to be $∅$. (It is somewhat harder to prove that this $f$ is an injection.) Using this $f$ we have $1 = f ( 0 ) = ∅ ∪ { ∅ } = { ∅ } = { 0 }$, $2 = f ( 1 ) = { ∅ } ∪ { { ∅ } } = { ∅ , { ∅ } } = { 0 , 1 }$, $3 = f ( 2 ) = { ∅ , { ∅ } , { { ∅ } } } = { 0 , 1 , 2 }$ and so on.

## 2. Induction and inductive definitions

Principle of Induction.

Suppose $P$ is a property such that $P ( 0 )$, i.e., $0$ has property $P$, and . Then .

Proof.

Let $X$ be the set of elements of $U$ that have property $P$, i.e., $X = { u ∈ U : P ( u ) }$. Then $X$ is an example of a set with and so $X ⊇ ℕ$ since the definition of $ℕ$ 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 ∈ ℕ$ has $P ( n )$.

Principle of Inductive Definitions.

A definition of the following kind, $F ( 0 ) = F 0 ∈ ℕ$ and $F ( x + 1 ) = G ( x , F ( x ) ) ∈ ℕ$, defines a function $F$ on $ℕ$.

Proof.

Let $X$ be the set of natural numbers for which $F$ is well-defined. Then $0 ∈ X$ as $F ( 0 ) = F 0$ is well-defined and if $x ∈ X$ then is well-defined so is $G ( x , F ( x ) )$ and hence so is $F ( x + 1 ) = G ( x , F ( x ) )$ well-defined, so $x + 1 = f ( x ) ∈ X$. Therefore $X$ is an example of a set with and so $X = ℕ$ as (by definition of $ℕ$) every natural number $x$ is in any such set $X$. So $F$ is well-defined.

Definition.

For a natural number $a ∈ ℕ$ we define $F a ( x ) = a + x$ inductively by $a + 0 = F a ( 0 ) = a$ and $a + ( x + 1 ) = F a ( x + 1 ) = F a ( x ) + 1 = ( a + x ) + 1$. We write $a ⩽ b$ if there is a natural number $x ∈ ℕ$ such that $a + x = b$.

## 3. Technical propositions

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

Proposition.

The following holds for all $x , y , z ∈ ℕ$: $( 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 ) = ( ( x + y ) + z ) + 1 = ( x + ( y + z ) ) + 1$ by the induction hypothesis, so $( x + y ) + ( z + 1 ) = x + ( ( y + z ) + 1 ) = x + ( y + ( z + 1 ) )$.

Proposition.

The following holds for all $x ∈ ℕ$: $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 ∈ ℕ$: $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 ∈ ℕ$: .

Proof.

Induction on $x$: Base case: is trivially true as $0 ≠ 0$ is false and any implication $0 ≠ 0 ⇒ A$ is therefore true. Now assume and consider $x + 1$. Then either $x = 0$ in which case $x + 1 = 0 + 1$ and we are finished with $w = 0$, or $x ≠ 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 ∈ ℕ$: $x + z = y + z ⇒ 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 $ℕ$ 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 ∈ ℕ$: $x + y = 0 ⇒ y = 0$.

Proof.

If $y ≠ 0$ then $y = w + 1$ for some $w ∈ ℕ$ 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 ∈ ℕ$.

Proposition.

The following holds for all $x , y ∈ ℕ$: $x + y = x ⇒ 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 ∈ ℕ$: $( x ⩽ y ∧ y ⩽ z ) ⇒ x ⩽ z$.

Proof.

If $x ⩽ y ∧ y ⩽ z$ 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 ⩽ z$.

Proposition.

The following holds for all $x , y , z ∈ ℕ$: $( x ⩽ y ∧ y ⩽ x ) ⇒ x = y$.

Proof.

If $x ⩽ y ∧ y ⩽ x$ then $x + u = y$ and $y + v = x$ for some $u , v ∈ ℕ$. 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 ∈ ℕ$: $x ⩽ y ∨ y ⩽ x$.

Proof.

Induction on $x$. For $x = 0$ note that $0 ⩽ y$ as $0 + y = y$ by a previous proposition. Now assume $x ⩽ y$. Then $y = x + u$ for some $u ∈ ℕ$. If $u = 0$ then $x = y$ and $y ⩽ x + 1$ as $y = x + 1$. On the other hand, if $u ≠ 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 ⩽ y$. Finally, assume $y ⩽ x$, so $y + u = x$ for some $u$. Then $y + ( u + 1 ) = ( y + u ) + 1 = x + 1$ so $y ⩽ ( x + 1 )$.

## 4. Subtraction

Theorem.

If $x , y ∈ ℕ$ and $x ⩽ y$ then there is a unique $z ∈ ℕ$ 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 ⩽ y$ then $z ≠ 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 ⩽ y$ we write $y - x$ for the unique $z$ such that $x + z = y$.

## 5. Least number principle

We also make the usual definitions concerning $⩽$: we say $x ⩾ y$ if $x ⩽ y$ and $x < y$ or $y > x$ if $x ⩽ y$ and $x ≠ y$ and can also justify the least number principle.

Least number principle.

Suppose there is some $n ∈ ℕ$ with a property $P$. Then there is a least $n 0$ in $ℕ$ with $P$.

Proof.

Let , 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 ∈ ℕ$ satisfying $P ( n )$.

Subproof.

Suppose there is no least $x ∈ ℕ$ satisfying $P ( x )$.

Then $0 ∈ X$ since since $y < 0 ⇒ ¬ P ( y )$ holds because $y < 0$ is false.

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

It follows by induction that , and this clearly implies that , contradicting our assumption that there is some $n$ with $P ( n )$.

This proves by contradiction, that there is a least $x ∈ ℕ$ with $P ( x )$.