5
$\begingroup$

Can some relation be at the same time symmetric and antisymmetric? And, can a relation be neither one nor the other? Please give me an example for your answer.

$\endgroup$
1
  • 1
    $\begingroup$ What do you know of the definitions of symmetric and antisymmetric? $\endgroup$ – JMoravitz Oct 11 '15 at 20:53
30
$\begingroup$

A convenient way of thinking about these properties is from a graph-theoretical perspective.

Let us define a graph (technically a directed multigraph with no parallel edges) in the following way:

Have a vertex for every element of the set. Draw an edge with an arrow from a vertex $a$ to a vertex $b$ iff there $a$ is related to $b$ (i.e. $aRb$, or equivalently $(a,b)\in R$).

If an element is related to itself, draw a loop, and if $a$ is related to $b$ and $b$ is related to $a$, instead of drawing a parallel edge, reuse the previous edge and just make the arrow double sided ($\leftrightarrow$)

For example, for the set $\{1,2,3\}$ the relation $R=\{(1,1), (1,2), (2,3), (3,2)\}$ has the following graph:

enter image description here

Definitions:

$\begin{array}{l|l|l} &\text{set theoretical}&\text{graph theoretical}\\ \hline \text{Symmetric}&\text{If}~aRb~\text{then}~bRa&\text{All arrows (not loops) are double sided}\\ \hline \text{Anti-Symmetric}&\text{If}~aRb~\text{and}~bRa~\text{then}~a=b&\text{All arrows (not loops) are single sided} \end{array}$

You see then that if there are any edges (not loops) they cannot simultaneously be double-sided and single-sided, but loops don't matter for either definition. Any relation on a set $A$ that is both anti-symmetric and symmetric then has its graph consisting of only loops (i.e. is of the form $R=\{(a,a)~|~a\in S\subseteq A\}$ for some $S\subseteq A$.

Any relation whose graph contains both types of arrows (single-sided and doublesided) will be neither symmetric nor antisymmetric.

$\endgroup$
1
  • 5
    $\begingroup$ +1 Nice. Visualisations are miraculous good. They make things easy to comprehend and remember. $\endgroup$ – drhab Oct 12 '15 at 8:18
5
$\begingroup$

Suppose that $R\subseteq A\times A$ is indeed symmetric and antisymmetric.

If $aRb$ then $bRa$ (symmetry) and based on $aRb\wedge bRa$ we find $a=b$ (antisymmetry).

Proved is now that $aRb\implies a=b$ or equivalently $R\subseteq\{\langle a,a\rangle\mid a\in A\}$

Conversely it is not difficult to show that any subset of $\{\langle a,a\rangle\mid a\in A\}$ is a relation that is symmetric and antisymmetric.


If $a,b,c\in A$ are distinct then relation $R:=A\times A-\{\langle a,b\rangle\}$ is not symmetric ($bRa$ but not $aRb$) and is not antisymmetric ($aRc\wedge cRa$ but not $a=c$).

$\endgroup$
3
$\begingroup$

A relation can be both symmetric and antisymmetric, for example the relation of equality. It is symmetric since $a=b\implies b=a$ but it is also antisymmetric because you have both $a=b$ and $b=a$ iff $a=b$ (oh, well...).

A relation can also be neither, for example preorders are generally neither symmetric nor antisymmetric

$\endgroup$
2
$\begingroup$

Definitions:

symmetric: if $a R b$ then $b R a$.

antisymmetric: if $a R b$ and $b R a$ then $a = b$.

The empty relation is both. More generally, any relation that's both symmetric and antisymmetric is then contained in the identity relation: if $a R b$, then by symmetry, $b R a$, so by antisymmetry, $a = b$. The converse it true too: any subset of the identity relation has both properties.

$<$ on integers is antisymmetric and it's also not symmetric.

$\endgroup$
0

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