从航天到原始递归函数的四个定理及其证明——哥德尔读后之十二

人类对于地球的兴趣，如同数学家观察数学角度的变化一样，从地球之中导向了地球之外。六月中旬的两条新闻，都是有关人类飞越地球的航天消息。六月17日，中国三名航天员从酒泉出发，开始了他们到空间站停留九十天的航天之旅。也是在这一天，又听到美国蓝色起源公司，开启商务空间旅游的新闻。本年度的7月20日，亚马逊总裁协同其弟与机舱执行官，又招标一人，一共四人，将启动人类第一次航天旅游。

空间站航天照片

航天旅游

不识庐山真面目，只缘身在此山中。跨出三界外，不在五行中。也许，这样超越物外体验到的世界，是一个更为精彩的世界。哥德尔创立的元数学，大概也是如此。人类走向星空，心灵俯瞰数符，继续来琢磨哥德尔90年前的那部经典文本吧。

哥德尔原著文本在给出基本概念之后，立刻就给出了4个命题，好家伙，每个命题都与递归recursion有关。这在敦促我去把递归论的东西做些理解，多年前买过莫先生的《递归论》，前段时间又买过郝先生中生代的《递归论》。多是闲翻，这次该认真看看了。莫先生在绪论中特别指出：1923年，斯库伦skolem便明显地宣称，所有初等数论中的数论函数都可以通过原始递归式而定义。这样，原始递归函数便开始展现其重要性。自斯库伦之后，这种重要性很快就体现出来。1931年，当哥德尔证明其有名的不完全性定理之时，原始递归函数果然就起到了极其重要的作用。到此，原始递归函数论便正式出现了。

而当你着手理解哥德尔原著二章中的命题1-4及其证明的时候，真可以说，递归概念贯穿这四个命题。自然可以想见，这个原始递归函数观念还要贯穿哥德尔的全篇论文。

哥德尔的证明与原始递归函数紧密相关，那么，你要理解这开头的四个命题证明何以成立，哪怕是粗浅地做点理解，这个原始递归函数的基本观念，恐怕难以见了红灯绕道走，最好是硬着头皮啃啃那些对递归论有研究的书。

知识无限，而人生有限，自然，关注重点只是那个原始递归函数观念。

递归的一个示意图

一、函数-递归函数-原始递归函数

莫先生关于函数的观念有点新奇且富哲学意味，他先说函数是一些数变成另一些数的运算，然后又接着说，函数不是指运算的过程，而是指运算应该遵循的规则（参见莫绍揆《递归论》第15页）。对函数的这个描述颇为耐人寻味，追随这个函数的观念，我们继续来理解递归论中的那个原始递归函数。先略知一点本原函数，算子和递归。

1、本原函数，算子与递归

首先需要知道，这里当然只是仅想知道一点，却并不究其源的“本原函数”。莫先生在递归论中给出25个本原函数，这里仅以列本原函数01位，03位，05位，14位，15位为例，可大致窥见本原函数观念的含义。

01.幺函数I：函数值与自变元的值相同，即Ix=x。

03.零函数0：函数值永为零，即0x=0。

05.相等性函数eq（x，y）：当x=y时，eq(x,y)值为0，当x≠y时，eq(x,y)值为1。

14.加法+：x+y函数的值为x的第y个后继数.

15.减法-：x-y函数的值为x的第y个前驱（当x≤y时，x-y之值为0）。

函数与递归联系起来，又有一个常见的观念在前，那就是“算子”观念。数学与逻辑都讲运算，拿什么东西来让符号进行运算呢？非算子莫属。一般人理解的算子就是数学运算，特别是自然数运算的加减乘除。我们上面列举的加法函数与减法函数，这个加法和减法不就是说的函数么？怎么又出来一个算子呢？但你看莫先生对加法+或减法-函数所作的定义，大概就可以略知一二了。

