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 by its "natural" or "magnitude" order in which x precedes y if and only if y is either x or the sum of x and some nonnegative integer (other orderings include the ordering ; and ). 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.

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 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 number belongs to a specified set S, 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 (by well-ordering principle). Let C be the set of all integers greater than one that cannot be factored as a product of primes. We show that C is empty. Assume for the sake of contradiction that C is not empty. Then, by the well-ordering principle, there is a least element n \in C; n cannot be prime since a prime number itself is considered a length-one product of primes. By the definition of non-prime numbers, n has factors a, b, where a, b are integers greater than one and less than n. Since a, b < n, they are not in C as n is the smallest element of C. So, a, b can be factored as products of primes, where and, meaning that , a product of primes. This contradicts the assumption that n \in C, so the assumption that C is nonempty must be false.

Integer summation

Theorem: for all positive integers n. Proof. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non-empty set of positive integers. By the well-ordering principle, C has a minimum element c such that when n = c, the equation is false, but true for all positive integers less than c. The equation is true for n = 1, so c > 1; c - 1 is a positive integer less than c, so the equation holds for c - 1 as it is not in C. Therefore, which shows that the equation holds for c, a contradiction. So, the equation must hold for all positive integers.