1
$\begingroup$

I'm trying to figure out how a relation can be both antisymmetric and symmetric simultaneously. And how is antisymmetric different from NOT symmetric. Is the easiest way to answer this is by graphing? I'm trying to come up with such a relation but I'm having a bit of confusion with the definitions.

$\endgroup$
3
$\begingroup$

Graphs are one easy way to see it. Think of each edge $x\mathrel{R}y$ as a permitted direction of travel on a ‘street’ from $x$ to $y$. If $x\mathrel{R}y$ and $y\mathrel{R}x$, the street allows two-way traffic. If only one of $x\mathrel{R}y$ and $y\mathrel{R}x$ holds, there’s only a one-way street, either from $x$ to $y$ or from $y$ to $x$.

  • $R$ is antisymmetric if there are no two-way streets between distinct vertices: you cannot have both $x\mathrel{R}y$ and $y\mathrel{R}x$ unless $x=y$.

  • $R$ is symmetric if every street between distinct vertices is a two-way street, i.e., there are no one-way streets between distinct vertices.

If there are no streets at all between distinct vertices, then:

  • $R$ is antisymmetric, because it has no two-way streets, and
  • $R$ is symmetric, because it has no one-way streets.

Thus, if the digraph of $R$ has only loops, and no edges at all between distinct vertices, then $R$ is both antisymmetric and symmetric. In terms of $R$ directly, this says that $R$ is antisymmetric and symmetric if and only if

$$R\subseteq\{\langle x,x\rangle:x\in A\}$$

(where I’m assuming that $R$ is a relation on the set $A$). In other words, $R$ is a subset of the diagonal in $A\times A$: $R$ is a subset of the equality relation on $A$.

$\endgroup$
  • $\begingroup$ "you cannot have both xRy and yRx unless x=y." Well in the case of R = { (1,1) }, then doesn't this mean it is also reflexive? $\endgroup$ – Dimitri Nov 21 '13 at 20:33
  • $\begingroup$ @Dimitri: Whether $\{\langle 1,1\rangle\}$ is reflexive depends entirely on what the underlying set is. If it’s a relation on $\{1\}$, then it’s reflexive. If it’s a relation on $\{1,2,3\}$, say, then it’s not reflexive. In either case, however, it is both symmetric and antisymmetric. $\endgroup$ – Brian M. Scott Nov 21 '13 at 20:35
  • $\begingroup$ +1 VERY enlightening answer! $\endgroup$ – Mathemagician1234 Oct 31 '18 at 4:19

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.