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$ be a set and let $\sim$ be an equivalence relation on $X$. If $x \in X$ then the Equivalence Class of $x$ is the set $[x] = \{ y \in X : x \sim y \}$, that is, $[x]$ is the set of all elements in $X$ which are equivalent to $x$.

For example, let $X = \{ 1, 2, 3, 4 \}$ and let:

(1)

\begin{align} \quad \sim = \{ (1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4) \} \end{align}

It can easily be shown that $\sim$ is an equivalence relation on $X$. Furthermore, the equivalence classes are:

(2)

\begin{align} \quad [1] &= \{ 1, 2 \} \\ \quad [2] &= \{ 1, 2 \} \\ \quad [3] &= \{ 3 \} \\ \quad [4] &= \{ 4 \} \end{align}

Observe that the set of equivalence classes $\{ [1], [2], [3], [4] \} = \{ [1], [3], [4] \}$ is a partition of $X$. In the theorem below we will prove that if $X$ is a set and $\sim$ is any equivalence relation on $X$ then the set of equivalence classes is a partition of $X$.

Theorem 1: Let $X$ be a set and let $\sim$ be an equivalence relation on $X$. If $\{ [x_k] : k \in K \}$ is the set of all equivalence classes of $X$ then $\{ [x_k] : k \in K \}$ is a partition of $X$.

• Proof: We first show that for each $k \in K$, $[x_k] \neq \emptyset$. Indeed, since $\sim$ is an equivalence relation on $X$, it is reflexive. So $x_k \sim x_k$. Hence $x_k \in [x_k]$. So $[x_k] \neq \emptyset$.

• Now we show that if $k_1, k_2 \in K$ and $k_1 \neq k_2$ then $[x_{k_1}] \cap [x_{k_2}] = \emptyset$ or $[x_{k_1}] = [x_{k_2}]$. Suppose otherwise, i.e., suppose that there exists an $x \in [x_{k_1}] \cap [x_{k_2}]$. Then $x \sim x_{k_1}$ and $x \sim x_{k_2}$. So $x_{k_1} \sim x_{k_2}$ from the symmetry and transitivity of $\sim$. So $[x_{k_1}] = [x_{k_2}]$

• Lastly we show that $X = \bigcup_{k \in K} [x_k]$. Let $x \in X$. Then $x \sim x_k$ for some $k \in K$ so $x \in [x_k] \subseteq \bigcup_{k \in K} [x_k]$. Therefore $X \subseteq \bigcup_{k \in K} [x_k]$. The reverse inclusion is trivial.

• Hence $\{ [x_k] : k \in K \}$ is a partition of $X$. $\blacksquare$