Results 1 to 5 of 5

Math Help - Equivalence classes

  1. #1
    Junior Member
    Joined
    Apr 2007
    Posts
    32

    Question Equivalence classes

    If you have a fixed equivalence relation ~ on a set S, then for any a contained in S the set:
    [a] = { b in S : b~a } is called the equivalence class of a.

    Can someone please explain the following 2 facts about equivalence classes:
    1) every element in S belongs to atleast one equivalence class because the relation is necessarily reflexive.

    2)No element can belong to two different equivalence classes.


    Thirdly, i get the impression that if u take into account both 1) and 2) this amounts to saying that every element belongs to exactly one equivalence class. If this is the case then what is the use of there being such a thing as equivalence classes if their only members are the elements themselves...i.e. for all a in S, [a] = {a} ?????
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Apr 2007
    Posts
    32
    Also, on the matter of equivalence relations, my textbook states that any partition on a set determines an equivalence relation on it. What exactly does this mean? (I understand what partitions and equivalence relations are but could someone show what they're saying a little more formally?)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Obstacle1 View Post
    If you have a fixed equivalence relation ~ on a set S, then for any a contained in S the set:
    [a] = { b in S : b~a } is called the equivalence class of a.

    Can someone please explain the following 2 facts about equivalence classes:
    1) every element in S belongs to atleast one equivalence class because the relation is necessarily reflexive.

    2)No element can belong to two different equivalence classes.
    This is the fundamental theorem of equivalence classes. It is used all the time in advanced mathematics.

    It is a theorem that partitions a non-empty set. Hence it takes all the elements of the set and puts them into disjoint sets.

    For example consider:
    Z={0,1,-1,2,-2,3,-3,...}

    And define x~y if and only if x=y(mod 2).
    So pick any number, say 0:
    Now find all y so that: 0 = y (mod 2).
    Those are: 0 (itself), 2, -2, 4, -4, ....

    Now pick any number which is not much those just listed above. Because if you do then the ones that are equivalent to it is going to be the same class of numbers.

    Say you pick 1 (for it is not in that set)/
    Now find all y so that: 1 = y(mod 2).
    Those are: 1(itself), -1,3,-3,.....

    As you can see we have completely depleted all the elements of the set. And divided the set into two disjoint sets:
    {0,2,-2,...}
    {1,-1,3,-3,...}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Apr 2007
    Posts
    32
    Quote Originally Posted by ThePerfectHacker View Post
    This is the fundamental theorem of equivalence classes. It is used all the time in advanced mathematics.

    It is a theorem that partitions a non-empty set. Hence it takes all the elements of the set and puts them into disjoint sets.

    For example consider:
    Z={0,1,-1,2,-2,3,-3,...}

    And define x~y if and only if x=y(mod 2).
    So pick any number, say 0:
    Now find all y so that: 0 = y (mod 2).
    Those are: 0 (itself), 2, -2, 4, -4, ....

    Now pick any number which is not much those just listed above. Because if you do then the ones that are equivalent to it is going to be the same class of numbers.

    Say you pick 1 (for it is not in that set)/
    Now find all y so that: 1 = y(mod 2).
    Those are: 1(itself), -1,3,-3,.....

    As you can see we have completely depleted all the elements of the set. And divided the set into two disjoint sets:
    {0,2,-2,...}
    {1,-1,3,-3,...}

    Thanks. That has made things a lot clearer. Unfortunately i think i was confused just by the explanation i had read in my textbook. This often seems to be the case with me, is there anything besides repeated practice a wise mathematician such as yourself could recommend to me to avoid becoming confused by textbook explanations in the future?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1615
    Awards
    1
    Quote Originally Posted by Obstacle1 View Post
    Also, on the matter of equivalence relations, my textbook states that any partition on a set determines an equivalence relation on it. Could someone show what they're saying a little more formally?
    There is a two-way relationship between a partition of a set and an equivalence relation on the same set.
    Given a relation ~ on a set S then the collection of equivalence classes determined by ~ forms a partition of S. You did that above.

    Now start with a partition \Pi of S. \Pi is a collection of non-empty subsets of S, their union is S. Define a relation on S as followers: \left( {x,y} \right) \in \rho if and only if x\& y belong to the same cell in \Pi. It is easy to see that because each x \in S is in some cell of \Pi then \rho is reflexive. And we know that ‘same as’ is symmetric and transitive. There \rho is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence classes of P(N)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 13th 2010, 08:26 AM
  2. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM
  5. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 30th 2008, 11:04 PM

Search Tags


/mathhelpforum @mathhelpforum