1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Transitive closure of a relation

  1. Jan 14, 2009 #1
    1. The problem statement, all variables and given/known data
    Let R be a relation and define the following sequence
    [tex] R^0 = R [/tex]
    [tex] R^{i+1} = R^i \cup \{(s,u) \vert \exists t, (s,t) \in R^i, (t,u) \in R^i \} [/tex]
    [tex] R^{+} = \bigcup_{i} R_i [/tex]
    Prove that [tex] R^{+} [/tex] is the transitive closure.

    2. Relevant equations

    3. The attempt at a solution
    [tex] R = R_0 \subset R^{+} [/tex]

    2) show transitive
    Assume [tex] xR^{+}y,yR^{+}z[/tex] Then there is a
    k, such [tex] \exists u, xR^{k}u, uR^{k}y [/tex], and
    l, such [tex] \exists w, yR^{l}w, wR^{l}z [/tex]
    Therefore [tex] \exists m \geq k+l, xR^{k+l}z [/tex], because ??
    I don't know why I think this is the way to go, and I don't know how to finish this part of the proof. I will continue on. Please suggestions here??

    3) show smallest transitive relation (by induction)
    Let T be any other transitive relation containing R.
    (I) [tex] R^0 = R \subset T [/tex]
    (II) Assume [tex] R^n \subset T [/tex] and let [tex]xR{n+1}y[/tex]. Then there is a z, such that
    [tex] (x,y) \in R^n \cup \{(x,y) \vert (x,z) \in R^n, (z,y) \in R^m \} [/tex]
    Now if [tex] (x,y) \in R^n [/tex] then we are done. Assume [tex] (x,y) \in \{(x,y) \vert (x,z) \in R^n, (z,y) \in R^m \} [/tex]. Then because [tex] R^n \in T [/tex] , then [tex] (x,z) \in T, (z,y) \in T [/tex]. Then because T is transitive (x,y) is in T.
    ????Is my last statement here correct????

    Therefore [tex] R^n \subset T [/tex]

    Any help on the above two questions would be greatly appreciated.
  2. jcsd
  3. Jan 15, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi icantadd! :smile:
    Try it with k = l. :wink:
  4. Jan 15, 2009 #3
    Do you mean max{k,l}?
    I got credit for changing my answer to that. Meaning I had the answer right. I seem to have trouble in this area, a lot of times, I know that something is working, but I don't know how to justify it to myself. For example, with this problem I can look at it, and say "yes, that is obvious" and write a proof that is technically right, but then I look back at it and I don't know why. Why does that answer work? Because you are guaranteeing recursively that the relation is transitive one step at a time. So then I realize my question is okay, how do you know you are making the relation transitive one step at a time? And to that I simply answer, "because it is" and that just isn't good enough for me.

    How do I correctly state what I am thinking on this problem, what is it that makes this work?
  5. Jan 15, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    mmm … all I can suggest is that, in a problem like this, you start by translating the definition into words before you do anything else

    in this case, stare at the definition until you satisfy yourself that Rn is the "pairs of people with 2n degrees of connection" … that is, Bud know Fred knows … … … Ginger knows Lou (with 2n names)

    then you can safely predict what will happen, and translate it back into symbols :smile:
  6. Jan 15, 2009 #5
    Then (somewhat removed from the original question) it is appropriate to say something like,
    at R^n for any (a,b) there is a set[tex] \{(a,a_1) (a_1,a_2) , ... , (a_{n-1},b)\} [/tex]whose size is at most n.

    Back to the problem:
    At any rate, if i take m = max {k,l}, then clearly we have
    [tex]xR^{m}y[/tex] and also [tex] yR{m}z[/tex], and therefore in [tex]R^{m+1}[/tex] we will have [tex] xR^{m+1}z[/tex]. I think I am getting it. Thank you!
  7. Jan 15, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    Yes, that's exactly right! :biggrin:
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Transitive closure of a relation