Lecture 25 — Partial Order Relations
Antisymmetry, comparable elements, partial and total orders, and Hasse diagrams. Pre-work: Video 032 (Partial Order Relations). The new property is collected in antisymmetric-relations, comparable elements and the two kinds of order in partial-order-relations, and the simplified drawing in hasse-diagrams. The note starts with two questions left over from 2026-09-21-equivalence-relations.
Goals
- Understand antisymmetry, comparable, partial order, total order in the context of relations.
- Learn how to prove a relation is antisymmetric.
- Learn how to prove a relation is a partial/total order.
- Learn how to draw a Hasse diagram.
Two things to have straight before starting:
- Antisymmetric does not mean “not symmetric”. A relation can be both, either one, or neither. Symmetric against antisymmetric has one of each.
- \(2 \mid 6\) is a statement. “2 divides 6” is true or false. It is not a number, and in particular it is not the fraction \(\frac26\) (divisibility-and-factorisation). The relation “divides” is the subject of a worked proof below.
Two questions carried over from Lecture 24
The classes of \(\sigma\)
The relation \(\sigma\) on \(\mathbb{Z}\) defined by \(m \mathrel{\sigma} n \leftrightarrow (8 \text{ divides } m - n) \text{ or } (8 \text{ divides } m + n)\) is an equivalence relation. Describe the equivalence classes of \(\sigma\).
Work out one class at a time, starting from the definition of a class:
\[\begin{aligned} [1] &= \{n \in \mathbb{Z} : 8 \mid (1 - n) \text{ or } 8 \mid (1 + n)\} \\ &= \{n \in \mathbb{Z} : n \equiv 1 \text{ or } 7 \pmod 8\} && = [7] \\[4pt] [2] &= \{n \in \mathbb{Z} : 8 \mid (2 - n) \text{ or } 8 \mid (2 + n)\} \\ &= \{n \in \mathbb{Z} : n \equiv 2 \text{ or } 6 \pmod 8\} && = [6] \\[4pt] [3] &= \{n \in \mathbb{Z} : n \equiv 3 \text{ or } 5 \pmod 8\} && = [5] \\[4pt] [4] &= \{n \in \mathbb{Z} : 8 \mid (4 - n) \text{ or } 8 \mid (4 + n)\} \\ &= \{n \in \mathbb{Z} : n \equiv 4 \pmod 8\} \\[4pt] [0] &= \{n \in \mathbb{Z} : n \equiv 0 \pmod 8\} \end{aligned}\]
For example 1, 9, 7 and 17 are four elements of \([1]\).
So \(\sigma\) has five classes. The reason:
- \(8 \mid (a - n)\) says \(n \equiv a \pmod 8\), and \(8 \mid (a + n)\) says \(n \equiv -a \pmod 8\). So \([a]\) collects the integers congruent to \(a\) together with the integers congruent to \(-a\).
- Mod 8, \(-1 \equiv 7\), \(-2 \equiv 6\) and \(-3 \equiv 5\), which joins the remainders in pairs.
- But \(-4 \equiv 4\) and \(-0 \equiv 0\), so \([4]\) and \([0]\) get nothing extra.
Every integer has exactly one remainder from 0 to 7, so every integer is in exactly one of the five classes, as it must be.
Figure 1: The eight remainders mod 8 on a clock face. Congruence mod 8 on its own has eight classes, one for each remainder. The relation \(\sigma\) also relates \(n\) to everything congruent to \(-n\), and replacing a remainder by its negative is the left-to-right flip of the clock. So each remainder is joined to its mirror image: 1 with 7, 2 with 6, 3 with 5. The remainders 0 and 4 lie on the mirror line and are their own images. That leaves five classes.
The proof that \(\sigma\) is an equivalence relation is in 2026-09-21-equivalence-relations.
A relation for the partition by sign
Any partition defines an equivalence relation: two elements are related if and only if they are in the same part (2026-09-21-equivalence-relations).
Consider the partition of the integers given by \(\{\mathbb{Z}^{-}, \{0\}, \mathbb{Z}^{+}\}\). Describe an equivalence relation that corresponds to this partition.
Define \(\tau\) by: for all \(a, b \in \mathbb{Z}\),
\[a \mathrel{\tau} b \ \longleftrightarrow\ a, b \text{ both positive} \quad\text{or}\quad a = b = 0 \quad\text{or}\quad a, b \text{ both negative}.\]
The condition has one alternative for each part. The middle part has one element, so “both in \(\{0\}\)” becomes \(a = b = 0\).
Figure 2: The partition \({\mathbb{Z}^{-}, {0}, \mathbb{Z}^{+}}\) of the integers, shown from \(-5\) to 5, and the relation it defines. Two integers are related exactly when they have the same colour. So \(-4 \mathrel{\tau} -1\) and \(2 \mathrel{\tau} 5\), the only thing related to 0 is 0, and no negative integer is related to a positive one.
Antisymmetry
Definition. A relation \(R\) on a set \(S\) is antisymmetric if and only if \[\forall a, b \in S,\ (a \mathrel{R} b \text{ and } b \mathrel{R} a) \to (a = b).\]
There are two equivalent ways to write it:
\[\forall a, b \in S,\ (a \neq b) \to {\sim}(a \mathrel{R} b \text{ and } b \mathrel{R} a)\]
\[\forall a, b \in S,\ (a \mathrel{R} b \text{ and } a \neq b) \to {\sim}(b \mathrel{R} a)\]
The first form is the easiest for proving a relation antisymmetric. The third is the most intuitive.
All three say the same thing about the arrow diagram: there is no pair of different elements with arrows both ways.
- The first reads it as “if you do find arrows both ways, the two ends were the same element all along”, so the pair of arrows is really one loop.
- The third reads it as “an arrow from \(a\) to a different element \(b\) has no return”.
- Loops are not restricted at all.
Figure 3: Antisymmetry in two pictures. Left, the first definition: arrows both ways between \(a\) and \(b\) are only possible if \(a\) and \(b\) are the same element, in which case the picture is a single dot with a loop. This is the form to use in a proof. Right, the third definition: an arrow from \(a\) to a different element \(b\) rules out the arrow back from \(b\) to \(a\). This is the form to picture.
Examples.
- \(\leq\) on \(\mathbb{R}\) is antisymmetric: for all \(x, y \in \mathbb{R}\), \((x \leq y \text{ and } y \leq x) \to (x = y)\).
- So are \(<\), \(>\) and \(\geq\) on \(\mathbb{R}\).
- “Divides” is antisymmetric on \(\mathbb{Z}^{+}\). It is proved below.
- \(\subseteq\) on any set \(S\) of sets is antisymmetric: for all \(X, Y \in S\), \((X \subseteq Y \text{ and } Y \subseteq X) \to (X = Y)\). This is the double-containment rule for showing two sets are equal (sets-and-set-notation).
Why \(<\) counts, and why “divides” needs \(\mathbb{Z}^{+}\) and not \(\mathbb{Z}\), are in antisymmetric-relations.
Worked: symmetric against antisymmetric
Symmetric says every arrow has a return: \(\forall a, b \in A,\ a \mathrel{\rho} b \to b \mathrel{\rho} a\). Antisymmetric says no arrow between different elements has one: \(\forall a, b \in S,\ (a \mathrel{R} b \text{ and } b \mathrel{R} a) \to (a = b)\).
Match each of the four arrow diagrams with the description of its relation.
A. Both symmetric and antisymmetric
B. Symmetric but not antisymmetric
C. Antisymmetric but not symmetric
D. Neither symmetric nor antisymmetric
Each diagram has three dots.
| The arrows | Answer | Why | |
|---|---|---|---|
| Diagram 1 | both ways between the first and second dots; one arrow from the second to the third; a loop at the third | D | the two-way pair joins different elements, so not antisymmetric; the single arrow has no return, so not symmetric |
| Diagram 2 | a loop at each of two dots; the third dot has no arrows | A | the only arrows are loops, which break neither property |
| Diagram 3 | both ways between the first and second dots, and both ways between the second and third; a loop at the third | B | every arrow has a return, so symmetric; the two-way pairs join different elements, so not antisymmetric |
| Diagram 4 | one arrow from the first dot to the second, and one from the second to the third; a loop at the third | C | neither single arrow has a return, so not symmetric; there is no two-way pair, so antisymmetric |
Diagram 2 is the one that shows antisymmetric is not the opposite of symmetric. Its only arrows are loops. A loop is its own return, so the relation is symmetric. There are no arrows between different elements, so nothing can break antisymmetry.
Figure 4: Four relations on three points, with their answers. Between two different dots there are three possibilities: no arrow, one arrow, or arrows both ways. A single arrow breaks symmetry, and arrows both ways break antisymmetry. Diagram 1 has one of each, the single arrow shaded cyan and the two-way pair yellow, so it is neither. Diagram 2 has no arrows between different dots, so it is both. Diagram 3 has only two-way pairs, so it is symmetric and not antisymmetric. Diagram 4 has only single arrows, so it is antisymmetric and not symmetric. The loops play no part in any of the four answers.
Comparable and non-comparable elements
If \(R\) is a relation on a set \(S\), then two elements \(a, b \in S\) are comparable if and only if \(a \mathrel{R} b\) or \(b \mathrel{R} a\).
Comparable means related in some direction.
Example. A relation \(R\) on six points \(a\) to \(f\), with arrows \(a \to c\) and \(c \to a\), \(c \to e\), \(b \to a\), \(b \to e\), \(f \to b\), \(b \to d\), and loops at \(b\) and at \(e\):
| Comparable | Noncomparable |
|---|---|
| \(a\) and \(c\) | \(a\) and \(e\) |
| \(a\) and \(b\) | \(a\) and \(d\) |
| \(c\) and \(e\) | \(a\) and \(f\) |
| \(b\) and \(e\) | \(b\) and \(c\) |
| \(b\) and \(d\) | \(c\) and \(d\) |
| \(b\) and \(f\) | \(c\) and \(f\) |
| \(d\) and \(e\) | |
| \(b\) and \(b\) | \(d\) and \(f\) |
| \(e\) and \(e\) | \(e\) and \(f\) |
What the two columns show:
- Direction does not matter. \(a\) and \(b\) are comparable because of the arrow \(b \to a\). One arrow either way is enough.
- Comparable means one arrow, not a path. \(a\) and \(e\) are noncomparable although \(a \to c \to e\) is a path, because there is no arrow between them. This \(R\) is not transitive.
- An element is comparable with itself only if it has a loop. Only \(b\) and \(e\) are comparable with themselves.
- The 15 pairs of different points split 6 and 9.
This \(R\) is not a partial order: \(a\) and \(c\) are joined both ways, and four points have no loop. The definition of comparable does not need one.
Figure 5: The relation \(R\) on six points, with three pairs highlighted. \(c\) and \(e\), in yellow, are comparable: there is an arrow \(c \to e\). \(b\) is comparable with itself, since it has a loop. \(a\) and \(d\), in cyan, are not comparable: no arrow joins them in either direction. Two points are comparable when at least one arrow joins them, whichever way it points.
Worked: comparable sets
In the partial order relation defined on the power set \(\mathcal{P}(\mathbb{Z})\) of \(\mathbb{Z}\) by \(X \mathrel{\rho} Y\) iff \(X \subseteq Y\), which of the following are comparable elements?
| Answer | Why | ||
|---|---|---|---|
| (a) | 7 and 9 | not elements of \(\mathcal{P}(\mathbb{Z})\) | 7 and 9 are integers, not sets of integers, so the relation is not defined on them |
| (b) | \(\{7\}\) and \(\{9\}\) | non-comparable | neither is a subset of the other |
| (c) | \(\{7\}\) and \(\{7,9\}\) | comparable | \(\{7\} \subseteq \{7,9\}\) |
| (d) | \(\{1,2,3\}\) and \(\{1,2,4\}\) | non-comparable | \(3 \notin \{1,2,4\}\) and \(4 \notin \{1,2,3\}\), so neither contains the other |
So the answer is (c). Two traps:
- In (a), the elements of \(\mathcal{P}(\mathbb{Z})\) are sets of integers. That is the element-versus-subset distinction of sets-and-set-notation.
- In (d), the two sets overlap in \(\{1,2\}\). Overlapping is not being comparable.
Partial and total orders
A relation \(R\) on a set \(S\) is a partial order relation if and only if \(R\) is
- reflexive;
- antisymmetric; and
- transitive.
A relation \(R\) on a set \(S\) is a total order relation if and only if \(R\) is
- reflexive;
- antisymmetric;
- transitive; and
- any two elements of \(S\) are comparable.
A total order is a partial order plus condition 4. So:
- Any total order relation is a partial order relation.
- A partial order relation is a total order relation if and only if every two elements are comparable.
As arrow diagrams, a total order is a single column: a loop at each element and an arrow from each element to every element above it. A partial order that is not total has at least one pair of elements with no arrow between them.
Figure 6: Two orders as arrow diagrams. Left, a total order on five elements: a loop at each, and an arrow from each element to every element above it, ten in all. Every two elements are joined by an arrow, so every two are comparable. Right, a partial order that is not total: the same column and a sixth element off to the side, above the bottom element and below the top one. It is joined to nothing else in the column. The two elements shaded cyan are one of the three pairs that are not comparable.
Worked: “divides” is a partial order
(a) Prove that the relation “divides” on \(\mathbb{Z}^{+}\) is a partial order relation.
(b) Is the relation “divides” on \(\mathbb{Z}^{+}\) a total order relation?
Name the relation and unfold it: for all \(a, b \in \mathbb{Z}^{+}\),
\[a \mathrel{\tau} b \leftrightarrow a \mid b \qquad (\text{that is, } b = ak \text{ for some } k \in \mathbb{Z}).\]
(a)
Reflexive. Let \(a \in \mathbb{Z}^{+}\). Since \(a = a \cdot 1\) we have \(a \mid a\), so \(\tau\) is reflexive.
Antisymmetric. Let \(a, b \in \mathbb{Z}^{+}\) and suppose \(a \mathrel{\tau} b\) and \(b \mathrel{\tau} a\). (Goal: show \(a = b\).) Thus \(b = ak\) for some \(k \in \mathbb{Z}\) and \(a = b\ell\) for some \(\ell \in \mathbb{Z}\). \[\text{Now } b = ak = (b\ell)k = b(\ell k), \qquad\text{so}\qquad 1 = \ell k.\] (The \(b\) can be cancelled because \(b \in \mathbb{Z}^{+}\), so \(b \neq 0\).) Note \(\ell > 0\) and \(k > 0\) since \(a, b > 0\). Thus \(\ell = k = 1\), so \(a = b\). \(\therefore \tau\) is antisymmetric.
Transitive. Let \(a, b, c \in \mathbb{Z}^{+}\) and suppose \(a \mathrel{\tau} b\) and \(b \mathrel{\tau} c\). Thus \(b = ak\) and \(c = b\ell\) for some \(k, \ell \in \mathbb{Z}\). Hence \(c = (ak)\ell = a(k\ell)\). Since \(k\ell \in \mathbb{Z}\) we have \(a \mid c\), that is, \(a \mathrel{\tau} c\). So \(\tau\) is transitive.
\(\therefore \tau\) is a partial order.
(b) Not a total order, since \(2 \mathrel{\not\tau} 3\) and \(3 \mathrel{\not\tau} 2\).
Points to notice:
- State the goal. The antisymmetric part begins by writing down where the first form of the definition is heading: show \(a = b\).
- Where \(\mathbb{Z}^{+}\) is needed. The step from \(\ell k = 1\) to \(\ell = k = 1\) uses that both are positive. On all of \(\mathbb{Z}\), \(\ell = k = -1\) is also possible, and the proof fails (antisymmetric-relations).
- One pair is enough for (b). \(2 \nmid 3\) and \(3 \nmid 2\), so 2 and 3 are not comparable. “Any two elements are comparable” is a “for all”, and one pair that fails disproves it.
- The set matters. On \(\{1, 2, 4, 8, 16\}\) each number divides the next, every two are comparable, and “divides” is a total order there.
Hasse diagrams
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;
- deleting the loops (the arrows from elements to themselves);
- deleting the arrows which are implied by the transitive property;
- deleting the direction indicators on the arrows.
A Hasse diagram is sufficient to define a partial order relation.
Example. The six-element partial order of Figure 6, with the column named \(a\), \(b\), \(c\), \(d\), \(e\) from the bottom and \(f\) at the side. The arrow \(a \to c\) is implied by \(a \to b\) and \(b \to c\), so it is one that step 3 deletes. What is left at the end is \(a\), \(b\), \(c\), \(d\), \(e\) in a vertical line joined by four segments, and \(f\) joined to \(a\) and to \(e\).
Figure 7: The four steps on a six-element partial order. First: the arrow diagram, already arranged so that every arrow points upward. It has 18 arrows. Second: the six loops are deleted, leaving 12. The six arrows that the transitive property implies are drawn in grey: each of them skips over at least one element of the column. Third: those are deleted, leaving six arrows, each from an element to one directly above it. Fourth: the arrowheads are deleted, since every line is understood to point up. What is left is the Hasse diagram.
Nothing is lost by the deleting. The removed arrows can all be put back, because the steps only take away what the three properties guarantee (hasse-diagrams).
Worked: the Hasse diagram of a power set
Draw a Hasse diagram for the partial order relation \(\subseteq\) on \(\mathcal{P}(\{1,2,3\})\).
\(\emptyset\) goes at the bottom, then \(\{1\}\), \(\{2\}\), \(\{3\}\), then \(\{1,2\}\), \(\{1,3\}\), \(\{2,3\}\), and \(\{1,2,3\}\) at the top, joined by twelve lines. The shape is a cube standing on one corner.
Figure 8: The Hasse diagram of \(\subseteq\) on \(\mathcal{P}({1,2,3})\). Each line joins a set to a set with exactly one more element. One set is a subset of another exactly when there is a path from the first up to the second, so \({1} \subseteq {1,2,3}\) by way of \({1,2}\) or \({1,3}\). Sets on the same level are never comparable. The twelve lines are the edges of a cube.
The arrow diagram of proper subset on the same eight sets has 19 arrows (2026-09-17-relations-reflexivity-symmetry-transitivity). The relation \(\subseteq\) has those 19 and a loop at each of the 8 sets, 27 arrows in all. The Hasse diagram keeps 12 of them: the ones that add a single element.
See also
- antisymmetric-relations — the three equivalent definitions, and symmetric against antisymmetric
- partial-order-relations — comparable elements, partial and total orders, and the proof template
- hasse-diagrams — drawing one, and reading the relation back off it
- equivalence-classes-and-partitions — classes and partitions, for the two questions at the start
- divisibility-and-factorisation — the definition of “divides”
- 2026-09-21-equivalence-relations — Lecture 24 · 2026-09-24-definitions-and-examples-of-groups — Lecture 26
- practice-problems — §32, with full worked solutions