兔宝宝属蛇 2009-11-4 23:31
数学家研究的“有意义”的数学命题也可能是不可判定的
希尔伯特之梦，以及梦的破灭 [url=http://www.bullock.cn/users/editorwlb/]科学松鼠会[/url] [url=]@ 2009-9-27 11:28[/url] [url=]阅读(797)[/url] [url=http://www.bullock.cn/blogs/songshuhui/diggs/80230.aspx]推荐值(29)[/url] [url=http://www.bullock.cn/blogs/songshuhui/Trackback.aspx?id=80230]引用通告[/url] [url=http://www.bullock.cn/blogs/songshuhui/?cat=%e6%95%b0%e5%ad%a6]分类: 数学[/url]
[b]一个天才质疑了另一个天才，并最终证明：数学家研究的“有意义”的数学命题也可能是不可判定的。[/b]
Wir müssen wissen, wir werden wissen.
我们必须知道，我们必将知道。
你听到的，正是80年前，1930年，希尔伯特在他退休时演讲的最后六个单词，也是鼓舞一代数学家的六个单词。尽管当时第三次数学危机仍然阴魂不散，但他们坚信，数学大厦的基础是坚实的。他们也坚信，任何数学真理，只要通过一代又一代人的不断努力，都能用逻辑的推理将其整合到数学的大厦中。
这是何等的气魄！这是何等的梦想！
但就在演讲前夕，他的同胞哥德尔，作出了一个断言，彻底打碎了这个梦。
[b]希尔伯特计划[/b][img]http://www.bullock.cn/blogs/songshuhui/files/2-35.jpg[/img]
希尔伯特
希尔伯特是一位名副其实的数学大师，有人将他称为“数学界最后一位全才”，他看待数学的眼光也是相当深刻的。
师从林德曼，希尔伯特在23岁便以一篇关于不变量理论的论文跻身数学界。他的证明方法在当时相当具有争议性。
在这篇论文中，他使用了非构造性的证明，也就是说他只能证明某个数学对象的存在性，却无法将它具体指出。比如说，一个报告厅有100个座位，有99位听众进去了，我可以断定一定有一个空座位，这就是一种非构造性证明。但我没办法将具体的空座位指出来，希尔伯特也无法具体构造所要证明的对象，所以当时也受到了一些数学家的批评。
另外，他的证明依赖于对无穷的对象使用排中律，从而遭到了不少人的质疑。
排中律，说的就是一件事非真即假，这再明白不过了，为什么还有反对的意见呢？
比如说这样一个命题：π中含有任意长度的连续数字9。如果我们接受排中律的话，这个命题非真即假。但无论这个命题是真是假，我们都无法在实际上验证，因为要验证这个命题，我们都要将π无穷地计算下去，而这是不可能做到的。所以，人们对于将排中律用到这种无穷的情况仍有顾虑，因为这不是他们的直觉能掌握的范围。
我们不知道是否因为这件事，希尔伯特动起了为整个数学寻求一个坚实基础的念头，但我们可以知道，在经过多年在不同数学领域富有成果的涉猎后，希尔伯特将目光投向了整个数学。对平面几何学的严格公理化可能是他在这方面的第一个尝试，但他的思考绝不仅限于几何。他的目标是将整个数学体系严格公理化，然后用元数学——证明数学的数学——来证明整个数学体系是坚实的。
为了这个目标，他制定了著名的希尔伯特计划。
首先，将所有数学形式化，让每一个数学陈述都能用符号表达出来，让每一个数学家都能用定义好的规则来处理这些已经变成符号的陈述。这使数学家可以摆脱自然语言的模糊性，取而代之的是毫无含糊之处的符号语言。比如说，我们如果想说“存在一个集合是空的”，我们就必须解释什么是存在，什么是空，等等。但如果用符号表达这句话的话，就成了：[url=http://songshuhui.net/wp-content/uploads/2009/09/axiom.gif][img=84,21]http://songshuhui.net/wp-content/uploads/2009/09/axiom.gif[/img][/url]，这就毫无含糊之处了。
然后，证明数学是完整的，也就是说所有真的陈述都能被证明，这被称为数学的完备性；证明数学是一致的，也就是说不会推出自相矛盾的陈述，这被称为数学的一致性。完备性保证了我们能证明所有的真理，只要是真的就可以证明；一致性确保我们在不违背逻辑的前提下获得的结果是有意义的，不会出现一个陈述，它既是真的又是假的。
最后，找到一个算法，可以机械化地判定数学陈述的对错，这被称为数学的可判定性。
如果这个计划完成了，那意味着什么？首先，一致性是很重要的，因为我们不能接受比如说“哥德巴赫猜想既对又不对”这样的结论，一致性就保证了自相矛盾的情况不会出现。在保证数学的一致性这个前提下，我们又有数学的完备性，也就是说只要是真的都可以证明。这其实就是说，对于任意一个数学猜想，不管它有多难，只要假以时日，通过一代又一代人的努力，总是可以知道这个猜想对不对，并且证明或否定它。换句话说，我们知道，在数学中，通过逻辑，我们必定能知道我们想要知道的东西，这只是个时间问题。
我们必须知道，我们必将知道。
这是个雄心勃勃的计划，但希尔伯特并不认为这是不可能的。他提出，先在基础的数学系统进行这样的形式化，然后再将其推广到更广阔的数学系统中，最后实现整个计划。于是，整个计划便归结于在算术系统中进行这样的形式化，并且在它的内部证明它的完备性、一致性和可判定性。算术系统可以说是非常基础的，我们做算术，对自然数做加法、乘法和数学归纳法，就都用到了这个系统。但我们平时只是凭直觉来理解这个系统，而数学家追求的是用逻辑的方法来定义它，这样他们才会觉得安心。
这似乎不太困难。算术系统并不是一个很复杂的系统，它早在1889年就被皮亚诺归结成一个有5条公理的系统，其中只有最后一条数学归纳法公理比较复杂。我们可以想象，希尔伯特本人也认为这是可以解决的问题。他将算术公理系统的相容性列入了他那23道希尔伯特问题中，位列第二，希望20世纪的数学家能给出一个证明。这份1900年写出的问题表，后来证明是相当具有前瞻性的，即使情况并不一如希尔伯特预计的那样。
1931年，仅仅在他退休一年之后，希尔伯特第二问题即告解决，尽管解决的方式是希尔伯特所没有预料到的。
逻辑弄人。
[b]哥德尔不完备性定理[/b][img]http://www.bullock.cn/blogs/songshuhui/files/3.bmp[/img]
哥德尔
可以说，哥德尔粉碎了希尔伯特计划。
在希尔伯特退休之时，哥德尔才刚刚登上数学舞台。在某种意义上，正是希尔伯特间接将哥德尔引领到数理逻辑这个领域的。在希尔伯特和他的学生阿克曼合著的《数理逻辑原理》中，他们提到了这样一个问题：在形式系统中，真的命题是否都是可证明的？这正是哥德尔博士论文的主题。在这篇论文中，哥德尔证明了一阶谓词演算是完备的，这就是不太著名的哥德尔完备性定理。一阶谓词演算是一种能力比较弱的数学系统，如果只是应用它的话，我们连自然数都定义不了，就更别说做算术了。自然，哥德尔的目光是不会仅仅局限于此的。
在完成博士论文之后，哥德尔便着手探索更一般的数学系统。一年后，也就是1931年，他对算术系统的探索即告胜利。这个胜利，也就是希尔伯特计划的失败。他的结论，就是哥德尔不完备性定理，一共有两个。
第一，他证明了，对于任意的数学系统，如果其中包含了算术系统的话，那么这个系统不可能同时是完备的和一致的。也就是说，要是我们能在一个数学系统中做算术的话，那么要么这个系统是自相矛盾的，要么有那么一些结论，它们是真的，我们却无法证明。
第二，他证明了，对于任意的数学系统，如果其中包含了算术系统的话，那么我们不能在这个系统内部证明它的一致性。这就是希尔伯特第二问题答案的一部分。
其实，这里“任意的数学系统”之中的“任意”并不是完全的任意。这些系统必须是可以显式地规定出来的，用数学的术语来说就是可有效生成的。但对于我们熟悉的像欧几里德公理这样的形式系统来说，这的确是相当任意了。
哥德尔证明这两个定理的武器，就是希尔伯特在他的计划中使用的武器：形式化。在哥德尔的证明中，他先将所有的数学陈述以及它们的证明用符号形式地表达出来，然后利用哥德尔自己发明的一个重要技巧——哥德尔数化——将所有这些陈述和证明变为一个个的自然数。那么，借助数学归纳公理，我们可以递归地建立针对所有自然数的陈述，而一个这样的陈述同时又是一个自然数，所以它描述了自己。换句话说，这个陈述陈述了它自己。
[img]http://www.bullock.cn/blogs/songshuhui/files/4-7096.jpg[/img]
自指
这种自指的情况，在数学上很有用，也非常凶险。它是不少悖论的源泉。第一个例子当然是说谎者悖论：“这句话是错的”。第二个就是罗素悖论，它引起了第三次数学危机，这也可以说是希尔伯特计划的一个动因。
我们来看看它的一个通俗版本，叫理发师悖论。
在一个小镇内，只有一名理发师，他在理发店门外公布了这样一个原则：只为不会自己理发的人理发。那么，他的头发谁理呢？要是他自己理的话，他就会自己理发了，那么根据他的原则，他不应该为自己理发；要是他不给自己理发的话，根据他的原则，他倒是应该给自己理发。逻辑似乎在这里失效了。
这种逻辑上的混乱局面，背后就是罗素悖论：定义一个集合，它包含所有不包含自身的集合，它是否包含自身？从上面的分析，我们可以看到，一切问题在于“包含自身”这种自指的描述。后来，在策梅洛和弗兰克等逻辑学家的努力下，通过在集合论中添加正则公理等限制，才将这种危险的自指从集合论中排除。当然，这是后话了。
这种自指的性质，尽管危险，但在哥德尔的妙手中，它就变成了证明的利器。他构造了一个命题，这个命题说的正是它自身的不可证明性。如果用类似说谎者悖论的语言来表达的话，就是：“不存在对这个命题的形式证明。”如果它是真的，那么它是不可证明的，说明系统是不完备的，因为存在一个真的而又不可证明的命题。如果它是假的，那么存在一个它的证明，这样它应该是真的，说明系统是自相矛盾的、不一致的。这就是哥德尔的第一个不完备性定理：如果有自然数的话，完备性和一致性不可得兼，这个系统要么自相矛盾，要么存在不能证明也不能否证的命题。
然后，我们来仅仅考虑一致性的问题。假定系统是一致的，也就是说不会自相矛盾的，那么我们刚才提到的命题就是不可证明的。如果我们能在系统内部证明系统的一致性的话，我们就相当于在系统内部证明了那个命题，这与不可证明性是矛盾的。也就是说，我们做了错误的假设：能在系统内部证明系统本身的一致性。由此，哥德尔证明了他的第二个不完备性定理。
他的这两个不完备性定理，对于希尔伯特计划是个沉重的打击：计划的第二步被证明是无法实行的。如果我们假定数学不会自相矛盾的话，我们就必须承认数学是不完备的，也就是说有这么一些数学命题是不可判定的：我们既不能证明它们为真，也不能证明它们为假。但很多数学家仍然认为，这并不威胁数学的正常发展，因为他们觉得有意义的数学命题极不可能是这样的。换句话说，数学家们仍然相当乐观。
同样是哥德尔，这次连同科恩，给这些数学家敲响了警钟：数学家研究的“有意义”的数学命题也可能是不可判定的。他们解决的又是一个希尔伯特问题：由康托尔提出的连续统假设。这个问题位于列表之首，是一个纯粹的集合论问题。哥德尔证明了连续统假设和策梅洛-弗兰克集合论是相容的，也就是说二者之间没有矛盾；科恩证明了从策梅洛-弗兰克集合论出发不能证明连续统假设。这两个结果综合起来，其实就说明了连续统假设在策梅洛-弗兰克集合论中是不可判定的。要是你知道策梅洛-弗兰克集合论正是解决第三次数学危机的武器和现代数学的逻辑基础，你就会明白这到底意味着什么。
哥德尔的魔鬼第一次露出了真面目。希尔伯特第一问题竟然就是不完备性定理中预言的那类不知真假的怪异命题的一个实例，这实在令人泄气。
既然希尔伯特计划的第二步都被证明是不可行的，那么第三步也就没有必要继续下去了。第三步是寻求一个能机械证明所有数学定理的程序，著名的停机定理也否定了这种可能性。停机定理的证明相对比较简单，也是利用自指的技巧，证明这样程序是不可能存在的。
至此，希尔伯特那宏伟的计划宣告全盘失败。
有些事情，我们确实不知道，即使对于数字，这是逻辑说的。
[b]余波[/b]既然对全部数学真理进行形式化是不可能的，数学家们只好退而求其次，尝试形式化他们熟悉的数学。法国的布尔巴基学派在这方面似乎走得最远。这是在巴黎高师的一帮数学家，继承了希尔伯特的一些理念，目标是将所有已知的数学在集合论的坚实基础上重建。他们出版了九本这方面的专著，每一部都以严密的公理化方法吸引着后来者的目光。他们的每本著作都会经过多次的修订，据说明年他们又会出版一本新修订的著作。
[img]http://www.bullock.cn/blogs/songshuhui/files/5-3859.jpg[/img]
布尔巴基办公室门牌，fwjmath拍摄
令希尔伯特在天国的灵魂有所安慰的是，算术系统的一致性被证明了。这个证明用到了不在算术系统内的超限归纳法，它可以被视为一种加强版的数学归纳法，是用在无穷序数上的。这其实就假定了策梅洛-弗兰克集合论的一致性。当初康托尔建立无穷集合论时，曾遭到不少人的攻击，这时希尔伯特挺身而出，为康托尔和他的无穷集合论疾呼：“没人能将我们从康托尔创造的乐园中赶出来。”如今，康托尔的无穷集合论衍生出来的超限归纳法反过来又部分实现了希尔伯特的梦，这是冥冥之中的安排，还是希尔伯特的敏锐眼光所致？恐怕没人能说得清楚。
但哥德尔的魔鬼仍在肆虐。越来越多的数学问题被证明是不可判定的，这些不可判定的问题也越来越初等。乍看起来并非不可捉摸，但到头来却不可判定。比如说，如果我们用可数种颜色对每一个实数染色，是否必定存在4个互不相等的数a,b,c,d，使得它们的颜色都相同，而又满足a+b=c+d？这看起来怎么也不像没有一个确切结论的问题，但有人证明了它实际上和连续统假设的否定是等价的，也就是说，在策梅洛-弗兰克集合论内，它也是不可判定的。这就给数学家们心头压上了一块大石：谁也不知道自己辛辛苦苦做了十几年的题目，会不会突然有一天被证明是在现有数学体系中不可判定的。
尽管这样，哥德尔的不完备性定理仍然带给我们很多教益。至少我们知道了，有些东西我们不可能知道。在哥德尔的这个划时代的证明之后，数学家对数学的基本工具——证明——有了新的认识。专门研究数学证明的证明论，在他的启发下蓬勃发展。但是，哥德尔教给我们最重要的一点是：
数学，如同人生，如同爱情，有些东西是真的，你却永远无法证明。
作者简介：[url=http://songshuhui.net/archives/author/fwjmath/][color=#217fbf]fwjmath[/color][/url]学的是数学，没啥好说的，大家随意。
© 本文来自科学松鼠会[url]http://songshuhui.net[/url]，转载请注明出处。.