Results 1 to 2 of 2

Math Help - Prove a transitive closure

  1. #1
    Newbie
    Joined
    May 2012
    From
    Atlanta
    Posts
    12

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Prove a transitive closure

    Quote Originally Posted by troe View Post
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Transitive Closure
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2010, 07:33 AM
  2. Determining transitive closure and prove
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 27th 2009, 10:01 AM
  3. Transitive closure relation.
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 8th 2009, 04:38 AM
  4. Transitive Closure in FOL and Prolog
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 22nd 2009, 03:06 AM
  5. Transitive closure
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 15th 2008, 12:06 AM

Search Tags


/mathhelpforum @mathhelpforum