1. ## equivalence relation

Hey guys, question... Let A = {1,2,3,4,5,6,7,8,9,10}. Define a relation R on A by writing (x,y) $\epsilon$ R iff 3|(x-y).

a) show that R is an equivalence relation on A.

Is it reflexive? Yes! since x-x = 0 and 0 is divisible by 3. (Eg x = 6)
Is it symmetric? Yes! since if x-y is divisible by 3, then y-x is divisible by 3. (Eg, x=8, y=2)
Is it transitive? Yes! since if 3|(x-y) and 3|(y-z), then 3|(x-z). (Eg. x=10, y=1 and z=4).

Is this correct? thanks..

2. Any help anyone? thank you

3. You're correct. But leave out the examples. They're irrelevant to the proof, in the sense that just because something holds for example x,y,z in A doesn't entail that it holds for all x,y,z in A.

Here's how I would write it:

x-x = 0, and 3*0 = 0, so 3|x-x. So we have reflexivity.

Suppose 3|x-y. So let 3*z = x-y. So 3*-z = y-x. So 3|y-x. So we have symmetry.

Suppose 3|x-y and 3|y-z. So let 3*v = x-y and 3*w = y-z.
But x-z = (x-y)+(y-z) = (3*v)+(3*w) = 3(v+w). So 3|x-z. So we have transitivity.

4. Originally Posted by jvignacio
Hey guys, question... Let A = {1,2,3,4,5,6,7,8,9,10}. Define a relation R on A by writing (x,y) $\epsilon$ R iff 3|(x-y).

a) show that R is an equivalence relation on A.

Is it reflexive? Yes! since x-x = 0 and 0 is divisible by 3. (Eg x = 6)
Is it symmetric? Yes! since if x-y is divisible by 3, then y-x is divisible by 3. (Eg, x=8, y=2)
Is it transitive? Yes! since if 3|(x-y) and 3|(y-z), then 3|(x-z). (Eg. x=10, y=1 and z=4).

Is this correct? thanks..
Incidentally, this equivalence relation is just congruence (mod 3).

5. Originally Posted by undefined
Incidentally, this equivalence relation is just congruence (mod 3).
Good point. We could prove this for any n for congruence(mod n).

6. Thanks for the replys! What about finding the equivalent classes on R???? Thank you!

7. Originally Posted by jvignacio
Thanks for the replys! What about finding the equivalent classes on R???? Thank you!
I don't know what you mean.

It is possible to partition A into subsets by equivalence class, as follows

{1,4,7,10}
{2,5,8}
{3,6,9}

The same can be done for the set of integers.

Or you can talk about the set of all equivalence classes, which is often expressed in terms of common residues, like this

$\{\bar0,\bar1,\bar2\}$

or this

{0,1,2}

Is that what you had in mind?

8. thank you, i ment the first solution..