I'm studying discrete mathematics in my course at university and I'm going through notes on relations, equivalence relations and classes and such. I've come across an example on equivalence classes but struggling to grasp the concept. If anyone could explain in better detail what defines an equivalence class, that would be great!
I'll leave the actual example below.
Let R be the relation on the set A = {1,3,5,9,11,18} defined by the
pairs (a,b) such that a - b is divisible by 4.
Given a set A with an equivalence relation R on it, we can break up
all elements in A into disjoint groups (subsets) such that within
each group all elements are related between themselves but no two
elements from two different groups are related. Such groups of elements
are called equivalence classes.
For example: C1 = {1,5,9}, C2 = {3,11}, C3 = {18}
How are the elements in each subset here related to each other? and where's an example where an element of C1 is not related to an element in say C2?
Thank you.
Best Answer
You are given a set $A = \{1,3,5,9,11,18\}$ and a relation $R$ on $A$ given by $$R = \{(a,b) \mid a - b \text{ is divisible by } 4\}.$$ For example, $(1,9) \in R$ because $1 - 9 = 8$ is divisible by $4$.
Now, any time we have an equivalence relation on a set, this relation partitions the set into disjoint sets called equivalence classes, where each equivalence class is given by those elements that are equivalent to each other with respect to the equivalence relation. In order for this to make sense, however, we first need to check that $R$ is indeed an equivalence relation, otherwise we can not speak of its equivalence classes.
Clearly $R$ is reflexive because $a - a = 0$, and $0$ is always divisible by $4$. $R$ is also symmetric because if $a$ is divisible by $4$, then $-a$ is divisible by $4$. If $a - b$ is divisible by $4$ and $b - c$ is divisible by $4$, then $a - c = (a - b) + (b - c)$ is also divisible by $4$, so $R$ is also transitive, and hence an equivalence relation.
The equivalence classes for $R$ on $A$ turn out to be $$C_1 = \{1,5,9\}$$ $$C_2 = \{3,11\}$$ $$C_3 = \{18\}$$ Note that these sets are disjoint, and together they contain all elements of $A$, just like we expected. To see why for example $C_1$ is an equivalence class, notice that $1 - 5 = 4$ and $1 - 9 = 8$ are divisible by $4$, so $1$ is equivalent to $5$ and $9$ with respect to $R$. However, $1$ is not equivalent to for example $3$, because $1 - 3 = 2$ is not divisible by $4$. Hence $1$ and $3$ must be in different equivalence classes.