Partial Order Relations

definitions
discrete-math
set-theory
relations
proof

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

  1. Reflexive;
  2. Antisymmetric; and
  3. 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

  1. Reflexive;
  2. Antisymmetric;
  3. Transitive; and
  4. 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