Page 644 - Discrete Mathematics and Its Applications

9.6 Partial Orderings 623

4 4 4

3 3 3

2 2 2

1 1 1
(a) (b) (c)

FIGURE 2 Constructing the Hasse Diagram
for ({1, 2, 3, 4}, ≤).

its initial vertex is below its terminal vertex (as it is drawn on paper). Remove all the arrows on
the directed edges, because all edges point “upward” toward their terminal vertex.
These steps are well defined, and only a finite number of steps need to be carried out for
a finite poset. When all the steps have been taken, the resulting diagram contains sufficient
information to find the partial ordering, as we will explain later. The resulting diagram is called
theHassediagramof(S, ),namedafterthetwentieth-centuryGermanmathematicianHelmut
Hasse who made extensive use of them.
Let (S, ) be a poset. We say that an element y ∈ S covers an element x ∈ S if x ≺ y
and there is no element z ∈ S such that x ≺ z ≺ y. The set of pairs (x, y) such that y
covers x is called the covering relation of (S, ). From the description of the Hasse diagram of
a poset, we see that the edges in the Hasse diagram of (S, ) are upwardly pointing edges cor-
responding to the pairs in the covering relation of (S, ). Furthermore, we can recover a poset
from its covering relation, because it is the reflexive transitive closure of its covering relation.
(Exercise 31 asks for a proof of this fact.) This tells us that we can construct a partial ordering
from its Hasse diagram.

EXAMPLE 12 Draw the Hasse diagram representing the partial ordering {(a, b)|a divides b} on
{1, 2, 3, 4, 6, 8, 12}.

Solution: Begin with the digraph for this partial order, as shown in Figure 3(a). Remove all
loops, as shown in Figure 3(b). Then delete all the edges implied by the transitive property.
These are (1, 4), (1, 6), (1, 8), (1, 12), (2, 8), (2, 12), and (3, 12). Arrange all edges to point
upward, and delete all arrows to obtain the Hasse diagram. The resulting Hasse diagram is shown
in Figure 3(c). ▲

EXAMPLE 13 Draw the Hasse diagram for the partial ordering {(A, B) | A ⊆ B} on the power set P(S) where
S ={a, b, c}.

HELMUT HASSE (1898–1979) Helmut Hasse was born in Kassel, Germany. He served in the German
navy after high school. He began his university studies at Göttingen University in 1918, moving in 1920 to
Marburg University to study under the number theorist Kurt Hensel. During this time, Hasse made fundamental
contributions to algebraic number theory. He became Hensel’s successor at Marburg, later becoming director
of the famous mathematical institute at Göttingen in 1934, and took a position at Hamburg University in 1950.
Hasse served for 50 years as an editor of Crelle’s Journal, a famous German mathematics periodical, taking over
the job of chief editor in 1936 when the Nazis forced Hensel to resign. During World War II Hasse worked on
applied mathematics research for the German navy. He was noted for the clarity and personal style of his lectures
and was devoted both to number theory and to his students. (Hasse has been controversial for connections with
the Nazi party. Investigations have shown he was a strong German nationalist but not an ardent Nazi.)