说x+y是个函数，因为它不仅仅包括加法运算+，还包含那个被运算客体x和y，算子只是这个函数中的一个转换功能而已。用俗世的一个说法，两个自然数变元x和y，或者更细致一点，自然数的两个变元x和y给它赋值，那就只是两个自然数的个体而已。它们躺平在那里，如果没有某个力的推动，它会永远躺平在那里，与世无争，自乐自为。但在其中加个加法算子或者其它什么算子，这两个自然数会转换成另一个自然数。两个躺平的自然数，由此就被算子给激活了，它们开始发生了变化，从原来的情形，变成了另外的一种情形。

人们常说，这个世界没有不变，只有永恒的变化。如果真是这样的话，大概是各种各样的算子在发挥永恒运动的作用吧。但这个世界的变化之中是否还有永恒，还真不是一句万物皆变能够道尽的。太初有道的那个道，也许就是这个世界的所谓永恒吧。智慧追求的极致，真不要全留给那些胆大妄为的哲学，还是留存在人的素朴与敬畏之中为好。

算子就说这么多，递归论所讨论的算子很多，递归算子应该是其中之一。议论了算子，该轮到递归了。

何谓递归呢？递归大概也是一个算子，具有把一个客体转换为另一个客体的功能。按照王宪钧先生的说法，递归概念起源较早，最早有戴德金和皮亚诺的递归定义。但哥德尔的递归定义，才第一次给出了严格的，实际上是原始递归函数的定义。（王宪钧《数理逻辑引论》第336页）

2、递归函数和原始递归函数

皮亚诺算术中的自然数生成方式，可以说是递归函数的一个缩影。在克林《元数学导论》下册第九章开首，我们就可以看到这样的一种表述方式，它让你自然地联想到PA算术。如果是做计算机理论研究的，自然想到的就可能是“可计算性”与那个著名的图灵机。因为递归函数与能行可计算函数，是一对描述同样客体的两个等价概念。

什么是递归函数？不那么正式地理解，就是类似皮亚诺算术中的自然数生成过程所使用的函数。

首先给出Φ(0)，随后，对任意自然数y，用y及Φ(y)来表示出Φ(y’),几乎完全是同样的过程，自然数由此而一个一个生成。只需看在自然数列中y的产生过程，就可以判定有一个类似的过程来决定下一个数Φ(y)。

啃读原著是一个艰难但有时却很快意的事，它会让你发现学界今天经常使用的一些观念，原来就在原著之中。在哥德尔原著文本第二章，哥德尔就给出他的递归函数了。

到目前为止，得引进一个插述式的思考了，它和形式系统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) （2）

一个数论函数Φ称作递归的，如果存在一个有限数论函数序列Φ₁，Φ₂，...Φ_n，该序列在Φ中终结，且有如下性质：

或者是，该序列的每一个函数Φ_k是被在前的数论函数递归定义的；

或者是，通过替换从在前的任意数论函数推导而来的；

最后，或者是，它是一个常元或者是那个后继函数x+1。（哥德尔原著英译本第43页）

哥德尔当时称这个函数为递归函数，但随后的递归函数研究发现，还有比哥德尔定义的递归函数更广泛的函数客体。在哥德尔的建议下，递归函数概念扩展了，这就是比哥德尔递归函数容量更大的一般递归函数。哥德尔在其经典文本中定义的递归函数，也就加上了一个限定词：原始。由是，哥德尔原来称作递归函数的东西，今天称之为原始递归函数。

有了这个原始递归函数观念，哥德尔随之而列出的四个命题中的1，2，3，依据他的说法，直接就从其定义可以证明出来。

二、哥德尔命题1，2，3及其证明

给出原始递归函数的定义之后，哥德尔立马列出四个有关递归函数的命题，其中的前三个命题，完全依据他所给出的原始递归函数定义，以下分别予以简要说明。

命题1.

每一个从递归函数或者关系运用递归函数来替换变元而导出的函数，是递归的；通过运用依据上述模式（2）获得的递归定义，从递归函数导出的每一个函数也是递归的。

