1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .