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

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

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

第二重：“静水流深”——“哥德尔不完备定理”的深刻背景

哥德尔为什么会想到证明这样一个“不完备定理”呢？既然已经修炼到第二重了，就稍微说的多一点。

（一）数学公理化

人们经常说，数学研究领先其他学科研究至少200年。其实在上上个世纪，也就是19世纪的时候，数学研究就已经大幅度超前于其他学科的研究了。数学家以及很多科学家们越来越意识到数学应该是一个公理化的系统，它的结构应该是这样的——首先定义一批公理和基本逻辑规则，然后依据这些公理和逻辑规则可以推演出这个体系内的无穷多的定理——这就应该是理想的数学。

倡导并推进数学公理化的最主要代表人物就是德国数学家大卫·希尔伯特（David Hilbert），19世纪和20世纪最具影响力的大数学家之一。希尔伯特的影响力主要体现在他于1900年在巴黎举行的第二届国际数学家大会上作的题为《数学问题》的演讲。在这个演讲中，希尔伯特提出了23个他认为最重要的数学问题，而这23个问题至今还在指引着数学家的研究方向。

这23个问题中的第2个问题，就是有关数学公理化的。希尔伯特说：“在这些无数个问题之上，我倾向于确定下面这个问题才是最重要的：这些公理在经过有限步骤的推演后是不会导致相互矛盾的结论的。……也就是说，我们需要一个关于算术公理一致性（相容性）的证明。”。

1910～1913年，怀特海（Alfred North Whitehead）和罗素（Bertrand Russell）撰写的《数学原理》（《Principia Mathematica》）的发表，是数学公理化推进的又一里程碑事件。《数学原理》希望从最基础的逻辑出发来定义全部数学，试图构建一个宏大的逻辑体系结构，彻底的解决数学公理化的问题。我们只要稍微想象一下，就能够猜到这个过程有多复杂，特别是罗素还要在这个过程中消除自己发现的“罗素悖论”（后面会提到）。直到《数学原理》第一卷的363页，才推导出了数字“1”的定义；第二卷又费了很大的力气，证明了乘法交换律。《数学原理》工程浩大，两位作者只完成了前三卷，覆盖了集合、基数、序数和实数的相关内容，虽然对第四卷几何的基础做了筹划，但整个体系结构实在太过复杂，两位作者“才智枯竭”^[2]，实在无法再写下去了。

数学公理化推进的最关键标志性事件是1920～1923年间，希尔伯特推动的“希尔伯特计划”。这个计划的主要目标，是为全部的数学提供一个安全的理论基础。这个计划对数学公理化提出了如下要求：

• 形式化：形式化是希尔伯特提出来的一个关键思想，意思是，所有数学应该使用用统一的、严格的、无意义的、形式化的语言来表述，并且按照一套严格的、基础的逻辑规则来推演。

• 完备性：形式化之后，数学里所有的真命题都可以通过上述规则被证明。

• 一致性：运用这一套形式化的表达和规则，不可能推导出矛盾。

• 保守性：这是针对形式化而言的，即如果赋予一些形式化的表达以含义（希尔伯特将这称为元数学），并由此证明了某些结论，那么必须保证即使不赋予这些含义，依然可以证明同样的结论。

• 确定性：可以通过一个算法来确定每一个形式化的命题是真还是假。

对于修炼完成了“哥德尔不完备定理”第一重神功的读者来说，应该会看出上述“希尔伯特计划”是有问题的。没错，之所以我们比大数学家希尔伯特还要目光如炬，是因为我们站在哥德尔这个巨人的肩膀上！要知道，在哥德尔的论文发表之前，甚至是发表之后的一段时间，主流数学家、逻辑学家们仍然认为希尔伯特计划毫无疑问是正确的，问题只不过是如何给出证明罢了。

（二）一致性（相容性）的重要意义

在详细阐述“哥德尔不完备定理”对数学公理化特别是“希尔伯特计划”的影响之前，我们先来谈一下“一致性”的重要意义。这里说的“一致性”就是指很多文章或书籍里面说的“相容性”，希尔伯特说的compatibility，哥德尔说的consistency，意思是“无矛盾的”。

