Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 14] ORDERED SETS AND LATTICES 339

EXAMPLE 14.2

(a) Consider the setNof positive integers ordered by divisibility. Then 21 and 7 are comparable since 7|21.

On the other hand, 3 and 5 are noncomparable since neither 3|5 nor 5|3. ThusNis not linearly ordered by

divisibility. Observe thatA={ 2 , 6 , 12 , 36 }is a linearly ordered subset ofNsince 2|6, 6|12 and 12|36.

(b) The setNof positive integers with the usual order≤(less than or equal) is linearly ordered and hence every

ordered subset ofNis also linearly ordered.

(c) The power setP (A)of a setAwith two or more elements is not linearly ordered by set inclusion. For

instance, supposeaandbbelong toA. Then{a}and{b}are noncomparable. Observe that the empty set
,

{a}, andAdo form a linearly ordered subset ofP (A)since
⊆{a}⊆A. Similarly,
,{b}, andAform a

linearly ordered subset ofP (A).

Product Sets and Order

There are a number of ways to define an order relation on the Cartesian product of given ordered sets. Two

of these ways follow:

(a)Product Order: SupposeSandTare ordered sets. Then the following is an order relation on the product
setS×T, called theproduct order:

(a, b)
(a′,b′) if a≤a′andb≤b′

(b)Lexicographical Order: SupposeSandTare linearly ordered sets. Then the following is an order relation
on the product setS×T, called thelexicographicalordictionary order:

(a, b)≺(a′,b′) if a<b or if a=a′andb<b′

This order can be extended toS 1 ×S 2 ×···×Snas follows:

(a 1 ,a 2 ,...,an)≺(a′ 1 ,a′ 2 ,...,an′) if ai=a′ifori= 1 , 2 ,...,k−1 andak<ak′

Note that the lexicographical order is also linear.

Kleene Closure and Order

LetAbe a (nonempty) linearly ordered alphabet. Recall thatA∗, called the Kleene closure ofA, consists of
all wordswonA, and|w|denotes the length ofw. Then the following are two order relations onA∗.

(a)Alphabetical (Lexicographical) Order: The reader is no doubt familiar with the usual alphabetical ordering
ofA∗. That is:

(i) λ<w, whereλis the empty word andwis any nonempty word.

(ii) Supposeu=au′andv=bv′are distinct nonempty words wherea,b∈Aandu′,v′∈A∗. Then

u≺v ifa<b or ifa=bbutu′≺v′

(b)Short-lex Order: HereA∗is ordered first by length, and then alphabetically. That is, for any distinct words
u,vinA∗,
u≺v if|u|<|v| or if|u|=|v|butuprecedesvalphabetically
For example, “to” precedes “and” since|to|=2 but|and|=3. However, “an” precedes “to” since they have
the same length, but “an” precedes “to” alphabetically. This order is also called thefree semigroup order.