康托爾對角線論證

康托爾對角線論證是一個出奇簡單的證明，表明實數無法被列舉，從而是不可數的。它是反證法：假設你確實擁有 (0, 1) 中全部實數的完整清單，每行一個，寫成無窮小數。論證製造出一個實數，按其構造，它與清單上每一項都不同——於是這份清單終究並不完整。

其構造是「對角線」一招。沿對角線讀下來造一個新數 d——它的第 n 位小數被選得與清單上第 n 個數的第 n 位不同（例如把每個對角位都改成 5，若原本已是 5 則改成 6）。於是 d 不可能等於清單的第一個數（它們在第 1 位不同），也不等於第二個（在第 2 位不同），如此下去：d 與第 n 個數在第 n 位不同。故 d 是 (0, 1) 中一個不在清單上的實數，即所求矛盾。

需要一處技術上的當心：小數展開並非完全唯一（0.4999… 等於 0.5000…），故須選取避開 0 與 9 的替換數字以躲開這一歧義。修補之後結論成立：不存在實數的枚舉。同樣的對角線想法施於特徵函數，便證明康托爾的一般定理：沒有集合能滿射到自己的冪集上；它還以哥德爾不完備性與停機問題不可解的核心姿態在邏輯中重現。