周祯祥
从航天到原始递归函数的四个定理及其证明——哥德尔读后之十二
2021-6-18 16:50
阅读:3075

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

 

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

空间站航天照片

 中国航天.jpg

航天旅游

 贝佐斯升空.jpg

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

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

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

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

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

递归的一个示意图

 递归示意图.jpg

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

莫先生关于函数的观念有点新奇且富哲学意味,他先说函数是一些数变成另一些数的运算,然后又接着说,函数不是指运算的过程,而是指运算应该遵循的规则(参见莫绍揆《递归论》第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个前驱(当xy时,x-y之值为0)。

 

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

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

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

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

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

 

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

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

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

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

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

 

到目前为止,得引进一个插述式的思考了,它和形式系统P没有直接的联系,并且,事先给出以下的定义:

一个数论函数Φ(x1x2...xn)被数论函数Ψ(x1x2...xn-1)和μ(x1x2...xn+1)说成是递归定义的,如果对于所有的x2x3...xnk而言,以下公式成立:

 

Φ(0,x2x3...xn) = Ψ(x2x3...xn)

Φ(k+1,x2x3...xn) = μ(k,Φ(k,x2x3...xn) (2)

 

一个数论函数Φ称作递归的,如果存在一个有限数论函数序列Φ1Φ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.

如果RS是递归关系,那么~RR∨S也是递归函数(因此R∧S也是)。

这个命题2如同命题1一样可分,可分为三个子命题,也同样地分别称名为命题2.1(~R),命题2.2R∨S)和命题2.3R∧S)

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

命题2.1(~R

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

证明:先为~构造一个函数,如原著字符所示a(x)

 否定的函数.jpg

 

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

命题2.22.3同此,构造出真值函数后,结论自明。

由此命题2.22.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。

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

 相等函数.jpg

 

这个等函数,哥德尔称之为关系,在元数学导论中,著者克林尼把这个等号当作谓词,并指出,哥德尔在其论文原著中给出了这个谓词的定理,这个定理正好就是这个命题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,η)].

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

对照表.jpg 

步骤三:对Χ(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,因为符号的费解,花了很多功夫了。符号谜团依然在,文本堆砌意朦胧。但也不能老躺平在一个地方,暂且搁置那些疑惑,继续在原著文本中前行吧。

 


转载本文请联系原作者获取授权,同时请注明本文来自周祯祥科学网博客。

链接地址:https://wap.sciencenet.cn/blog-3478957-1291734.html?mobile=1

收藏

分享到:

当前推荐数:1
推荐人:
推荐到博客首页
网友评论0 条评论
确定删除指定的回复吗?
确定删除本博文吗?