对角论证法

对角论证法乔治·康托尔于1891年提出的用于说明实数集合不可数集的证明。

对角线法并非康托尔关于实数不可数的第一个证明,而是发表在他第一个证明的三年后。他的第一个证明既未用到十进制展开也未用到任何其它数系。自从该技巧第一次使用以来,在很大范围内的证明中都用到了类似的证明构造方法,它们一般亦称为对角论证法。

实数

康托尔的证明表明区间[0, 1]不是可数无穷大。该证明是用反证法完成的,步骤如下:

  1. 假设区间[0, 1]是可数无穷大的,已知此区间中的每个数字都能以小数形式表达。
  2. 我们把区间中所有的数字排成数列(这些数字不需按序排列;事实上,有些可数集,例如有理数也不能按照数字的大小把它们全数排序,但单只是成数列就没有问题的)。对于那些有两种小数形式的数字,例如0.499 ... = 0.500 ...,我们选择前者。
  3. 举例,如果该数列小数形式表现如下:
    r1 = 0 . 5 1 0 5 1 1 0 ...
    r2 = 0 . 4 1 3 2 0 4 3 ...
    r3 = 0 . 8 2 4 5 0 2 6 ...
    r4 = 0 . 2 3 3 0 1 2 6 ...
    r5 = 0 . 4 1 0 7 2 4 6 ...
    r6 = 0 . 9 9 3 7 8 3 8 ...
    r7 = 0 . 0 1 0 5 1 3 5 ...
    ...
  4. 考虑 小数点后的第k个位,我们给这些数字加上底线与粗体。从这里可以看出“对角论证法”名称的由来。
    r1 = 0 . 5 1 0 5 1 1 0 ...
    r2 = 0 . 4 1 3 2 0 4 3 ...
    r3 = 0 . 8 2 4 5 0 2 6 ...
    r4 = 0 . 2 3 3 0 1 2 6 ...
    r5 = 0 . 4 1 0 7 2 4 6 ...
    r6 = 0 . 9 9 3 7 8 3 8 ...
    r7 = 0 . 0 1 0 5 1 3 5 ...
    ...
  5. 我们设一实数 ,其中 的第k个小数位为 的第 个小数位加2之后的个位数值。
  6. 明显地 是一个在区间[0, 1]内的实数,以之前的数列为例,则相对应的 应为 0 . 7 3 6 2 4 5 7 ...。
  7. 由于 的特殊定义,  会在第 个小数位不同。这使得序列 之中所有的实数俱不能与 完全相等,即 不在序列 中。
  8. 但我们假设 包括了所有区间[0, 1]内的实数,即应该要存在一个 。这发生了矛盾。
  9. 所以在第一点内所提出的假设“区间[0, 1]是可数无穷大的”不成立,证毕。

外部链接