Chapter 2 The Well Ordering Principle26
m 0 =n 0 , which implies
the fraction
m 0 =p
n 0 =p
cannot be in written in lowest terms either.
So by definition ofC, the numerator,m 0 =p, is inC. Butm 0 =p < m 0 , which
contradicts the fact thatm 0 is the smallest element ofC.
Since the assumption thatCis nonempty leads to a contradiction, it follows that
Cmust be empty. That is, that there are no numerators of fractions that can’t be
written in lowest terms, and hence there are no such fractions at all.
We’ve 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 alln 2 N” using the Well Ordering Principle:
Define the set,C, ofcounterexamplestoPbeing true. Namely, define^1
CWWDfn 2 NjP.n/is falseg:
Assume for proof by contradiction thatCis nonempty.
By the Well Ordering Principle, there will be a smallest element,n, inC.
Reach a contradiction (somehow) —often by showing how to usento find
another member ofCthat is smaller thann. (This is the open-ended part
of the proof task.)
Conclude thatCmust be empty, that is, no counterexamples exist. QED
2.3 Summing the Integers
Let’s use this template to prove
