Union of Equivalences

From ProofWiki
Jump to: navigation, search

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 = \left\{{a, b, c}\right\}$, and let $\mathcal R_1$ and $\mathcal R_2$ be equivalences on $S$ such that:

$\left[\!\left[{a}\right]\!\right]_{\mathcal R_1} = \left[\!\left[{b}\right]\!\right]_{\mathcal R_1} = \left\{{a, b}\right\}$
$\left[\!\left[{c}\right]\!\right]_{\mathcal R_1} = \left\{{c}\right\}$
$\left[\!\left[{a}\right]\!\right]_{\mathcal R_2} = \left\{{a}\right\}$
$\left[\!\left[{b}\right]\!\right]_{\mathcal R_2} = \left[\!\left[{c}\right]\!\right]_{\mathcal R_2} = \left\{{b, c}\right\}$


Let $\mathcal R_3 = \mathcal R_1 \cup \mathcal R_2$.

Then:

\(\displaystyle \) \(\) \(\displaystyle \left({a, b}\right) \in \mathcal R_1\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\displaystyle \left({b, c}\right) \in \mathcal R_2\) $\quad$ $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle \left({a, b}\right) \in \mathcal R_1 \cup \mathcal R_2 \land \left({b, c}\right) \in \mathcal R_1 \cup \mathcal R_2\) $\quad$ $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle \left({a, b}\right) \in \mathcal R_3 \land \left({b, c}\right) \in \mathcal R_3\) $\quad$ $\quad$


However:

\(\displaystyle \) \(\) \(\displaystyle \left({a, c}\right) \notin \mathcal R_1\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\displaystyle \left({a, c}\right) \notin \mathcal R_2\) $\quad$ $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle \left({a, c}\right) \notin \mathcal R_1 \cup \mathcal R_2\) $\quad$ $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle \left({a, c}\right) \notin \mathcal R_3\) $\quad$ $\quad$


So $\mathcal R_3$ is not transitive, and therefore $\mathcal R_3 = \mathcal R_1 \cup \mathcal R_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$