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!
EDIT: I am sorry tonio. I didn't see your post!
Why so complicated? Just notice that if you want to construct a subset of , you have two possibilities for every element of : either you include it, or you exclude it. So in total you have possibilities.
Another proof : clearly the number of subsets of is
The "another proof" is not so unless you first prove that there are subsets with k elements out of a set with n elements, , and also you forgot the number 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.