對角論證法

對角論證法是喬治·康托爾於1891年提出的用於說明實數集合是不可數集的證明。

對角線法並非康托爾關於實數不可數的第一個證明，而是發表在他第一個證明的三年後。他的第一個證明既未用到十進制展開也未用到任何其它數系。自從該技巧第一次使用以來，在很大範圍內的證明中都用到了類似的證明構造方法，它們一般亦稱為對角論證法。

實數

康托爾的證明表明區間[0, 1]不是可數無窮大。該證明是用反證法完成的，步驟如下：

1. 假設區間[0, 1]是可數無窮大的，已知此區間中的每個數字都能以小數形式表達。
2. 我們把區間中所有的數字排成數列（這些數字不需按序排列；事實上，有些可數集，例如有理數也不能按照數字的大小把它們全數排序，但單只是成數列就沒有問題的）。對於那些有兩種小數形式的數字，例如0.499 ... = 0.500 ...，我們選擇前者。
3. 舉例，如果該數列小數形式表現如下：

   r₁ = 0 . 5 1 0 5 1 1 0 ...

   r₂ = 0 . 4 1 3 2 0 4 3 ...

   r₃ = 0 . 8 2 4 5 0 2 6 ...

   r₄ = 0 . 2 3 3 0 1 2 6 ...

   r₅ = 0 . 4 1 0 7 2 4 6 ...

   r₆ = 0 . 9 9 3 7 8 3 8 ...

   r₇ = 0 . 0 1 0 5 1 3 5 ...

   ...

4. 考慮$r_{k}$小數點後的第k個位，我們給這些數字加上底線與粗體。從這裏可以看出「對角論證法」名稱的由來。

   r₁ = 0 . 5 1 0 5 1 1 0 ...

   r₂ = 0 . 4 1 3 2 0 4 3 ...

   r₃ = 0 . 8 2 4 5 0 2 6 ...

   r₄ = 0 . 2 3 3 0 1 2 6 ...

   r₅ = 0 . 4 1 0 7 2 4 6 ...

   r₆ = 0 . 9 9 3 7 8 3 8 ...

   r₇ = 0 . 0 1 0 5 1 3 5 ...

   ...

5. 我們設一實數$x\in [0,1]$，其中$x$的第k個小數位為$r_{k}$的第$k$個小數位加2之後的個位數值。(例如說，r1的第1個小數位加2便是7）
6. 明顯地$x$是一個在區間[0, 1]內的實數，以之前的數列為例，則相對應的$x$應為 0 . 7 3 6 2 4 5 7 ...。
7. 由於$x$的特殊定義，$x$和$r_{n}$會在第$n$個小數位不同。這使得序列$(r_{1},r_{2},r_{3},...)$之中所有的實數俱不能與$x$完全相等，即$x$不在序列$(r_{1},r_{2},r_{3},...)$中。
8. 但我們假設$(r_{1},r_{2},r_{3},\ldots )$包括了所有區間[0, 1]內的實數，即應該要存在一個$r_{n}=x$。這發生了矛盾。
9. 所以在第一點內所提出的假設「區間[0, 1]是可數無窮大的」不成立，證畢。

外部連結

• Original German text of the 1891 proof, with English translation
• A variation on Cantor's diagonal proof, completely formalized from first principles （頁面存檔備份，存於互聯網檔案館）