在修炼第一重神功的时候，我们谈到构造一个不一致（不相容、存在矛盾）的公理体系是无意义的。从直觉出发，我们都清楚，存在矛盾的体系当然有问题了。这里，我们给出逻辑上的说明（或者说证明）。

做这件事之前，让我们先来感谢罗素和怀特海，是他们的艰苦工作成果《数学原理》给出了数学形式化的基础。我们正是以此为基础，来说明一致性的重要意义。另外，了解《数学原理》中给出的数学形式化的基本表示，也是继续修炼第三重、第四重神功的基础，因为哥德尔就是基于《数学原理》中数学形式化的表达来证明“哥德尔不完备定理”的。

由于形式化表达的符号存在不同的样式，为避免歧义，本文中数学形式化的表达与哥德尔论文中的样子保持一致。以下是数学形式化的基本原则：

（1）使用字母（一般使用p、q、r等）表示命题变量，即一个字母表示一个命题；使用如下符号表示特定逻辑（注意，形式化之后的表达式是无含义的，因此这些符号仅表示某种逻辑关系）：

～        逻辑“非”；

∨        逻辑“或”；

⇒    逻辑“推出”，意思是“如果……那么……”；

∧        逻辑“与”；

∀x∙p   对于任意x，p都成立；

∃x∙p   存在x使p成立；

（2）组成合理的命题表达式。譬如，“p∨q”就是一个合理的命题表达式，而“p∨”就是一个错误的表达式。

（3）两条变换规则：一是代入规则，可以使用其它的命题表达式对某个命题表达式中的某个命题变量进行全部统一替换；二是分离规则，其实就是我们常说的逻辑三段论，已知p和p⇒q成立，则q成立。

（4）《数学原理》提出的四条基本逻辑推演公理：

(p∨p)⇒p

p⇒(p∨q)

(p∨q)⇒(q∨p)

(p⇒q)⇒((r∨p)⇒(r∨q))

大家可能觉得这四条基本逻辑推演公理看起来像是废话，由此可知《数学原理》这本巨著是从多么基础的逻辑出发的。不要小看这四条基本推演公理，它们可以推导出难以想象的复杂的结论。

好，以上四条数学形式化的基本原则叙述完毕，下面开始推出一个逻辑定理：p⇒(~p⇒q)。推演过程如下：

根据第二条推演公理，得到p⇒(p∨q)；

根据变换规则二，设p成立，则得到如下结论，

p∨q成立；

在p成立的前提下，设～p成立（即p不成立），则由∨逻辑的基本含义得到q成立（意思就是，“p或q”成立，且p不成立，那么必然q要成立）；

根据上述结果，在p成立的条件下，如果～p也成立，那么q成立。

于是得到上面的逻辑定理p⇒(~p⇒q)。注意，这里面q是一个自由的命题变量，根据基本变换规则一，可以把任何命题代入q。因此，我们得到了一个重要结论，如果有一个命题“p”和它的逻辑非“～p”都成立，那么任意命题q都成立。也就是说，有矛盾的公理体系可以推导出任意命题都成立。这就是为什么公理体系必须一致，不一致的公理体系为什么无意义的原因了。

（三）数学形式化的目的

在谈完了“一致性”的意义后，我们还要再谈一下为什么希尔伯特要搞数学形式化？希尔伯特是提出数学形式化的代表人物，他提出数学形式化的目的还是从证明“希尔伯特第2问题”出发来考虑的。人们之所以笃信公理体系必然是一致的、无矛盾的，其实是因为人们日常研究并应用的公理体系都是有含义的，都是对应着客观实体的。人们相信客观实体及其规则是不会发生矛盾的。这正像我们中国成语“自相矛盾”故事所说的，一个无坚不摧的矛和一个无比坚固的盾在现实世界是不会同时存在的，只要用这个矛刺一下这个盾，就会有一方露馅。可是我们的公理体系不总是对应着存在的客观实体，很多情况下（特别是数学中）的公理体系对应着抽象实体或者理想实体（如集合、点、线、面），而且被对应的实体是无穷多的，我们无法通过有限枚举来证明这些公理体系的一致性。

