在大学时，我听到一个匪夷所思的定理：哥德尔用数学证明了，数学里有不能被证明的定理。这充满矛盾离奇的说法超越了我的想象，但让我记住了这个名字，一直到几十年后，有了足够的基础，我才了解他是怎么说的，如何证明这个革命性的定理。

现在互联网可以很方便地得到信息，从网上很快能了解到哥德尔定理（Gödel's Theorem）的严谨陈述【1】，但是进一步的解读往往似是而非，一些推论或反驳多是从字面上的联想和发挥。这个理论是如此地刺激人，逻辑又很纠缠，游走在形式和含义的相接之处，最常被误用和责难。对于数学定理的理解最好是了解它的观念及核心逻辑，这样才能知道定理陈述的准确含义，才能合乎逻辑地推论。这系列关于哥德尔定理证明的几篇博文，基本按经典的普及本Ernest Nagel & James Newman《Gödel's Proof》【2】的思路，揉合后续研究的补充。直指基本概念、思路和核心逻辑，引导读者思考，逐篇细化深入，而不过分拘泥细节的严谨性，因为它的正确性已由原来的研究来保证的。希望用四五篇的短文，让有理工科基础的读者能领会精神，数学、计算机和哲学专业了解数理逻辑的读者，能够消化这个证明。

自从牛顿用物理的直觉，闯进无穷领域里大胆计算，铸造出犀利无比的分析工具后，许多人凭借着直观想象和聪明，也涌进去推导出许多互相冲突的结论，数学家花了两百多年的时间，才厘清了分析领域里的混乱，将整个数学建立在严格逻辑，而不是直观想象的基础上。欧几里德几何一直是科学理论的范本，四条自明性的公理加上一条平行公设，通过逻辑演绎，推导出平面几何无穷数量的定理。一直到了近代还只有几何，被认为是具有坚实基础的数学分支。在这光辉的榜样下，人们尝试用这公理化的方法来规范整个数学。人们后来发现欧几里德也不够严谨，逻辑上的漏洞得以修补，但追到极致，要依赖于“数”的理论。

自然数的算术运算是数学的最基本的内容，自然数的性质曾经被中国先哲看成天道的机密，古希腊人作为宇宙的根本，在笛卡尔的哲学沉思里，认为我们无法判断自己是清醒还是幻觉，但在这两者中，2+3=5都是永远不变的真理。1889年意大利的数学家Peano用几条公理（皮亚诺算术公理Peano arithmetic axiom，简记为PA）【3】抽象地定义了“自然数”，“相等”，“直接后继”和数学归纳法的概念，从而能够用一阶逻辑演绎出整个自然数的算术系统，对应着包括通常的加法、乘法、质数等数论的定理。这样的客观世界真理，竟可以从一组有限的假设出发，描写成符号的式子，抽去了客观世界上的含义，不再依赖它们所代表对象的真实性来验证，只是用一组固定的操作规则，将字符串按照规则变换得出新的字符串，便产生出能够对应于客观世界真理的表达式。这个机械化的信念吸引了很多数学家。

在这个运动的高潮时，罗素和怀特海在1910-1913年出版了三卷的《数学原理》，他们自信已将全部的数学建立在纯逻辑的基础上，为今后的所有数学打下了坚实的基础。1920年，当时数学界领军人物希尔伯特，提出一个计划，根据《数学原理》的思想，将所有的数学形式化，称为形式公理系统（formal axiomatic system），在这里用精确的形式符号语言来叙述数学命题，根据形式逻辑的规则来操作这些字符串的变换和生成，称之为“形式证明”。这个系统如果有完备性（completeness），相容性（consistency），保守性（conservation）和确定性（decidability），数学研究从此不再需要创造性的工作了，一切定理的发现和证明，归结为在这个形式公理系统下的机械运算。【4】

