Well-ordering principle

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 2,4,6,...; and 1,3,5,...).

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 {…,−2,−1,0,1,2,3,…} 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∈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 a=p1p2...pk and b=q1q2...ql, meaning that n=p1p2...pk⋅q1q2...ql, a product of primes. This contradicts the assumption that n∈C, so the assumption that C is nonempty must be false.

Integer summation

Theorem: 1+2+3+...+n=n(n+1)2 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 C={n∈ℕ∣1+2+3+...+n≠n(n+1)2}. 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,

1+2+3+...+(c−1)=(c−1)c21+2+3+...+(c−1)+c=(c−1)c2+c=c2−c2+2c2=c2+c2=c(c+1)2,

which shows that the equation holds for c, a contradiction. So, the equation must hold for all positive integers.