由此，希尔伯特想到，彻底抛弃（数学）公理体系中的含义，构造一个形式化的公理体系，这个体系内的各种表达式仅仅具有符号意义。如果能由此证明这样的公理体系的一致性，那么无论把任何含义赋予这个公理体系时，必然是无矛盾的、一致的了。

正是由于希尔伯特这个想法，以及罗素和怀特海的“身体力行”，才使得哥德尔最终发现了不完备定理。否则，人们在研究公理体系的时候，总会把它对应的含义和其逻辑关系一起考虑，就不太容易把思路聚焦到公理体系的逻辑本身上面，也就不容易发现“哥德尔不完备定理”了。

（四）“哥德尔不完备定理”打破了“希尔伯特计划”么？

最后让我们再回到“哥德尔不完备定理”，看看哥德尔是如何在数学公理化（以及公理体系形式化）的大背景下“釜底抽薪”的。我们先来看“希尔伯特计划”的几个要素：

一是形式化。显然，“哥德尔不完备定理”并没有反对形式化，而且正是通过《数学原理》中公理体系形式化的成果，哥德尔才证明了不完备定理。

二是完备性和一致性。“哥德尔不完备定理”明确指出了公理体系完备性和一致性的矛盾之处，它证明了一致的公理体系（指蕴含皮亚诺公理的公理体系，以下类似，不再赘述）必然是不完备的，也就是说，完备性和一致性不可能同时获得。另外，“哥德尔不完备定理”还有一个推论，一般被叫做“哥德尔第二不完备定理”，它表明公理体系的一致性不能在这个公理体系内被推导出来。也就是说，不仅完备性和一致性有矛盾，即使是一致性本身，也不能在公理体系内得到证明（这个结论似乎显得更可怕）。

三是保守性。事实上，保守性也不再成立了。在“哥德尔不完备定理”的详细证明过程（第四重）和“Goodstein定理”介绍（第五重）中，我们就可以发现，当赋予了某些含义给公理体系之后，原来不可证明的命题变得可证明了。个人认为，赋予含义的过程本身就是在扩充这个公理体系（个人观点，可讨论）。这也是为什么哥德尔构造的forall(v,r)这个命题在《数学原理》确定的逻辑基础和皮亚诺公理体系内不可通过形式化的推演而证明，但是却在哥德尔的论文中被证明了的原因。哥德尔论文中也提到了，provable(x)是他构造的46个表达式中唯一个不能断言为原始递归性质的，这说明命题的“可证性”某种意义上是被哥德尔新赋予的含义。

四是确定性。显然确定性也不成立，因为哥德尔证明了存在某些命题无法证明其真假。而且就算在确定性判断的“真”和“假”以外加入“不可证明”这一类，也是不成立的。我们前面提到过，没有一个通用的算法能够判定任意命题是否不可证。

从上面这些要素来看，除了公理形式化没有问题外，其他要素都存在问题，要么互相矛盾，要么根本不成立。从这个意义上讲，“希尔伯特计划”确实被打破了，这也是当年“哥德尔不完备定理”最重大且最直接的影响。

“哥德尔不完备定理”发表时，希尔伯特还在世，面对这个伟大成果，大数学家希尔伯特也只能退让，不过只是略微退让。毕竟哥德尔只是在某一个范畴内（皮亚诺公理体系+原始递归性质）构造出了一个在公理体系内不可证明的命题，剔除这个范畴之后，结果又会是怎么样的呢（第五重）？

无论怎样，我们必须指出希尔伯特“为全部的数学提供一个安全的理论基础”这个目标并没有被打破，通过不断扩展公理体系，我们仍然可以为数学提供一个越来越安全的基础，只不过这个公理体系结构看起来要从原来的“有限”变为“无限”了^[3]。

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