这个形式公理系统计划，关键的一个环节是相容性的绝对证明。相容性（consistency）指系统不能产生自相矛盾的结论。过去所有科学理论的相容性，实际上并没有得到过逻辑的证明，结论依赖于客观的经验来验证。客观的事实是确定的，不矛盾的，这保证了结论的相容性。欧几里德几何虽然以公理化的方式，用逻辑推出所有的定理，它依赖这些公理是自明的，即符合直觉，也就是符合实际的空间经验，所以认为是真理。但这在逻辑上是不完全的。直觉只是经验的印象，怎么保证没有想象之外的事实？希尔伯特用笛卡尔坐标的解析几何，将欧几里德几何的相容性，用代数系统的相容性来保证，但代数系统的相容性该怎么得到保证？这仍然没有得到最后的解决。希尔伯特认为必须构建“绝对”的证明，即这个系统的相容性不再借助其他系统来保证，在抽去具体含义的形式化系统中，相信这个只包含逻辑结构和功能的系统，容易在一览无遗中寻找各个命题字符串之间的逻辑规律，而不需要依赖于不可靠的直觉和经验，从而来证明相容性，这个证明希望只用到有限次推理，每次只用到有限个数学的对象。

1931年，就在大家为这数学毕其功于一役做努力时，25岁的数学家哥德尔发表了一篇论文“论《数学原理》及相关系统的不可判定命题”。让这雄心勃勃的希尔伯特计划成为泡影。哥德尔根据《数学原理》构造出一个简单的包含着皮亚诺算术公理的形式演算系统，称之为PM。哥德尔定理有两个结论，这结论对任何包含有自然数加法和乘法的形式公理系统也成立：

1.  PM如果是相容的（consistent）则是不完备的（incomplete）。

2.  PM不能证明自身的相容性（consistency）。

解释一下这几个关键词。

相容的（consistent），或者译为“一致的”或者“自洽的”，意思是说在这个系统里不能推出互相矛盾的结论。因为，若有一对相反的命题（比如说a=b和a≠b）同时为真，那么由它们可以合乎逻辑地推出任何命题（为真）。所以数学系统只有是相容的才有价值。相容的系统里至少有一个命题不能被证明（为真）。

完备性（completeness），指所有的真理（语义上为真的命题），都能在这个系统里被形式证明（从系统里的定理或公理，按照形式逻辑的方法通过有限步骤推导出来）。Incomplete有时中文翻译成“不完备“或者“不完全的”，就是说有些真理不能在这个系统里被证明。

这是数学里最具有革命性，也最让人沮丧的定理，它告诉我们公理化固有的局限性。哥德尔虽然只证明了在那个包含有PA的简单PM系统，但是它适用于任何包含自然数加法和乘法的数学系统。又有哪个足够大的数学系统不包括这算术运算？

哥德尔是数学家和逻辑学者，在琢磨这个提供了严谨的形式逻辑基础，将数学命题形式化的《数学原理》时，他发现了一个秘密，这形式逻辑的操作与算术运算极其相似，如果将形式符号的式子对应于一个自然数，那么形式逻辑的运算就对应于算术的运算，这系统用形式逻辑来描述算术，但算术也可以来描述形式逻辑的过程，它可以合法地自己来谈论自己！这让人想起“这句话是错的”这个古老的谎言悖论。那么我们可以用《数学原理》的规则将“这个公式是不可证明的”，这个谈论数学公式的命题，形式化变成系统里的数学公式，造成一个恶性循环来摧毁这座精巧构建的纯洁的大厦。

（待续）

【参考资料】

【1】      Wikipedia，Gödel'sincompletenesstheorems http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems

【2】      《Gödel's Proof》by Ernest Nagel andJames Newman, NYU Press, 2001, 2nd edition  http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371

【3】      Wikipedia，Peano axiomshttp://en.wikipedia.org/wiki/Peano_axioms

【4】      Wikipedia，Hilberts programhttp://en.wikipedia.org/wiki/Hilbert's_program