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

340 ORDERED SETS AND LATTICES [CHAP. 14

14.3Hasse Diagrams of Partially Ordered Sets

LetSbe a partially ordered set, and supposea,bbelong toS. We say thatais animmediate predecessorof
b, or thatbis animmediate successorofa, or thatbis acoverofa, written

a/b

ifa<bbut no element inSlies betweenaandb, that is, there exists no elementcinSsuch thata<c<b.
SupposeSis a finite partially ordered set. Then the order onSis completely known once we know all pairs
a,binSsuch thata/b, that is, once we know the relation/onS. This follows from the fact thatx<yif
and only ifx/yor there exist elementsa 1 ,a 2 ,...,aminSsuch that

x/a 1 /a 2 /···/am/y

TheHasse diagramof a finite partially ordered setSis the directed graph whose vertices are the elements
ofSand there is a directed edge fromatobwhenevera/binS. (Instead of drawing an arrow fromatob,
we sometimes placebhigher thanaand draw a line between them. It is then understood that movement upwards
indicates succession.) In the diagram thus created, there is a directed edge from vertexxto vertexyif and only
ifx/y. Also, there can be no (directed) cycles in the diagram ofSsince the order relation is antisymmetric.
The Hasse diagram of a posetSis a picture ofS; hence it is very useful in describing types of elements
inS. Sometimes we define a partially ordered set by simply presenting its Hasse diagram. We note that the Hasse
diagram of a posetSneed not be connected.

Remark:The Hasse diagram of a finite posetSturns out to be a directed cycle-free graph (DAG) studied in

Section 9.9. The investigation here is independent of the previous investigation. Here we mainly think of order

in terms of “less than” or “greater than” rather than in terms of directed adjacency relations. Accordingly, there

will be some overlap in the content.

EXAMPLE 14.3

(a) LetA={ 1 , 2 , 3 , 4 , 6 , 8 , 9 , 12 , 18 , 24 }be ordered by the relation “xdividesy.” The diagram ofAis given

in Fig. 14-1(a). (Unlike rooted trees, the direction of a line in the diagram of a poset is always upward.)

(b) LetB={a, b, c, d, e}. The diagram in Fig. 14-1(b)defines a partial order onBin the natural way. That is,

d≤b,d≤a,e≤candsoon.

(c) The diagram of a finite linearly ordered set, i.e., a finite chain, consists simply of one path. For example,

Fig. 14-1(c)shows the diagram of a chain with five elements.

Fig. 14-1