Ordering

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

- (R) For any , and , thus .
- (AS) Let and be two natural numbers such that and . We have:

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

Hence, .

Thus we have , i.e. .

Thus we have , 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.

or or |

by induction on .

- Suppose that :
- If , then ;
- If , then

- 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.

- (i)
- and .
- (ii)
- or .