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
Hello tukilala -
When an equivalence relation is defined on a set , it partitions set into equivalence classes.
Let's break that sentence down a bit. What does partitions mean? Well, it means that divides the whole of set 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, and are two elements from the same equivalence class if and only if .
As an example, suppose set is {human beings} and is the relation "has the same birthday (month and day) as". Then it's fairly obvious that is reflexive (you have the same birthday as yourself), symmetric (if has the same birthday as , then has the same birthday as ) and transitive (if has the same birthday as , and has the same birthday as , then has the same birthday as ). So 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? is the equivalence relation on which is such that if and only if is divisible by 3. What this means is that if and only if and leave the same remainder when divided by 3.
Can you see why? Suppose leaves a remainder and a remainder when they are divided by 3. Then, for some :
and (This means that and are the quotients when and are divided by 3.)
So
Two things then follow:
(1) If is divisible by 3, then , or . In other words, and must leave the same remainder when divided by 3.
(2) If , then . In which case, is divisible by 3.
In other words, is divisible by 3 if and only if and leave the same remainder when divided by 3.
OK so far?
Now we can think about the equivalence classes of . 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