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 1s; fortunately there is a way round this problem.

Definition.

Choose to be some fixed infinite universe of objects, and be an injection which is not a surjection, so ()=() implies = for all , but some is not equal to () for any . Fix some such and call this zero or 0. Now let +1 be () , and define the set of natural numbers =0,(0),((0)) ,(((0))) , by

= 0 ()

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

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

2. Induction and inductive definitions

Principle of Induction.

Suppose

is a property such that

(0)

, i.e., 0 has property

, and (

()

(+1))

. Then

()

.

Proof.

Let be the set of elements of that have property

, i.e., =

()

. Then is an example of a set with 0 () and so since the definition of is that it is the intersection of all such sets with this property. So every natural number is in and hence each has

()

.

Principle of Inductive Definitions.

A definition of the following kind, (0)= ₀ and (+1)=(,()) , defines a function on .

Proof.

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

Definition.

For a natural number we define ₍₎₌₊ inductively by +0= (0)= and +(+1)= (+1)= ()+1=(+)+1 . We write if there is a natural number such that += .

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 ,, : (+)+=+(+) .

Proof.

Induction on . Base case: (+)+0=+=+(+0) . Induction step: (+)+(+1)=((+)+)+1=(+(+))+1 by the induction hypothesis, so (+)+(+1)=+((+)+1)=+(+(+1)) .

Proposition.

The following holds for all : =0+ .

Proof.

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

Proposition.

The following holds for all , : +=+ .

Proof.

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

Proposition.

The following holds for all : 0 =+1 .

Proof.

Induction on : Base case: 00 0=+1 is trivially true as 00 is false and any implication 00 is therefore true. Now assume 0 =+1 and consider +1. Then either =0 in which case +1=0+1 and we are finished with =0, or 0 so =+1 for some hence +1=(+1)+1 and we are done with =+1 .

Proposition.

The following holds for all ,, : +=+ = .

Proof.

Induction on . For =0 note that if +0=+0 then = as +0= and +0= by definition. Now assume +(+1)=+(+1) , so (+)+1=(+)+1 by definition of +. But the +1 operation on is one-to-one so this implies +=+ which implies = by the induction hypothesis.

Proposition.

The following holds for all , : +=0 =0 .

Proof.

If 0 then =+1 for some so 0=+(+1)=(+)+1 which is impossible as 0 is not in the image of the function on , so 0 cannot equal +1 for any .

Proposition.

The following holds for all , : += =0 .

Proof.

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

Proposition.

The following holds for all ,, : ( ) .

Proof.

If then there are , with =+ and =+ . So =(+)+=+(+) by associativity, so .

Proposition.

The following holds for all ,, : ( ) = .

Proof.

If then += and += for some , . Thus =(+)+=+(+) and so +=0 , ==0 and hence = by previous parts.

Proposition.

The following holds for all , : .

Proof.

Induction on . For =0 note that 0 as 0+= by a previous proposition. Now assume . Then =+ for some . If =0 then = and +1 as =+1 . On the other hand, if 0 and =+ then =+1 for some , by a previous proposition, so =+=+(+1)=(+1)+ by commutativity and associativity, hence . Finally, assume , so += for some . Then +(+1)=(+)+1=+1 so (+1) .

4. Subtraction

Theorem.

If , and then there is a unique such that += .

Proof.

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

For uniqueness suppose, +=+= . Then +=+ so = by a previous proposition.

Definition.

If we write - for the unique such that += .

5. Least number principle

We also make the usual definitions concerning : we say if and or if and and can also justify the least number principle.

Least number principle.

Suppose there is some with a property

. Then there is a least ₀ in with

.

Proof.

Let =

()

, the set of such that every smaller fails to have

. We use to show that there is a least number satisfying

.

Subproof.

Suppose there is some satisfying

()

.

Subproof.

Suppose there is no least satisfying

()

.

Then 0 since 0

()

since 0

()

holds because 0 is false.

Also if !math X then if

()

hold it would mean that is the least element satisfying

()

, since all have

()

because . This is impossible by our assumption, so therefore

()

, and hence +1 is in .

It follows by induction that , and this clearly implies that

()

, contradicting our assumption that there is some with

()

.

This proves by contradiction, that there is a least with

()

.