跳轉到

5.2 GODEL完備性定理1930#

本章導言#

1929 年，23 歲的 Kurt Gödel 在維也納大學的博士論文中證明：一階邏輯的語法與語義完全吻合——凡語義上有效的公式皆可形式證明。這就是完備性定理，Hilbert–Ackermann 1928 年提出的公開問題的答案。它是 Hilbert 綱領（3.3 節）的重大勝利：形式系統確實「抓得住」一階真理。一年之後，同一作者證明了它的反面限制（不完備性，第 6 章）。本節講完備性定理的證明思想——模型構造——以及它如何催生了整個模型論。

定理的精確表述#

完備性定理（Gödel 1929/1930）：對一階語言 \(\mathcal{L}\) 的任意語句集 \(\Gamma\) 與語句 \(\phi\) ：

\[ \Gamma \models \phi \implies \Gamma \vdash \phi. \]

等價形式（哥德爾形式，更常用）：

\[ \Gamma \text{ 可滿足（有模型）} \implies \Gamma \text{ 語法一致（推不出矛盾）}. \]

以及模型存在定理：語法一致的語句集有模型。注意方向：完備性定理說「一致則有模型」——它把語法性質（一致性）轉換為語義對象（模型）。這是定理最深的生產力：只要系統不矛盾，模型就自動長出來。

證明思想：HENKIN 構造#

Gödel 的原證明歸約到緊緻性的特例；現代標準證明是 Henkin 構造（Henkin 1949 簡化版），步驟清晰：

步驟 1：見證常元（Henkin constants）。對 \(\Gamma\) 中每個形如 \(\exists x\, \phi(x)\) 的子公式，加入新常元 \(c_{\phi}\) 與公理 \(\exists x\, \phi(x) \to \phi(c_{\phi})\) 。目的：保證每個存在命題在語言內有具名見證。

步驟 2：極大一致擴張。將擴張後的語言的語句按枚舉逐一加入或加入其否定，得極大一致理論 \(T^*\) ：每個語句 \(\phi\) ， \(T^* \vdash \phi\) 或 \(T^* \vdash \neg\phi\) 。

步驟 3：項模型。域取閉項的等價類： \(t_1 \sim t_2 \iff T^* \vdash t_1 = t_2\) 。解釋 \(f([t_1], \dots) = [f(t_1, \dots)]\) 。由構造可證：

\[ T^* \vdash \phi \iff \mathfrak{T} \models \phi \quad (\text{項模型的真值定理}). \]

步驟 4：歸還。 \(\mathfrak{T} \models \Gamma\) ，故 \(\Gamma\) 有模型。

證明的哲學重量：模型不是從天上找來的，是用語法材料（項與等價類）拼出來的。語法一致性本身就含有足夠的「存在資訊」。這與 Hilbert 的理想元素論證（3.3 節）遙相呼應，但方向相反：Hilbert 從模型護形式，Gödel 從形式造模型。

完備性的三個推論：模型論的三根柱子#

  1. 緊緻性（compactness）： \(\Gamma\) 的每個有限子集可滿足 \(\Rightarrow \Gamma\) 可滿足。（若不可滿足，則 \(\Gamma \models \bot\) ，由完備性 \(\Gamma \vdash \bot\) ，證明有限，只用到有限子集——矛盾。）5.3 節展開。
  2. Löwenheim–Skolem：可數語言的可滿足理論有可數模型（Henkin 構造的域是項等價類，至多可數）。
  3. 語法與語義的可互換性：證明一致性可用模型（如 \(V_\kappa \models \mathrm{ZFC}\) ），證明不可滿足可用語法分析——兩條研究路線互相轉換。

一個具體例子#

例題 5.2.1：用完備性定理證明：若圖論語句集 \(T\) （語言 \(\{E\}\) ）在所有有限圖上都為真，且 \(T\) 語法一致，則 \(T\) 有一個無窮圖模型。

解：設 \(T\) 一致。加入語句集 \(\Sigma = \{\sigma_n : n \in \mathbb{N}\}\) ，其中 \(\sigma_n\) = 「至少存在 \(n\) 個兩兩不同的頂點」（一階可寫： \(\exists x_1 \cdots \exists x_n\, \bigwedge_{i<j} x_i \ne x_j\) ）。

