We define a relation R on Z by setting xRy if and only if x-y divisible by 3.

Find all the equivalence classess of R

someone can help me to solve me this? and explain me a bit with words what r u doing....

thnx

2. Originally Posted by tukilala
We define a relation R on Z by setting xRy if and only if x-y divisible by 3. Find all the equivalence classess of R.
There are three equivalence classess:
$\displaystyle \begin{gathered} \left\{ { \cdots , - 9, - 6, - 3,0,3,6,9, \cdots } \right\} \hfill \\ \left\{ { \cdots , - 8, - 5, - 2,1,4,7, \cdots } \right\} \hfill \\ \left\{ { \cdots , - 7, - 4, - 1,2,5,8, \cdots } \right\} \hfill \\ \end{gathered}$.

Can you explain why?

3. ## but why????

what is common to
......1,4,7..........
......2,5,8..........
......3,6,9.......

????
why this is the three equivalence classess????
what is special about each class?????

4. ## Equivalence Classes

Hello tukilala -

Originally Posted by tukilala
We define a relation R on Z by setting xRy if and only if x-y divisible by 3.

Find all the equivalence classess of R

someone can help me to solve me this? and explain me a bit with words what r u doing....

thnx
When an equivalence relation $\displaystyle R$ is defined on a set $\displaystyle A$, it partitions set $\displaystyle A$ into equivalence classes.

Let's break that sentence down a bit. What does $\displaystyle R$ partitions $\displaystyle A$ mean? Well, it means that $\displaystyle R$ divides the whole of set $\displaystyle A$ into disjoint (non-overlapping) subsets. These subsets are called equivalence classes.

Why are they called equivalence classes? Because any one of these subsets contains only elements that are equivalent to one another. In other words, $\displaystyle x$ and $\displaystyle y$ are two elements from the same equivalence class if and only if $\displaystyle xRy$.

As an example, suppose set $\displaystyle A$
is {human beings} and $\displaystyle R$ is the relation "has the same birthday (month and day) as". Then it's fairly obvious that $\displaystyle R$ is reflexive (you have the same birthday as yourself), symmetric (if $\displaystyle x$ has the same birthday as $\displaystyle y$, then $\displaystyle y$ has the same birthday as $\displaystyle x$) and transitive (if $\displaystyle x$ has the same birthday as $\displaystyle y$, and $\displaystyle y$ has the same birthday as $\displaystyle z$, then $\displaystyle x$ has the same birthday as $\displaystyle z$). So $\displaystyle R$ is an equivalence relation. What are its equivalence classes? Well, of course, there's an equivalence class for each day of the year - 365 of them altogether (or even 366, if you count February 29!). Each class contains all the people whose birthdays are on that particular day.

Now, what about your question? $\displaystyle R$ is the equivalence relation on $\displaystyle \mathbb{Z}$ which is such that $\displaystyle xRy$ if and only if $\displaystyle (x-y)$ is divisible by 3. What this means is that $\displaystyle xRy$ if and only if $\displaystyle x$ and $\displaystyle y$ leave the same remainder when divided by 3.

Can you see why? Suppose $\displaystyle x$ leaves a remainder $\displaystyle r_1$ and $\displaystyle y$ a remainder $\displaystyle r_2$ when they are divided by 3. Then, for some $\displaystyle m, n \in \mathbb{Z}$:

$\displaystyle x=3m+r_1$ and $\displaystyle y=3n+r_2$ (This means that $\displaystyle m$ and $\displaystyle n$ are the quotients when $\displaystyle x$ and $\displaystyle y$ are divided by 3.)

So $\displaystyle x-y=(3m+r_1)-(3n+r_2)$

$\displaystyle =3(m-n)+(r_1-r_2)$

Two things then follow:

(1) If $\displaystyle x-y$ is divisible by 3, then $\displaystyle r_1-r_2=0$, or $\displaystyle r_1=r_2$
. In other words, $\displaystyle x$ and $\displaystyle y$ must leave the same remainder when divided by 3.

(2) If $\displaystyle r_1=r_2$, then $\displaystyle x-y=3(m-n)$. In which case, $\displaystyle x-y$ is divisible by 3.

In other words, $\displaystyle x-y$ is divisible by 3 if and only if $\displaystyle x$ and $\displaystyle y$ leave the same remainder when divided by 3.

OK so far?

Now we can think about the equivalence classes of
$\displaystyle R$. The most important question is: what are the possible remainders when a number is divided by 3? The answers, of course, are 0, 1 and 2. This means that there will be:

• one equivalence class for all the numbers that leave a remainder 0;
• one equivalence class for all the numbers that leave a remainder 1;
• and one equivalence class for all the numbers that leave a remainder 2.

There aren't any other remainders, so every whole number must appear in one of these three classes.

Can you see now where Plato's answers came from?