哥德爾不完全性定理 悖論式陳述 PM不可判定命題，和哥德爾可表達性定理——哥德爾讀後之十八

命題6 悖論式陳述 PM不可判定命題，和哥德爾可表達性定理——哥德爾讀後之十八

開始命題六，也就是哥德爾第一不完全性定理的閱讀了，但似乎離這個著名定理，還有那麼一丁點的距離。于是本篇依然是交代命題6證明前的那些必不可少的證明鋪墊。

一、哥德爾命題6，即第一不完全性定理的兩個版本表達

在預設了c為任意公式類及其相關條件，并且給出一緻性觀念之後，命題6（VI）即對後世影響深遠的哥德爾第一不完全性定理出場了。

（依據1962年英譯本）

這個有關不可判定命題存在的一般性結果讀作命題6：

命題6：

對于每一個一緻性的遞歸類公式c，都存在對應的遞歸類符号r，使得無論是對于v一般化r還是對于并非v一般化r，它們都不屬于Flg©。其中，v是r的自由變元。（（這裡的一般化是德語縮寫Gen，v一般化r的符号在1962英譯本中表示為v Gen r。并非v 一般化 r，則表示為Neg（v Gen r）。而這裡的後承集合是德語縮寫Flg，後承集合c在1962英譯本中表示為Flg©，請注意字型的不同。））

（而依據2000年英譯本）

這個有關不可判定命題存在的一般性結果展示如下：

命題6：

對于每一個一緻性的原始遞歸類公式k，都存在一個原始遞歸類符号r，使得無論是對于所有的v,r,即forall（v,r），還是對于并非所有的v,r，即not(forall(v,r))，它們都不屬于conseq(k)。（其中，v是r的自由變元）。

二、重溫編号（1）-（4）

這兩個版本有關命題6的描述好像沒有什麼差别，版本其它内容的對照也就沒有什麼必要了。這個命題6的哥德爾證明過程真還有點複雜悠長，在前有四個公式作為命題6證明的鋪墊，證明則從公式（5）開始，一環扣一環地前行，一直到公式（16），才使得命題6得證。

既然哥德爾這樣來為他的命題6的依據排序，重溫一下他在編号（5）之前的前四個編号（1）-（4），應該是一件有意義的事情。

那麼這個标号為（5）的公式，為什麼要這樣來編碼呢？這讓閱讀者很自然地又把目光折回到前面的文字，尋找這個編号（5）前面的那四個東西，看看這前面的四個公式和這個命題6證明究竟是個什麼關聯。

（一）從編号為（1）、類似悖論的表達式起步

我們浏覽命題6的字元旅行，由此也就從他的第一個編号，編号（1）開始。

旅程做了這樣的安排，經典閱讀也就從原著英譯本的52頁向後倒退，退到标号為（1）那個公式所在的第38頁。用超越的心境來看我們的閱讀，那不就是一個有窮盡的後退麼？而所謂經典的讀物不就是曆史的讀物麼？我們在實在世界的所謂旅行，實際上也是在回顧既往。過往才是可回憶可圈點的。所謂現在和未來，才更有點虛無和虛拟的味道。

回溯到編号（1），我們就看到這裡的公式是：

K≡provable(Rn(n))，标号（1）

這顯然是一個元數學的公式，表示的是符号Rn(n)不可證，而其中的Rn(n)，明顯是一個有某種自指特性的公式。用哥德爾的原話：這個公式，類似于法國數學家理查德的“理查德悖論“，也非常接近古希臘著名的“撒謊者悖論”。因為不可判定性命題Rq(q)精确地陳述了q屬于K，依據标号（1）的陳述，Rq(q)是不可證的。是以，我們面對的是一個斷定其自身不可判定性的命題，盡管其外貌并不存在什麼自身的循環。因為這個标号為（1）的字元串所展示的命題，是用斷定全部确定公式的不可證作為起點，也就是說，它用一個有限定的代換在按字母表n個排序中的第q個數位置的變元而得（參見哥德爾原著1962年英譯本第38頁和注釋16）。

這個公式（1），出現在哥德爾原著的導言部分，公式所在的系統是哥德爾給出的PM系統，即《數學原理》一書中的系統，簡稱為PM。這表明，哥德爾一開始就給出了PM系統中的不可證命題，命題6則是在PM中存在着不可證公式的基礎上，再來證明不同于PM的另一類系統，即哥德爾自己建構的系統P。這個類似于理查德悖論和羅素悖論的公式（1），在公式編号的意義上，恰好就是命題6證明的起點。

