Contents / Discrete Mathematics / Relations and Equivalence

Chapter 3

Relations and Equivalence

Binary relations, their matrices and digraphs; the five properties shown independent by explicit witnesses; the correspondence between equivalence relations and partitions proved in both directions; congruence modulo n; transitive closure as a union of powers and as a smallest relation; partial orders, Hasse diagrams and maximal elements; and total orders with topological sorting.

Introduction

A set knows only which objects belong to it. It has nothing to say about how those objects stand to one another — which files depend on which, which records share a key, which version supersedes which. That information is carried by a relation, and a relation is a startlingly cheap object: just a set of ordered pairs. Everything in this chapter is extracted from that one definition by imposing conditions on the pairs.

Two families of conditions matter above all others. Impose reflexivity, symmetry and transitivity and you get an equivalence relation, which behaves like equality: it declares certain objects interchangeable for the purpose at hand. Impose reflexivity, antisymmetry and transitivity and you get a partial order, which behaves like $\leq$ : it ranks objects, but tolerates pairs it refuses to rank. These two are not arbitrary picks from the sixteen-odd combinations available. Each is the exact structure that answers a question that keeps recurring: when may I treat two things as the same? and when must one thing come before another?

The centrepiece of the chapter is the theorem that equivalence relations on a set are the same data as partitions of it. Not merely that one produces the other — that the correspondence is a bijection, so that every fact about equivalence relations translates into a fact about partitions and back. It is the first place in a mathematics course where two definitions that look nothing alike turn out to be two descriptions of one object, and the proof is worth the care it takes.

For orders, the payoff is algorithmic. Every finite partially ordered set can be flattened into a linear list that respects all the constraints it did impose — that is topological sorting, which is what a build system does when it decides the order to compile your files, what a package manager does when it installs dependencies, and what a spreadsheet does when it decides which cells to recalculate. We will prove that it is always possible, and the proof is essentially the algorithm.

Throughout, $A$ denotes a set, and $∣ A ∣ = n$ when $A$ is finite. We write $Z$ for the integers and $[n]$ for ${1, 2, \dots, n}$ .

3.1Relations, their representations, and composition

Start with the definition, which is deliberately thin. A relation is not required to be meaningful, computable, or describable by a rule; it is a set of pairs and nothing else. The thinness is the point, because it means the theorems we prove apply to every relation, including the ones nobody would think to write down.

Definition 3.1 (Binary relation). Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset $R \subseteq A \times B$ of the Cartesian product. We write $a R b$ as shorthand for $(a, b) \in R$ , and $a \neq R b$ when $(a, b) \in / R$ .

A relation on $A$ is a relation from $A$ to $A$ , that is, a subset of $A \times A$ .

Unless stated otherwise every relation in this chapter is a relation on a single set, because the properties we care about — reflexivity, transitivity and the rest — compare the two coordinates and so need them drawn from the same place.

Intuition. Picture the elements of $A$ as dots. A relation is a choice, for each ordered pair of dots, of whether to draw an arrow from the first to the second. A dot may point at itself. The arrows $a \to b$ and $b \to a$ are different choices and may be made independently.

Definition 3.2 (Domain, range, inverse, identity). Let $R$ be a relation on $A$ .

$dom (R) = {a \in A : (a, b) \in R for some b}$ , the domain.
$ran (R) = {b \in A : (a, b) \in R for some a}$ , the range.
$R^{- 1} = {(b, a) : (a, b) \in R}$ , the inverse (or converse) relation.
$Δ_{A} = {(a, a) : a \in A}$ , the identity or diagonal relation on $A$ .

The diagonal $Δ_{A}$ is the relation of literal equality, and it will keep reappearing: reflexivity is the statement $Δ_{A} \subseteq R$ , and antisymmetry is the statement $R \cap R^{- 1} \subseteq Δ_{A}$ . Translating conditions into set containments like these is not a stylistic preference; it is what makes them provable in one line instead of three.

Proposition 3.3 (How many relations a set carries). A set $A$ with $∣ A ∣ = n$ carries exactly

2^{n^{2}}

relations.

Proof. A relation on $A$ is by definition an arbitrary subset of $A \times A$ , and no condition restricts which subsets qualify. Since $∣ A \times A ∣ = n \cdot n = n^{2}$ , and a set of size $m$ has exactly $2^{m}$ subsets, the number of relations is $2^{n^{2}}$ .∎

For $n = 3$ that is $2^{9} = 512$ , and for $n = 4$ it is $2^{16} = 65536$ . The count grows so fast that exhaustive search over relations is hopeless past $n = 5$ ; this is why we reason about relations by their properties rather than by enumerating them.

Two representations

A relation on a finite set can be written down in two ways that are genuinely useful, as opposed to merely listing the pairs.

Definition 3.4 (Matrix of a relation). Let $A = {a_{1}, \dots, a_{n}}$ with a fixed ordering of its elements, and let $R$ be a relation on $A$ . The matrix of $R$ is the $n \times n$ array $M_{R}$ with entries in ${0, 1}$ given by

