“哥德尔不完备定理”到底说了些什么？——（五）

已有 8778 次阅读 2017-7-18 19:34 |个人分类:科学|系统分类:科普集锦| 数学, 逻辑, 哥德尔, 不完备定理

“哥德尔不完备定理”到底说了些什么？——（五）

第五重：“洞见古今”——拓展了解“哥德尔不完备定理”的相关知识

正像金庸小说《倚天屠龙记》中的乾坤大挪移神功一样，连创作者都没有修炼到最高层。本人也一样，完全不敢说自己修炼成了第五重神功。因此，这部分内容略简单，只谈两个方面。

（一）“哥德尔不完备定理”的实例

1931年哥德尔提出了不完备定理以来，人们逐步相信了复杂公理体系的不完备性。80多年来，人们也逐渐发现了越来越多的哥德尔不完备定理的实例，最著名的就是“选择公理和连续统假设是在集合论中不能确定的命题”，1963年美国数学家保罗∙科恩最终证明了这一点，解决了希尔伯特23个问题中的第1个问题，这其中也有着哥德尔的贡献。

那么有没有直接符合哥德尔论文条件下的实例呢？也就是在皮亚诺公理体系中不可确定的命题？1982年，人们发现了第一个不属于哥德尔构造的、在皮亚诺公理体系内无法证明也无法证伪的算术命题实例——Goodstein定理。

Goodstein定理说的是，Goodstein数列一定会在有限步收敛到0。

Goodstein数列是这样的：首先选取一个正整数g₁，比如设g₁=18，然后把它写成2的次幂之和的形式（18 = 2⁴+ 2¹），再把大于2的指数也写成2的次幂的形式，如果改写后得到的表达式中还有大于2的指数，则再继续把这样的数字写成2的次幂的形式，直到所有出现的数字都小于等于2，最后得到，

g₁=2^{2^2}+2¹

这种写法叫Hereditary Base 2 Notation。g₂是把g₁的这种写法中所有的2都换成3，得到的新数字再减1，也就是，

g₂=3^{3^3}+3¹-1

注意到这是个非常大的数，约等于7.6×10¹²。再继续下去，把g₂写成3的次幂的形式，一直到不出现大于3的数字，然后把3换成4，得到的数再减1，就得到了g₃。以此类推，不断计算下去，就得到了一个数列，这个数列就是Goodstein数列。

下面我们以g₁=18为例，看看数列的前几项：

g₁=2^{2^2}+2¹=18

g₂=3^{3^3}+3¹-1=3^{3^3}+2×3⁰=7.6×10¹²

g₃=4^{4^4}+2×4⁰-1=4^{4^4}+4⁰=1.3×10¹⁵⁴

g₄=5^{5^5}+5⁰-1=5^{5^5}=1.9×10²¹⁸⁴

只看这几项，我们一定会认为这个数列以极快的速度发散到无穷。事实上，这个数列会在有限步骤收敛到0。

Goodstein定理是一个容易看懂的算术命题，其证明可以通过集合论、良序定理以及超限序数等理论和知识来完成。大概思路就是使用超限序数ω构造一个与Goodstein数列平行的数列，这个新数列的每一项都不小于Goodstein数列的对应项，且这个新数列是递减的，必然在有限步后会收敛到0。

Goodstein定理在集合论中的证明过程不长，简单易懂。但是当我们在皮亚诺公理体系内研究这个命题的时候，神奇的事情发生了。1982年，Laurie Kirby和Jeff Paris发现，这个定理在皮亚诺公理体系下是不可证的。这个定理正好是哥德尔不完备定理的一个典型例证。

我们前面说过，哥德尔不完备定理是通过构造出一个不可证的算术命题来证明的。可是，作为已经修炼到第五重神功的我们，清楚的知道，哥德尔构造的这个算术命题我们几乎不可能直接的表达出来，因为太复杂、做不到。所以，哥德尔只是通过构造方法证明了不可证命题的存在性。直到Goodstein定理的发现，我们终于可以见到一个皮亚诺公理体系内不确定的算术命题的样子了。Goodstein定理简明易懂，计算过程明确，但是在皮亚诺公理体系居然无法证明，想想都觉得神奇。由此，我们应该更加钦佩哥德尔的伟大贡献了吧！

（二）是存在既一致且完备的公理体系的

我们讨论了这么多关于哥德尔不完备定理的内容了，估计大家已经毫无疑问地坚信这个定理了。在此，还是要再一次提醒大家，哥德尔不完备定理是有前提条件的，那就是“蕴含皮亚诺公理体系”。也就是说，并不是任何一致的公理体系都不完备。那么，真的存在既一致又完备的公理体系么？答案是肯定的。

我在这里可以给大家即兴构建一个公理体系：

这个公理体系只有两个数字0和1，只有一种二元运算“+”，其三条公理如下，

（1）0+0=0

（2）0+1=1+0=1

（3）1+1=0

公理体系构建完毕。

这个公理体系极为简单，在这个体系内可表达的全部命题都可以证明（比如1+1+1+0=1），而且这个公理体系肯定是一致的，也是“ω一致”的。

其实，一个公理体系如果比较简单，不能承载哥德尔对应中起码的编码要求，那么这个公理体系的一致性与完备性是否存在矛盾就不属于哥德尔定理覆盖的范畴了。对于一些简单的公理体系，是可以证明其既一致又完备的。当然，我构造的公理体系太简单了，以至于一点用处也没有。在实际的数学中，有一种叫做Presburger arithmetic（Presburger算术）的体系，因不包括乘法，所以其实是既一致又完备的，感兴趣的话可以Google之以详细了解。

另外，对于一些也很复杂的公理体系，如果其不足以定义自然数，哪怕这样的公理体系包含了自然数，也可能不受“哥德尔不完备定理”的约束。比如，塔斯基（Tarski）证明了实数和复数理论都是一致且完备的一阶公理体系，虽然它们都包括了自然数；再比如，著名的欧几里德几何在补充了平行公理和实数理论之后，也是一个一致且完备的一阶公理化系统。

“哥德尔不完备定理”确实伟大，但是也用不着神化，它有它的前提条件，有它的适用范围，当然，也同样有着划时代的伟大贡献！

结语

到此，五重神功全部修炼完毕。“哥德尔不完备定理”是一个划时代的伟大成就，也是哥德尔一生唯一的一个重大研究成果。作为一个数学家、逻辑学家的哥德尔，一生能做出这样一个伟大的成就，值了。作为读者，如果通过这个修炼过程，能够真正深入了解并理解了“哥德尔不完备定理”，我想，也值回大家花费在阅读和思考上的时间了吧。

[1] 网上能查到的哥德尔论文的英译版，网址：http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf 

[2] 本人实在不忍心这样描述罗素和怀特海，“才智枯竭”这个说法参见维基百科https://zh.m.wikipedia.org/zh-hans/数学原理 

[3] 参见张寅生先生在科学网的博客，http://blog.sciencenet.cn/blog-320682-969874.html 

转载本文请联系原作者获取授权，同时请注明本文来自赵昊彤科学网博客。
链接地址：http://blog.sciencenet.cn/blog-409681-1067026.html