2.3. The Principle of Induction

Example 2.3.5(a):

Impose a new ordering labeled << on the natural numbers as follows:
  • if n and m are both even, then define n << m if n < m
  • if n and m are both odd, then define n << m if n < m
  • if n is even and m is odd, we always define n << m
Is the set of natural numbers, together with this new ordering << well-ordered ? Does it have the property that every element has an immediate predecessor ?
The natural numbers, ordered by the ordering <<, could be listed in order as follows:
2, 4, 6, 8, ....., 1, 3, 5, 7, 9, ..... ,
To show it is well-ordered, take any subset A of natural numbers. Hence, the set is well-ordered.

But, not every element has an immediate predecessor. For example, the set:

A = {1, 3, 5, 7, ...}
has a smallest element (namely 1), but 1 does not have an immediate predecessor, since every even number is smaller than 1 by definition.
Next | Previous | Glossary | Map