哥德爾證明的兩大關鍵想法#

本章標題改編自哥德爾 1931 年那篇關鍵論文〈論《數學原理》及相關系統中形式不可判定命題〉。哥德爾的論文嚴謹而技術性，這裡則以直覺方式呈現其核心。

哥德爾證明由兩個融合在一起的關鍵想法組成：

1. TNT 字串能夠談論其他 TNT 字串——透過哥德爾編號（Gödel-numbering），TNT 具備「自我審視」的能力
2. 這種自我審視可被凝聚為一條字串——讓該字串只談論自己（出自康托爾對角線方法的精神）

作者認為第一個想法更深——它觸及「符號系統中的指稱與意義」這個遠超出邏輯學的問題。

第一個想法：證明對#

把「字串 X 是 TNT 的定理」翻譯為一個數論陳述，須引入證明對（proof-pair）：

TNT 證明對：兩自然數 m, n 構成證明對，若 m 是某 TNT 推導的哥德爾編號，且該推導最後一行的哥德爾編號是 n。

先以 MIU 系統為範例：

m = 3131131111301
n = 301

對應推導：MI → MII → MIIII → MUI
(m 即此推導的哥德爾編號，n = 301 即 MUI 的編號)

這是合法的 MIU 證明對。但若 m = 31311311130, n = 30，對應推導包含非法步驟（MII → MIII），便不是證明對。

關鍵事實#

基本事實 1：「(m, n) 構成證明對」是個原始遞迴的數論性質——可寫 BlooP 程式判定。

基本事實 2：因此，「證明對」在 TNT 中可被某個含兩個自由變數的公式所表徵。

