康先生和哥德尔数配置——哥德尔读后之二十三

这一篇博客，该用来直击哥德尔数的配置了。哥德尔的系统P，词项是一个系统P中，符号构成的基底；由词项再构成公式；而由公式继而构成证明。行文之际，有幸看到陈波老友的中国逻辑学70年回顾（微信公众号“哲学社”2021年10月14日）一文，涵盖够周密的了，但感觉有关中国逻辑学界对于现代逻辑，特别是对于哥德尔的研究，有点概略不全，漏掉了康宏逵先生。康先生的其它译著姑且忽略不论，仅他对哥德尔所下的功夫，中国逻辑学70年中没有记录，实在是有点不公。
近一两年关注哥德尔，能参考的书籍很多，但对哥德尔理解之深，理解之早，对哥德尔的朋友王浩理解之深，交往之密，在中国逻辑学界，恐怕除了康先生，国内再无第二人。如同王浩所言，他们同是王宪钧的学生。也如同康先生所言，王浩是最爱护他最关心他的长者（参见康宏逵译，王浩著《哥德尔》前言第5页，及尾部第448页）。
康先生的哥德尔研究也确实了得，他1991年写成，于1993年出版的《可能世界的逻辑》一书，代序九十多页，就是专门讨论哥德尔的。我对哥德尔的理解，最先就是从这本书开始的。刚看时，一头雾水，不知所云。近来读哥德尔原著英译本，回头再来看康先生作为代序的《模态 自指和哥德尔定理》一文，好像找到点文字感觉。
康宏逵先生（1935-2014）

（来自《知乎》杜珊珊文前截图）

一、康先生配置法与哥德尔配置法的一致

（一）康先生如何解读哥德尔数配置？

哥德尔数的配置法则，虽在哥德尔原著中有论述，康先生给出的哥德尔数说明和配置公式，似乎比哥德尔原著更好理解一些。我所设想的词项、公式和证明的安排，其实就是重读康先生文本的结果。摘录康先生谈哥德尔数的片断论述，立刻就可以感觉到这样三个哥德尔数配置的客体。
康先生在代序中写道，哥德尔当年分两步来给出一元谓词Pr，这个Pr表示哥德尔系统P中的可证性谓词。获得可证性谓词Pr的第一步，那就是哥德尔编码，或者说给符号客体来配置哥德尔数。
这个第一步如何来做呢？康先生写道：
第一步：语法编码，简称编码 这一步在普通算术的一小片中进行，目的是先把可证性命题变换成普通算术命题。编码始于给PA（皮亚诺算术简称PA）中的语法对象各配一哥德尔数，旨在以数代物。配数法总有点任意，但必须一对一。怎么配都是要产生天文数字的，不如只设想按某种固定方法给每个符号配好数了。对i=0，1，……，n，如果符号si的数是ki，则符号序列s0s1……sn的数通常定为：

p0k0 * p1k1 * p2k2 *…… * pnkn，(*为算术相乘号)

这里的pi是按大小排列的第i个素数。相仿，如果符号序列ei的数是li，则符号序列的序列e0e1e2……en的数也可以定为:

p0l0 * p1l1 * p2l2 *…… * pnln，(*为算术相乘号)

这样，每个语法对象，特别是词项、公式和证明，就都对应于唯一的数了（参见康宏逵《可能世界的逻辑》上海译文出版社1993年版第5-6页）。
书籍截图

康先生的这段论述，其实就是对于哥德尔配数一种更为清晰的理解方式。未读哥德尔原文，这样的理解恐怕很难获得。有了康先生以上那几段配数论述，我们来看哥德尔本人对于哥德尔数配置的行文。
哥德尔在其论文第二章中，给出了常元符号的哥德尔数配置之后，接之就写道：

进一步，类型n的变元被给定形式为pn的数字（其中p是大于13的素数）。因此，对于每一个基本符号的有限序列（也是对于每一个公式），都有一一对应，也就是一一对应于一个自然数的有限序列。我们现在把这个自然数的序列，通过让数字2n1 * 3n2 *……*pknk使对应于序列n1，n2，……nk，（再次一一对应地）映射到自然数，其中p是第k个素数（按数量大小排序）。因此，一个自然数就一一对应地，不仅指派给了每一个基本符号，而且也指派给了这些符号的每一个有限序列（参见哥德尔原著1962年英译本第二章）。

