Prove or disprove: if $R$ and $S$ are two equivalence relations on a set $A$ then $R\cup S$ is also an equivalence relation.

Question

Does my disproof below suffice to disprove the statement below? Also, does anyone have a simpler way to disprove this?

If $R$ and $S$ are two equivalence relations on a set $A$ then $R\cup S$ is also an equivalence relation.

Disproof. Suppose $A=\{a,b,c\}$ and $R$ and $S$ are equivalence relations on $A$. Let

\begin{align*} R&=\{(a,a),(b,b),(c,c),(a,b),(b,a)\} \\ S&=\{(a,a),(b,b),(c,c),(b,c),(c,b)\} \end{align*}

Then

$$R\cup S=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)\}$$

But then $a(R\cup S)b \land b(R\cup S)c \nRightarrow a(R\cup S)c$, thus $R\cup S$ is not transitive and therefore not an equivalence relation.

Answer 1

This counterexample is perfectly valid.

To help see this, visualize each relation as a directed graph like below, where $x$ points to $y$ if and only if $x$ is related to $y$ under the relevant relation. We have, for $R$ and $S$ respectively,

You can see these are equivalence relations because each property is demonstrated:

• Reflexivity follows since every node points to itself.
• Symmetry follows since, whenever a path extends from one node to another, a path going the opposite direction also exists.
• Transitivity follows since, whenever three nodes are connected along a single path, there's also a path from the start point to the end point. (Loosely this looks like, whenever two sides of a triangle exist, a path exists by which you can "cut" from the start of the path to the end as well, filling in the triangle in a sense.)

The graph representing the union $R \cup S$ is given by effectively overlapping the pair:

Now we have two triangles where each is missing a side: the sides $a \to b$ and $b \to c$ are missing $a \to c$; likewise, the sides $c \to b$ and $b \to a$ are missing $c \to a$.

(That is, $(a,b),(b,c) \in R \cup S$ but $(a,c) \not \in R \cup S$. And similarly, $(c,b),(b,a) \in R \cup S$ but $(c,a) \not \in R \cup S$.)

Thus $R \cup S$ is not transitive. And, indeed, in general, unions of equivalence relations are not always themselves equivalences.

---

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.