Talk:Cardinality of Power Set

Would not an easier proof/another proof be along the lines of:

To choose the elements from $S$ to be in a subset, we can either include or not include each element, that is for each element in $S$ we have two possibilities, so the total number of combinations of elements from $S$ (which is the same as $\vert\mathcal{P}(S)\vert$) is $2\times 2 \times \ldots \times 2 = 2^{\vert S \vert}$.

If you think so, post it up. It would probably be filed under "informal and handwavey", mainly because the gap between "for each element in $S$ we have two possibilities" and "the total number of combinations of elements from $S$ (which is the same as $\vert\mathcal{P}(S)\vert$) is $2\times 2 \times \ldots \times 2 = 2^{\vert S \vert}$" is not filled. --prime mover 15:51, 23 March 2011 (CDT)

I added a version of the informal proof, feel free to tweak it. I also made a couple edits to the second proof to make it a bit clearer. As it was, the reference to Sum of Binomial Coefficients for Given n seemed confusing (and actually circular if you look at the second proof for that result).

On a separate note, I'm pretty sure I've read that this result holds for infinite sets, but I'm not sure these proofs would be valid in that case (without a background in transfinite stuff I'm more than a bit hazy on what $2^{\vert \N \vert}$ would even mean...). Is there anything particular we should say to handle the infinite cases (or just qualify the theorem to only be for finite sets)? --Alec (talk) 00:34, 24 March 2011 (CDT)

It does hold for infinite sets which is where you get $\aleph_{n_1} = 2^{\aleph_n}$ from. But as you say, there's a lot of work on transfinites to get under our collective belts. I ought to start work on it but I'm still mucking about with the nuts and bolts.--prime mover 01:24, 24 March 2011 (CDT)