(M_{R})_{ij} = {10 if (a_{i}, a_{j}) \in R, otherwise.

Definition 3.5 (Digraph of a relation). The digraph (directed graph) of $R$ has one vertex for each element of $A$ and a directed edge from $a$ to $b$ exactly when $(a, b) \in R$ . An edge from a vertex to itself is a loop.

The matrix is what a computer stores; the digraph is what a human draws. They carry identical information, and different properties are easy to see in each. Reflexivity is a glance at the diagonal of the matrix; transitivity is a statement about paths in the digraph.

Example 3.6 (Both representations of one relation). Let $A = {1, 2, 3}$ and $R = {(1, 1), (1, 2), (2, 1), (3, 3)}$ . Write the matrix of $R$ , list $dom (R)$ and $ran (R)$ , and describe the digraph.

Solution.

Row $i$ of $M_{R}$ records which elements $i$ points at. Row $1$ : $(1, 1)$ and $(1, 2)$ are present, $(1, 3)$ is not, giving $110$ . Row $2$ : only $(2, 1)$ , giving $100$ . Row $3$ : only $(3, 3)$ , giving $001$ . So

M_{R} = 110100001 .

The first coordinates occurring are $1, 2, 3$ , so $dom (R) = {1, 2, 3}$ . The second coordinates occurring are $1, 2, 3$ as well, so $ran (R) = {1, 2, 3}$ .
The digraph has loops at $1$ and $3$ , no loop at $2$ , and a two-way pair of edges between $1$ and $2$ . Vertex $3$ is isolated apart from its loop.

The number of $1$ s in the matrix is $4 = ∣ R ∣$ , which is the check to run every time: $∣ R ∣$ counts entries, not rows.□

Composition and powers

Composition is where relations start to do work. If $R$ records "imports directly" and we want "imports, possibly through a chain", we need to follow two arrows and then many.

Definition 3.7 (Composition of relations). Let $R$ and $S$ be relations on $A$ . Their composition is

S \circ R = {(a, c) \in A \times A : (a, b) \in R and (b, c) \in S for some b \in A} .

In words: $a$ reaches $c$ by first taking an $R$ -step and then an $S$ -step.

Notation. The order in $S \circ R$ follows the convention for functions, where $(g \circ f) (x) = g (f (x))$ applies $f$ first. Some books write $R; S$ for the same thing with the steps in reading order. We will mostly compose a relation with itself, where the question does not arise.

Definition 3.8 (Powers of a relation). For a relation $R$ on $A$ define $R^{1} = R$ and $R^{k + 1} = R \circ R^{k}$ for $k \geq 1$ .

Unwinding the definition, $(a, b) \in R^{k}$ exactly when there is a chain $a = x_{0}, x_{1}, \dots, x_{k} = b$ of elements of $A$ with $(x_{i - 1}, x_{i}) \in R$ for each $i$ — that is, a walk of length exactly $k$ from $a$ to $b$ in the digraph of $R$ . We record this because it is the fact every later proof about closures uses.

Lemma 3.9 (Powers are walks). For every $k \geq 1$ and all $a, b \in A$ , we have $(a, b) \in R^{k}$ if and only if there exist $x_{0}, x_{1}, \dots, x_{k} \in A$ with $x_{0} = a$ , $x_{k} = b$ and $(x_{i - 1}, x_{i}) \in R$ for $i = 1, \dots, k$ .

Proof. Induct on $k$ . For $k = 1$ the claim is that $(a, b) \in R$ if and only if there is a chain $a = x_{0}, x_{1} = b$ with $(x_{0}, x_{1}) \in R$ , which is a restatement.

Suppose the claim holds for $k$ . By definition $(a, b) \in R^{k + 1} = R \circ R^{k}$ means there is some $c \in A$ with $(a, c) \in R^{k}$ and $(c, b) \in R$ . By the induction hypothesis, $(a, c) \in R^{k}$ is equivalent to the existence of a walk $a = x_{0}, \dots, x_{k} = c$ of length $k$ ; appending $x_{k + 1} = b$ using the edge $(c, b) \in R$ produces a walk of length $k + 1$ from $a$ to $b$ . Conversely, a walk $x_{0}, \dots, x_{k + 1}$ from $a$ to $b$ splits at $x_{k}$ : its initial segment is a walk of length $k$ from $a$ to $x_{k}$ , so $(a, x_{k}) \in R^{k}$ by the induction hypothesis, and $(x_{k}, b) \in R$ , so $(a, b) \in R \circ R^{k}$ .∎

Now the connection to linear algebra. Define the Boolean product of two $0$ - $1$ matrices $M$ and $N$ of size $n \times n$ by

(M ⊙ N)_{ij} = k = 1 ⋁ n (M_{ik} \land N_{kj}),

where $\land$ is logical and ( $1$ if both are $1$ ) and $⋁$ is logical or ( $1$ if any term is $1$ ). This is the ordinary matrix product with $+$ replaced by "or" and $\times$ by "and"; equivalently, it is the ordinary product followed by replacing every nonzero entry with $1$ .

Theorem 3.10 (Composition is Boolean matrix product). Let $R$ and $S$ be relations on a finite set $A$ with a fixed ordering of elements. Then

M_{S \circ R} = M_{R} ⊙ M_{S} .

Consequently $M_{R^{k}}$ is the $k$ -fold Boolean power of $M_{R}$ .

Proof. Both sides are $0$ - $1$ matrices, so it suffices to show they have a $1$ in the same positions. Fix $i$ and $j$ .

The entry $(M_{S \circ R})_{ij}$ is $1$ exactly when $(a_{i}, a_{j}) \in S \circ R$ , which by the definition of composition holds exactly when there exists an index $k$ with $(a_{i}, a_{k}) \in R$ and $(a_{k}, a_{j}) \in S$ .

The entry $(M_{R} ⊙ M_{S})_{ij}$ is $1$ exactly when the disjunction $⋁_{k} ((M_{R})_{ik} \land (M_{S})_{kj})$ is $1$ , which holds exactly when there is some index $k$ for which both $(M_{R})_{ik} = 1$ and $(M_{S})_{kj} = 1$ — that is, some $k$ with $(a_{i}, a_{k}) \in R$ and $(a_{k}, a_{j}) \in S$ .

The two conditions are word for word the same, so the entries agree for every $i, j$ . The statement about powers follows by induction on $k$ , the inductive step being the case $S = R$ , $R = R^{k}$ of what was just proved.∎

Remark. This is why reachability in a graph on $n$ vertices can be computed with matrix multiplications rather than by an explicit search: $lo g_{2} n$ Boolean squarings of the adjacency matrix suffice to find all walks of length up to $n$ . It is also why the same code that multiplies matrices of numbers computes transitive closures if you swap the two arithmetic operations.

Example 3.11 (Composing a small relation with itself). Let $A = {1, 2, 3, 4}$ and $R = {(1, 2), (2, 3), (3, 4)}$ . Compute $R^{2}$ and $R^{3}$ , and say how many pairs $R^{4}$ has.

Solution.

By the lemma Powers are walks, $R^{2}$ consists of the pairs joined by a walk of length $2$ . The walks are $1 \to 2 \to 3$ and $2 \to 3 \to 4$ , so $R^{2} = {(1, 3), (2, 4)}$ .
Walks of length $3$ : only $1 \to 2 \to 3 \to 4$ , so $R^{3} = {(1, 4)}$ .
A walk of length $4$ would need five distinct steps' worth of vertices in a chain that stops at $4$ ; since $R$ has no edge out of $4$ , no walk of length $4$ exists and $R^{4} = \emptyset$ , which has $0$ pairs.

Notice the sizes $3, 2, 1, 0$ : each extra step costs one starting point, which is what a path-shaped relation does.□

Exercises for §3.1 →

3.2The five properties and their independence

Five conditions on a relation account for almost everything that follows. Each is a single quantified sentence, and each has a one-line translation into the matrix and into the digraph.

Definition 3.12 (The five properties). Let $R$ be a relation on $A$ . Then $R$ is

reflexive if $(a, a) \in R$ for every $a \in A$ ;
irreflexive if $(a, a) \in / R$ for every $a \in A$ ;
symmetric if $(a, b) \in R$ implies $(b, a) \in R$ , for all $a, b \in A$ ;
antisymmetric if $(a, b) \in R$ and $(b, a) \in R$ together imply $a = b$ , for all $a, b \in A$ ;
transitive if $(a, b) \in R$ and $(b, c) \in R$ together imply $(a, c) \in R$ , for all $a, b, c \in A$ .

$R$ is connex (or total, or complete) if for all $a, b \in A$ at least one of $(a, b) \in R$ and $(b, a) \in R$ holds.

Pitfall. "Antisymmetric" is not the negation of "symmetric", and the two are not alternatives. The negation of symmetric is: some pair is related one way only. Antisymmetric is: no pair of distinct elements is related both ways. A relation can be both, and a relation can be neither — we prove exactly that below. Likewise "irreflexive" is not the negation of "reflexive": a relation with a loop at $a$ but not at $b$ is neither reflexive nor irreflexive.

Proposition 3.13 (The properties read off the matrix). Let $R$ be a relation on the finite set $A = {a_{1}, \dots, a_{n}}$ , with matrix $M = M_{R}$ .

$R$ is reflexive if and only if $M_{ii} = 1$ for all $i$ ; irreflexive if and only if $M_{ii} = 0$ for all $i$ .
$R$ is symmetric if and only if $M = M^{T}$ .
$R$ is antisymmetric if and only if $M_{ij} \land M_{ji} = 0$ for all $i \neq = j$ .
$R$ is transitive if and only if $R \circ R \subseteq R$ , equivalently $(M ⊙ M)_{ij} = 1$ implies $M_{ij} = 1$ .

Proof. Parts 1 to 3 are the definitions rewritten with $(M)_{ij} = 1 ⟺ (a_{i}, a_{j}) \in R$ substituted throughout. For 1, " $(a, a) \in R$ for all $a$ " becomes " $M_{ii} = 1$ for all $i$ ". For 2, symmetry says $(a_{i}, a_{j}) \in R ⟺ (a_{j}, a_{i}) \in R$ , that is $M_{ij} = M_{ji}$ for all $i, j$ , which is exactly $M = M^{T}$ . For 3, antisymmetry forbids $(a_{i}, a_{j})$ and $(a_{j}, a_{i})$ both lying in $R$ when $i \neq = j$ , that is, forbids $M_{ij} = M_{ji} = 1$ .

For 4, unfold the composition: $(a, c) \in R \circ R$ means there is $b$ with $(a, b) \in R$ and $(b, c) \in R$ . So the containment $R \circ R \subseteq R$ says precisely that whenever such a $b$ exists, $(a, c) \in R$ — which is transitivity. The matrix form is then the theorem Composition is Boolean matrix product applied with $S = R$ .∎

Part 4 is the useful one. It replaces a statement with three quantified variables by a containment between two sets, and containments can be manipulated. Every proof of transitivity in the rest of the chapter can be run either way; we will pick whichever is shorter.

Proposition 3.14 (Counting relations with a given property). Let $∣ A ∣ = n$ . The number of relations on $A$ that are

reflexive is $2^{n^{2} - n}$ ;
symmetric is $2^{n (n + 1) /2}$ ;
both reflexive and symmetric is $2^{n (n - 1) /2}$ .

Proof. Each part counts matrices with a constraint, using the fact that free entries may be filled in independently.

Reflexivity fixes the $n$ diagonal entries to $1$ and constrains nothing else. The remaining $n^{2} - n$ off-diagonal entries are free, giving $2^{n^{2} - n}$ choices.
Symmetry means the matrix is determined by its entries on and above the diagonal, of which there are $n + (n - 1) + \dots + 1 = n (n + 1) /2$ , and any assignment to those extends uniquely to a symmetric matrix. Hence $2^{n (n + 1) /2}$ .
Imposing both, the diagonal is forced and the strictly-upper entries — there are $n (n - 1) /2$ of them — are free and determine the strictly-lower ones. Hence $2^{n (n - 1) /2}$ .

∎

Example 3.15 (Counting on a four-element set). With $∣ A ∣ = 4$ , how many relations on $A$ are reflexive? How many are symmetric? How many are both?

Solution.

Reflexive: $2^{16 - 4} = 2^{12} = 4096$ .
Symmetric: $2^{4 \cdot 5/2} = 2^{10} = 1024$ .
Both: $2^{4 \cdot 3/2} = 2^{6} = 64$ .

As a check, every relation counted in part 3 is counted in both parts 1 and 2, and $64$ is indeed a common divisor's worth smaller than each — in fact $4096 \cdot 1024/65536 = 64$ , which is the inclusion–exclusion identity for two independent constraints on disjoint sets of matrix entries.□

The properties are genuinely independent

It is easy to believe, after seeing $\leq$ and $=$ , that the properties come in fixed bundles: that symmetric and antisymmetric are opposites, that transitive implies reflexive, and so on. They do not. The following proposition settles the question by exhibiting, for each of the combinations that students conflate, a relation realising it.

Proposition 3.16 (Independence of the five properties). Let $A = {1, 2, 3}$ . Then:

There is a relation on $A$ that is both symmetric and antisymmetric.
There is a relation on $A$ that is neither symmetric nor antisymmetric.
There is a relation on $A$ that is symmetric and transitive but not reflexive.
There is a relation on $A$ that is reflexive and symmetric but not transitive.
There is a relation on $A$ that is reflexive and transitive but not symmetric and not antisymmetric.
There is a relation on $A$ that is both irreflexive and transitive, and one that is neither reflexive nor irreflexive.

Proof. We exhibit a relation in each case and verify the claims directly from the definition of The five properties.

Take $R = Δ_{A} = {(1, 1), (2, 2), (3, 3)}$ . It is symmetric, since the reverse of $(a, a)$ is $(a, a)$ . It is antisymmetric, since the only pairs $(a, b) \in R$ have $a = b$ already, so the implication's conclusion holds vacuously whenever its hypothesis does. More generally any $R \subseteq Δ_{A}$ is both, and these are the only such relations: if $R$ is symmetric and antisymmetric and $(a, b) \in R$ , then $(b, a) \in R$ by symmetry and hence $a = b$ by antisymmetry.
Take $R = {(1, 2), (2, 1), (1, 3)}$ . It fails symmetry because $(1, 3) \in R$ but $(3, 1) \in / R$ . It fails antisymmetry because $(1, 2)$ and $(2, 1)$ are both in $R$ while $1 \neq = 2$ . So the two properties are not exhaustive either.
Take $R = {(1, 1)}$ . Symmetric and transitive by the same vacuous reasoning as in part 1, but not reflexive since $(2, 2) \in / R$ . This example matters: it is the standard refutation of the false claim that symmetry plus transitivity imply reflexivity. The bogus argument reads " $a R b$ gives $b R a$ by symmetry, then $a R a$ by transitivity", and it breaks for any $a$ that is related to nothing at all.
Take $R = Δ_{A} \cup {(1, 2), (2, 1), (2, 3), (3, 2)}$ . It is reflexive by construction and symmetric because the non-diagonal pairs were added in mirrored couples. It is not transitive: $(1, 2) \in R$ and $(2, 3) \in R$ but $(1, 3) \in / R$ . (Read $R$ as "differs by at most one", which is exactly the relation that is not transitive in everyday life: near-duplicates in a database are pairwise similar without all being the same record.)
Take $R = Δ_{A} \cup {(1, 2), (2, 1), (1, 3), (2, 3)}$ . Reflexive by construction. Not symmetric, since $(1, 3) \in R$ and $(3, 1) \in / R$ . Not antisymmetric, since $(1, 2), (2, 1) \in R$ with $1 \neq = 2$ . For transitivity, the only composable non-diagonal chains are $(1, 2)$ then $(2, 1)$ , needing $(1, 1) \in R$ ✓; $(2, 1)$ then $(1, 2)$ , needing $(2, 2) \in R$ ✓; $(1, 2)$ then $(2, 3)$ , needing $(1, 3) \in R$ ✓; $(2, 1)$ then $(1, 3)$ , needing $(2, 3) \in R$ ✓. Chains through a diagonal pair add nothing new. So $R$ is transitive.
For the first, take $R = {(1, 2), (2, 3), (1, 3)}$ : no loops, so irreflexive, and the only composable chain $(1, 2), (2, 3)$ has its shortcut $(1, 3)$ present, so transitive. For the second, take $R = {(1, 1)}$ again on $A$ : it has a loop at $1$ , so it is not irreflexive, and lacks a loop at $2$ , so it is not reflexive.

∎

Intuition. The useful mental picture is that each property constrains a different feature of the digraph — loops (reflexive, irreflexive), the pairing of opposite edges (symmetric, antisymmetric), and shortcuts across two-step paths (transitive) — and these features can be adjusted independently. That is why so many combinations occur.

Closures

Given a relation that fails a property, the natural repair is to add the missing pairs and nothing more.

Definition 3.17 (Closure with respect to a property). Let $P$ be one of the properties reflexive, symmetric, transitive, and let $R$ be a relation on $A$ . The $P$ -closure of $R$ is a relation $S$ such that (i) $S$ has property $P$ , (ii) $R \subseteq S$ , and (iii) $S \subseteq T$ for every relation $T$ with property $P$ and $R \subseteq T$ .

Condition (iii) is what makes the closure unique if it exists: two relations each contained in the other are equal. The reflexive closure is easy, being $R \cup Δ_{A}$ , and the symmetric closure is $R \cup R^{- 1}$ . The transitive closure is the interesting one, and it is not obtained by one pass of adding shortcuts.

Definition 3.18 (Transitive closure). The transitive closure of $R$ is written $R^{+}$ , and the reflexive transitive closure is $R^{*} = R^{+} \cup Δ_{A}$ .

Theorem 3.19 (The transitive closure is the union of the powers). Let $R$ be a relation on a set $A$ and put

R^{+} = k \geq 1 ⋃ R^{k} .

Then $R^{+}$ is transitive, contains $R$ , and is contained in every transitive relation containing $R$ . That is, $R^{+}$ is the transitive closure of $R$ , and it consists exactly of the pairs $(a, b)$ joined by a walk of positive length in the digraph of $R$ .

Proof. $R^{+}$ contains $R$ . Immediate, since $R = R^{1}$ is one of the sets in the union.

$R^{+}$ is transitive. Suppose $(a, b) \in R^{+}$ and $(b, c) \in R^{+}$ . Then $(a, b) \in R^{j}$ and $(b, c) \in R^{k}$ for some $j, k \geq 1$ . By the lemma Powers are walks there is a walk of length $j$ from $a$ to $b$ and a walk of length $k$ from $b$ to $c$ ; concatenating them at $b$ gives a walk of length $j + k$ from $a$ to $c$ , so $(a, c) \in R^{j + k} \subseteq R^{+}$ .

$R^{+}$ is smallest. Let $T$ be any transitive relation with $R \subseteq T$ . We show $R^{k} \subseteq T$ for every $k \geq 1$ by induction on $k$ . For $k = 1$ this is the hypothesis $R \subseteq T$ . Assume $R^{k} \subseteq T$ and let $(a, c) \in R^{k + 1}$ . By definition there is $b$ with $(a, b) \in R^{k}$ and $(b, c) \in R$ . Then $(a, b) \in T$ by the induction hypothesis and $(b, c) \in T$ since $R \subseteq T$ , so $(a, c) \in T$ by transitivity of $T$ . Hence $R^{k + 1} \subseteq T$ , and taking the union over $k$ gives $R^{+} \subseteq T$ .

The description in terms of walks is the lemma Powers are walks read across the union: $(a, b) \in R^{+}$ if and only if $(a, b) \in R^{k}$ for some $k \geq 1$ , if and only if some walk of positive length runs from $a$ to $b$ .∎

Corollary 3.20 (A finite bound on the union). If $∣ A ∣ = n$ then $R^{+} = R^{1} \cup R^{2} \cup \dots \cup R^{n}$ .

Proof. One containment is clear, since the right-hand side is part of the union defining $R^{+}$ . For the other, suppose $(a, b) \in R^{k}$ with $k$ minimal. By the lemma Powers are walks there is a walk $a = x_{0}, \dots, x_{k} = b$ . If two of $x_{0}, \dots, x_{k}$ coincided, say $x_{i} = x_{j}$ with $i < j$ , then deleting the steps between them would leave a walk of length $k - (j - i) < k$ from $a$ to $b$ , contradicting minimality of $k$ . So the $k + 1$ vertices $x_{0}, \dots, x_{k}$ are distinct, and since they all lie in $A$ we get $k + 1 \leq n$ , hence $k \leq n - 1 < n$ .∎

Figure 3.21. A relation

R

{1, 2, 3, 4}

with edges

1 \to 2 \to 3 \to 4

in the accent tone, and the three edges the transitive closure adds —

1 \to 3

2 \to 4

and

1 \to 4

— drawn dashed in the result tone. Adding shortcuts once would supply only the first two; the pair

(1, 4)

appears at the second pass, which is why the closure is a union over all powers rather than a single sweep.

Example 3.22 (Computing a transitive closure). Let $A = {1, 2, 3, 4}$ and $R = {(1, 2), (2, 3), (3, 4), (4, 1)}$ , a directed cycle. Compute $R^{+}$ and give $∣ R^{+} ∣$ .

Solution.

By the theorem The transitive closure is the union of the powers, $(a, b) \in R^{+}$ exactly when some walk of positive length runs from $a$ to $b$ .
In a directed $4$ -cycle you may walk any number of steps forward, so from any vertex you can reach every vertex, including itself after four steps.
Hence $R^{+} = A \times A$ , and $∣ R^{+} ∣ = 4^{2} = 16$ .

The closure of a cycle is everything, which is worth contrasting with the path $1 \to 2 \to 3 \to 4$ of the figure, whose closure has only $(2 4) = 6$ pairs. A single extra edge closing the loop takes the closure from $6$ pairs to $16$ .□

Example 3.23 (Closure under dependency). A build system records that module $b$ depends directly on $a$ , $c$ on $b$ , and $e$ on $d$ . Which rebuilds are triggered by a change to $a$ ?

Solution.

Model the direct dependencies as $R = {(a, b), (b, c), (d, e)}$ on ${a, b, c, d, e}$ , where $(x, y) \in R$ reads "a change to $x$ forces a rebuild of $y$ ".
The set of modules needing a rebuild is ${y : (a, y) \in R^{+}}$ . Powers: $R^{2} = {(a, c)}$ and $R^{3} = \emptyset$ .
So $R^{+} = {(a, b), (b, c), (d, e), (a, c)}$ and changing $a$ rebuilds $b$ and $c$ , two modules. The component ${d, e}$ is untouched, which is exactly the property a build system exploits to avoid rebuilding the world.

□

Exercises for §3.2 →

3.3Equivalence relations

Definition 3.24 (Equivalence relation). A relation $\sim$ on $A$ is an equivalence relation if it is reflexive, symmetric and transitive. We write $a \sim b$ and say $a$ and $b$ are equivalent.

The three conditions are exactly the three properties of literal equality that any notion of "same for present purposes" must retain. Drop reflexivity and some object fails to be the same as itself; drop symmetry and sameness acquires a direction; drop transitivity and sameness fails to propagate, which is the failure of "differs by at most one" in the proposition Independence of the five properties.

Intuition. An equivalence relation is a way of deciding to forget information. Congruence mod $12$ forgets everything about an integer except its clock position. Comparing files by content hash forgets their names. What survives the forgetting is exactly what the relation cannot tell apart.

Proposition 3.25 (Two extreme examples). On any set $A$ , both $Δ_{A}$ and $A \times A$ are equivalence relations. Moreover, if $\sim$ is any equivalence relation on $A$ , then $Δ_{A} \subseteq \sim \subseteq A \times A$ .

Proof. $Δ_{A}$ is reflexive by definition; it is symmetric and transitive because, as in part 1 of the proposition Independence of the five properties, every pair in it has equal coordinates. $A \times A$ contains every pair, so all three conditions hold trivially. For the containments: $Δ_{A} \subseteq \sim$ is precisely reflexivity of $\sim$ , and $\sim \subseteq A \times A$ holds because every relation on $A$ is a subset of $A \times A$ .∎

So equivalence relations on $A$ form a range from the finest ( $Δ_{A}$ : nothing is identified with anything else) to the coarsest ( $A \times A$ : everything is identified with everything). Every interesting equivalence lies strictly between.

Proposition 3.26 (The kernel of a function). Let $f : A \to B$ be any function and define $a \sim_{f} a^{'}$ to mean $f (a) = f (a^{'})$ . Then $\sim_{f}$ is an equivalence relation on $A$ , called the kernel of $f$ .

