哥德尔定理说：不存在着一个自洽的形式公理系统，能够有效地证明这里面所有的算术真理。这个系统的无矛盾性，也不可能在系统里被证明。

哥德尔定理被很多地方传述引用，表面看来是不同的说法。从上一篇的证明中，可以看出之间的联系。我们先谈内部的论断再谈外面的同类。

首先，这是针对所有包含算术的形式公理系统。形式公理系统，指用形式化的一阶谓词逻辑来描述公式、命题和证明。这些逻辑演绎通常都用在自然语言表达的数学证明中，只是用符号形式化后更加明确严密，涉及到无限时十分谨慎和限制。这系统的提法，有的说包含“皮亚诺算术（PA）的公理”或说“一阶算术”，其实指的都是同一个东西。PA是最早研究的算术公理，是能够用一阶谓词表达的公理。包含了加法和乘法的形式公理系统，必须含有算术的公理。哥德尔虽然只在PM上证明了他的定理，很容易看到，他的结论也适用于所有包含了算术更大的系统。

“相容的”（consistent，或译为“一致的”或者“自洽的”）是数学系统最基本的要求，说明这个系统推出的结论不会自相矛盾。在科学发展的初期，研究都是基于直觉和经验，逻辑偶尔点缀其间只为理解内容，人们并不担心这个问题。随着微积分踏进了无穷的领域，悖论频现，数学家们看着这迅速增长的系统忧心忡忡，唯恐有朝一日发现，这只是场终归会自相矛盾的游戏，推理出来的怕只是一面之词。为此，相容性的证明便提到日程来。

完备性（completeness，或译为“完全的”）则是要说明这个系统功能足够强大，对系统中的问题都能给个答案。这是第二位的期望。希尔伯特领导的形式公理化运动，希望如同形式逻辑系统一样，用形式化的方式，为数学建造一个严谨、清晰、相容且完备的系统。

凡是用反证法证明的，都要在相容的系统假设下才能得到结论。不相容的系统，任何命题都能得证，这是平凡的完备。在相容的系统中，不完备性与存在着不可判定的命题等价。所以哥德尔的第一个定理，称“不完备性定理”或“不可判定定理”。

有时哥德尔定理的表述中的条件是“ω-相容的”而不是“相容的”。“ω-相容的”在逻辑上是比“相容的”更强的要求。从前者可以推出后者。这是“每一个自然数都没有这性质”和“不存在着一个数有这性质”两者语义的差异，大多数人的理解，它们是相同。但是在形式系统中，因为没有一个能处理无限的规则，形式推理跨不过这个间隙。所以哥德尔的证明是用“ω-相容的”来表述。定理中“相容的”表述，是J Barkley Rosser在1936年证明的更好的结果。

为什么希尔伯特计划不包含着能够处理无限的规则？这要从“有限主义”的影响讲起。上个世纪初，一系列涉及到无穷的悖论将数学家弄得焦头烂额，有限的都是坚实可靠的，对无穷看法的分歧引起对数学基础的争论。因为无穷超越了想象，罗素提出将数学归结为逻辑，称为逻辑主义。与之对立的是直觉主义。最早的是克罗内克，他反对康托尔的实无穷，只接受整数，认为自然数是上帝创造的，直觉上清楚的。其他都是人造的，例如无理数没有一个构造方法或判定准则，不能用有限的步骤来确定，是可疑的。彭加勒嘲笑逻辑主义，认为这是将数学建立在无限的同语反复上，反对不能用有限个个体来定义的概念，用选择公理逐一从无限集合中选择是不可理解的。布劳威尔认为数学的基础只能建立在构造性的程序上，正确性和可靠性的决定是靠直觉而不是经验和逻辑。反对将有限经验总结的排中律推向无限的领域。布劳威尔和外尔只接受像数学归纳法那样，叙述进行中状态的潜无穷，反对像无穷集合和无理数那样，作为实体的实无穷。这个争论造成数学研究的分裂和混乱，直觉主义的主张将导致一批经典数学和数学分析的大部分成果失效，希尔伯特出自保卫无穷领域革命的成果，用行政手段压制了直觉主义。但是有限主义的疑虑，毕竟还是产生了影响，在希尔伯特计划里有两个原则，一是“形式化”，定义和推理抛弃了符号和规则之外的东西，形式地进行，这让数学清晰且严谨。这个形式公理化的思想被历史认同了。第二个是“有限化”，迷惘于由无穷产生的悖论，以及疑虑只凭逻辑思考不能验证之事的真实性，他希望有效的证明只用有限的步骤，每一步只涉及到有限个数学的对象。全称命题表达的规律对每一个对象都必须能够验证，存在的判断必须能给出一个特定的对象。有限制地在元数学上使用数学归纳法等等。【2】这些规则相当于原始递归的方法，被用在绝大多数能够被人认可的数学证明中。哥德尔看到“有限化”的局限性，他的定理说明，如此局限的系统必定是不完备的，甚至连自身的无矛盾性都不能证明。虽然他的证明不否定在PM之外的可能性，但对于不能映射到PM系统的“有限化”证明，还没有人知道是什么概念。【3】

哥德尔定理之后，人们关心的是，我们能够证明系统的相容性吗？有完备的系统吗？

