Results 1 to 2 of 2

Math Help - Transitive Closure

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof concerning a transitive closure
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2011, 01:26 PM
  2. transitive closure, cardinality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 05:13 PM
  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