首先，哥德爾需要用一組符號來表達一個強的算術係統。哥德爾用了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 是變量，是自然數（正整數）
-
和 (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) 。
現有一對數 p(x, y) 是真的，如果 x 是公式 B 的變量的哥德爾數 和 y 是公式 B 的證明的哥德爾數。
考慮公式：
對所有的 y ~ p(x, y)
設上述公式的哥德爾數是 m , 考慮封閉公式：
G = 對所有的 y ~ p(m, y) , （此式是在上述公式中用 m 自替代 x 後得到）
上述公式表明 G 是一個真公式，因為它是由封閉公式得到。封閉公式的意思是 G 或~G 是一組公式邏輯推導的結果。
但是 G 又不是 m 的任何證明。
所以，G 是一個真公式，但它不能被證明。
本文是在吳道平先生CND原文上改寫而成，在此致謝。
更多我的博客文章>>>
