The Well-ordering Principle

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 $S$ of non-negative integers contains a least element; there is some integer $a$ in $S$ such that $a≤b$ for all $b$’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 $S$ 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 $S,$ suppose $S$ is nonempty, obtain a contradiction from the well-ordering principle, and conclude that $S$ must be empty.

There are no positive integers strictly between 0 and 1.

Let $S$ be the set of integers $x$ such that $0<x<1.$ Suppose $S$ is nonempty; let $n$ be its smallest element. Multiplying both sides of $n<1$ by $n$ gives $n^2<n.$ The square of a positive integer is a positive integer, so $n^2$ is an integer such that $0<n^2<n<1.$ This is a contradiction of the minimality of $n.$ Hence $S$ is empty. $_\square$

Every positive integer $> 1$ has a prime divisor.

Let $S$ be the set of positive integers $>1$ with no prime divisor. Suppose $S$ is nonempty. Let $n$ be its smallest element. Note that $n$ is cannot be prime, since $n$ divides itself and if $n$ were prime, it would be its own prime divisor. So $n$ is composite: it must have a divisor $d$ with $1<d<n.$ But then $d$ must have a prime divisor (by the minimality of $n$). Call it $p.$ Then $p|d,$ but $d|n,$ so $p|n.$ This is a contradiction. Therefore $S$ is empty. $_\square$

Every positive integer $>1$ can be written as a product of one or more primes.

Let $S$ be the set of positive integers $>1$ that cannot be written as a product of primes. Suppose $S$ is nonempty. Let $n$ be its smallest element. Note that $n$ is not prime, since then $n=n$ would be a prime factorization. So $n$ is composite: $n=de$ with $1<d,e<n.$ But $d$ and $e$ can be written as a product of primes, by the minimality of $n.$ So $n$ is a product of products of primes and hence is a product of primes itself. This is a contradiction. Therefore $S$ is empty. $_\square$

First, here is a proof of the well-ordering principle using induction:

Let $S$ be a subset of the positive integers with no least element. Clearly, $1\notin S,$ since it would be the least element if it were. Let $T$ be the complement of $S;$ so $1\in T.$ Now suppose every positive integer $\le n$ is in $T.$ Then if $n+1 \in S,$ it would be the least element of $S,$ since every integer smaller than $n+1$ is in the complement of $S.$ This is not possible, so $n+1\in T$ instead.

The above paragraph implies that every positive integer is in $T,$ by strong induction. So $S$ is the empty set. $_\square$

Second, here is a proof of the principle of induction using the well-ordering principle:

Suppose $P$ is a property of an integer such that $P(1)$ is true, and $P(n)$ being true implies that $P(n+1)$ is true. Let $S$ be the set of integers $k$ such that $P(k)$ is false. Suppose $S$ is nonempty and let $k$ be its least element. Since $P(1)$ is true, $1\notin S,$ so $k\ne 1,$ so $k-1$ is a positive integer, and by minimality $k-1 \notin S.$ So by definition $P(k-1)$ is true, but then by the property of $P$ given above, $P(k-1)$ being true implies that $P(k)$ is true. So $k \notin S,$ contradiction. So $S$ is empty; so $P(k)$ is true for all $k.$ $_\square$

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.