the Well-Ordering Principle – Foundations of Mathematics

Here's a nice fact about the natural numbers:

Well-Ordering Principle. Every nonempty collection of natural numbers has a least element.

Observe, before we prove this, that a similar statement is not true of many sets of numbers. The interval $(0,1)$ , for example, has no least element. The set of even integers has no least element. The set of natural numbers has no greatest element.

Proof. We'll prove the contrapositive, namely, that if a collection of natural numbers has no least element, then it must be empty.

Let $T$ be a nonempty collection of natural numbers. Consider $S$ , the natural numbers that aren't in $T$ (in set notation, $S=\mathbb{N}\setminus T$ ). Since $T$ isn't empty, $S$ isn't all of $\mathbb{N}$ . We'll show that, for all $n\in\mathbb{N}$ , $n$ is in $S$ .

base case $n=1$ : If $1\in T$ , then $1$ is least. So $1\notin T$ , i.e. $1\in S$ .

inductive step: Suppose $n\in S$ . If any of the numbers less than $n$ were in $T$ , then one of them would be least (since there are only finitely many such numbers and we proved every finite set has a least element). So none of the numbers $1,\ldots,n$ is in $T$ . If $n+1\in T$ , then $n+1$ would be least. So $n+1\notin T$ , i.e. $n+1\in S$ . This completes the inductive step.

So we've shown that every natural number is in $S$ , which means that $T$ must be empty. This establishes the contrapositive of the theorem. $\Box$

The Well-Ordering Principle can be used to prove all sort of theorems about natural numbers, usually by assuming some set $T$ is nonempty, finding a least element $n$ of $T$ , and ``inducting backwards" to find an element of $T$ less than $n$ --thus yielding a contradiction and proving that $T$ is empty. In this sense, the Well-Ordering Principle and the Principle of Mathematical Induction are just two ways of looking at the same thing.

Indeed, one can prove that WOP, PCI, and PMI are all logically equivalent, so we could have taken any one of them as our fifth axiom for the natural numbers.

Fundamental Theorem of Arithmetic. Any natural number greater than 1 can be written as the product of primes.

Proof. Let $S$ be the set of natural numbers greater than 1 which cannot be written as the product of primes. By WOP, $S$ has a least element $n$ .

