Thread: 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₂,…x_n, such that x = x₁, x₁Rx₂, x₂Rx₃, …, x_n-1Rx_n = y

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₂,…x_n, such that x = x₁, x₁Rx₂, x₂Rx₃, …, x_n-1Rx_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?