2.2 哥德爾編號與自我指涉：數學透過「談論自身」宣告絕對完美的幻滅#

步驟一：把符號變成數字#

哥德爾的第一步是平凡的、卻是革命性的：給每個符號指定編號。

這個動作今天看來平淡無奇——它就是「字元編碼」。ASCII（1963）、Unicode、UTF-8 全是哥德爾編號的工程化後裔。1931 年它卻是概念突破：從此數學命題是一個數。

公式是一串符號 $s_1 s_2 \dots s_n$。用質數編碼：

\[\ulcorner s_1 s_2 \dots s_n \urcorner = 2^{g(s_1)} \cdot 3^{g(s_2)} \cdot 5^{g(s_3)} \cdots p_n^{g(s_n)}\]

（$p_n$ 是第 $n$ 個質數。）由算術基本定理（質因數分解唯一），編碼與解碼一一對應。例：公式 $0 = 0$ 編碼為

\[2^1 \cdot 3^5 \cdot 5^1 = 2 \cdot 243 \cdot 5 = 2430\]

一個命題 = 一個自然數。證明（命題的有限序列）同理也是一個自然數。數學的全部句法世界，被折疊進了自然數的宇宙。

關鍵問題：算術能否自己判斷「數 $x$ 編碼的序列是否是數 $y$ 編碼的公式的合法證明」？

答案：可以。檢查證明是純機械操作（逐條對照公理模式、檢查推理規則），所有這些操作都能用原始遞歸函數實現——即基本算術函數的和、積、有界極小化。於是存在算術公式：

\[\text{Proof}(x, y) \;=\; \text{「} x \text{ 是 } y \text{ 的證明」}\]

以及可定義的謂詞：

\[\text{Provable}(y) \;=\; \exists x\, \text{Proof}(x, y)\]

「被證明」從元語言（我們談論系統的話）跌落為對象語言（系統內部的一條算術公式）。 這是整個證明的阿基米德支點。

還需要最後一塊：造出一個說自己的公式。用「代入」的技巧：

考慮含一個自由變數的公式 $\varphi(x)$，其哥德爾數為 $n$。定義操作：

\[\text{subst}(n) = \ulcorner \varphi(n) \urcorner\]

（把數 $n$ 填入自身公式——「自我代入」。）此操作也是機械可算的，因此在系統內可表達。

現在構造公式 $G$：

\[G \;=\; \neg \text{Provable}\big(\text{subst}(\ulcorner \neg\text{Provable}(\text{subst}(x)) \urcorner)\big)\]

說白了，$G$ 的內容是：

「哥德爾數等於 $g(G)$ 的公式不可證明。」

而 $g(G)$ 恰好就是 $G$ 自己。於是 $G \leftrightarrow$「$G$ 不可證明」。

設系統 $S$ 一致：

若 $S \vdash G$：則存在證明，$\text{Provable}(g(G))$ 為真，$S$ 證明了一個假命題——矛盾（需要較強一致性條件，嚴格版用 $\omega$-一致性）
若 $S \vdash \neg G$：則 $S$ 證明「$G$ 可證」，而若 $S$ 真的一致，$G$ 其實不可證——$S$ 證明了假話，再次矛盾（而且第二不完備定理隨後指出：證明這一步需要的一致性，恰恰無法在系統內自證）

所以：$S \nvdash G$ 且 $S \nvdash \neg G$。而從外面（元數學）看，$G$ 是真的。∎

哥德爾編號＝「把程式存進記憶體」的邏輯前夜。馮·諾伊曼 1945 年設計儲存程式電腦時，這個思想已經存在十五年：指令與資料同質，都是數；程式可以讀取、修改、生成程式。自我指涉不是邏輯的 Bug，它是計算的本性：

哥德爾 1931	電腦時代
哥德爾編號	指令的機器碼表示
公式自代入	自我修改程式、解譯器讀取自身
「證明檢查器」可表達於系統內	編譯器用語言自身寫成（自舉，bootstrapping）
對角線引理	停機問題、Rice 定理、病毒與防毒的軍備競賽

圖靈 1936 年的證明（下一章）本質上是把哥德爾的算術化換成更直接的機器化——他不必繞道質數冪積，直接讓機器模擬機器。

哥德爾本人極為謹慎，論文發表後十年間僅少數人真正讀懂；他 1930s 反覆強調定理不否定希爾伯特的一切——只是否定了「系統內自證一致性」這一條
維也納學圈試圖把他收編為實證主義者，哥德爾（柏拉圖主義者）斷然拒絕：「形式主義者的立場是我的定理的直接對立面。」作者的哲學立場常被學派挪用，這是思想史的常態
1938 年起，哥德爾在普林斯頓 IAS 與愛因斯坦成為每日散步的摯友（愛因斯坦晚年說「我上班，只為了與哥德爾一起走回家」）——兩個顛覆各自領域的人，在流亡中互相取暖。科學社群的功能，常常是給「讓所有人不安的人」一個容身之處。