Proving Power Set of S is Equal to 2^n

[FunkyDwarf]

Homework Statement

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 couldn't find any.

Homework Equations

Binomial theorem

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 I am having a hard time relating a sumation over some crazy factorial stuff to something as simple as 2^n. Any ideas?

Thanks
-Z

 

[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.

 

[HallsofIvy]

I would do that by induction. A set with only one member, say {a} has two subsets, {a} and {}: 2¹= 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}.

 

[FunkyDwarf]

Both super ideas, alas i read this after handing it in :) i went with a kinda wishy washy approach (its only 2nd year I am 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.

 

[MathematicalPhysicist]

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.

you need to remember this, crap...

 

[matt grime]

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