Understanding Equivalence Classes in Integer Sets

[annoymage]

Homework Statement

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

 

[radou]

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

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

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

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

 

[radou]

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

 

[annoymage]

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

yes, integer,

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

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

 

[radou]

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.

 

[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.

 

[annoymage]

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.

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

 

[annoymage]

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.

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)

 

[HallsofIvy]

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.

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

suddenly i get all what radou was conveying.

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

Earlier you said

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

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.

 

[annoymage]

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.

you mean b~c right?

 

[radou]

Yes, HallsofIvy meant b ~ c (since a ~ b and a ~ c).

 

[HallsofIvy]

Yes, thanks.