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

= { X U : 0 X x X   f ( x ) X }

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 x   ( P ( x ) P ( x +1 ) ) . Then x   P ( x ) .

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 0 X x X   f ( x ) X 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 0 X x X   f ( x ) X 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 : x 0 w   x = w + 1 .

Proof.

Induction on x : Base case: 0 0 w   0 = w + 1 is trivially true as 0 0 is false and any implication 0 0 A is therefore true. Now assume x 0 w   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 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 X = { x : y < x   ¬ P ( y ) } , 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 y   y < 0 ¬ P ( y ) 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 y   y X , and this clearly implies that y   ¬ P ( y ) , contradicting our assumption that there is some n with P ( n ) .

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