Union of Equivalences/Proof 1

Theorem

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

Proof

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$