Results 1 to 3 of 3
Like Tree2Thanks
  • 2 Post By Plato

Thread: Sets- Power sets

  1. #1
    Newbie
    Joined
    Oct 2016
    From
    Manchester
    Posts
    13

    Sets- Power sets

    How many elements does the power set of [n] = {1, 2, . . . , n} have? Justify your answer with afew lines of English.

    I understand that power sets are sets of all subsets including the empty set, but I'm not sure how to work out the amount for n elements.
    Thanks in advance for any help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,738
    Thanks
    2459
    Awards
    1

    Re: Sets- Power sets

    Quote Originally Posted by cs1632 View Post
    How many elements does the power set of [n] = {1, 2, . . . , n} have? Justify your answer with afew lines of English.
    If $\|A\|$ denotes the number of elements in a set $A$, then its power-set has $\|\mathscr{P}(A)\|=2^{\|A\|}$.
    Thanks from cs1632 and topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    18,760
    Thanks
    2676

    Re: Sets- Power sets

    We can prove that theorem, that if set A has n elements then the power set has 2^n subsets, "by induction".
    If n= 0, we have the empty set which has only itself as a subset. There are 2^0= 1 subset.

    Now assume that we have proved that this for n= k and A has n+ 1 elements. For any x\in A, A\{x} has n elements so has 2^n subsets. A has two kinds of subsets- those that contain x and those that don't. There are 2^n subsets that do not contain x and every set that does contain x is the union of a set those does not contain x and {x} so there is a one to one relation between the two kinds of sets- they have the same cardinality, 2^n. There for A has 2^n+ 2^n= 2(2^n)= 2^{n+1}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Power Sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 25th 2013, 01:02 PM
  2. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 8th 2011, 05:26 PM
  3. Power Sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 9th 2009, 02:27 AM
  4. Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 22nd 2008, 08:43 AM
  5. Power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 22nd 2007, 07:21 PM

Search Tags


/mathhelpforum @mathhelpforum