斷言 \(T \cup \Sigma_0\) 對每個有限子集 \(\Sigma_0 \subseteq \Sigma\) 一致：取 \(\Sigma_0\) 中最大的 \(N\) ，由假設有（有限）圖 \(\mathfrak{G}_N\) 滿足 \(T\) 且頂點數 \(\ge N\) ，故 \(\mathfrak{G}_N \models T \cup \Sigma_0\) ，由可靠性 \(T \cup \Sigma_0\) 一致。

每個有限子集 \(T \cup \Sigma_0\) 一致；由緊緻性（完備性定理的推論）， \(T \cup \Sigma\) 一致；再由完備性定理（模型存在形式）， \(T \cup \Sigma\) 有模型 \(\mathfrak{G}^*\) ——它是滿足 \(T\) 的無窮圖。 \(\blacksquare\)

方法論要點：整個論證沒有構造任何具體無窮圖——無窮模型的存在是從「有限近似的一致性」中邏輯地抽出的。這是非構造性存在證明的極致形式，也是 Kronecker（2.3 節）最不能接受、而模型論以之為日常的推理類型。

例題 5.2.2（緊緻性的代數應用）：證明：若域 \(K\) 的每個有限生成子環都嵌入某個域，則 \(K\) 本身嵌入某個域。

解：考慮語言 \(\{+, \times, 0, 1\} \cup K\) （ \(K\) 的每個元素作常元）與理論

\[ T = \text{域公理} \cup \{k + l = m : k + l = m \text{ 在 } K\} \cup \{k \cdot l = m\} \cup \{\bar{k} \ne \bar{0} : k \ne 0\}. \]

\(T\) 的每個有限子集只涉及 \(K\) 的有限個元素，生成有限子環 \(R_0\) ；由假設 \(R_0\) 嵌入域 \(F_0\) ， \(F_0\) 給出 \(T\) 的有限子集的模型。緊緻性給出 \(T\) 的模型 \(F\) ， \(K\) 經解釋嵌入 \(F\) 。 \(\blacksquare\)

這正是「域的分式環構造」的無窮推廣：緊緻性把代數的局部構造黏合成全域存在。模型論與代數的這類互餵（代數閉域的完備性、阿廷–施賴爾定理）是 1960 年代模型論成為「實用數學」的標誌。

GÖDEL 的 1929：一年之間的兩個方向#

值得強調歷史的弔詭：完備性（1930 發表）與不完備性（1931 發表）是一對方向相反的定理。

完備性定理 不完備性定理
對象 純一階邏輯 含算術的理論
結果 語法抓得住語義 語法抓不住算術真理
意義 形式化的可行性 形式化的極限

關鍵在於對象不同：一階邏輯（無算術）完備；一旦理論強到能表達自然數的加法乘法，不完備性降臨。兩定理合起來畫出形式化的精確邊界——這正是 Hilbert 綱領需要的答案，雖然答案的一半出乎 Hilbert 之意料。

歷史啟示#

  • Henkin 構造是「語法造模型」的範式：項模型技術推廣為力迫法（8.3 節）、可構造宇宙（8.2 節）的同族工具——模型論的建造術一脈相承。
  • 緊緻性是「局部到整體」的邏輯定理：有限近似的一致性保證全域模型——這在拓撲（緊緻性的名稱來源：積拓撲的 Tychonoff 類比）、代數、組合中反覆發力。
  • 勝利與失敗相隔一年：完備性證實形式化抓得住「純邏輯」，不完備性證實抓不住「算術」。形式化的能力邊界被 Gödel 一人兩年內測繪完畢。

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

  • 5.1 節：語法—語義對偶是本定理的主題。
  • 5.3 節：緊緻性與非標準模型——完備性的第一應用。
  • 6.1 節：不完備性是完備性的邊界標記。
  • 4.3 節： \(V_\kappa \models \mathrm{ZFC}\) 是完備性定理的「信任方向」用法（由模型證一致）。
  • 8.3 節：力迫法的模型構造是 Henkin 精神的遠親。
  • 7.3 節：完備性使一階邏輯的有效性半可判定——Turing 機可枚舉全部證明，但不會停機於無效公式。
  • 計算機科學：SAT/SMT 求解器是完備性的工程化（命題邏輯完備且可判定）；Prolog 的 SLD 消解是一階片段的證明搜索。

