Transitive closure

From Wikipedia, the free encyclopedia

This article is about the transitive closure of a binary relation. For the transitive closure of a set, see transitive set.

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R.

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. Define a relation T on X by saying xTy iff there exists a finite sequence of elements (x_i) such that x = x₀ and

x₀Rx₁, x₁Rx₂, …, x_n−1Rx_n, and x_nRy

Formal notation: $R^+ = \bigcup_{i\in\mathbb{N}} R^i$

(for more info, see function composition)

It is easy to check that the relation T is transitive and contains R. Furthermore, any transitive relation containing R must also contain T, so T is the transitive closure of R.

1 Demonstration that T is the smallest transitive relationship containing R
- 1.1 Corollary
2 Examples
3 Uses
4 Relationship to complexity
5 Related concepts
6 Algorithms

[edit] Demonstration that T is the smallest transitive relationship containing R

Let A be any set of elements.

Supposition: $\exists$ G_A transitive relationship $\left / \right .$ R_A $\subseteq$ G_A $\wedge$ T_A $\not\subseteq$ G_A. So, $\exists$ (a,b) $\not\in$ G_A. So, that particular (a,b) $\not\in$ R_A.

Now, by definition of T, we know that $\exists$ n $\in \mathbb{N} \left / \right .$ (a,b) $\in$ Rⁿ_A. Then, $\forall$ i $\in \mathbb{N}$ , i $<$ n $\Rightarrow$ e_i $\in$ A. So, there is a path from a to b like this: aR_Ae₁R_A...R_Ae_(n-1)R_Ab.

But, by transitivity of G_A on R_A, $\forall$ i $\in \mathbb{N}$ , i $<$ n $\Rightarrow$ (a,e_i) $\in$ G_A, so (a,e_(n-1)) $\in$ G_A $\wedge$ (e_(n-1),b) $\in$ G_A, so by transitivity of G_A, we get (a,b) $\in$ G_A. A Contradiction of (a,b) $\not\in$ G_A.

Therefore, $\forall$ (a,b) $\in$ A $\times$ A, (a,b) $\in$ T_A $\Rightarrow$ (a,b) $\in$ G_A. This means that T $\subseteq$ G, for any transitive G containing R. So, T is the smallest transitive relationship containing R.

[edit] Corollary

If R is transitive, then R = T.

[edit] Examples

If X is the set of humans (alive or dead) and R is the relation 'parent of', then the transitive closure of R is the relation "x is an ancestor of y."
If X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the transitive closure of R is the relation "it is possible to fly from x to y in one or more flights."

[edit] Uses

Note that the union of two transitive relations need not be transitive. In order to preserve transitivity one must take the transitive closure. This occurs, for example, when taking the union of two equivalence relations or two preorders. In order 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).

[edit] 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.

[edit] Related concepts

The transitive reduction of a relation R is the smallest relation having the transitive closure of R as its transitive closure. It is not unique in general.

[edit] Algorithms

Efficient algorithms for computing the transitive closure of a graph can be found here. The simplest technique is probably the Floyd-Warshall algorithm.

Retrieved from "http://en.wikipedia.org../../../t/r/a/Transitive_closure.html"

Categories: Mathematical relations | Closure operators