# Prove that a relation $R$ on a set $X$ satisfies $R \circ R^{-1} = \Delta_X$ iff $R$ is reflexive and antisymmetric.

Prove that a relation $$R$$ on a set $$X$$ satisfies $$R \circ R^{-1} = \Delta_X$$ iff $$R$$ is reflexive and antisymmetric. ($$\Delta_X = \{(x,x) \mid x \in X\}$$)

Consider right direction "If $$R \circ R^{-1} = \Delta_X$$, then $$R$$ is reflexive and antisymmetric".

Let $$X = \{1,2\}$$ and $$R=\{(1,2), (2,1)\}$$. We have $$R \circ R^{-1} = \{(1,1), (2,2)\} = \Delta_X$$. But clearly R is no reflexive neither antisymmetric.

Am I right? Or where I made mistake? Thank you.

• Your counter example is correct. Where did you get the question from?. Jul 18, 2019 at 17:04
• @MohammadRiazi-Kermani Thank you. This is exercise from book "Invitation to Discrete Mathematics" (JIří Matoušek and Jaroslav Nešetřil). Jul 18, 2019 at 17:09
• Thanks for the comment. Jul 18, 2019 at 17:16

The equivalence is obviously wrong, as shown. The correct statement is that a relation $$R$$ on a set $$X$$ satisfies the property that $$R \circ R^{-1} = \Delta_{X}$$ if and only if $$R$$ defines a surjective function from some subset of $$X$$ to $$X$$. A surjection from a proper subset can exist only for infinite sets. Also, the original statement would hold if $$\circ$$ (composition) were to be replaced with $$\cap$$ (intersection).