Page 641 - Discrete Mathematics and Its Applications

620 9 / Relations

EXAMPLE 6 The poset (Z, ≤) is totally ordered, because a ≤ b or b ≤ a whenever a and b are integers. ▲

EXAMPLE 7 The poset (Z , | ) is not totally ordered because it contains elements that are incomparable, such
+
as 5 and 7. ▲

In Chapter 6 we noted that (Z , ≤) is well-ordered, where ≤ is the usual “less than or equal
+
to” relation. We now define well-ordered sets.

DEFINITION 4 (S, ) is a well-ordered set if it is a poset such that is a total ordering and every nonempty
subset of S has a least element.

+
EXAMPLE 8 The set of ordered pairs of positive integers, Z × Z , with (a 1 ,a 2 ) (b 1 ,b 2 ) if a 1 <b 1 ,orif
+
a 1 = b 1 and a 2 ≤ b 2 (the lexicographic ordering), is a well-ordered set. The verification of this
is left as Exercise 53. The set Z, with the usual ≤ ordering, is not well-ordered because the set
of negative integers, which is a subset of Z, has no least element. ▲

At the end of Section 5.3 we showed how to use the principle of well-ordered induction
(there called generalized induction) to prove results about a well-ordered set. We now state and
prove that this proof technique is valid.

THEOREM 1 THE PRINCIPLE OF WELL-ORDERED INDUCTION Suppose that S is a well-
ordered set. Then P(x) is true for all x ∈ S,if
INDUCTIVE STEP: For every y ∈ S,if P(x) is true for all x ∈ S with x ≺ y, then P(y)
is true.

Proof: Suppose it is not the case that P(x) is true for all x ∈ S. Then there is an element
y ∈ S such that P(y) is false. Consequently, the set A ={x ∈ S | P(x) is false} is nonempty.
Because S is well ordered, A has a least element a. By the choice of a as a least element of A,
we know that P(x) is true for all x ∈ S with x ≺ a. This implies by the inductive step P(a) is
true. This contradiction shows that P(x) must be true for all x ∈ S.

Remark: We do not need a basis step in a proof using the principle of well-ordered induction
because if x 0 is the least element of a well ordered set, the inductive step tells us that P(x 0 )
is true. This follows because there are no elements x ∈ S with x ≺ x 0 , so we know (using a
vacuous proof) that P(x) is true for all x ∈ S with x ≺ x 0 .

The principle of well-ordered induction is a versatile technique for proving results about
well-ordered sets. Even when it is possible to use mathematical induction for the set of positive
integers to prove a theorem, it may be simpler to use the principle of well-ordered induction, as
we saw in Examples 5 and 6 in Section 6.2, where we proved a result about the well-ordered
set (N × N, ) where is lexicographic ordering on N × N.

Lexicographic Order

The words in a dictionary are listed in alphabetic, or lexicographic, order, which is based on the
ordering of the letters in the alphabet. This is a special case of an ordering of strings on a set