Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.