康托尔对角化论证

对角论证法是乔治 · 康托尔于 1891 年提出的用于说明实数集合是不可数集的证明。
要证明实数集合是不可数的,就假定实数集合是可数的并得出矛盾。于是,所有落在 $0$ 和 $1$ 之间的实数所成的子集合也是可数的 (因为可数集合的所有子集合都是可数的)。在此假设下,在 $0$ 和 $1$ 之间的实数按照某种顺序列出,比如说 $r_1,r_2,r_3,\dots$ 设这些实数的十进制表示为
$$
r_1 =0.d_{11}d_{12}d_{13}d_{14}\dots \\
r_2 =0.d_{21}d_{22}d_{23}d_{24}\dots \\
r_3 =0.d_{31}d_{32}d_{33}d_{34}\dots \\
r_4 =0.d_{41}d_{42}d_{43}d_{44}\dots \\
.\\
.\\
.\\
$$
其中 $d_{ij}\in {0,1,2,3,4,5,6,7,8,9}$。(例如,如果 $r_1=0.23794101\dots$,就有 $d_{11}=2,d_{12}=3,d_{14}=7\dots$)于是,构造新的实数具有十进制展开式 $r=0.d_1d_2d_3d_4\dots$,其中用下列规则确定十进制数字:
$$
f(n) =
\begin{cases}
4, & \text{if $d_i\neq$ 4} \[2ex]
5, & \text{if $d_i$= 4}
\end{cases}
$$
例如,假定 $r_1=0.23794102\dots, r_2=0.44590138\dots,r_3=0.09118764\dots$ 等等,于是 $r=0.d_1d_2d_3d_4\dots =0.4544\dots$, 其中因为 $d_{11}\neq 4,d_1=4,d_{22}=4,d_2=5 \dots$)
每个实数都有唯一的十进制展开式 (展开式结尾全部由数字 $9$ 组成的可能性除外)。于是,实数 $r$ 不等于 $r_1,r_2,\dots $ 中的任何一个,因为对每个 $i$ 来说,$r$ 的十进制展开式与 $r_i$ 的十进制展开式在小数点右边第 $i$ 位是不同的。
由于存在着不在列表中而在 $0$ 和 $1$ 之间的实数 $r$,所以可以列出在 $0$ 和 $1$ 之间所有实数的假设必定为假。因此,不能列出在 $0$ 和 $1$ 之间的所有实数,在 $0$ 和 $1$ 之间的实数集合是不可数的。任何包含不可数子集合的集合都是不可数的。因此实数集合是不可数的。