Proof. Reflexive: $f (a) = f (a)$ for every $a$ , since equality in $B$ is reflexive. Symmetric: if $f (a) = f (a^{'})$ then $f (a^{'}) = f (a)$ . Transitive: if $f (a) = f (a^{'})$ and $f (a^{'}) = f (a^{''})$ then $f (a) = f (a^{''})$ . Each of the three conditions is the corresponding property of equality in $B$ , transported along $f$ .∎

This little proposition is more powerful than it looks: it says that every way of grouping objects by a computed value is automatically an equivalence relation. Grouping records by department, files by hash, integers by remainder, strings by length — all are kernels, so none of them needs a separate three-part verification. In fact the theorem Equivalence relations are partitions, proved in the next section, will show the converse: every equivalence relation is the kernel of some function.

Definition 3.27 (Congruence modulo $n$ ). Fix an integer $n \geq 1$ . For $a, b \in Z$ write

a \equiv b (mod n) to mean n ∣ (a - b),

that is, $a - b = nk$ for some $k \in Z$ .

Theorem 3.28 (Congruence mod $n$ is an equivalence with $n$ classes). For every integer $n \geq 1$ , congruence modulo $n$ is an equivalence relation on $Z$ , and it has exactly $n$ distinct equivalence classes, represented by $0, 1, \dots, n - 1$ .

