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 verified 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
find 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 find 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 first 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 definition of a relation
on a set follows this example.
Definition 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.