- #1
privyet
- 13
- 1
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 [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.