2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ With your arguments you would get that $\mathbb Q$ has a strictly larger cardinality as $\mathbb N$ as the natural numbers are strictly contained in the rationals. But as is well-known they have the same cardinality! $\endgroup$ – StefanH Dec 14 '15 at 12:38
  • 2
    $\begingroup$ This works for finite sets, but not infinite ones. For example the set $\{1,2,3,\dots\}$ is in bijection with the set $\{0,1,2,3,\dots\}$ (the bijection being $n\to n-1$) despite the latter having nominally one more element than the former. $\endgroup$ – lulu Dec 14 '15 at 12:39
  • 2
    $\begingroup$ You have noticed that there is an bijective function from $X$ to a proper subset of $P(X)$. So what? Note that there is an bijective function from $\mathbb R$ (the real line) to a proper subset of $\mathbb R$, namely the function $e^x$. Can you conclude from that that the real line has greater cardinality than itself? $\endgroup$ – bof Dec 14 '15 at 12:41
  • 1
    $\begingroup$ Maybe this famous characterisation of the infinite is of interest here: en.wikipedia.org/wiki/Dedekind-infinite_set Then your argument would imply that all infinite sets have the same cardinality, which certainly is not the case as it is also well known that $\mathbb R$ and $\mathbb Q$ have different cardinalities. Or that it is not well-defined to speak about cardinalities for infinite sets as your argument would show that every set has a higher cardinality as itself, a contradiction. $\endgroup$ – StefanH Dec 14 '15 at 12:44
3
$\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.

|cite|improve this answer
$\endgroup$
1
$\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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So is the introductory step in the proof incorrect then? In case you have it handy to look up the entire proof the book I am referencing is Zorich's Mathematical Analysis 1, pg 26, where it says "Since P(X) contains all one-element subsets of X, cardX $\ge$ cardP(X). Or is this argument allowed, but attempting to make the argument stronger, as I did above, is not allowed? $\endgroup$ – Guest Dec 14 '15 at 12:45
  • $\begingroup$ The introductory step is correct, as by giving an injection $f : A \to B$ between two sets $A$ and $B$ would give that $|A| \le |B|$ (i.e. $A$ is isomorphic to a subset of $B$). $\endgroup$ – StefanH Dec 14 '15 at 12:48
  • $\begingroup$ So have they essentially said that there exists an injective function f:A→B that is something along the lines of f(x)={x}, and so |A|≤|B|? $\endgroup$ – Guest Dec 14 '15 at 12:53
  • $\begingroup$ That's right. And to prove that $|A| = |B|$, they'd have to give an injective function in the other direction, so to show that $|A| \ne |B|$, they have to show that there's \emph{no} injective function in the other direction...which is where the diagonal argument (in some form) comes in. $\endgroup$ – John Hughes Dec 14 '15 at 12:56
  • $\begingroup$ Ah ok, now that first statement makes much more sense now, thank you! $\endgroup$ – Guest Dec 14 '15 at 12:57
0
$\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]

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.