1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Power Set

  1. Aug 9, 2007 #1
    1. The problem statement, all variables and given/known data

    I need to show that the power set of S is equal to 2^n where n is the number of elements (inlcuding the empty set and S). I found this kinda hard as this is just what it is defined as and not much room to work with, well i couldnt find any.

    2. Relevant equations
    Binomial theorem

    3. The attempt at a solution
    I worked out that you can take a sum of 'choose' functions with k from 1 to n and that should give you the number of sets, but im having a hard time relating a sumation over some crazy factorial stuff to something as simple as 2^n. Any ideas?

  2. jcsd
  3. Aug 9, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Firstly, get the question straight: you want to show that if S is a finite set and |S|=n, then |P(S)|=2^n (hopefully with the obvious notation: P(S) is the power set and |X| means the number of elements in X).

    I believe you're attempting to show that if we add the number of ways to choose 0 elemnts, 1 element and so on that you wish to show

    [tex]2^n= \binom{n}{0} + \binom{n}{1}+\ldots \binom{n}{n}[/tex]

    but this is trivial - remember 2=1+1.
  4. Aug 10, 2007 #3


    User Avatar
    Science Advisor

    I would do that by induction. A set with only one member, say {a} has two subsets, {a} and {}: 21= 2.

    To go from n to n+1, choose a specific member of the set of n+1 elements, call it x, and remove it from the set. Now you have a set of n elements. How many subsets does it have?

    Every subset of the original set either does not contain x (so how many of those are there?) or it does contain x in which case it is a set that does not contain x (how many of those are there) union {x}.
  5. Aug 11, 2007 #4
    Both super ideas, alas i read this after handing it in :) i went with a kinda wishy washy approach (its only 2nd year im allowed to) and said that the pattern that emerges in the number of sets equals the rows in pascals triangle for the choose function, and by the rules governing said triangle the answer is 2^n.
  6. Aug 11, 2007 #5


    User Avatar
    Gold Member

    you need to remember this, crap...
  7. Aug 11, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Remembering that 1=x/x for any non zero x, and that 0=x-x are also incredibly useful.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook