Partial Order Relations
A partial order is a relation that ranks the elements of a set: it is reflexive, antisymmetric and transitive. If in addition every two elements can be compared, it is a total order. The property that is new here is in antisymmetric-relations, and the picture of a partial order is its Hasse diagram. First met in 2026-09-22-partial-order-relations.
The definitions
A relation \(R\) on a set \(S\) is a partial order relation if and only if \(R\) is
- Reflexive;
- Antisymmetric; and
- Transitive.
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\).
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.
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.
The model is \(\leq\) on numbers, and it helps to read \(a \mathrel{R} b\) as “\(a\) is below or equal to \(b\)”. Partial refers to condition 4 being absent. In a partial order some pairs may not be ranked against each other at all. Partial does not mean “not total”: a total order is a partial order that happens to rank every pair.
Comparable elements
Two elements are comparable when they are related in some direction. They are non-comparable when neither \(a \mathrel{R} b\) nor \(b \mathrel{R} a\) holds.
| Relation | Comparable | Non-comparable |
|---|---|---|
| \(\subseteq\) on \(\mathcal{P}(\mathbb{Z})\) | \(\{7\}\) and \(\{7,9\}\) | \(\{7\}\) and \(\{9\}\); \(\{1,2,3\}\) and \(\{1,2,4\}\) |
| divides on \(\mathbb{Z}^{+}\) | 2 and 6 | 2 and 3 |
| \(\leq\) on \(\mathbb{R}\) | every pair | none |
The first row is worked in 2026-09-22-partial-order-relations.
- Non-comparable is not “different”. \(\{7\}\) and \(\{7,9\}\) are different and comparable.
- Non-comparable is not “disjoint” or “unlike”. \(\{1,2,3\}\) and \(\{1,2,4\}\) share two elements and are still non-comparable, because neither contains the other.
- Both directions have to fail. \(6 \nmid 2\) on its own does not make 2 and 6 non-comparable, because \(2 \mid 6\).
- The elements have to be in the set. 7 and 9 are not comparable under \(\subseteq\) on \(\mathcal{P}(\mathbb{Z})\), and not non-comparable either: they are not elements of \(\mathcal{P}(\mathbb{Z})\).
In a partial order every element is comparable with itself, because the relation is reflexive. The definition of comparable applies to any relation, and in a relation that is not reflexive an element is comparable with itself only if it has a loop, as in the six-point example of 2026-09-22-partial-order-relations.
Proving a relation is a partial order
Three labelled parts, as for an equivalence relation (equivalence-relations), with the middle one changed:
| Part | Start with | Show |
|---|---|---|
| reflexive | Let \(a \in S\). | \(a \mathrel{R} a\) |
| antisymmetric | Let \(a, b \in S\) and suppose \(a \mathrel{R} b\) and \(b \mathrel{R} a\). | \(a = b\) |
| transitive | Let \(a, b, c \in S\) and suppose \(a \mathrel{R} b\) and \(b \mathrel{R} c\). | \(a \mathrel{R} c\) |
Worked: divides on \(\mathbb{Z}^{+}\)
The proof is written out in full in 2026-09-22-partial-order-relations. Unfold \(a \mid b\) as \(b = ak\) for some \(k \in \mathbb{Z}\) (divisibility-and-factorisation).
- Reflexive. \(a = a \cdot 1\), so \(a \mid a\).
- Antisymmetric. If \(b = ak\) and \(a = b\ell\) then \(b = b(\ell k)\), so \(\ell k = 1\). Both are positive, so \(\ell = k = 1\) and \(a = b\).
- Transitive. If \(b = ak\) and \(c = b\ell\) then \(c = a(k\ell)\) and \(k\ell \in \mathbb{Z}\), so \(a \mid c\).
Worked: \(\subseteq\) on a set of sets
Let \(S\) be any set of sets, for instance a power set.
- Reflexive. Every set is a subset of itself: \(X \subseteq X\).
- Antisymmetric. If \(X \subseteq Y\) and \(Y \subseteq X\) then \(X = Y\) (sets-and-set-notation).
- Transitive. If \(X \subseteq Y\) and \(Y \subseteq Z\), then every element of \(X\) is in \(Y\) and so in \(Z\): \(X \subseteq Z\).
Proper subset, \(\subset\), is not a partial order under this definition: it is not reflexive (2026-09-17-relations-reflexivity-symmetry-transitivity). The same goes for \(<\) on \(\mathbb{R}\). Both are antisymmetric and transitive, and neither has a single loop.
Total or not
Once a relation is known to be a partial order, totality is one more “for all”: for all \(a, b \in S\), \(a \mathrel{R} b\) or \(b \mathrel{R} a\).
| How | |
|---|---|
| To show it is total | Let \(a, b \in S\). Show that \(a \mathrel{R} b\) or \(b \mathrel{R} a\), usually by splitting into cases. |
| To show it is not total | Find one pair that is not comparable. |
Divides on \(\mathbb{Z}^{+}\) is not total: \(2 \nmid 3\) and \(3 \nmid 2\). One pair that cannot be compared is the whole answer. With \(\tau\) for “divides” it is written \(2 \mathrel{\not\tau} 3\) and \(3 \mathrel{\not\tau} 2\).
A total order by cases (practice-problems, Q1): for \(x \mathrel{\rho} y \leftrightarrow x^3 - 1 < y^3\) on \(\mathbb{Z}\), take two different integers \(x, y\). Then \(x^3 \neq y^3\), so either \(x^3 < y^3\), giving \(x \mathrel{\rho} y\), or \(y^3 < x^3\), giving \(y \mathrel{\rho} x\).
Whether an order is total depends on the set. Take “divides” on \(\{1, 2, 4, 8, 16\}\). There each number divides all the later ones, every two are comparable, and the order is total. On a set that contains 2 and 3 it is not.
Figure 1: The relation divides on two sets, drawn as Hasse diagrams: a line means the lower number divides the upper one, and so does any path that goes up all the way. Left: on \({1,2,4,8,16}\) the diagram is a single column. Any two numbers are joined by an upward path, so every two are comparable and the order is total. Right: on \({1,2,3,6}\) the diagram branches. 2 and 3, shaded, are not joined by an upward path, since neither divides the other, so the order is partial and not total.
The examples side by side
| Relation | on | Partial order? | Total order? |
|---|---|---|---|
| \(\leq\) | \(\mathbb{R}\) | yes | yes |
| divides | \(\mathbb{Z}^{+}\) | yes | no: 2 and 3 |
| divides | \(\{1,2,4,8,16\}\) | yes | yes |
| \(\subseteq\) | \(\mathcal{P}(\{1,2,3\})\) | yes | no: \(\{1\}\) and \(\{2\}\) |
| \(\subseteq\) | \(\mathcal{P}(\mathbb{Z})\) | yes | no: \(\{7\}\) and \(\{9\}\) |
| \(x^3 - 1 < y^3\) | \(\mathbb{Z}\) | yes | yes |
| five elements in a single column | five elements | yes | yes |
| the same with a sixth element at the side | six elements | yes | no |
| \(\operatorname{weight}(s) \leq \operatorname{weight}(t)\) | binary strings of length 6 | no: not antisymmetric | — |
| \(<\) | \(\mathbb{R}\) | no: not reflexive | — |
| divides | \(\mathbb{Z}\) | no: not antisymmetric | — |
Rows 6 and 9 are Q1 and Q2 of practice-problems. Rows 7 and 8 are the two diagrams of 2026-09-22-partial-order-relations.
Equivalence relations and partial orders
The two kinds of relation the course singles out differ in one property.
| Equivalence relation | Partial order | |
|---|---|---|
| Properties | reflexive, symmetric, transitive | reflexive, antisymmetric, transitive |
| Between two different related elements | arrows both ways, always | an arrow one way only, always |
| What it does to the set | sorts it into classes | ranks it |
| Its picture | separate clusters, a partition | a Hasse diagram |
| Standard examples | \(=\), congruence mod \(n\), same parity | \(\leq\), \(\subseteq\), divides on \(\mathbb{Z}^{+}\) |
| Notes | equivalence-relations, equivalence-classes-and-partitions | partial-order-relations, hasse-diagrams |
A relation that is both an equivalence relation and a partial order is symmetric and antisymmetric, so all its arrows are loops (antisymmetric-relations), and reflexive, so it has every loop. It is equality.
Common mistakes
- Taking “partial order” to mean “not a total order”. Every total order is a partial order.
- Proving “not symmetric” where “antisymmetric” is wanted. They are different properties (antisymmetric-relations).
- Calling \(<\) or \(\subset\) a partial order. With this course’s definition a partial order is reflexive.
- Declaring a pair non-comparable after checking one direction.
- Showing a relation is total with an example. “2 and 4 are comparable” proves nothing about every pair. Not total, on the other hand, needs only one pair.
- Forgetting the set. Divides is a partial order on \(\mathbb{Z}^{+}\), a total order on \(\{1,2,4,8,16\}\), and not even antisymmetric on \(\mathbb{Z}\).
See also
- antisymmetric-relations — the property that separates a partial order from an equivalence relation
- hasse-diagrams — the standard drawing of a partial order
- reflexive-symmetric-and-transitive-relations — reflexive and transitive, with their proof templates
- equivalence-relations — the other important kind of relation
- divisibility-and-factorisation · sets-and-set-notation — the two standard partial orders, divides and \(\subseteq\)
- 2026-09-22-partial-order-relations — Lecture 25
- practice-problems — §32, with full worked solutions