0
$\begingroup$

A relation is asymmetric if and only if it is both antisymmetric and irreflexive.

I read this in Wikipedia's article about binary relation. So my problem with the statement is that though I can relate asymmetry with antisymmetry but cannot see the reasoning behind a binary relation being asymmetric is also irreflexive.

Here's what I understand about the statement.

Asymmetry $ \forall a,b\in X \quad aRb \implies \lnot (bRa) $

Antisymmetry $ \forall a,b\in X \quad (aRb \land bRa) \implies a=b $

In other words, $ \forall a,b\in X \quad (aRb \land a≠b) \implies \lnot (bRa) $

Now, if $ a=b $ was true in an asymmetric relation then by definition of asymmetry it would state that (putting $ a $ in place of $b$)

$ \forall a,a\in X \quad aRa \implies \lnot (aRa) $

But this statement seems contradictory. So we conclude that a binary relation between any two elements of a set will be asymmetric if equality does not hold between them. If this is the case then we have three condition.

  1. $ aRb $
  2. $ \lnot (aRb) $
  3. $ a≠b $

From this 3 conditions we can simply conclude that an asymmetric relation is also antisymmetric. Is my understanding correct? Any insightful thoughts on this will be appreciated. However, I still can't figure out why an asymmetric relation has to be irreflexive as well?

$\endgroup$

1 Answer 1

3
$\begingroup$

Your argument towards anti-symmetry is not correct.

In your argument towards anti-symmetry, you state:

$ \forall a,a\in X \quad aRa \implies \lnot (aRa) $

But this statement seems contradictory.

No, it is not contradictory. It simply means that you cannot have $aRa$ for any $a$, for if you did, then you would get a contradiction. So, this statement implies:

$ \forall a\in X \quad \lnot (aRa) $

and that is irreflexivity!

So your argument, which was supposed to demonstrate antisymmetry, actually demonstrates irreflexivity.

Moreover, your argument does not demonstrate anti-symmetry!

First, your statement:

So we conclude that a binary relation between any two elements of a set will be asymmetric if equality does not hold between them.

is a really strange statement: you shouldn't say that 'a binary relation between any two elements is asymmetric'. Rather, the whole relation is asymmetric, and that will constrain what relations may or may not hold between any two elements. But given asymmetry, any two elements can of course still be the same or not.

What you should have said is: if we assume that $aRb$ for some asymmetric relation, then we can conclude that $a \neq b$. But that of course means that if $a = b$, then $\lnot aRb$ .... but now we're back at irreflexivity!

So like I said, your argument can get you to irreflexivity, but not anti-symmetry.

OK, so how do we get anti-symmetry? Well, you were right to say that anti-symmetry can be rephrased as:

$ \forall a,b\in X \quad (aRb \land a≠b) \implies \lnot (bRa) $

To prove that, let's assume $aRb$ and $a≠b$ for some arbitrary $a$ and $b$. Well, given $aRb$, then given asymmetry, we immediately get $\neg (aRb)$. Hence: if $aRb$ and $a≠b$, then $\neg (aRb)$. And that's anti-symmetry!

$\endgroup$

You must log in to answer this question.

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