Equivalence relations, from the previous chapter, group things that are "the same". Many relations do something different: they rank things. One course is a prerequisite of another, one task must finish before another starts, one set is contained in another, one number divides another. These relations are not symmetric. They point in a direction, and they usually leave some pairs unranked: neither "Data Structures before Computer Networks" nor the reverse is required.
The mathematical model for this is the partial order. It is the foundation of scheduling (topological sort), dependency resolution in build tools, version histories, and the lattices of the next chapter.
A partial order is a relation that is reflexive, antisymmetric and transitive. A set together with a partial order is a partially ordered set, or poset. "Partial" means some pairs of elements may be incomparable.
In this chapter we define posets, learn to draw them compactly as Hasse diagrams, identify special elements (maximal, minimal, greatest, least, upper and lower bounds, lub and glb), study chains and antichains, and finish with topological sorting. All diagrams and answers were computed and checked by program.
Partial Orders and Posets
A relation ≼ on a set A is a partial order if for all a, b, c ∈ A:
a ≼ a (reflexive),
a ≼ b and b ≼ a imply a = b (antisymmetric),
a ≼ b and b ≼ c imply a ≼ c (transitive).
The pair (A, ≼) is called a poset.
We write ≼ (not ≤) to remind ourselves that the order need not be the usual one on numbers. We write a ≺ b for "a ≼ b and a ≠ b".
Standard examples
Poset | Meaning of a ≼ b | Total? |
|---|---|---|
(ℤ, ≤) | usual less-than-or-equal | Yes |
(ℤ+, |) | a divides b | No: 2 and 3 are incomparable |
(P(S), ⊆) | subset | No (if |S| ≥ 2): {a} and {b} are incomparable |
(Σ*, prefix) | a is a prefix of b | No: "ab" and "ba" are incomparable |
(ℕ × ℕ, product order) | (a1, a2) ≼ (b1, b2) ⇔ a1 ≤ b1 and a2 ≤ b2 | No: (1, 2) and (2, 1) are incomparable |
(ℕ × ℕ, lexicographic order) | a1 < b1, or a1 = b1 and a2 ≤ b2 | Yes |
Divisibility must be restricted to positive integers: on all non-zero integers, 2 | −2 and −2 | 2 break antisymmetry (see Properties of Relations).
Comparable elements, total orders, well-orders
a and b are comparable if a ≼ b or b ≼ a; otherwise incomparable (sometimes written a ∥ b).
A total order (linear order) is a partial order in which every two elements are comparable. Its Hasse diagram is a single vertical line. A totally ordered set is also called a chain.
A well-order is a total order in which every non-empty subset has a least element. (ℕ, ≤) is well-ordered, which is exactly what makes induction work. (ℤ, ≤) is not: ℤ itself has no least element.
A nice trap: dictionary order on strings is total but not well-ordered. Over {a, b}, the strings b, ab, aab, aaab, … are each smaller than the one before, so the set has no least element. Ordering first by length and then alphabetically (shortlex) fixes this, which is why it is the order used to enumerate Σ*.
Strict partial orders
A strict partial order ≺ is irreflexive and transitive (it is then automatically asymmetric: a ≺ b and b ≺ a would give a ≺ a). Strict and non-strict orders carry the same information: ≺ is ≼ minus the diagonal, and ≼ is ≺ plus the diagonal. Examples: < on numbers, ⊂ on sets, "is an ancestor of".
On n labelled elements there are 1, 3, 19, 219 partial orders for n = 1, 2, 3, 4 (verified by checking all 216 relations for n = 4). There is no simple formula.
Hasse Diagrams
The digraph of a partial order has a lot of redundant arrows: a loop at every vertex (implied by reflexivity) and a shortcut for every 2-step path (implied by transitivity). A Hasse diagram throws all the redundant information away.
b covers a if a ≺ b and there is no c with a ≺ c ≺ b. The Hasse diagram of a finite poset draws each element as a point, places b higher than a whenever a ≺ b, and draws a line between a and b exactly when b covers a.
To turn a digraph of a partial order into a Hasse diagram:
Remove all self-loops.
Remove every edge implied by transitivity (an edge a → c whenever a → b → c exists).
Arrange the vertices so that every edge points upward, then drop the arrowheads.
You recover the full order from the diagram: a ≼ b exactly when you can go from a to b by moving upward along lines (or a = b).
Example 1: divisors of 12, D12 = {1, 2, 3, 4, 6, 12} under |
Covering pairs: 1–2, 1–3, 2–4, 2–6, 3–6, 4–12, 6–12. Note 1–4 is not drawn (2 sits between them) and 1–12 is not drawn either.
12
/ \
4 6
\ / \
2 3
\ /
1Read off: 4 and 6 are incomparable (no upward path between them), 3 ≼ 12 (path 3 → 6 → 12), 4 and 3 are incomparable.
Example 2: the power set of {a, b, c} under ⊆
{a,b,c}
/ | \
{a,b} {a,c} {b,c}
| \ / \ / |
| \/ \/ |
| /\ /\ |
| / \ / \ |
{a} {b} {c}
\ | /
∅The crossing lines connect {a, b} to {b} and {a, c} to {a} (left cross), and {a, c} to {c} and {b, c} to {b} (right cross). This diagram is a cube. In general the Hasse diagram of P(S) with |S| = n is the n-dimensional hypercube, with n · 2n−1 edges (12 for n = 3).
Example 3: a poset without a top or bottom
S = {2, 4, 5, 10, 12, 20, 25} under divisibility. Covering pairs: 2–4, 2–10, 4–12, 4–20, 5–10, 5–25, 10–20.
12 20
\ / \
\ / \
4 10 25
\ / \ /
\ / \ /
2 5We will use this poset for the rest of the chapter.
Special Elements
In a poset (A, ≼):
m is maximal if no element is strictly above it: there is no x with m ≺ x.
m is minimal if no element is strictly below it.
g is the greatest element if x ≼ g for every x ∈ A.
l is the least element if l ≼ x for every x ∈ A.
The difference between "maximal" and "greatest" is the most tested idea in this topic. Maximal is a local statement: nothing beats m. Greatest is a global statement: m beats everything. In the Hasse diagram, maximal elements are the points with no line going up; a greatest element is a single point that every point can reach by going up.
For S = {2, 4, 5, 10, 12, 20, 25}:
Minimal elements: 2 and 5. Maximal elements: 12, 20 and 25.
No least element (2 and 5 are incomparable) and no greatest element (three maximal elements).
Facts with proofs
1. A greatest element, if it exists, is unique. If g and g′ are both greatest, then g ≼ g′ and g′ ≼ g, so g = g′ by antisymmetry. (Same for least.)
2. A greatest element is the unique maximal element. It is maximal (if g ≺ x, then also x ≼ g, and antisymmetry gives x = g, a contradiction), and any other maximal m satisfies m ≼ g, which forces m = g.
3. Every finite non-empty poset has at least one minimal and one maximal element. Start at any element a1. If it is not minimal, pick a2 ≺ a1, and so on. By transitivity aj ≺ ai whenever i < j, so all the ai are distinct (a repeat ai = aj would give ai ≺ ai). A finite set cannot supply infinitely many distinct elements, so the process stops at a minimal element.
4. In a finite poset, a unique maximal element is the greatest element. Take any x. Applying fact 3 upward from x, the chain x ≺ … must end at some maximal element, which can only be the unique one, m. So x ≼ m for every x. This fails for infinite posets: take (ℤ, ≤) together with one extra point p that is incomparable to every integer. Then p is the only maximal element (the integers have none), but p is not greatest.
Bounds, lub and glb
Let B ⊆ A. An element u ∈ A is an upper bound of B if b ≼ u for every b ∈ B; a lower bound if u ≼ b for every b ∈ B. The least upper bound (lub, supremum, join) is an upper bound that is ≼ every other upper bound. The greatest lower bound (glb, infimum, meet) is a lower bound that is ≽ every other lower bound.
Bounds are taken in the whole poset A, not just in B. A lub or glb may fail to exist, either because there are no upper bounds at all or because the upper bounds have no least member.
Worked examples in S = {2, 4, 5, 10, 12, 20, 25}:
Subset B | Upper bounds | lub | Lower bounds | glb |
|---|---|---|---|---|
{2, 5} | 10, 20 | 10 | none | does not exist |
{4, 10} | 20 | 20 | 2 | 2 |
{2, 4} | 4, 12, 20 | 4 | 2 | 2 |
{10, 20} | 20 | 20 | 2, 5, 10 | 10 |
{12, 20} | none | does not exist | 2, 4 | 4 |
{4, 5} | 20 | 20 | none | does not exist |
Two observations. First, when B has a greatest element, that element is the lub ({2, 4} → 4). Second, in a divisibility poset the lub is the lcm only when the lcm belongs to the set. For {12, 20}, lcm = 60 is not in S and S has no common multiple of 12 and 20 at all, so there is no lub. And in the poset {1, 2, 3, 12} under divisibility, the lub of {2, 3} is 12, not 6, because 6 is not available. Always look at what is actually present.
A clean example where upper bounds exist but there is no lub is the "bowtie" {a, b, c, d} with a ≺ c, a ≺ d, b ≺ c, b ≺ d: the upper bounds of {a, b} are c and d, which are incomparable, so neither is least. Posets in which every pair has both a lub and a glb are called lattices, the subject of the next chapter.
Chains, Antichains, Height and Width
A chain is a subset in which every two elements are comparable. Its length is usually counted as the number of elements (some books count edges, i.e. elements − 1; check the convention).
An antichain is a subset in which no two distinct elements are comparable.
The height is the size of the largest chain, and the width is the size of the largest antichain.
In S: a longest chain is 2 | 4 | 12 (also 2 | 4 | 20, 2 | 10 | 20, 5 | 10 | 20), so height = 3. Largest antichains: {4, 10, 25}, {10, 12, 25}, {12, 20, 25}, so width = 3.
Two classical theorems connect these numbers:
Mirsky's theorem: the minimum number of antichains needed to partition a finite poset equals its height. (Easy proof: label each element x by the number of elements in the longest chain that ends at x. Two elements with the same label are incomparable, because if x ≺ y then y's label is bigger. So each label class is an antichain, and there are exactly "height" labels.)
Dilworth's theorem: the minimum number of chains needed to cover a finite poset equals its width. For S, three chains suffice: {2, 4, 12}, {5, 10, 20}, {25}, and three are needed because {4, 10, 25} must go into three different chains.
Scheduling reading of Mirsky: if tasks are ordered by "must finish before", the height is the minimum number of rounds needed when unlimited workers can run independent tasks in parallel.
Topological Sorting (Linear Extensions)
A linear extension (topological order) of a poset is a listing of all its elements such that whenever a ≺ b, a appears before b. It turns a partial order into a total order without breaking any constraint. Course planning, build systems (make, Gradle), package managers and spreadsheet recalculation all compute one.
Algorithm (repeated removal of minimal elements):
while the poset is non-empty:
pick any minimal element m (exists by fact 3)
output m and remove itThe output is valid: when m is output, everything below it was already removed (otherwise m would not be minimal). In graph language this is Kahn's algorithm on the Hasse diagram, choosing a vertex of in-degree 0 each time. Every finite poset therefore has at least one linear extension.
For D12 there are exactly 5 linear extensions. 1 must come first and 12 last. In the middle, 2 must precede 4 and 6, and 3 must precede 6. If 2 comes first among {2, 3, 4, 6}, the remaining 3, 4, 6 can be arranged in 3 ways with 3 before 6; if 3 comes first, 2 must come next and then 4, 6 in either order (2 ways). Total 3 + 2 = 5.
Code: Hasse edges, extremal elements, topological orders
from itertools import permutations
def leq(a, b):
"""The partial order used here: a divides b."""
return b % a == 0
def hasse_edges(S):
"""Covering pairs (a, b): a < b and nothing lies strictly between them."""
return [(a, b) for a in S for b in S
if a != b and leq(a, b)
and not any(c not in (a, b) and leq(a, c) and leq(c, b) for c in S)]
def minimal(S):
return [m for m in S if not any(x != m and leq(x, m) for x in S)]
def maximal(S):
return [m for m in S if not any(x != m and leq(m, x) for x in S)]
def linear_extensions(S):
"""All orderings of S in which every element comes after everything below it."""
return [p for p in permutations(S)
if all(not leq(p[j], p[i]) for i in range(len(p)) for j in range(i + 1, len(p)))]
S = [2, 4, 5, 10, 12, 20, 25]
print("Hasse edges:", hasse_edges(S))
print("minimal :", minimal(S))
print("maximal :", maximal(S))
ext = linear_extensions(S)
print("number of linear extensions:", len(ext))
print("one topological order:", ext[0])Output:
Hasse edges: [(2, 4), (2, 10), (4, 12), (4, 20), (5, 10), (5, 25), (10, 20)]
minimal : [2, 5]
maximal : [12, 20, 25]
number of linear extensions: 70
one topological order: (2, 4, 5, 10, 12, 20, 25)The brute-force linear_extensions tries all n! orders, which is fine for 7 elements but useless for large inputs. Use the removal algorithm above to find one order in O(V + E) time; counting all linear extensions is a much harder problem in general (#P-complete).
Common Mistakes
Confusing maximal with greatest. A poset may have many maximal elements and no greatest one.
Drawing transitive edges in a Hasse diagram, such as 1–4 in D12. Only covering pairs are drawn.
Reading incomparable elements as ordered because one is drawn higher on the page. Only upward paths count: 4 is drawn level with 6 in D12, but even if it were drawn higher, 6 ≼ 4 would still be false.
Looking for upper bounds only inside B. Bounds are elements of the whole poset.
Assuming lub = lcm in any divisibility poset. That holds in Dn, not in an arbitrary subset of ℤ+.
Using divisibility on ℤ as a partial order. It is not antisymmetric there.
Practice and GATE-Style Questions
Q1. Which of these are posets: (ℤ, ≠), (ℤ, <), (P(S), ⊆), (ℤ+, |)?
(ℤ, ≠) is not reflexive. (ℤ, <) is not reflexive (it is a strict order). (P(S), ⊆) and (ℤ+, |) are posets.
Q2. In the poset ({1, 2, 3, 4, 6, 9}, |), find the minimal, maximal, least and greatest elements.
Minimal: 1. Least: 1 (it divides everything). Maximal: 4, 6, 9 (none of them divides another element of the set). Greatest: none.
Q3. How many edges does the Hasse diagram of (P({1, 2, 3, 4}), ⊆) have?
Each edge adds one element to a set. Choose the set being added to and the new element: n · 2n−1 = 4 · 8 = 32.
Q4. How many edges does the Hasse diagram of D36 have?
36 = 22 · 32, so each divisor is 2i3j with 0 ≤ i, j ≤ 2: a 3 × 3 grid. Covering means multiplying by a single prime. Edges: 3 rows × 2 + 3 columns × 2 = 12.
Q5. True or false: every finite poset with exactly one minimal element has a least element.
True (fact 4 turned upside down): every element sits above some minimal element, and there is only one.
Q6. Interview: you are given a list of package dependencies. How do you detect that no install order exists?
An install order is a linear extension of the "depends on" relation, which exists only if that relation's transitive closure is a strict partial order, i.e. the dependency graph has no directed cycle. Run Kahn's algorithm: if at some point no vertex has in-degree 0 while vertices remain, those vertices contain a cycle and no order exists.
Summary
A partial order is reflexive, antisymmetric and transitive; a total order makes every pair comparable; a well-order also has a least element in every non-empty subset.
A Hasse diagram draws only covering pairs, with larger elements higher; a ≼ b iff there is an upward path.
Maximal/minimal are local; greatest/least are global and unique when they exist. In finite posets a unique maximal element is greatest.
lub and glb are the least upper bound and greatest lower bound; either can fail to exist.
Height = longest chain = minimum number of antichains (Mirsky); width = largest antichain = minimum number of chains (Dilworth).
Every finite poset has a topological order, found by repeatedly removing a minimal element.
Draw the Hasse diagram first. Almost every poset question, from maximal elements to lub, glb and topological orders, is answered by looking up and down its lines.