3
$\begingroup$

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)$$

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

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

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

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 $[0]_R=\{a\in A|aR0\}$. Then find the 'first' element which is not in $[0]_R$, call it $b$. Now find $[b]_R$. Continue untill you have listed all the elements of $A$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.