Results 1 to 4 of 4

Math Help - Equivalence relation

  1. #1
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318

    Equivalence relation

    Let S be a finite set and denote by 2^S = {A|A ⊆ S} the set of all subsets of S. Define
    a relation ∼ on 2^S by A ∼ B if and only if A and B have the same number of elements.
    (a) Show that ∼ is an equivalence relation on 2^S.
    (b) Let S = {1, 2, 3, 4}. List the (sixteen) elements of 2^S and explicitly list the
    elements in each equivalence class determined by ∼.

    I understand how to do (a), but not b.
    For (b), I have 2^1=2,2^2=4,2^3=8,2^4=16
    I have 2 elements of 2^S because 8 and 16 aren't in S.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    By 2^S it's not meant to raise 2 to a power (although there's a reason that notation is used), but rather to take all possible subsets of S. Then you partition 2^S (the set of all subsets) into equivalence classes based on their cardinality. So the class of subsets with zero elements is {{}}, the class of one-element subsets is {{1},{2},{3},{4}}, and so forth.

    How many subsets have four elements?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    That makes a lot more sense now.
    Only one subset has 4 elements, the subset being S itself.
    If 2^S is not meant to raise 2 to a power why is this notation used?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1
    Quote Originally Posted by kathrynmath View Post
    If 2^S is not meant to raise 2 to a power why is this notation used?
    If each of A~\&~B is a set the notation B^A is the set of all functions f:A\to B.
    It is common to have 2^A=\{f:A\to \{0,1\}\} which corresponds to all the subsets of A.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  3. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  4. equivalence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 12th 2009, 05:33 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum