希尔伯特之梦,以及梦的破灭(作者删节版)

注:本文遵守首页上的CC版权声明,严禁商业性媒体和网站未经本人同意的转载,个人转载请注明作者与出处,谢谢!

本文来源:科学松鼠会http://songshuhui.net/archives/20161.html

Wir müssen wissen, wir werden wissen.

我们必须知道,我们必将知道。

你听到的,正是80年前,1930年,希尔伯特在他退休时演讲的最后六个单词,也是鼓舞一代数学家的六个单词。尽管当时第三次数学危机仍然阴魂不散,但他们坚信,数学大厦的基础是坚实的。他们也坚信,任何数学真理,只要通过一代又一代人的不断努力,都能用逻辑的推理将其整合到数学的大厦中。

这是何等的气魄!这是何等的梦想!

但就在演讲前夕,他的同胞哥德尔,作出了一个断言,彻底打碎了这个梦。

希尔伯特计划

希尔伯特是一位名副其实的数学大师,有人将他称为“数学界最后一位全才”,他看待数学的眼光也是相当深刻的。

师从林德曼,希尔伯特在23岁便以一篇关于不变量理论的论文跻身数学界。他的证明方法在当时相当具有争议性。在这篇论文中,他使用了非构造性的证明,也就是说他只能证明某个数学对象的存在性,却无法将它具体指出。另外,他的证明依赖于对无穷的对象使用排中律,从而遭到了不少人的质疑。

排中律,说的就是一件事非真即假,这再明白不过了,为什么还有反对的意见呢?

比如说这样一个命题:pi中含有任意长度的连续数字9。如果我们接受排中律的话,这个命题非真即假。但无论这个命题是真是假,我们都无法在实际上验证,因为要验证这个命题,我们都要将pi无穷地计算下去,而这是不可能做到的。所以,人们对于将排中律用到这种无穷的情况仍有顾虑,因为这不是他们的直觉能掌握的范围。

我们不知道是否因为这件事,希尔伯特动起了为整个数学寻求一个坚实基础的念头,但我们可以知道,在经过多年在不同数学领域富有成果的涉猎后,希尔伯特将目光投向了整个数学。对平面几何学的严格公理化可能是他在这方面的第一个尝试,但他的思考绝不仅限于几何。他的目标是将整个数学体系严格公理化,然后用元数学——证明数学的数学——来证明整个数学体系是坚实的。

为了这个目标,他制定了著名的希尔伯特计划。

首先,将所有数学形式化,让每一个数学陈述都能用符号表达出来,让每一个数学家都能用定义好的规则来处理这些已经变成符号的陈述。

然后,证明数学是完整的,也就是说所有真的陈述都能被证明,这被称为数学的完备性;证明数学是一致的,也就是说不会推出自相矛盾的陈述,这被称为数学的一致性。

最后,找到一个算法,可以机械化地判定数学陈述的对错,这被称为数学的可判定性。

如果这个计划完成了,那意味着什么?在保证数学的一致性这个前提下,我们又有数学的完备性,也就是说只要是真的都可以证明。这其实就是说,对于任意一个数学猜想,不管它有多难,只要假以时日,通过一代又一代人的努力,总是可以知道这个猜想对不对,并且证明或否定它。

这是个雄心勃勃的计划,但希尔伯特并不认为这是不可能的。他提出,先在基础的数学系统进行这样的形式化,然后再将其推广到更广阔的数学系统中,最后实现整个计划。于是,整个计划便归结于在算术系统中进行这样的形式化,并且在它的内部证明它的完备性、一致性和可判定性。

这似乎不太困难。算术系统并不是一个很复杂的系统,它早在1889年就被皮亚诺归结成一个有5条公理的系统,其中只有最后一条数学归纳法公理比较复杂。我们可以想象,希尔伯特本人也认为这是可以解决的问题。他将算术公理系统的相容性列入了他那23道希尔伯特问题中,位列第二,希望20世纪的数学家能给出一个证明。这份1900年写出的问题表,后来证明是相当具有前瞻性的,即使情况并不一如希尔伯特预计的那样。

1931年,仅仅在他退休一年之后,希尔伯特第二问题即告解决,尽管解决的方式是希尔伯特所没有预料到的。

逻辑弄人。

哥德尔不完备性定理

可以说,哥德尔粉碎了希尔伯特计划。

在希尔伯特退休之时,哥德尔才刚刚登上数学舞台。在某种意义上,正是希尔伯特间接将哥德尔引领到数理逻辑这个领域的。在希尔伯特和他的学生阿克曼合著的《数理逻辑原理》中,他们提到了这样一个问题:在形式系统中,真的命题是否都是可证明的?这正是哥德尔博士论文的主题。在这篇论文中,哥德尔证明了一阶谓词演算是完备的,这就是不太著名的哥德尔完备性定理。一阶谓词演算是一种能力比较弱的数学系统,如果只是应用它的话,我们连自然数都定义不了,就更别说做算术了。自然,哥德尔的目光是不会仅仅局限于此的。

在完成博士论文之后,哥德尔便着手探索更一般的数学系统。一年后,也就是1931年,他对算术系统的探索即告胜利。这个胜利,也就是希尔伯特计划的失败。他的结论,就是哥德尔不完备性定理,一共有两个。

第一,他证明了,对于任意的数学系统,如果其中包含了算术系统的话,那么这个系统不可能同时是完备的和一致的。也就是说,要是我们能在一个数学系统中做算术的话,那么要么这个系统是自相矛盾的,要么有那么一些结论,它们是真的,我们却无法证明。

第二,他证明了,对于任意的数学系统,如果其中包含了算术系统的话,那么我们不能在这个系统内部证明它的一致性。这就是希尔伯特第二问题答案的一部分。

哥德尔证明这两个定理的武器,就是希尔伯特在他的计划中使用的武器:形式化。在哥德尔的证明中,他先将所有的数学陈述以及它们的证明用符号形式地表达出来,然后利用哥德尔自己发明的一个重要技巧——哥德尔数化——将所有这些陈述和证明变为一个个的自然数。那么,借助数学归纳公理,我们可以递归地建立针对所有自然数的陈述,而一个这样的陈述同时又是一个自然数,所以它描述了自己。换句话说,这个陈述陈述了它自己。

这种自指的情况,在数学上很有用,也非常凶险。它是不少悖论的源泉。第一个例子当然是说谎者悖论:“这句话是错的”。第二个就是罗素悖论,它引起了第三次数学危机,这也可以说是希尔伯特计划的一个动因。

我们来看看它的一个通俗版本,叫理发师悖论。

在一个小镇内,只有一名理发师,他在理发店门外公布了这样一个原则:只为不会自己理发的人理发。那么,他的头发谁理呢?要是他自己理的话,他就会自己理发了,那么根据他的原则,他不应该为自己理发;要是他不给自己理发的话,根据他的原则,他倒是应该给自己理发。逻辑似乎在这里失效了。

这种逻辑上的混乱局面,背后就是罗素悖论:定义一个集合,它包含所有不包含自身的集合,它是否包含自身?从上面的分析,我们可以看到,一切问题在于“包含自身”这种自指的描述。后来,在策梅洛和弗兰克等逻辑学家的努力下,通过在集合论中添加正则公理等限制,才将这种危险的自指从集合论中排除。当然,这是后话了。

这种自指的性质,尽管危险,但在哥德尔的妙手中,它就变成了证明的利器。他构造了一个命题,这个命题说的正是它自身的不可证明性。如果用类似说谎者悖论的语言来表达的话,就是:“不存在对这个命题的形式证明。”如果它是真的,那么它是不可证明的,说明系统是不完备的,因为存在一个真的而又不可证明的命题。如果它是假的,那么存在一个它的证明,这样它应该是真的,说明系统是自相矛盾的、不一致的。这就是哥德尔的第一个不完备性定理:如果有自然数的话,完备性和一致性不可得兼,这个系统要么自相矛盾,要么存在不能证明也不能否证的命题。

然后,我们来仅仅考虑一致性的问题。假定系统是一致的,也就是说不会自相矛盾的,那么我们刚才提到的命题就是不可证明的。如果我们能在系统内部证明系统的一致性的话,我们就相当于在系统内部证明了那个命题,这与不可证明性是矛盾的。也就是说,我们做了错误的假设:能在系统内部证明系统本身的一致性。由此,哥德尔证明了他的第二个不完备性定理。

他的这两个不完备性定理,对于希尔伯特计划是个沉重的打击:计划的第二步被证明是无法实行的。如果我们假定数学不会自相矛盾的话,我们就必须承认数学是不完备的,也就是说有这么一些数学命题是不可判定的:我们既不能证明它们为真,也不能证明它们为假。但很多数学家仍然认为,这并不威胁数学的正常发展,因为他们觉得有意义的数学命题极不可能是这样的。换句话说,数学家们仍然相当乐观。

同样是哥德尔,这次连同科恩,给这些数学家敲响了警钟:数学家研究的“有意义”的数学命题也可能是不可判定的。他们解决的又是一个希尔伯特问题:由康托尔提出的连续统假设。这个问题位于列表之首,是一个纯粹的集合论问题。哥德尔证明了连续统假设和策梅洛-弗兰克集合论是相容的,也就是说二者之间没有矛盾;科恩证明了从策梅洛-弗兰克集合论出发不能证明连续统假设。这两个结果综合起来,其实就说明了连续统假设在策梅洛-弗兰克集合论中是不可判定的。要是你知道策梅洛-弗兰克集合论正是解决第三次数学危机的武器和现代数学的逻辑基础,你就会明白这到底意味着什么。

哥德尔的魔鬼第一次露出了真面目。希尔伯特第一问题竟然就是不完备性定理中预言的那类不知真假的怪异命题的一个实例,这实在令人泄气。

既然希尔伯特计划的第二步都被证明是不可行的,那么第三步也就没有必要继续下去了。第三步是寻求一个能机械证明所有数学定理的程序,著名的停机定理也否定了这种可能性。停机定理的证明相对比较简单,也是利用自指的技巧,证明这样程序是不可能存在的。

至此,希尔伯特那宏伟的计划宣告全盘失败。

有些事情,我们确实不知道,即使对于数字,这是逻辑说的。

余波

令希尔伯特在天国的灵魂有所安慰的是,算术系统的一致性被证明了。这个证明用到了不在算术系统内的超限归纳法,它可以被视为一种加强版的数学归纳法,是用在无穷序数上的。这其实就假定了策梅洛-弗兰克集合论的一致性。当初康托尔建立无穷集合论时,曾遭到不少人的攻击,这时希尔伯特挺身而出,为康托尔和他的无穷集合论疾呼:“没人能将我们从康托尔创造的乐园中赶出来。”如今,康托尔的无穷集合论衍生出来的超限归纳法反过来又部分实现了希尔伯特的梦,这是冥冥之中的安排,还是希尔伯特的敏锐眼光所致?恐怕没人能说得清楚。

但哥德尔的魔鬼仍在肆虐。越来越多的数学问题被证明是不可判定的,这些不可判定的问题也越来越初等。乍看起来并非不可捉摸,但到头来却不可判定。比如说,如果我们用可数种颜色对每一个实数染色,是否必定存在4个互不相等的数a,b,c,d,使得它们的颜色都相同,而又满足a+b=c+d?这看起来怎么也不像没有一个确切结论的问题,但有人证明了它实际上和连续统假设的否定是等价的,也就是说,在策梅洛-弗兰克集合论内,它也是不可判定的。这就给数学家们心头压上了一块大石:谁也不知道自己辛辛苦苦做了十几年的题目,会不会突然有一天被证明是在现有数学体系中不可判定的。

尽管这样,哥德尔的不完备性定理仍然带给我们很多教益。至少我们知道了,有些东西我们不可能知道。在哥德尔的这个划时代的证明之后,数学家对数学的基本工具——证明——有了新的认识。专门研究数学证明的证明论,在他的启发下蓬勃发展。但是,哥德尔教给我们最重要的一点是:

数学,如同人生,如同爱情,有些东西是真的,你却永远无法证明。

Advertisements

6 thoughts on “希尔伯特之梦,以及梦的破灭(作者删节版)

  1. Pingback引用通告: 计算的极限(三):函数构成的世界 | fwjmath的相空间

  2. Pingback引用通告: 计算的极限(五):有限的障壁 | fwjmath的相空间

  3. 你好,我想问一下,你在科学松鼠会发表的同一篇文章中提到的巴黎学院九本数学书叫什么名字呢?有沒有类似的好书呢?

  4. “令希尔伯特在天国的灵魂有所安慰的是,算术系统的一致性被证明了。这个证明用到了不在算术系统内的超限归纳法,它可以被视为一种加强版的数学归纳法,是用在无穷序数上的。这其实就假定了策梅洛-弗兰克集合论的一致性。”

    用不到假定整个ZF的一致性吧。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s