對角論證法

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

实数[编辑]

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

  1. 假設(從原題中得出)区间[0,1]中的點數是可數無窮大的
  2. 於是乎我們可以把所有在這区间內的數字排成數列, (r_1, r_2, r_3, ... )
  3. 已知每一個這類的數字都能以小數形式表達
  4. 我們把這些數字排成數列(這些數字不需按序排列; 事實上,有些可數集, 例如有理數也不能按照數字的大小把他們全數排序,但單只是成數列就沒有問題的),在部份有多種表達形式的數字上,例如0.499 ... = 0.500 ..., 我們選擇前者.
  5. 舉例,如果該數列小數形式表現如下:
    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 ...
    ...
  6. 考慮r_k小數點後的第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 ...
    ...
  7. 我們設一實數x \in [0,1], 其中x是因應以下的方式定義的
    • 如果r_k的第k個小數位等於5, 那麼x的第k個小數位是4
    • 如果r_k的第k個小數位不等於5, 那麼x的第k個小數位是5
  8. 明顯地x是一個在区间[0,1]內的實數,以之前的數為例, 則相對應的x應為 0 . 4 5 5 5 5 5 4 ...
  9. 由於我們假設(r_1,r_2,r_3,... )包括了所有區間[0, 1]內的實數,所以一定有一個r_n=x
  10. 但由於x的特殊的定義,這使到x和r_n的第n個小數位是不同的,所以x \notin (r_1,r_2,r_3,... )
  11. 所以(r_1,r_2,r_3,... )並不能羅列所有區間[0, 1]內的實數,這發生了矛盾。
  12. 所以在第一點內所提出的假設"区间[0,1]中的點數是可數無窮大的"是不成立的。

外部連結[编辑]

Original German text of the 1891 proof, with English translation

A variation on Cantor's diagonal proof, completely formalized from first principles