Union of Equivalences

Theorem

The union of two equivalence relations is not necessarily an equivalence relation itself.

Proof 1

This can be shown by giving an example.

Let $S = \set {a, b, c}$, and let $\RR_1$ and $\RR_2$ be equivalences on $S$ such that:

$\eqclass a {\RR_1} = \eqclass b {\RR_1} = \set {a, b}$

$\eqclass c {\RR_1} = \set c$

$\eqclass a {\RR_2} = \set a$

$\eqclass b {\RR_2} = \eqclass c {\RR_2} = \set {b, c}$

Let $\RR_3 = \RR_1 \cup \RR_2$.

Then:

\(\ds \tuple {a, b}\)

\(\in\)

\(\ds \RR_1\)

\(\ds \tuple {b, c}\)

\(\in\)

\(\ds \RR_2\)

\(\ds \leadsto \ \ \)

\(\ds \tuple {a, b}\)

\(\in\)

\(\ds \RR_1 \cup \RR_2\)

\(\, \ds \land \, \)

\(\ds \tuple {b, c}\)

\(\in\)

\(\ds \RR_1 \cup \RR_2\)

\(\ds \leadsto \ \ \)

\(\ds \tuple {a, b}\)

\(\in\)

\(\ds \RR_3\)

\(\, \ds \land \, \)

\(\ds \tuple {b, c}\)

\(\in\)

\(\ds \RR_3\)

However:

\(\ds \tuple {a, c}\)

\(\notin\)

\(\ds \RR_1\)

\(\, \ds \land \, \)

\(\ds \tuple {a, c}\)

\(\notin\)

\(\ds \RR_2\)

\(\ds \leadsto \ \ \)

\(\ds \tuple {a, c}\)

\(\notin\)

\(\ds \RR_1 \cup \RR_2\)

\(\ds \leadsto \ \ \)

\(\ds \tuple {a, c}\)

\(\notin\)

\(\ds \RR_3\)

So $\RR_3$ is not transitive, and therefore $\RR_3 = \RR_1 \cup \RR_2$ is not an equivalence relation.

$\blacksquare$

Proof 2

We have that the Union of Reflexive Relations is Reflexive.

We also have that the Union of Symmetric Relations is Symmetric.

However, we also have that the Union of Transitive Relations Not Always Transitive.

Hence the union of two equivalence relations is not always an equivalence relation.

$\blacksquare$