Proof. Equivalence. Reflexive: $a - a = 0 = n \cdot 0$ , so $n ∣ (a - a)$ . Symmetric: if $a - b = nk$ then $b - a = n (- k)$ and $- k \in Z$ . Transitive: if $a - b = nk$ and $b - c = nm$ then $a - c = (a - b) + (b - c) = n (k + m)$ with $k + m \in Z$ .

At most $n$ classes. Let $a \in Z$ . Division with remainder gives unique integers $q$ and $r$ with $a = q n + r$ and $0 \leq r < n$ . Then $a - r = q n$ , so $a \equiv r (mod n)$ with $r \in {0, 1, \dots, n - 1}$ . Hence every integer is congruent to one of these $n$ values, so there are at most $n$ classes.

At least $n$ classes. Suppose $r \equiv s (mod n)$ with $0 \leq r, s < n$ . Then $n ∣ (r - s)$ , while $∣ r - s ∣ < n$ because both lie in an interval of length $n$ . The only multiple of $n$ of absolute value less than $n$ is $0$ , so $r - s = 0$ and $r = s$ . Hence the $n$ values $0, 1, \dots, n - 1$ lie in pairwise distinct classes, giving at least $n$ classes.

Combining the two counts, there are exactly $n$ classes.∎

Remark. Congruence mod $n$ is also the kernel of the function $a \mapsto a mod n$ , so the proposition The kernel of a function gives the equivalence half of the theorem instantly. The counting half is the part that needs division with remainder, which is where the arithmetic actually enters.

Example 3.29 (Congruence in practice). On $Z$ , how many equivalence classes does congruence mod $7$ have, and which class contains $- 3$ ?

Solution.

By the theorem Congruence mod $n$ is an equivalence with $n$ classes, there are exactly $7$ classes.
Divide with remainder: $- 3 = (- 1) \cdot 7 + 4$ , and $0 \leq 4 < 7$ , so $- 3 \equiv 4 (mod 7)$ .
The class is therefore $[4] = {\dots, - 10, - 3, 4, 11, 18, \dots}$ .

The trap is answering $- 3$ or $3$ : the remainder is required to be non-negative, so the quotient is $- 1$ , not $0$ .□

Definition 3.30 (Equivalence class). Let $\sim$ be an equivalence relation on $A$ and $a \in A$ . The equivalence class of $a$ is

[a] = {b \in A : b \sim a} \subseteq A .

Any element $b$ with $[b] = [a]$ is called a representative of the class.

The next lemma is short but it is the engine of the whole theory: it says that a class does not depend on which of its members you name it after.

