6.2 編碼與對角線法#

本章導言#

Gödel 不完備定理的核心技術是一對工具：編碼（把語法裝進算術）與對角線引理（讓語句談論自身）。1931 年的原始編碼笨拙而可行；1936 年 Turing 把編碼改裝為「機器與程式」；今天的電腦——原始碼以數位儲存、程式處理程式——正是編碼技術的日常化。本節把編碼與對角線法拆開來講：前者是表達力工程，後者是自我指涉的受控使用，兩者合起來是數理邏輯最深的單一技術。

編碼：把語法裝進 \(\mathbb{N}\)#

編碼的目標：把符號、項、公式、證明映射為自然數，使語法關係變成算術關係。Gödel 配對函數：

它是雙射 \(\mathbb{N}^2 \to \mathbb{N}\) ，且其分量函數是遞迴的（可由初等函數定義）。用配對函數反覆叠代，可得任意有限序列的編碼 \(\langle a_0, \dots, a_{n-1}\rangle\) ，以及解碼函數 \(\operatorname{seq}(e, i)\) （第 \(i\) 個分量）。

編碼的三個關鍵性質（全部可證）：

1. 可計算性：編碼、解碼、「 \(p\) 是公式」「 \(p\) 是 \(T\) -證明」都是遞迴（原始遞迴）關係——機器可判定。
2. 可表達性：這些關係在 \(Q\) （弱算術）中一階可表達——系統內部能談論它們。
3. 可表示性：遞迴函數在 \(Q\) 中「可表示」： \(f(n) = m \iff Q \vdash \bar f(\bar n) = \bar m\) ——系統的證明行為與真實計算吻合。

性質 3（可表示性定理，Gödel 1931 第四、五節）是橋樑：外部（後設層）可計算 ⟹ 內部（系統內）可表達。由此 \(\operatorname{Prov}_T(y) \equiv \exists p\, \operatorname{Proof}_T(p, y)\) 在 \(T\) 內可表達，自我指涉成為可能。

對角線引理：語句的自我指涉裝置#

對角線引理（不動點引理）：設 \(\phi(x)\) 為含一個自由變元的公式。則存在語句 \(\theta\) 使

證明（構造性的，值得完整看）：

1. 對公式 \(x\) 定義函數 \(\operatorname{diag}(x) = \ulcorner x(\ulcorner x \urcorner)\urcorner\) （「把 \(x\) 自己代入 \(x\) 」的碼）。 \(\operatorname{diag}\) 是原始遞迴函數，故在 \(Q\) 中可表示為 \(\operatorname{Diag}(x, y)\) 。
2. 令 \(\theta := \forall y\,(\operatorname{Diag}(\ulcorner \phi \urcorner, y) \to \phi(y))\) ——「**凡 \(\phi\) 自己代入自己者，皆滿足 \(\phi\) **」。
3. 在 \(Q\) 中可證： \(\operatorname{Diag}(\ulcorner\phi\urcorner, \ulcorner\theta\urcorner)\) （因 \(\theta\) 就是 \(\phi(\ulcorner\phi\urcorner)\) 的展開）。故 \(Q \vdash \phi(\ulcorner\theta\urcorner) \to \theta\) 。
4. 反之由 \(\theta\) 的定義直接得 \(Q \vdash \theta \to \phi(\ulcorner\theta\urcorner)\) 。 \(\blacksquare\)

θ 是「提到自己的公式」：它不是神秘的循環定義，而是顯式構造—— \(\theta\) 的文本中不含 \(\theta\) ，只含 \(\phi\) 與「代入機制」。自我指涉被間接化了：語句指涉的是「某個構造過程的輸出」，而該過程恰好輸出自己。這與羅素悖論的直接指涉（ \(R \in R\) ）的技術差異就在此——間接化使自我指涉合法且可控。

對角線法譜系：三個登場、一次總結#

統一格式：設有「枚舉」 \(f: S \to \mathcal{P}(S)\) （或 \(\operatorname{Prov}\) 、 \(\operatorname{Halt}\) ），構造

\(D\) 不在枚舉中 → 矛盾或不可判定。差異全在「取反」後的命運：Cantor 的 \(D\) 是合法集合（定理）；Russell 的 \(D\) 被系統保證存在（悖論）；Gödel 的 \(D\) 是合法語句但不可判定（定理）；Turing 的 \(D\) 導致「假設算法存在→矛盾」（不可計算性）。

一個具體例子#

例題 6.2.1：構造 PA 的 Gödel 語句的「迷你版」：在一個玩具系統中完成對角線構造的全過程，使讀者看見 \(\theta\) 如何「說自己不可證」。

解：取玩具系統 \(S\) ：語言含常元數字 \(\bar 0, \bar 1, \bar 2, \dots\) 、一元函數符號 \(\operatorname{Pr}(x)\) （「 \(x\) 編碼的語句可證」）、語句碼之間的數字編碼。設 \(\phi(x) := \neg\operatorname{Pr}(x)\) 。

1. \(\operatorname{diag}(\ulcorner\phi\urcorner) = \ulcorner\phi(\ulcorner\phi\urcorner)\urcorner = \ulcorner\neg\operatorname{Pr}(\ulcorner\phi\urcorner)\urcorner\) 。
2. 構造 \(\theta := \neg\operatorname{Pr}(\ulcorner\neg\operatorname{Pr}(\ulcorner\neg\operatorname{Pr}\urcorner\ \text{代入自身}\urcorner)\urcorner)\) ——顯式寫出即「編碼為 \(\bar k\) 的語句不可證」，其中 \(\bar k\) 恰為本語句的碼。
3. 驗證不動點： \(\theta\) 說「 \(\bar k\) 不可證」，而 \(\theta\) 的碼恰是 \(k\) 。自我指涉閉合。

若 \(S\) 一致且 \(S \vdash \theta\) ，則存在證明碼 \(p\) ， \(S\) 可證 \(\operatorname{Pr}(\bar k)\) ，與 \(\theta\) 矛盾——故 \(S \not\vdash \theta\) 。若 \(S \vdash \neg\theta\) ，即 \(S \vdash \operatorname{Pr}(\bar k)\) ，但 \(\operatorname{Pr}\) 的可表示性保證（ \(S\) 一致時）沒有真證明卻證「可證」是 \(\omega\) -不一致——故（ \(\omega\) -一致下） \(S \not\vdash \neg\theta\) 。 \(\blacksquare\)

例題 6.2.2（Tarski 不可定義性的對角線證明）：證明：不存在公式 \(\operatorname{True}(x)\) 使對每個語句 \(\phi\) ， \(Q \vdash \operatorname{True}(\ulcorner\phi\urcorner) \iff \phi\) 。

解：反設有 \(\operatorname{True}\) 。取 \(\phi(x) := \neg\operatorname{True}(x)\) ，由對角線引理得 \(\theta\) ： \(Q \vdash \theta \iff \neg\operatorname{True}(\ulcorner\theta\urcorner)\) 。但由 \(\operatorname{True}\) 的性質（取 \(\phi := \theta\) ）： \(Q \vdash \operatorname{True}(\ulcorner\theta\urcorner) \iff \theta\) 。合併： \(Q \vdash \theta \iff \neg\theta\) ， \(Q\) 不一致——矛盾。謊言者悖論以無矛盾的姿態重現為「真謂詞不可定義」定理（3.1 節場景三、5.1 節）。 \(\blacksquare\)

編碼的計算時代：從定理到工程#

1931 年的編碼是證明的技術；1936 年起它成為計算的理論：

• Turing（1936）：程式以自然數編碼（通用機的輸入碼）——通用 Turing 機 = 「程式處理程式」的機器，現代作業系統與編譯器的理論原型。
• Kleene 的 s-m-n 定理與遞迴定理：程式可獲知自身碼（ Kleene 不動點定理是對角線引理的計算版）——自我複製程式（Quine）、病毒、巨集系統的理論根據。
• 現代形式驗證：Lean 的 kernel 以自然數（或更高效表示）編碼證明項並機械檢查——Hilbert 的有限方法願景，以 Gödel 編碼的工程後代實現。

歷史啟示#

• 編碼是「表達力」的工程：把語法塞進算術，看似取巧，實則揭示了算術的普遍性——它足夠豐富以模擬任何有限符號操作。這是「計算的普遍性」的最早定理式陳述，直接通往 Turing 普遍機（7.1 節）。
• 間接自我指涉是受控的：對角線引理表明自我指涉不必是悖論——構造技術決定自我指涉的命運。
• 後設層的合法化：Gödel 證明「系統可以（部分地）談論自己」，但「真」不行（Tarski）。可談與不可談的清單——可證可以，真不可以——是二十世紀邏輯最精確的哲學成果之一。

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

• 2.1、3.1 節：對角線法的譜系。
• 6.1 節：本節的兩件工具是第一定理的引擎。
• 7.1–7.3 節：編碼思想的機器化；停機問題是對角線法的程式版。
• 8.2 節： \(L\) 的可定義性分層使用類似的「碼與階段」技術。
• 9.2 節：「證明即程式」使編碼從「表示」升級為「同一」——命題與類型、證明與程式同構。
• 計算機科學：Quine 程式、編譯器自舉（compiler bootstrapping）、反射式程式設計、Gödel 編碼在柯爾莫哥洛夫複雜性中的應用（不可壓縮串的存在）。
• 密碼學：對角線構造是「不可判定/不可區分」證明的模板（如 Kolmogorov 複雜性的不可計算性）。

