カントールの定理:実数は非可算である

背理法で示す。$[0,1]$ が可算であると仮定する:その中のすべての実数がある列挙 $x_1, x_2, x_3, \ldots$ にちょうど一度ずつ現れるとする。各数を10進展開 $x_n = 0.d_{n1}d_{n2}d_{n3}\ldots$ として書き、ある数が2通りの表現を持つ場合は無限に9が続かない方の展開を選ぶ。

次に、この列の対角線をたどることで、新しい数 $y$ を1桁ずつ構成する:$y = 0.e_1e_2e_3\ldots$、ここで $n$ 桁目は $e_n=\begin{cases}5 & d_{nn}\neq5\\6 & d_{nn}=5\end{cases}$ で定める。選択肢を $\{5,6\}$ に限定することで、$y$ が無限に0や9が続く展開になることはなく、その10進展開は一意で曖昧さがない。

すべての添字 $n$ について、構成法により $y$ は $n$ 桁目で $x_n$ と異なる($e_n\neq d_{nn}$)ので、$y\neq x_n\ \forall n$。$y$ の各桁はすべて $5$ か $6$ なので、$y\in[0,1]$ である。

しかしそうすると、$y$ は $[0,1]$ に属する実数でありながら、完全なはずのリスト中のどの $x_n$ とも等しくない——これは、そのリストが $[0,1]$ のすべての要素を含むと仮定したことに矛盾する。したがって $[0,1]$ の列挙は存在し得ず、$[0,1]$(したがってより大きな集合 $\mathbb{R}$)は非可算である。