Talk:Cardinality of Power Set of Finite Set

From ProofWiki
Jump to navigation Jump to search

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 over Lower Index 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)
This is distinct from proving that $\forall$A, |P(A)| $\geq$ |A|, correct? This doesn't show that $2^{\aleph_n} \geq \aleph_n$. Is that proof also on the site? This was the only article I found about the "Cardinality of a Power Set." Should I be looking elsewhere?--aleph_one 03:16, 21 November 2013 (CDT)
Cantor's Theorem. — Lord_Farin (talk) 23:26, 21 November 2013 (UTC)


Why is this about cardinals? I would suggest that the "Cardinals" category be reserved for the technical details which demonstrate the behaviour of cardinals (i.e. that finite ones are isomorphic to numbers and ordinals, infinite ones have all sorts of non-intuitive behaviour). But when discussing simple results in combinatorics I would suggest not.

This result is not about cardinals, it's about the number of subsets of a finite set. --prime mover (talk) 08:14, 8 September 2012 (UTC)