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

  • $\begingroup$ R is an equivalence relation for the "range" { x : some y with xRy }. How is domain defined? $\endgroup$ – William Elliot Feb 12 '18 at 8:54
  • $\begingroup$ @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$. $\endgroup$ – egreg Feb 12 '18 at 9:07
  • $\begingroup$ @RJM Well, in this case there’s no difference, owing to $R=R^{-1}$ $\endgroup$ – egreg Feb 12 '18 at 9:12
  • $\begingroup$ Please, add the definition of domain in the book, it would help in clarifying the problem. $\endgroup$ – egreg Feb 12 '18 at 9:18
  • $\begingroup$ @egreg - See my edit. $\endgroup$ – 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)\}$.

  • $\begingroup$ The empty relation has empty dand main. $\endgroup$ – egreg Feb 12 '18 at 9:16
  • $\begingroup$ @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$. $\endgroup$ – Taroccoesbrocco Feb 12 '18 at 9:18
  • $\begingroup$ Remove the “correctly” bit. $\endgroup$ – egreg Feb 12 '18 at 9:21
  • $\begingroup$ @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\}$. $\endgroup$ – Taroccoesbrocco Feb 12 '18 at 9:33
  • $\begingroup$ The question is about the relation being an equivalence relation on its domain, which is implicitly defined by the relation itself. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – William Elliot Feb 12 '18 at 8:50
  • 2
    $\begingroup$ If the domain $D$ is non-empty, take any $x\in D$. Then $x\not\mathrel{R}x$. Therefore, $R$ is not reflexive. $\endgroup$ – José Carlos Santos Feb 12 '18 at 8:51
  • $\begingroup$ Is the empty set a function? $\endgroup$ – William Elliot Feb 12 '18 at 8:57
  • $\begingroup$ Yes, but that's not relevant here. $\endgroup$ – user370967 Feb 12 '18 at 9:05
  • $\begingroup$ Any different counterexamples? I mean: is this the only possible counterexample? Can my statement be proven if we require $R \neq \emptyset$? $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.