Hasse Diagrams
The arrow diagram of a partial order carries a lot of arrows that the three properties already guarantee. A Hasse diagram leaves those out and keeps only what cannot be worked out. Partial orders are in partial-order-relations, and arrow diagrams in relations-on-sets. First met in 2026-09-22-partial-order-relations.
The four steps
A Hasse diagram for a partial order relation is obtained from its arrow diagram by:-
- placing the elements so that all the arrows point upwards.
- delete the loops (the arrows from elements to themselves).
- delete the arrows which are implied by the transitive property.
- delete the direction indicators on the arrows.
A Hasse diagram is sufficient to define a partial order relation.
The relation has to be a partial order. Each step leans on its properties, and that is why nothing is lost:
| Step | Why it is safe |
|---|---|
| 1. arrows point up | Needs antisymmetric and transitive together. If arrows led from an element round through others and back to it, transitivity would join two of them both ways, and antisymmetry forbids that. With no such round trips, the elements can be arranged so that every arrow climbs. |
| 2. delete the loops | The relation is reflexive, so every element has a loop. Drawing them says nothing. |
| 3. delete the implied arrows | The relation is transitive, so an arrow \(x \to z\) that follows from \(x \to y\) and \(y \to z\) can be put back. |
| 4. delete the arrowheads | After step 1, every line points up. |
A six-element example is worked step by step in 2026-09-22-partial-order-relations.
Step 3 in practice: delete \(x \to z\) whenever there is some other element \(y\) with \(x \to y\) and \(y \to z\). What survives are the arrows from an element to one directly above it, with nothing in between.
Worked: divides on \(\{1, 2, \dots, 6\}\)
The arrow diagram of \(x \mid y\) on \(\{1,\dots,6\}\) is drawn in reflexive-symmetric-and-transitive-relations, already arranged with every arrow pointing up. It has 14 arrows.
- Arrows point up. Put 1 at the bottom, since it divides everything. Above it go 2, 3 and 5, and above them 4 and 6.
- Delete the loops. Six go, leaving eight: \(1 \to 2\), \(1 \to 3\), \(1 \to 5\), \(2 \to 4\), \(2 \to 6\), \(3 \to 6\), \(1 \to 4\), \(1 \to 6\).
- Delete the implied arrows. \(1 \to 4\) follows from \(1 \to 2 \to 4\), and \(1 \to 6\) follows from \(1 \to 2 \to 6\) (and from \(1 \to 3 \to 6\)). Two go, leaving six.
- Delete the arrowheads.
Figure 1: The relation \(x \mid y\) on \({1, \dots, 6}\), as an arrow diagram and as a Hasse diagram. Left: all 14 arrows. The 8 that the steps delete are grey: the 6 loops, and the arrows \(1 \to 4\) and \(1 \to 6\), which the transitive property implies. Right: the 6 that remain, without arrowheads. A number divides another exactly when a path leads from it up to the other, so \(1 \mid 6\) still shows, by way of 2 or 3. 5 is joined only to 1, since it divides none of the others and only 1 divides it.
Reading a Hasse diagram
A Hasse diagram is sufficient to define the relation: nothing was lost in drawing it. To read the relation back, undo the steps:
\(x \mathrel{R} y\) exactly when \(x = y\), or there is a path from \(x\) to \(y\) that goes upward all the way.
- \(x = y\) restores the loops (step 2).
- A path of one line is an arrow that was kept.
- A path of two or more lines restores an implied arrow (step 3).
- “Upward” restores the direction (step 4).
For the six-element example the count comes back as 6 loops, 6 kept arrows and 6 implied arrows, 18 in all.
The same rule reads off the other notions of partial-order-relations:
- Comparable: two different elements are comparable exactly when an upward path joins them, starting from either one.
- Non-comparable: no upward path either way. Two elements drawn at the same height are never comparable, because every line climbs.
- Total order: the whole diagram is a single column, one element above the other.
A path that goes up and then comes down does not count. In the diagram of \(\subseteq\) on \(\mathcal{P}(\{1,2,3\})\) you can get from \(\{1\}\) to \(\{2,3\}\) along lines, but only by going down at some point. \(\{1\} \not\subseteq \{2,3\}\), and the two are not comparable.
Figure 2: Reading the Hasse diagram of \(\subseteq\) on \(\mathcal{P}({1,2,3})\). The green path climbs at every step, from \({1}\) through \({1,3}\) to \({1,2,3}\), so \({1} \subseteq {1,2,3}\) and the two sets are comparable. The dashed orange path also joins two sets, \({1}\) and \({2,3}\), but it goes up, then down, then up. It does not show a relation. No path from \({1}\) climbs all the way to \({2,3}\), and none climbs from \({2,3}\) to \({1}\), so those two sets are not comparable.
The diagrams in the course so far
| Partial order | Its Hasse diagram | Where |
|---|---|---|
| six elements \(a\) to \(f\) | a column \(a, b, c, d, e\) with \(f\) joined to \(a\) and \(e\) | 2026-09-22-partial-order-relations |
| \(\subseteq\) on \(\mathcal{P}(\{1,2,3\})\) | a cube standing on a corner, 12 lines | 2026-09-22-partial-order-relations |
| divides on \(\{1,\dots,6\}\) | 6 lines, above | above |
| divides on \(\{1,2,4,8,16\}\) | a single column | partial-order-relations |
In the power-set diagram each line adds exactly one element to a set. In the divides diagram above each line multiplies by a prime: \(1 \to 2\), \(1 \to 3\), \(1 \to 5\), \(2 \to 4\), \(2 \to 6\), \(3 \to 6\). In both cases a line is a single smallest step up.
Common mistakes
- Keeping an implied line. If \(x\) is joined up to \(y\) and \(y\) up to \(z\), there is no line from \(x\) to \(z\). A triangle in a Hasse diagram is always wrong.
- A horizontal line. Every line has to climb, or the deleted arrowhead cannot be recovered.
- Putting the larger element lower. The relation reads upward. For divides, 1 is at the bottom. For \(\subseteq\), \(\emptyset\) is.
- Reading only the lines as the relation. The lines are the kept arrows. The relation also contains every loop and every implied arrow.
- Drawing one for a relation that is not a partial order. If two different elements are related both ways, step 1 cannot be done.
- Treating any path as a comparison. The path must go upward at every step.
See also
- partial-order-relations — partial and total orders, and comparable elements
- antisymmetric-relations — the property that lets the arrows all point one way
- relations-on-sets — the full arrow diagram a Hasse diagram is cut down from
- reflexive-symmetric-and-transitive-relations — loops and short cuts, the arrows steps 2 and 3 delete
- 2026-09-22-partial-order-relations — Lecture 25
- practice-problems — §32, with full worked solutions