# Math Help - Transitive Closure

1. ## Transitive Closure

Let R be a relation on the set A. Define Tr = {(x,y) element of AxA | for some natural number n, there exist a0=x, a1, a2, ..., an = y element of A such that (a0, a1), (a1, a2),..., (an-1, an) element of R}.

Prove that R is transitive. (Tr is the transitive closure of R.)

I really don't know how to prove this. I know that if it is transitive, (a,b), (b,c) element of Tr --> (a,c) element of Tr. Then what?

2. I know that if it is transitive, (a,b), (b,c) element of Tr --> (a,c) element of Tr.
The implication here goes both ways, i.e., if (a,b) in Tr and (b,c) in Tr implies (a,c) in Tr for all a, b, c, then Tr is transitive. So, this (the premise in the previous sentence) is what you need to show.

Fix arbitrary a, b, and c and assume that (a,b) is in Tr and (b,c) is in Tr. Write what this means according to the definition of Tr. Then write, again according to the definition, what is means for (a,c) to be in Tr. Can you show this latter fact from the previous two?