6.1 GODEL不完備定理1931#

本章導言#

1931 年，Gödel 發表〈論《數學原理》及相關系統中不可判定命題〉，證明兩個定理，合稱不完備定理：任何包含初等算術、語法一致的一階理論 \(T\) ，都有它不能證明也不能反駁的真語句（第一定理）；且 \(T\) 的自身一致性不能在 \(T\) 內證明（第二定理）。這是數學基礎研究的分水嶺：Hilbert 綱領原版死亡，對角線法完成它從集合論到算術的遷徙，而「真與可證的分離」成為二十世紀思想史的公共財產。本節精確陳述並證明兩定理的思想骨架。

第一不完備定理：真與可證的分離#

第一不完備定理：設 \(T\) 是包含 Robinson 算術 \(Q\) （足以表達 \(+, \times\) 與遞迴關係）、遞迴可公理化、且語法一致（或更弱： \(\omega\) -一致 / 1-一致）的一階理論。則存在語句 \(G_T\) 使

\[ T \not\vdash G_T \quad \text{且} \quad T \not\vdash \neg G_T, \]

且在標準模型 \(\mathbb{N}\) 中 \(G_T\) 為真。

\(G_T\) 的直觀內容是「** \(G_T\) 在 \(T\) 中不可證**」：

\[ G_T \iff \neg \operatorname{Prov}_T(\ulcorner G_T \urcorner). \]

證明骨架：

編碼（6.2 節）：把語法（公式、證明）編碼為自然數，使「 \(p\) 是語句 \(\phi\) 的 \(T\) -證明」成為算術上可表達的遞迴關係 \(\operatorname{Proof}_T(p, y)\) 。
可證謂詞： \(\operatorname{Prov}_T(y) \equiv \exists p\, \operatorname{Proof}_T(p, y)\) （「 \(y\) 可證」）。
對角線引理（6.2 節）：對任意公式 \(\phi(x)\) ，存在語句 \(\theta\) 使 \(T \vdash \theta \iff \phi(\ulcorner \theta \urcorner)\) 。取 \(\phi(x) = \neg\operatorname{Prov}_T(x)\) ，得 \(G_T\) 。
推理：若 \(T \vdash G_T\) ，則有證明 \(p_0\) ，故 \(\mathbb{N} \models \operatorname{Prov}_T(\ulcorner G_T\urcorner)\) ，但 \(G_T\) 的內容是 \(\neg\operatorname{Prov}_T(\ulcorner G_T\urcorner)\) —— \(T\) 證出了假的東西，違反一致性（更精細的分析只需 \(\omega\) -一致性）。若 \(T \vdash \neg G_T\) ，則 \(T \vdash \operatorname{Prov}_T(\ulcorner G_T\urcorner)\) 而（由一致性） \(T \not\vdash G_T\) ， \(T\) 證「可證」卻證不出——違反 \(\omega\) -一致性。

對角線引理的源頭正是 Cantor 對角線（2.1 節）與羅素悖論（3.1 節）：「在第 \(n\) 個處對付第 \(n\) 個」的取反構造。Gödel 的天才在於把取反對象從「集合的成員關係」換成「可證性謂詞」，把矛盾降級為不可判定。

第二不完備定理：一致性不能自證#

第二不完備定理：在上述條件下（一致性加強為算術一致性 \(\operatorname{Con}(T) \equiv \neg\operatorname{Prov}_T(\ulcorner 0 = 1 \urcorner)\) 可表達），

\[ T \not\vdash \operatorname{Con}(T). \]

證明思想： \(G_T\) 等價於 \(\operatorname{Con}(T)\) 的某種形式（更精確： \(T \vdash \operatorname{Con}(T) \to G_T\) ，Gödel 1931 的第 V 個正式觀察，Hilbert–Bernays 1939 完成細節）。若 \(T \vdash \operatorname{Con}(T)\) ，則 \(T \vdash G_T\) ，違反第一定理。

對 Hilbert 綱領的判決：綱領要求「以有限方法（形式化後 ≈ PRA）證明 PA 一致」。若 \(\operatorname{Con}(\mathrm{PA})\) 可在 PRA 中證明，則因 PRA \(\subseteq\) PA 且 PA 證明 \(\operatorname{Con}(\mathrm{PRA}) \to \operatorname{Con}(\mathrm{PA})\) 型的模擬，得 PA \(\vdash \operatorname{Con}(\mathrm{PA})\) ——違反第二定理。原版綱領不可能。

一個具體例子#

