Hasse Diagram

The Hasse diagram is a special graph for the intuitive representation of partial orders. Its purpose is to simply show which elements are directly related to each other in the ordering.

Definition

The Hasse diagram of a partially ordered set (A, ≤) is a graph in which:

• The elements of the set appear as vertices.
• If a ≤ b, then in the graph, the vertex a is placed below b.
• We draw an edge only if a ≤ b is true, but there is no intermediate c element for which a ≤ c and c ≤ b (i.e., there is a direct connection between a and b).
• The edges are drawn upwards from lower to higher elements.

How to Construct a Hasse Diagram

• Place the minimal elements (those with no smaller elements) at the bottom.
• Place maximal elements (those with no larger elements) at the top.
• Draw directed edges (usually upward) only for covering relations (direct successors).
• Arrange vertices so that the order is visually clear, with no crossing edges if possible.

Example

Let A = {1,2,3,6}, with the divisibility relation (|).

The partial order: 1 | 2, 1 | 3, 2 | 6, 3 | 6.

The Hasse diagram: 1 at the bottom, above it 2 and 3 (parallel), and 6 at the top connected to both 2 and 3.

Properties

• The Hasse diagram is always a directed acyclic graph (DAG).
• Reflexive edges (a → a) are not represented.
• Transitive connections (if a ≤ b and b ≤ c, then a ≤ c) are not drawn separately, as edges only show direct connections.
• The Hasse diagram makes the hierarchy of the partial order easily visible.

Summary

Using the Hasse diagram, we can represent a partial order in a simple and overviewable way. It only shows direct connections, omitting reflexive and transitive edges. This makes the hierarchy of the set's elements easily visible.

Practice Exercise