The Well-Ordering Principle 559

All of the re sults that we used in this proof—including those tha t you may not have seen

before—are veriﬁed in our investigations, with one exception. This exception illustrates how easy it

is to take certain mathematical results for granted. The exception in the proof is that we can always

ﬁnd a rational number in reduced form that is equal to

m

n

. How do we kn ow we can do th is? Recall

that the rational numb ers

a

b

and

c

d

are equal if ad = bc. To show that we can ﬁnd a rational number

in reduc e d form that is equal to

m

n

, we might consider all rational numbers

a

b

that are equal to

m

n

and prove that there is one so that the greatest common divisor (or gcd) of a and b is 1. In other

words, let

S =

n

gcd(a, b) :

a

b

=

m

n

o

be the set of all greatest comm on divisors of the numerators and denominators of fractions that are

equal to

m

n

. Certainly S is not empty, since gcd(m, n) is in S. Also, since gcd(x, y) ≥ 1 for any

integers x and y, not both 0, it follows that the integers in S are all greater than or equal to 1. We

need to actually show that 1 is in S. If 1 is in S, then 1 will have to be the smallest element in S.

This is where our conclusion from Activity B.12 is helpful. If we assume that every none mpty

subset of N contains a smallest in teger, then S must contain a smallest integer d. Now all we have

to do is show that d = 1. This is be cause if d = 1, then there must be a fractio n

a

b

equal to

m

n

with

gcd(a, b) = 1. Since d ∈ S, there exists a rational number

a

b

that is equal to

m

n

with gc d(a, b) = d.

Now d divides both a and b, so let da

′

= a and db

′

= b for some positive integers a

′

and b

′

. Since

d = gcd(a, b), it follows that gcd(a

′

, b

′

) = 1. But

m

n

=

a

b

=

a

′

d

b

′

d

=

a

′

b

′

,

and so gcd(a

′

, b

′

) is in S. However, this can happen only if d = 1, and so 1 is the sma llest element

in S, and there is a fraction in reduced form that is equal to

m

n

.

The key to our proof that every rational number is equal to a rational number in reduced form

was the assumption that the set S contained a smallest elem ent. Based on Activity B.12, this seems

like a reasonable assumptio n to make. The principle that allows us to make it is called the Well-

Ordering Principle.

To thoro ughly understand the Well-Ordering Principle, we ﬁrst need to discuss well-ordered

sets. But to talk about well-o rdered sets, we need to understand ordered sets in general. This leads

us to th e idea of binary relations.

A binary relation on a set (or relation for sho rt) is simply a way to compare elements in the

set. For example, consider the set consisting of the citizens of the state of Michigan. We might say

that one person is related to another if the two have a t least one par e nt in common. Note that some

people in this set are relate d and others are not. This observation illustrates the fact that a relation

on a set does not need to compare every pair of elements in the set.

As a smaller example, let S = {1, 2, 3, 4}, and say that a an d b are related in S if a divides b.

In this case we have that 1 is related to 2, 3, and 4, while 2 is related only to 4. To clearly identify

related pairs of elements in S, we might list all of the related elements as ordered pairs. For this

relation, the resulting pairs are (1, 2), (1, 3), (1, 4), and (2, 4). The general deﬁnition of a relation

on a set follows this example.

Deﬁnition B.13. A relation o n a set S is a subset R of the Cartesian product S ×S. In other words,

a relation on S is a set of ordered pairs, where both coordinates of each pair are elements of S.

For example, the subset R = {(a, a) : a ∈ Z} of Z × Z is the relation we call equals. If R

is a r elation on a set S, we usually suppress the set notation and write a ∼ b, read “a is related to

b,” if (a, b) ∈ R. In this case, we often refer to ∼ as the relation instead of the set R. Sometimes

Get *Abstract Algebra* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.