1.4 Equivalence classes

Let’s recall the definition of an equivalence relation:

A relation R on a set A is termed an equivalence relation if it is simultaneously reflexive, symmetric and transitive.

Let’s look at more examples:

Example One: Let $A = \{2, 11, 17, 20\}$ be a set with the following relation: $R = \{ (2,2) (11,11) (17,17) (20,20) (2,20) (20,2) (11,17) (17,11) \}.$

The relation described by R is termed “the same parity.” Elements x and y are said to have the same parity if they are both odd or both even. In our case, the elements 11 and 17 are both odd – hence have the same parity. Similarly, 20 and 2 have the same parity because they are both even. An element will always have the same parity as itself.

The elements that share the same parity as 11 can be grouped together to form a set: $O = \{ 11, 17 \}.$ This is the set of all odd elements from A.

Similarly, the even elements can be grouped together to form the set: $E = \{ 2, 20\}.$

The new sets, O and E, form the equivalence classes of the relation R on set A.

Equivalence classes are defined in the following way: Suppose R is an equivalence relation on a set A. Given any element a from set A, the equivalence class containing a is the subset $\{ x \in A : xRa \}$ of A consisting of all the elements of A that relate to a. This set is denoted as [a].

In other words, the equivalence class of some element a in set A is a subset of set A. The subset contains all the elements related to a under the given relation R. Let’s look at an example.

Example Two: $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ is a set. Let x $\sim$ y if and only if $x - y$ is divisible by $3$ , where x and y are elements of S.

First, we need to show that $\sim$ is an equivalence relation. Then we can find the equivalence classes.

Note: To prove this if and only if statement, it is enough to assume the left hand side and prove the right.

Show that $\sim$ is reflexive.

Let x be an element from S. Since $x-x = 0$ and 0 is divisible by 3, then we know $\sim$ is reflexive as required.

Show that $\sim$ is symmetric.

Let x and y be elements from S such that x $\sim$ y.

We want to show that y $\sim$ x. This is equivalent to saying that $y - x$ is divisible by $3.$ In other words, we can find some integer (let’s call it p) such that $3p = y - x.$

Since x $\sim$ y, then the definition of $\sim$ (in our question) tells us that we have $x - y$ is divisible by $3.$

This is the same as saying we can find at least one integer $t,$ such that $3t = x -y$

We can multiply both sides of the equation by -1 and get: $-3t = y - x.$ We do this because we want the right hand side to have the form: $y - x$

We can finally write that y $\sim$ x because $-3t = y - x$ is the same as writing $3(-t) = y - x.$

So the integer we wanted is $p = -t.$ In conclusion, $\sim$ is, indeed, symmetric.

Show that $\sim$ is transitive.

Let x, y and z be elements from S such that x $\sim$ y and y $\sim$ z hold true.

We want to show that x $\sim$ z holds, too. In other words, $x - z$ is divisible by $3$ so there exists some integer p such that $3p = x -z$

Since x $\sim$ y, then there exists some integer $t$ such that $3t = x - y.$

Similarly, y $\sim$ z so there exists some integer $r$ such that $3r = y -z.$

We can add the above equations to get

$3t + 3r = (x - y) + (y - z)$

$3(t + r) = x + (-y + y) - z$

$3(t + r) = x + 0 - z$

$3(r + t) = x - z$

So since $r, t \in \mathbb{Z},$ then their sum $r + t$ is also some integer. In fact, this is the integer we were looking for: $p = r + t$

In other words, $x - z$ is divisible by $3$ as required! This tells us x $\sim$ z, hence $\sim$ is transitive.

So $\sim$ is an equivalence relation! Now we can go on to find its equivalence classes.

Find the equivalence classes of $\sim$

Recall our set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ . An equivalence class for $a \in S$ is defined as the subset $\{ x \in S : xRa \}.$ This subset has all the elements that relate to a under the relation R. In our case, R is denated $\sim.$

Lets find the equivalence class for 1. We need to find a subset of S such that all the elements in the subset are related to 1 under $\sim$ . In other words, we want to find elements $x$ in S such that 1 $\sim$ x:

Since 1 $\sim$ x means $1 - x$ is divisible by $3,$

Then we know there exists some $p \in \mathbb{Z}$ such that $3p = 1 - x$

We can rewrite this as $3p -1 = -x$

$1 - 3p = x$

We now substitute different values of $p$ (e.g. …, -2, -1, 0 , 1, 2,…) to find values of $x$ that are in set S.

For instance, we get the set $\{.. , -5, -2, 1, 4, 7, 10, ..\}$ for different values of $p.$ However, since an equivalence class is defined as a subsets of S and S only consists of positive integers 1 to 9, then we must remove the negative values from the set obtained. In conclusion, the equivalence class of 1 is the set $\{ 1, 4, 7\}$