# How to prove relation is asymmetric if it is both anti-symmetric and irreflexive

Prove a relation is asymmetric if it is both anti-symmetric and irreflexive (anti-reflexsive).

I tried to go from the definitions of the relations:

Anti symmetric: $\forall x,y \, (xRy \land yRx \Rightarrow x=y )$

Irreflexsive: $\forall x\in A \ ,((x,x)\notin R)$

Assymetric: $\forall x,y \in A \,(xRy \Rightarrow \lnot yRx )$

But it doesn't get me anywhere... I also tried to think about proof by contraposition but I can't seem to be able to connect the definitions.

Any help would be appreciated.

Proof by contradiction will work here.

Assume $R$ is antisymmetric and irreflexive:

• Let $R$ be irreflexive: $$\forall x \in A, (x, x)\notin A$$ which means alternatively, $$\forall x \in A, \lnot( xRx)$$
• Let $R$ be antisymmetric: $$\forall x \in A, \forall y \in A, \Big(x R y \land yRx \rightarrow (x = y)\Big)$$

And assume, for contradiction, that $R$ is not asymmetric. The negation of asymmetry is given by $$\exists x \in A, \exists y \in A\,\Big(x R y \land yRx\Big)$$

Now show that this assumption contradicts antisymmetry or irreflexivity:

Can you see that this last assumption implies, by the definition of antisymmetry, that $x = y$?

But if $x = y$, then $xRy \implies xRx$.

But this contradicts irreflexivity! Contradiction. $\square$

• I guess I didn't know how to negate the statement. Thank you. – GinKin Dec 14 '13 at 16:00
• You're welcome, GinKin! – Namaste Dec 14 '13 at 16:01
• @amWhy: Nice feedback +1 – Amzoti Dec 15 '13 at 0:16