这个命题1可以分为两个子命题，分别称名为命题1.1和命题1.2。

先来证明命题1.1：每一个从如下递归函数，即通过递归函数的替换来取代变元而导出的函数，是递归的。

这个命题1.1，可以说是哥德尔定义中的一种情形。哥德尔在其递归定义中，分列了三种情形，其中的或者是，通过替换从在前的任意数论函数推导而来的，不就是命题1.1所描述的情形么。

这就证明了命题1.1。

而命题1.2，就是依据定义模式（2）而获得的函数，自然完全符合递归定义的要求。

由此而证明了命题1.2。

命题2.

如果R和S是递归关系，那么～R，R∨S也是递归函数（因此R∧S也是）。

这个命题2如同命题1一样可分，可分为三个子命题，也同样地分别称名为命题2.1（～R），命题2.2（R∨S）和命题2.3（R∧S）。

从命题2开始，我们看到点哥德尔证明的风格了。他不是去直接证明这个命题，例如命题2.1，而是先构造一个和所证对象构件相关的函数，然后再来和他的递归定义进行对照，我们且从命题2.1开始。

命题2.1（～R）

先插一点闲话，命题逻辑连接词～，还有∨与∧在美国学者皮尔斯最早给出真值表之后，它们就具有函项功能，这里的函项实际上和英文的function完全相同，因为不是数而是表达命题项或者词项的函数，所以逻辑界多称为函项，在王宪钧先生的《数理逻辑引论》中称之为真值函项，这里的函项和函数应该在符号指称上没有区别。

证明：先为～构造一个函数，如原著字符所示a(x)。

显然函数R和函数～R，在～的上述真值函数条件下完全一一对应，由是，R为原始递归函数，～R自然也是完全合乎递归定义的原始递归函数。

命题2.2和2.3同此，构造出真值函数后，结论自明。

由此命题2.2和2.3得证。

命题3.

如果函数Φ(x)与Ψ(y)是递归的，则关系Φ(x)=Ψ(y)也是递归的。

同样，算术中的等号也可以构造出函数，如上所示，在莫先生的递归论中，等函数属于基本函数中的第五个函数：

5.相等性函数eq（x，y）：当x=y时，eq(x,y)值为0，当x≠y时，eq(x,y)值为1。

莫先生的这个表述完全等价于哥德尔的等函数表示，

γ(x,y)=0, 如果x=y; γ(x,y)=1,如果x≠y。

这也可以表示为如下公式：

这个等函数，哥德尔称之为关系，在元数学导论中，著者克林尼把这个等号当作谓词，并指出，哥德尔在其论文原著中给出了这个谓词的定理，这个定理正好就是这个命题3。

证明同样是依据哥德尔的递归定义，因为命题3的构成，满足哥德尔定义的条件：或者是，该序列的每一个函数Φ_k是被在前的数论函数递归定义的。

由等号连接的两个在前函数是原始递归的，所以，命题3成立。

由此而证明命题3。

在这里再插一段闲话，命题3因为其函数涉及到多元，在哥德尔原著中称为关系，相应的函数依据其变元数量从而便有了一元到n元函数的称呼。这样看待函数的方式，很容易和古典逻辑的主谓项观念联系起来。古典逻辑的主谓项观念，在德国人弗雷格那里形成了经典现代谓词逻辑。这就使得，我们所关注的原始递归函数，不仅有函数，不仅有递归，不仅有关系，还把古典的谓词观念带到了元数学。而这个古典的谓词观念，又似乎天然地与逻辑量词不离不弃。于是我们的命题4，就更为复杂一些，它出现了量词，自然，谓词观念恐怕也要如影随形。但原著文本表达式的符号好像有误打之嫌，我做了相应改动，但这符号的疑惑让人纠结。

三、哥德尔命题4及其证明，一个带有疑惑的证明

