In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which precedes if and only if is either or the sum of and some positive integer. The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element. Depending on the framework in which the natural numbers are introduced, this property of the set of natural numbers is either an axiom or a provable theorem. For example:
Considering the natural numbers as a subset of the real numbers, and assuming that we know already that the real numbers are complete, i.e., every bounded set has an infimum, then also every set of natural numbers has an infimum, say. We can now find an integer such that lies in the half-open interval, and can then show that we must have, and in .
In axiomatic set theory, the natural numbers are defined as the smallest inductive set. One can show that the set of all natural numbers such that " is well-ordered" is inductive, and must therefore contain all natural numbers; from this property one can conclude that the set of all natural numbers is also well-ordered.
In the second sense, this phrase is used when that proposition is relied on for the purpose of justifying proofs that take the following form: to prove that every natural numberbelongs to a specified set, assume the contrary, which implies that the set of counterexamples is non-empty and thus contains a smallest counterexample. Then show that for any counterexample there is a still smaller counterexample, producing a contradiction. This mode of argument is the contrapositive of proof by complete induction. It is known light-heartedly as the "minimal criminal" method and is similar in its nature to Fermat's method of "infinite descent". Garrett Birkhoff and Saunders Mac Lane wrote in A Survey of Modern Algebra that this property, like the least upper bound axiom for real numbers, is non-algebraic; i.e., it cannot be deduced from the algebraic properties of the integers.
