Next: Substraction Up: The natural numbers Previous: Multiplication   Contents

## Ordering

We define a binary relation (=''less than or equal to'') in in the following way:

Definition 6.1.27   For any two natural numbers and , we have:

The following theorem requires the belonging of 0 to the set of natural numbers.

Theorem 6.1.28   The binary relation is an ordering on .

Proof. First we prove that is an ordering on .
1. (R) For any , and , thus .
2. (AS) Let and be two natural numbers such that and . We have:

Thus and by Proposition 1.16, , i.e. .
3. (T) Let , and be three natural numbers such that and . We have:

Hence, .

Proposition 6.1.29   For any triple of natural numbers,

Proof. By definition, we have:

Thus we have , i.e. .

Proposition 6.1.30   For any triple of natural numbers,

Proof. By definition, we have:

Thus we have , i.e. .

Now we define a not so new'' binary relation on : when and are two natural numbers, we denote if     and , i.e.

Obviously, this relation is not an ordering, because of a lack of reflexivity. Nevertheless it has useful properties; in particular it is transitive and verifies properties like Proposition 1.29 and Proposition 1.30.

Theorem 6.1.31   The relation is a total ordering in , i.e.

 or

Proof. What has to be proven is that the ordering is total; we will prove it in the following form:

 or     or

by induction on .
• Suppose that :
• If , then ;
• If , then
and we are done.
• Assume that and verify the theorem for any ; we shall now compare and .
• Suppose that , i.e. it exists such that . Then we have: and .
• If , it exists such that . As , it exists a natural number such that and we have:

If , then ; otherwise, and we are done.

The following result is easily proven by contrapositive arguments.

Proposition 6.1.32   Let , and be three natural numbers. Then we have:
(i)
and .
(ii)
or .

Next: Substraction Up: The natural numbers Previous: Multiplication   Contents
root 2002-06-10