2

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

egreg
  • 238,574
lyme
  • 1,351
  • 1
  • 13
  • 30
  • 1
    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 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
  • @egreg It was from my exam and I'm sure it was $RoR^{-1}$ :) . so cant we prove when the statement is like this? . – lyme Jan 12 '14 at 22:59
  • @lyme No, we can't: there's a counterexample – egreg Jan 12 '14 at 23:07

1 Answers1

3

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

egreg
  • 238,574