2

I am finding difficulty in understanding the difference between asymmetric (non-symmetric) and anti-symmetric relations. Though I didn't quite find any mention of the word asymmetric in the reference book, our teacher had mentioned it while explaining the concepts.

So my question, are non-symmetric and anti-symmetric relations, both the same thing or different? It would be appreciated if someone could explain using a couple of examples. (I did not understand the definition, so I did not approach the sums, hence this is a general question.)

Asaf Karagila
  • 393,674
Dhanishtha
  • 33

3 Answers3

1

A symmetric relation is one where the order can be flipped. Equality is symmetric because if $x=y,$ then $y=x$ also. Weak inequality $\leq$ is also symmetric. Strict inequality $<$ is not symmetric.

An antisymmetric relation is one where distinct elements cannot be reversed. Weak inequality is antisymmetric.

An asymmetric relation is one where the equation never holds. Asymmetric means antisymmetric and irreflexive. Strict inequality is asymmetric.

ziggurism
  • 16,756
1

Denote $R$ the relation.

Non-symmetric is just $\:\lnot(aRb\implies bRa)$, whereas anti-symmetric is $(aRb)\wedge(bRa)\implies a=b$.

Bernard
  • 175,478
  • You've left behind the quantifiers, and yes it does matter; $\neg (\forall a,b (aRb \to bRa))$ is not the same as $\neg (\exists a,b (aRb \to bRa))$ and also $\neg (\forall a,b (aRb \to bRa))$ is not the same as $\forall a, b (\neg(aRb \to bRa))$. – Rick Sep 10 '20 at 17:55
  • 1
    @Rick: Yes, I intentionally didn't add them to make a more intuitive sketch. I don't think the O.P.'s difficulties are at that level. But maybe I'm wrong. – Bernard Sep 10 '20 at 18:04
  • @Bernard Yes, you are right. The difficulty level is not too high, just the beginners. – Dhanishtha Sep 10 '20 at 18:09
  • @Rick Though it is not mentioned in our book, I am quite intrigued in knowing the difference between your second statement. ¬(∀,(→)) is not the same as ∀,(¬(→)). I know that "for all" is very much different than "there exists", but the second statement is quite new to me. – Dhanishtha Sep 10 '20 at 18:20
  • Should I post a new question in accordance to this, or will it be okay if you edit your answer here? – Dhanishtha Sep 10 '20 at 18:21
  • It is the same as $;\exists a\exists b\bigl(\lnot(aRb \to bRa)\bigr)$. If can be further simplified, as $p\to q$ is $(\lnot p)\vee q$. So it finally becomes $;\exists a\exists b\bigl( (aRb)\wedge(\lnot(bRa))\bigr)$. – Bernard Sep 10 '20 at 18:25
1

The definitions are as follows:

  • A relation $R$ on a set $X$ is symmetric if for all $a, b \in X$, $aRb$ implies $bRa$.
  • A relation $R$ on a set $X$ is non-symmetric if it is not symmetric; i.e. there exist $a, b \in X$ such that $aRb$ does not imply $bRa$.
  • A relation $R$ on a set $X$ is called antisymmetric if for all $a, b \in X$, $aRb$ and $bRa$ implies $a = b$.

One can see that non-symmetric and antisymmetric relations are quite different through easy examples. One stock of examples for antisymmetric relations is given by directed graphs; take $X = \{1,2,3,4\}$ to be the set of vertices of graph and define the relation $R_1$ on $X$ as follows: $$a R_1 b \iff \text{there is a directed edge from } a \text{ to }b.$$ A concrete example witnessing non-symmetricity for $R_1$ would be the following graph: $$\require{AMScd}\begin{CD} 1 @>>> 2\\ @VVV @VVV\\ 3 @>>> 4 \end{CD}$$ Then $R_1$ is non-symmetric, since $2 \to 4$ (i.e. $2R_14$) but $4 \not\to 2$ (i.e. it is not the case that $4 R_1 2$).

Finally, for antisymmetric relations you can take any partial order on a set, such that the standard $\leq$ relation on the integers or the reals, say.

Rick
  • 1,896