ProofOfCantorsTheorem 2002-06-05 23:35:24 2007-08-08 21:41:57 Proof Cantor's theorem 0 diagonal argument % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. \def\equiv{\Leftrightarrow} % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here \def\P{{\mathcal P}} \def\sse{\subseteq} The proof of this theorem is fairly \PMlinkescapetext{simple} using the following construction, which is central to Cantor's diagonal argument. Consider a function $F\colon X\to \P(X)$ from a set $X$ to its power set. Then we define the set $Z\sse 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 \equiv x\not\in F(x) \equiv x\not\in Z\] Hence, $F$ cannot be a bijection between $X$ and $\P(X)$.