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!

Help proving some basic properties of relations

  1. Aug 15, 2013 #1
    1. The problem statement, all variables and given/known data

    Prove the following properties of relations:

    1) If R is asymmetric then it's antisymmetric.
    2) If R is asymmetric then it's irreflexive.
    3) If R is irreflexive and transitive then it's asymmetric.

    3. The attempt at a solution

    1)
    If R is asymmetric on a set X, then for all x,y in X: xRy implies [itex]\neg[/itex](yRx).
    If R is antisymetric on X, then for all x,y in X: xRy and yRx implies x = y.

    The premise of the antisymmetry relation requires that xRy and yRx but as R is asymmetric we know that [itex]\neg[/itex](xRy and yRx), therefore given that the premise is false, the conclusion is vacuously true and we can say that if R is asymmetric then it's antisymmetric.

    2)If R is asymmetric on a set X, then for all x,y in X: xRy implies [itex]\neg[/itex](yRx).
    If R is irreflexive, then for all x in X, [itex]\neg[/itex](xRx)

    I really don't know how to think about this proof.

    3)
    If R is irreflexive, then for all x in X, [itex]\neg[/itex](xRx).
    R is transitive if when xRy and yRz for all x,y,z in X, then xRz.

    Likewise, I don't know how to begin thinking about this proof.

    In all of these problems I'm finding it hard to get my head around the process of doing the proof. If I write the 3rd problem in logic notation I get:
    ([itex]\forall[/itex]x [itex]\neg[/itex](xRx)) [itex]\wedge[/itex] ([itex]\forall[/itex]x,y,z in X xRy [itex]\wedge[/itex] yRz [itex]\Rightarrow[/itex] xRz) [itex]\Rightarrow[/itex] (xRy [itex]\Rightarrow[/itex] [itex]\neg[/itex](yRx))

    How do I break this down and think about it? Any help much appreciated.
     
  2. jcsd
  3. Aug 16, 2013 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    With regard to 2), what happens if R is not irreflexive, that is, there exists some x in X such that xRx?

    With regard to 3), what does transitivity say about xRy and yRx?
     
  4. Aug 16, 2013 #3
    Thanks for your reply.

    1) I'm not sure, to be honest. One approach I had in mind was to say let x = y, then in the assymetric relation xRx [itex]\Rightarrow[/itex] [itex]\neg[/itex](xRx), then using the irreflexive relation I can say that since xRx is the premise it is false and therefore the implication is vacuously true. As I say, I don't feel like I have any idea how to organize my thoughts with regard to this so I have no idea if my statement is correct or not.

    2) Transitivity would say that if xRy and yRx then xRx, but this should be false in this case because it is transitive and irreflexive. Am I going in the right direction here?

    P.s. If anyone can point to an online resource that gives examples of proofs involving the properties of relations please let me know. I've done a lot of googling but haven't found much that i can apply to these types of questions.
     
  5. Aug 16, 2013 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You're welcome.


    The premise is *not* that R is irreflexive. The premise is that R is asymmetric. Your job is to prove that this means that R is irreflexive. So assume the contrary, that R is not irreflexive. (Hint: Look for a contradiction.)


    Yes, you are going in the right direction. Transitivity, irreflexivity, and the assumption that there exists some x,y in X such that xRy and yRx leads to a contradiction. One of these things does not go with the other. That assumption has to be false. What does this say about R (Hint #1: It says it's asymmetric, but you have to prove it. Hint #2: Rewrite A→B using 'and' and 'not'.)


    You apparently have forgotten about proof by contradiction. It's a powerful tool.
     
    Last edited: Aug 16, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted