# proof of Cantor’s theorem

The proof of this theorem is fairly using the following construction, which is central to Cantor’s diagonal argument.

Consider a function $F\colon X\to{\mathcal{P}}(X)$ from a set $X$ to its power set. Then we define the set $Z\subseteq X$ as follows:

 $Z=\{x\in X\mid x\not\in F(x)\}$

Suppose that $F$ is a bijection. Then there must exist an $x\in X$ such that $F(x)=Z$. Then we have the following contradiction:

 $x\in Z\Leftrightarrow x\not\in F(x)\Leftrightarrow x\not\in Z$

Hence, $F$ cannot be a bijection between $X$ and ${\mathcal{P}}(X)$.

Title proof of Cantor’s theorem ProofOfCantorsTheorem 2013-03-22 12:44:55 2013-03-22 12:44:55 Wkbj79 (1863) Wkbj79 (1863) 7 Wkbj79 (1863) Proof msc 03E17 msc 03E10