哥德尔不完全性定理 关系 谓词和代入——哥德尔读后之二十

这两天从外刊文字中了解到，人工智能AI很牛，不是一般地牛，很可能超越人的智能。但有一个事实，却不是能够轻易就被否定掉的。那就是，所谓现代机器人，包括可以自动驾驶的汽车，它们应该是人工智能的典型代表，其实际智能可能还没有超过一个七个月的婴儿。这个智能测试直观简洁，似乎只涉及到一个基本的哲学观念：存在。

婴儿的照片

自动驾驶汽车

一个使用玩具的七个月婴儿，当把玩具放在他旁边的毯子之下时，婴儿可以从毯子下面找到玩具，他知道玩具虽然看不见，但玩具依然存在。但一个自动驾驶汽车则似乎没有这样的智能，它可以自动避开阻挡在前的东西，但如果一物被另一物完全挡住，自动汽车的感应功能感应不到，那么，它就完全不知道这个被挡物的存在。人类关于存在的感知，那是人工智能恐怕很长时间都是无法具备的。笛卡尔那句著名的格言：我思故我在，机器人因为几乎没有思，它关于存在的观念自然就是空白。

其实，不仅存在观念，我们人类有关知识的许多观念，那都是人的自然智能所特有的。人工智能要能感受到这类抽象观念，一定还有很长的路要走。哥德尔在其原创性论文中的许多抽象观念，本篇论文将涉及到的关系、谓词还有性质、代入这类概念，大概永远也进不了AI人工智能的法眼。

一、标号（8.1）的关系概念，兼及谓词概念和性质概念

不可判定和证明有着天然的联系，但要理解这个不可判定，还有一些重要的元数学概念你无法规避。这些概念在开始证明命题6之前就有了一些交代，深入到命题6的证明环节，这些概念又走进哥德尔的视野。相关于“证明“的概念有了以上8个标号的铺垫之后，关系概念作为比证明更为抽象的客体，再一次出现了。

在标号（8）之下继而有标号（8.1），那是哥德尔又定义出来的一个概念，他称之为关系。哥德尔的关系概念没有涉及可证，它仅和”证明公式”相关联，请看以下的（8.1）。