練習#

1. 計算 \(\langle 3, 5\rangle\) 與 \(\langle 0, 0\rangle\) （Cantor 配對），並驗證解碼還原。
2. 寫出例題 6.2.1 中 \(\theta\) 的完整顯式文本（用「 \(\ulcorner\phi\urcorner =\) 某數 \(n\) 」的假設），指出其中沒有循環定義的哪個特徵。
3. 證明對角線引理在「 \(\phi\) 含參數」情形的推廣：對任意 \(\phi(x, \vec z)\) 存在公式 \(\theta(\vec z)\) 使 \(Q \vdash \theta(\vec z) \iff \phi(\ulcorner\theta\urcorner, \vec z)\) 。
4. 用對角線法證明：Kolmogorov 複雜性 \(K(x)\) （最短程式輸出 \(x\) 的長度）不是可計算函數。
5. 思考題：對角線引理給出的 \(\theta\) 「指涉自己」嗎？它只指涉一個構造過程。這對「自我意識」「自我指涉」的哲學討論有何啟示？

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

場景一：Gödel 編碼的原始笨拙與現代簡潔。1931 的編碼用質數分解（ \(2^{a_1} 3^{a_2} \cdots\) ），解碼需質因數分解（原始遞迴但繁瑣）；現代以配對函數或二進制編碼。技術的「醜」不影響定理的「真」，但影響傳播速度——編碼的簡化（Mendelson、Smullyan 的教科書處理）使不完備定理進入大學部課程。

場景二：Kleene 遞迴定理（1938）：對每個可計算函數 \(F(e, x)\) ，存在程式 \(e_0\) 使 \(\varphi_{e_0}(x) = F(e_0, x)\) ——程式可以合法地「知道」自己的碼。這是對角線引理的計算版，其工程化身：自引用的 Quine 程式、自舉編譯器、元程式設計。1931 年的邏輯技術在 1970 年代成為軟體工程常識。

場景三：Yablo 悖論與無窮對角線。Stephen Yablo 1985 構造無窮語句列 \(Y_1, Y_2, \dots\) ，每句說「之後的句子都假」——沒有直接自我指涉（每句只指涉更後的），卻仍矛盾。這顯示對角線矛盾的根源不是「自我指涉」而是「循環依賴的無窮版本」，深化了 Gödel 與 Tarski 的分界分析。

名詞速查表#

• Gödel 配對： \(\mathbb{N}^2 \to \mathbb{N}\) 的原始遞迴雙射。
• 可表示性：遞迴函數在弱算術中可表達且證明行為吻合。
• 對角線引理： \(\phi\) 的不動點語句 \(\theta\) 。
• ** \(\operatorname{diag}\) 函數**： \(x \mapsto \ulcorner x(\ulcorner x\urcorner)\urcorner\) 。
• Tarski 不可定義性：真謂詞不可在系統內定義。
• Kleene 遞迴定理：程式自我指涉的計算版。

年表速查#

• 1931：Gödel 編碼與對角線引理。
• 1933：Tarski 不可定義性。
• 1936：Turing 機與通用機；Rosser 技巧。
• 1938：Kleene 遞迴定理。
• 1950s–60s：s-m-n 定理、遞迴論標準化（Rogers 1967）。
• 1962：Quine〈論「因為它而存在」〉（自指結構的哲學分析）。
• 1985：Yablo 悖論。

深化問答三則#

問：對角線引理是「定義 \(\theta\) 為自己」的循環定義嗎？ 答：不是。 \(\theta\) 的構造是顯式的：先有 \(\phi\) ，再機械地展開代入。 \(\theta\) 與 \(\phi(\ulcorner\theta\urcorner)\) 的等價是事後證明的不動點性質，不是構造的前提。循環定義（vicious circle）與不動點（fixed point）的區別正是 3.1 節危機與 6.1 節定理的分界線。

問：編碼需要算術有多強？ 答：Robinson 算術 \(Q\) 就夠——只需 \(+, \times\) 與極少公理。Presburger 算術（只有 \(+\) ）不夠：乘法缺失使編碼失去表達力，且 Presburger 完備可判定。乘法是自我指涉的門檻——這個精確的邊界（Matiyasevich 1970 的丟番圖刻畫）是二十世紀邏輯最深的技術成果之一。

問：對角線法與電腦病毒的關係？ 答：結構上同源：病毒需要「把自身複製到宿主」，即程式取得自身碼並輸出它——Kleene 遞迴定理保證這類程式存在，且沒有循環定義（碼由構造獲得）。Von Neumann 1948 的自複製自動機理論直接引用此結構——邏輯學的對角線技術是生命自我複製理論的數學祖先之一。

（本節完）