Chapter 2

The Well Ordering Principle

Every nonempty set of nonnegative integers has a smallest element.
This statement is known as The Well Ordering Principle. Do you believe it?
Seems sort of obvious, right? But notice how tight it is: it requires a nonempty
set its false for the empty set which has no smallest element because it has no
elements at all! And it requires a set of nonnegative integers its false for the
set of negative integers and also false for some sets of nonnegative rationals for
example, the set of positive rationals. So, the Well Ordering Principle captures
something special about the nonnegative integers.
2.1 Well Ordering Proofs
While the Well Ordering Principle may seem obvious, its hard to see offhand why
it is useful. But in fact, it provides one of the most important proof rules in discrete
mathematics.
In fact, looking back, we took the Well Ordering Principle for granted in prov-
ing that

2is irrational. That proof assumed that for any positive integers mand
n, the fraction m/ncan be written in lowest terms, that is, in the form m

/n

where
m

and n

are positive integers with no common factors. How do we know this is

always possible?
Suppose to the contrary that there were m, n Z
+
such that the fraction m/n
cannot be written in lowest terms. Now let Cbe the set of positive integers that are
numerators of such fractions. Then m C, so C is nonempty. Therefore, by Well
Ordering, there must be a smallest integer, m
0
C. So by denition of C, there is
an integer n
0
>0such that
the fraction
m
0
cannot be written in lowest terms.
n
0
31
32 CHAPTER 2. THE WELL ORDERING PRINCIPLE
This means that m
0
and n
0
must have a common factor, p >1. But
m
0
/p m
0
= ,
n
0
/p n
0
so any way of expressing the left hand fraction in lowest terms would also work
for m
0
/n
0
, which implies
m
0
/p
the fraction cannot be in written in lowest terms either.
n
0
/p
So by denition of C, the numerator, m
0
/p, is in C. But m
0
/p<m
0
, which contra-
dicts the fact that m
0
is the smallest element of C.
Since the assumption that C is nonempty leads to a contradiction, it follows
that C must be empty. That is, that there are no numerators of fractions that cant
be written in lowest terms, and hence there are no such fractions at all.
Weve been using the Well Ordering Principle on the sly from early on!
2.2 Template for Well Ordering Proofs
More generally, there is a standard way to use Well Ordering to prove that some
property, P(n)holds for every nonnegative integer, n. Here is a standard way to
organize such a well ordering proof:
To prove that P(n)is true for all nN using the Well Ordering Principle:
Dene the set, C, of counterexamples to P being true. Namely, dene
a
C::={nN|P(n)is false}.
Assume for proof by contradiction that Cis nonempty.
By the Well Ordering Principle, there will be a smallest element, n, in C.
Reach a contradiction (somehow) often by showing how to use nto nd
another member of C that is smaller than n. (This is the open-ended part of
the proof task.)
Conclude that Cmust be empty, that is, no counterexamples exist. QED
a
The notation {n|P(n)}means the set of all elements n, for which P(n)is true.
2.2. TEMPLATE FOR WELL ORDERING PROOFS 33
2.2.1 Problems
Class Problems
Problem 2.1.
The proof below uses the Well Ordering Principle to prove that every amount of
postage that can be paid exactly using only 6 cent and 15 cent stamps, is divisible
by 3. Let the notation j | k indicate that integer j is a divisor of integer k, and
let S(n) mean that exactly n cents postage can be paid using only 6 and 15 cent
stamps. Then the proof shows that
S(n) IMPLIES 3|n, for all nonnegative integers n. (*)
Fill in the missing portions (indicated by . . . ) of the following proof of (*).
Let Cbe the set of counterexamples to (*), namely
1
C::={n|. . .}
Assume for the purpose of obtaining a contradiction that Cis nonempty.
Then by the WOP, there is a smallest number, m C. This mmust be
positive because. . . .
But if S(m)holds and mis positive, then S(m6)or S(m15)must
hold, because. . . .
So suppose S(m6)holds. Then 3|(m6), because. . .
But if 3|(m6), then obviously 3|m, contradicting the fact that mis
a counterexample.
Next suppose S(m15)holds. Then the proof for m6carries over
directly for m15to yield a contradiction in this case as well. Since we
get a contradiction in both cases, we conclude that. . .
which proves that (*) holds.
Problem 2.2.
Eulers Conjecture in 1769 was that there are no positive integer solutions to the
equation
a
4
+b
4
+c
4
=d
4
.
Integer values for a, b, c, d that do satisfy this equation, were rst discovered in
1986. So Euler guessed wrong, but it took more two hundred years to prove it.
Now lets consider Lehmans
2
equation, similar to Eulers but with some coef-
cients:
8a
4
+ 4b
4
+ 2c
4
=d
4
(2.1)
1
The notation {n|. . .} means the set of elements, n, such that . . . .
2
Suggested by Eric Lehman, a former 6.042 Lecturer.

