I have just been learning about Cantor's Theorem, which has been stated in by book as "the carndinality of every set is strictly less than the cardinality of it's power set", and I have a question about the theorem.
In the proof I have been given for Cantor's Theorem, the argument is put forward that the power set contains a singleton set corresponding to each element of the original set, and hence cardX $\le$ cardP(X). They then must just prove that X$\ne$P(X), that is that there exists no surjective function from X to P(X), and hence there can exist no bijective function between them, so the theorem must be true.
Is this introductory step correctly stated? If it is, then I don't understand why Cantor's Theorem doesn't trivially hold true. Using the same reasoning, could it not be said that if the power set contains a singleton set corresponding to each element in the original set, but it also contains the empty set, then surely the power set must have strictly greater cardinality than the original set?
Does this reasoning perhaps not apply when dealing with infinite sets? If not, please try and provide some intuitive reason why the argument I have supplied above fails.
$\endgroup$ 43 Answers
$\begingroup$Two sets have the same cardinality if there exists a bijection between them. And we can say a set $B$ has a higher cardinality then $B$ if there exists an injection from $A$ to $B$ (or equivalently a surjection of some subset of $B$ to $A$).
Your argument is a naive extrapolation from the finite case, this was discussed early on in mathematics, see for example Hilbert's Hotel and also the definition of Dedekind-infinite in one of my comments. Also see the examples given by the others. I would also suggest to read carefully the two famous diagonal proofs of Cantor that $\mathbb N$ and $\mathbb Q$ have the same cardinality and $\mathbb R$ has a strictly larger cardinality than $\mathbb N$.
For completeness I add a proof that there could be no bijection between $X$ and its power set $\mathcal P(X)$. For suppose we have such a bijection $f : X \to \mathcal P(X)$, then define $M := \{ x \in X : x \notin f(x) \}$ (which is well-defined by injectivity). As $M \in \mathcal P(X)$ there exists some $z \in X$ with $f(z) = M$ as it is surjective. If $z \in M$, then this would imply $z \notin M$ by definition, otherwise if $z \notin M$ we would have $z \in M$ by definition, in both cases we got a contradiction showing that we could not have such a bijection.
Compare this scheme with the diagonal argument for the real number from here, they are closely related.
$\endgroup$ $\begingroup$Let me make Stefan's remark even more concrete: your argument would show that the natural numbers are strictly contained in the naturals, because you can send 0 to 1, 1 to 2, 2 to 3, 3 to 4, and so on, and you have nothing sent to 0. So the second set has "room" for one more item.
It's exactly the infinitude that makes this work, and it's why dealing with cardinalities of infinite sets requires a bit more careful formalization than do those of finite sets.
$\endgroup$ 5 $\begingroup$Your counter-argument is 'since the map from elements to corresponding singletons omits the empty-set, the power-set is strictly larger'. I.e you are observing that one specific map isn't a bijection. That fails to consider the possibility that some other map could be a bijection. With infinite sets, that is a distinct possibility (side note: it is worth your time to try proving that it ISN'T a possibility for finite sets [hint: induction]]). In order to establish a size difference, you need to show that every possible map cannot be a bijection (which is what the standard proof shows).
[note: the elements-to-singletons map is cited only to show that a set and its power-set can in fact be compared in size, and that the latter is at least as large as the former]
$\endgroup$
