LinkBack URL
About LinkBacks
equivalence class ?
How do we define
equivalence class ?
First, do you know what an "equivalence relation" is?Originally Posted by ADARSH
An equivalence relation is a relation, say "x is related to y" is some way that satisfies
a) Any x is related to itself (reflexive property)
(that means, for example, that x> y is NOT an equivalence relation)
b) If x is related to y, then y is related to x (symmetric property)
(that means, for example, that [tex]x\ge y[tex] is NOT an equivalence relation)
c) If x is related to y, and y is related to z, then x is related to z (transitive property).
Those are all properties of the most basic of all relations, identity (x is only related to itself, or x= x). All equivalence relations say two things are "equivalent" if they are the same in some way.
An equivalence class is simply a set that contains only things that are equivalent to one another by the given equivalence relation.
A commonly used relation is this: "For all integers, x, y, x is equivalent to y if and only if x-y is an integer multiple of 3". It is
1) Reflexive: x- x= 0= 3(0)
2) Symmetric: If x is equivalent to y, then x- y= 3n for some integer n. Then y- x= -(y-x)= -(3n)= 3(-n), an integer multiple of 3.
3) Transitive. If x is equivalent to y and y is equivalent to z, then x-y= 3n and y- z= 3m for some integers m and n. Then x- z= (x- y)+ (y- z)= 3n+ 3m= 3(n+m), an integer multiple of 3.
Now, suppose we start with y= 0. What integers are equivalent to 0? Well, we must have x- 0= x a multiple of 3: the integers equivalent to 0 are precisely the multiples of 3. One "equivalence class" for this equivalence relation is "all multiples of 3": {0, 3, -3, 6, -6, ...}
What integers are equivalent to 1? Well, we must have x- 1 a multiple of 3: x- 1= 3n so x= 3n+ 1. By taking different integer values for n, we get different numbers that are equivalent to 1: x= 3(1)+ 1= 4, x= 3(2)+1= 7, x= 3(-1)+ 1= -2, etc. Those are precisely the number that are 1 more than a multiple of 3: {1, 4, -2, 7, -5, 10, -8, ...}
What integers are equivalent to 2? Well, we must have x-2 a multiple of 3: x- 2= 3n so x= 3n+ 2. x= 3(0)+ 2= 2, x= 3(1)+2= 5, x= 3(-1)+ 2= -1, etc. Those are precisely the numbers that are 2 more than a multiple of 3: {2, -1, 5, -4, 8, -7, ...}
What integers are equivalent to 3? Now we must have x- 3= 3n so x= 3n+ 3= 3(n+1). But that is just another multiple of 3! More generally since 3 is itself equivalent to 0, by the "transitive" relation the numbers that are equivalent to 3 are exactly the numbers that are equivalent to 0: we already have this equivalence class. In fact, it is easy to see that all integers are in one of the three equivalence classes we already have:
{all integers of the form 3n}
{all integers of the form 3n+1}
{all integers of the form 3n+2}
You might recognize that as the same as "integers modulo 3".
  |
..thank you
