Can someone please help me prove this:
Show that |P(X)| = 2 ^ (|X|) for all finite sets X
Any help would be greatly appreciated!! Thank you!
Let $\displaystyle f(n)$ denote the number of subsets of $\displaystyle \left\{1\cdots,n\right\}$. Consider the power set of $\displaystyle \left\{1,\cdots,n,n+1\right\}$. Partition set into two blocks $\displaystyle B_1=\left\{A\in\wp\left(\left\{1,\cdots,n+1\right\ }\right):n+1\in A\right\}$ and $\displaystyle \wp\left(\left\{1,\cdots,n+1\right\}\right)-B_1=B_2$. Clearly, we have that $\displaystyle \left|B_2\right|=f(n)$. And, with the exception of $\displaystyle \{n+1\}$ we may (and can) only put $\displaystyle \{n+1\}$ into each of the subsets of in $\displaystyle B_1$. Thus, we have that $\displaystyle f\left(n+1\right)=f(n)+f(n)+1$...almost...we double counted one thing (what is it??). So $\displaystyle f(n+1)=f(n)+f(n)+1-1=2f(n)$. Thus, it follows by induction that the recurrence relation $\displaystyle f(n+1)=2f(n)$ has solution $\displaystyle f(n)=C\cdot 2^n$ for some $\displaystyle C$. Noting though that $\displaystyle f(0)$ is the number of subsets of the empty set we may conclude that $\displaystyle f(0)=1=C\cdot 2^0=C$. The conclusion follows.
EDIT: I am sorry tonio. I didn't see your post!
Why so complicated? Just notice that if you want to construct a subset $\displaystyle S$ of $\displaystyle X$, you have two possibilities for every element of $\displaystyle X$: either you include it, or you exclude it. So in total you have $\displaystyle 2^{|X|}$ possibilities.
Another proof : clearly the number of subsets of $\displaystyle X$ is
$\displaystyle {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n$
The "another proof" is not so unless you first prove that there are $\displaystyle \binom{n}{k}$ subsets with k elements out of a set with n elements, $\displaystyle k\le n$, and also you forgot the number $\displaystyle \binom{n}{0}$ in the sum and also, and perhaps most important, this another proof relies on "hidden induction": after all, we need to show that's true for all n, just like the formal proof of Newton's binomial theorem is usually, and as far as I am aware uniquely, done by induction.
Tonio