哥德尔用n1，n2，……nk，表示序列，康先生则用s0s1……sn表示序列，这个序列其实有三种情形。一种情形是，由常元符号后继和0组成的数字个体序列，它们就是一个一个具体的数字。第二种情形是，由符号序列组成的公式，为形式系统所关注的，自然是合式公式。第三种情形是，由公式序列构成的序列的序列，这种序列的序列，为一个形式系统关注的，那就是所谓证明。说一个公式可证，无非是在说，这个公式有一个序列的序列为其提供了证明。于是，我们可以通过对于证明的分析，来理解哥德尔数的配置。
一个公式在系统P中可证，一定是有一个证明序列来提供证明。也就是说，这个证明序列末项恰好就是被证明的公式，末项之前的若干个公式，它们或者是公理，或者是依据在前命题推出的直接后承。于是从证明的分析，可以得到由公理和直接后承构成的序列中的各个公式。然后，我们再对公式进行分析，可以知道公式是用词项构成的。
使用康先生的语法编码，序列si表示的，是公式序列中的某个符号，而序列s0s1……sn作为整体表示的形式客体，则往往就是一个公式。
但要注意，康先生这里的序列s0s1……sn之间没有逗号，也没有运算符号，这是他有意而为之。序列s0s1……sn这种符号表示方法，实际上是在表述公式序列之间的符号拼接，哥德尔符号连接中的一种特殊运算。这个运算在哥德尔定义1-46中的定义8，哥德尔解释为“joining together”，康先生翻译为‘’拼接‘’有点传神。
且按康先生给出的这个语法编码，来分别给词项、公式和证明以哥德尔配数。这样做之前，先对康先生的论述做一些解读。

（二）解读康先生的符号表达

对于符号串的哥德尔数配置，我们先从表达词项的符号串开始，然后再看命题（即公式）变元，即公式变元的哥德尔数配置。
先来解读康先生有关哥德尔数配置的第一段符号串：
对i=0，1，……，n，如果符号si的数是ki，则符号序列s0s1……sn的数通常定为：

p0k0 * p1k1 * p2k2 *…… * pnkn，(*为算术相乘号)

这段符号串的含义可以简单解读为，我们有一个有限的从0到n的自然数，即i=0，1，……，n。符号si则表示某个符号序列s中，第i个位置的符号。这个符号序列的s，可以是常元的，也可以是变元的。或者说，可以是数字个体的，也可以是数字变元的，还可以是命题变元，谓词变元的。符号si的哥德尔数为ki，这里的ki，显然是数字序列k中的第i个数字。而s = s0s1……sn，这即是我们前面提到的s符号拼接运算的结果。那么，这个时候，该符号拼接序列s= s0s1……sn的哥德尔数就是以素数为底，以ki为幂的各个数字的乘积。那就是上面已经标示出的：

p0k0 * p1k1 * p2k2 *…… * pnkn，

这行乘积符号串有点复杂，乘积各项既带有上下标，上标中还另带有下标。这行符号串，是n个数字的一个乘积。即n个按从小到大顺序排列的素数p，从第一个素数p0到第n个素数pn。这些素数的幂，也是按照数字顺序排列的符号位置所配的哥德尔数。例如上标k0表示数字序列k中第一个位置上的哥德尔数，自然，上标k1则表示数字序列k中第二个位置符号上的哥德尔数，依此类推，一直到尾部素数的下标n。
依据这种符号串的表示法，我们可以配置哥德尔形式系统P中的任意词项，公式和公式序列的哥德尔数。

二、哥德尔数的配置

（一）常元和数字个体变元序列的哥德尔数配置

当我们为常元词项配置哥德尔数的时候，一个常元符号串就是一个符号序列s，s中的各个字符就分别是s0到sn。于是，依照上述康先生公式，符号k就是这个常元符号串的哥德尔数。K中的各个ki，自然就是对应于常元符号串各个位置符号的哥德尔数。而整个常元符号串的哥德尔数k，由此就成为以按大小顺序的素数为底，以符号串各个位置符号上的哥德尔数为幂的各个常元符号的乘积。
这可以用上篇给出的实例略加复述，以下图表表明，这个过程是一一对应的。可以以常元符号串为起点，获得它的哥德尔数。也可以从它的哥德尔数为起点，获得这个数字所代表的常元符号串。其后的公式序列和证明序列的数字太大，我们就很难仿照下图来表示其一一对应。但很显然，它们依然是一一对应的。
实例1：fff0
图1
常元序列fff0哥德尔配数过程图表
编号 操作 互推过程中结果 编号 备注
1 匹配的哥德尔数 189,000 5 fff0的哥德尔数
2 展开数字指数乘积 8* 27 * 125 * 71= 4 计算
3 常元哥德尔数为指数 2 3* 33 * 53 * 71 = 3 幂底为四个素数
4 常元序列fff0和其
哥德尔数的对应 3 3 3 1
   
   
f f f 0 2
每个常元符号的哥德尔数，f为3，0为1，分别作为素数的指数。
5 常元序列符号 fff0 1 形式客体

按照顺序排列的素数：2，3，…p1。

设常元数字序列的哥德尔数为G，p为素数，k为素数的个数，
则以下乘积的结果，就是数字符号序列的哥德尔数：

G=23 * 33 *…pk-13 pk1

那么属于个体变元的符号该如何配置其哥德尔数呢？因为个体变元总是被套到公式之中，所以，关于个体变元，也可以称作数字变元的哥德尔数配置，似乎离不开公式序列的哥德尔数配置。同样，如果把谓词变元也看做有关词项的变元，那么，有关谓词变元的哥德尔数配置，也同样离不开公式序列。因此，有关数字变元的哥德尔数配置，且放到证明序列的哥德尔数配置中再来讨论。

（二）公式序列的哥德尔数配置

可以用一个符合哥德尔原本的方便实例来说明公式序列的哥德尔数配置。
实例2：( p ∨ q ） → r
依据哥德尔定义32，该公式可以变形为：( p ∨ q ）∨ r

再依据哥德尔对于常量的哥德尔数配置，‘’‘’的哥德尔数为5，左括号“（”的哥德尔数为11，右括号‘’）‘’为13，‘’∨‘’为7。
命题变元为同类型的p，q，r，因为表达个体数字的变元是第一类型变元，即所谓数字符号，它的哥德尔数配置的幂就是1。而表达命题变元的符号，至少是第二类型变元，我们姑且看作是第二类型变元，其哥德尔配数自然就是172，192，232。
该公式序列总共8个符号，5个常元，3个变元，我们用图表一一对应相配：
图2
公式序列的哥德尔数配置

单符号  ( p ∨ q ) ∨ r 备注
哥数字 5 11 172 7 192 13 7 232 哥德尔数
素数幂 25 311 5⁽¹⁷2 ) 77 11⁽¹⁹2 ) 1313 177 19⁽²³2 ) 哥数为指数
公式序列哥德尔数 25* 311 * 5⁽¹⁷2 ) * 77 * 11⁽¹⁹2 ) * 1313 * 177 * 19⁽²³2 )。（*为乘号）
天文数字 如康先生言，公式序列哥德尔数，怎么也是一个天文数字。

难怪后来出现许多哥德尔配数的升级版，哥德尔数的想法异常神奇，但数字也的确大得惊人。当用到对于证明序列配置哥德尔数的时候，这个序列之序列的哥德尔数，恐怕更是超大超大，找个实例方便地作图说明，大概很难办到了。
但我们还是从公式进到证明，即所谓公式序列的序列，看看这样的符号串该如何配置哥德尔数。

（三）证明序列的哥德尔数配置，包括数字变元的哥德尔数配置

依然用康先生的符号表达式，我们来看康先生给出的另一段符号串。
相仿，如果符号序列ei的数是li，则符号序列的序列e0e1e2……en的数也可以定为:

p0l0 * p1l1 * p2l2 *…… * pnln，(*为算术相乘号)

这里，对于符号串的理解，从公式序列，进化到序列的序列了。在哥德尔的形式系统P中，这样的合式序列的序列，应该就是证明。也就是，有一个序列的序列e，它由若干个公式序列构成，序列ei显然是其中的某一个公式。公式序列ei的哥德尔数配置为li，这又表明，有一个符号l是公式序列的序列e配置的哥德尔数，符号e与l的下标i承继公式序列中的含义i = 0，1，2，……，n，一个有限的数字序列。而那个符号序列的序列e0e1e2……en，显然又是类似于公式符号拼接（joining together）那样，现在变更为公式符号与公式符号间的拼接。由此，这些拼接而成的序列的序列所构成的证明，其哥德尔数的配置结果就是：

p0l0 * p1l1 * p2l2 *…… * pnln，(*为算术相乘号)
除了素数p的上标由ki变更为li之外，其它完全一样。所以，一个证明序列的哥德尔数配置，无非是重复公式配置的过程而已。以下，我们也走类似的流程，用一个简单的证明序列实例，来强化一下哥德尔的这种方法。该实例对内格尔《哥德尔证明》中的证明序列实例稍作更动，两行公式变成三行公式（参见内格尔《哥德尔证明》中文版第61页）。
实例3：一个三行的证明序列e

1. (x)(x = ffy) 这可以用e0来替代；其哥德尔数配置为l0。
2. (x)(x = fy) 这可以用e1来替代；其哥德尔数配置为l1。
3. (x)(x = f0) 这可以用e2来替代；其哥德尔数配置为l2。

该证明序列e拼接起来，就是e0e1e2。自然，这个证明序列s的哥德尔数就是：

