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

338 ORDERED SETS AND LATTICES [CHAP. 14

EXAMPLE 14.1

(a) LetSbe any collection of sets. The relation⊆of set inclusion is a partial ordering ofS. Specifically,A⊆A

for any setA;ifA⊆BandB⊆AthenA=B; and ifA⊆BandB⊆CthenA⊆C.

(b) Consider the setNof positive integers. We say “adividesb,” writtena|b, if there exists an integercsuch

thatac=b. For example, 2|4, 3|12, 7|21, and so on. This relation of divisibility is a partial ordering ofN.

(c) The relation “|” of divisibility is not an ordering of the setZof integers. Specifically, the relation is not

antisymmetric. For instance, 2|−2 and− 2 |2, but 2=−2.

(d) Consider the setZof integers. DefineaRbif there is a positive integerrsuch thatb=ar. For instance, 2R 8

since 8= 23. ThenRis a partial ordering ofZ.

Dual Order

Let
be any partial ordering of a setS. The relation, that is,asucceedsb, is also a partial ordering ofS;

it is called thedual order. Observe thata
bif and only ifba; hence the dual orderis the inverse of the

relation
, that is,=
−^1.

Ordered Subsets

LetAbe a subset of an ordered setS, and supposea,b∈A. Definea
bas elements ofAwhenevera
bas
elements ofS. This defines a partial ordering ofAcalled theinduced orderonA. The subsetAwith the induced
order is called anordered subsetofS. Unless otherwise stated or implied, any subset of an ordered setSwill be
treated as an ordered subset ofS.

Quasi-order

Suppose≺is a relation on a setSsatisfying the following two properties:

[Q 1 ] (Irreflexive) For anya∈A, we havea/≺a.

[Q 2 ] (Transitive) Ifa≺b, andb≺c, thena≺c.

Then≺is called aquasi-orderonS.
There is a close relationship between partial orders and quasi-orders. Specifically, if
is a partial order
on a setSand we definea≺bto meana
bbuta=b, then≺is a quasi-order onS. Conversely, if≺is a
quasi-order on a setSand we definea
bto meana≺bora=b, then
is a partial order onS. This allows
us to switch back and forth between a partial order and its corresponding quasi-orders using whichever is more
convenient.

Comparability, Linearly Ordered Sets

Supposeaandbare elements in a partially ordered setS. We sayaandbarecomparableif

a
b or b
a

that is, if one of them precedes the other. Thusaandbarenoncomparable, written

a‖b

if neithera
bnorb
a.
Theword“partial” is used in defining a partially ordered setSsince some of the elements ofSneed not be
comparable. Suppose, on the other hand, that every pair of elements ofSare comparable. ThenSis said to be
totally orderedorlinearly ordered, andSis called achain.Although an ordered setSmay not be linearly ordered,
it is still possible for a subsetAofSto be linearly ordered. Clearly, every subset of a linearly ordered setSmust
also be linearly ordered.