Help proving some basic properties of relations

[privyet]

Homework Statement

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.

The Attempt at a Solution

1)
If R is asymmetric on a set X, then for all x,y in X: xRy implies \neg(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 \neg(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 \neg(yRx).
If R is irreflexive, then for all x in X, \neg(xRx)

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

3)
If R is irreflexive, then for all x in X, \neg(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:
(\forallx \neg(xRx)) \wedge (\forallx,y,z in X xRy \wedge yRz \Rightarrow xRz) \Rightarrow (xRy \Rightarrow \neg(yRx))

How do I break this down and think about it? Any help much appreciated.

 

[D H]

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?

 

[privyet]

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 \Rightarrow \neg(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.

 

[D H]

Thanks for your reply.

You're welcome.

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 \Rightarrow \neg(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.

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

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?

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.