Closure as relation powers
R+ = R ∪ R² ∪ R³ ∪ ⋯
Each power represents paths of another length. A finite relation reaches a fixed point.
Transitive Closure Calculator for Binary Relations
Enter a finite relation
Use one ordered pair per line. The carrier set fixes the row and column order.
Private by design: labels and relation entries are processed on this device. They are not uploaded, saved, or added to the page URL.
Advertisement
What is the transitive closure of a relation?
For a binary relation R ⊆ A × A, the transitive closure R+ is the smallest transitive relation on A that contains every pair in R. A pair (x,z) belongs to R+ exactly when there is a nonempty chain from x to z.
Transitivity condition
(x,y),(y,z) ∈ R+ ⇒ (x,z) ∈ R+
Every two-step chain in the closure must contain its direct conclusion.
Reflexive-transitive closure
R* = IA ∪ R+
R* also adds all identity pairs. This calculator returns R+, not R*.
How the Warshall algorithm finds R+
The calculator first stores R as a Boolean matrix M. For each possible intermediate element k, it marks i → j reachable whenever both i → k and k → j are already reachable:
M[i,j] ← M[i,j] ∨ (M[i,k] ∧ M[k,j])
Original entries
Every 1 from the entered relation stays 1. Transitive closure only adds pairs; it never removes an original pair.
Implied entries
A highlighted added 1 means at least one nonempty path connects its row label to its column label.
Cycles and the diagonal
A diagonal pair (a,a) is added only when a nonempty cycle returns to a. An acyclic chain does not automatically add diagonal pairs.
Complexity
For n elements, the matrix uses O(n²) space and Warshall's algorithm uses O(n³) Boolean checks.
Transitive closure example
Let A = {a,b,c,d} and R = {(a,b),(b,c),(c,d),(d,b)}. The chain a → b → c adds (a,c), and continuing to d adds (a,d). Because b → c → d → b is a cycle, the closure also contains the diagonal pairs (b,b), (c,c), and (d,d).
| Source | Reachable in R+ | New pairs |
|---|---|---|
| a | b, c, d | (a,c), (a,d) |
| b | b, c, d | (b,b), (b,d) |
| c | b, c, d | (c,b), (c,c) |
| d | b, c, d | (d,c), (d,d) |
Input rules, assumptions, and limits
In ordered-pair mode, set labels are case-sensitive. List the carrier set with commas, semicolons, or line breaks, then put one pair on each relation line. Accepted pair styles are (a,b), [a,b], a,b, a -> b, and a → b. If the set field is blank, the calculator infers labels from pair endpoints in first-seen order.
In matrix mode, enter one row per line and separate entries with spaces or commas. The matrix must be square and contain only 0 and 1. Optional labels determine row and column names; when omitted, the calculator uses 1 through n. Duplicate pairs and labels are ignored and reported.
The empty relation is supported in ordered-pair mode. Its transitive closure is empty, whether the carrier set is empty or nonempty. In matrix mode, a nonempty carrier set must be represented by its square all-zero matrix.
The calculator supports up to 150 elements, 30,000 nonempty pair lines, and labels of 80 characters. These bounds cap a rendered matrix at 22,500 cells and prevent accidental extreme input from making the page unresponsive.
Relation and transitive-closure terminology follows Mathematics LibreTexts, “Properties of Relations”. The implementation uses the standard Boolean-matrix form of Warshall's algorithm.
Calculation note: representative chains, cycles, already-transitive relations, empty relations, invalid matrices, and exports are checked locally. Last reviewed: .
Transitive closure FAQ
What is the transitive closure of a relation?
The transitive closure R+ is the smallest transitive relation containing R. It preserves every original pair and adds exactly the pairs implied by nonempty relation chains.
How do you calculate a transitive closure?
Represent the relation as a Boolean matrix. For each intermediate element k, add i → j whenever i → k and k → j are reachable. After all intermediates have been considered, the matrix represents R+.
Does transitive closure include reflexive pairs?
Only when a diagonal pair was already present or a nonempty cycle makes an element reachable from itself. To add every identity pair regardless of cycles, use the reflexive-transitive closure R*.
What is the difference between R+ and R*?
R+ represents paths of length at least one. R* also permits length-zero paths, so R* = IA ∪ R+ and every diagonal pair is present.
Can I enter a relation as a matrix?
Yes. Choose 0–1 matrix, enter a square binary matrix with one row per line, and optionally provide the same number of labels. Spaces and commas are accepted between entries.
Is transitive closure the same as transitive reduction?
No. Closure adds all implied reachability pairs. Reduction removes redundant pairs while preserving reachability; it is a different operation and is not uniquely defined for every directed graph.
Does this calculator store my relation?
No. Parsing, closure calculation, copying, and CSV creation happen locally in your browser. The tool does not transmit or save the relation.