Show that $R^{-1}=R=R \circ R$ implies $R$ is an equivalence relation

909 Views Asked by At

I was leafing through the "Introduction to Classical Real Analysis" (Stromberg), and while reading the paragraph "Equivalence Relations" in the "Preliminaries" section, I saw:

One checks that any such $R$ [i.e. which is reflexive, symmetric and transitive] satisfies $R^{-1}=R=R \circ R$ and that, conversely, any relation $R$ satisfying these two equalities is an equivalence relation on its domain.

I am not able to prove that $R^{-1}=R=R \circ R$ implies $R$ being reflexive, that is, why if $R^{-1}=R=R \circ R$ then $$\newcommand{\dom}{\operatorname{dom }} x \in \dom R \implies (x,x) \in R \;?$$

Here the domain of the binary relation $R$ over a set $X$ is defined as $$\dom R = \{x \in X : (x,y) \in R \textrm{ for some } y \in X\}.$$

3

There are 3 best solutions below

6
On BEST ANSWER

As correctly pointed out by José Carlos Santos, the fact that $R^{-1} = R = R \circ R$ does not imply that $R$ is an equivalence relation over a set $X \neq \emptyset$ in the case of $R = \emptyset$. But it does imply that $R$ is an equivalence relation over the domain of $R$ defined as $\mathrm{dom}(R) = \{x \in X \mid \exists \, y \in X : x \,R\, y\}$ (which is actually what the book you cited claims on p. 3). Let us prove it.

  1. Reflexivity over $\mathrm{dom}(R)$: Let $x \in \mathrm{dom}(R)$. By definition of domain of $R$, there is $y \in X$ such that $x \, R \, y$. Since $R^{-1} = R$, then $y \, R \, x$. Since $R = R \circ R$, from $x \,R\, y$ and $y \,R\, x$ it follows that $x \,R\, x$.

  2. Symmetry: Let $x \,R\, y$. Since $R^{-1} = R$, then $y \,R\, $.

  3. Transitivity: Let $x \,R\, y$ and $y \,R\, z$. Then, $x \,R\, z$ because $R = R \circ R$.

Clearly, if to the hypothesis $R^{-1} = R = R \circ R$ we add the further hypothesis $\mathrm{dom}(R) = X$, then $R$ is an equivalence relation over $X$.

Note that the fact that $R^{-1} = R = R \circ R$ with the further hypothesis $R \neq \emptyset$ does not imply the reflexivity of $R$ over $X$ if $X$ has at least two elements. For instance, take $X = \{0,1\}$ and $R = \{(1,1)\}$.

6
On

Because it is not true. Suppose that $R=\emptyset$. Then $R^{-1}=R=R\circ R(=\emptyset)$. But, unless the domain itself is the empty set, this is not a reflexive relation.

0
On

Suppose $x$ is in the domain of $R$. Then there exists $y$ with $(x,y)\in R$. Owing to $R=R^{-1}$, we have $(y,x)\in R$. Apply $R\circ R=R$.