## 2.3. The Principle of Induction

### Example 2.3.5(a):

Impose a new ordering labeled

The natural numbers, ordered by the ordering *<<*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*

*<<*well-ordered ? Does it have the property that every element has an immediate predecessor ?*<<*, 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.

- If it contains only odd numbers, then the smallest
number in the usual ordering is the smallest element of
*A* - If it contains only even numbers, then the smallest
number in the usual ordering is the smallest element of
*A* - If it contains both even and odd numbers, then
the smallest of the even numbers in the usual ordering is
the smallest element of
*A*

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

has a smallest element (namely 1), but 1 does not have an immediate predecessor, sinceA= {1, 3, 5, 7, ...}

*every*even number is smaller than 1 by definition.