Lemma 3.31 (Classes coincide exactly for equivalent elements). Let $\sim$ be an equivalence relation on $A$ and $a, b \in A$ . The following are equivalent:

$a \sim b$ ;
$[a] = [b]$ ;
$[a] \cap [b] \neq = \emptyset$ .

Proof. (1) implies (2). Suppose $a \sim b$ . Let $x \in [a]$ , so $x \sim a$ . Combined with $a \sim b$ , transitivity gives $x \sim b$ , so $x \in [b]$ ; hence $[a] \subseteq [b]$ . Symmetry of $\sim$ gives $b \sim a$ , and the same argument with the roles exchanged gives $[b] \subseteq [a]$ . Therefore $[a] = [b]$ .

(2) implies (3). By reflexivity $a \sim a$ , so $a \in [a] = [b]$ , and thus $a \in [a] \cap [b]$ , which is therefore non-empty.

(3) implies (1). Let $x \in [a] \cap [b]$ . Then $x \sim a$ and $x \sim b$ . By symmetry $a \sim x$ , and with $x \sim b$ transitivity gives $a \sim b$ .∎

Pitfall. Every step of that proof used a different one of the three axioms, and none was decorative. Reflexivity is what makes $[a]$ non-empty; symmetry is what lets the argument run in both directions; transitivity is what glues two chains together. A "proof" of the lemma that names only transitivity has a gap.

Exercises for §3.3 →

3.4Partitions and the fundamental correspondence

Definition 3.32 (Partition). A partition of a set $A$ is a collection $P$ of subsets of $A$ , called blocks, such that

every block is non-empty;
the blocks cover $A$ : every $a \in A$ lies in some block;
the blocks are pairwise disjoint: distinct blocks $B, C \in P$ satisfy $B \cap C = \emptyset$ .

Equivalently: every element of $A$ lies in exactly one block.

Figure 3.33. A partition of an eight-element set into three blocks, drawn as disjoint regions. Each element sits in exactly one region — the regions do not overlap and nothing is left outside them, which is conditions 2 and 3 of the definition made visible. Reading the picture as a relation, two elements are equivalent precisely when the same region encloses both.

The last sentence of the definition is worth checking against the three conditions, because it is the form we will actually use. Coverage says "at least one block"; disjointness says "at most one block"; together they say "exactly one". Non-emptiness is a separate normalisation that rules out padding a partition with copies of $\emptyset$ , which would otherwise break the correspondence we are about to prove by making infinitely many partitions out of one.

Here, then, is the central theorem of the chapter.

Theorem 3.34 (Equivalence relations are partitions). Let $A$ be a set.

If $\sim$ is an equivalence relation on $A$ , then the collection of its equivalence classes

A / \sim = {[a] : a \in A}

is a partition of $A$ .

If $P$ is a partition of $A$ , then the relation $\sim_{P}$ defined by

a \sim_{P} b ⟺ a and b lie in the same block of P

is an equivalence relation on $A$ .

These constructions are mutually inverse: starting from an equivalence relation $\sim$ , forming its classes and then forming the same-block relation returns $\sim$ ; and starting from a partition $P$ , forming the same-block relation and then its classes returns $P$ .

Hence the map $\sim \mapsto A / \sim$ is a bijection from the set of equivalence relations on $A$ to the set of partitions of $A$ .

Proof. Part 1: classes form a partition. Let $\sim$ be an equivalence relation.

Blocks are non-empty. Every block of $A / \sim$ has the form $[a]$ for some $a \in A$ . By reflexivity $a \sim a$ , so $a \in [a]$ and $[a] \neq = \emptyset$ .

Blocks cover $A$ . Given $a \in A$ , the block $[a]$ belongs to $A / \sim$ and contains $a$ , again by reflexivity.

Blocks are pairwise disjoint. Let $[a]$ and $[b]$ be blocks with $[a] \cap [b] \neq = \emptyset$ . By the lemma Classes coincide exactly for equivalent elements, condition (3) implies condition (2), so $[a] = [b]$ . Contrapositively, two blocks that are not equal have empty intersection, which is exactly condition 3 of the definition of Partition.

Part 2: a partition induces an equivalence. Let $P$ be a partition. By the definition of Partition, each $a \in A$ lies in exactly one block; write $B (a)$ for that block, so that $a \sim_{P} b$ means $B (a) = B (b)$ .

Reflexive. $B (a) = B (a)$ , so $a \sim_{P} a$ .

Symmetric. If $B (a) = B (b)$ then $B (b) = B (a)$ .

Transitive. If $B (a) = B (b)$ and $B (b) = B (c)$ then $B (a) = B (c)$ .

(Each is the corresponding property of equality between blocks; this is the proposition The kernel of a function applied to $B : A \to P$ , and the fact that $B$ is a well-defined function is precisely where "exactly one block" is used.)

Part 3, first direction: classes then same-block returns $\sim$ . Let $\sim$ be an equivalence relation, let $P = A / \sim$ , and let $\approx$ be the same-block relation of $P$ . By part 1, $P$ is a partition, and by part 1's first bullet the block containing $a$ is $[a]$ — it contains $a$ , and by disjointness it is the only block that does. So $a \approx b$ means $[a] = [b]$ , which by the lemma Classes coincide exactly for equivalent elements holds if and only if $a \sim b$ . Hence $\approx$ and $\sim$ contain the same pairs, so $\approx = \sim$ .

Part 3, second direction: same-block then classes returns $P$ . Let $P$ be a partition and $\sim_{P}$ its same-block relation, with $B (a)$ as above. We claim $[a] = B (a)$ for every $a$ , where $[a]$ is the $\sim_{P}$ -class.

If $b \in [a]$ then $b \sim_{P} a$ , that is $B (b) = B (a)$ ; since $b \in B (b)$ , we get $b \in B (a)$ . Conversely if $b \in B (a)$ then $B (a)$ is a block containing $b$ , and since $b$ lies in exactly one block, $B (b) = B (a)$ , so $b \sim_{P} a$ and $b \in [a]$ . Hence $[a] = B (a)$ .

It follows that $A / \sim_{P} = {[a] : a \in A} = {B (a) : a \in A}$ . Every $B (a)$ is a block of $P$ , so this collection is contained in $P$ ; conversely every block $B \in P$ is non-empty, so it contains some $a$ , and then $B = B (a)$ lies in the collection. Therefore $A / \sim_{P} = P$ .

Conclusion. Parts 1 and 2 give maps in both directions between equivalence relations on $A$ and partitions of $A$ , and part 3 shows each composite is the identity. A pair of mutually inverse maps is a bijection.∎

Remark. Note where non-emptiness of blocks was used: only in the very last step, to recover $P$ from the classes. Allow $\emptyset$ as a block and the correspondence stops being injective, since $P$ and $P \cup {\emptyset}$ would induce the same relation. Small hypotheses of this kind usually earn their place at exactly one point in a proof, and finding that point is how you tell whether a hypothesis is needed.

Definition 3.35 (Quotient set). The set $A / \sim$ of equivalence classes is called the quotient of $A$ by $\sim$ . The map $π : A \to A / \sim$ with $π (a) = [a]$ is the canonical projection.

Corollary 3.36 (Every equivalence is a kernel). Every equivalence relation $\sim$ on $A$ is the kernel of a function, namely of the canonical projection $π : A \to A / \sim$ .

Proof. By definition $π (a) = π (b)$ means $[a] = [b]$ , which by the lemma Classes coincide exactly for equivalent elements is equivalent to $a \sim b$ . So the kernel of $π$ , in the sense of the proposition The kernel of a function, is exactly $\sim$ .∎

Together with that proposition this closes the circle: equivalence relations, partitions, and "group by a computed value" are three descriptions of one idea. A database index on a column is a partition of the rows; the equivalence relation is "these rows agree in that column"; the quotient set is the set of distinct keys.

Definition 3.37 (Bell and Stirling numbers). The Bell number $B_{n}$ is the number of partitions of an $n$ -element set, and the Stirling number of the second kind $S (n, k)$ is the number of partitions into exactly $k$ non-empty blocks. Thus

B_{n} = k = 0 \sum n S (n, k) .

Corollary 3.38 (Counting equivalence relations). The number of equivalence relations on an $n$ -element set is $B_{n}$ , and the number with exactly $k$ classes is $S (n, k)$ .