p0l0 * p1l1 * p2l2 。

而各个公式序列ei的哥德尔数配置方式，也就自然是公式序列的配置方式，前已有实例2标示，不用再来重复列表说明。但是，这个实例3
序列中有两个数字个体变元x与y，我们仅以其中的公式序列1）(x)(x = ffy)为例，来简略评述一下个体变元的哥德尔数配置。
同样可以用一个表来说明个体变元的哥德尔数配置，但一定是在公式整体中来显现个体变元的配置情形。因为哥德尔原著中的常元没有算术等号=，按照哥德尔给常元配以奇数哥德尔数的方式，以下图表中等号=，配以哥德尔数15。而特称符号，按照哥德尔定义32：exists(x,y)=not(forall(v,not(y)))，即(x) = (x)，由此1）成为(x)(x = ffy)，这个公式序列可以分解为13个符号。
请看下图：
图3
从公式序列1） (x)(x = ffy)看个体变元的哥德尔数配置
公式  (x)(x = ffy)可以分解为单独的符号
分解    ( x ) ( x = f f y )
哥数 5 9 5 11 17 13 11 17 15 3 3 19 13
素数 2 3 5 7 11 13 17 19 23 29 31 37 41
个体变元属于第一类型变元，所以其幂为1，但整个公式s依然是天文数字
s哥德尔数 = 25 * 39* 55 * 711 * 1117 * 1313 * 1711 * 1917 * 2315 * 293 * 313 * 3719 * 4113。

三、略谈谓词变元的哥德尔数配置

实例2给出的证明序列，没有使用实例1中的命题变元p，q，r。该证明序列中的公式，是使用常元中的量词，等号和后继运算，结合个体变元x和y而构成的，这类变元表达任意数字个体。这些常元和个体变元的哥德尔数配置，我们已在在前的博文中有所说明。但还有一类变元，可以说形式上像词项，称其为谓词变元，不就是有点类似于主谓结构语句中的任意谓语么？然而，这类谓词变元，实质上更像是任意命题，不像是任意个体。亚里士多德时代就有的谓词，在哥德尔论文中虽未明指，却无处不在，这里得做一点说明。因为谓词变元似乎是元数学算术化的核心，用康先生的论述：
PA实现自我反映的方法叫做元数学的算术化，它的中心任务无非是把元数学的可证性变换成形式算术PA的句子。
这里的可证性，其实就是一个谓词。哥德尔在其原创论文中给出的46个定义，其中的前45个，都是具有谓词特征的定义。依据克林的意见，谓词是函数中的一种。数学和逻辑大概有四种不同的函数，1）从数字到数字的函数称作数论函数，2）从真假到数字的函数称作代表函数，3）从真假到真假的函数称作真值函数，4）而由数字到真假的函数则称作数论谓词，或者简称为谓词。由此可见，元数学算术化的结果，在相当程度上，就是处理从数字到真假的数论谓词。哥德尔原著中的所谓原始递归函数，在克林的这个分析之下，自然就是原始递归谓词（参见克林《元数学导论》第246页）。
于是我们可以看到，数字个体变元是以数字个体或者个体类来赋值以决定一个命题的真假。谓词变元则并非以数字个体或者数字类来赋值，而是以连接数字的算术运算符号或者其它性质作为其变域，例如算术中的等号运算=，大于>运算，小于运算等等<，包括加法，乘法等等，还有哥德尔四十六个定义中的“是变元”，“是素数”，“可证”，“不可判定”等，都具有元数学中的谓词特征，它们才是谓词变元的变域。
这样，我们就得到内格尔在《哥德尔证明》一书中的一个图表。该图表基于他为叙述方便预先设立的常元符号表，常元不同于哥德尔，比哥德尔的常元多了5个，共有12个。增加了3个谓词符号=，+和*（乘号）。由此，内格尔理解的哥德尔数配置方式，如果使用哥德尔的原创文本，就成了以下的图表所示：（参见内格尔《哥德尔证明》第60页）
图4
哥德尔数配置的基本规则略表
数字变量 哥德尔数 可能代入
x 17 0
y 19 f0
z 23 y
数字变量与大于13的素数相联系（原表为13，17，19）
命题变量 哥德尔数 可能代入
p 172 0 = 0
q 192 (x)(x = fy)
r 232 p∨q
数字变量与大于13的素数平方相联系（原表为13，17，19）
谓词变元 哥德尔数 可能代入
P 173 x = fy
Q 193 (x = ff0 * y)
Q 233
数字变量与大于12的素数立方相联系（原表为13，17，19）

关于哥德尔数的配置，似乎还有很多模糊之处需要琢磨，但本篇博文就暂且到此了。