0
$\begingroup$

As I understand, Cantor’s diagonal set can be empty, that is, there could be a mapping from the the Natural Numbers to the Power Set of the Natural Numbers in which the empty set is not mapped. The function is still not a bijection but there is only one element not mapped (one set that is there only because it is vacuously true). So, does Cantor theorem depend on the empty set being part of the Power set? And how could there be a cardinality in between if in this mapping only one element is not mapped?

$\endgroup$
6
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Feb 28 at 10:24
  • $\begingroup$ It seems you are misunderstanding the proof. The diagonal argument shows that for any injection from $\mathbb{N}$ to $P(\mathbb{N})$ a set can be found that is not in its image, so no injection is a surjection, i.e. there are no bijections. For any injection there are in fact (uncountably) infinitely many sets not in the image, not just one, but one suffices for the proof. If you fixed the injection by adding the missing set, you'd get a new injection missing some other set - repeat ad infinitum. $\endgroup$ Feb 28 at 11:03
  • $\begingroup$ “A set can be found” which in some cases could only be the empty set. Where are the “infinitely many sets” if every natural number belongs to its mapped set? Is the theorem solely relying on the inclusion of the empty set on the Power Set? How could there be cardinalities in between if the proof relies on one extra set? I am aware that if I add an extra digit, say zero, the Power Set would be larger, but I can create a mapping in which only the empty set is not mapped. Therefore my question. $\endgroup$ Feb 28 at 11:10
  • $\begingroup$ Cantor gave several proofs of the uncountability of the reals, I suggest reading several of them and then revisiting the diagonalization argument (which I find the most opaque): en.wikipedia.org/wiki/Cantor%27s_first_set_theory_article $\endgroup$ Feb 28 at 11:26
  • $\begingroup$ The diagonal argument only proves that there is no bijection from a set to its power set. It shows that any map misses at least one element of the power set; of course an element of the power set is a subset of the original set. So, the power set must have a larger cardinality. It says nothing about how much bigger it is. It is tempting to imagine that only one subset is missing but it does not say that. It says "at least one is missing". It does not answer the question of whether there is a cardinality in between. It is not obvious to me why are concerned about the empty set. $\endgroup$
    – badjohn
    Feb 28 at 13:41

1 Answer 1

4
$\begingroup$

I believe the discussion is transparent if we work with the set-theoretical version of Cantor's theorem. The theorem says that given any function $f:X\to P(X)$, the set $H(f,X)=\{x\in X\,:\, x\notin f(x)\}$ is not in $\operatorname{im}(f)$. Therefore, a proof that there is no surjection $X\to P(X)$ would be like this:

  1. consider a function $f:X\to P(X)$;
  2. by Cantor's theorem $\forall y\in X,[f(y)\ne H(f,X)]$;
  3. since $H(f,X)\in P(X)$, $f$ is not surjective.

Now, the same argument doesn't work if we substitute $P(X)$ with $P(X)\setminus\{\emptyset\}$, because the claim $H(f,X)\in P(X)\setminus\{\emptyset\}$ in (3) may fail. In fact, $f(x)=\{x\}$ is an easy example of a function $f:X\to P(X)$ such that $H(f,X)=\emptyset$ and, moreover, there are bijections $X\to P(X)\setminus\{\emptyset\}$ if $\lvert X\rvert\le1$.

For the special case where $X=\Bbb N$ (or more generally $X$ Dedekind-infinite) a proof that there isn't a surjection $X\to P(X)\setminus\{\emptyset\}$ could be like this:

  • consider an appropriate pair $(g,x)$ such that $x\in X$ and $g:X\to X\setminus\{x\}$ is a bijection (for $X=\Bbb N$ that could be $x=0$ and $g(t)=t+1$);
  • consider a hypothetical surjection $f:X\to P(X)\setminus \{\emptyset\}$;
  • the function $h(t)=\begin{cases}\emptyset &\text{if }t=x\\ f(g^{-1}(t))&\text{if }t\ne x\end{cases}$ is a surjection $X\to P(X)$;
  • this in contrast with Cantor's theorem.

The second question about the "cardinality in-between" seems nonsense to me.

$\endgroup$
1
  • $\begingroup$ Thank you, sir. $\endgroup$ Feb 28 at 15:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .