# Explanation of and alternative proof for Cantor's Theorem

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.

• "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).$$
– bof
Jul 26, 2018 at 8:19
• The definition of $A$ is a kind of diagonalization. Jul 26, 2018 at 8:21

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

• 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$? Jul 26, 2018 at 8:20
• $A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true. Jul 26, 2018 at 8:23

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

• So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"? Jul 26, 2018 at 8:15
• @Michal Dvořák Right, you have to prove no mapping from $X$ to $\mathcal{P}(X)$ can be surjective. Jul 26, 2018 at 8:19
• 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). Jul 26, 2018 at 8:57

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}$).