数学里存在不可能被证明的问题吗？

中科院物理所

2024-03-02 12:51发布于北京中科院物理所官方账号

在中学数学课里，除了学习如何计算，还会学到如何证明。证明是在公理、定理、假设或前提条件等基础上，用逻辑的方法推导出结果的过程。所以，我们很容易会认为所有的数学问题，只要使用公理或定理等加以检验的话，就一定能证明其真伪。

但是，根据“哥德尔不完全性定理”，这种想法却是错误的。那么，就让我们来了解一下在证明数学问题的世界里绝对逾越不了的“两堵墙”吧。

“公理”是数学的出发点

“不完全性定理”是于1931年由出生在现捷克境内的奥地利数学家库尔特·哥德尔（1906～1978）发表的。当时哥德尔年仅24岁。在20世纪的数理逻辑学（用数学方法解析逻辑学的领域）中，该定理被认为具有最大的影响。

库尔特·哥德尔（Kurt Gödel，1906～1978）

数学课总会讲授“公理”(最基础的前提条件）和“命题”(需要判断其真伪性的问题）。公理的集合被称作“公理系统”，基于“公理系统”就能够证明“定理”。换句话说，公理就是证明的出发点。不完全性定理，就是陈述关于公理和命题相关性质的定理。

根据逻辑学阐明数学的原理

在20世纪初的数学界，既是哲学家、逻辑学家又是数学家的英国人伯特兰·罗素（Bertrand Russell，1872～1970）和阿尔弗雷德·诺思·怀特海（Alfred North Whitehead，1861～1947）等人尝试用公理和推理规则去阐述证明所有的数学原理。这与艾萨克·牛顿（Isaac Newton，1642～1727）在其著作《自然哲学的数学原理》中阐明了自然界的原理一样，只是把目光对准了数学界。罗素和怀特海为此写下了著作《数学原理》。

在逻辑学里，通常会把语句替换成逻辑符号。首先，把名词或短语等用A、B、C……来替代；接着,将表示逻辑关系的“并且”“或者”“如果……那么”等词置换为“∧”“∨”“⇒”等符号。

逻辑学里最有名的推理规则，应该要算“三段论”了。让我们尝试着把下面这段典型的通过两个前提得出结论的三段论语句，替换成逻辑符号来表示。“如果早上起不了床，那么就不能去听课。如果不能去听课，那么就会留级。所以，如果早上起不了床，那么就会留级”。假设A表示“早上起不了床”、B表示“不能去听课”、C表示“留级”。于是，就可以把上面这段话变成“A⇒B。B⇒C。所以A⇒C ”。

哥德尔发表的不完全性定理从根本上颠覆了罗素等人的尝试，对逻辑学和数学的世界造成了很大的冲击。

自涉悖论

为了让大家更好地理解不完全性定理，我们先来试着考虑在哲学和逻辑学中常常被当做例子的“自涉悖论”。悖论指的是，从看似正确的前提和看似稳妥的推理过程出发，却推导出违背直觉令人难以接受的结论。在逻辑学里，把对同一个对象或问题的两个互相矛盾的命题，但又分别被证明成立的现象称作“二律背反”。二律背反也是悖论的同义词。

例如，像“这句话是错误的”这样一个看起来没什么问题的简单命题，就会引起悖论。这就是所谓的自涉悖论，这句话无法确定它是真（正确的）还是伪（错误的）。如果这句话是真，但是因为“这句话是错误的”，那么这句话就变成伪。一个命题不可能既是真命题又是伪命题，由于产生了这样的矛盾，因此，用反证法会得到它是伪命题。

但是，如果“这句话是错误的”是伪命题，那这句话反而又变成正确的了。这又出现了既是伪命题又是真命题的情况，也就是说，这里发生了二律背反。所以，像这样无法判断是真是伪的命题是存在着的。

哥德尔不完全性定理中的“不完全性”（也作“不完备”），指的是“无法通过证明来判断命题真伪”的意思。哥德尔通过使用与自涉悖论相似的讨论方法，证明了在罗素等人的著作《数学原理》的体系里存在着无法肯定也无法否定的“佩亚诺算术”命题，也即第一不完全性定理。随后，通过运用此结果，推导出了“无法在《数学原理》体系里去证明《数学原理》体系里不存在矛盾”的结论，也即第二不完全性定理。

上面所说的佩亚诺算术，指的是基于意大利数学家朱塞佩·佩亚诺（Giuseppe Peano，1858～1932）提出的五大算术公理建立的将自然数体系化的数学基础理论。把佩亚诺公理系统中公理5的数学归纳法用“一阶逻辑”改写，再追加自然数的和与积的公理后，就称为“佩亚诺算术”。在本文开篇展示的不完全性定理中提到的“自然数论”，指的就是佩亚诺算术。

导入哥德尔数来证明定理

那么，哥德尔又是怎样推导出不完全性定理，以及怎么证明它的正确性的呢？对此，哥德尔思考出了崭新的方法，就是利用“哥德尔数”把算术的命题和证明等符号化（见下方图文中的例子）。哥德尔在《数学原理》涵盖的体系中，就通过使用哥德尔数，指出存在无法通过证明来判定真伪的命题。

在哥德尔数的基础上，哥德尔运用被称作“对角线方法”的数学工具，制作出了“此命题在《数学原理》的体系中无法证明”的佩亚诺算术命题。基于此，证明了第一不完全性定理。

对角线方法是数学里的一种证明方法。哥德尔利用对角线方法进行的证明全过程非常复杂也非常巧妙，在本文有限的篇幅里很难详细地清楚说明。所以，在此就用相对来说比较简单的“康托尔的对角线方法”，对其精华部分简单介绍一下（下图）。

首先，准备9个两面分别为黑白色的翻转棋（黑白棋）棋子，摆放为3×3的形式（横向3行纵向3列）。接着，把处于对角线上的3个棋子翻转后，当作第4行的棋子。新生成的第4行的第1个棋子是从第1行的第1个棋子翻转过来得到的，所以第4行与第1行的棋子排列相异。同样的，第4行与第2行至少在第2个棋子上不同，与第3行至少在第3个棋子上不同。像这样，通过翻转对角线上的棋子，就能够生成与之前的3行都不一样的新的排列了。

最后，我们再把3×3扩展到n×n来看看。如果准备每组有n个n组棋子，并把每一组记为L₁，L₂，L₃……L_n。通过只翻转对角线上的棋子，就一定能够得到一组新的与L₁……L_n都不一样的棋子排列。

德国数学家格奥尔格·康托尔（Georg Cantor，1845～1918）基于这样的对角线方法，证明了对于所有的集合（包含无限集合），总存在集合元素个数更多的集合。因此，这也被称为“康托尔的对角线方法”。

由于哥德尔通过巧妙使用哥德尔数和对角线方法证明了不完全性定理的正确性，导致了被称为“希尔伯特计划”的数学计划以失败而告终。希尔伯特计划指的是在20世纪20年代，以被称为“现代数学之父”的德国数学家大卫·希尔伯特（David Hilbert，1862～1943）为中心推进的数学计划。这个计划的最大目的就是“要展示在数学里是不存在矛盾的”（不存在矛盾在数学上被称为“相容性”)。

但是，由于出现了第二不完全性定理，导致这个计划的目标无法实现。希尔伯特也曾定下展示“数学完全性”的目标，但是根据第一不完全性定理，这也成为了不可能的事。这位数学家当时的失望心情应该很难想象吧。

哥德尔与爱因斯坦一起度过的时光

最后，让我们回顾一下哥德尔的生平。哥德尔于1906年4月28日出生于奥匈帝国布尔诺（现捷克境内的城市）的一个富裕的奥地利裔家庭。1924年，他进入奥地利的维也纳大学学习，最开始学习物理，随后决心把数学作为自己研究的中心。

不完全性定理发表于1931年。1940年，为了逃离纳粹德国，他与妻子阿黛尔一起前往美国。虽然他不是犹太人，但是有一天却被纳粹分子当作犹太人而遭受袭击。当时阿黛尔用雨伞赶走了纳粹分子，没有发生严重的后果，但是这件事让哥德尔感受到了危险，并开始考虑是否需要离开欧洲。当时，帮助他们去往美国的正是匈牙利裔著名数学家约翰·冯·诺伊曼（John von Neumann，1903～1957）。

哥德尔到达美国后，于普林斯顿高等研究院任职，与物理学家阿尔伯特·爱因斯坦（Albert Einstein，1879～1955）成为了同事。据说，爱因斯坦认为哥德尔的智力水平与自己匹敌，非常喜欢和他一起讨论问题。之后，哥德尔再也没有回过欧洲。

对宇宙物理和人工智能也有影响

哥德尔在普林斯顿高等研究院时，除了与爱因斯坦，还跟帮助他来到美国的冯·诺伊曼、“曼哈顿计划”的负责人罗伯特·奥本海默（Robert Oppenheimer，1904～1967）等很多著名学者有过密切的交流。其中，哥德尔受到爱因斯坦的强烈影响，对广义相对论进行了深入研究，随后构筑了被称作“哥德尔宇宙”的宇宙论。哥德尔于1978年1月14日病逝于普林斯顿医院，享年71岁。

在哥德尔去世后，他提出的不完全性定理在计算机科学、人工智能等领域常常被引用。实际上，在哥德尔生前的某次演讲中，就曾对英国数学家艾伦·图灵（Alan Turing，1912～1954）所设想的计算机原型“图灵机”做了评论。从中可以看出，哥德尔在当时就已经对人类的理性与机器之间有了深刻的思考。可以说，哥德尔在年仅24岁时发现的定理是构建现代科学技术的基础之一。

本文摘自《科学世界》2021年第1期《哥德尔不完全性定理》。

新媒体编辑 | 张丽君

来源：科学世界

编辑：紫竹与

转载内容仅代表作者观点

不代表中科院物理所立场