把這個公式記為 TNT-PROOF-PAIR{a, a'}。

證明對 vs. 定理數#

要注意對照：

證明對：是否原始遞迴？  → 是。可被 TNT 表徵。
定理數：n 是否為定理之 Gödel 數？
       = 「存在 m，使得 (m, n) 是證明對」
       → 涉及無上界搜尋，不是原始遞迴

a' 是定理數可用以下方式表達（不一定可表徵）：

∃a: TNT-PROOF-PAIR{a, a'}

例如「0=0 是 TNT 定理」可寫成（記 0=0 的哥德爾編號為 666,111,666）：

∃a: TNT-PROOF-PAIR{a, SSSS...SSS0/a'}
            ← 666,111,666 個 S

這條句子稱為 JOSHU。

後設層級的無窮疊代#

可進一步寫：

• META-JOSHU：「JOSHU 是 TNT 定理」
• META-META-JOSHU：「META-JOSHU 是 TNT 定理」
• ……

每一層後設陳述都可被翻譯回 TNT。

第二個想法：代換與算術奎寧#

要把「自我審視」凝聚到單一字串，需要看清用具體數值取代公式中自由變數時，哥德爾編號如何變化：

原公式：a = a              編號：262, 111, 262
代入 a := 2 後得 SS0 = SS0  編號：123,123,666, 111, 123,123,666

原公式：∃a:∃a':a"=(SSa·SSa')
編號：223,333,262,636,333,262,163,636,262,163,163,111,362,123,123,262,236,...
代入 a" := 2 後...
代入 a" := 4 後...

「代換關係 SUB(a, a’, a")」——三數 a, a’, a" 是否滿足「a 是原編號、a’ 是代入值、a" 是結果編號」——是原始遞迴的，因此可被 TNT 表徵為一條三自由變數的公式。

算術奎寧（Arithmoquining）#

奎寧（quining）的算術版：把公式自己的哥德爾編號代入自己中。

取公式：a = S0          編號：262, 111, 123, 666
代入 a := 262,111,123,666 得：
   SSS...SS0 = S0      （262,111,123,666 個 S）

新字串斷言「262,111,123,666 = 1」——荒唐的偽。但若改自 ~a=S0，則奎寧後得真陳述。

把「對編號為 a" 的公式進行算術奎寧得到 a’ 」表達為：

ARITHMOQUINE{a", a'}   ← 即 SUB{a", a", a'} 的縮寫

哥德爾字串的構造#

哥德爾的最後一招：算術奎寧一個本身談論算術奎寧的公式——猶如「奎寧一個奎寧自身的句子」。

寫下「G 的叔叔（uncle of G）」：

~∃a:∃a': <TNT-PROOF-PAIR{a, a'} ∧ ARITHMOQUINE{a", a'}>

設此公式的哥德爾編號為 u。

然後算術奎寧這個叔叔——也就是把 a" 處全部換成 u 的 numeral：

G = ~∃a:∃a': <TNT-PROOF-PAIR{a, a'} ∧ ARITHMOQUINE{SSS...SSS0/a", a'}>
                                                   ← u 個 S

G 的詮釋#

逐步解讀 G：

字面：「不存在 a 與 a' 使得 (a, a') 是 TNT 證明對，且 a' 是 u 的算術奎寧。」

第二輪：a' 確實存在（就是 u 的算術奎寧），所以 a 不可能存在：
   「不存在 a 與 (u 的算術奎寧) 構成 TNT 證明對。」

第三輪：u 的算術奎寧，正是 G 自己的哥德爾編號：
   「G 不是 TNT 的定理。」

最後：「我不是 TNT 的定理。」

G 兼具兩種解讀：

• 算術陳述（純數論層面）
• 後設陳述（談論 TNT 自身）

兩種解讀都有效。

TNT 投降了#

若 G 是定理 → G 斷言為真 → G 不是定理（自相矛盾）
若 G 不是定理 → G 斷言為真，但確實不是定理 → 存在真但非定理之陳述

結論：G 是真的但不可被 TNT 證明——TNT 是不完備的。

TNT 是 ω-不完備的#

可以證明對應的金字塔家族中的所有實例都是定理（因為證明對是原始遞迴的），但統括這些實例的全稱句卻不是——這正是 ω-不完備的標誌。

哥德爾第二定理：一致性無法在系統內證明#

哥德爾還證明了更深的結果。考慮「TNT 一致」這個陳述：

TNT 一致 ⟺ 存在某條 TNT 字串不是定理
         ⟺ 「~0=0 不是 TNT 定理」

可表達為：
~∃a: TNT-PROOF-PAIR{a, SSSS...SS0/a'}   ← 223,666,111,666 個 S

哥德爾第二不完備定理：除非 TNT 不一致，否則這條「自證一致性」之語句不能是 TNT 的定理。

換句話說：一致系統無法在自身內部證明自己的一致性。

希爾伯特計畫——希望用更弱的方法（有限主義）證明數學系統的一致性——至此徹底破產。對人類自我認知亦具強烈的隱喻意味。

兩種填補漏洞的方式#

G 不可判定，意味著 TNT 可被以兩種互斥的方向擴充：

• 標準擴充：把 G 當作新公理（直觀上「對」，因 G 確實為真）
• 非標準擴充：把 ~G 當作新公理

第二條路看似荒謬——~G 似乎與我們對自然數的理解相矛盾。但這正類比於把「平行公設的否定」加入絕對幾何，最終得到非歐幾何。

薩凱里（Saccheri）的錯誤是不肯放下對「點、直線」既有的視覺意象。我們不該重蹈覆轍。

超自然數#

新增 ~G 為公理會強迫我們重新詮釋量詞：

∃ 不再讀為「存在自然數」
而讀為「存在廣義自然數」

廣義自然數 = 自然數 + 超自然數（supernatural numbers）。

超自然數可想像為「比所有自然數都大的整數」——無限大整數。它們共享自然數的所有形式性質（凡是 TNT 證得的，對它們皆成立），但不是分數、負數、無理數或複數。

矛盾消失：

• 金字塔家族仍說「沒有自然數 與 u 的算術奎寧構成證明對」
• ~G 說「存在某廣義自然數 與 u 的算術奎寧構成證明對」——這個數是個超自然數

歷史上每次擴充數的概念（有理數、負數、無理數、虛數）都被冠以蔑稱（「無理」、「虛」）。超自然數這個名字也帶有同樣的歷史色彩。

與 i（虛數單位）類似——超自然數 I 「就是與 u 的算術奎寧構成 TNT 證明對的那個數」——它的「大小」無法用普通整數的尺度衡量，正如不能說「i 約是 14 的一半」。

超自然定理需要無限長的推導#

當 ~G 作為公理時，「G 有證明」是其斷言。但只要我們僅構造有限推導，G 與 ~G 永不衝突——超自然證明所對應的推導長度是「無限長」的，超出有限推導的範圍。這正是這個非標準擴充得以維持一致的微妙之處。

哥德爾論證對 Tarski 的延伸（預告）#

哥德爾證明展示了「真理超越定理性」。Tarski 後來在更普遍的意義上證明了：真理本身無法在系統內被定義。這將在第 17 章繼續發展。