第一不完全性定理证明标号分类 拆解汉译 知识背景——哥德尔原著英译拆解汉译之一

哥德尔原著中的第一不完全性定理证明的全过程，已经艰难地旅行了一趟。不是浮光掠影，却依然处在似懂非懂之中。静坐沉思，常自叹功力甚浅，未能力透纸背，了悟哥德尔符号玄机也。

刚刚学到两个对待知识态度的英文单词。一个是know-it-all，中文翻译为无所不知，另一个是learn-it-all，中文翻译为无所不学。我们这个社会好像有不少know-it-all即无所不知的人和团体，所有人，所有团体都得听它的，因为它无所不知。好在还有一个正好与这个无所不知对应的无所不学，它恰恰是无所不知的反面。我们总有学不完的知识，我们应该用一种谦恭包容的态度对待人类的知识，用虔诚的学习态度来对待这人世间的一切存在。

无所不知图

上帝无所不知

无所不学

一个智慧的存在，谦恭的学习态度应该为第一要义。你准备去学习某种东西，除非不可抗拒的因素在给你困扰，不然，浅度漂学解惑不了，就不可不懂装懂，自以为无所不知。倒应该是提升强度，如同旅行中的普通游升华为深度游那样。在粗读哥德尔原著一轮之际，好像来了点这样的感觉，感觉非增加点深度游览，才有可能窥见哥德尔文字之奥妙，或者练出点功力，能够察知哥德尔符号之瑕疵。

于是，那计算机指令中经常用到的循环迭代，就起了一点启示作用。也许，这循环迭代产生的熟，继而生发出的灵性，能够映衬出孔老夫子的那句千古名言：温故而知新的。

由此，哥德尔原著英译本的迭代阅读就这样开始了，因为有第一轮的打底，可以先对哥德尔第一不完全性定理的证明流程，做一个概要性的描述了。

一、哥德尔第一定理证明流程分类

好几本哥德尔参考读物，都是从哥德尔定理的大背景角度来概括哥德尔证明的。我的第一着眼点没有大背景，仅在哥德尔原著本身。先对哥德尔证明第一不完全性定理给出的16个标号，给出分类的描述。然后看有不有可能，捣鼓出哥德尔证明的一个路线图。

（一）18个标号与4个分类

哥德尔证明第一不完全性定理中的16个标号，再加上标号（6）之下的（6.1），标号（8）之下的（8.1），总共18个标号。按其符号性质分类，大致可以分为以下几类：

第一类：六个定义

1.标号（1）自然数类K定义