例題 6.1.1（Goodstein 定理：PA 不可證的真定理）：Goodstein 數列從 \(n\) 出發：把 \(n\) 寫成以 \(2\) 為底的 Hereditary 記法（如 \(19 = 2^{2^2} + 2 + 1\) ），把底換成 \(3\) ，減一；再把底換成 \(4\) ，減一……Kirby–Paris 1982 證明 PA 不能證明「每個 Goodstein 數列終於零」，但該命題在 ZFC 中真（以 \(\varepsilon_0\) 歸納證明）。以 \(n = 4\) 為例演示數列前幾項。

解： \(n_0 = 4 = 2^2\) 。換底： \(3^3 = 27\) ，減一： \(n_1 = 26 = 3^3 - 1 = 3^2 \cdot 2 + 3 \cdot 2 + 2\) 。換底： \(4^2 \cdot 2 + 4 \cdot 2 + 2\) ，減一： \(n_2 = 4^2 \cdot 2 + 4 \cdot 2 + 1 = 41\) 。換底減一： \(n_3 = 5^2 \cdot 2 + 5 \cdot 2 = 60\) ， \(n_4 = 6^2 \cdot 2 + 6 + 5 = 83\) ……數值看似增長，但 Kirby–Paris 證明：把每項對映到基 \(\omega\) 的 Cantor 範式（把底 \(k\) 換成 \(\omega\) ），每次操作使該序數嚴格遞減：

\[ \omega^\omega \mapsto \omega^2 \cdot 2 + \omega \cdot 2 + 1 \mapsto \cdots \]

序數的良基性（4.3 節）保證必達 \(0\) ——但這個證明用了 \(\varepsilon_0\) 歸納，超出 PA。Goodstein 定理因此是「獨立於 PA 但真」的具體自然例子（6.2 節的對角線語句 \(G_T\) 是抽象例子，Goodstein 是「日常數學」例子）。 \(\blacksquare\)

教訓：不完備性不是邏輯學的收藏品，它滲入初等數論——「每個 Goodstein 數列停止」是一個學生可寫出前一百項的具體命題，PA 卻證不了它。

第一定理的強化與邊界#

Gödel 原版用 \(\omega\) -一致性；Rosser 1936 以巧妙的「取第一個證明」技巧把條件降到單純一致性（Rosser 語句 \(R\) ：「對每個 \(R\) 的證明，存在更短的 \(\neg R\) 的證明」）。同時定理有精確的邊界：

\(T\) 必須足夠強（含 \(Q\) ）：Presburger 算術（只有 \(+\) ）完備且可判定；實閉域理論（Tarski）完備可判定。弱到一定程度，不完備性消失。
\(T\) 必須遞迴公理化：真算術（ \(\operatorname{Th}(\mathbb{N})\) ，所有真語句）完備但不可遞迴公理化。
\(G_T\) 依賴 \(T\) ：不同的 \(T\) 有不同的 \(G\) ——不完備性是「系統族」的現象。

歷史啟示#

對角線法的第三次登場：Cantor（證不可數）、Russell（造矛盾）、Gödel（證不可判定）——同一結構的三種命運：定理、悖論、不可判定。關鍵差異在「取反」的對象是否被系統預先保證存在。
第二定理的殺傷比第一定理大：第一定理說「有漏網語句」，可加公理補；第二定理說「補不完」（新系統有自己的 \(\operatorname{Con}\) ）——一個無窮上升的階梯，永無終點。
「真」與「可證」的分裂是永久的：此後數學基礎的研究對象從「什麼是真」轉為「真與可證的差距有多大」（證明論序數、逆數學，6.3 節）。

與其他章節及領域的關聯#

2.1、3.1 節：對角線法的譜系。
3.3 節：Hilbert 綱領是本定理的靶子與受益者。
6.2 節：編碼與對角線引理的技術細節。
6.3 節：綱領的轉型與重生。
5.3 節：非標準模型中 \(G_T\) 的真值行為——獨立性的模型論形象。
7.1–7.3 節：可計算性理論把第一定理的「遞迴可枚舉但不可判定」變成停機問題。
計算機科學：第二定理是形式驗證的邊界（Lean 不能證自身一致，只能證「若元理論一致則我一致」）；Goodstein 型獨立性出現在組合學（Kruskal 樹定理、Paris–Harrington Ramsey 定理）。
哲學／認知科學：Lucas–Penrose 論證（「人心超越機器」）引用第一定理，其有效成分與謬誤至今爭論（10.3 節）。

練習#

