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.