Transitive Closure

• Oct 26th 2010, 06:07 PM
veronicak5678
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?
• Oct 27th 2010, 06:33 AM
emakarov
Quote:

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?