The well-ordering principle is a property of the positive integers which is equivalent to the statement of the principle of mathematical induction. Every nonempty set of non-negative integers contains a least element; there is some integer in such that for all ’s belonging. Many constructions of the integers take it as an axiom. It is useful in proofs of properties of the integers, including in Fermat's method of infinite descent.
The well-ordering principle says that the positive integers are well-ordered. An ordered set is said to be well-ordered if each and every nonempty subset has a smallest or least element. So the well-ordering principle is the following statement:
Every nonempty subset of the positive integers has a least element.
Note that this property is not true for subsets of the integers (in which there are arbitrarily small negative numbers) or the positive real numbers (in which there are elements arbitrarily close to zero).
An equivalent statement to the well-ordering principle is as follows:
The set of positive integers does not contain any infinite strictly decreasing sequences.
The proof that this principle is equivalent to the principle of mathematical induction is below.
Here are several examples of properties of the integers which can be proved using the well-ordering principle. Note that it is usually used in a proof by contradiction; that is, construct a set suppose is nonempty, obtain a contradiction from the well-ordering principle, and conclude that must be empty.
There are no positive integers strictly between 0 and 1.
Let be the set of integers such that Suppose is nonempty; let be its smallest element. Multiplying both sides of by gives The square of a positive integer is a positive integer, so is an integer such that This is a contradiction of the minimality of Hence is empty.
What is wrong with this "proof" of the following statement?
For every positive integer the number is even.
Let be the subset of positive integers for which is odd. Assume is nonempty.
Let be its smallest element.
Then so is even.
But so equals which is a sum of two even numbers, which is even.
So which is a contradiction. Therefore, is empty, and the result follows.
Every positive integer has a prime divisor.
Let be the set of positive integers with no prime divisor. Suppose is nonempty. Let be its smallest element. Note that is cannot be prime, since divides itself and if were prime, it would be its own prime divisor. So is composite: it must have a divisor with But then must have a prime divisor (by the minimality of ). Call it Then but so This is a contradiction. Therefore is empty.
Every positive integer can be written as a product of one or more primes.
Let be the set of positive integers that cannot be written as a product of primes. Suppose is nonempty. Let be its smallest element. Note that is not prime, since then would be a prime factorization. So is composite: with But and can be written as a product of primes, by the minimality of So is a product of products of primes and hence is a product of primes itself. This is a contradiction. Therefore is empty.
First, here is a proof of the well-ordering principle using induction:
Let be a subset of the positive integers with no least element. Clearly, since it would be the least element if it were. Let be the complement of so Now suppose every positive integer is in Then if it would be the least element of since every integer smaller than is in the complement of This is not possible, so instead.
The above paragraph implies that every positive integer is in by strong induction. So is the empty set.
Second, here is a proof of the principle of induction using the well-ordering principle:
Suppose is a property of an integer such that is true, and being true implies that is true. Let be the set of integers such that is false. Suppose is nonempty and let be its least element. Since is true, so so is a positive integer, and by minimality So by definition is true, but then by the property of given above, being true implies that is true. So contradiction. So is empty; so is true for all
The above discussion assumed the standard ordering on the positive integers (and integers, and positive real numbers). As pointed out in the introduction, not every ordered set is well-ordered, but it is in fact true that every set has an ordering under which it is well-ordered, if one assumes the axiom of choice. In fact, these two statements are equivalent, and the first one is sometimes, confusingly, called the "well-ordering principle" in the literature. Our convention will be to call this set-theoretic statement the "well-ordering theorem," and to preserve the name "well-ordering principle" for the property of the positive integers discussed above.