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!

Help finding a counterexample for a relation's transitivity

  1. Apr 17, 2012 #1
    1. The problem statement, all variables and given/known data

    I'll spare most of the details, R = {(x,y) | |x-y| < 5}

    I need to find a counter-example to show that it is not transitive. I'm having trouble.


    3. The attempt at a solution


    First, in order to find a counter example, I know this must be satisfied:

    | x - y | < 5
    |y - z | < 5
    |x - z | >= 5



    So to remove the absolute values, I did (which makes sense to me on paper):

    -5 < x - y < 5
    -5 < y - z < 5

    x - z > 5 or x - z <= -5

    So to isolate x and y, I did this (which again, only makes sense to me on paper)

    -5 + y < x < 5 + y

    -5 - y < -z < 5 - y
    -5 + y < z < 5 + y

    So I have "information" about both z and x, but how can I use that in:

    x - z > 5 or x - z <= -5

    To make it say something about y? (since that's what I chose to express x and z in terms of)


    I feel like I essentially have a system of inequalities:

    -5 + y < z < 5 + y
    -5 + y < x < 5 + y
    x - z > 5 or x - z <= -5


    Am I on the right track here? I'm just doing what makes sense to me, I've never dealt with inequalities in any classes in this way.
     
  2. jcsd
  3. Apr 17, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You are probably better off just fiddling with some numbers to create a counterexample. Is (1,5) in your relation? Now you want another ordered pair that has a 5 in the first position that violates transitivity. Just play with it.
     
  4. Apr 17, 2012 #3
    I did find a counter example that way, x = 0, y = 1, z = 5, but is there a more methodical approach?
     
  5. Apr 17, 2012 #4

    Mark44

    Staff: Mentor

    This is a lot to go through, so I'll instead appeal to your geometric intuition. a and b are related (i.e., aRb) if a is within 5 units of b. Similarly, b R c if b and c are within 5 units of each other. On the number line, can you come up with numbers a, b, and c so that a R b and b R c, but a is more than 5 units from c? IOW, it's not true that a R c.
     
  6. Apr 17, 2012 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Probably, but I think that would be more trouble than it's worth.
     
  7. Apr 17, 2012 #6
    I see.

    Thanks for the visual approach idea, it becomes simple if I draw a number line. All I did was draw two points that were 4 units away, then the next one 4 units away from that one, thus the first and third are 8 units away. Called the middle one 0, making the other two -4 and 4.

    So x = -4, y = 0, z = 4 is a counter example.
     
  8. Apr 17, 2012 #7

    Mark44

    Staff: Mentor

    Keep that in mind. If a problem lends itself to a graphical or geometric approach, always give that some thought. Don't limit yourself by taking a strictly algebraic approach.
     
  9. Apr 17, 2012 #8
    http://www.infoocean.info/avatar1.jpg [Broken]You are probably better off just fiddling with some numbers to create a counterexample
     
    Last edited by a moderator: May 5, 2017
  10. Apr 17, 2012 #9
    Alright guys, I wasn't sure if this warranted a new thread because I'm working the same type of problem again. Again, it's transitivity (reflexive and symmetric are very trivial for my problems).

    This time the relation is x^2 + y^2 = 1.

    I figured that a counter example is any time x =/= y =/= z =/= sqrt(.5) like so (besides from knowing that if they weren't all equal, it can't work):

    x^2 + y^2 = 1
    y^2 + z^2 = 1

    So x^2 + z^2 = 2(1-y^2)

    2(1-y^2) =/= 1
    1-y^2 =/= .5
    -y^2 =/= -.5
    y^2 =/= .5
    y =/= sqrt(.5)

    I have to show some reasoning for my counter-example. Is this reasonable and correct?

    Thanks again!
     
  11. Apr 17, 2012 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    What is your domain for x and y? I can certainly see that is symmetric. Why is it reflexive?
     
  12. Apr 17, 2012 #11
    It's not reflexive. I didn't mean to imply that it is "trivially reflexive" only that determining whether or not it is is trivial. Counter example is the same thing because it still requires that they are both the same (since x = x) and for both of the variables in x^2 + y^2 = 1 to be the same, there is only one solution, sqrt(.5).

    This is how I determined my counter example for transitivity beforehand.

    do you agree?
     
  13. Apr 17, 2012 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Not really. I don't follow your logic at all. 0^2+1^2=1, so (0,1) is in your relation. So is (1,0). (0,0) isn't. Doesn't that mean it's not transitive? I think you are taking an overcomplicated approach again.
     
    Last edited: Apr 17, 2012
  14. Apr 17, 2012 #13
    I'm not sure I understand what you mean. My work shows that it's not transitive, because the only way that (x,y), (y,z), and (x,z) are all in the relation is if x = y = z = sqrt(.5).

    So a counterexample is anything other than that case. So it's not transitive.

    Similarly, regarding reflexivity, a counter example is anything other than the case x = y = sqrt(.5).
     
  15. Apr 17, 2012 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    How about x=(-sqrt(.5))? I'm not really saying that you can't do it that way. But you are ignoring the simple counterexamples and going for a more complicated reasoning. I don't know why.
     
  16. Apr 17, 2012 #15
    I guess because I figure that finding counter-examples will get more difficult, and I think that finding a "template" for a counter example in a certain problem is good for when that happens. I don't really want to just find one from intuition and plug it in. I know that a single counter example will always do the trick to disprove something, but I am curious to know what the features of the counter examples are, I guess.

    But my thought boiled down to this:

    All variables must be equal for reflexivity, by definition, and they all must be equal for transitivity, in this case, due to the nature of the relation in that if I can add some y^2 to x^2 to get 1, and can add some z^2 to x^2 to get 1, then z^2 must equal y^2. For that to be the case, y^2 + z^2 = 1 => y = sqrt(.5); z = sqrt(.5).

    And, since by that reasoning y = sqrt(.5),

    x^2 + .5 = 1
    x^2 = .5
    x = sqrt(.5)

    So x = y = z is the only way that (x,y), (y,z), and (x,z) could possibly be in the relation.

    EDIT: Though I agree that it would be truly correct to say:

    |x| = |y| = |z|
     
  17. Apr 17, 2012 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Your reasoning is roughly correct, but you are forgetting that x^2=.5 has two solutions. Turning a problem where you can simply guess counterexamples into something more complicated isn't what you want to do. There's no magic formula that covers all cases. Your first problem turned into a fairly complicated system of inequalities and this turns in a more complicated problem involving quadratics. Those are two different things. Just grab the simple way.
     
  18. Apr 18, 2012 #17

    Mark44

    Staff: Mentor

    For this problem, I don't know if you are seeing the geometry involved. x is related to y if x2 + y2 = 1. IOW, if (x, y) is a point on the unit circle. Understanding that might be helpful in your work.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook