Results 1 to 2 of 2

Math Help - Equivalence classes and relations.

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Equivalence classes and relations.

    Prove that an equivalence relation can on a set S uniquely defines a partition of that set.
    Suppose S can be separated into A_1, A_2,.......,A_n partitions.

    Hence A_1 \cup A_2 \cup........\cup A_n=S. Assume that reflexivity, symmetry and transitivity hold.

    1). Reflexivity \Rightarrow A_1 \cap A_i=\phi since an element from one subset cannot belong to another subset (property 2 of a partition- the intersections are empty).

    This is where I have no idea where to go. Symmetry and transitivity I cannot connect to the definition of a partition.

    I was wondering if this is the right idea to follow.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    Quote Originally Posted by Showcase_22 View Post
    Suppose S can be separated into A_1, A_2,.......,A_n partitions.

    Hence A_1 \cup A_2 \cup........\cup A_n=S. Assume that reflexivity, symmetry and transitivity hold.

    1). Reflexivity \Rightarrow A_1 \cap A_i=\phi since an element from one subset cannot belong to another subset (property 2 of a partition- the intersections are empty).

    This is where I have no idea where to go. Symmetry and transitivity I cannot connect to the definition of a partition.

    I was wondering if this is the right idea to follow.
    This is not a proof. I'll give you an outline or a proof. you want to prove (i) that all element in S belong to an equivalence class and (ii) that any two equivalence classes are either disjoint or equal and that once you have proved these two properties your pretty much done.

    i) is trivial using the reflexive property.

    ii) first suppose  [s_{1}] and [s_{2}] share and element x. then by definition s_{1}Rx and s_{2}Rx using the transitivity and symmetry properties you can show that s_{1}Rs_{2}. I'll leave you to prove that  s_{1}Rs_{2}  iff [s_{1}] = [s_{2}].


    Bobak
    Last edited by bobak; December 15th 2008 at 06:40 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  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 Relations and Classes
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 13th 2009, 04:43 AM
  5. Equivalence relations and classes.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2008, 05:51 AM

Search Tags


/mathhelpforum @mathhelpforum