隨筆
隨筆，聊天
首先，哥德爾需要用一組符號來表達一個強的算術係統。哥德爾用了12個常量，9個變量。因為符號少了，表達就必然複雜。比如說，常量中的數字隻有一個0，如何表達自然數？辦法是常量中還有一個表示“直接後繼”的符號s，意義一看就懂：s0表達0的直接後繼數1。以此類推，ss0為2, sss0為3，等等。可以想象，如果數字大到成千上萬，那該有多長。因此請不要考慮“可操作性”問題。數學證明隻考慮原則上是否可行。
其次，哥德爾需要一套方法來將一個算術係統中所有的公式編碼。請注意，不僅是總共21個常量和變量，而且要將所有由這些量組成的公式全部編碼。這裏，就表現出哥德爾的天才。
他為每個常量或變量指定一個數，稱為“哥德爾數”(Godel Number)，12個常量的哥德爾數就是1-12，9個變量的哥德爾數分別是13，17，19以及它們的平方、立方。
然後就可以編碼了。他的編碼方法被稱為“哥德爾編碼(Godel Numbering)”。每個符號都有了哥德爾數，比如0的哥德爾數是6，=是5，那麽公式0=0是不是就編碼為656？不是，下麵要解釋為什麽這樣編碼不行。
哥德爾編碼是，用素數2，3，5，7，9，11……來表示符號的在公式中的順序，而用符號的哥德爾數作為其指數。因此，0=0，第一個位置上是0，0 的哥德爾數是6，因此在這個位置上的0就是2的6次方，根據同樣原則=是3的5次方，第二個0 是5的6次方，這個公式的哥德爾編碼就是它們的乘積: 2的6次方乘3的5次方乘5的6次方，這個數是243,000,000。這就是這條公式的哥德爾數。
這麽簡單的一條公式就得用這麽大的數字來編碼，那麽複雜的公式用上了13次方，17次方甚至19次方，不是大到一個編碼要寫上幾十頁紙？
沒有錯，是這樣。再提醒一下，不要考慮可操作性，沒有人真的去做這樣複雜的編碼，這隻是原則上可行的方法。
不難想象，隻要知道0的哥德爾數是6，= 是5，從243,000,000可以唯一恢複為64乘以243乘以15625，進一步恢複為2的6次方、3的5次方、5的6次方，最後恢複為0=0。顯然，單純以哥德爾數來代替哥德爾編碼，比如以656來編碼0=0，就不具有唯一可恢複性。
這樣，有了一套可以表征一個算術係統的符號、有了一種編碼方法，可以將那個係統每一個的公式都編碼成一個整數，而且這個整數可以唯一地恢複為原有的公式。哥德爾又定義了一係列規則。下麵是他的少部分定義，對下文必不可少：
(1) 定義1 : 替代(x, v, y)
其中v是一個變量。意思是用y替代公式x中的v。大家已經明白，這裏的x，v和y, 都是哥德爾數。當然，替代之後仍然得到一個哥德爾數。
所以下麵的替代(y, 17, y)表示 “ 用 y 來替代公式y 中的哥德爾數是17 的變量 ” ；替代(n, 17, n)表示 “ 用 n 來替代公式n 中的哥德爾數是17 的變量 ” 。替代(n, 17, n) 是一種有意思的替代，稱為 “自替代 ” 。
為什麽要用 替代(x, v, y) ？
因為在算術係統 , 證明的過程經常是替代過程 ，如
(a) ~(sa= 0) 公理
(b) ~(s1= 0) 將1替代(a) 式中的 a
~ 是邏輯否定詞 ，s 是 “直接後繼”符號 ，a 是變量，是自然數（正整數）
(?a) 和 (b) 構成一公式 組合 ，它由兩個哥德爾數 k, l 係列組成，記為 B (w) , w 是指k或 l 。
替代(x, v, y)時，替代後公式x 不再包括v ，替代之後結果稱為封閉公式。
(2) 定義2： 證明(u, B)
意思是公式u是公式B的一個證明。再提醒一下，u和B也都是哥德爾數。
(3) 定義3： 可證(B):(存在一u) 證明(u, B)
意思是“存在一哥德爾數u，u是哥德爾數B的證明”。更簡單的陳述是“哥德爾數B可證。”
所謂證明(u, B) 就是在B的一係列公式中找出最後的公式，這裏是 B(l) 。
(4) 不可證(B); ~可證(B). (加一個邏輯否定詞 ~ )
表示哥德爾數B不可證。
將定義(1)具體化，比如說，有
(5) 替代(y, 17, y), 這條公式表示“用y來替代公式y中的哥德爾數17”，
在哥德爾的證明中，y的哥德爾數就是17。
然後用(5)替換(4) 中的B，就得到
(6) 不可證(替代(y, 17, y))
意思是“用哥德爾數y替代公式y中的變量17, 不可證”。這是一條形式命題，包含
變量。請記住17 恰好是y的哥德爾數，這一點在證明中非常關鍵。
當然這個命題仍然是一個哥德爾數。令這個哥德爾數為n, 然後再一次
運用規則，用n (也就是公式(6)的哥德爾數) 來替代y, 得到：
(7) 不可證(替代(n, 17, n)), “用哥德爾數n替代公式n中的變量17, 不可證”。
我們把這個公式命名為G:
(8) G =不可證(替代(n, 17, n))
上述公式表明 G 是一個真公式，因為它是由封閉公式得到。封閉公式的意思是 G 或~G 是一組公式邏輯推導的結果。
請注意思考一下，從(6)到(7)，我們作了什麽運算？我們正是運用了替代，以n代替
了n 中的變量y，即把n中所有的17(y的哥德爾數)，以n代替。因此G等於是說，
(9) G = 替代(n, 17, n)
然而 (7)說“替代(n, 17, n)不可證”，然而(9)告訴我們，G又等於“替代(n, 17, n)”，
於是
(10) G =不可證(G)
G 是一個真公式，但它不能被證明。
本文是在吳道平先生CND原文上改寫而成，在此致謝。