命题4带来的观念还不止是谓词和量词，还有算术中的大于等于符号。算术与逻辑，似乎混合在这个命题4之中了，且看命题4。

命题4

如果函数Φ(x)与关系R(x，y)是递归的，那么关系S，T也是递归的

S(x,y)≡($x)[x ≤ Φ(x)∧R(x，y)]

T(x,y)≡("x)[x ≤ Φ(x)→R(x，y)]（源文本～似误打，改为等价符号≡）

同样，以下函数Ψ也是递归的

Ψ(x,y)=min x[x ≤ Φ(x)∧R(x，y)]

其中，min xF(x)意味着：那个最小的的数x，对于这个数而言，F(x)成立；并且，如果没有这样的数，则数字为0。

哥德尔用语简洁，命题4实际上是三个支命题，分别为命题4.1，命题4.2与命题4.3。他在文本上已经给出证明的思路，这里按照他的思路给出证明的步骤。

命题4.1.

如果函数Φ(x)与关系R(x，y)是递归的，那么下述关系S也是递归的。

S(x,y)≡($x)[x ≤ Φ(x)∧R(x，y)]

命题4.2

如果函数Φ(x)与关系R(x，y)是递归的，那么下述关系T也是递归的。

T(x,y)≡("x)[x ≤ Φ(x)→R(x，y)]

命题4.3

如果函数Φ(x)与关系R(x，y)是递归的，那么下述函数Ψ也是递归的。

Ψ(x,y)=min x[x ≤ Φ(x)∧R(x，y)]

以下是命题4.1的证明。

证明：

步骤一：从假设导出一个存在命题。

因为有函数Φ(x)与关系R(x，y)是递归的，两个递归客体都有变元x，则一定存在一个递归函数ρ(χ,η)，使得

R(χ,η)≡[ρ(χ,η)=0],（源文本～似误打，改为等价符号≡）

步骤二：依据递归定义模式（2），我们构造以下情境中的递归函数Χ(x,η)。

Χ(0,η)=0

Χ(n+1,η)=(n+1).α+Χ(n,η).α(α)

其中，

α=α[α(ρ(0,η))].α[ρ(n+1,η)].α[Χ(n,η)].

这个构造的依据与构造客体如以下对照表所示：

步骤三：对Χ(n+1,η)的分析

在尾注33中，哥德尔注释，加法和乘法已经作为原始递归函数来看待。构造情景中的加法“+”和乘法“.”皆作为已知的原始递归函数。

由此，依据以上对于α的定义，它只能取0或者1两个值，而不能取其他值（见哥德尔文本注释34）。这样函数Χ(x,η)的第二式Χ(n+1,η)就

或者是第一种情形：如果α=1，那么Χ(n+1,η)=n+1；

或者是第二种情形：如果α=0，那么Χ(n+1,η)=Χ(n,η）。

步骤四：导出产生第一种情形的充要条件

而第一种情形很清晰地得以产生，当且仅当α的所有构成要素都是1，

也就是说，如果有

～（（R(0,η)）∧R(n+1,η)∧[Χ(n,η）=0].

步骤五：导出命题4.1，也导出了命题4.3

由此，推导出函数Χ(n,η）（考虑为n的函数）保留了0直到最小的n值，对于这个n，关系R(n,η）成立。并且从那刻起，如果有R(0,η)的话，则等于这个最小值，就已经是这样的情形了，相应的Χ(x,η）就是常元，并且这个常元=0。

因此而有以下结果：

Ψ(χ,η)=Χ(Φ(χ),η)

S(χ,η)≡R[Ψ(χ,η),η]（源文本～似误打，改为等价符号≡）

关系T可以用否定归结到类似于S的情形，所以，命题4.2由此而得证，命题4全部得到了证明。

这个命题4，因为符号的费解，花了很多功夫了。符号谜团依然在，文本堆砌意朦胧。但也不能老躺平在一个地方，暂且搁置那些疑惑，继续在原著文本中前行吧。