有限的障壁,或许也不坏

作者: 美高梅游戏官网娱乐  发布:2019-11-28

计算无处不在。

*   “上帝是存在的,因为数学是自洽的。魔鬼也是存在的,因为我们不能证明数学是自洽的。”*

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

                                                                                  ——据说出自外尔

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

在日常生活中,我们不时会发现原有的观点是自相矛盾的,尤其是被现实狠狠地打脸以后

第一位发现这一点的,便是图灵。

让我们试想一下,如果常被我们当做推理的工具和严谨的标杆的数学是自相矛盾的——

《计算的极限》系列

这便是华裔科幻名作家特德·姜(姜峯楠)小说《除以零》中的情节了。

难料的世事

美国普林斯顿大学,1936年9月底。

离乡别井,总是一种冒险。即使是一衣带水的英国与美国,文化与传统上的微妙差异,不知制造了多少惶惑。而图灵这时来到普林斯顿,可以说是双重冒险。他刚申请了普林斯顿的奖学金,但却受不了漫长的等待:精英荟萃的普林斯顿实在太诱人了。虽然图灵当时已是剑桥国王学院的研究员,每年有一笔比上不足比下有余的薪金,但人在他乡,经济上需要更多余裕。多申请一笔普林斯顿的奖学金,自然也合乎常理。

图片 1一致的扩充