Proof. By the theorem Equivalence relations are partitions, the map sending an equivalence relation to its set of classes is a bijection onto the partitions of $A$ , so the two collections have the same size, which is $B_{n}$ by definition. The bijection sends an equivalence with $k$ classes to a partition with $k$ blocks and back, so it restricts to a bijection between those subcollections, giving $S (n, k)$ .∎

The first Bell numbers are $B_{0} = 1$ , $B_{1} = 1$ , $B_{2} = 2$ , $B_{3} = 5$ , $B_{4} = 15$ , $B_{5} = 52$ , $B_{6} = 203$ . Compare with the $2^{n^{2}}$ relations of the proposition How many relations a set carries: on a $4$ -element set, $15$ of the $65536$ relations are equivalences. The conditions are extremely restrictive, which is another way of saying that an equivalence relation carries a lot of structure.

Example 3.39 (Listing the equivalence relations on a three-element set). List all partitions of ${1, 2, 3}$ and confirm the count $B_{3} = 5$ . How many have exactly two blocks?

Solution.

One block: the only option is ${{1, 2, 3}}$ , so $S (3, 1) = 1$ .
Two blocks: one block is a pair and the other a singleton. Choosing the singleton in $3$ ways gives ${{1}, {2, 3}}$ , ${{2}, {1, 3}}$ , ${{3}, {1, 2}}$ , so $S (3, 2) = 3$ .
Three blocks: all singletons, ${{1}, {2}, {3}}$ , so $S (3, 3) = 1$ .
Total $1 + 3 + 1 = 5 = B_{3}$ , and exactly $3$ have two blocks.

The corresponding equivalence relations have $9$ , $5$ , $5$ , $5$ and $3$ pairs respectively — a relation with blocks of sizes $n_{1}, \dots, n_{k}$ has $\sum n_{i}^{2}$ pairs, since it is the union of the full relations on each block.□

Example 3.40 (Size of an equivalence relation as a set of pairs). An equivalence relation on a $7$ -element set has classes of sizes $3, 3, 1$ . How many ordered pairs does it contain?

Solution.

By the theorem Equivalence relations are partitions, $a \sim b$ holds exactly when $a$ and $b$ lie in the same class, so the relation is the disjoint union of $B \times B$ over the classes $B$ .
A class of size $m$ contributes $m^{2}$ pairs.
Total: $3^{2} + 3^{2} + 1^{2} = 9 + 9 + 1 = 19$ .

The smallest possible value for a $7$ -element set is $7$ (all singletons) and the largest is $49$ (one class), and every equivalence sits between.□

Example 3.41 (Rows of a database table). A table has $12$ rows and a column dept taking exactly $4$ distinct values, with $5$ , $4$ , $2$ and $1$ rows respectively. Describe the induced equivalence and give the size of the quotient set.

Solution.

