1
$\begingroup$

I'll state the Cantor's theorem proof as is it is in my study texts:

Theorem (Cantor): Let $X$ be any set. Then $|X|<|\mathcal{P}(X)|$

Proof: Define map $\varphi:X\rightarrow\mathcal{P}(X)$ by $\varphi:x\mapsto\{x\}$. $\varphi$ is injective, thus $|X|\leq|\mathcal{P}(X)|$. Now suppose there is a bijection (surjection) $\psi:X\rightarrow\mathcal{P}(X)$. Denote the set $A=\{x\in X, x\notin \psi(x)\}$. By assumption, $\psi$ is surjection so we find some $a\in X$ such that $\psi(a)=A$. Then we have two cases, either $a\in A$, but the, by definition of $A$: $a\notin \psi(a)$ which is a contradiction. So $a\notin A$ but then $a\in \psi(a)=A$ which is a contradiction aswell thus such surjection cannot exist.

So now, for my question. The definition of $A$ seems really weird to me. Because, in the first place. Assume $X=\{1,2\}$ then $\mathcal{P}(X)=\{\{1,2\},\{1\},\{2\},\emptyset\}$. In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $\psi$ but, the range of $\psi$ are sets, aren't they? Thus $A=\{1,2\}$ and the case is $\forall a\in X:a\in{A}$ thus the second case of the proof applies. Basically this leads me to the following idea: instead of constructing this set $A$, we can say that:

Estabilish injection and thus $|X|\leq|\mathcal{P}(X)|$ by $\varphi:x\mapsto\{x\}$ thus $\forall{S}\in\varphi(x):|S|=1$, but for any set $X:$ $\emptyset\subset\mathcal{P}(X)$ but $|\emptyset|=0$ so $\emptyset\notin ran(\varphi)$ thus $\varphi$ is not surjective.

$\endgroup$
2
  • 2
    $\begingroup$ "In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $\psi$" No, that's not what $A$ is supposed to be. If $x\in X$ then $\psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $A\ne\psi(x)$ because the two sets, $A$ and $\psi(x),$ differ at $x$; namely, $$x\in A\iff x\notin\psi(x).$$ $\endgroup$
    – bof
    Jul 26, 2018 at 8:19
  • 1
    $\begingroup$ The definition of $A$ is a kind of diagonalization. $\endgroup$
    – Hanul Jeon
    Jul 26, 2018 at 8:21

3 Answers 3

6
$\begingroup$

In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $\psi$

No, this is not quite true. The construction is more subtle than that. For any $x \in X$, the value $\psi(x) \in \mathcal P(X)$ is some set -- a subset of $X$ to be precise. Note that this is not the range of $\psi$, it is the value of $\psi(x)$ for a single $x$.

Then we have either $x \in \psi(x)$ or $x \notin \psi(x)$, and we add $x$ to the set $A$ if and only if $x \notin \psi(x)$.

$\endgroup$
2
  • $\begingroup$ So $A$ is the set for which the map $\psi$ maps some $x\in X$ to some say $T\in \mathcal{P}(X)$ for which $x\notin T$? $\endgroup$ Jul 26, 2018 at 8:20
  • 2
    $\begingroup$ $A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true. $\endgroup$ Jul 26, 2018 at 8:23
3
$\begingroup$

That the specific mapping $ \varphi$ is not surjective, hence not bijective, is clear.

To prove that $|X|<|\mathcal{P}(X)|$ , it is enough to show that each(!) mapping $\psi:X\rightarrow\mathcal{P}(X)$ cannot be surjective.

In the proof above it is assumed that there is a surjective mapping $\psi:X\rightarrow\mathcal{P}(X)$ . But this leads to a contradiction....

$\endgroup$
3
  • $\begingroup$ So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"? $\endgroup$ Jul 26, 2018 at 8:15
  • 1
    $\begingroup$ @Michal Dvořák Right, you have to prove no mapping from $X$ to $\mathcal{P}(X)$ can be surjective. $\endgroup$
    – Hanul Jeon
    Jul 26, 2018 at 8:19
  • $\begingroup$ Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection). $\endgroup$
    – Asaf Karagila
    Jul 26, 2018 at 8:57
1
$\begingroup$

Mees de Vries' answer gives an explanation of where your misunderstanding of the usual proof was.

To address your alternative proof attempt: you show that there is a particular injection from $X$ to $\mathcal{P}(X)$, but that it's not surjective. This isn't enough to prove that $|X|<|\mathcal{P}(X)|$. For example, we can define a function from $\mathbb N$ to $\mathbb N\times \mathbb N$ by $\varphi(n)=(n,1)$, which is injective but not surjective. However, $|\mathbb N|=|\mathbb N\times \mathbb N|$ because other, more complicated, functions exist which are both injective and surjective (e.g. $\psi(n)=(a,b)$ where $a,b$ are the unique positive integers such that $n=(2a-1)2^{b-1}$).

$\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.