Motivation
Equality is often too strict for a computation: two integers may be treated alike when they leave the same remainder, and two tasks may be constrained only by which must precede which. Both situations are described by a rule saying which ordered pairs of elements count as related.
Definitions
Definition 12.5.1
(Binary relation and arrow diagram)
A binary relation on a set is a subset of . Write when . The order of the pair matters. An arrow diagram represents each related pair by an arrow, including a loop for .
Definition 12.5.2
(Reflexive, symmetric, transitive and antisymmetric relations)
A relation is reflexive if for every , symmetric if implies , and transitive if and imply . It is antisymmetric if and together imply . Antisymmetry does not mean that every pair has an arrow in one direction: incomparable pairs are allowed. Each condition is a universal implication, so one counterexample disproves it; on the empty set all four conditions hold vacuously.
Common mistake
(Antisymmetric does not mean not symmetric)
Antisymmetry restricts pairs of distinct elements: they may not be related in both directions. It does not forbid symmetry. Equality on any set is both symmetric and antisymmetric, and so is the relation on . A relation with and is symmetric at that pair but fails antisymmetry, because .
Equivalence and partitions
Definition 12.5.3
(Equivalence relation, class and partition)
An equivalence relation is reflexive, symmetric and transitive. Its class at is . A partition of is a family of nonempty, pairwise disjoint subsets whose union is ; the empty family partitions the empty set.
Theorem 12.5.4
(Classes are exactly the blocks of a partition)
The distinct classes of an equivalence relation partition . Conversely, declaring two elements related exactly when they belong to the same block of a partition defines an equivalence relation.
Proof
(Classes cover, and overlapping classes coincide)
Every lies in by reflexivity, so the classes cover and are nonempty. If , then and . Symmetry gives , and transitivity gives . For any , we have and , so ; reversing the roles gives equality. Thus intersecting classes coincide. Conversely, belonging to the same block is reflexive and symmetric; if share a block and share a block, disjointness forces the blocks to be the same, proving transitivity.
Proof X-ray
Why one common element is enough
The non-obvious move is to use a common element as a bridge between and . Symmetry turns into , and transitivity composes with to give ; the same pattern shows that each class lies inside the other, so the argument closes with equality. Reflexivity is used only at the start, to make classes nonempty and covering. Symmetry cannot be dropped: on the relation is reflexive and transitive, with and , so these two classes overlap without being equal.
Definition 12.5.5
(Quotient set and representatives)
The set of distinct classes is the quotient set . A representative is a convenient name, not a unique element of its class. To define an operation on classes by choosing representatives, first prove that changing the representatives cannot change the resulting class.
Worked example 12.5.6
(Remainders and a well-defined operation)
For an integer , put when divides . Divisibility of , negation and sums proves reflexivity, symmetry and transitivity. There are classes, represented by . Define . If and , then divides , so : the result is independent of the chosen representatives.
Counterexample mode
A representative-dependent rule
On integers modulo , the proposed value is not a well-defined integer-valued function: , but the rule gives both and . A formula using a representative does not automatically define a function on classes.
Partial orders and dependencies
Definition 12.5.7
(Partial order, least and minimal elements)
A partial order is reflexive, antisymmetric and transitive. The pair is a poset. For example, inclusion orders subsets of a fixed set; divisibility orders positive integers. A least element is below every element; a minimal element has no distinct element below it. A least element, if present, is unique and minimal, but several minimal elements can exist without any least element.
Definition 12.5.8
(Strict order, covers and the Hasse diagram)
Write when and . For a finite poset, draw a Hasse diagram by omitting loops and transitive arrows: connect below when and no satisfies . Orient edges upward. Every strict comparison is recoverable by following upward edges: if a comparison is not a cover, insert an intermediate element and repeat; finiteness forces termination. The diagram is therefore a compact representation, not the complete list of related pairs.
Common mistake
(Reading a Hasse diagram as the whole relation)
The diagram omits loops and every pair that follows by transitivity. Under divisibility on , the relation holds although no edge joins and ; to recover a comparison, follow upward edges through intermediate elements. An edge, in turn, records only a cover, so the absence of a direct edge does not by itself mean that two elements are incomparable.
Theorem 12.5.9
(A finite poset has a linear extension)
Every finite poset admits a listing such that implies . The empty listing works when .
Proof
(Removing minimal elements one at a time)
If a nonempty finite poset had no minimal element, repeatedly choosing a strictly smaller element would eventually repeat an element. Transitivity would then give a strict cycle, contradicting antisymmetry. Choose a minimal element, list it first, remove it, and repeat on the remaining induced order. A removed element cannot have an unlisted strict predecessor, so every strict comparison respects the final order. This is the principle behind scheduling precedence constraints. A finite directed acyclic graph can be ordered by repeatedly removing a zero-indegree vertex; the reachability relation, including length-zero paths, is a partial order. With adjacency lists and maintained indegrees this takes time, counting each vertex and edge a constant number of times.
Proof X-ray
Where finiteness and antisymmetry enter
Each stage needs a minimal element, and that is where the hypotheses are used. In a finite poset, choosing strictly smaller elements forever must repeat one; transitivity turns the repeat into , which antisymmetry forbids. Finiteness cannot be dropped: with its usual order has no minimal element. The listing is correct because each listed element was minimal among those remaining, so every strict predecessor of it was listed earlier. Induction on the number of elements closes the argument.
Worked example 12.5.10
(Minimal does not mean least)
Order by divisibility. Both and are minimal; neither is below the other, so no least element exists. The covers are , , and . Both and are linear extensions. The comparison is still part of the relation even though its edge is omitted from the Hasse diagram.
Functions that respect a partition
A quotient is useful when the distinctions inside each class do not affect the answer to a question. Let send to , and let be a function. We would like to evaluate on a class by writing . This only makes sense if is constant on each class: whenever , the equality must hold. Notice the direction: the relation groups inputs, and the output must remain unchanged within each group. There is no requirement that inputs in different classes have different outputs.
Theorem 12.5.11
(The factorization criterion)
There is a function with if and only if implies . When it exists, is unique.
Proof
(Constant on classes is necessary and sufficient)
If such a function exists, then related inputs have the same class, so . Conversely, if is constant on classes, define to be for any . Every class is nonempty, and the hypothesis makes this value independent of the choice. The formula gives . Finally, every element of the quotient has the form , so the equation determines the value of on every possible input. This also works for : both and the induced function have empty domain.
Common mistake
(Reversing the factorization criterion)
The criterion asks that related inputs have equal outputs. It does not ask that unrelated inputs have different outputs: the constant function is constant on every class, so it factors through every quotient. Nor does factoring through mean that determines the classes; that happens only when the induced map on classes is injective.
Worked example 12.5.12
(Grouping strings by length)
Let be the set of finite binary strings, including the empty string , and let mean . Equality of lengths makes an equivalence relation. Each class contains all strings of one length; the class of length zero is . The function is constant on every class and factors through the quotient via . In contrast, , the number of ones in , does not factor: but and . A quotient can discard information needed by another task.
Definition 12.5.13
(Kernel relation)
Every function creates its own relation, the kernel relation : exactly when .
Theorem 12.5.14
(A function factors bijectively through its kernel)
The kernel relation is an equivalence relation on whose classes are the nonempty fibers . The induced map , , is a bijection. Conversely, every equivalence relation on is the kernel relation of the quotient map .
Proof
(Fibers as classes, and every relation as a kernel)
Equality of outputs is reflexive, symmetric and transitive, and the class of is the fiber . By the factorization criterion the map is well defined, because related inputs have equal outputs. It is surjective onto by the definition of image, and injective because means , that is, . Codomain elements never attained by do not produce empty classes, and for an empty domain the image and the quotient are both empty, so the bijection still exists. For the converse, means , which by the partition theorem holds exactly when .
Concept lensStructural
An equivalence relation as a labeling
The kernel statement gives a second description of the same object. A relation is a rule on pairs; its quotient map is a labeling of each element by its class, and is exactly the relation "has the same label". In this language, " respects " means that depends on only through the label , which is the factorization criterion read directly.
The criterion also explains why class operations need a compatibility proof. For a binary operation on , one may propose . This is well defined precisely when and imply . It is not enough to check a few preferred representatives: the condition quantifies over every pair of choices. The modular addition proof above verifies this condition, and the exercise on products of residues below verifies it for multiplication.
Building and reading dependency orders
A relation supplied as a list of arrows may fail to include consequences required by a partial order. For a finite acyclic directed graph, define when a directed path from to exists, allowing the path of length zero. The zero-length path supplies reflexivity; concatenating paths supplies transitivity. If reaches and reaches with , their paths contain a directed cycle, contradicting acyclicity. Thus reachability is antisymmetric. The original edges need not include all pairs in this order, but every original edge must point forward in every linear extension.
Theorem 12.5.15
(Topological orders exist exactly for acyclic graphs)
Let be a finite directed graph. If has no directed cycle, then reachability is a partial order whose linear extensions are exactly the listings in which every edge points forward. If has a directed cycle, no such listing exists. Repeatedly removing a vertex of indegree zero either lists all vertices or stops with remaining vertices that contain a directed cycle.
Proof
(Edges forward, cycles impossible, stuck means a cycle)
Every linear extension of the reachability order is a topological ordering of the graph. A topological ordering also respects every path, because each of its edges points forward, so the two descriptions give exactly the same valid listings. If the input graph contains a directed cycle, no such listing exists: following the cycle would force the first vertex to occur strictly before itself. For a finite graph, repeated zero-indegree removal either lists all vertices or gets stuck. If it gets stuck with vertices remaining, each remaining vertex has an incoming edge from a remaining vertex. Following such edges backwards must repeat a vertex, producing a directed cycle. This argument gives a failure certificate, rather than merely saying that the algorithm could not find an order.
Worked example 12.5.16
(Counting legal schedules)
Suppose tasks have only the direct constraints before , before , and before . Initially and are available. If is first, must be second, after which may appear in either order: and . If is first, the available tasks are . Choosing next gives or ; choosing next forces then , giving . These five are all the linear extensions. The enumeration branches on the next available task, so it neither loses a valid schedule nor counts one twice. An isolated task would be another available choice, not an impossible task.
A linear extension is one total ordering compatible with a partial order, not a proof that all incomparable tasks have an intrinsic ordering. In the example, and occur in both possible orders across different extensions. Conversely, precedes in every extension because it is an original constraint. A precedence graph may have many legal schedules, and listing all of them can require exponential output even when finding one takes linear time.
Counterexample mode
Reachability and an undirected cycle are different questions
The directed edges , , form a directed acyclic graph even though their underlying undirected graph is a triangle. Its only linear extension is . A directed cycle requires a consistently oriented route back to the start; an undirected cycle alone is not a contradiction in a dependency graph.
Exercises
Quick check
(On the integers let mean that is even. Find the classes and justify that is an equivalence relation.)
Solution · Answer
Reflexivity holds because is even. Symmetry holds because is even when is. Transitivity holds because is a sum of even integers. The classes are the set of even integers and the set of odd integers.
Quick check
(On let mean . Which of reflexivity, symmetry and transitivity hold?)
Solution · Answer
Symmetry holds. Reflexivity fails at every element. Transitivity fails because and hold but does not.
Quick check
(Under inclusion on , find the minimal and least elements and all linear extensions.)
Solution · Answer
Both singleton sets are minimal, and neither is least. There are exactly two linear extensions: the two singletons in either order, followed by .
Quick check
(Suppose and modulo . Prove that .)
Solution · Answer
Write . Both terms are divisible by , so . Thus multiplication, too, is well defined on residue classes.
Quick check
(Let and satisfy and . Give the kernel classes and the image. Is the induced map from the quotient onto the whole codomain surjective?)
Solution · Answer
The classes are and , and the image is . The induced map into misses , so it is not surjective onto the codomain, though it is bijective onto the image.
Quick check
(A directed graph has edges , and . Give all topological orders. What happens if the edge is added?)
Solution · Answer
Both and must occur before , and must follow ; the orders are and . Adding creates the directed cycle , so no topological order exists.
Quick check
(On integers modulo , does define a function from residue classes to residue classes? Explain why choosing another representative cannot change the answer.)
Solution · Answer
Yes. If divides , then it divides . Hence equivalent inputs yield equivalent outputs, and the factorization criterion gives a unique function on the quotient.