# the Well-Ordering Principle

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 , 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 be a nonempty collection of natural numbers. Consider , the natural numbers that aren't in (in set notation, ). Since isn't empty, isn't all of . We'll show that, for all , is in .

base case : If , then is least. So , i.e. .

inductive step: Suppose . If any of the numbers less than were in , 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 is in . If , then would be least. So , i.e. . This completes the inductive step.

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

The Well-Ordering Principle can be used to prove all sort of theorems about natural numbers, usually by assuming some set is nonempty, finding a least element of , and inducting backwards" to find an element of less than --thus yielding a contradiction and proving that 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 be the set of natural numbers greater than 1 which cannot be written as the product of primes. By WOP, has a least element .

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

This contradiction establishes that 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.

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

The Division Algorithm. Let be natural numbers. Then there are nonnegative integers so that and . Moreover, and are unique. We call the quotient and 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 and , if , then set and . Then , and as required.

If , set and .

We are left with the case . Consider the set . Since , for all . In particular, , or equivalently . So , hence .

Since is nonempty, by WOP, has a least element, which we'll call . Set and . By choice of , we have , but we need to show that .

Since is least in , cannot be an element of . So .

We need to show that . Suppose, to the contrary, that . Then

so that . But , which is an element of . This contradiction establishes that as required.

Now that we have established the existence of and , let us prove their uniqueness. Consider two pairs , so that

Without loss of generality, assume . We have

Since , this means that guarantees , and that iff . We will show that , hence , i.e. the quotient-remainder pair is unique.

Consider the set as above, with least element . If , then , so . But then cannot be a quotient. So . On the other hand, if , then

and subtracting from both sides we have . But is least, so . This contradiction establishes that .

So we see that . But the same argument applies to , hence .

Corollary. Any integer is either even or odd.

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

The division algorithm says we must be able to write for some . Since we ruled out , we must have , i.e. is odd.

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 natural numbers is .

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 ) so that the sum of the first natural numbers isn't . Consider the set of all such numbers:

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

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

Maybe ? No, because . So . But then has a predecessor, .

Since , we know (, after all, was least among the elements of ).

That is, .

Now, consider :

which shows that actually, . But this is a contradiction! So our initial supposition was incorrect, and thus the claim is true. .

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 to ).

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