3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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