node, or vertex, of the diagram. If x is an immediate predecessor of y, then the
node for y is placed above the node for x and the two nodes are connected by a
straight-line segment.
example 10
Consider `(51, 26) under the relation of set inclusion. This is a partially ordered set,
a restriction of the partially ordered set (`(N), #). The elements of `(51, 26) are
[, 516, 526, and 51, 26. The binary relation # consists of the following ordered
pairs:
([, [), (516, 516), (526, 526), (51, 26, 51, 26), ([, 516),
([, 526), ([, 51, 26), (516, 51, 26), (526, 51, 26)
The Hasse diagram of this partially ordered set appears in Figure 5.2. Note that
although [ is not an immediate predecessor of 51, 26, it is a predecessor of 51, 26
(shown in the diagram by the chain of upward line segments connecting [ with
51, 26).
PRaCtiCe 9 Draw the Hasse diagram for the relation “x divides y” on 51, 2, 3, 6, 12, 186.
■
RemInDeR
Two nodes in a Hasse
diagram should never be
joined by a horizontal line.
Figure 5.2
{1}
{1, 2}
{2}
Ø
The Hasse diagram of a partially ordered set conveys all the information
about the partial ordering. We can reconstruct the set of ordered pairs making up
the partial ordering just by looking at the diagram. The lines in the diagram tell
us immediate (predecessor, successor) pairs. We can fill in the rest by using the
reflexive and transitive properties. Thus, given the Hasse diagram in Figure 5.3 of
a partial ordering d on a set 5a, b, c, d, e, f 6, we can conclude that d is the set
5(a, a), (b, b), (c, c), (d, d ), (e, e), ( f, f ), (a, b), (a, c), (a, d ), (a, e), (d, e)6
Section 5.1 Relations
337
b
c
e
d
a
f
Figure 5.3