5
$\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$

1 Answer 1

7
$\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$
3
  • $\begingroup$ I guess I didn't know how to negate the statement. Thank you. $\endgroup$
    – GinKin
    Commented Dec 14, 2013 at 16:00
  • $\begingroup$ You're welcome, GinKin! $\endgroup$
    – amWhy
    Commented Dec 14, 2013 at 16:01
  • $\begingroup$ @amWhy: Nice feedback +1 $\endgroup$
    – Amzoti
    Commented Dec 15, 2013 at 0:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .