Transitive closure

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R (Lidl and Pilz 1998:337). If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation. For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y", then the transitive closure of R on X is the relation "it is possible to fly from x to y in one or more flights."

Transitive relations and examples

A relation R on a set X is transitive if, for all x,y,z in X, whenever x R y and y R z then x R z. Examples of transitive relations include the equality relation on any set, the "less than or equal" relation on any linearly ordered set, and the relation "x was born before y" on the set of all people.

One example of a non-transitive relation is "city x can be reached via a direct flight from city y" on the set of all cities. Simply because there is a direct flight from one city to a second city, and a direct flight from the second city to the third, does not imply there is a direct flight from the first city to the third. The transitive closure of this relation is a different relation, namely "there is a sequence of direct flights that begins at city x and ends at city y". Every relation can be extended in a similar way to a transitive relation.

Existence and description

For any relation R, the transitive closure of R always exists. To see this, note that the intersection of any family of transitive relations is again transitive. Furthermore, there exists at least one transitive relation containing R, namely the trivial one: X × X. The transitive closure of R is then given by the intersection of all transitive relations containing R.

We can describe the transitive closure of R in more concrete terms as follows, intuitively constructing it step by step. To start, define

and, for i > 0,

Each set in this construction takes the relation from the previous set, and adds any new elements necessary to make chains that are "one step" more transitive. The relation T is made by taking all of the together, which we write as

To show that T is the transitive closure of R, we must show that it contains R, that it is transitive, and that it is the smallest set with both of those characteristics.

• : T contains all of the , so in particular T contains R.
• T is transitive: every element of T is in one of the , so T must be transitive by the following reasoning: if and , then (and thus in T) due to the definition of .
• T is minimal: Let G be any transitive relation containing R, we want to show that . It is sufficient to show that for every i > 0, . Well, since G contains R, . And since G is transitive, whenever , according to the construction of and what it means to be transitive. Therefore, by induction, G contains every , and thus also T.

Uses

Note that the union of two transitive relations need not be transitive. To preserve transitivity, one must take the transitive closure. This occurs, for example, when taking the union of two equivalence relations or two preorders. To obtain a new equivalence relation or preorder one must take the transitive closure (reflexivity and symmetry—in the case of equivalence relations—are automatic).

The transitive closure of a directed acyclic graph or DAG is the reachability relation of the DAG and a strict partial order.

Graph theory

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed, as depicted in the following figure, in an O(1) operation one may determine that node d is reachable from node a. The data structure is typically stored as a matrix, so if matrix[1][4] = 1, then it is the case that node 1 can reach node 4 through one or more hops.

Relationship to complexity

In computational complexity theory, the complexity class NL corresponds precisely to the set of logical sentences expressible using first-order logic together with transitive closure. This is because the transitive closure property has a close relationship with the NL-complete problem STCON for finding directed paths in a graph. Similarly, the class L is first-order logic with the commutative, transitive closure. When transitive closure is added to second-order logic instead, we obtain PSPACE.

Algorithms

Efficient algorithms for computing the transitive closure of a graph can be found here. The simplest technique is probably the Floyd–Warshall algorithm. The fastest worst-case methods, which are not practical, reduce the problem to matrix multiplication.

See also

• Transitive reduction (a smallest relation having the transitive closure of R as its transitive closure)
• Symmetric closure
• Reflexive closure

References

• Lidl, R. and Pilz, G., 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6

External links

• "Transitive closure and reduction]", The Stony Brook Algorithm Repository, Steven Skiena .