# Fundamental Theorem on Equivalence Relations/Examples/Arbitrary Equivalence on Set of 6 Elements 2

Jump to navigation
Jump to search

## Example of Use of Fundamental Theorem on Equivalence Relations

Let $S = \set {1, 2, 3, 4, 5, 6}$.

Let $\mathcal R \subset S \times S$ be an equivalence relation on $S$ with the properties:

\(\displaystyle 1\) | \(\mathcal R\) | \(\displaystyle 3\) | |||||||||||

\(\displaystyle 3\) | \(\mathcal R\) | \(\displaystyle 4\) | |||||||||||

\(\displaystyle 2\) | \(\mathcal R\) | \(\displaystyle 6\) | |||||||||||

\(\displaystyle \forall a \in A: \ \ \) | \(\displaystyle \size {\eqclass a {\mathcal R} }\) | \(=\) | \(\displaystyle 3\) |

Then the equivalence classes of $\mathcal R$ are:

\(\displaystyle \eqclass 1 {\mathcal R}\) | \(=\) | \(\displaystyle \set {1, 3, 4}\) | |||||||||||

\(\displaystyle \eqclass 2 {\mathcal R}\) | \(=\) | \(\displaystyle \set {2, 5, 6}\) |

## Proof

We have that:

- $1 \mathrel {\mathcal R} 3$ and $3 \mathrel {\mathcal R} 4$

As $\mathcal R$ is an equivalence relation, it follows that $\mathcal R$ is transitive and so:

- $1 \mathrel {\mathcal R} 4$

Thus:

- $\eqclass 1 {\mathcal R} \subseteq \set {1, 3, 4}$

but as:

- $\size {\eqclass a {\mathcal R} } = 3$

it follows that:

- $\eqclass 1 {\mathcal R} = \set {1, 3, 4}$

There are $6$ elements of $S$.

Thus the other $3$ elements must all be in the same equivalence class of $\mathcal R$ which does not contain $1$, for example.

Thus we have:

- $\eqclass 2 {\mathcal R} \subseteq \set {2, 5, 6}$

and the information we were given that $2 \mathrel {\mathcal R} 6$ was superfluous.

$\blacksquare$

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $14$