The Well-Ordering Principle 561
An e le ment a A is a least or smallest e le ment in A if a a
for all a
A.
It is important to note the difference betwe en a lower bound and a smallest element. The integer
2 is a lower bound for N, but is not a smallest element in N since it is no t an element of N.
Every smallest element in a set is also a lower boun d for the set. However, not every set is bounded
below or contains a least element. For example, the set of even integers is not bounded below. In
addition, a set can be bounded below but not contain a least eleme nt. For example, the open interval
(0, 1) = {x R : 0 < x < 1} is bounded be low by 0 but doe s does not have a smallest element
(since there is n o smallest positive real number).
We have one more step before stating the Well-Or dering Principle.
Deﬁnition B.17. A totally ordered set S is well-ordered if every nonempty subset A of S contains
a least element.
We can now formally state the Well-Ordering Principle.
Axiom B.1 8 (The Well-O rdering Principle). Eve ry nonempty subset of Z that is bounded below is
well-ordered.
The Well-Ordering Principle is often stated within the speciﬁc context of the natural number s,
where it implies that every nonem pty subset o f N contains a smallest element. Our version is some-
what m ore general and is equivalent to th e following:
Axiom B.19 (The Well-Ordering Principle). Every nonempty subset of Z that is bounded below
contains a smallest element.
Note that, in general, a set c a n have a smallest elemen t without being well-ordered . Consider, for
example, the set R
of all nonnegative real numbers. Note that R
has a smallest elem ent—namely,
0—but is not well-orde red, since it contains a none mpty subset (the positive reals, for example) that
does not have a sma llest element. The equ ivalence of the two f orms of the Well-Ordering Principle,
as we have stated them, stems from the fact that both are universally quantiﬁed—that is, both refer to
every nonempty subset of Z that is bounded below. The ﬁrst is really saying that if S is a none mpty
subset of Z that is bounded below, then every nonemp ty subset of S contains a smallest element.
But a nonempty subset of S is still a nonempty subset of Z that is bounded below. For this reason ,
the seco nd version of the Well-Ordering Principle is equivalent to the ﬁrst.
As an example of the use of th e We ll-Ordering Prin ciple, we w ill prove the following th eorem,
which we also proved in Investigation 4 as part of the Fundamental Theo rem of Arithmetic. (See
page 35.)
Theorem. Every in teger greater than 1 is either prime or can b e facto red into a product of primes.
Proof. To use the Well-Ordering Principle, we need to deﬁne a nonempty subset of Z that is bo unded
below. To do so, we will proceed by contradiction and assume that the re is an integer greater than 1
that is no t prim e and cannot be written as a product of primes. Let
S = {n N : n is not prime and cannot be written as a product o f primes}.
Then S is nonempty by hypothesis and is bounded below (b y 1). The Well-Ordering Princip le tells
us that S conta ins a smallest element m. By deﬁnition, m is not prime, so there exist integers a and
b with 1 < a, b < m such that m = ab. Since m is the smallest element in S, it follows that a and
b are not in S. Thus, a and b are either prime or can be written as a produ c t of primes. Therefore,
there exist positive integer s r and s and primes p
1
, p
2
, . . ., p
r
and q
1
, q
2
, . . ., q
s
such that
a = p
1
p
2
···p
r
and b = q
1
q
2
···q
s
.

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.