Sets and relations · Definition

Hasse diagram

discrete mathematicsrelations

Before you start you need to know

It shows the structure of a partial order at a glance, without cluttering the picture with redundant arrows.

Definition

A Hasse diagram draws a partially ordered set \((S,\preceq)\) with one point per element and an edge only between consecutive elements, placing the smaller one lower.

\[a\ \text{covers}\ b\iff b\prec a\ \wedge\ \nexists\,c:\ b\prec c\prec a\]

A full partial order contains many relations that follow from others: the loops \(a\preceq a\) and the pairs \(a\preceq c\) that come from \(a\preceq b\preceq c\). The Hasse diagram removes them and keeps only the covering pairs, that is, pairs \(b\prec a\) with no element strictly between. By convention the larger element is drawn higher, so no arrows are needed.

To recover the order, read the picture backwards: \(b\preceq a\) exactly when some path climbs from \(b\) to \(a\) along edges. In the divisors of \(12\) under divisibility, the path \(3-6-12\) says \(3\mid 12\), while \(2\) and \(3\) are joined by no upward path, so they are incomparable.

The picture reveals the shape of the order: a total order is a single vertical chain; the divisors of \(30\) form a cube; an element with nothing above it is maximal and one with nothing below it is minimal. A set of elements with no paths between them is an antichain.

A common mistake is joining non-consecutive elements, such as \(1\) with \(4\) in the divisors of \(12\), since \(2\) lies between. Another is thinking that two elements at the same height are comparable: height in the drawing is only a convenience, and what counts are the paths.

Think about it

Which edges does the Hasse diagram of \(\{1,2,3,6\}\) under divisibility have?

Four: \(1-2,\ 1-3,\ 2-6,\ 3-6\). They form a diamond; \(2\) and \(3\) are incomparable.

Exercises 10

  1. In the Hasse diagram of the divisors of \(12\) under divisibility, how many edges are there?
  2. In the Hasse diagram of the divisors of \(30\), how many elements directly cover \(1\)?
  3. In the divisors of \(12\) under divisibility, which pair is an edge of the Hasse diagram?
  4. In \(\{2,3,4,6,8,12\}\) under divisibility, how many maximal elements does the diagram have (nothing above them)?
  5. Why does a Hasse diagram draw no loops and no edges that follow by transitivity?
  6. How many edges does the Hasse diagram of the divisors of \(30\) under divisibility have?
  7. How many edges does the Hasse diagram of \(\{1,2,4,8,16,32\}\) under divisibility have?
  8. In the Hasse diagram of the divisors of \(12\), which pair of elements is comparable (an upward path joins them)?
  9. How many elements does the longest chain in the Hasse diagram of the divisors of \(60\) under divisibility have?
  10. What is the largest set of divisors of \(30\) that are pairwise incomparable (an antichain) under divisibility?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §9.6
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §8.5
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §7.3