# Prove a transitive closure

• Oct 30th 2012, 05:48 AM
troe
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 RT be the transitive closure of R . Prove that for all x and y in A, (x,y) ∈ RT if and only if there is a sequence of elements of A say x1, x2,…xn, such that x = x1, x1Rx2, x2Rx3, …, xn-1Rxn = y
• Oct 30th 2012, 08:12 AM
emakarov
Re: Prove a transitive closure
Quote:

Originally Posted by troe
Prove
Let R be a binary relation on a set A, and let RT be the transitive closure of R . Prove that for all x and y in A, (x,y) ∈ RT if and only if there is a sequence of elements of A say x1, x2,…xn, such that x = x1, x1Rx2, x2Rx3, …, xn-1Rxn = 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 RT as the smallest transitive relation containing R. Is this so?