Page 642 - Discrete Mathematics and Its Applications

9.6 Partial Orderings 621

constructed from a partial ordering on the set. We will show how this construction works in any
poset.
First, we will show how to construct a partial ordering on the Cartesian product of two
posets, (A 1 , 1 ) and (A 2 , 2 ). The lexicographic ordering on A 1 × A 2 is defined by
specifying that one pair is less than a second pair if the first entry of the first pair is less than
(in A 1 ) the first entry of the second pair, or if the first entries are equal, but the second entry of
this pair is less than (in A 2 ) the second entry of the second pair. In other words, (a 1 ,a 2 ) is less
than (b 1 ,b 2 ), that is,

(a 1 ,a 2 ) ≺ (b 1 ,b 2 ),

either if a 1 ≺ 1 b 1 or if both a 1 = b 1 and a 2 ≺ 2 b 2 .
We obtain a partial ordering by adding equality to the ordering ≺ on A 1 × A 2 . The
verification of this is left as an exercise.

EXAMPLE 9 Determine whether (3, 5) ≺ (4, 8), whether (3, 8) ≺ (4, 5), and whether (4, 9) ≺ (4, 11) in the
poset (Z × Z, ), where is the lexicographic ordering constructed from the usual ≤ relation
on Z.

Solution: Because 3 < 4, it follows that (3, 5) ≺ (4, 8) and that (3, 8) ≺ (4, 5).We have
(4, 9) ≺ (4, 11), because the first entries of (4, 9) and (4, 11) are the same but 9 < 11. ▲

+
In Figure 1 the ordered pairs in Z × Z + that are less than (3, 4) are highlighted.
A lexicographic ordering can be defined on the Cartesian product of n posets (A 1 , 1 ),
(A 2 , 2 ),...,(A n , n ). Define the partial ordering on A 1 × A 2 × ··· × A n by

(a 1 ,a 2 ,...,a n ) ≺ (b 1 ,b 2 ,...,b n )

if a 1 ≺ 1 b 1 , or if there is an integer i> 0 such that a 1 = b 1 ,...,a i = b i , and a i+1 ≺ i+1 b i+1 .
In other words, one n-tuple is less than a second n-tuple if the entry of the first n-tuple in the
first position where the two n-tuples disagree is less than the entry in that position in the second
n-tuple.

. . . . . . . . . . . . . . . . . . . . .

. . .
(1,7) (2,7) (3,7) (4,7) (5,7) (6,7) (7,7)
. . .
(1,6) (2,6) (3,6) (4,6) (5,6) (6,6) (7,6)
. . .
(1,5) (2,5) (3,5) (4,5) (5,5) (6,5) (7,5)
. . .
(1,4) (2,4) (3,4) (4,4) (5,4) (6,4) (7,4)

. . .
(1,3) (2,3) (3,3) (4,3) (5,3) (6,3) (7,3)
. . .
(1,2) (2,2) (3,2) (4,2) (5,2) (6,2) (7,2)
. . .
(1,1) (2,1) (3,1) (4,1) (5,1) (6,1) (7,1)

FIGURE 1 The Ordered Pairs Less Than (3, 4) in Lexicographic Order.