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

5.8k Views Asked by At

$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

There are 1 best solutions below

0
On BEST ANSWER

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