# How to prove $R$ is an antisymmetric relation if and only if $R\circ R^{-1}\subseteq\Delta_X$?

$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?

• 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}$. – Hagen von Eitzen Jan 12 '14 at 22:39
• I translated your "o" into $\circ$, but it should probably be "intersection" $\cap$. – egreg Jan 12 '14 at 22:49
• @HagenvonEitzen Your relation is vacously antisymmetric, is it not? – Pedro Tamaroff Jan 12 '14 at 22:51
• @egreg thanks. I was thinking the same. It should be "intersection". or shouldnt R is transitive relation? – lyme Jan 12 '14 at 22:54
• @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. – egreg Jan 12 '14 at 22:56

$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.)