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)andimplies

andare not well ordered because they contain no smallest element: ifthen so isNeither iswell ordered:

Supposeis well ordered andthen by 2)
Ifthen by 1)
and soso any ordering would result in 0<=(-1), which is impossible, because ifthen by 1),By 2),
ThusANDso

and neither isthe set of positive real numbers, because ifis the least element ofthesois the least element ofa contradiction.

The well ordering principle implies that every well ordered set bounded below has an infimum, so every setof natural numbers has an infimum, sayWe can find an integersuch thatlies in the half-open intervalhence we must haveand

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