Well-ordering principle

From Wikipedia, the free encyclopedia

Sometimes the phrase well-ordering principle is taken to be synonymous with "well-ordering theorem".

On other occasions the phrase is taken to mean the proposition that the set of integers {..., -2, -1, 0, 1, 2, 3, ....} contains a well-ordered subset, called the natural numbers, of which any nonempty subset always contains a least element. Depending on the framework in which the natural numbers are introduced, this (second order) 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 (again, either as an axiom or a theorem about the real number system), i.e., every bounded (from below) set has an infimum, then also every set A of natural numbers has an infimum, say a^*. We can now find an integer n^* such that a^* lies in the half-open interval (n^*-1, n^* ], and can then show that we must have a^* = n^*, and n^* in A.
• In axiomatic set theory, the natural numbers are defined as the smallest inductive set (i.e., set containing 0 and closed under the successor operation). One can (even without invoking the regularity axiom) show that the set of all natural numbers n such that "{0,..., n} is well-ordered" is inductive, and must therefore contain all natural numbers; from this property it is easy to conclude that the set of all natural numbers is also well-ordered.

In the second sense, the 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 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".

Garrett Birkhoff and Saunders MacLane 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 (which form an ordered integral domain). It therefore characterizes integers among integral domains; every well-ordered integral domain is isomorphic to the integers.