哥德尔不完备性定理

在ZF系统的影响下，希尔伯特用公理化方法写出《几何基础》一书之后，于1922年着手制定著名的“希尔伯特纲领”，即一个使数学中永远消除悖论的方案.他的基本思路是：

（1）先把古典数学的内容公理化进而形式化，使之成为用形式符号和符号序列组成的系统，并用TF表示;

（2）用有限方法证明TF的无矛盾性;

（3）在TF中不会有某个命题A，使A与非A可以同时推出.

这里要特别说明一下（2）中关于有限方法问题：由于古典数学的无矛盾性问题是由实无限引起的，古典的逻辑演算也假定了实无限.所以，如果仍然使用以实无限为前提的思想方法或工具去论证古典数学的无矛盾性，会犯循环论证的逻辑错误. 希尔伯特所用方法的特点是：

（1）每一步只考察确定的有限数量的对象，只承认潜无限;

（2）全称命题表达的规律对其中每一个具体对象都必定是可以验证的;

（3）对于存在性判断必須直接给出一个特定对象，或给出一个其步骤有特定界限的方法来得到那个对象（因此排中律对涉及无限的命题不能用）;

（4）只能有限制地使用数学归纳法.

当这一纲领在当年出炉之后，不少数学家立即着手开展工作，并很快取得成绩.意大利数学家皮亚诺以五条自然数公理为出发点，为算术理论形式化奠定了基础.他证明了只含加法的算术公理系统是无矛盾的.

希尔伯特在三年后出版的《论无穷》一书中信心十足地说：“每一个明确的数学问题，必能被正确地解答，因为在数学中没有不可知的.”

1930年，他又在《数学基础》一书中更明确地提出：“我力图用建立数学基础的办法达到一个有意义的目标，这种方法可以恰当地被称为证明论.我想把数学基础中所有的问题按照其现在提出的形式一劳永逸地解决.换言之，即把每一数学命题都变成一个可以具体表达的和严格推导的公式.经过这样改造的数学所推导出来的结果就会无懈可击，同时又能为整个科学描绘一幅合适的景象.我相信我能用证明论达到这一目标.”

虽然如此，只要回忆数学中四大学派之间的激烈争论，我们就不难发现，数学的相容性和完备性作为公理化进程中必须解决的两大问题仍在继续困扰着早已名不副实的“数学共同体”.

就在持有各种不同观点的数学家们为数学的基础问题展开激烈争论，形式主义的领军人物希尔伯特满怀信心打造他的“证明论”，并确信他的“元数学”和证明论将成功地确立全部数学相容性和完备性的时候，奥地利旅美数学家哥德尔于希尔伯特发表上述言论的当年9月，在哥尼兹堡的数学研讨会上公布了他的研究成果：数论相容的形式系统的不完备性.其中一个核心定理，被后人称为哥德尔不完备性定理.该定理的推证过程写在哥德尔的代表作《论数学原理和有关系统I的形式不可判定命题》中.定理向人们揭示出，在任何包含初等数论的相容的形式系统中，存在不可判定命题，即该命题和它的否定命题在这一系统中都既无法证其真，也无法证其假.由此又可推出：一个包含初等数论形式系统的相容性，在该系统内也是不可证明的.这一结论作为前一定理的推论常被称为哥德尔第二定理.

正当数学家们全神贯注地期待数学大师希尔伯特“一劳永逸地解决”“数学基础中所有的问题”时，出现了这种严重危及基础的事，后果是可以想象的.哥德尔的论文发表后，在数学界引起强烈震撼，它无异于证明了数学中魔鬼的存在.使刚刚结束第三次数学危机后心情略为舒畅的数学家们，又不得不面对一场更为严峻的挑战.

哥德尔在证明他的不完备性定理时，创造性地使用了一种将信息转换成数值的技巧和方法： 他首先将逻辑主义和形式主义者们在数学方法中使用的所有符号、符号的顺序及构成证明的命题或命题集合都统统与自然数对应起来.方法是先为每个数学对象、概念或关系指派一个自然数：比如1指派给1，2指派给等号，3指派给集合的属于符号，4指派给2，5指派给加号，……于是符号串1+1=2就变成了1，5，1，2，4，相应取出最小的5个素数2，3，5，7，11，由此可以得到 21·35·51·72·114=1743303870 ，再将自然数1743303870指派给“1+1=2”，如果注意到该数只能唯一地被分解，便可知从它开始，原路返回必可得到1+1=2.即是说在“1743303870”与“1+1=2”之间建立了一种对应关系，显然这种对应是“一一对应”.我们把用这种方法得到的数称为哥德尔数.类似地，不仅被考察的系统中每个公式有一个哥德尔数，而且对构成证明的整个公式序列，也可得到一个哥德尔数，该数的各个因数的指数正是每个公式的哥德尔数（底数均为由小到大的各个素数）.显然，这一过程是可逆的.