K=｛n∈N ▏￢proveable(Rn(n)｝    （1）

2.标号（2）原始递归定义

这是与哥德尔形式系统P无直接联系的递归定义

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

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

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

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

3.标号（5）证明序列定义

       递归ω一致条件下公式类k，一公式x可证定义，类似于哥德尔文本中提及的概念，也就是哥德尔46个定义中的定义44

isProofFigurek(x)<=>(n(n≤length(x))→(isAxiom(x)(term(n,x))∨term(n,x)∈k))∨((p,q)(0<p∧q<n)∧(Conseq(term(n,x)∧term(p,x)∧term(q,x)))∧length(x)>0    (5)

这个定义标号为（5），意在说明一个在ω一致条件下，证明序列是什么样的客体对象。

4.标号（6）证明定义

递归一致条件下公式类k，一公式y是x证明序列的定义，同样类似于哥德尔文本中提及的概念，也就是哥德尔46个定义中的定义45

proofFormulak(x,y)<=(isprooFiguresk(x))∧(term(length(x),x)=y))      (6)

5.标号（6.1）可证定义

递归一致条件下公式类k，一公式x可证明的定义，也类似于哥德尔文本中提及的概念，也就是哥德尔46个定义中的定义46的类似定义，一个不是原始递归关系的定义。

provablek(x) <=>((y)(proofFormulak(y,x))       (6.1)

6.标号（8.1）二元关系定义

Q(x,y) <=>￢proofFormulak(x,subst(y,19,number(y)))         (8.1)

第二类：两个命题

1.标号（3）肯定对应定理1

R(x1,x2,…,xn) =>provable(subst(r,u1,…,un,number(x1)…number(xn)))          (3)

2.标号（4）否定对应定理2

￢R(x1,x2,…,xn) =>provable(not(subst(r,u1,…,un,number(x1)…number(xn))))     (4)

第三类：两个假定

1.标号（11）带有一个自由变元的类符号p

p =forall(17,q)          （11）

2.标号（12）带有一个自由变元的类符号r

r = subst(q,19,number(p))      （12）

第四类：八个导出命题

1.标号（7）全称等价公式

x（provablek(x) <=>x∈Conseq(k)）       (7)

2.标号（8）全称蕴涵公式

x（provable(x) =>provablek(x)）       (8)

3.标号（9）运用对应定理获得的否定证明序列蕴涵式1

(￢(proofFormulak(x,subst(y,19,number(y))) =>

(provablek(subst(q,(17,19,number(x),number(y)))   （9）

4.标号（10）运用对应定理获得的肯定证明序列蕴涵式2

((proofFormulak(x,subst(y,19,number(y))) =>

(provablek(not(subst(q,(17,19,number(x),number(y))))   （10）

5.标号（13）对类符号p使用代入运算获得的连续等式

subst(p,19,number(p))=subst(forall(17,q),19,number(p))

=forall(17,subst(q,19,number(p)))

=forall(17,r)                   （13）

6.标号（14）对二元符号q使用代入运算获得的等式

subst(q,17 19,number(x)number(p))=subst(r,17,number(x))       （14）

7.标号（15）否定的证明序列蕴涵式3

(￢(proofFormulak(x,forall(17,r)) =>(provablek(subst(r,17,number(x)))   （15）

8.标号（16）肯定的证明序列蕴涵式4

(proofFormulak(x,forall(17,r)) =>(provablek(not(subst(r,17,number(x)))))   （16）

（二）最后导出两个不可证结论，获得不可判定命题forall(17,r)

       由以上标号导出以下两种结果：

1.forall(17,r)不是k可证。

2. not(forall(17,r))也不是k可证， 

       由此，forall(17,r)在k中不可判定，命题VI得到证明。

       以上哥德尔给出的这18个标号，我按性质给予了分类。但在原文中，则是按标号顺序列出的。为了对哥德尔的思路有更好的了解，以下给出哥德尔原著2000年英译本的汉译。分类之后做拆解汉译，这拆解汉译所翻译的内容，仅汉译出其中的标号部分和标号部分的联结语，包括英译者的评注。汉译中的英译者评注为英译本中原已附带的，汉译评注则是我另外给出的。

二、按照哥德尔18个标号顺序的原著2000英译本部分汉译

       以上标号分类，来自哥德尔原著英译本中部分译文，我在这里将英译本再做一次中文转译。黑体字是从英文转为汉语的哥德尔原著，其中使用方括号的文字为英译者评注，非黑体字的汉译评注，则略略解读与联结这些原著英译文字。

       在哥德尔原著英译文本导言的第4段，哥德尔在给出他简洁的证明直观之后，很快就进入主题，构造了一个在PM中的不可判定命题。请注意，这里是给定PM中的不可判定命题，然后才开始构建哥德尔自己的系统P。

       再次提醒注意，以下拆解汉译形成的中文文字，黑体字是哥德尔原著英译的汉译，非黑体字则是我给出的评注和联结语。

（一）拆解汉译（1）（2）（3）（4）

       我们开始哥德尔原著英译文本的第一段汉译，从原著的标号（1）起步。

       我们现在将构造一个系统PM的不可判定命题，那就是，它是如下给出的一个定理A，对于该定理A而言，既不是A可证，也不是￢A可证。

       我们将把仅带有一个自由变元，该自由变元的类型为自然数的PM公式，称作类符号（class-sign）。我们将假定这些类符号可用某种方式按顺序编排，我们将把第n个顺序编排的类符号，称作Rn。请注意，概念“类符号”和序关系R都在系统PM内可定义。设α为任意类符号，我们用α(n)表示用n代入α中自由变元而形成的公式。再假定，三元关系x<=>y(z)也在PM中是可定义的。现在，我们就定义一个自然数的类K如下：

K=｛n∈N ▏ ￢proveable(Rn(n)｝    （1）

       汉译评注：标号（1）中Rn(n)的表示恐有误，应该是Rnn或者R(n);n为好，我暂按原本不变。标号（1）之后的标号（2），则是数页之后出现的原始递归定义。这个原始递归函数的定义，是在哥德尔构造了一个不同于PM的系统P后给出的。所以，我们从标号（1）出发，进入到标号（2）的时候，所面对的形式系统就不是PM而是P了。有意思的是，这个标号（2）的定义，虽然位于构造了不同于PM的系统P之后，却是哥德尔跳出P之后而定义的。哥德尔似乎特别地指出了这一点，他是跳出P之外做的一个短暂的旅行，而且，这个原始递归概念几乎和P没有任何关系。

       我们来看哥德尔的标号（2）

       拆解汉译：

       此刻，我将跳出P之外做一个短暂的旅行，以形成一个和P几乎没有任何关联的观察结果。首先给出的是以下定义：我们说一个数论公式Φ(x1,x2,…,xn)被定义，那是根据数论公式Ψ(x1,x2,…,xn-1)和μ(x1,x2,…,xn+1)而递归定义的，如果对于所有的x1,x2,…,xn，k，以下等式成立：

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

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

       汉译评注：哥德尔给递归所做的这个定义客体，现在称为原始递归函数。由这个原始递归函数，又引申出一些相关于原始递归函数的定理。因而接之立刻就列出了，具有原始递归性质的45个定义。在定义45之后，再列出一个不是原始递归性质的定义46。跳过非原始递归函数的第46个定义，这一次穿越原著文本好几个页码，哥德尔定理证明中的第3个标号登场了，紧接着，第4个标号也登场了。这两个标号，就是著名的可表达性定理V，而这个登场亮相完毕之后，我们又从P之外回到了p之中。需要注意的是，这个可表达性定理V的排序，是哥德尔定义原始递归函数概念之后系列定理的排序。它给出了哥德尔另一类定理序列，在原始递归函数定义之后，先有原始递归函数的四个定理。依据这些定理，我们就有随后出现的46个定义。在46个定义之后，再出现展示递归关系和可证性观念之间对应的对应定理V。

       拆解汉译（3）与（4）：

       每一个原始递归关系在系统P内可定义这个事实（也就是按照其内容来解释P）,将用以下定理来表达。

定理 V（5）：每一个原始递归关系R(x1,x2,…,xn)都存在一个关系符号r（带有自由变元u1,…,un,）使得对于每一个n元组符号(x1，…xn)，有以下公式成立：

R(x1,x2,…,xn) =>provable(subst(r,u1,…,un,number(x1)…number(xn)))          (3)

￢R(x1,x2,…,xn) =>provable(not(subst(r,u1,…,un,number(x1)…number(xn))))     (4)

（二）拆解汉译从标号（5）到标号（16）

       汉译评注：有了以上4个标号之后，哥德尔命题VI（6）的证明正式上了轨道，从标号（5）到标号（16）一气呵成，完成了第一不完全性定理的全部证明流程，也就是完成了哥德尔原著的目标。为了实现这个目标，哥德尔还需要一个观念，这就是他为系统P新增的一个一致性观念，数论中的一致性。我们的拆解汉译，也就从哥德尔界定的一致性开始。这里也有一个关注点，哥德尔的定理序列，到标号（4）为止，已经编排了5个定理。哥德尔第一不完全性定理，原著文本最为出彩的定理，就是他编排的定理VI（6）。

       现在，我们来到那个详述本文目标的地方了。设k是任意公式类。我们用Conseq(q)表示含有所有k的公式，所有k的公理，并且在直接后承关系下封闭的最小公式集合。k被称为ω一致，如果没有类符号α使得

(n. subst(α,v,number(n))Conseq(k)not(forall(v,α))Conseq(k)

       其中，v是类符号α的自由变元【英译者评注：换句话说，对抗一致性的反证将会是一个带有一个自由变元的公式α，这个公式α，我们可以对所有n，导出一个α(n)来。我们也可以用这个公式α，但我们同样也可以，并非对于所有的n，导出一个α(n)，这是一个矛盾。】

当然，每一个ω一致性系统也是一致的。然而反过来并不成立，如同后面将会证明的那样。【英译者评注：我们称一个系统是一致的，如果没有公式α使得α和￢α都可证。这样一个公式是一致性的反例，但这样一个公式一般而言不是ω一致的反例。换句话说，ω一致比一致性强，前者蕴涵着后者，但反过来却不是。】

有关不可判定命题存在的一般性结果表述如下：

命题VI（6）：

对于每一个ω一致性的原始递归类公式k，都存在一个原始递归类符号r，使得无论是对于所有的v,r,即forall（v,r），还是对于并非所有的v,r，即not(forall(v,r))，它们都不属于Conseq(k)。（其中，v是r的自由变元）。

【英译者评注：因为定理中的前提是ω一致性，它强于一致性，所以该定理若与其假定前提仅仅是一致性的同样定理相比较，就具有更少的普遍性】

证明：设K是任意ω一致的原始递归公式类。我们定义：

isProofFigurek(x)<=>(n(n≤length(x))→(isAxiom(x)(term(n,x))∨term(n,x)∈k))∨((p,q)(0<p∧q<n)∧(Conseq(term(n,x)∧term(p,x)∧term(q,x)))∧length(x)>0    (5)

(这个标号可以与类似的定义44相比较)

proofFormulak(x,y)<=>(isprooFiguresk(x))∧(term(length(x),x)=y))      (6)

provablek(x) <=>((y)(proofFormulak(y,x))       (6.1)

(这个标号可以与类似的定义45，定义46相比较)

       以下两个标号公式明显成立：

x（provablek(x) \Leftrightarrowx∈Conseq(k)）       (7)

x（provable(x) \Rightarrowprovablek(x)）       (8)

现在，我们定义以下关系：

Q(x,y) <=>￢proofFormulak(x,subst(y,19,number(y)))         (8.1)

       【英译者评注：直观上Q(x,y)意味着x并不证明y(y)】

        因为，（依据标号（6）和（5）），proofFormulak(x,y)是原始递归的；（再依据定义17和31），subst(y,19,number(y))同样原始递归的，所以Q(x,y)也是原始递归的。而依据定理V，我们因此而有关系符号q（带有自由变元17和19）使得以下公式成立：

(￢(proofFormulak(x,subst(y,19,number(y))) =>

(provablek(subst(q,(17,19,number(x),number(y)))   （9）

((proofFormulak(x,subst(y,19,number(y))) =>

(provablek(not(subst(q,(17,19,number(x),number(y))))   （10）

       我们设：

p =forall(17,q)          （11）

       （p是带有自由变元19的类符号【英译者评注：它直观上意味着19（19），也就是y(y)，是不可证的】）和

r = subst(q,19,number(p))      （12）

（r是一个带有自由变元17的原始递归类符号【英译者评注：它直观上意味着17，也就是，也就是x并不证明p(p)，这里的p(p)意味着是不可证的】）

       由此，以下公式也成立：

subst(p,19,number(p))=subst(forall(17,q),19,number(p))

=forall(17,subst(q,19,number(p)))

=forall(17,r)                   （13）

（因为（11）和（12））；进一步就有：

subst(q,17 19,number(x)number(p))=subst(r,17,number(x))       （14）

（因为（14）），【英译者评注：这个递归的forall(17,r)可以解释为它对p(p)没有证明，换句话说，forall(17,r)陈述了：陈述自身不可证的命题p(p)是不可证的】。如果我们现在在标号（9）与（10）中对y代入p，再使用标号（13）和（14），那就可以得到：

(￢(proofFormulak(x,forall(17,r)) =>(provablek(subst(r,17,number(x)))   （15）

(proofFormulak(x,forall(17,r)) => (provablek(not(subst(r,17,number(x)))))   （16）

（三）哥德尔第一不完全性定理得到证明

       汉译评注：由以上18个标号的公式序列，导出以下两个结论。一个结论是否定的可证，另一个结论是否定的不可证。也就是说，我们既不能证明公式forall(17,r)可证，也不能证明公式forall(17,r)不可证。这恰恰就是一个公式在某个形式系统中不可判定的状态，也就是定理VI陈述中所表明的：对于每一个一致性的原始递归类公式k，都存在一个原始递归类符号r，使得无论是对于所有的v,r,即forall（v,r），还是对于并非所有的v,r，即not(forall(v,r))，它们都不属于Conseq(k)。（其中，v是r的自由变元）。

       这里的都不属于Conseq(k)，等价于在k中不可判定。

       由此而有了命题VI的证明。

       拆解哥德尔原著汉译就是以下黑体字陈述。

       这导致：

1.forall(17,r)不是k可证，因为，如果它可证，依据标号（6.1），就存在一个n使得

proofFormulak(n,forall(17,r))。而依据标号（16），又有：

(provablek(not(subst(r,17,number(n)))

       与此同时，另一个方面，从forall(17,r)是k可证，则会导致((subst(r,17,number(n))也是可证，这样k将会是不一致的（特别是不一致）。

2. not(forall(17,r))也不是k可证，正如以上证明过的，forall(17,r)不是k可证，那就是说，依据标号（6.1），以下公式成立：

n￢(proofFormulak(n,forall(17,r))。

       在2中出现的结果，再加上标号（15），又导致以下公式的成立

n(provablek(subst(r,17,number(n)))

       这个公式的成立和以下公式的成立，合在一起，与k的ω一致相冲突，

provablec(not(forall(17,r)))。

       因此，(forall(17,r))在k中不可判定，命题VI得到证明。

三、哥德尔定理证明，需要哪些知识背景？

       哥德尔原著英译本的拆解汉译，先译到这里。从这个简洁的证明流程中可以看到，哥德尔第一不完全性定理的证明，涉及到颇多不同的数学与逻辑观念。对这些观念予以梳理概括，逐渐去靠近解读哥德尔的思路，看来是一条有可能通达的途经。

       这个梳理毫无疑问，也主要依据哥德尔的原著英译本。让人感到欣慰的是，如今信息获取的便捷，有好几个译本可以互为参照。同时，如今的学术界，哥德尔似乎受到越来越多人的关注，业界提供了不少阐释哥德尔的读本，这些读物为弄明白哥德尔带来了期待。

       我在前的博客，大都已涉及到哥德尔原著中的一些知识背景。但既然是循环迭代，这循环迭代的功夫，那就干脆将其贯彻到底。且待我把这些理解哥德尔定理证明的背景知识列一个简略清单，本篇之后，按清单顺序一路迭代扫来。

       人类的知识，大概都因这样的循环迭代而得以流传和继承。

       人类的知识，大概也因这种循环迭代而带来的灵感和彻悟，才使得后来者的开拓与创新成为可能。

       于是我们就很容易理解，除非你是上帝，你才可能被拥戴为无所不知。而实际上，谁也不可能无所不知。

       于是我们就更容易理解，茫茫人世，学海无涯。我们最好是准备一个无所不学的心态，来应对这个知识不断累积不断爆炸的时代。如今的时代，连机器都在进行学习，何况具有智慧和灵性的人类物种。

       学海无涯，哥德尔的文本就是这个学海无涯的范例。短短几页的第一不完全性定理的证明，就含蕴着许许多多数学与逻辑中累积起来的知识。

       依据哥德尔第一不完全性定理证明的18个标号所示，至少应该有以下的知识背景清单，要作为循环迭代的备选对象。

1.罗素 怀特海《数学原理》一书中的PM系统

2.皮亚诺的算术系统PA

3.康托的对角线论证与对角线方法

4.理查德悖论与罗素悖论

5.原始递归谓词、关系与函数

6.哥德尔配数与哥德尔编码

7.可表达与可证之间的对应原理

8.元数学的一致性观念

9.集合运算与逻辑运算

10.元数学的算术化

       暂列以上10项，仅这些内容就够折腾人的了。经历这个实在的世界几十年，我们所面对的有形的物质的世界，好像已经给人多多审视疲劳的感觉，你好像无力参与，似乎任何一点涉猎的兴趣，都因为人世间的险恶而被阻断。唯有符号的缥缈的世界，却依旧在展现它的魅力。无论是自然语言的符号还是人工语言的符号，无论是这些符号外显的意蕴，或者潜藏的意蕴，都在诱惑人的精魂和智慧去着力参与。即使常常遇到困惑和阻隔，你在犹豫徘徊之后，不经意间又走进的，还是这些符号的世界。

       迭代既然从这里开启，那就期待它的延续吧。