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 be a set with the following relation:
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: This is the set of all odd elements from A.
Similarly, the even elements can be grouped together to form the set:
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 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: is a set. Let x y if and only if is divisible by , where x and y are elements of S.
First, we need to show that 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 is reflexive.
Let x be an element from S. Since and 0 is divisible by 3, then we know is reflexive as required.
Show that is symmetric.
Let x and y be elements from S such that x y.
We want to show that y x. This is equivalent to saying that is divisible by In other words, we can find some integer (let’s call it p) such that
Since x y, then the definition of (in our question) tells us that we have is divisible by
This is the same as saying we can find at least one integer such that
We can multiply both sides of the equation by -1 and get: We do this because we want the right hand side to have the form:
We can finally write that y x because is the same as writing
So the integer we wanted is In conclusion, is, indeed, symmetric.
Show that is transitive.
Let x, y and z be elements from S such that x y and y z hold true.
We want to show that x z holds, too. In other words, is divisible by so there exists some integer p such that
Since x y, then there exists some integer such that
Similarly, y z so there exists some integer such that
We can add the above equations to get
So since then their sum is also some integer. In fact, this is the integer we were looking for:
In other words, is divisible by as required! This tells us x z, hence is transitive.
So is an equivalence relation! Now we can go on to find its equivalence classes.
Find the equivalence classes of
Recall our set . An equivalence class for is defined as the subset This subset has all the elements that relate to a under the relation R. In our case, R is denated
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 . In other words, we want to find elements in S such that 1 x:
Since 1 x means is divisible by
Then we know there exists some such that
We can rewrite this as
We now substitute different values of (e.g. …, -2, -1, 0 , 1, 2,…) to find values of that are in set S.
For instance, we get the set for different values of 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
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 such that 2 x. This means is divisible by
Let We can write which is equivalent to
To find the equivalence class for 2, we need to substitute for values of
The set is condensed to 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: