Theorem 4.7: Let x and n be natural numbers. The following are equivalent

1. 
2. 
3. x < n

Proof: The fact that 2. and 3. are equivalent follow from Definition 4.6

To show that 1. implies 2., assume that

We proceed by induction on n. If n = 0 then the result is vacuously true. Assume that the result is true for n = k and consider n = k + 1. Let

Then by Definition 1.3, either

or

If

then

by the induction hypothesis, and since

by Theorem 2.7. If

then

by Theorem 1.2.

In either case,

To show that 3. implies 1., Assume that x < n. To show that

we again proceed by induction on n. If n = 0, then n has no proper subsets, so the result is vacuously true. Assume that the result is true if n = k and we seek to prove that it is true if n = k + 1. Let

Since, by Definition 4.3, the natural numbers are all obtained by taking successive successors by Definition 4.3, and since the first successor of k is k + 1, it follows that x is not greater than k. By Theorem 4.6, either

or

If x = k, then

If x < k, then by the induction hypothesis,

In either event,