1、歌德爾不完全定理 定理：如果形式算術系統是簡單無矛盾的，那么它就是簡單不完全的；這就是說，在系統中存在具有形式(x)Ax的公式(或稱命題)B，使得B和B都不是系統的定理，這樣的B稱為不可判定的命題。§1.歌德爾定理的直觀說明 歌德爾從說謊者悖論(我正在說的這句話是假的)得到啟發，領悟到“真實性”與“可證性”是兩種不同的概念。歌德爾巧妙地用“可證性”代替“真實性”，把形式算術系統中的可證性表達在該系統中，避免了悖論，得到不完全性結論。不完全性定理的直觀證明：設形式算術系統是簡單完全的，即命題B或B 是可證的。若B可證，則它所表達的元數學命題“B在系統中不是可證的”就是真的，這就是說B不

2、是可證的，與題設矛盾。如果B 是可證的，則“并非B在系統中不是可證的”這一命題真，即B是可證的，這與題設“B 是可證的”相矛盾。由上可得：系統不是簡單無矛盾的。所以，如果形式算術系統是簡單無矛盾的，那么它就是簡單不完全的。B就是一個不可判定命題，即B與B 都不可證。由于B確實不可證，因而“B在系統中不是可證的”這一元數學命題就是真的，在系統中表達它的命題B也就是真的。因此，在系統中存在真的但又不可證的命題。(以下紅色字符表示公式，綠色字符表示歌德爾數，蘭色字符表示自由變項，粉紅色字符表示與歌德爾數相應的數字)§2.歌德爾配數法把自然數114依次配給如下符號：、 、=、+、·

3、 、0、(、)。對每一個不同的自然數變項配以大于14的不同素數。因此，我們在初始符號和自然數的一個子集之間建立了一一對應的關系。規定：自然數的有窮序列k1,k2,kn,對應于單個的自然數：2k1·3k2·5k3·Pnkn,這里Pi是第i個素數(按數量大小的順序排列)。一個公式是符號的有窮序列，對每個公式配以一個數，該數對應于配給其構成公式的符號的自然數序列。例如公式 (C)(C+a=b)中，該公式的歌德爾數為：213·37·523·714·1113·1323·1711·199·2317

4、·298·3119·3714 因構成該公式的12個初始符號對應的歌德爾數是： ( C ) ( C + a = b ) 13 7 23 14 13 23 11 9 17 8 19 14一個證明是公式的有窮序列，對每一個證明配以一數，它對應于配給其構成證明的公式的自然數序列。例如，以下兩個公式的序列：(a)(a=b)，(a)(a=0)，構成一個證明，設已求出第一式的歌德爾數為m，第二式的歌德爾數為n，則該證明的歌德爾數為：2m·3n。由此，在公式和自然數的一個子集之間，證明和自然數的一個子集之間建立了一一對應的關系。這樣，我們就為形式算術系統建立了一種完全算

5、術化的方法，使系統中的初始符號、公式和證明同自然數的子集之間建立起一一對應的關系。§3.歌德爾不完全性定理的證明在歌德爾原來的證明中，需要引用無矛盾性的概念。一個形式系統是無矛盾的，如果有一個公式F使得： F(Z0)，F(Z1)，F(Z2)，; ()F()并非全都可證。否則，F(Z0)，F(Z1)，F(Z2)，; ()F()全都可證，系統就是矛盾的。顯然，無矛盾性蘊涵簡單無矛盾性。嚴格陳述的歌德爾不完全性定理：如果形式算術系統是簡單無矛盾的，則U(Zm)不是可證的；如果系統是無矛盾的，則U(Zm)不是可證的。因此，如果系統是無矛盾的，則它就是不完全的，U(Zm)就是一個不可判定的命題

6、。§4.U(Zm)的形式構造設公式(a)(a=b)的歌德爾數為m，而自由變項b有歌德爾數為19。在公式中，以m的相應的數字Zm替代b，得公式 (a)(a= Zm )；該公式亦有一個歌德爾數，它是從歌德爾數為m的公式中，以m的數字Zm 替代歌德爾數為19的自由變項所得公式的歌德爾數。這就唯一地確定了一個數，該數是m和19的一個算式函數。假定原公式為A，包含自由變項b，所得公式記為SubStAZmb,該公式的歌德爾數記為Sb(mm19),簡記為Sb(m,m)。函數Sb(m,m)稱之為“代入函數”。該函數是能行可計算的，即它是一個遞歸函數。一般的，用Sb(x,y)表示代入函數，它是在歌德爾

7、數為x的公式(含自由變項)中，以y的數字Zm代替自由變項所得的公式的歌德爾數。如果原公式無自由變項，則代入的結果等于不代入，即Sb(x,y)=x。由于Sb(x,y)是遞歸函數，因而在系統中是數字可表示的，令表示Sb(x,y)的形式函數表達式是S (1，2)。Pf(y,a)相應于元數學謂詞“Y是公式A的一個證明”是遞歸謂詞，因而在形式算術系統中是數字可表達的，令表達Pf(y,a)的公式為B (1，2)。在形式算術系統中構造以下公式： U(a):( b) B(b,S(a,a),令該公式的歌德爾數為m。在上述公式中，以m的數字Zm替代自由變項a，得到公式：U(Zm):( b) B(b,S(Zm, Z

8、m)，根據代入函數Sb(x,y)的定義，U(Zm)的歌德爾數為Sb(m,m)。U(Zm)就是不可判定的命題，即：對所有b而言，B(b,S(Zm, Zm)是假的。由于S(Zm, Zm)表示Sb(m,m)，B (1，2)表達Pf(y,a)，因而U(Zm)即 ( b) B(b,S(Zm, Zm)表達了直觀的算術命題：對所有自然數x而言，Pf(x,Sb(m,m)是假的，可記為( x) Pf(x,Sb(m,m),即所有自然數x都不是歌德爾數為Sb(m,m)的公式的證明的歌德爾數。即：歌德爾數為Sb(m,m)的公式不是可證的，但U(Zm)的歌德爾數正是Sb(m,m)，因此，與上述算術命題相應的元數學命題就

9、是：“U(Zm)在系統中不是可證明的”。 U(Zm)在系統中表達了這個元數學命題，是一個斷定自身不可證的公式。歌德爾定理證明：如果形式算術系統是簡單無矛盾的，則U(Zm)不是可證的。假設U(Zm)可證，它就有一個證明，其歌德爾數為k,則有Pf(k,Sb(m,m).因為S (1，2)表示Sb(x,y)，B (1，2)表達Pf(y,a)，所以可得B(Zk,S(Zm,Zm)是可證的。又由假設U(Zm)即( b) B(b,S(Zm, Zm)可證，根據系統中的全稱消去規則可得：B(Zk,S(Zm, Zm)是可證的。這樣，系統中有矛盾。根據歸謬法，假設是不成立的。如果系統是無矛盾的(從而也是簡單無矛盾的)，則U(Zm)不是可證的。據，U(Zm)不可證，即沒有一個數是U(Zm)的證明的歌德爾數，而U(Zm)的歌德爾數為Sb(m,m),因此Pf(0,Sb(m,m),Pf(1,Sb(m,m),皆假，表達在系統中即為： B(Z0,S(Zm, Zm)， B(Z1,S(Zm, Zm)， B(Z2,S(Zm, Zm)，皆可證。根據系統的無矛盾性，可得 ：( b) B(b,S(Zm, Zm)即U(Zm)不是可證的。歌德爾第二不完全性定理：如果形式算術系統是簡單無矛