Q(x,y)≡Ø(proofFormula_c(x,subst(y,19,number(y)))      (8.1)

这个定义标号为（8.1），哥德尔意图说明x与y之间的关系。在说明关系的时候，证明公式参合进来了，哥德尔数也加入进来。为什么哥德尔在这里，要把很容易与函数混淆的关系概念放在命题6的证明过程中呢？在标号（8.1）解读之前，先回看哥德尔在前对关系的表述，大概会找到些感觉。

（一）关系的一般描述

不可判定虽然和证明有着天然的联系，但要理解这个不可判定，还有一些重要的元数学概念你无法规避。那些相关‘’证明‘’的概念有了以上的铺垫之后，又来了一个抽象观念，那就是关系概念，它作为证明的一个必涉观念，再一次出现在读者面前，这就是标号（8.1）定义的关系Q。

塔尔斯基在谈到关系概念时说：关系的理论是逻辑中一个专门的而且非常重要的部分，关系理论研究带有完全任意性质的关系。（参见塔尔斯基《逻辑与演绎科学方法论导论》第84页）。塔尔斯基这个评述似乎告诉我们，对关系概念的理解是在完全任意性质的视野下进行的。就此而言，关系是比函数更为宽泛和抽象的概念，关系应该是函数的型，而函数则可能是关系的例。所以塔尔斯基在随后讨论函数时，说函数是另一类特别重要的关系。

标号（8.1），似乎是在定义一种塔尔斯基意义上的一般二元关系relation，也就是关系Q(x,y)。在解读这个（8.1）之前，回顾一下哥德尔在其论文中对于关系的几处描述，还是有点意思的。

（二）一元关系和多元关系

第一处：一元关系R(n)

哥德尔说：

仅带有一个自由变元的PM公式，并且属于自然数类型中的类的类，我们将其称之为类符号class-sign。同时，这样的公式所对应的类符号，我们将其看作是在一个序列中可按顺序编号的，由此，我们可以用R(n)指称该序列中的第n个字符。我们注意到，这个类符号和序偶关系R，在PM中就是可以定义的。……，三词项关系x=y(z)，在PM中也是可以定义的。

以上的黑体字来自哥德尔的论述，用R(n)指称该序列中的第n个字符，这个R(n)为什么是一种序偶关系呢？这里可以对这个序偶关系做一点想象。一个有限序列S，它从左到右排开，表达一个类符号，也称之为PM的一个仅带一个自由变元的公式。设这个S的长度为v，这个v长度实际上就是一个一个的个体构成的类，由此，v作为长度在逻辑上就等于是一个自由变元。在v中的任意一个个体，它没有客体来构成多元关系，它只是具有某个性质或者属性的有限个体中的一个。这样的关系，自然就是一元函数的关系。所以，哥德尔在这里提及的序偶关系，可以理解为给v长度的序列，按照顺序对应于v中某个自然数的关系。由此，这个v长度的S，其第n个位置的那个个体，是用另一个符号取代自由变元而获得的结果。当用另一个符号替换自由变元形成新公式时，这个新公式就称作命题公式。哥德尔标号（1）中的公式R(q)，就是这么样得到的。R作为一元关系，其实也可以看作是个体客体q的某个性质，这在后面还会有讨论。

第二处：多元关系作为基本符号是多余的

在对第一类型符号的论述中，哥德尔如同上述第一处的关系论述一样，提醒读者注意：他这里的函数和关系是不做区分的等义概念。

表述二词项和多词项的函数（关系）作为基本符号是多余的，哥德尔在函数之后用了一个括弧注释，括弧内就是词项：关系（relation）。显然，这里的函数和关系就是不加区分的等义词，函数就是关系。为什么多余呢？哥德尔直接使用关系词项来予以解释。

因为关系可以定义为序偶类，序偶类又可以作为类的类，例如，被(a,(a,b))表述的序偶(a，b)，其中(x,y)意味着这个类仅有的元素是x和y，(x)则表示这个类，仅有一个元素x。（参见张寅生《证明方法与理论》第287-288页）

哥德尔对于关系的这种表述，关系显然超越函数的范围，在很多时候，函数就是关系中的一种。除了在第一类型符号论述中提到关系，接下来，哥德尔又有第三处谈到关系的文字。

第三处：以变元数量来确定关系类别

在第二章的基本符号描述部分，哥德尔说：一个仅带有n个自由变元的公式（没有其他自由变元）为n元关系符号，若n=1，这个符号也称为类符号。

这里的关系，显然指称若干客体之间的一般关系，由自由变元来代表的类与类之间的关系。n个类之间关系的研究，如塔尔斯基所言，形成数理逻辑高度发展的关系理论。而其中的一元关系，它只有一个变元，颇类似亚里士多德三段论的直言命题，某个类成为命题的主词，关系则成为命题的谓词。哥德尔为原始递归函数所做的定义，就是一个主谓句。这就把我们导向了哥德尔第四处讨论关系的地方，讨论的是原始递归关系。

（三）关系、谓词和性质

第四处：

哥德尔说：

自然数之间的关系R(x₁…..x_n)称作递归的，如果存在递归函数Φ(x₁…..x_n)使得对于所有的(x₁…..x_n)，有如下等价式：

R(x₁…..x_n) ≡ (Φ(x₁…..x_n)=0)

这个表述告诉我们，何为递归关系呢？递归关系中的这个关系，是作为一个一般性的关系来使用的。这里的关系，更为严格的称呼应该称为谓词，我们前面提到的亚里士多德意义上的谓词。关系范畴就包括了谓词这个词项的基本意义，因此可以替代式的使用。当一个函数关系的表达式R(x₁…..x_n) ，只以0或者1作为其值域，这样的关系表达式就是谓词。哥德尔定义的是原始递归关系，也就是原始递归谓词。这个定义表明，当R(x₁…..x_n)为1时，用通俗的表述，也就是为真时，原始递归函数(Φ(x₁…..x_n)=0)，或者说它为假，则R(x₁…..x_n)为原始递归关系，更严格的表述就是原始递归谓词。

而当这个谓词的变元只有一个的时候，这就是所谓的一元关系，也称作一元谓词。这时候的谓词，实际上表达了主项的性质。亚里士多德的经典定义理论公式：属+种差，其中的属和种，其实就相当于哥德尔论文中的类，种差中的那个差则相当于性质。哥德尔的46个定义之中，属于一元谓词，即表达主词性质的定义有很多，譬如定义44和定义46就是含有一个变量的表达式，自然也是表达主词性质的表达式。

对于关系、谓词和性质的简单评述，有助于标号（8.1）的解读

二、变元类型 代入和标号（8.1）解读

标号（8.1）是这样的定义式：

Q(x,y)≡Ø(proofFormula_c(x,subst(y,19,number(y)))

依据哥德尔给出的原始递归关系，即原始递归谓词的定义，（8.1）左式是一个二变元的原始递归谓词。有变元x和y，而x和y之间是这样的关系：x不是(subst(y,19,number(y)))的证明公式。

这个以subst开头，含有变元y的表达式，其中有哥德尔数19。哥德尔为基本符号规定的哥德尔数已经有1-13的自然数，这些自然数对应第一类符号，称为哥德尔P系统中的基本符号（basic-sign）。那么，如果有更多的基本符号需要自然数对应的话，该如何对应哥德尔数呢？这一点，哥德尔已经预先想到了。在做了7个常元符号的数字对应配置之后，哥德尔接着说：

进一步，类型n的变元被给定形式为pⁿ的自然数（其中，p是一个大于13的素数）。

这就涉及到符号中的变元类型的界定了，也就是说，我们从常元哥德尔数的配置，到达了对于各种类型变元哥德尔数的配置。这个配置首先确定变元类型，于是我们就有了变元类型的定义，这个定义的起点从第一类型开始。什么是第一类型变元呢？当变元作为一个类，其个体是自然数，包括数字0的时候，它被称之为数字符号的类型（number-sign），这类变元类型也就是第一类型变元。由此外推，如果n>1，变元类型就以n值所取而判定为第n个类型的变元符号，表达第n个类型的符号，自然就是第n元类型符号。再表述得具体一点，第n个类型的个体，就只能是自然数的序列，或者序列的序列等等。

由此，初等公式概念在这里就出现了，当我们把不同类型符号跨级组合的时候，例如形式为a(b)的符号。其中b是第n类型符号，而a是第n+1类型符号。这两类符号组合成的符号序列，就是一个初等公式。这类初等公式，其实就是一个亚里士多德的主谓句形式，b具有a的性质，或者b属于a。

再来说明一下那个subst。这个subst是一个元数学符号，它表示把一个公式中的自由变元符号v代入为另一个与v同类型的符号，以标号（8.1）的右式为例：

Ø(proofFormula_c(x,subst(y,19,number(y)))

这里的19就是大于13的第二个素数，另一个素数是17，哥德尔留作与待建标号（9）中的基本符号number(x)相对应，19则与（8.1）中的基本符号number(y)相对应。这种数字指派称为哥德尔配数，简称哥德尔数。它被人们看做是哥德尔在其论文中给出的又一重大知识贡献，如同笛卡尔在几何图形和数字之间找到的对应一样伟大而奇特。这个话题，先暂且到此，留待下篇专论一下这个哥德尔数。

由此，x与y之间的关系Q，即Q(x,y)可以理解为这样的一个否定式，解读这个否定式之前，先分别说明一下各个基本符号。

特别要深入说明一下这里的subst，中文翻译为代入。注意，这里是代入substitution，不是替换replacement。

所谓在一项或者一个公式A中处处把变元x代入项t，这是指在A中，把x的每个自由出现都同时地换为t的出现。若用拼接记法来表述。设n为x在A中自由出现的次数（n≥0），则A可以写为A₀xA₁x…A_n-1xA_n。其中的(A₀，A₁,…,A_n-1,A_n)是不含x自由变元的部分，可能为空，而写出的全部x的n次出现都是自由的。这样，在A中把x代入t的结果，其中的x都变成了t，也就是A₀tA₁t…A_n-1tA_n。（参见克林《元数学导论》第79页）

克林对于代入的这个解释，正好就是对于哥德尔论述的解释，哥德尔对于他的代入是这样论述的：subst是一个元数学的运算符号，由此，一个标号（8.1）右式部分的代入式，(subst(y,19,number(y)))，其中的y代表一个公式，19代表一个变元，number(y)是如同19那样类型的数字符号。把代入运算置前，那就表示：在y中出现的自由变元19，如果没有自由变元，即变元为空，则y依然是y。如果y中有n个自由变元，则代入运算就把原先的公式y中的n个自由变元19，转换成了n个number(y)之后而形成的公式。

这就如同克林所言，x都变成了t。放在标号（8.1）的部分右式中，其中的number(y),如同哥德尔定义17所示，是对于作为数字y的数字符号。变元用数字19，也是遵照哥德尔已经给出的约定，如果是系统P中第一类型的基本符号或者第n类型的符号序列等等，这些类型的变元就一一对应了pⁿ数字。这里的p表示素数，上标n表示属于什么类型的数字。显然，n=1，则p就是那个素数自身。若n>1，则是该素数的n次方数。变元x在y之前，它自然是大于13的第一个素数17，随后有y，y对应的素数也就成为19。

于是，这个代入后形成的字符串，就可以理解为：变元y的哥德尔数对应到y自身的数位。直觉上看，那就如同哥德尔原著2000译本的注释所述，它成了公式y(y)。这个y(y)不正类似于PM版的(R(n),n))么？它在PM中不可证，类似地，在哥德尔的系统P中，同样是不可证。

由此，Q(x,y)是一个什么样的关系或者谓词呢？它表明：x与y之间是这样一种原始递归关系或者原始递归谓词，x不是公式y在y中变元中代入数位数字所形成的公式的证明。如果简单地表述，那就是：x不能够证明y(y)。这个结果，简直就是哥德尔第一章中，得出PM中不能够证明(R(n),n))的进化版。当然，必须是在那个证明公式即proofFormula的下标c的条件之下。

三、标号（9）与标号（10）的解读需要理解哥德尔数

还剩两个有关证明的标号，标号（9）和标号（10），这是两个关联度很高的标号。互为否定的两个蕴涵式前件，分别蕴涵着两个看似互相矛盾的后件。一个否定式前件表明两个变元代入后的结果”可证”，另一个肯定式前件则是这个结果的否定式也”可证“”。这一对互为交叉的否定肯定蕴涵式，是不是有点悖论式味道？

跟随哥德尔的论述。

依据标号（5）与（6）的定义，proofFormula_c(x,y)是递归的，而那个（8.1）中的代换式(x,subst(y,19,number(y))，可依据哥德尔定义17和31，它也是递归的。所以，Q(x,y)也是递归的。由此，继而依据哥德尔命题4和标号（8），就有一个关系符号q，它带有自由变元对应的哥德尔数17与19，使得以下标号（9）和标号（10）成立。

于是，我们看到，出现了两个哥德尔数，x配以13之后的第一个素数17，y配以13之后的第二个素数19。

先看标号（9）：

(Ø(proofFormula_c(x,subst(y,19,number(y)))→

(provable_c(subst(q,(17,19,number(x),number(y)))   标号（9）

这个公式为标号（9），它告诉读者，在Q(x,y)关系下，原始递归谓词”x不是相关条件下的证明公式”，这样的谓词该蕴涵着什么呢？

再看标号（10）

标号（10）的表达式：

((proofFormula_c(x,subst(y,19,number(y)))→

(provable_c(not(subst(q,(17,19,number(x),number(y))))   标号（10）

这个公式为标号（10），标号（9）为否定式的前件，标号（10）则为肯定式的前件，依据标号（8.1），标号（9）前件可以表达为Q(x,y)，标号（10）前件则可以表达为ØQ(x,y)。它们在一起表明：证明公式proofFormula和可证概念provable之间的两种蕴涵关系。

但是，这两个标号的解读都涉及到两个哥德尔数。我们在标号（8.1）的解读中已经暂时避开了哥德尔数的说明，似乎再也不能避开了。那么，在解读标号（9）和（10）之前，我们还是重温一下哥德尔创建的那个哥德尔数吧。

这自然需要留待下文。