1. ## 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

2. ## Re: Sets- Power sets

Originally Posted by cs1632
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\|}$.

3. ## 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}$.