please help me with equivalence relations

**tukilala** · December 16th 2008, 12:54 PM

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

**Plato** · December 16th 2008, 01:06 PM

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:
$\begin{gathered}<br /> \left\{ { \cdots , - 9, - 6, - 3,0,3,6,9, \cdots } \right\} \hfill \\<br /> \left\{ { \cdots , - 8, - 5, - 2,1,4,7, \cdots } \right\} \hfill \\<br /> \left\{ { \cdots , - 7, - 4, - 1,2,5,8, \cdots } \right\} \hfill \\ <br /> \end{gathered}$ .

Can you explain why?

**tukilala** · December 16th 2008, 10:17 PM

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?????

**Grandad** · December 20th 2008, 06:42 AM

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 $R$ is defined on a set $A$ , it partitions set $A$ into equivalence classes.

Let's break that sentence down a bit. What does $R$ partitions $A$ mean? Well, it means that $R$ divides the whole of set $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, $x$ and $y$ are two elements from the same equivalence class if and only if $xRy$ .

As an example, suppose set $A$ is {human beings} and $R$ is the relation "has the same birthday (month and day) as". Then it's fairly obvious that $R$ is reflexive (you have the same birthday as yourself), symmetric (if $x$ has the same birthday as $y$ , then $y$ has the same birthday as $x$ ) and transitive (if $x$ has the same birthday as $y$ , and $y$ has the same birthday as $z$ , then $x$ has the same birthday as $z$ ). So $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? $R$ is the equivalence relation on $\mathbb{Z}$ which is such that $xRy$ if and only if $(x-y)$ is divisible by 3. What this means is that $xRy$ if and only if $x$ and $y$ leave the same remainder when divided by 3.

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

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

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

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

Two things then follow:

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

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

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

OK so far?

Now we can think about the equivalence classes of $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

Thread: please help me with equivalence relations

LinkBack

Thread Tools

Display

please help me with equivalence relations

but why????

Equivalence Classes

Similar Math Help Forum Discussions

Mathematical logic--> Binary relations, orders, and equivalence relations/classes

Equivalence Relations

Question on equivalence relations and equivalence classes

Equivalence Relations

Equivalence Relations

Search Tags