# Equivalence Relation & corresponding equivalence Classes

From my basic understanding, $R$ is an equivalence relation on the set $A$, which is a relation between elements of a set that is reflexive, symmetric, and transitive.

I am not sure how to find the distinct equivalence classes of $R$ in the following relation:

$$A = \{-4,-3,-2,-1,0,1,2,3,4,5\}$$ $$\text{For all}\;x, y \in A,\;x\,R\,y \iff 3 \mid (x-y)$$

• Do you want to prove that the relation you defined is an equivalence relation or what? – Albanian_EAGLE Apr 19 '13 at 15:18

## 4 Answers

You are correct that the relation defined is an equivalence relation on A is an equivalence relation, essentially $$\forall x \in A, xRy \iff 3\mid (x - y) \iff x\equiv y \pmod 3$$

The relation $R$, i.e., defines congruence modulo $3$. So your task boils down to finding the congruence classes, $\pmod 3$.

Do you know how to find the equivalence classes of your set, $\pmod 3$?

• Class one: Which elements have are divisible by $3$? $\quad A_0 = \{-3, 0, 3\}$
• Class two: Which elements leave a remainder of $1$ when divided by $3$? $\quad A_1 =\{-2, 1, 4\}$
• Class three: Which elements leave a remainder of $2$ when divided by $3$? $\quad A_2 = \{-4, -1, 2, 5\}$

You're done: three equivalence classes.

$$A = A_0 \cup A_1 \cup A_2 = \{-4,-3,-2,-1,0,1,2,3,4,5\},$$ $$\quad A_i \cap A_j = \varnothing, \;\text{when}\;\;i\neq j, \text{ for}\;\; i, j \in \{0, 1, 2\}$$

• No, I dont know how to find the equivalence classes of the set. Please help. – CodingWonders90 Apr 19 '13 at 15:26
• Perfectly explained. Now I know how to do the rest of the problems. Thanks! – CodingWonders90 Apr 19 '13 at 15:37
• You're welcome, CodeLover! – Namaste Apr 19 '13 at 15:42
• @amWhy: Excellent when you've answered and know you've taught! +1 – Amzoti Apr 20 '13 at 2:09

Hint: When you need to list all equivalence classes, you should start with one element, and find it's equivalence class. For example, take $0$. Find $_R=\{a\in A|aR0\}$. Then find the 'first' element which is not in $_R$, call it $b$. Now find $[b]_R$. Continue untill you have listed all the elements of $A$.

Take an element (say, -4) and find all elements equivalent to it w. r. t. your relation (i. e. calculate the differences and find out if 3 divides them). Thus you'll have one equivalence class. Proceed in the same fashion until you classify all the elements.

xample: if we have 12 polygons numbered 0 through 11 0  4, 3  1, 6  10, 8  9, 7  4, 6  8, 3  5, 2  11, 11  0 we can partition the twelve polygons into the following equivalence classes: {0, 2, 4, 7, 11};{1, 3, 5};{6, 8, 9,10} Two phases to determine equivalence First phase: the equivalence pairs (i, j) are read in and stored. Second phase: we begin at 0 and find all pairs of the form (0, j). Continue until the entire equivalence class containing 0 has been found, marked, and printed. Next find another object not yet output, and repeat the above process.

• Always consider formatting your posts with MathJax here. – StubbornAtom Oct 6 '16 at 6:12