In mathematics, the well-ordering principle states that every non-empty subset of nonnegative integers contains a least element. In other words, the set of nonnegative integers is well-ordered).

The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem", according to which every set can be well-ordered. 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.

Properties

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:

• In Peano arithmetic, second-order arithmetic and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well-ordering principle, the principle is derived from the principle of mathematical induction, which is itself taken as basic.

• 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 in .

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

, 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 (which form an ordered integral domain).

Example applications

The well-ordering principle can be used in the following proofs.

Prime factorization

Theorem: Every integer greater than one can be factored as a product of primes. This theorem constitutes part of the Prime Factorization Theorem.

Proof be the set of all integers greater than one that cannot is empty.

cannot be prime since a prime number is nonempty must be false.

Integer summation

.

Proof. Therefore,

,

, a contradiction. So, the equation must hold for all positive integers.

References

cs:Princip dobrého uspořádání