Define $r \sim r^{'}$ when the two rows agree in dept. By the proposition The kernel of a function this is an equivalence relation, no verification needed.
Its classes are the four groups of rows, of sizes $5, 4, 2, 1$ , which sum to $12$ as a partition must.
The quotient set has one element per distinct value, so $∣ A / \sim ∣ = 4$ — which is precisely what a SELECT COUNT(DISTINCT dept) returns.

□

Exercises for §3.4 →

3.5Partial orders

Swap symmetry for antisymmetry and the character of the relation changes completely: instead of identifying elements, it ranks them.

Definition 3.42 (Partial order and poset). A relation $⪯$ on $A$ is a partial order if it is reflexive, antisymmetric and transitive. The pair $(A, ⪯)$ is a partially ordered set, or poset.

Elements $a, b$ are comparable if $a ⪯ b$ or $b ⪯ a$ , and incomparable otherwise. We write $a ≺ b$ for " $a ⪯ b$ and $a \neq = b$ ".

Proposition 3.43 (Three standard posets). Each of the following is a partial order:

$\subseteq$ on the power set $P (X)$ of any set $X$ ;
divisibility $∣$ on the positive integers $N$ ;
$\leq$ on $R$ .

Proof.

Reflexive: $S \subseteq S$ , since every element of $S$ is in $S$ . Antisymmetric: if $S \subseteq T$ and $T \subseteq S$ then $S$ and $T$ have the same elements, so $S = T$ by extensionality. Transitive: if $S \subseteq T \subseteq U$ and $x \in S$ , then $x \in T$ , hence $x \in U$ .
Reflexive: $a = a \cdot 1$ , so $a ∣ a$ . Transitive: if $b = aj$ and $c = bk$ then $c = a (jk)$ . Antisymmetric: if $a ∣ b$ and $b ∣ a$ with $a, b \geq 1$ , write $b = aj$ and $a = bk$ with $j, k \geq 1$ ; then $a = ajk$ , so $jk = 1$ , forcing $j = k = 1$ and $a = b$ . (The restriction to positive integers is essential: on $Z$ we have $2 ∣ - 2$ and $- 2 ∣ 2$ with $2 \neq = - 2$ , so divisibility on $Z$ is not antisymmetric.)
The three properties of $\leq$ on $R$ are standard: $a \leq a$ ; $a \leq b$ and $b \leq a$ give $a = b$ ; and $a \leq b \leq c$ gives $a \leq c$ .

∎

In (1) the sets ${1}$ and ${2}$ are incomparable, and in (2) the integers $4$ and $6$ are incomparable, neither dividing the other. In (3) no pair is incomparable, which is the extra condition that makes $\leq$ a total order — the subject of the next section.

Intuition. A partial order encodes constraints that must be respected while staying silent about everything else. "This task must finish before that one" is a constraint; two tasks with no dependency between them are incomparable, and the order deliberately declines to say which runs first. That silence is what lets a scheduler run them in parallel.

Definition 3.44 (Covering relation and Hasse diagram). In a poset $(A, ⪯)$ , we say $b$ covers $a$ , written $a ⋖ b$ , 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, placed so that $b$ sits higher than $a$ whenever $a ≺ b$ , and joins $a$ to $b$ by a line segment exactly when $a ⋖ b$ .

The Hasse diagram omits loops (implied by reflexivity) and every edge forced by transitivity, leaving only the covers. Nothing is lost: for a finite poset the full order is recovered by taking the reflexive transitive closure of the covering relation, since $a ≺ b$ holds exactly when an upward path of covers runs from $a$ to $b$ .

Figure 3.45. The Hasse diagram of the divisors of

12

ordered by divisibility. An upward path from

a

b

means

a ∣ b

; the absence of any path between

3

and

4

— or between

4

and

6

— records that those pairs are incomparable. The edges drawn are exactly the covers, so the edge from

1

12

implied by transitivity is deliberately absent.

Definition 3.46 (Extremal elements). Let $(A, ⪯)$ be a poset and $a \in A$ .

$a$ is maximal if no $b \in A$ satisfies $a ≺ b$ ; minimal if no $b$ satisfies $b ≺ a$ .
$a$ is a greatest element if $b ⪯ a$ for every $b \in A$ ; a least element if $a ⪯ b$ for every $b$ .

The distinction between maximal and greatest is the one students lose. Maximal means "nothing is above it"; greatest means "it is above everything". In a total order they coincide, which is why the difference is invisible until you meet a genuine poset.

Proposition 3.47 (Greatest implies maximal, and greatest is unique). Let $(A, ⪯)$ be a poset.

A greatest element, if one exists, is maximal.
There is at most one greatest element.
A maximal element need not be greatest.

Proof.

Let $a$ be greatest and suppose $a ≺ b$ for some $b$ . Since $a$ is greatest, $b ⪯ a$ ; combined with $a ⪯ b$ , antisymmetry gives $a = b$ , contradicting $a ≺ b$ , which requires $a \neq = b$ . So no such $b$ exists and $a$ is maximal.
Let $a$ and $a^{'}$ both be greatest. Then $a^{'} ⪯ a$ because $a$ is greatest, and $a ⪯ a^{'}$ because $a^{'}$ is greatest; antisymmetry gives $a = a^{'}$ .
Take $A = {1, 2, 3}$ ordered by divisibility. Then $2$ is maximal, since neither $1$ nor $3$ is a proper multiple of $2$ inside $A$ , and $3$ is maximal for the same reason. But neither is greatest, since $2 ∤ 3$ and $3 ∤ 2$ . Indeed part 2 already shows that two distinct maximal elements cannot both be greatest.

∎

Theorem 3.48 (Every finite non-empty poset has a maximal element). Let $(A, ⪯)$ be a poset with $A$ finite and non-empty. Then $A$ has at least one maximal element, and likewise at least one minimal element.

Proof. Suppose, for contradiction, that no element of $A$ is maximal. Pick any $a_{0} \in A$ , which is possible since $A \neq = \emptyset$ . Since $a_{0}$ is not maximal, there is $a_{1}$ with $a_{0} ≺ a_{1}$ . Since $a_{1}$ is not maximal, there is $a_{2}$ with $a_{1} ≺ a_{2}$ , and continuing we obtain an infinite sequence $a_{0} ≺ a_{1} ≺ a_{2} ≺ \dots$ .

All the $a_{i}$ are distinct. Indeed if $i < j$ then repeated transitivity along the chain gives $a_{i} ⪯ a_{j}$ , and in fact $a_{i} ≺ a_{j}$ : if $a_{i} = a_{j}$ then from $a_{i} ⪯ a_{i + 1}$ and $a_{i + 1} ⪯ a_{j} = a_{i}$ antisymmetry would force $a_{i} = a_{i + 1}$ , contradicting $a_{i} ≺ a_{i + 1}$ .

So $A$ contains infinitely many distinct elements, contradicting finiteness. Hence some element is maximal. The statement about minimal elements is the same argument applied to the reverse order $⪰$ , which is a partial order because reflexivity, antisymmetry and transitivity are each unchanged when both coordinates are swapped.∎

Remark. Finiteness is not a technicality here. The poset $(Z, \leq)$ has no maximal element, and the poset of finite subsets of $N$ ordered by $\subseteq$ has none either. What the proof actually needs is that no infinite strictly ascending chain exists, a condition called the ascending chain condition, which finite posets satisfy automatically.

Example 3.49 (Extremal elements of a divisibility poset). In the poset $({2, 3, 4, 6, 9, 12}, ∣)$ , list the minimal elements, the maximal elements, and say whether a greatest element exists.

Solution.

Minimal: an element is minimal when nothing else in the set properly divides it. Nothing in the set divides $2$ or $3$ other than themselves, so $2$ and $3$ are minimal. Every other element is a proper multiple of $2$ or of $3$ , so the minimal elements are $2, 3$ — two of them.
Maximal: nothing in the set is a proper multiple of $9$ , and nothing is a proper multiple of $12$ . But $4 ∣ 12$ and $6 ∣ 12$ , so $4$ and $6$ are not maximal. The maximal elements are $9, 12$ .
A greatest element would have to be a multiple of every element, in particular of both $9$ and $12$ , hence of $36$ , which is not in the set. Moreover by the proposition Greatest implies maximal, and greatest is unique a greatest element would be the unique maximal element, and there are two. So no greatest element exists.

□

Definition 3.50 (Chains and antichains). In a poset, a chain is a subset in which every two elements are comparable, and an antichain is a subset in which every two distinct elements are incomparable. The height of a finite poset is the size of its largest chain, and its width is the size of its largest antichain.

Example 3.51 (A chain and an antichain in the subsets of a three-set). In $(P ({1, 2, 3}), \subseteq)$ , give a chain of maximum size and an antichain of maximum size.

Solution.

A chain must be a nested family; each step up can add at least one element, and going from $\emptyset$ to ${1, 2, 3}$ takes three steps. So $\emptyset \subset {1} \subset {1, 2} \subset {1, 2, 3}$ is a chain of size $4$ , and no chain is longer, since the sizes of the sets in a chain are strictly increasing integers between $0$ and $3$ .
The three two-element subsets ${1, 2}, {1, 3}, {2, 3}$ are pairwise incomparable, giving an antichain of size $3$ . So is the family of singletons. No antichain of size $4$ exists here — that is Sperner's theorem, whose answer $(1 3) = 3$ matches.
So the height is $4$ and the width is $3$ .

□

Exercises for §3.5 →

3.6Total orders, linear extensions and Zorn's lemma

Definition 3.52 (Total order). A partial order $⪯$ on $A$ is a total order (or linear order) if every two elements are comparable: for all $a, b \in A$ , either $a ⪯ b$ or $b ⪯ a$ . A totally ordered set is also called a chain.

Equivalently, a total order is a partial order whose only antichains are the subsets with at most one element. The usual order on $N$ , $Z$ , $Q$ and $R$ is total; so is dictionary order on strings, and so is chronological order on timestamps. Subset inclusion and divisibility are not.

Proposition 3.53 (Totality strengthens antisymmetry to trichotomy). If $⪯$ is a total order on $A$ , then for all $a, b \in A$ exactly one of $a ≺ b$ , $a = b$ , $b ≺ a$ holds.

Proof. At least one. By totality, $a ⪯ b$ or $b ⪯ a$ . In the first case either $a = b$ or $a ≺ b$ ; in the second either $a = b$ or $b ≺ a$ .

At most one. If $a = b$ then neither $a ≺ b$ nor $b ≺ a$ can hold, since both require $a \neq = b$ . And $a ≺ b$ and $b ≺ a$ cannot both hold: they give $a ⪯ b$ and $b ⪯ a$ , so $a = b$ by antisymmetry, contradicting $a \neq = b$ .∎

Definition 3.54 (Linear extension). A linear extension of a poset $(A, ⪯)$ is a total order $\leq^{*}$ on the same set $A$ such that $a ⪯ b$ implies $a \leq^{*} b$ . Producing one from a finite poset is called topological sorting.

Theorem 3.55 (Every finite poset has a linear extension). Let $(A, ⪯)$ be a poset with $A$ finite. Then a linear extension of $⪯$ exists. Concretely, repeatedly extracting a minimal element from what remains produces a listing $a_{1}, a_{2}, \dots, a_{n}$ of $A$ such that $a_{i} ⪯ a_{j}$ implies $i \leq j$ .

Proof. Induct on $n = ∣ A ∣$ .

Base case. If $n = 0$ the empty order is a linear extension, vacuously.

Inductive step. Let $n \geq 1$ and assume the result for all posets with fewer than $n$ elements. Since $A$ is finite and non-empty, the theorem Every finite non-empty poset has a maximal element supplies a minimal element; call it $m$ .

Let $A^{'} = A ∖ {m}$ and let $⪯^{'}$ be the restriction of $⪯$ to $A^{'}$ . Restricting a partial order to a subset again gives a partial order, since reflexivity, antisymmetry and transitivity are statements about elements that remain true when fewer elements are available. As $∣ A^{'} ∣ = n - 1$ , the induction hypothesis gives a listing $a_{2}, \dots, a_{n}$ of $A^{'}$ with $a_{i} ⪯ a_{j} ⟹ i \leq j$ for $i, j \geq 2$ .

Set $a_{1} = m$ and consider the listing $a_{1}, a_{2}, \dots, a_{n}$ of $A$ . We must check that $a_{i} ⪯ a_{j}$ implies $i \leq j$ . If $i, j \geq 2$ this is the induction hypothesis. If $i = 1$ then $i \leq j$ holds automatically. The remaining case is $j = 1$ and $i \geq 2$ : then $a_{i} ⪯ m$ with $a_{i} \neq = m$ , that is $a_{i} ≺ m$ , contradicting minimality of $m$ . So this case does not occur.

Finally, define $a_{i} \leq^{*} a_{j}$ to mean $i \leq j$ . This is a total order, being a copy of the usual order on ${1, \dots, n}$ transported along the bijection $i \mapsto a_{i}$ , and by the property just verified $a ⪯ b$ implies $a \leq^{*} b$ . Hence $\leq^{*}$ is a linear extension.∎

Intuition. The proof is a program. Keep a set of "ready" items — those with no unmet prerequisite, that is, the minimal elements — emit one, delete it, and repeat. That is Kahn's algorithm, and the theorem says it never gets stuck on a finite poset: a non-empty remainder always has a minimal element to emit. A scheduler that does get stuck is looking at a digraph with a cycle, which is therefore not a poset at all, since a cycle $a ≺ b ≺ a$ violates antisymmetry.

Example 3.56 (Counting linear extensions). The poset on ${a, b, c, d}$ has $a ≺ b$ , $a ≺ c$ , $b ≺ d$ and $c ≺ d$ (plus what reflexivity and transitivity force), with $b$ and $c$ incomparable. How many linear extensions does it have?

Solution.

A linear extension is an ordering of the four elements respecting all constraints. Since $a ≺ b ≺ d$ and $a ≺ c ≺ d$ , the element $a$ must come first and $d$ last.
That leaves $b$ and $c$ in the two middle positions, in either order, and both choices respect every constraint because $b$ and $c$ are incomparable.
So there are $2$ linear extensions: $a, b, c, d$ and $a, c, b, d$ .

This poset is the "diamond". Contrast the four-element antichain, which has $4! = 24$ extensions, and the four-element chain, which has exactly $1$ : the number of extensions measures how much freedom the order leaves.□

Example 3.57 (Topological sort of a dependency graph). A package manager must install packages with these direct dependencies: $B$ needs $A$ ; $C$ needs $A$ ; $D$ needs $B$ and $C$ ; $E$ needs $C$ . Give an installation order, and count how many valid orders exist.

Solution.

Take the reflexive transitive closure of the dependency digraph; it is a partial order because the digraph is acyclic. Minimal elements are packages with no unmet dependency.
Run the extraction: only $A$ is minimal, so emit $A$ . Now $B$ and $C$ are minimal; emit $B$ , then $C$ ; now $D$ and $E$ are minimal; emit $D$ , then $E$ . The order $A, B, C, D, E$ works.
Counting all valid orders: $A$ must be first. Of the remaining $4! = 24$ arrangements of $B, C, D, E$ , we need $B$ before $D$ , $C$ before $D$ and $C$ before $E$ . Enumerating the orders of $B, C, D, E$ that satisfy all three gives $BC D E$ , $BCE D$ , $CB D E$ , $CBE D$ , $CEB D$ — five of them. So there are $5$ valid installation orders.

□

Theorem 3.58 (A finite total order is a numbering). Let $(A, ⪯)$ be a totally ordered set with $∣ A ∣ = n$ . Then there is a bijection $f : A \to {1, 2, \dots, n}$ such that

a ⪯ b ⟺ f (a) \leq f (b) .

Such an $f$ is unique, so up to relabelling there is exactly one total order on an $n$ -element set.

Proof. Existence. Apply the theorem Every finite poset has a linear extension to $(A, ⪯)$ , obtaining a listing $a_{1}, \dots, a_{n}$ with $a_{i} ⪯ a_{j} ⟹ i \leq j$ , and set $f (a_{i}) = i$ . This $f$ is a bijection onto ${1, \dots, n}$ because the listing enumerates each element of $A$ exactly once.

It remains to prove the equivalence. The forward implication $a ⪯ b ⟹ f (a) \leq f (b)$ is the property of the listing. For the converse, suppose $f (a_{i}) \leq f (a_{j})$ , that is $i \leq j$ . If $i = j$ then $a_{i} = a_{j}$ and $a_{i} ⪯ a_{j}$ by reflexivity. If $i < j$ , totality gives $a_{i} ⪯ a_{j}$ or $a_{j} ⪯ a_{i}$ ; in the latter case the forward implication would give $j \leq i$ , contradicting $i < j$ . So $a_{i} ⪯ a_{j}$ .

(This is the step where totality is indispensable. For a general poset the listing produced by topological sorting satisfies only the forward implication, and indeed the diamond poset above has two different listings, so no such $f$ can be canonical.)

Uniqueness. Suppose $f$ and $g$ both have the stated property, and suppose $f \neq = g$ . Among the elements where they differ, and using the total order on ${1, \dots, n}$ , pick $a$ with $f (a)$ least. Let $k = f (a)$ . The set ${b \in A : b ⪯ a}$ is mapped by $f$ onto ${1, \dots, k}$ : it is mapped into that set by the stated property, and onto it because $f$ is a bijection and any $c$ with $f (c) \leq k$ satisfies $c ⪯ a$ . The same argument applies to $g$ , so both $f$ and $g$ send $a$ to the size of ${b : b ⪯ a}$ , that is $f (a) = g (a)$ — contradicting the choice of $a$ . Hence $f = g$ .∎

The theorem is the reason sorting is a well-posed problem. Whatever finite set of comparable items you are handed — version numbers, timestamps, strings — there is exactly one arrangement consistent with the order, so "sort this list" has a single right answer, and any two correct sorting algorithms must produce the same output.

Definition 3.59 (Well-order). A total order on $A$ is a well-order if every non-empty subset of $A$ has a least element.

Proposition 3.60 (Finite total orders are well-orders). Every total order on a finite set is a well-order.

Proof. Let $S \subseteq A$ be non-empty with $A$ finite. Then $(S, ⪯)$ is a finite non-empty poset, so by the theorem Every finite non-empty poset has a maximal element it has a minimal element $m$ . Since $⪯$ is total, every $s \in S$ is comparable to $m$ , and $m ⪯ s$ must hold — otherwise $s ≺ m$ , contradicting minimality. So $m$ is a least element of $S$ .∎

$(N, \leq)$ is well-ordered, which is exactly the principle that makes induction and "least counterexample" arguments work. $(Z, \leq)$ is not, since $Z$ itself has no least element, and $((0, 1), \leq)$ is not, since the interval has no least element either: for any candidate $x$ , the number $x /2$ is smaller and still in the interval. Both are total orders, so well-ordering is a strictly stronger condition.

Theorem 3.61 (Zorn's lemma, stated without proof). Let $(A, ⪯)$ be a non-empty poset in which every chain has an upper bound in $A$ . Then $A$ has a maximal element.

Remark. Zorn's lemma is the infinite analogue of the theorem Every finite non-empty poset has a maximal element, and it is emphatically not a theorem of the kind proved in this chapter: it is equivalent to the axiom of choice and to the well-ordering theorem (that every set admits a well-order), and it is proved — or adopted — in Set Theory, not here. No argument in this chapter uses it, and none needs to, because every poset we meet is finite. Where it does earn its keep is in algebra and analysis: that every vector space has a basis, and that every non-trivial ring has a maximal ideal, are Zorn's lemma applied to a poset of subsets ordered by inclusion.

Example 3.62 (Version ordering). Semantic versions are compared by major, then minor, then patch. Is this a total order on a finite set of versions, and what is the first version in the list $1.2.0$ , $1.10.3$ , $1.2.9$ , $0.9.9$ ?

Solution.

Comparison is lexicographic on triples of integers. Given two distinct versions, the first coordinate where they differ decides, so every pair is comparable and the order is total; reflexivity, antisymmetry and transitivity are inherited coordinatewise.
By the theorem A finite total order is a numbering, the four versions have a unique correct arrangement.
Compare major numbers first: $0.9.9$ has major $0$ , the others have major $1$ , so $0.9.9$ is least.

The classic bug is comparing versions as strings, which puts $1.10.3$ before $1.2.0$ because the character 1 precedes 2. Lexicographic order on strings and lexicographic order on tuples of integers are different total orders on the same set.□

Exercises for §3.6 →

Common Mistakes

Treating "symmetric" and "antisymmetric" as opposites. The proposition Independence of the five properties exhibits a relation that is both (any subset of the diagonal) and one that is neither. The same applies to reflexive and irreflexive: a relation with some loops but not all is neither.
"Symmetric plus transitive implies reflexive." The argument " $a R b$ , so $b R a$ , so $a R a$ " silently assumes that $a$ is related to something. The relation ${(1, 1)}$ on ${1, 2, 3}$ is symmetric and transitive but not reflexive.
Computing a transitive closure with one pass. Adding every shortcut $(a, c)$ for existing pairs $(a, b), (b, c)$ does not in general produce a transitive relation, because the new pairs create new two-step paths. The closure is a union over all powers, bounded by $n$ terms on an $n$ -element set.
Confusing maximal with greatest. Maximal means nothing is above it; greatest means it is above everything. A poset can have many maximal elements and no greatest one, as in $({2, 3}, ∣)$ .
Counting relations instead of pairs. On an $n$ -set there are $2^{n^{2}}$ relations but only $n^{2}$ pairs available; and an equivalence relation with class sizes $n_{1}, \dots, n_{k}$ contains $\sum n_{i}^{2}$ pairs, not $k$ or $n$ .
Forgetting that a class is a set, not an element. $[a]$ is a subset of $A$ ; $π (a) = [a]$ lives in the quotient $A / \sim$ . Writing $a \in A / \sim$ is a type error.
Allowing the empty block in a partition. Non-emptiness is what makes the correspondence of the theorem Equivalence relations are partitions a bijection rather than merely a surjection.
Assuming every digraph gives a poset. A digraph with a directed cycle through two distinct vertices violates antisymmetry, so no topological sort exists — which is exactly what a build tool reports as a circular dependency.
Expecting a maximal element in an infinite poset. The theorem needs finiteness (or the ascending chain condition). In the infinite case you need Zorn's lemma, and Zorn's lemma has a hypothesis — every chain has an upper bound — that must be checked.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter