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
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?
Hello tukilala -
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?
Grandad