歌德爾不完全定理

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

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

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

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

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

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

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

8、m)，根據(jù)代入函數(shù)Sb(x,y)的定義，U(Zm)的歌德爾數(shù)為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)表達了直觀的算術(shù)命題：對所有自然數(shù)x而言，Pf(x,Sb(m,m)是假的，可記為( x) Pf(x,Sb(m,m),即所有自然數(shù)x都不是歌德爾數(shù)為Sb(m,m)的公式的證明的歌德爾數(shù)。即：歌德爾數(shù)為Sb(m,m)的公式不是可證的，但U(Zm)的歌德爾數(shù)正是Sb(m,m)，因此，與上述算術(shù)命題相應(yīng)的元數(shù)學(xué)命題就

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