1. Not finding help here? Sign up for a free 30min 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!

Proof concerning a transitive closure

  1. Aug 23, 2011 #1
    1. The problem statement, all variables and given/known data

    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.*



    2. Relevant equations


    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).



    3. The attempt at a solution

    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 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!
     
  2. jcsd
  3. Aug 23, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Hi Syrus!

    There is another description of the transitive closure. This description will make this exercise very easy. Basically it is this

    If K is any relation, then we denote [itex]K^\circ=K\cup \{(x,z)~\vert~\exists y:~(x,y)\in K~\text{and}~(y,z)\in K\}[/itex]. Practically, this means that if we see (x,y) and (y,z) in K, then we adjoin the relation (x,z) to K.

    Now, define

    [tex]R_0=R,~R_1=R_0^\circ,~R_2=R_1^\circ,...,R_n=R_{n-1}^\circ,...[/tex]

    Then the transitive closure is

    [tex]M=\bigcup_{n\in \mathbb{N}}{R_n}[/tex]

    Can you prove this?? And does this make your question easier?
     
  4. Aug 23, 2011 #3
    Hey Micromass, thank you for your response!

    I believe your response deals with the definition of transitive closure that uses compositions of relations and proof via induction. It turns out this topic is addressed in a later section than that which this problem is from. I have since reviewed and understood that section, and as such, I respect and understand your post. At the same time, however, I am trying to do this exercise justice by attempting a proof using the definition of transitive closure provided within the corresponding text (which i stated above).

    But you are obviously well-informed regarding this subject!
     
  5. Aug 23, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, I thought that actually.

    Here's another thing to try. By contradiction. Assume that x is not in the domain of R, but suppose that x is in the domain of M (the transitive closure). Can we then not remove all relations with x as first argument and still have a transitive relation?
     
  6. Aug 23, 2011 #5
    So far I've got:

    To prove Dom(S) ⊆ Dom(R), suppose to the contrary there is some x ∈ A such that x ∈ Dom(S) and x ∉ Dom(R). Then there is some y ∈ A such that (x,y) ∈ S. Also,(∀z ∈ A)((x,z) ∉ R).

    Hmmm, still feeling a little stuck. I'm trying to produce a contradiction at this point.
     
    Last edited: Aug 23, 2011
  7. Aug 24, 2011 #6
    I need to learn from my mistakes! Look here: https://www.physicsforums.com/showthread.php?t=520630.

    In the last post of the thread linked above, I realized my difficulty with that exercise was I didn't make proper use of a given of the following form: (∀X ⊆ A)(statement). It turns out, as I discovered, that when this appears you must more or less "design" a set which has the specified properties and helps you solve the proof. This is the case here as well.

    As it turns out, the beginning of my original post was correct for this approach. That is,
    "Let x ∈ Dom(S). Then there is some y ∈ A such that (x,y) ∈ S = ∩M. This means (∀K ∈ M)((x,y) ∈ K)."

    Thus, it appears that if we can come up with any set K ∈ M, we can show that (x,y) ∈ K. Still, though, we'd have to somehow use this to conclude x ∈ Dom(R).

    Now, we must "construct" a set T which is an element of M. The criteria for being a member of M are (as in the original post) that R ⊆ T and T is transitive. But recall we also need this set T to somehow relate to R (in order to show x ∈ Dom(R)).

    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).
     
    Last edited: Aug 24, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook