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

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\}.$$

• R is an equivalence relation for the "range" { x : some y with xRy }. How is domain defined? – William Elliot Feb 12 '18 at 8:54
• @WilliamElliot The domain of a relation $R$ is the set of elements $x$ such that there exists $y$ with either $(x,y)\in R$ or $(y,x)\in R$. – egreg Feb 12 '18 at 9:07
• @RJM Well, in this case there’s no difference, owing to $R=R^{-1}$ – egreg Feb 12 '18 at 9:12
• Please, add the definition of domain in the book, it would help in clarifying the problem. – egreg Feb 12 '18 at 9:18
• @egreg - See my edit. – Davide Gallo Feb 12 '18 at 9:49

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)\}$.

• The empty relation has empty dand main. – egreg Feb 12 '18 at 9:16
• @egreg - I agree, but I don't see what you want to say. There are more than the two cases $\mathrm{dom}(R) = \emptyset$ and $\mathrm{dom}(R) = X$, provided $|X| > 1$. – Taroccoesbrocco Feb 12 '18 at 9:18
• Remove the “correctly” bit. – egreg Feb 12 '18 at 9:21
• @egreg - Sorry, I don't understand, I think that also my first sentence is correct. Take $X = \{0\} \neq \emptyset$ and $R = \emptyset$: then, $\mathrm{dom}(R) = \emptyset$ and $R$ is a binary relation over $X$ that satisfies $R^{−1}=R=R \circ R$ but it is not an equivalence. By definition (see p. 3 of the cited book), $\mathrm{dom}(R) = \{x \in X \mid \exists \, y : x \,R\, y\}$. – Taroccoesbrocco Feb 12 '18 at 9:33
• The question is about the relation being an equivalence relation on its domain, which is implicitly defined by the relation itself. – egreg Feb 12 '18 at 9:41

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.

• Even though it is not a full or total relation, it is nevertheless an equivalence relation. This is a domain quibble like is 1/x or the empty set a function? – William Elliot Feb 12 '18 at 8:50
• If the domain $D$ is non-empty, take any $x\in D$. Then $x\not\mathrel{R}x$. Therefore, $R$ is not reflexive. – José Carlos Santos Feb 12 '18 at 8:51
• Is the empty set a function? – William Elliot Feb 12 '18 at 8:57
• Yes, but that's not relevant here. – user370967 Feb 12 '18 at 9:05
• Any different counterexamples? I mean: is this the only possible counterexample? Can my statement be proven if we require $R \neq \emptyset$? – Davide Gallo Feb 12 '18 at 9:12

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