34 CHAPTER 2. THE WELL ORDERING PRINCIPLE
Prove that Lehmans equation (2.1) really does not have any positive integer
solutions.
Hint: Consider the minimum value of aamong all possible solutions to (2.1).
Homework Problems
Problem 2.3.
Use the Well Ordering Principle to prove that any integer greater than or equal to
8 can be represented as the sum of integer multiples of 3 and 5.
2.3 Summing the Integers
Lets use this this template to prove
Theorem.
1 + 2 + 3 + +n=n(n+1)/2 (2.2)
for all nonnegative integers, n.
First, we better address of a couple of ambiguous special cases before they trip
us up:
If n= 1, then there is only one term in the summation, and so 1+2+3+ +n
is just the term 1. Dont be misled by the appearance of 2 and 3 and the
suggestion that 1and nare distinct terms!
If n0, then there are no terms at all in the summation. By convention, the
sum in this case is 0.
So while the dots notation is convenient, you have to watch out for these special
cases where the notation is misleading! (In fact, whenever you see the dots, you
should be on the lookout to be sure you understand the pattern, watching out for
the beginning and the end.)
We could have eliminated the need for guessing by rewriting the left side of (2.2)
with summation notation:
n
i or i.
i=1 1in
Both of these expressions denote the sum of all values taken by the expression to
the right of the sigma as the variable, i, ranges from 1 to n. Both expressions make
it clear what (2.2) means when n = 1. The second expression makes it clear that
when n = 0, there are no terms in the sum, though you still have to know the
convention that a sum of no numbers equals 0 (the product of no numbers is 1, by
the way).
OK, back to the proof:

35 2.4. FACTORING INTO PRIMES
Proof. By contradiction. Assume that the theorem is false. Then, some nonnegative
integers serve as counterexamples to it. Lets collect them in a set:
C::= nN|1 + 2 + 3 + +n=
n(n
2
+1)
.
By our assumption that the theorem admits counterexamples, Cis a nonempty set
of nonnegative integers. So, by the Well Ordering Principle, C has a minimum
element, call it c. That is, cis the smallest counterexample to the theorem.
Since cis the smallest counterexample, we know that (2.2) is false for n=cbut
true for all nonnegative integers n < c. But (2.2) is true for n = 0, so c > 0. This
means c1is a nonnegative integer, and since it is less than c, equation (2.2) is true
for c1. That is,
1 + 2 + 3 + + (c1) =
(c1)c
.
2
But then, adding cto both sides we get
1 + 2 + 3 + + (c1)+c=
(c1)c
+c=
c
2
c+ 2c
=
c(c+1)
,
2 2 2
which means that (2.2) does hold for c, after all! This is a contradiction, and we are
done.
2.3.1 Problems
Class Problems
Problem 2.4.
Use the Well Ordering Principle to prove that
n

k
2
=
n(n+1)(2n+1)
. (2.3)
6
k=0
for all nonnegative integers, n.
2.4 Factoring into Primes
Weve previously taken for granted the Prime Factorization Theorem that every inte-
ger greater than one has a unique
3
expression as a product of prime numbers. This
is another of those familiar mathematical facts which are not really obvious. Well
prove the uniqueness of prime factorization in a later chapter, but well ordering
gives an easy proof that every integer greater than one can be expressed as some
product of primes.
Theorem 2.4.1. Every natural number can be factored as a product of primes.
3
. . . unique up to the order in which the prime factors appear
36 CHAPTER 2. THE WELL ORDERING PRINCIPLE
Proof. The proof is by Well Ordering.
Let C be the set of all integers greater than one that cannot be factored as a
product of primes. We assume Cis not empty and derive a contradiction.
If Cis not empty, there is a least element, nC, by Well Ordering. The ncant
be prime, because a prime by itself is considered a (length one) product of primes
and no such products are in C.
So nmust be a product of two integers aand bwhere 1<a, b<n. Since aand b
are smaller than the smallest element in C, we know that a, b / C. In other words,
a can be written as a product of primes p
1
p
2
p
k
and b as a product of primes
q
1
q
l
. Therefore, n = p
1
p
k
q
1
q
l
can be written as a product of primes,
contradicting the claim that nC. Our assumption that C = must therefore be
false.
MIT OpenCourseWare
http://ocw.mit.edu
6.042J / 18.062J Mathematics for Computer Science
Spring 2010
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.