Results 1 to 3 of 3

Math Help - Proof concerning a transitive closure

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Proof concerning a transitive closure

    Problem Statement:

    Suppose R is a relation on A and let S be the transitive closure of R. Prove that Dom(S) = Dom(R) and Ran(S) = Ran(R).

    *Dom() signifies the domain of the specified relation. Ran() signifies the range of the specified relation.*


    My attempt thus far:

    Let M = {T ⊆ A x A | R ⊆ T and T is transitive}. I have already shown (in a different exercise) that ∩M is the transitive closure of R (so S = ∩M).


    Let x ∈ Dom(S). Then there is some y ∈ A such that (x,y) ∈ S = ∩M. This means (∀K ∈ M)((x,y) ∈ K). We must show x ∈ Dom(R), which means there is some z ∈ A such that (x,z) ∈ R... (and this is where i can't seem to find how to proceed)


    As you can see, I am trying to prove the two conjuncts separately. I am proving the equalities by proving that each side is a subset of the other. I can prove the opposite direction- Dom(R) ⊆ Dom(S)- easily, but this one doesn't seem as easy. I'm sure it is analogous for the range equalities as well.


    Any insight is appreciated, thanks!
    Last edited by Syrus; August 23rd 2011 at 03:29 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Proof concerning a transitive closure

    Let T = {(x,y) ∈ A x A | x ∈ Dom(R) and y ∈ Ran(R)}.

    Clearly, if (x,y) ∈ R then (x,y) ∈ T. So R ⊆ T. Also, if (x,y),(y,z) ∈ T, then x ∈ Dom(R) since (x,y) ∈ T and similarly z ∈ Ran(R) since (y,z) ∈ T. Hence, (x,z) ∈ T, so T is transitive. Therefore, T ∈ M and so (x,y) ∈ T, which in turn implies x ∈ Dom(R).

    Whew! I've proven the other subset direction and it is much easier. I'm sure the range equality is analogous and can use the same relation T. On the other hand, I'm not sure how to feel. I'm definitely happy the problem has been solved, but I feel I shouldn't have struggled as much with it (I usually post problems for help only after pondering them for a few hours with no avail).
    Follow Math Help Forum on Facebook and Google+

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

    Re: Proof concerning a transitive closure

    Basically, the problem is to prove that a journey of a thousand miles begins with a single step

    This is obvious if a journey is defined as a sequence of steps, that is, if the transitive closure of R is defined as \bigcup_{i=1}^\infty R^n. If the transitive closure S is instead defined as the smallest transitive relation containing R, the problem reduces to proving that S\subseteq\bigcup_{i=1}^\infty R^n. This is proved by showing that \bigcup_{i=1}^\infty R^n contains R and is transitive.

    More generally, one can show that S\subseteq T for some relation T such that Dom(R) = Dom(T) and Ran(R) = Ran(T). The inclusion follows if in addition T contains R and is transitive. This is what you did, and your choice of T is quite elegant.

    Quote Originally Posted by Syrus View Post
    Clearly, if (x,y) ∈ R then (x,y) ∈ T. So R ⊆ T. Also, if (x,y),(y,z) ∈ T, then x ∈ Dom(R) since (x,y) ∈ T and similarly z ∈ Ran(R) since (y,z) ∈ T. Hence, (x,z) ∈ T, so T is transitive. Therefore, T ∈ M and so for all (x,y), if (x,y) ∈ S, then (x,y) ∈ T, which in turn implies x ∈ Dom(R).
    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. 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