Clearly $n$ cannot be prime, so $n$ is composite. Then we can write $n=ab$ , where neither of $a$ and $b$ is 1. So $a<n$ and $b<n$ . If both of $a$ and $b$ had prime factorizations, then so would $n$ . Therefore at least one of $a$ and $b$ does not have a prime factorization (by relabeling, we can assume it's $a$ ). But $a<n$ and $a\in S$ , so $n$ was not least in $S$ .

This contradiction establishes that $S$ has no least element, hence by WOP must be empty. So every natural number greater than 1 can be written as the product of primes. $\Box$

Observe that this proof has more or less the same ``juicy bits" as the proof by PCI.

The Division Algorithm. Let $a,b$ be natural numbers. Then there are nonnegative integers $q,r$ so that $0\leq r<b$ and $a=bq+r$ . Moreover, $q$ and $r$ are unique. We call $q$ the quotient and $r$ the remainder.

This theorem is called the Division Algorithm because it asserts that any natural number can be divided, with remainder, by any other natural number.

Proof. Given $a$ and $b$ , if $a<b$ , then set $q=0$ and $r=a$ . Then $0\leq r<b$ , and $a=qb+r$ as required.

If $a=b$ , set $q=1$ and $r=0$ .

We are left with the case $a>b$ . Consider the set $S=\left\{n\in\mathbb{N}\middle| a-nb< 0\right\}$ . Since $b\geq 1$ , $kb\geq k$ for all $k\in\mathbb{N}$ . In particular, $ab\geq a$ , or equivalently $a-ab\leq 0$ . So $a-(a+1)b<0$ , hence $a+1\in S$ .

Since $S$ is nonempty, by WOP, $S$ has a least element, which we'll call $s$ . Set $q=s-1$ and $r=a-qb$ . By choice of $r$ , we have $a=qb+r$ , but we need to show that $0\leq r<b$ .

Since $s$ is least in $S$ , $q=s-1$ cannot be an element of $S$ . So $r=a-qb\geq 0$ .

We need to show that $r<b$ . Suppose, to the contrary, that $r\geq b$ . Then

$\begin{align*} r&\geq b\\ a-qb&\geq b\\ a-qb-b&\geq 0\\ a-(q+1)b&\geq 0 \end{align*}$

so that $q+1\notin S$ . But $q+1=s$ , which is an element of $S$ . This contradiction establishes that $r< b$ as required.

Now that we have established the existence of $q$ and $r$ , let us prove their uniqueness. Consider two pairs $(q,r)$ , $(q',r')$ so that

$\begin{align*} a&=qb+r\\ a&=q'b+r' \end{align*}$

Without loss of generality, assume $r\geq r'$ . We have

$\begin{align*} q'b+r'&=qb+r\\ q'b-qb&=r-r'\\ (q'-q)b&=r-r' \end{align*}$

Since $b\geq 1$ , this means that $r\geq r'$ guarantees $q\leq q'$ , and that $q=q'$ iff $r=r'$ . We will show that $q=q'$ , hence $r=r'$ , i.e. the quotient-remainder pair is unique.

Consider the set $S$ as above, with least element $s$ . If $q'>s-1$ , then $q'\geq s$ , so $q'\in S$ . But then $q'$ cannot be a quotient. So $q'\leq s-1$ . On the other hand, if $q'<s-1$ , then

$\begin{align*} b> r'&=a-q'b\\ &> a-(s-1)b \end{align*}$

and subtracting $b$ from both sides we have $0>a-(s-1)b$ . But $s$ is least, so $s-1\notin S$ . This contradiction establishes that $q'\geq s-1$ .

So we see that $q'=s-1$ . But the same argument applies to $q$ , hence $q=q'$ . $\Box$

Corollary. Any integer is either even or odd.

Proof. Given an integer $n$ , if $n$ is even we're done. So suppose $n$ is not even, i.e. we know that we cannot write $n=2k$ for any $k$ .

The division algorithm says we must be able to write $n=2k+r$ for some $0\leq r<2$ . Since we ruled out $r=0$ , we must have $r=1$ , i.e. $n=2r+1$ is odd. $\Box$

Note that we established previously that no integer could be both even and odd. Now we know that ``odd" and ``not even" are, in fact, synonyms.

"Disguised" Induction Proofs

We can use the WOP to give a kind of induction proof in disguise. Consider:

Claim. The sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$ .

Ordinarily, we'd prove this by induction.

Exercise. Write a proof of this claim by ordinary induction.

But we can set up a proof that uses the Well-Ordering Principle, like this:

Proof. Suppose not. Then there is some natural number (call it $p$ ) so that the sum of the first $p$ natural numbers isn't $\frac{p(p+1)}{2}$ . Consider the set of all such numbers:

$A=\left\{k\middle\vert 1+\cdots+k\neq \frac{k(k+1)}{2}\right\}$

Our assumption is that $p\in A$ ; in particular $A$ is not empty. (We believe in our hearts that there are no such numbers, i.e. that $A$ is empty. But this is a reductio ad absurdum proof, so we'll have to roll with it.)

By the Well-Ordering Principle, $A$ has a least element, which we'll call $N$ .

Maybe $N=1$ ? No, because $1=\frac{1\cdot (1+1)}{2}$ . So $N>1$ . But then $N$ has a predecessor, $n=N-1$ .

Since $n<N$ , we know $n\notin A$ ( $N$ , after all, was least among the elements of $A$ ).

That is, $1+2+\cdots+n=\frac{n(n+1)}{2}$ .

Now, consider $1+2+\cdots+N$ :

$\begin{align*} 1+2+\cdots+N&=1+2+\cdots+n+(n+1)\\ &=\frac{n(n+1)}{2}+n+1\\ &=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}\\ &=\frac{n^2+n+2(n+1)}{2}\\ &=\frac{n^2+3n+2}{2}\\ &=\frac{(n+1)(n+2)}{2}=\frac{N(N+1)}{2}\end{align*}$

which shows that actually, $N\notin A$ . But this is a contradiction! So our initial supposition was incorrect, and thus the claim is true. $\Box$ .

Now, I've highlighted some parts of the proof in green and orange. Why? The green part is what would be the base case if we wrote an ordinary induction proof. The orange part is the inductive step (from $n=N-1$ to $n+1=N$ ).

In fact any proof by ordinary induction can be gussied up this way, if you desire.