哥德爾配數

哥德爾配數

構造哥德爾句的基本方法，是所謂的“哥德爾配數”，即把S的不同的語形對象與不同的自然數一一對應，使得我們可以用數代表那些符號、符號的序列以及符號的序列的序列。
配數或編碼的思想並不是哥德爾首創的。我們可以找到許多對不同的對象進行編碼的例子，最簡單的如把一家的孩子編為老大、老二、老三，把兩組的學生編為一班、二班等等。我們通常用阿拉伯數字的序列表示數，如用3861表示某個特別的數，這也是一種編碼，但跟這裡說的配數方向相反，不是給“物”配數，而是以“物”代數。
對於一個形式語言的語形對象，有不同的配數方法。比如先給初始符號配數，再利用數的素分解的唯一性（算術基本定理），給初始符號的序列以及序列的序列配數。我們不必深入其中細節，只要知道，按哥德爾配數法，對每個符號、符號的序列或序列的序列，都可以通過基本的數值計算找到它所對應的唯一的自然數（稱為它的哥德爾數）；反之，給定這樣的一個自然數，我們也可以能行地把它所對應的語形對象還原出來。
對於S的一個語形對象，我們記它的哥德爾數為[]。

主要內容

GedeerPeishu哥德爾配數《C加elnumbering)使用素數冪的乘積來表示自然數的任意有限序列xo，x1，…，xn的所有方案。表示本身稱為序列x。，xl，…，x，的哥德爾數，通常記為(x。，x，，…，x。>。雖然每種方案都有自己的長處與不足，但是，經常使用的是所謂標準方案。在標準方案中，序列x。，xl，…，x，用自然數即代1…代硯來表示，其中屍*表示第i個素數。按標準方案，許多不同的序列可能具有相同的哥德爾數。定義2元函式E，使得:E(i，z)=產zx[div(凡(i)‘+，，二)=o」其中:2元函式div定義為:若x>0，y>0且x整除y，則div(x，y)=1;否則div(x，y)=O。P。(i)是第i個素數。若z是序列x。，x;，…，x，的哥德爾數，則對每個0簇i簇n有:E(i，z)=x:;對每個i>n有:E(i，z)=0。函式E稱為提取函式，值E(0，z)，E(1，z)，，二稱為z的分量。定義1元函式Lh，使得:Lh(z)一。、〔n凡(，)““，·，一z」則Lh(z)是整除z的最大素數的下標。函式Lh稱為長度函式，Lh(z)的值稱為z的長度，常記為}zI。為了對不同的序列提供不同的表示，經常使用標準方案的以下兩種變形:在第一種變形中，序列x。，xl，”’，x，用自然數即十’代1十’…玲十’來表示。按這種方案，許多自然數根本不表示任何序列。在第二種變形中，序列xl，xZ，…，x，用自然數瑞代‘玲…代n來表示。按這種方案，並非每個自然數都表示某個序列。除此之外，還有許多其他的變形。哥德爾配數為長度不等的所有有限序列規定了一個順序。許多重要定理的證明都用到哥德爾配數。

哥德爾句

哥德爾句g是一個自指句，在直觀上，g表達的意義正是“g在S中不可證”。這種談論自身的自指句總有些糾纏。比如，如果一個自指句p說的是“p不為真”，那么就有我們熟知的說謊者悖論：p真，若且唯若p不真。但是，哥德爾句並不導致悖論。g說的是“g在S中不可證”，而情形也恰恰是g在S中不可證，因此，（當S滿足哥德爾定理所要求的條件時），g是真的。真的不必在S中可證，這並無悖理之處，只說明S不完全。
構造S中的自指句的一般技巧，由下面的對角化引理顯示出來：
如果S的語言中可定義的φ(x)表達數的性質，那么就存在φ(x)的一個可證不動點，即這樣的一個算術句ψ，使得Sψφ([ψ])。
就是說，S可證：ψ為真，若且唯若它的哥德爾數具有φ所表達的性質（比如：[ψ]是一個S-公理的哥德爾數）。在這個意義上，S“肯定”了，ψ說的是它“自身”具有φ所表達的性質（比如：ψ是一個S-公理）。這樣的自指句如何構造呢？
對於給定的算術式φ(x)，如前面提到的E(x)（即y(x=y+y)），我們可以用n（它在S的語言中表達數n）代入其中的x，從而得到一個符號句，如E(n)。這是元數學中的代入運算Sub。Sub(x,y)=用數y代入其哥德爾數為x的符號式的變元的結果的哥德爾數。代入過程是機械可檢驗的，因此Sub(x,y)=z在S中強可表達為Sub(x,y)=z，這是S的符號式。
考慮運算Sub(x,x)。它是用x代入其哥德爾數為x的符號式的結果（的哥德爾數），在S中表為函式式Sub(x,x)。用x代入它自己標示的符號式，就是這裡所謂的“對角化”。
在普通算術里，用Sub(x,x)代入φ(x)中的x，得到結果φ(Sub(x,x))，設其哥德爾數為m。
再用m代入φ(Sub(x,x))中的x，得到結果φ(Sub(m,m))。
因此，我們用m代入它自己所標示的符號式φ(Sub(x,x))，得到算術句φ(Sub(m,m))。這個直觀過程表明，Sub(m,m)=[φ(Sub(m,m))]。這樣，我們就構造出了一個算術句ψ，即φ(Sub(m,m))，使得ψ就是φ([ψ])。
因為Sub在S中可表達為Sub，而語句的同一性在S中可證為等價式，所以，把以上過程實現在S里，我們就有：
Sψφ([ψ])。
這證明了對角化引理。
令上面的φ(x)為ProvS(x)，則根據引理，存在算術句g，使得
（***）SgProvS([g])。
這個g，當然就是哥德爾句。它的形式是對一個-句的否定，這種句子，叫-句。我們也可以稱它們為G型句（哥德爾句、哥德巴赫猜想等，都是這種形式）。
對角化引理的一個推論是，我們不能在S中定義算術式True(x)，使得算術句φ是真的若且唯若S可證True([φ])。否則就會有性質True(x)的一個可證不動點p，說自己不是真的。這陷入了說謊者悖論。“真”不能在S中定義，通常稱作塔斯基定理，但哥德爾在證明自己的定理時已經發現了它。（雖然“…是真的算術句”不能定義，但“…是真的G型句”等限制後的性質卻可以定義。這樣得到的不動點，雖然說自己不是真的G型句，但它的確不是，因此是真的。）

哥德爾不完全性定理

哥德爾定理是數理邏輯中的一個定理，1931年奧地利邏輯、數學家克爾特.哥德爾(KurtGodel)發現並證明的，這個定理徹底粉碎了希爾伯特的形式主義理想。

第一不完全定理

設系統S包含有一階謂詞邏輯與初等數論，如果S是一致的，則下文的T與非T在S中均不可證。

第二不完全定理

如果系統S含有初等數論，當S無矛盾時，它的無矛盾性不可能在S內證明。

第一不完備性定理

任意一個包含算術系統在內的形式系統中，都存在一個命題，它在這個系統中既不能被證明也不能被否定。

第二不完備性定理

任意一個包含算術系統的形式系統自身不能證明它本身的無矛盾性。

哥德爾