这答案都是肯定的。逻辑系统的相容性很平凡，因为公理都是重言式，定理也是重言式了。其否定命题一定不是定理。对于包含算术的公理系统，哥德尔定理只说，在系统里不能证明其相容性，并不排斥在系统外的证明。PM的相容性，在1936年由甘岑（Gerhard Gentzen）用“超限归纳法”证明了。大多数数论逻辑家并不怀疑这个证明的正确性，但这个证明用的不是“有限的”方法，不能映射到PM中，超出了希尔伯特“绝对证明”的规定。人们最关心的是实数理论（数学分析）的无矛盾性，五十年代，日本学者将甘岑的工作推广到高阶谓词演算来探索，1967年，日本高桥元男用非构造的方法证明了数学分析子系统的相容性，由于这证明不是构造性的，数学分析的相容性至今还没有得到有效的证明。【3】

很多系统不是完备的，这并不奇怪。例如，欧几里德几何在缺乏平行公设时，显然不是完备的。关键是经过扩充后，有没有可能让它完备化。一阶形式逻辑推理系统，比如说群论等一阶系统，可以是既相容又完备的系统。哥德尔在他的1929年博士论文，证明了一阶谓词逻辑的完备性定理。【2】但他的算术形式系统不完备性定理，杜绝了以扩充来完备它的希望。

在一阶集合论的ZF系统中，由于可以定义自然数，所以也是不完备的。存在着不可判定的命题与不完备性是等价的。不从哥德尔定理出发，哥德尔1940年和Cohen1960年代的工作合起来，证明了连续统假设在ZFC集合公理系统中是不可判定的，选择公理在ZF集合公理系统中也是不可判定的。1982年美国帕里斯、哈林顿、弗里德曼相继在有限组合理论中找到既不能肯定也不能否定的关于自然数的命题。【1】【2】时至今日，人们用不同的方法，构造性了在现有系统中不可判定的一些命题，哥德尔定理得到了很好的验证。

哥德尔的贡献在科学史上是罕见的，他以一人之力在短短的几年内，对一阶逻辑系统的完备性，数论和分析形式系统的完备性，选择公理的相容性等中心问题作出明确的解答。科学在长期演化中，某种思想到了一定时期必定成熟。1931年哥德尔发表了不完备性定理。几乎在同一个时间，波兰逻辑学家塔斯基（Tarski）在1931年送交了《形式化语言中的真理概念》论文。【4】塔斯基从理论语义学或逻辑语义学角度研究形式语言，回答了类似哥德尔的问题。塔斯基认为真理的定义，所要求满足的条件是“形式上正确、实质上充分”，这后者表达为，对于理论中所有句子的一个T范式（Schema T）：φ ↔ T<φ>。就PM系统而言，这范式说：数学命题可证，当且仅当这命题在数学上是正确的。他同样构造一个自我纠缠的例子，证明了塔斯基定理：任何包含一阶算术的理论，如果有T范式，它是不相容的。

1936年英国数学家图灵研究抽象的计算模型，发表了图灵机的理论。图灵机是等价于任何有限逻辑数学过程的终极强大的逻辑机器。现代的电子计算机也可以看作是通用的图灵机。图灵机的停机问题是：能否有个程序判断任意一个程序，它是否在有限的时间内结束运行。他同样也是构造出一个自我纠缠的例子，证明这是不可能的。【6】塔斯基定理和图灵停机不可判定，都与哥德尔不完备性定理等价，相互间可以推证。

哥德尔的不完备性定理，塔斯基的形式语言真理论，图灵机和停机判定问题，被称为现代逻辑科学在哲学方面的三大成果。这分别在数学形式系统，语义学和计算领域，研究数学证明能力，语言表达能力和机器计算能力，他们都应用和发展了递归理论，研究在有限或向无限进行中的逻辑推理，所（不）能到达的极限。

无穷超越了人类理解的极限。在芝诺的悖论里，阿基里斯一直无法在逻辑上超越乌龟。【7】几千年来人类智力的进步解答了一部分的困惑，但它在不断被征服后，又屹立在那里，就像他们间的距离只是缩小而不是消除。每个人可能会有个梦中情人，现实中人们只可能在有限的时间里，接触到有限的人中搜寻，也许是终生无缘相遇。人们在潜无穷和实无穷的逻辑鸿沟两边相望，没有一座桥梁跨越。有限化的证明、计算和语言表达站在潜无穷这一边，自我纠缠无休止的自诘，意味着实无穷。难道这告诉我们：逻辑永远无法跨越潜无穷到达实无穷？

（完）

【参考资料】

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

【2】      哥德尔不完全性定理(朱水林) http://ishare.iask.sina.com.cn/f/23413902.html

【3】      数理逻辑的发展http://www.kepu.net.cn/gb/basic/szsx/4/44/4_44_1014.htm

【4】      张祥龙，塔斯基对于“真理”的定义及其意义http://www.cnphenomenology.com/modules/article/view.article.php/24/c2

【5】      SEP Self-reference http://plato.stanford.edu/entries/self-reference/

【6】      维基百科，停机问题http://zh.wikipedia.org/wiki/%E5%81%9C%E6%9C%BA%E9%97%AE%E9%A2%98

【7】      应行仁科学网博文，阿基里斯与乌龟的悖论解决了吗？http://blog.sciencenet.cn/blog-826653-642105.html