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\}

So the equivalence class for 1 is the same the equivalence class for 4 and 7.

Let’s look at the equivalence class for element 2:

We want to find elements x \in S such that 2 \sim x. This means 2 - x is divisible by 3.

Let t \in \mathbb{Z}. We can write 3t = 2 - x which is equivalent to 2 - 3t = x.

To find the equivalence class for 2, we need to substitute for values of t = -2,-1, 0, 1.

The set \{.. , -1, 2,5,8, ..\} is condensed to \{2, 5, 8 \} to fit the requirements for an equivalence class.

Again, note that the equivalence classes for 2, 5 and 8 are the same.

Repeat the process to obtain the last equivalence class: \{3, 6, 9\}


How clear is this post?