哥德尔第一不完全性定理  悖论式陈述 PM不可判定命题，和哥德尔可表达性定理——哥德尔读后之十八

开始命题六，也就是哥德尔第一不完全性定理的阅读了，但似乎离这个著名定理，还有那么一丁点的距离。于是本篇依然是交代命题6证明前的那些必不可少的证明铺垫。

一、哥德尔命题6，即第一不完全性定理的两个版本表达

在预设了c为任意公式类及其相关条件，并且给出w一致性观念之后，命题6（VI）即对后世影响深远的哥德尔第一不完全性定理出场了。

（依据1962年英译本）

这个有关不可判定命题存在的一般性结果读作命题6：

命题6：

对于每一个w一致性的递归类公式c，都存在对应的递归类符号r，使得无论是对于v一般化r还是对于并非v一般化r，它们都不属于Flg(c)。其中，v是r的自由变元。（（这里的一般化是德语缩写Gen，v一般化r的符号在1962英译本中表示为v Gen r。并非v 一般化 r，则表示为Neg（v Gen r）。而这里的后承集合是德语缩写Flg，后承集合c在1962英译本中表示为Flg(c)，请注意字体的不同。））

（而依据2000年英译本）

这个有关不可判定命题存在的一般性结果展示如下：

命题6：

对于每一个w一致性的原始递归类公式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没有直接联系，但贯穿哥德尔论文全篇的一个定义。这就是对于数论函数的原始递归定义，也是递归论历史上创建的最早一个定义（参见郝兆宽等著《递归论》引言部分）。

一个数论函数Φ(x₁,x,…,x_n)被说成是根据数论函数Ψ(x₁,x,…,x_n-1)和μ(x₁,x,…,x_n+1)而递归定义的，如果对于所有的x₁,x,…,x_n，k,以下等式成立：

Φ(0,x₁,x,…,x_n)= Ψ(x₁,x,…,x_n),

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

哥德尔给递归所做的这个定义客体，现在称为原始递归函数。

函数观念几乎就是数学之命根，也是逻辑之命根。离开了函数观念，想去讨论逻辑和数学，几乎连数学与逻辑的门都进不了。当年柏拉图在他的学园门口高挂起的牌匾“不懂几何学者不得入内”，用在今天，应该是“不懂函数观念的人不得入内”了。我桌上摆着一本刚刚去世的齐民友先生的著作，厚厚的《重温微积分》。齐先生讨论微积分，书中的头两章都是在漫议函数。第一章以变量的科学为题，第二章干脆就是函数。而克林先生的《元数学导论》和莫绍奎先生的《递归论》，则几乎通篇都是函数。在先的博文中，我曾经用过莫先生关于函数的一个通俗定义：函数便是把一些数变成另一个数的运算。更严格一点，函数不是指的运算过程，而是指运算所根据的规则（参见莫绍揆《递归论》第15页）。对函数的这样一种运算过程和运算规则的理解，我们就有了元数学的视角了。

回到哥德尔的著作上来，那么，我们该如何理解哥德尔的原始递归函数呢？

第一，有本原函数，也称初始函数的观念。这样的函数是无需计算，只需观察变元值就可判定的函数。零函数、后继函数和投射函数，属于这样的本原函数。

第二，原始递归函数是使用上述本原函数，用递归方式或者复合方式而生成。

第三，这样的递归函数都是有穷的生成序列，它有起始点，也有终点。

这个标号（2），大概就只能说这么多。

2、标号（3）与（4），引入对应表达定理

哥德尔的原始递归定义，带来了有关递归函数的四个可证命题，随后就是密集的46个定义。从第43页出发，跨过这些命题和定义，到达哥德尔原著英译本的第51页，那就是命题5。这个命题5，就是在前连接标号（1）与（2），在后连接哥德尔第一不完全性定理的对应表达定理。这个对应表达定理告诉我们，每一个原始递归关系的序列都对应着一个n元关系符号，如命题5所示：

对于每一个递归关系R(x₁,…,x_n)，都对应地存在一个n元关系符号r，r带有自由变元μ₁,μ₂,…μ_n,使得对于每一个n元组数字(x₁,…,x_n)，以下表达式成立：

R(x₁,…,x_n)→provable(subst(r,u₁,…,u_n,number(x₁)…(x_n))) 标号（3）

ØR(x₁,…,x_n)→provable(not(subst(r,u₁,…,u_n,number(x₁)…(x_n)))) 标号（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），进入到哥德尔原著论文的核心，开始赏鉴哥德尔著名的第一不完全性定理了。

且留待下篇。