他的不完备定理让全世界开始反思

luyuanhong

他的不完备定理让全世界开始反思

原创 蔡驰南 蔡爸谈数学 2024 年 09 月 22 日 12:33 浙江

罗素悖论的出现，让人们意识到生活中充满了自我指涉带来的矛盾。



罗素悖论有一个通俗版本，那就是理发师悖论

正如黑格尔所说：人类从历史中学到的唯一的教训，就是没有从历史中吸取到任何教训。

那人类究竟有没有从历史中吸取到教训？


大哲学家黑格尔的名言就是一种自我指涉

罗素悖论在数学界引发的地震，直接导致了第三次数学危机。

于是数学家们八仙过海，各显神通，分为三派试图改造数学，走的最远的要数希尔伯特。



他设想将数学符号化，然后引入公理体系，像搭积木一样，搭建出整座数学大厦。按他的设想，这座大厦将坚实无比且毫无死角。

他对此（希尔伯特纲领）充满信心，并于 1930 年 9 月 8 日在科尼斯堡的大会上发表了演讲，说出了那句名言“我们必须知道，我们必将知道”。

可他不知道的是，就在他发表演说的前一天，在另一个规格不高的数学基础研讨会上，一位年轻人发表了一项声明，而台下正巧坐着希尔伯特的学生冯·诺依曼，他听完这个讲话后就意识到，老师宏伟的设想不可能实现了。


冯·诺依曼是当时台下唯一意识到这个声明的划时代意义的人

发表讲话的年轻人名叫哥德尔（Kurt Friedrich Godel），当时才 24 岁。第二年（1931 年），他发表论文，正式提出了哥德尔第一不完备定理。



哥德尔证明了一件事情，按照希尔伯特构想下的数学大厦，将不具有完备性，也就是说无法从几条公理推导出所有的命题来。

让我们来看看这位天才是如何做到的。

他的证明仅仅只用了两步。

第一步，哥德尔配数。

他将所有的数字、符号和命题都变成唯一的数字哥德尔数。

比如他规定最基本的固定符号和数字变量对应于前几个自然数。



这样就能表达所有的命题，比如：这个等式 x=5 ，自然数都可以表示为 0 的后继，于是每个符号对应的哥德尔数是这样的。



然后将质数从小到大排列，将各个符号的哥德尔数按顺序放到指数位置，整体相乘得到的数字就是整个等式的哥德尔数。

因为一个数字的分解质因数是唯一的，因此可以把所有的等式、命题和证明都写成哥德尔数的形式。而且已知一个哥德尔数，还能通过分解质因数，反过来知道对应的等式或者命题。

第二步，构造自指命题。

定义这样一个命题：无法证明哥德尔数为 k 的命题。

符号形式：a﹁R(k,a)

那么这个命题会存在一个哥德尔数，展开形式是这样的，必定有某个质数的指数为 k ，来对应命题中出现的 k 这个数字，这个哥德尔数很大，我们假定它为：n



我们将 n 替换原命题的 k ，那么原来这个哥德尔数展开式中的数字 k 将被数字 n 所替代。



注意我们要进行无尽地替换，因为将 n 再展开，还有 k ，将其中包含的 k 再用数字 n 所替代，以至无穷。

这个新的哥德尔数我们定为 G ，那么 G 对应的是一个什么命题？

恰好对应的就是：无法证明哥德尔数为“将 n 的展开式中的 k 都换成 n ”的命题。

“将数字 n 的展开式中的 k 都替换成 n ”的新哥德尔数恰恰就是 G 。



所以到此为止，我们构造了一个不可思议的“无法证明哥德尔数是 G 的命题”，这个命题的哥德尔数恰好就是 G ！



接下来就是我们熟悉的悖论环节了：

如果这个命题“无法证明哥德尔数是 G 的命题”是假的

那么就说明可以证明哥德尔数是 G 的命题

而哥德尔数是 G 的命题就是“无法证明哥德尔数是 G 的命题”

那么就可以推出“无法证明哥德尔数是 G 的命题”为真

与假设矛盾



所以这个不可思议的命题为真

若这个命题为真，则说明系统中存在真却无法被证明的命题。

也就意味着这个数学系统的完备性不存在。



希尔伯特为了解决罗素悖论而构想的纲领，竟然还是被反身自指所击溃，看来罗素悖论比想象中要强大。

更令人沮丧的是，哥德尔不久又发表了第二不完备定理，就是通过之前的结论，顺理成章地推导出，系统的一致性也无法被证明。

哥德尔以一己之力推翻了希尔伯特的宏大设想，彻底改变了数理逻辑的发展方向。

他虽然成了数理逻辑的“终结者”，但他的研究大大促进了计算机的发展。多年后，图灵找到了另一种证明哥德尔不完备定理的方法，原来一切都是殊途同归。


图灵的“停机问题”与哥德尔不完备定理殊途同归

哥德尔的发现为数学划出了边界，在数学王国里，终究有一些人力所不能及的地方。数学大厦也许并不完美，但经此一役，恰恰说明了它的绝大部分依然坚固无比。



不完备性背后的本质，是自我指涉带来的矛盾。认识自己，一直是世上最深刻的、最终极的问题之一。

哥德尔的横空出世让人们再次回想起，两千年前苏格拉底的那个灵魂发问：我是谁？

虽然哥德尔将数学王国从理想世界里拉了回来；但也许正是自我指涉，才让这个真实的世界变得更加有趣。

蔡爸谈数学