Prove a transitive closure

Hello everyone. I have a proof that I am having trouble beginning. Should try to solve this proof directly or by induction?

Thanks.

__Prove__

Let R be a binary relation on a set A, and let R^{T} be the transitive closure of R . Prove that for all x and y in A, (x,y) ∈ R^{T } if and only if there is a sequence of elements of A say x_{1, }x_{2},…x_{n}, such that x = x_{1}, x_{1}Rx_{2}, x_{2}Rx_{3}, …, x_{n-1}Rx_{n} = y

Re: Prove a transitive closure

Quote:

Originally Posted by

**troe** __Prove__

Let R be a binary relation on a set A, and let R^{T} be the transitive closure of R . Prove that for all x and y in A, (x,y) ∈ R^{T } if and only if there is a sequence of elements of A say x_{1, }x_{2},…x_{n}, such that x = x_{1}, x_{1}Rx_{2}, x_{2}Rx_{3}, …, x_{n-1}Rx_{n} = y

The property that you need to prove is often given as a definition of transitive closure. Since you need to prove this, I guess you define R^{T} as the smallest transitive relation containing R. Is this so?