## 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:

Suppose is well ordered and then by 2) If then by 1) and so so any ordering would result in 0&lt;=(-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 of the so is the least element of a 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 &quot;If not B then not A&quot; (the style of modus tollens) bears to &quot;If A then B&quot; (the style of modus ponens). It is known light-heartedly as the &quot;minimal criminal&quot; method and is similar in its nature to Fermat's method of &quot;infinite descent&quot;. 