Transitive Closure

The transitive closure of a relation is the smallest relation that contains the original relation and satisfies the transitivity condition. In other words, if the original relation has a → b and b → c connections, then the transitive closure always includes a → c as well.

Formal Definition

Here Rⁿ means the n-fold composition of the relation with itself. The transitive closure thus contains every connection that is reachable through finite-length chains from the original relation.

Example

Let A = {1,2,3,4}, R = { (1,2), (2,3), (3,4) }.

The transitive closure R⁺ = { (1,2), (2,3), (3,4), (1,3), (2,4), (1,4) }, because (1,3) follows from (1,2) and (2,3), (2,4) from (2,3) and (3,4), and (1,4) from (1,3) and (3,4) or longer chains.

Properties

• The transitive closure is always transitive.
• The transitive closure contains the original relation: R ⊆ R⁺.
• The transitive closure is the smallest transitive relation containing R.
• If R is already transitive, then R⁺ = R.

Graphical Interpretation

In graph theory, the transitive closure shows which points are reachable from a given point through paths. For example, if there is a path from A to B and B to C, then the transitive closure includes the connection from A to C.

Summary

The transitive closure is an extension of a relation that ensures transitivity, adding the fewest new elements possible. This concept is key in mathematics, algorithms, and graph theory.

Practice Exercise