$R$ is antisymmetric relation if and only if $R\circ R^{-1}\subseteq\Delta_X$

$\leftarrow$ assume $R\circ R^{-1}\subseteq\Delta_X$. let $(x,y)\in R $ and $(y,x)\in R\rightarrow (y,x)\in R^{-1}$, so $(x,y)\in R\circ R^{-1}$ therefore $(x,y) \in\Delta_X$ for this reason $x=y$. $R$ is antisymmetric.

$\rightarrow $ let $R$ be an antisymmetric relation, and $(x,y)\in R\circ R^{-1}\rightarrow\exists z\in X$ such that $(z,y)\in R \wedge (x,z)\in R^{-1}$ we must show $y=z$ and $z=x$.

How can I continue?

  • 1
    $\begingroup$ If $R$ is (the well-known antisymmetric) $<$ on $\{1,2,3\}$. Then $R=\{(1,2),(1,3),(2,3)\}$ amd $R^{-1}=\{(2,1),(3,1),(3,2)\}$. Then the non-diagonal $(2,3)$ is in $R\circ R^{-1}$. $\endgroup$ – Hagen von Eitzen Jan 12 '14 at 22:39
  • $\begingroup$ I translated your "o" into $\circ$, but it should probably be "intersection" $\cap$. $\endgroup$ – egreg Jan 12 '14 at 22:49
  • $\begingroup$ @HagenvonEitzen Your relation is vacously antisymmetric, is it not? $\endgroup$ – Pedro Tamaroff Jan 12 '14 at 22:51
  • $\begingroup$ @egreg thanks. I was thinking the same. It should be "intersection". or shouldnt R is transitive relation? $\endgroup$ – lyme Jan 12 '14 at 22:54
  • $\begingroup$ @lyme As Hagen's example shows, $R\circ R^{-1}$ can be included in the diagonal even for antisymmetric (and transitive) relations. So I believe you reported the statement wrongly. $\endgroup$ – egreg Jan 12 '14 at 22:56

The correct statement should be

$R$ is antisymmetric if and only if $R\cap R^{-1}\subseteq\Delta_X$

Proof. If $(x,y)\in R$ and $(y,x)\in R$, then $(x,y)\in R^{-1}$ and so $(x,y)\in R\cap R^{-1}$. Therefore $(x,y)\in \Delta_X$ and so $x=y$. Hence $R$ is antisymmetric. (This is your argument, which is correct after changing $\circ$ into $\cap$.)

Conversely, let $R$ be antisymmetric and $(x,y)\in R\cap R^{-1}$. Then $(x,y)\in R$ and $(x,y)\in R^{-1}$. Therefore $(y,x)\in \dots$ and …

The statement with $\circ$ instead of intersection is false. Consider the relation $R=\{(1,2),(1,3),(2,3)\}$ on $X=\{1,2,3\}$. Then it is antisymmetric, because for no elements $x,y\in X$ we have $(x,y)\in R$ and $(y,x)\in R$. Then $R^{-1}=\{(2,1),(3,1),(3,2)\}$ and $(2,3)\in R\circ R^{-1}$. If you don't trust this relation, consider $$ \bar{R}=\{(1,2),(1,3),(2,3),(1,1),(2,2),(3,3)\} $$ which clearly is a partial order on $\{1,2,3\}$. Then the same applies and $(2,3)\in \bar{R}\circ\bar{R}^{-1}$. (Counterexample proposed by Hagen von Heitzen in comments.)


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.