哥德尔正是在上述基础上一步步深入展开其工作的：他一方面使形式系统中“元数学”的任何断言都有指派给它的哥德尔数，另方面每个这样的数又是某个算术语句的哥德尔数.这样，“元数学”便被映射为算术.接下来再在算术论断中去寻找对应于某个哥德尔数的命题是不可证的元数学语句.哥德尔不仅证明了这种命题可以构造出来，而且还可以通过形式系统允许的更为直观的推理来确认它是真命题.由此得出结论，该命题从属的形式系统如果无矛盾，则必定不完备. 仔细分析后不难发现，哥德尔处理这一问题时，采用的基本逻辑方法是：对于命题A：A不可证.则A与非A都不可证.原因是： （1）A不能为假.因为，若A为假，即“A不可证”为假，故A不是不可证，这与假命题不可证相矛盾，故A为真; （2）A不可证.因为，若A可证，则“A不可证”为假，即A为假，与（1）中证明的“A为真”相矛盾; （3）由（1）知A为真，故非A为假，即非A不可证. 根据（2）与（3）知A与非A均不可证.

其实，这种面临两难选择的问题，早在古希腊时期就提出并讨论过.当时有个著名的“柏拉图非存在之谜”，讲的是有关诗神缪斯坐骑的事： 缪斯的坐骑是一匹飞马，象征着诗的灵感.柏拉图问：“飞马存在吗？”实事求是讲，飞马并不存在.故答曰：“飞马不存在.”但谈论一个不存在的东西是荒唐的，所以谈论飞马的不存在性是不能成立的.既然“飞马不存在”不成立，那么“飞马存在”.但飞马并不存在，所以“飞马存在”也不成立.

数学家E·拿盖尔认为：“按照哥德尔的不完备性定理，在初等数论中，有着无穷无尽的这种问题类，对于它们中的任何一个，无论计算机的构造机理多么复杂，运算速度多么快，也不可能给出答案.” 哥德尔以十分锐利的目光深翻了数理逻辑这片土地，揭示出即使费九牛二虎之力也无法全面实现希尔伯特纲领的根本原因.

直到19世纪末，人们还以为数学与公理化了的各分支的总和具有相同的广度.但根据哥德尔不完备性定理可知，不仅数学的全部、就是数学的任何一个系统也不能用可以算术化的公理系统来概括.因为在任何这样的公理系统中，始终存在可以用非形式的论证证明其正确而在系统内部无法证明其正确的有意义的命题.换言之，任何这样的公理系统都是不完备的，公理化的能力存在致命的局限性. 哥德尔得出的又一结论是：数学系统的相容性也不能证明.即使用任何数学方法都不可能借助安全的逻辑原理证实该数学系统的相容性.这意味着我们期望的数学结论的确定性和有效性实际是不存在的.数学家们随时面临传播谬误的危险，说不准哪一天，在数学中突然冒出一个矛盾来.而且这种情况一旦出现，就等于说全部数学都变得毫无意义.因为早已被所有数理逻辑学家认可的“蕴涵”这一概念允许从一个假命题推出任何命题来.

哥德尔在1940年以后发表的论文，给数学带来了新的、更大的震撼.他证明了在策梅罗—弗兰克尔系统中，连续统假设和选择公理都不能被证伪.沿着他的方向，数学家柯恩又证明了，在这一系统中连续统假设和选择公理都是不可判定的. 数学的发展似乎以惊人的相似回到了非欧几何诞生前夕那个混乱的年代.它面对着多个发展方向，但数学家们又不知道往哪个方向走去为好. 看来，一方面，哥德尔定理是逻辑学和数学在现代发展中取得高度成就的前提下產生的.没有形式化的高度发展，不会有哥德尔的成就;另一方面，哥德尔定理的出现又突显出形式化的局限性.哪怕是早已在我们思想中根深蒂固的自然数的相关理论，也无法用一个形式系统对其进行完整的刻画.

冯·诺依曼在1951年授予哥德尔爱因斯坦勋章时说：“哥德尔在现代逻辑方面的成就是无与伦比的、不朽的——确实，它们不只是一座纪念碑，而且是一座其意义由于受时间、空间限制还远未显现的里程碑……由于哥德尔的成就，逻辑科学已完全改变了它的本性和发展前景.”

无论是逻辑主义、形式主义、还是集合论公理化者，都受到哥德尔理论的沉重打击.因为，他们都崇尚公理化，但公理化却是靠不住的.当然，也不排除找到一种优于这几大学派所使用的逻辑原理和为这些原理所允许的更好的方法的可能性，但无论怎样，直到现在都尚未在研究前沿出现找到这种原理或方法的迹象. 似乎只有直觉主义者在暗暗高兴，因为他们认为人的直觉能保证相容性，哥德尔的结论等于进一步证明了直觉的可靠性超出了数学的证明.直觉主义者的确在满怀信心地思索着数学的未来，但凭他们的“直觉”真能看透并揭示数学领域中发生的一切吗？！真能解决数学中所有问题和矛盾吗？

对于一个特定的断言，并非总能找到一个算法判定它是否可以证明.看来，连续统假设也许不能证明，哥德巴赫猜想也许不可判定，无穷小量或许并不存在，集合论不可能无条件公理化……

“事物内部存在的矛盾性是推动事物前进和发展的动力”，从这个意义上讲，哥德尔定理的出现，只会给数学的发展注入新的活力.