由此可以看到，這個PM系統，一開始就被認定其中有不可判定的命題。标号（1）作為論文開端，再來複述一遍還是有意義的。從PM中有不可判定性命題，到哥德爾的P中有不可判定性命題，顯然後者是前者的一個擴充。依然用哥德爾的語言：對這一不尋常結果的深入分析導緻了涉及到形式系統一緻性相關證明的令人驚異的另一些結果，這些結果的更為詳盡的細節見第四章的命題6-11。自然，特别重要的結果是這些命題中的命題6。

（二）用反證法證明PM中的不可判定性命題

1．公式Rn(n)如何構造？

我們把自然數作為基本符号basic sign（包括變元，邏輯常元，括号和分割點）；

一個公式是一個自然數的有限序列；

一個特指的證明模式是自然數有限序列的有限序列；

元數學的概念和命題是以就是涉及到自然數或者其序列的概念和命題。

這些概念、公式和公式序列都在PM中可定義或者可表述。

帶有一個自然數類型的自由變元（即類的類），我們稱之為類符号class-sign。顯然，類符号因為是自然數類型的，它可以依數字順序來排列。

PM中的一個公式A不可證，它的否定A也不可證，則稱A在PM中是不可判定的。

然後，我們把R作為在PM中可定義的序關系，由此，Rn即表示某個類符号序列中的某一個符号。因為我們已經規定了PM中的公式隻帶一個變元，則這個公式構成的類符号序列，就可以用Rn來指謂那個單一自由變元轄域中的第n個符号。而那個Rn(n)，則是升了一個級次的有限序列的有限序列，依然是那個單一自由變元轄域中的第n個符号。

Rn(n)由此而被構造出來。

2為什麼Rq(q)不可判定？

這就需要給出(Rq(q))的證明，肯定的證明和否定的證明。

哥德爾給出這個證明，僅僅使用了一段文字，但正是這段文字，導引出哥德爾論文的主體與核心。我們繼續往下看：

因為出現在這個标号（1）中定義的各個符号，都在PM中可定義，是以标号（1）中的K也就構造出來。這個構造出來的K意味着，存在一類符号S，使得公式S(n)陳述了自然數n屬于K。而這裡的S作為一個類符号則等同于一個特定的R(q)，這裡的q，即那個單一自由變元轄域中的第q個數字。由此而有：

S = R(q)

對于某個确定的自然數q成立。

這樣，哥德爾開始了他的反證法證明陳述，顯示對于命題(R(q),q)在PM中的不可判定。

假定命題(R(q),q)可證，那麼這個命題為真；但是這就意味着，如同我們已經說過的，q會屬于K，也就是，依據标号（1），n∈K當且僅當provable(Rq(q))，也就是provable(Rq(q))，R(q(q)不可證，這與前面假設相沖突。

再來一個反證，假定否定命題(R(q),q)可證，那麼(n∈K)，那就是命題(R(q),q)可證，同樣也是出現沖突。

是以無論是其肯定式可證，還是否定式可證的假設，都會出現邏輯沖突。由此，命題(R(q),q)既不是可證，其否定也不是可證。

這就表明：

這個看似自指的命題是不可判定的。

PM中存在不可判定命題，就這麼簡潔地得到了證明，但P中存在不可判定命題，卻不是這麼簡單，還有标号為（2），（3），（4）的表達式，來和命題6中的标号（5）接續，進而開始命題6的證明。

（三）标号為（2），（3），（4）的表達式，引入原始遞歸定義與對應可表達定理

1、标号（2），引入原始遞歸函數

沿着編号的線索繼續前行，從第38頁穿行到第43頁，我們遇到了标号為（2）的公式。在給出哥德爾自己的系統P，它的各種構件之後，哥德爾又引入了一個定義性公式，一個和系統P沒有直接聯系，但貫穿哥德爾論文全篇的一個定義。這就是對于數論函數的原始遞歸定義，也是遞歸論曆史上建立的最早一個定義（參見郝兆寬等著《遞歸論》引言部分）。

一個數論函數Φ(x1,x,…,xn)被說成是根據數論函數Ψ(x1,x,…,xn-1)和μ(x1,x,…,xn+1)而遞歸定義的，如果對于所有的x1,x,…,xn，k,以下等式成立：

Φ(0,x1,x,…,xn)= Ψ(x1,x,…,xn),

Φ(k+1,x1,x,…,xn)= μ (k,Φ(k,x1,x,…,xn),x,…,xn) 标号（2）

哥德爾給遞歸所做的這個定義客體，現在稱為原始遞歸函數。

函數觀念幾乎就是數學之命根，也是邏輯之命根。離開了函數觀念，想去讨論邏輯和數學，幾乎連數學與邏輯的門都進不了。當年柏拉圖在他的學園門口高挂起的牌匾“不懂幾何學者不得入内”，用在今天，應該是“不懂函數觀念的人不得入内”了。我桌上擺着一本剛剛去世的齊民友先生的著作，厚厚的《重溫微積分》。齊先生讨論微積分，書中的頭兩章都是在漫議函數。第一章以變量的科學為題，第二章幹脆就是函數。而克林先生的《元數學導論》和莫紹奎先生的《遞歸論》，則幾乎通篇都是函數。在先的博文中，我曾經用過莫先生關于函數的一個通俗定義：函數便是把一些數變成另一個數的運算。更嚴格一點，函數不是指的運算過程，而是指運算所根據的規則（參見莫紹揆《遞歸論》第15頁）。對函數的這樣一種運算過程和運算規則的了解，我們就有了元數學的視角了。

回到哥德爾的著作上來，那麼，我們該如何了解哥德爾的原始遞歸函數呢？

第一，有本原函數，也稱初始函數的觀念。這樣的函數是無需計算，隻需觀察變元值就可判定的函數。零函數、後繼函數和投射函數，屬于這樣的本原函數。

第二，原始遞歸函數是使用上述本原函數，用遞歸方式或者複合方式而生成。

第三，這樣的遞歸函數都是有窮的生成序列，它有起始點，也有終點。

這個标号（2），大概就隻能說這麼多。

2、标号（3）與（4），引入對應表達定理

哥德爾的原始遞歸定義，帶來了有關遞歸函數的四個可證命題，随後就是密集的46個定義。從第43頁出發，跨過這些命題和定義，到達哥德爾原著英譯本的第51頁，那就是命題5。這個命題5，就是在前連接配接标号（1）與（2），在後連接配接哥德爾第一不完全性定理的對應表達定理。這個對應表達定理告訴我們，每一個原始遞歸關系的序列都對應着一個n元關系符号，如命題5所示：

對于每一個遞歸關系R(x1,…,xn)，都對應地存在一個n元關系符号r，r帶有自由變元μ1,μ2,…μn,使得對于每一個n元組數字(x1,…,xn)，以下表達式成立：

R(x1,…,xn)→provable(subst(r,u1,…,un,number(x1)…(xn))) 标号（3）

R(x1,…,xn)→provable(not(subst(r,u1,…,un,number(x1)…(xn)))) 标号（4）

在标号（1）中用到的符号R，在命題5中再次出現了，依然表示的是關系。在标号（1）相關PM的公式中，那裡的Rn是一進制關系，不可證面對的隻是一進制關系。标号（3）和（4）則面對的是n元關系，自然包括了一進制。

這裡似乎可以簡單評論一下關系和函數了，這兩個觀念的确很結緣。你有時會覺得它們簡直沒有什麼不同。說一個客體是n元函數，和說這些客體是n元關系，似乎完全是一回事情。但其間的差異還是有些明顯的，它們并不是同義詞。說遞歸是一個函數，和說遞歸是一種關系，大概可以這樣來差別。當我們說一個客體是函數的時候，關注的是函數參數之間的變換。而當我們說一個客體是關系的時候，關注的則是參數的多少，還有參數間各種不同的特指關系。就此而言，關系似乎比函數更為抽象。

好了，現在回到标号（3）和标号（4）中來。标号（1）給出了不可證的類理查德悖論的命題Rn(n)，标号（2）給出原始遞歸函數的定義，我們現在看到了它們的整合。一進制關系R升格為n元關系，不可證命題現在成為可證的命題，隻是标号（1）中的等價，成了單向的蘊涵式。而且，不僅是肯定式可證，否定式同樣也是可證。這樣的結論，在2000年哥德爾原著英譯本中冠以“可表達性和可證性”。

可證性已經做了簡要說明，但這個标号（3）和（4）更重要的意義是其可表達性。哥德爾的這個标号（3）（4），實際上是哥德爾的又一個發現。那就是：帶有若幹自由變元的n元遞歸關系R，總存在對應的在PM中的形式證明。如果是肯定的R關系，則一定有一個證明序列成立。如果是否定的關系R，則一定有否定的證明序列成立。這其實等于是在說：一個具有n元遞歸關系的R表達式，它一定有肯定證明序列的表達式與之對應。而一個具有否定的n元遞歸關系R的表達式，它一定有否定證明序列的表達式與之對應。這樣一種特性，稱之為n元遞歸關系R在PM中強可表達，而如果去掉否定式，則是弱可表達。

回顧完标号（1），（2），（3），（4），我們該接上命題6的标号（5），進入到哥德爾原著論文的核心，開始賞鑒哥德爾著名的第一不完全性定理了。

且留待下篇。