練習#

  1. 完成緊緻性由完備性的推導：若 \(\Gamma\) 的每個有限子集可滿足，則 \(\Gamma\) 一致（反證 + 證明的有限性），再由模型存在定理得模型。
  2. 寫出「至少 \(n\) 個元素」的一階語句 \(\sigma_n\) ，並證明 \(\{\sigma_n : n \ge 2\} \cup \{\text{「至多 } 1 \text{ 個元素」}\}\) 有限可滿足但不可滿足——解釋這與緊緻性不矛盾的原因。
  3. 在項模型構造中，證明關係符號的解釋是良定的（與代表元的選取無關）。
  4. 用例題 5.2.2 的技術證明：每個交換環的局部化到域的存在（分式環的存在性）的模型論重述。
  5. 思考題：完備性定理證明「一致則有模型」，但 ZFC 不能證明「ZFC 一致」。「有模型」與「一致」在 ZFC 內部討論時的處境有何不同？

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

場景一：Gödel 的博士論文與會議宣布。1929 年論文〈論邏輯演算的完備性〉；1930 年 8 月 Königsberg 會議上宣布不完備性（一天討論後 von Neumann 立刻理解其證明並私下重推）。同一場會議見證了 Hilbert 綱領的勝利與死刑判決——科學史的戲劇密度罕有其匹。

場景二：Henkin 定理與內模型技術。Henkin 1949 的簡化使完備性證明進入教科書；其「保證存在見證」的思想推廣為飽和模型、初等鏈（Tarski–Vaught 檢驗）——模型論的構造工具箱成形。Cohen 的力迫（8.3 節）雖然獨立發明，結構上是「條件化的 Henkin」。

場景三：完備性的計算面。一階邏輯的有效性半可判定：可枚舉全部有效式（枚舉證明），但非可判定（Church 1936、Turing 1936，7.3 節）。完備性 + 不可判定性 = 搜索會成功但不會知道何時該放棄——這是自動定理證明的根本處境，也是 SAT 求解器只在命題層（可判定）成功的理論原因。

名詞速查表#

  • 完備性定理： \(\Gamma \models \phi \Rightarrow \Gamma \vdash \phi\) ；等價地，一致理論有模型。
  • Henkin 常元：存在命題的具名見證常元。
  • 項模型：以閉項等價類為域的模型。
  • 緊緻性：有限可滿足則可滿足。
  • Löwenheim–Skolem：可數語言的可滿足理論有可數模型。
  • 半可判定：有效式可枚舉，但無判定算法。

年表速查#

  • 1928：Hilbert–Ackermann 提出完備性問題。
  • 1929：Gödel 博士論文。
  • 1930：完備性定理發表；Königsberg 宣布不完備性。
  • 1936：Church、Turing 證明一階邏輯不可判定。
  • 1949：Henkin 簡化證明。
  • 1950s：模型論成為學科（Tarski、Robinson）。
  • 1969：Lindström 刻畫定理。

深化問答三則#

問：完備性定理證明「數學可以被形式系統完全捕捉」嗎？ 答：不。它只針對一階邏輯的邏輯真理（不含任何特定數學結構的真理）。數學理論（PA、ZFC）的真理超出一階邏輯真理——不完備性定理正是在「理論真理」層面否定完全捕捉。完備性是邏輯的勝利，不是數學的勝利——區分這兩層是理解 Gödel 兩定理的關鍵。

問：項模型的域「全是語法對象」，這樣的模型有意義嗎？ 答：有，而且正是它的力量：模型的存在性不依賴任何「外部」數學直覺，只依賴語法一致性。代價是項模型通常醜（不可數理論的項模型可以很怪）——但模型論後來發展出的飽和模型、素模型理論，就是「把 Henkin 模型打磨成好模型」的工藝史。

問：緊緻性與「有限近似」的哲學關係？ 答：緊緻性是邏輯版的有限性原理：任何「全體語句」的性質由有限片段決定。它使無窮對象的存在性問題化約為有限一致性問題——這既強大（非標準分析、無窮圖）又危險（Skolem 悖論、非標準自然數）。同一個定理，既是模型論的引擎，也是「絕對性」的終結者。

（本節完）