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!

If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexample

  1. Oct 10, 2011 #1
    1. The problem statement, all variables and given/known data
    Suppose R1 and R2 are relations on A. Therefore, R1 [itex]\subseteq[/itex]A X A
    and R2 [itex]\subseteq[/itex]A X A


    2. Relevant equations
    Let (x, y) and (y, z) [itex]\in[/itex]R1. Then since R1 is transitive, xR1y, and
    yR1z implies xR1z.

    Does R1\R2 mean: (x,y) [itex]\in[/itex]R1 [itex]\wedge[/itex] (x,y) [itex]\notin[/itex]
    R2?


    3. The attempt at a solution
    Any suggestions? I am losing what a relation R1 minus R2 means to prove or disprove that it is transitive?
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Oct 10, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    So [itex](x,y)\in R_1\setminus R_2[/itex] means [itex](x,y)\in R_1[/itex] and [itex](x,y)\notin R_2[/itex].

    So, you must prove that if [itex](x,y)\in R_1\setminus R_2[/itex] and [itex](y,z)\in R_1\setminus R_2[/itex], then [itex](x,z)\in R_1\setminus R_2[/itex].

    Try to prove it directly. If you're unable to, then try to find a counterexample.
     
  4. Oct 10, 2011 #3
    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    Let arbitrary (x, y) and (y,z) [itex]\in[/itex] R1\R2. This is equivalent to
    (x, y) [itex]\in[/itex] R1 [itex]\wedge[/itex] (x, y)[itex]\notin[/itex] R2 and
    (y, z) [itex]\in[/itex] R1 [itex]\wedge[/itex] (y, z)[itex]\notin[/itex] R2.

    So (x, y) and (y, z) [itex]\in[/itex]R1. Because R1 is transitive, (x, z) [itex]\in[/itex]R1.

    Since (x, y) [itex]\wedge[/itex] (y, z) [itex]\notin[/itex]R2, then (x, z) [itex]\notin[/itex]R2.

    Therefore, (x, z) [itex]\in[/itex]R1\R2. Since (x,y) and (y,z) were arbitrary elements of R1\R2, then if R1 and R2 are transitive, then R1\R2 must be transitive.
     
  5. Oct 10, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    Why??
     
  6. Oct 11, 2011 #5
    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    I had my doubts about this, but I was thinking if (x, y) [itex]\notin[/itex]R2 [itex]\wedge[/itex] (y, z)[itex]\notin[/itex]R2, since R2 is transitive, then (x, z) cannot be an element of R2.

    But I now think this is incorrect. Can I just say since (x, z) is [itex]\in[/itex] R1/R2, by definition it is [itex]\notin[/itex]R2?
     
  7. Oct 11, 2011 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    No, because that is exactly what you need to prove!!

    Maybe you should start looking for a counterexample.
     
  8. Oct 12, 2011 #7
    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    Counterexample. Let A = {1,2,3}
    Let R1 be the identity relation, iA. iA is transitive. R1 = {(1,1),(2,2),(3,3)}

    Let R2 be the relation, R2 = {(x,y)[itex]\in[/itex]A X A l x [itex]\leq[/itex]y}
    R2 = {(1,1), (1,2), (2,2), (2,3), (3,3)}. R2 is also transitive.

    Then R1\R2 = Empty set.

    I don't believe that the empty set could be transitive. (?) If true, then this would be a
    counterexample.
     
  9. Oct 12, 2011 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    Your R2 is not transitive: it misses (1,3).

    Also the empty set is trivially transitive: indeed, for each (x,y) and (y,z) in the emptyset (there is no such x,y, and z!!), we have that (x,z) is in there. So the condition is vacuously true.
     
  10. Oct 12, 2011 #9
    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    Thanks for your patience. I think I finally understand "vacuously" and "trivially" in regards to meeting the definition of transitive.

    If R2 and R2 are transitive, must R1\R2 be transitive? No.
    Counterexample: A = {1, 2, 3} and R1 = {(1,2), (2,3), (1, 3)} and R2 = {(1, 3)}.
    R1 is transitive and R2 is transitive (vacuously).

    Then, R1\R2 = {(1,2), (2,3)}. Therefore, R1\R2 is not transitive because it does not include
    (1, 3).
     
  11. Oct 12, 2011 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Re: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexampl

    Very good!! That is indeed a counterexample!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: If R1 and R2 are transitive, must R1\R2 be transitive?Prove or give counterexample
Loading...