Well-ordering principle

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (April 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.