# Power Set

1. Aug 9, 2007

### FunkyDwarf

1. The problem statement, all variables and given/known data
Hey

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?

Thanks
-Z

2. Aug 9, 2007

### matt grime

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

$$2^n= \binom{n}{0} + \binom{n}{1}+\ldots \binom{n}{n}$$

but this is trivial - remember 2=1+1.

3. Aug 10, 2007

### HallsofIvy

Staff Emeritus
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}.

4. Aug 11, 2007

### FunkyDwarf

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.

5. Aug 11, 2007

### MathematicalPhysicist

you need to remember this, crap...

6. Aug 11, 2007

### matt grime

Remembering that 1=x/x for any non zero x, and that 0=x-x are also incredibly useful.