哥德尔的不完备性定理(参见希尔伯特之梦,以及梦的破灭以及计算的极限,其实描述的就是数学本身的界限。在此之前,数学家认为真理必可达到,而希尔伯特的那句“我们必须知道,我们必将知道”,正是这项信念奏出的最强音。但哥德尔打破了这种幻想,他证明了,对于强得足以包含算术而又不自相矛盾的数学系统而言,“真”与“可证明”是两个彻底不同的概念。在这些系统中,存在着无法证明的真理。

哥德尔的不完备性定理有两条。

第一,一个“合适的”包含了算术系统的数学系统不可能同时是一致和完备的,也就是说,如果它没有自相矛盾,那么必定存在这样的命题,它们是真的,但无法证明。

第二,在这样的系统中,我们可以将“系统本身没有自相矛盾”表述为系统中的一个命题,而这个命题正是一个无法被证明的真命题。假设我们有一个包含算术系统,但又没有自相矛盾的数学系统T>TT,我们将表达“T>TT没有自相矛盾”的命题记作Cons(T)>ConsCon**s(T),那么,哥德尔的第二不完备性定理说的就是Con(T)>ConCon(T)在T>TT中无法被证明。

你可能会有这样的疑问:如果把Cons(T)>ConsCon**s(T)当作一条公理加进T>TT中,那么得到的新系统不就能证明T>TT没有自相矛盾了吗?这是否与哥德尔的定理矛盾?

但如果将Cons(T)>ConsCon**s(T)作为新的公理,我们研究的公理系统就不再是T>TT,而是另一个系统T1=T∪{Cons(T)}>T1=T∪{Cons}T1 = T ∪ {Con**s(T)}。虽然在新的系统T1>T1T1中的确能证明Cons(T)>ConsCon**s(T),但它只表达了原有系统T>TT没有自相矛盾,而对于新系统T1>T1T1,它不能表达这一点。结合了新的公理之后,表达系统本身没有自相矛盾的命题同样会产生变化。这就像一场猫捉老鼠的游戏,我们自以为封死了一切退路,把猎物逼进了墙角,但事实却是按下葫芦浮起瓢,在我们不知道的地方又出现了新的漏洞,狡猾的猎物得以全身而退。

图片 2系统的证明

从某个理论T0=T>T0=TT0 = T开始,逐次添加关于新理论一致性的公理Cons(Ti)>ConsCon**s(T*i*),不断得到T1=T0+Cons(T0),T2=T1+Cons(T1),T3,…>T1=T0+Cons,T2=T1+Cons,T3,…T1 = T0 + Con**s(T0), T2 = T1 + Con**s(T1), T3, …,一直到最后包含无穷条公理的T∞>T∞T,其中每一条公理都有更大的公理来断言它的一致性。似乎我们就得到了一个超越哥德尔不完备性定理的数学系统。

但事情当然不会那么顺利。

首先,在包含无穷条公理的数学系统中,如何在系统内部谈论它的一致性,这并非顺理成章。的确,从理论上来说,包含任意的无穷条公理的数学系统是存在的。但如果要在这种系统内思考,很快就会遇到困境。先不说在系统中进行推理,就算是阅读一个证明,也并非显然。要理解这一点,需要对“形式证明”有更具体的理解。

一个数学系统内的形式证明,实际上是一串有限的命题组合,其中的命题要么是系统内的公理,要么是此前命题明白无误的简单逻辑推论,而最后出现的命题就是这个形式证明要得出的结论,也就是要证明的定理。这种一环套一环的组合方式,恰好保证了最后结论的正确性。而我们在阅读一个形式证明时,也只需要顺次检查这些命题,看看每一个命题是否本身就是公理或者此前命题的推论,就能验证这个证明的正确性。

而如果要在系统内部用命题表达系统本身的一致性,就要用到哥德尔在证明他的不完备性定理时用到的技术。简单来说,我们需要“阅读证明”的这个过程能够完全机械化,即使将人脑换成图灵机,也可以完成类似的验证。但如果数学系统本身包含无穷条公理的话,这个机械的阅读过程可能甚至连第一步都无法开始:如果有无穷条公理,那么面对一个命题,又如何知道它是否一个公理呢?

打个比方,数学系统好比是座仓库,里边装的都是公理。现在有人给我们一件东西,比如说一本书,我们的任务则是查看仓库里是否有一模一样的存货。如果仓库里只有有限样东西,一个个清点总能完成任务;但如果仓库容纳了无数物件,即使仓库的确有相应的存货,如果清点的次序不当,也有可能永远也碰不上我们的目标。

图片 3有限的障壁

无限扩充得到的公理系统T∞>T∞T,虽然能在其中表达系统本身的一致性,但它的一致性却不像我们想象中的那么显然。虽然对于其中的每一条新公理Cons(Tk)>ConsCon**s(T*k*),都有比它更强大的另一条公理Cons(Tk+1)>ConsCon**s(T*k* + 1)保证它的一致性,但这真的能证明包含无数条新公理的系统是一致无矛盾的吗?

我们重温一下一致性的定义:一个公理系统是一致无矛盾的,当且仅当系统中不存在对于假命题的证明。也就是说,无论系统有多大有多复杂,只要系统本身不能证明任意一个假命题,比如说“1=2”,那么这个系统就是一致的。

我们现在尝试考虑无限扩充得到的公理系统T∞>T∞T。要超越哥德尔不完备性定理,就需要在系统内部证明有关系统本身一致性的命题Cons(T∞)>ConsCon**s(T)。假设系统中存在一个这样的形式证明P>PP,这意味着什么呢?

我们知道,形式证明的长度是有限的,毕竟无论是人类还是计算机,都无法完整阅读无限长的证明。所以,证明P>PP用到的公理也只有有限条。既然有限,那么其中形如Cons(Tk)>ConsCon**s(T*k*)的公理也有限,对应的k>kk必然有一个最大值,不妨设为N>NN。那么,证明P>PP中的所有公理,在更小的系统TN+1>TN+1T*N* + 1中早已存在,所以证明P>PP在TN+1>TN+1T*N* + 1中同样有效。也就是说,仅仅在TN+1>TN+1T*N* + 1中就可以证明T∞>T∞T的一致性,它也蕴含了更小的系统TN+1>TN+1T*N* + 1的一致性。

也就是说,因为形式证明的长度是有限的,如果无限扩充后的系统T∞>T∞T能超越不完备性定理,证明它自身的一致性,那么在之前有限次扩充中,必然已经存在一个系统,它能证明自身的一致性。根据之前的论述,这也表示一开始的出发点——也就是系统T>TT——也能证明自身的一致性,而这是不可能的。

尽管我们尝试用无限来突破不完备性定理,但名为“有限”的障壁挡住了我们的去路。

图片 4

对数学史有兴趣的读者(或者说:不觉得《除以零》这小说味同嚼蜡无聊透顶的人)首先会想到的大约会是又一次数学危机和各种奇怪的思潮盛行,极端点科幻点的人大概会想到《除以零》本身或者大刘的《朝闻道》里把莫名其妙的玻璃心粉饰成理想主义,强行让学者寻死的恶心情节。

其实,我们确实不能保证数学里没有自相矛盾。

为什么?

我们无法证明策梅洛-弗兰克尔集合论+选择公理(简称ZFC)是自洽的。由著名的哥德尔第二不完备性定理,如果ZFC是自洽的,那么反而不能证明自身的自洽性。要是我们居然发现了这种证明,那么,ZFC就真的成了自相矛盾的理论。

由于ZFC的基础意义,ZFC的矛盾可以说就是整个数学的矛盾。

至今为止,我们认为ZFC自洽,实际上是根据没有发现任何矛盾的“经验”。

哥德尔的定理说明什么呢?是理性的局限还是真理的相对性?抑或是不可知论的伟大胜利?现实不可理解的混沌本质?

都不是。

在上述的讨论中,隐含了这样一种态度:证明了自身的自洽性,那么这个理论就确认清白了。

正因如此,不完备性定理才会造成一种印象:ZFC做不到这种事情是一种缺陷。

但是我们遗漏了一个真相:不自洽的理论本来就可以证明本身的自洽啊

由于矛盾式的性质,如果ZFC不自洽,那么ZFC就能证明其中任何命题,这也包括“ZFC是自洽的”(数理逻辑中一般用Con(ZFC)表示)本身。

因此,就算没有第二不完备性定理,我们能自如地在ZFC中证出ZFC是自洽的,这也压根不能保证ZFC的清白(第二不完备性定理所做的事是补上一刀:它铁定是有罪的),因为ZFC完全可能是因为不自洽而具备这种能力。

既然自证清白本就不可信,不能做这种证明又于我们何损?

要说明这种证明的可信,就需要保证“ZFC不能证明自己是不自洽的”,否则它完全可以在证出自己自洽后,又翻脸证出自己是不自洽的。

那么,是不是一旦和这一点结合,“理论能证明本身自洽”这个性质就是有用的呢?

并没有

注意前面已经提到了,不自洽的理论不存在“不能证明”能够表达出来的命题的可能。

我们交代过:ZFC可以表达“ZFC自洽”。它当然也就能表达“ZFC不自洽”(记作¬Con(ZFC))

所以单独用“ZFC不能证明自己是不自洽的”就已经说明了ZFC自洽这件事本身,又去在ZFC里证明它自洽完全就是多余的。

可见,对本身自洽性的证明本来就不要也罢。毕竟有了它也不能增加多少理论基础的安全性,没了它也不见得会减少。

现在我们看第二不完备性定理,是不是觉得理所当然多了?

本文由美高梅手机登录网站发布于美高梅游戏官网娱乐,转载请注明出处:有限的障壁,或许也不坏

关键词: