Results 1 to 3 of 3

Math Help - equivalence class ?

  1. #1
    Like a stone-audioslave ADARSH's Avatar
    Joined
    Aug 2008
    From
    India
    Posts
    726
    Thanks
    2

    Post equivalence class ?

    How do we define
    equivalence class ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,598
    Thanks
    1421
    Quote Originally Posted by ADARSH View Post
    How do we define
    equivalence class ?
    First, do you know what an "equivalence relation" is?

    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".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Like a stone-audioslave ADARSH's Avatar
    Joined
    Aug 2008
    From
    India
    Posts
    726
    Thanks
    2

    Wink ..thank you

    A million $ thanks to you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence class
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: March 10th 2010, 09:31 AM
  2. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  3. Equivalence Class HELP!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 19th 2009, 06:52 AM
  4. equivalence class
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 20th 2008, 06:32 PM
  5. Equivalence class
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 10th 2007, 02:50 AM

Search Tags


/mathhelpforum @mathhelpforum