The Well Ordering Principle
The well-ordering principle states that every non-empty set of positive integers contains a smallest element.
It is necessary for this that the set of positive numbers is a well ordered set – that is, they can be arranged in increasing order. Every subset of this set is then well ordered, so the smallest element in the set can be identified.
Any well ordered set satisfies
1)
if
2)
and
implies
and
are not well ordered because they contain no smallest element: if
then so is
Neither is
well ordered:
Supposeis well ordered and
then by 2)
If
then by 1)
and so
so any ordering would result in 0<=(-1), which is impossible, because if
then by 1),
By 2),
Thus
AND
so
and neither is
the set of positive real numbers, because if
is the least element ofthe
so
is the least element ofa contradiction.
The well ordering principle implies that every well ordered set bounded below has an infimum, so every set
of natural numbers has an infimum, say
We can find an integer
such that
lies in the half-open interval
hence we must have
and
The well ordering principle is often used in the following way: to prove that every natural number belongs to a specified set S, assume the contrary and infer the existence of a (non-zero) smallest counterexample. Then show either that there must be a still smaller counterexample or that the smallest counterexample is not a counter example, producing a contradiction. This mode of argument bears the same relation to proof by mathematical induction that "If not B then not A" (the style of modus tollens) bears to "If A then B" (the style of modus ponens). It is known light-heartedly as the "minimal criminal" method and is similar in its nature to Fermat's method of "infinite descent".
