Equivalence Classes

# Equivalence Classes

Recall from the Equivalence Relations page that an equivalence relation on a set $X$ is a reflexive, symmetric, and transitive relation on $X$.

We will now look at the equivalence classes of an equivalence relation on $X$ which we define below.

Definition: Let $X = \{ x_1, x_2, ... \}$ be a set and let $\sim$ be an equivalence relation on $X$. Then the Equivalence Class for each $x_j \in X$, $j \in \{ 1, 2, ...\}$ denoted $[x_j]$ is defined to be the set of all elements $x \in X$ such that $x \sim x_j$, that is $[x_j] = \{ x \in X : x \sim x_j \}$. |

We will now look at an important theorem which will tell us that a set $X$ can be partitioned its collection of equivalence classes.

Theorem 1: Let $X = \{ x_1, x_2, ..., x_n \}$ be a finite $n$-element set and let $\sim$ be an equivalence relation on $X$. Then the collection of sets $[x_1], [x_2], ..., [x_n]$ form a partition of $X$, that is $X = [x_1] \cup [x_2] \cup ... \cup [x_n] = \bigcup_{i=1}^{n} [x_i]$ and for each $i, j \in \{1, 2, ..., n \}$ where $i \neq j$ we have that $[x_i] \cap [x_j] = \emptyset$. |

*Theorem 1 also holds when $X$ is an infinite set.*

**Proof:**Let $X = \{ x_1, x_2, ..., x_n \}$ be a finite $n$-element set and let $\sim$ be an equivalence relation on $X$. Consider the collection of equivalence classes $[x_1], [x_2], ..., [x_n]$. Note that for each $j \in \{1, 2, ..., n \}$ we have $x_j \in [x_j]$ since $x_j ~ x_j$. Therefore each $[x_j] \neq \emptyset$. We now need to show that $X = \bigcup_{i=1}^{n} [x_i]$.

- Let $x \in X$. Since $~$ is an equivalence relation we have that $x ~ x$ and so for some $j \in \{1, 2, ..., n \}$ we have that $x \in [x_j]$, so $X \subseteq \bigcup_{i=1}^{n} [x_i]$. Now let $x \in \bigcup_{i=1}^{n} [x_i]$. Then there exists an $j \in \{ 1, 2, ..., n \}$ such that $x \in [x_j]$. But $[x_j] = \{ x \in X : x ~ x_j \}$ so clearly $x \in X$.

- We finally show that for each $i, j \in \{1, 2, ..., n \}$ where $i \neq j$ we have that $[x_i] \cap [x_j] = \emptyset$. We will show this by contradiction. Suppose that there exists an $i, j \in \{1, 2, .., n \}$ such that $[x_i] \cap [x_j] \neq \emptyset$. Then there exists an element $y \in [x_i] \cap [x_j]$. Therefore $y \in [x_i]$ and $y \in [x_j]$. Since $y \in [x_i]$ we have that $y ~ x_i$, and since $y \in [x_j]$ we have that $y ~ x_j$, i.e., $x_j ~ y$. Since $x_j ~ y$ and $y ~ x_i$ we have that by the transitive property of the relation $~$ that then $x_j ~ x_i$. Therefore we have that $[x_i] \subseteq [x_j]$ and similarly $[x_i] \supseteq [x_j]$. Therefore $[x_i] = [x_j]$ which is equivalent to any two equivalent classes being disjoint.

- Therefore we have that $[x_1], [x_2], ..., [x_n]$ form a partition of $X$. $\blacksquare$