Science Fair Project Encyclopedia
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.
- x0Rx1, x1Rx2, …, xn−1Rxn, and xnRy
- Formal notation:
- (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.
Demonstration that T is the smallest transitive relationship containing R
Let A be any set of elements.
Supposition: GA transitive relationship RAGA TAGA. So, (a,b)GA. So, that particular (a,b)RA.
Now, by definition of T, we know that n (a,b)RnA. Then, i, i < n eiA. So, there is a path from a to b like this: aRAe1RA...RAe(n-1)RAb.
But, by transitivity of GA on RA, i, i < n (a,ei)GA, so (a,e(n-1))GA (e(n-1),b)GA, so by transitivity of GA, we get (a,b)GA. Absurd
Therefore, (a,b)AA, (a,b)TA (a,b)GA. This means that TG, for any transitive G containing R. So, T is the smallest transitive relationship containing R.
If R is transitive, then R = T.
- 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."
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).
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.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details