# Homework Help: Equivalence class definition

1. Jul 5, 2010

### annoymage

1. The problem statement, all variables and given/known data

Definition: If A is a set and if ~ is an equivalence relation on A, then the equivalence class of a$$\in$$A is the set {x$$\in$$A l a~x}. We write it as cl(a)

Let S be the set of all integer. Given a,b $$\in$$ S, define a~b if a-b is an even integer.

so, the equivalent class of a consist of all integer of the form a+2m, m are rational number.

and can someone explain why only cl(0) and cl(1) is the distinctive equivalence classes?

is cl(1) simply means {x$$\in$$A l 1~x}??

Last edited: Jul 5, 2010
2. Jul 5, 2010

You mean, where m is an integer, I assume?

Use the definition and calculate cl(0) and cl(1).

3. Jul 5, 2010

By the way, for any equivalence relation, x ~ y if and only if cl(x) = cl(y). Is 0 - 1 an even integer?

4. Jul 5, 2010

### annoymage

yes, integer,

i still confused with what exactly is cl(0) or cl(1)

is cl(1)= {x$$\in$$S l 1~x}= 1+2m , m is integer??

if it is, why not cl(2)? because it's equivalent relation with "even number" too

Last edited: Jul 5, 2010
5. Jul 5, 2010

Write down cl(2), slowly, using your definitions. Then write down cl(0). Is 0 ~ 2? In general, any two equivalence classes are either the same or they are disjoint. In your case, you have two equivalence classes (disjoint) whose union is the set of integers.

6. Jul 5, 2010

### HallsofIvy

Given a an equivalence relation, ~, on a set S, the equivalence class, cl(a), is the set of all objects, x, in S such that x~ a. That is, it is the set of all things in S equivalent to a.

To find equivalence classes, first you need to understand the equivalence relation!

Here, the equivalence relation is "a~ b if and only if a-b is an even integer.

It shouldn't take too much to see that if a and b are "of the same parity" (either both even or both odd) then a- b is even:
If a and b are both even then we can write a= 2m, b= 2n so that a- b= 2m- 2n= 2(m-n) and so is even.
If a and b are both odd then we can write a= 2m+1, b= 2n+ 1 so that a- b= (2m+1)- (2n+1)= 2m- 2n= 2(m- n) which again is even.

If is only if one of a, b is even and the other odd that a and b are NOT even:
If a is even and b odd, then a= 2m and b= 2n+1 so a- b= 2m-(2n+1)= m- 2n- 1= 2(m-n)-1= 2(2m-n-1)+ 1 which is an odd number, not an even number. Similarly, if a is odd and b even, then a= 2m+1, b= 2n so a- b= (2m+1)- 2n= 2(m- n)+ 1, an odd number.

That is, odd numbers are equivalent to all other odd numbers and even numbers are equivalent to all other even numbers. The two equivalence classes are the set of all odd numbers and the set of all even numbers. 1 is in the first of those and 0 is in the second.

7. Jul 5, 2010

### annoymage

sorry but i'm still moving in circle, and still new with algebra

hmm, you kinda creating me more question than answer

ok, 1 by 1,

"In general, any two equivalence classes are either the same or they are disjoint"

let m be integer

cl(0)=2m={...,-2,0,2,...}
cl(2)=2+2m={...,0,4,6,..}

so this is not disjoint because 0 in the element of cl(0) and cl(2),
and they are not the same either??

thank you for enduring my whine

8. Jul 5, 2010

### annoymage

ok maybe i understand, try check my understanding with other question

the equivalence relation is "a~b if a-b is a multiple on n(n>1 be a fixed integer)"

so the equivalence class are set of x~a,

x-a=kn (k in integer) => x=a+kn

so the distinctive equivalence class are cl(0),cl(1),....,cl(n-1)

cl(n)=(k+1)n is simply the same set as cl(0)=kn, so it doesn't count.

suddenly i get all what radou was conveying.

anyway, correct me if i went wrong (time to sleep, see you tomorrow ;P)

Last edited: Jul 5, 2010
9. Jul 5, 2010

### HallsofIvy

Yes, and what you get are the "integer modulo n".

Earlier you said
No, that's impossible. One of important properties of "equivalence classes" on a set S is that they "partition" S- they divide S into sets such that every member of S is in one and only one such set. If two equivalence classes have any member in common, then they have all members in common- they are the same equivalence class (I am assuming, of course, equivalence classes under the same equivalence relation). That is true because if "a" is in equivalence class C1 and in C2, "b" is in C1, and "c" is in C2, then we have a~ b because they are both in C1, a~ c because they are in they are in C2 and so b= c by the "transitive property" of equivalence relations.

Last edited by a moderator: Jul 5, 2010
10. Jul 6, 2010

### annoymage

you mean b~c right?

11. Jul 6, 2010