寫出 Robinson 算術 \(Q\) 的公理清單，並說明為何 \(Q\) 缺歸納公理但仍足以支撐編碼。
證明：若 \(T \vdash G_T\) 則 \(T\) 不一致（用 \(\operatorname{Prov}_T\) 的性質與對角線引理）。
對 PA 的 Goodstein 數列 \(n = 3\) （ \(3 = 2 + 1\) ）寫出前三項與對應的序數下降。
說明為何「真算術 \(\operatorname{Th}(\mathbb{N})\) 」違反定理的哪個條件，因而完備。
思考題：第二定理說 \(T\) 不能證 \(\operatorname{Con}(T)\) ，但我們「相信」ZFC 一致。這種相信的認識論地位是什麼？比較：相信公理本身 vs 相信其一致性。

進階研讀：三個深化場景#

場景一：Gödel 與 Hilbert 學派的溝通失敗。1930 Königsberg 上 Gödel 的宣布被忽視；1931 論文發表後，von Neumann 立即寫信指出第二定理（Gödel 已知）；Bernays 1932 承認綱領受挫但主張「有限方法可擴充」。學派內的消化用了三年——基礎革命被理解的延遲是常態。

場景二：Gödel–Gentzen 的雙重否定翻譯（1933）。經典 PA 與直覺主義 PA 在翻譯下等價（3.2 節場景二）——不完備性對兩個學派同時成立，直覺主義沒有逃脫，形式主義也沒有被完全消滅：兩者的共同敵人是「可遞迴公理化的完備理論」。

場景三：不完全性的具體清單。Paris–Harrington 定理（1977，有限 Ramsey 定理的加強版）、Kruskal 樹定理（PA 甚至 ATR₀ 都不夠，Friedman）、Goodstein（Kirby–Paris）——「自然」的獨立命題清單持續增長，證實 Gödel 的抽象現象有大量日常化身。Friedman 的「grand conjecture」：多數數學定理可在比 ZFC 弱得多的系統中證明——不完備性與「日常數學的安全」可以並存。

名詞速查表#

** \(Q\) （Robinson 算術）**： \(0, S, +, \times\) 的極小公理，編碼的最小平台。
** \(\operatorname{Prov}_T\) **：可證性謂詞（遞迴可表達）。
對角線引理： \(\exists \theta\, (T \vdash \theta \iff \phi(\ulcorner\theta\urcorner))\) 。
** \(\omega\) -一致性**： \(T \not\vdash \exists x\, \phi(x)\) 同時 \(T \vdash \neg\phi(\bar n)\) 對每個 \(n\) 。
Rosser 技巧：以「最短證明」比較降低一致性要求。
Goodstein 數列：換底減一序列，終止性獨立於 PA。
** \(\varepsilon_0\) **： \(\omega^{\omega^{\cdots}}\) ，PA 的證明論序數。

年表速查#

1930：Königsberg 首次宣布。
1931：第一、二不完備定理發表。
1936：Rosser 強化；Gentzen 一致性證明。
1939：Hilbert–Bernays《數學基礎》II，第二定理的嚴格化。
1977：Paris–Harrington 獨立性。
1982：Kirby–Paris（Goodstein）。

深化問答三則#

問： \(G_T\) 是「真」的嗎？憑什麼？ 答：在標準模型 \(\mathbb{N}\) 中：若 \(T\) 一致，則無 \(G_T\) 的證明，故 \(\operatorname{Prov}_T(\ulcorner G_T \urcorner)\) 為假， \(G_T\) （其否定）為真。「真」是在 \(\mathbb{N}\) 的語義中判定的——這預先假定了「標準 \(\mathbb{N}\) 」的客觀性（5.3 節的爭論）。形式主義者會說： \(G_T\) 只是在 PA 的非標準模型中可真可假。

問：第二定理是否意味著「數學無法自證安全」？ 答：它說遞迴公理化且夠強的系統不能內證一致性。但 Gentzen 證 \(\operatorname{Con}(\mathrm{PA})\) （用 \(\varepsilon_0\) 歸納）、ZFC + 大基數證更強系統的一致性——安全證明總是可能的，只是要站在更高的層。「自足」不可能，「透明」可能。

問：不完備定理與羅素悖論的深層關係？ 答：兩者同源（對角線）而命運不同：悖論需要系統保證對角對象存在（概括原則），不完備性中對角對象（ \(G_T\) ）由語法構造給出、其存在不傷系統。Gödel 的洞見：把自我指涉從「對象語言」移到「後設語言的構造」，矛盾就變成洞見——這是對 3.1 節危機的技術性了結。

（本節完）