A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The transitive closure of a relation R is the smallest transitive relation containing R. It adds edges wherever there is a path in the graph representation of R. The transitive closure can be computed using matrix multiplication (reaching all paths) or using DFS/BFS for reachability queries.
From your study of binary relations, you know that a relation R on a set A is transitive if whenever (a, b) ∈ R and (b, c) ∈ R, it follows that (a, c) ∈ R. Many natural relations fail this property in their raw form. "Directly reports to" in an organization is not transitive: Alice reports to Bob, Bob reports to Carol, but Alice does not directly report to Carol. The transitive closure R⁺ fixes this by adding all the implied pairs — it is the smallest transitive relation that contains R. Applied to the example, R⁺ would include all pairs (a, b) where a is anywhere in b's chain of command, directly or indirectly.
The connection to graph theory, which you have seen as a soft prerequisite, makes this concrete. Represent the relation R as a directed graph: nodes are elements of A, and there is an edge from a to b whenever (a, b) ∈ R. Then (a, b) ∈ R⁺ if and only if there is a directed path from a to b in the graph. Computing the transitive closure is exactly the reachability problem: from each node, which other nodes can you reach by following directed edges? This is why DFS or BFS from every node correctly computes the transitive closure — you explore all reachable nodes from each starting point.
The matrix approach gives the same answer algebraically. Represent R as an n × n boolean matrix M where M[i][j] = 1 if (i, j) ∈ R. The matrix Mᵏ (under boolean multiplication, where 1+1=1) has a 1 in position (i,j) whenever there is a path of length exactly k from i to j. The transitive closure matrix is M¹ OR M² OR M³ OR ··· OR Mⁿ. Since any path that isn't a cycle has length at most n − 1, the series terminates at n. Warshall's algorithm implements this efficiently in O(n³), iterating over intermediate nodes and updating reachability in place.
The reflexive-transitive closure R* — your next topic — adds one more property: it includes all pairs (a, a) as well, encoding "can reach in zero or more steps." This is the relation that captures reachability including staying in place, and it arises naturally in formal language theory (as the Kleene star of a language) and in program verification (where R* over a transition relation describes all possible states reachable from a starting state). Understanding transitive closure is the prerequisite for reasoning about what states a system can reach, which is fundamental to model checking and formal verification.