Mathematics for Computer Science

Chapter 2 The Well Ordering Principle32

Definition 2.4.2.Alower bound(respectively,upper bound) for a set,S, of real
numbers is a number,b, such thatbs(respectively,bs) for everys 2 S.

Note that a lower or upper bound of setSis not required to be in the set.

Corollary 2.4.3.Any set of integers with a lower bound is well ordered.

Proof. A set of integers with a lower boundb 2 Rwill also have the integernD
bbcas a lower bound, wherebbc, called the floor ofb, is gotten by rounding down
bto the nearest integer. So Theorem 2.4.1 implies the set is well ordered. 

Corollary 2.4.4.Any nonempty set of integers with an upper bound has a maximum
element.

Proof. Suppose a set,S, of integers has an upper boundb 2 R. Now multiply each
element ofSby -1; let’s call this new set of elementsS. Now, of course,bis a
lower bound ofS. SoShas a minimum elementmby Corollary 2.4.3. But
then it’s easy to see thatmis the maximum element ofS. 

2.4.1 A Different Well Ordered Set (Optional)

Another example of a well ordered set of numbers is the setFof fractions that can
be expressed in the formn=.nC1/:

0

1

;

1

2

;

2

3

;

3

4

;:::;

n

nC 1

;::::

The minimum element of any nonempty subset ofFis simply the one with the
minimum numerator when expressed in the formn=.nC1/.
Now we can define a very different well ordered set by adding nonnegative inte-
gers to numbers inF. That is, we take all the numbers of the formnCfwherenis
a nonnegative integer andf is a number inF. Let’s call this set of numbers—you
guessed it—NCF. There is a simple recipe for finding the minimum number in
any nonempty subset ofNCF, which explains why this set is well ordered:

Lemma 2.4.5.NCFis well ordered.

Proof. Given any nonempty subset,S, ofNCF, look at all the nonnegative inte-
gers,n, such thatnCfis inSfor somef 2 F. This is a nonempty set nonnegative
integers, so by the WOP, there is a minimum one; call itns.
By definition ofns, there is somef 2 Fsuch thatnSCf is in the setS. So
the set all fractionsf such thatnSCf 2 Sis a nonempty subset ofF, and since
Fis well ordered, this nonempty set contains a minimum element; call itfS. Now
it easy to verify thatnSCfSis the minimum element ofS(Problem 2.14).