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
Letbe any partial ordering of a setS. The relation, that is,asucceedsb, is also a partial ordering ofS;
it is called thedual order. Observe thatabif 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. Defineabas elements ofAwheneverabas
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, ifis a partial order
on a setSand we definea≺bto meanabbuta=b, then≺is a quasi-order onS. Conversely, if≺is a
quasi-order on a setSand we defineabto meana≺bora=b, thenis 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
ab or ba
that is, if one of them precedes the other. Thusaandbarenoncomparable, written
a‖b
if neitherabnorba.
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.