如何简单清晰地解释哥德尔不完备定理？第1页

lllbk 网友的相关建议:

唉，一直想写一个哥德尔不完全性定理的回答，但每每下笔都感觉自己了解的还是太少了，而这一定理涉及的实在太多了...

按照“哥德尔不完全性定理”这个名称，本回答可以分三部分，“哥德尔（是谁）”、“不完全性（是什么）”、“定理（的证明）”。最后还会说一说这一定理的影响。

1. 哥德尔是谁

哥德尔18岁的时候到维也纳上大学。当时的维也纳是个很有特点的城市，出了很多非常杰出的人，包括科学家、音乐家、诗人、画家、哲学家、建筑家等等各种领域的大师。由于集中了很多人才，维也纳的思想文化很开放。当时那里有很多咖啡馆，你随便走进一家，随便找一张桌子坐下，很可能就听到你的邻桌在谈论艺术或建筑，另一个邻桌又在谈论数学和哲学。像这样集中起来定期讨论学术问题的小圈子在当时的维也纳简直不要太多，其中一个就是哲学界非常著名的“维也纳小组”。

维也纳小组发起了“逻辑实证主义‘的哲学运动，这个哲学流派现在已经基本没人支持了，但当时可以说是席卷整个英语哲学界，简单来说，他们主张”一个句子的意义就是你要如何去用经验去证实它“。比如”这篇回答不少于1000字“这句话的意义就在于你去数一下看看这篇回答是不是不少于1000字。按照这种标准，形而上学的句子就是没意义的，因为像”上帝“这种形而上学的东西你根本不知道该如何去用经验证实它。它跟感觉经验是没关系的。当时逻辑实证主义一出来以后，基本上都没人敢提”形而上学“这几个字了，因为提这个似乎就显得很傻帽没意义。

这个维也纳小组大概就是这么牛逼的小组。他们每周聚一次，讨论哲学问题交流意见。这个聚会不是谁都能参加的，要受到邀请才能参加。牛逼如Popper（波普尔，提出科学的证伪主义的那个人）也没收到邀请。然而哥德尔还在维也纳上大学的时候就已经应邀参加了...（他的导师门格尔带他和另一个学生一起去的）

哥德尔当时坐在这一群逻辑实证主义者中间的时候基本一言不发，这当然和他的性格有关——他是很孤僻的，基本没有社交和朋友。但更重要的是，哥德尔从根本上是反对逻辑实证主义的。他并不认为形而上学无意义，哥德尔是一个柏拉图主义者，也就是说，他认为句子的意义不能仅仅取决于人的感觉经验，还应该存在一个超越人感觉经验的类似柏拉图的理念世界——至少在数学上是如此。实证主义者认为数学陈述如“1+1=2”是无意义的，它们为真仅仅是因为语法而不是语义——因为按照实证主义的标准，数学陈述既然不涉及现实，那就跟感觉经验没关系，那就没意义。哥德尔无法同意这一点，他认为数学陈述实实在在地表达了数学世界的情况，因而是有意义的。这就是为什么哥德尔在维也纳小组中一言不发的原因。（还有一个原因可能是，维也纳小组全员把维特根斯坦视为神，把他的《逻辑哲学论》当成圣经一样，而哥德尔和维特根斯坦是互相鄙视的...）

后来二战爆发，哥德尔和很多欧洲杰出的思想家和科学家一样前往美国。他去了普林斯顿的高等研究院。这个高等研究院是某个富豪出资建的，目的是为了养着全世界最优秀的一批人，让他们能全心投入到理论研究中。研究院里比较出名的有爱因斯坦、冯诺依曼、摩根斯坦等等。哥德尔的好朋友数来数去只有爱因斯坦和摩根斯坦两个。最好的朋友应该算是爱因斯坦，他们每天都一起散步回家，好像有说不完的话。这其实是很奇怪的，爱因斯坦搞物理，哥德尔搞数学和逻辑，爱因斯坦外向开朗，哥德尔内向孤僻，爱因斯坦是诺奖级别的中老年泰斗，而哥德尔只是个青年教师...这俩能有什么话可以天天说呢？

其实，爱因斯坦和哥德尔遭到的对待是一样的。爱因斯坦的相对论经常被解读为“把人的因素带进了科学”。因为相对论主张各种东西都是相对于观察者而言的，因此似乎表明把“软”的人的因素带进了“硬的”物理学中。自牛顿以来，自然规律似乎是客观的，人似乎只能去服从而不能参与到自然规律中。而相对论好像就把人重新放回了世界中心的位置。——这让许多后现代主义者十分开心。而哥德尔不完全性定理表明，数学系统中总存在一些不可证的真命题，而数学系统是人为构造的，这说明没有一个系统是绝对正确的，没有一个系统能力压其他系统。这似乎表明“软的”人的因素进入了“硬”的数学中，即使客观如数学，所使用的系统也都是人为的而并非绝对正确的。——这也让许多后现代主义者十分开心。

相对论和哥德尔不完全性定理被广泛流传，但基本都是以后现代主义者希望的方式，他们认为这两个理论表明“人是万物的尺度”，人重回了宇宙的中心。然而爱因斯坦和哥德尔的本意却不是这样。相对论确实主张各种东西都是相对于观察者而言的，但相对论也说了，不同的参考系是平权的，没有谁有优先地位。爱因斯坦认为物理学不能掺杂任何“软”的东西，比如人的因素，比如本质上的随机性（这也是爱因斯坦始终不接受量子力学的原因），他认为我们这个世界的运行规律是绝对确定的。哥德尔也一样，他认为自己的不完全性定理表明，存在一些确实为真的东西是人为构造的逻辑系统无法达到的，这些确实为真的东西就是数学的理念世界，它们跟人无关，它们有自己确定的真值，不论人有没有去研究它。

诗人最讨厌的就是自己的诗广泛地流传，却被所有人误读了自己的本意。爱因斯坦和哥德尔都有这种感觉，他们各自最重要的成果都广泛地流传，却被世人误解。这大概就是他们能成为至交好友的原因吧。

2. 不完全性是什么

说完了哥德尔，接下来说说什么是不完全性。大多数人的理解就是“存在不可证的真命题’，但其实不完全性是一个十分专业的逻辑学概念，不是简单几个字就能说清的。

首先还是要说一些背景性的东西。数学工作是靠数学证明来完成的，每个证明总得有个出发点，不然证明就无法开始。因此，整个数学必然要有一些不证自明的出发点，由它们出发来构建整个数学大厦。这些出发点就是数学公理。但公理为什么是正确的呢？这时似乎就只能求助于我们的直观。那些直观上非常简单，甚至根本无法想象它不对的那些数学命题就能够作为公理，比如欧式几何的五条公理：任意两点能连成一条直线、所有直角都相等...等等。这些都是看起来很trivial甚至不值一提的命题，但正是因为这样，它们才足够作为公理——因为它们看起来不可能错。

但人们逐渐发现，靠直观的公理还是有可能会错。比如集合论的公理（见 LLLBK：据说罗素悖论有解，如何解？）会导致矛盾，欧式几何的第五公理虽然说不上错但完全可以被修改为非欧几何。直觉总是有可能不靠谱的，因此有些形式主义的数学家（如希尔伯特）希望把直觉完全排除出数学。这时，谁来保证公理为真？形式主义者会说，公理没有什么真假可言，也没有什么意义，它们仅仅是人为约定的符号组成的符号串而已，数学家所做的工作无非就是按照既定的推理规则从一个符号串推出另一个符号串。

这就像下象棋一样，每个棋子有自己的移动规则，车走直线，马会被拐马脚，炮需要支炮架才能攻击，这样的理解有助于我们记住每个棋子的移动规则。但即使不这样理解，也不影响一个人会下象棋。他不必把棋子“车”理解为战车，“马”理解为马，“炮”理解为炮，“帅”理解为军队的大帅，他也可以学会下象棋并且下的不错。数学家不必理解那些数学符号的“意义”，只需要知道该如何按照既定的推导规则推理下去就行了。这样一来，数学公理系统就变为了纯形式的符号系统。

（推荐拓展阅读： @翟刚的数学哲学简介(上)，数学哲学简介(下)）

形式系统简单来说，有三部分：符号、公理、推导规则。公理是由符合组成的公式，形式系统做的事就是从公理出发，根据推理规则，机械地推导一个又一个的公式。

我举一个例子（GEB中的例子），以下这个系统叫ep系统：

符号：-, e, p
公理：x-exp-，其中x代表任意一串“-”。（如 ---e--p-, -----e----p-都是公理，注意x不是系统内的符号，只是我们为了简写这一公理模式而将-的串简写为x）
推导规则：从xeypz可以推出x-eypz-，其中xyz都代表任意一串“-”。（如，可从 --e-p-推出---e-p--）

简单地说，这个系统中的合法字符串都长这样...e...p... 字符e和p将“-”的串分成了三段，这一推导规则意为，如果一个字符串被推导出来了，那么可在这个字符串的第一段“-”串和第三段“-”串后各添加一个“-”。

这个形式系统可以从公理出发，根据推导规则推导出类似-----e--p---的字符串，推导如下：

公理：---e--p-

推出：----e--p--

推出：-----e--p---

事实上，一个形式系统就是一个字符串操作机器，它有一些公理和推导规则，然后就能哗啦啦地得到许许多多的字符串（或者叫公式）。当然，形式主义者需要先证明，自己的形式系统能够推导出所有数学中的真命题，这样才能用形式系统真正取代传统的数学研究。一旦证明了这一点，就可以不再管什么是“真”命题，而只进行纯形式的推导就够了。也就是说，虽然本质上形式系统是没有意义的，但人们希望自己的形式系统能够“表达”一些东西。在数学中，形式主义数学家希望形式系统能“表达”所有的数学真理。

这个“表达”是很神秘的概念，以上面的ep系统为例，它表达了什么？如果你进行了十几个系统内的推导，你会发现导出的公式都是类似这样的：---e-p--, -----e----p-, ----e-p---... 第一段“-”的数量等于第二段和第三段“-”的数量之和。反过来，类似 ----e-p-, -----e---p---这样不满足第一段“-”的数量等于第二段和第三段“-”的数量之和的公式是推不出来的。因此这个ep系统似乎“表达”了加法。

需要注意的是，这种“表达”关系并不是唯一的，而是我们希望它能表达什么，系统本身并没有一个固定的表达。ep系统可以表达加法——只要把e理解为equal，p理解为plus就行了。但它也同样可表达减法，只要把e理解为减法，而p理解为=就行了。

那么，是不是说有了ep系统之后，加减法就不再是必要的了，我们可以像形式主义者所说的那样，不用再管加减法的意义，彻底抛弃传统的加减法，只需要按照ep系统去操作就可以取代传统的加减法呢？现在还是不够的。要想证明ep系统确实有取代加法算术的能力，我们需要证明两点：

ep系统的完全性：所有正确的加法算式（如2+3=5, 5+7=12等）都能在ep系统中推出。
ep系统的可靠性：所有ep系统能推出的公式，都表达的是正确的而不是错误的加法算式。（如ep系统不能推出4=1+2）

简单地说就是，可靠性保证了ep系统能推的都是正确的算式，完全性保证了正确的算式ep系统都能推出。这两条合起来保证了ep系统能完成所有的加法运算。其中，可靠性是很好证明的，只需证明ep系统的公理都是正确的，并且ep系统的推导规则是保真的（如果推导规则的前提是正确的，那么结论也是正确的）。这样由于系统内所有公式都由公理出发经过推理规则得到，而公理是对的，推理规则保证了不可能从对的推出错的，那么系统内所有公式就都是对的了。但完全性是很难证明的，事实上完全性证明是逻辑学的中心问题之一。（我暂时也不知道怎么证明ep系统的完全性...）

以上是用ep系统举例，说明了什么是可靠性和完全性。相对的，不完全性自然就是说，人们希望一个形式系统能表达某领域内所有的真命题，但这个系统做不到，即，有一些真命题是该形式系统推不出的。哥德尔不完全性定理说的就是这个。哥德尔证明了，能够表达初等数论（算术）的形式系统，总存在一些真的算术命题是它无法推出的。（这里有错，根据评论里 @ZS Chen 指出，哥德尔证明的不是这个，而是“存在一个公式，形式系统既不能推出它，也不能推出它的否定，即形式系统无法判定它”。）当然，这种形式系统比上面的ep系统复杂得多，但基本的原理就是这样。形式主义数学家希望他们的形式系统足够刻画整个数论，即能推出所有的算术真命题，但年轻的哥德尔粉碎了他们的梦想。

简单来说，这种表达算术的形式系统包含一些类似的符号——都是我们现在经常在数学中见到的。这种包含量词和变元和性质的逻辑叫做一阶逻辑。这个名称要来源于罗素的《数学原理》。在罗素悖论之后，数学家们对数学的基础展开了新的探索，罗素自己当然也不例外。他拯救罗素悖论的方式是“类型论”（见 LLLBK：据说罗素悖论有解，如何解？），将语言进行分层，最底层的就是一阶的。数学家们按照类型论纲领发展数理逻辑，自然是先从最简单的第一阶开始研究，这些研究现在被归入了一阶逻辑这个领域中。事实上，哥德尔的论文题目就是《〈数学原理〉及有关系统中的形式不可判定命题》，也就是《论罗素那本书里的系统以及相关的一系列系统中有什么推不出的命题》。

3. 定理的证明

虽然这篇论文本身艰深难懂，但思路倒是非常简明。把哥德尔证明的那个不完全的形式系统叫做PM.

首先要区分两个层次的定理：系统内定理和元定理。系统内定理就是PM能推出的公式，如就是PM的内定理。而元定理是关于PM系统本身的定理。如“ 的首个字符是 ”就是一个元定理，“ 在系统内可推导（简称“可证”）”也是一个元定理。

显然，内定理和元定理是两个不同层次的东西。元定理陈述了一些关于内定理的事情，但内定理无法陈述关于元定理的事。但如果内定理也能陈述关于元定理的事呢，情况会怎么样？那我们就可以在系统内部用字符串表达“xxx公式不可证”，“xxx公式的首字符是 ”这种元定理。我们甚至有可能写出一个公式，它表达了“本公式不可证”。

为表达对哥德尔的敬意，把表达了“本公式不可证”的系统内公式记作G。显然，G为真当且仅当G不可证，G为假当且仅当G可证。PM系统的可靠性是毋庸置疑的——没有数学家会使用不可靠的系统。因此G是绝对不能为假的，因为这意味着G可证，即PM系统推出了假命题，这违反了可靠性。因此，G为真，但这恰好说明G不可证，这也就是说存在不可证的真公式，因此PM系统是不完全的。

因此哥德尔定理证明的关键就在于如何构造这个G。更本质地说，如何发现PM系统能表达关于它自身的元定理。我们已经知道的是，PM系统能够表达算术命题，比如1=1这种。那如果算术能够表达PM的元定理，不就说明了PM能表达PM的元定理？简单的表示就是：

PM—（表达）—算术—（表达）—PM的元层面—（表达）—PM

因此，问题的关键就落在了，如何建立算术和PM系统的元层面之间的关系。举例来说，类似 “ 的首字符是 ”这样的元定理，是否能找到一个类似这样的正确算式来刻画？

哥德尔通过哥德尔编码的方式来完成这个任务，哥德尔编码给每个基本符号如等等指派一个数字，如以上三个符号可分别指派1，2，3。从此出发，可以用建立数字和符号串之间的对应。用一个例子来说明：看一个最简单的公式，假如给定的编码是，这个公式的六个字符分别对应数字1 2 3 4 3 5，则整个公式对应的哥德尔数为，将这个数记为n。即，将素数从小到大排好，在它们上面按顺序写出符号对应的哥德尔数。类似地，也是一个哥德尔数，它对应的字符串是，当然，这并不是一个合法的公式，仅仅是随意排列的字符串而已。根据算数基本定理，一个合数可唯一的分解为这种素数^指数的乘积，这保证了不同的公式对应了不同的哥德尔数。

而元定理“ 的首字符为 ”就能通过它的哥德尔数n的某些算术性质来表示。显然，如果能说明n的哥德尔数可被分解为这种因式，就能说明的首字符为了。即，要说明n能被2^1整除，但不能被2^2整除。即，要说明：存在一个数a，使得2a=n；但不存在一个数b，使得4b=n。而这就是一个纯粹的算术命题了。这是一个直观的例子，展示了如何建立算术和PM系统的元层面之间的关系。

一个推导就是公式组成的序列，它也可以被一个哥德尔数表示，表示的方法是：如果这一推导中的公式对应的哥德尔数分别为a,b,c... 那这个推导本身就对应着哥德尔数，这个很大很大的数记为x。这个推导有个最终的结论公式，假设这个结论的哥德尔数是z，那么显然，x和z之间会存在一些算术上的关系（如x^2+4=z，当然要比这种复杂得多）这个关系我们记为prove(x, z)（意为x对应的序列证明了z对应的公式）。

prove(x, z)表示x是z的证明，因此，“存在x，prove(x, z)” 就表示“数z对应的那个命题（在PM系统内）可证”。这样，我们就把“可证性”这个元层面的性质也用算术表达出来了。当然，可证性对应的算术性质是非常非常复杂的，但理解起来并不难。同样的，不可证性就也表示出来了——“不存在x，prove(x, z)”。简便起见，把z的可证性表示为“provable(z)”，z的不可证性为unprovable(z)。z取不同的数，对应着不同的真假。如对于上述的哥德尔数n，provable(n)就是假的，因为系统推不出n对应的这一公式。

由于provable是一个算术性质，因此可以被PM系统所表达。（被PM系统所表达，意为存在一个公式对应着这个性质，这不意味着PM能推出这个公式。）这个表达可能很复杂，但我们并不需要考虑这个表达的内部结构，只要抽象地表示为PROVABLE就行了。即，provable(z)这个算术层面的性质，可以找到一个系统中的很复杂的公式相对应，这个公式简记为PROVABLE(Z)。对应地，unprovable(z)对应的系统内公式记为UNPROVABLE(Z)。

但是，注意到z是一个哥德尔数，它对应着一个公式。根据不动点定理（不知道也没关系，想知道的同学参见 @ZS Chen 的https://www.zhihu.com/question/66094972/answer/238396535），存在一个数a，使得UNPROVABLE(A)的哥德尔数恰好是a自身。事实上，这个UNPROVABLE(A)就是我们最开始要构造的那个G了。因为UNPROVABLE(A)为真，当且仅当unprovable(a)，即a具有算术性质unprovable，这等价于a（通过哥德尔编码）所对应的PM系统内公式不可证，即UNPROVABLE(A)不可证。也就是说，我们成功地构造出了一个公式，它“说它自己不可证”。这个公式为真，但不可证。这就证完了整个定理。

4. 定理的一些影响

上述的是哥德尔第一不完全性定理，实际上还有一个第二不完全性定理。这个第二定理是让希尔伯特非常头疼的定理。众所周知，希尔伯特提出了23个希尔伯特问题，其中第二个问题就是算术系统的一致性问题。一致性，即系统不会推出矛盾。矛盾能推出一切。事实上，上述定理的证明中隐含的使用了PM系统的一致性——如果PM系统不一致，那它就能推出一切公式，也包括G。因此，上述定理实际上证明的是，如果PM是一致的，那么存在G为真但它不可证。因此，如果PM系统能证明它自身的一致性，那么实际上就已经证明了G为真，而这就违反了上述第一不完全性定理——PM证不出G。因此可以得出结论：PM无法证明自身的一致性。

在哲学上，哥德尔认为他这个定理支持了数学的柏拉图主义——数学真理不依赖于人，是客观存在的。哥德尔定理的证明还影响了许许多多的方面，比如他这个定理的证明直接开启了递归论、模型论等等重要的逻辑学分支，并且直接启发图灵证明了停机定理。（哥德尔非常称赞图灵的工作，这是不多见的）

有些人认为，这个定理似乎表明人工智能是不可能超越人类的。因为再复杂的人工智能本质上还是一个计算机程序，而程序其实就是一个形式系统，哥德尔定理表明有些东西形式系统推不出，但人类能推出。但其实也未必如此，因为这个定理并未表明人的智慧不能被形式系统化。哥德尔本人也并没有认为他的这个定理支持了这样一个结论。

关于哥德尔定理的影响，可参见这个问题：https://www.zhihu.com/question/23323646

这个回答很长，很长，我猜许多人都不会看到最下面，而在中途就直接放弃了，所以感谢认真看到这里的你：）

最后建议学有余力的同学看看评论中 @ZS Chen 的评论，惭愧...

参考资料：

侯世达：《集异璧》

丽贝卡戈德斯坦：《哥德尔的证明和悖论》

内格尔, 纽曼：《哥德尔证明》

J Ferreiros：The Road to Modern Logic

zh3036 网友的相关建议:

现在读来觉得这个答案既不是很易懂叙述中也存在一些错误我觉得我有新的更好的解释方法。。

------------------

注：本文注重理解，所以有些说法可能不严谨，还请见谅。
我们先来看一个句子：「我在说谎」。这句话是谎言，还是真话？这个著名的说谎者悖论其实已经触碰到了哥德尓不完备定理。
我们再来看一个句子B：「本句话是假的」。
句B是真的，还是假的？假如你判定句B是真的，则句B是假的。假如你判定句B是假的，则句B是真的。所以，你要么接受：句B，既真又假。要么接受：句B的真值，无法判断。哥德尓指出，在任何表达力足够强的形式系统中，我们都可以构造出一个类似句B的命题T，使得；即T可以被证明，当且仅当T无法被证明；即T的含义便是「T这个命题是无法被证明的」。通过构造T，哥德尓得出了他的「第一不完备定理」：任何表达力足够强的形式系统都不可能同时具有「一致性」，和「完备性」。

什么样的系统具有完备性呢？如果一个系统中所有可以表达的命题，他们的真值都能被决定，要么真，要么假，那么我们就说这个系统是完备的。比如，在算术系统中，命题1>2 是假的，命题3>2是真的，命题是假的。如果所有这样使用二阶逻辑，数字，和其比较符号构成的命题都能被决定真假，那么算术系统就是完备的。

什么样的系统具有一致性呢？永远不允许「矛盾」出现的系统，就是一致的。矛盾就是.比如，在某算术系统中，如果不同时允许1 > 2 和 1<=2，就说明该算术系统是「一致」的。

为什么这个定理没有叫「哥德尓不一致定理」呢？因为「一致性」实在是一个系统起码的标准。以至于数学家们愿意为了一致放弃完备。你可能注意到，我上边说，只要不同时允许1>2和1<=2，就说明一致。那万一允许了其他矛盾呢？这是不可能的，因为如果系统存在一对矛盾，也就是不一致的话，那么，这个系统就可以推出任何命题和他们的反命题。
比如，我们随便举一个命题A：太阳从西边升起。我现在就以1>2和1<=2为前提，尝试推导A。
设
我们有

那么

取逆否

得到

我们已知

所以

本证明没有使用到A的任何性质，可见，如果一个系统允许矛盾存在，那么这个系统中的任意命题都可得证，这系统也就失去了存在的意义。

看到这，你应该已经知道什么叫「一致」和「完备」，你也就已经理解什么叫「哥德尓不完备定理」了：一个系统要么有矛盾不自恰，要么有命题判断不了。这一切，都是因为T：「本命题无法被证明」。在集合论里，这个T就是罗素悖论：对于一个集合E，E包含所有不包含自己的集合。E是否包含自己？在计算理论里，这个T就是停机问题，如果有一个程序P，P输入一个会终止的程序代码就无限循环，输入一个会无限循环的程序代码就终止；那么把P的代码输入给P，会发生什么？只要一个系统表达力强到可以自指，那么就不可能是完备的。

哥德尓当初在算术逻辑系统里用非常巧妙的方法构造了T，这里给出一个非常不严谨的介绍：（待更新）

jasonchen0325 网友的相关建议:

假设楼主没有任何形式逻辑基础, 那么我借用Raymond Smullyan(R.I.P.)的打印机比喻来直观地解释不完备定理：

假设有一台打印机, 我们可以通过输入指令来让它打印出某些字符串. 一些指令如下：

对于任意字符串X, 输入P*X, 机器便会打印X

输入NP*X, 机器则永远不会打印X

输入PR*X, 机器便会打印XX

输入NPR*X, 机器则永远不会打印XX

例:

输入PR*123, 机器会打印123123

输入NPR*000, 机器则永远不会打印000000

因为指令本身也是一些字符串, 所以这台打印机也可以打出指令出来, 例如输入P*P*123, 那么打印出来的就是P*123, 然后我们假设如果打印机打印出来的是指令, 那么打印出来的指令则会自动被输入, 那么例子中的P*P*123得出来的就是123.

现在问题来了：输入P*NPR*NPR*, 机器会有什么反应?

一方面, 机器应该打印出NPR*NPR*, 因为这是P*这个指令在这里的作用

另一方面, 机器不应该打出NPR*NPR*, 因为这是NPR*这个指令在这里的作用.

结论就是, 这台打印机里有一条应该打印出来却打印不出来的指令, 或者打印出来了就会违规的指令.

哥德尔第一条不完备定理说的就是：任何相容的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的命题，因此通过推演不能得到所有命题（即体系是不完备的）。

在这个比喻里打印机就是一个这样相容的形式系统, 打印=证明, 打印出来的东西=定理.

楼主不介意读英文的话, George Boolos写过一篇Gödel's Second Incompleteness Theore Explained in Words of One Syllable，很有趣, 链接在这里：

http:// www2.kenyon.edu/Depts/M ath/Milnikel/boolos-godel.pdf

mathqjye 网友的相关建议:

前些天，我最喜欢的数学科普频道3blue1brown的制作人发了一条推特，盛赞这篇介绍哥德尔不完备定理的文章。我阅读之后，发现所言不虚。怀着激动的心情，我决定在知乎翻译这篇文章，让更多人了解证明的奥秘。由于本人水平有限，翻译可能会有不恰当的地方，请评论区指正。

哥德尔证明的原理

——每个数学系统都存在一些语句永远无法被证明。

1931年，奥地利逻辑学家库尔特·哥德尔（Kurt Gödel）取得了有史以来最惊人的智力成就之一。

那个时代的数学家们为数学寻求坚实的基础：一系列基本的数学事实，或者说公理。它们既是一致的，即不会导致矛盾，同时也是完备的，以作为所有数学真理的基础。

但是，哥德尔年仅25岁时发表的令人震惊的不完备定理彻底粉碎了这一梦想。他证明了任何一个你假定的能作为数学基础的公理集都不可避免地是不完备的：总有一些关于数的事实不能被这些公理证明。他还说明甚至没有任何一个候选的公理集能够证明其自身的一致性。

他的不完备定理意味着不存在一个对万事万物皆适用的数学理论，可证明性和正确性也无法统一。数学家可以证明的内容取决于他们的初始假设，而非所有答案所依据的基本事实。

自哥德尔发现定理以来的89年中，数学家们偶然发现了他的定理所预言的那些无法回答的问题。例如，哥德尔本人帮助建立了连续统假设（这与无穷集的大小有关）是无法判定的，正如停机问题，该问题询问对于随机输入，计算机程序将永远运行还是最终停止。不确定性问题甚至出现在物理学中，这表明哥德尔不完备定理不仅困扰了数学，而且以某种不被理解的方式困扰了现实。

下面是哥德尔如何证明定理的简要且非正式的描述。

哥德尔数

哥德尔的主要策略是把关于某个公理系统的语句映射到一个特定的系统内的语句，即映射到一个关于数字的语句。这个映射使公理系统能够有效地谈论自身。

这个过程的第一步是将任何可能的数学语句或一系列语句映射到一个被称为哥德尔数的唯一数字。

这个对哥德尔的方案略微修改后的版本是由欧内斯特·内格尔（Ernest Nagel）和詹姆士·纽曼（James Newman）在他们1958年出版的《哥德尔的证明》（《Gödel's Proof》）的书中提出的，始于用12个基本符号作为词汇来表达一系列基本公理。例如，用符号表示存在，用符号表示加法。重要的是，符号表示“后继”，给出了表示特定数字的方法。例如，指的是。

这12个符号被分配到了从1至12的哥德尔数。

下一步，用字母表示变量，从开始，映射到大于12的素数（即）。

接下来，这些符号和变量的任意组合，即任何可以被构造的算术公式或公式序列，都将有自己的哥德尔数。

比如，考虑。这个公式的三个符号对应的哥德尔数是。哥德尔需要将这三个数字的序列改为一个唯一的数字，也就是其他符号序列不会生成的数字。为此，他采用前三个质数（），将每个符号的哥德尔数作为这个序列相同位置的指数，并将它们相乘。因此变为，即。

该映射之所以有效，是因为没有两个公式会有相同的哥德尔数。哥德尔数是整数，而整数仅以一种方式分解为质数。因此，的唯一质数分解是，这意味着只有一种可能的方法可以解码这个哥德尔数：公式。

哥德尔之后更进一步。数学证明是由一系列的公式组成的。因此，哥德尔也为每个公式序列赋予了唯一的哥德尔编号。在这种情况下，正如前面一样，他从质数列表开始，即依此类推。然后，他将公式的哥德尔数作为对应位置素数序列的指数（例如，若先出现，则为），然后将所有数相乘。

算数元数学

这么做真正的好处是，即使是关于算术公式的语句，也被称为元数学语句，也可以转换为以它们自身的哥德尔数所产生的公式。

首先考虑公式，意思是“零不等于零”。这个公式显然的错误的。不过它依然有哥德尔数：2的1次幂（符号的哥德尔数是1），乘以3的8次幂（“左括号”的哥德尔数是8），依次类推，得到。

因为我们可以为所有公式甚至错误的公式生成哥德尔数，所以我们可以通过谈论它们的哥德尔数来明智地谈论这些公式。

考虑以下语句：“公式的第一个符号是波浪号”。这个关于的正确的元数学语句转化为关于公式的哥德尔数的语句，即其第一个指数为1，即波浪号的哥德尔数。换句话说，我们的语句为只有一个2因子。如果以除波浪号以外的任何符号开头，那么其哥德尔数至少应该有两个2因子。因此，更准确地说，是的因子，但不是因子。

我们可以将最后一个语句转换为精确的算术公式，即我们可以使用基本符号写下。这个公式当然有一个哥德尔数，我们可以通过将其符号映射到素数的幂上来进行计算。

对于好奇的读者，这个语句可以读作“存在一个整数使得乘以2等于，且不存在一个整数使得乘以4等于 ”。对应的公式为其中表示有个后继符号。符号意思是“且”，是基本词汇中较长表达的简写：可以用替代。

对于这个例子，内格尔和纽曼写道“这说明了一个非常普遍且深刻的见解，它位于哥德尔发现的核心：长链符号的印刷性质可以以间接但完全准确的方式替代对大整数因式分解性质的讨论”。

对于元数学语句，转换为符号依然是可能的：“存在某个哥德尔数为的公式序列，可以证明哥德尔数为的公式”，或者简言之，“哥德尔数为的公式可以被证明”。将此类语句“算术化”的能力为解决这个难题奠定了基础。

自身

哥德尔的独到见解是，他可以用公式本身的哥德尔数代入到公式中，从而导致无穷无尽的麻烦。

为了看出这个代入是如何起效的，考虑公式（它读作“存在一个变量使得它是的后继”，或者简言之，“ 有一个后继”）。像所有公式一样，它有哥德尔数，即某个大整数，我们就叫它。

现在让我们在公式中用代替符号。这形成一个新公式，表示“ 有一个后继”。我们怎么记这个公式的哥德尔数呢？我们需要传达三点信息：我们从哥德尔数为的公式开始。在其中，我们用代替了符号。根据前面介绍的映射方案，符号的哥德尔数为17。因此，让我们指定新公式的哥德尔数为。

译者注：这段是理解的难点，我们更仔细的再叙述一遍。在这段中，我们定义了一个函数，这个函数一共有3个输入，他们都是正整数，我们记为。其中，第一个参数是一个公式的哥德尔数，我们接收到之后要把它解码成此哥德尔数所对应的公式。最后一个参数指的是一个符号的哥德尔数，我们要找到对应公式的所有哥德尔数为的符号所对应的位置。最后，我们把刚才找到的位置全部替换成数字。现在，我们计算这个修改后的公式的哥德尔数，这个数字就是。

替换构成了哥德尔证明的关键。

他考虑下面一个元数学语句“无法证明哥德尔数为的公式”。回想一下我们刚刚学到的符号，哥德尔数为的公式是通过取哥德尔数为（某个未知量）的公式并将该变量替换掉哥德尔数为17的符号（也是任何一个的位置）。

事情变得令人迷惑，但是不管怎么说，我们的元数学语句“无法证明哥德尔数为的公式”肯定能转化为某个特定哥德尔数所对应的公式。我们把这个数称为。

现在进行最后一轮替换：哥德尔通过将数字替换先前公式中的位置来创建一个新公式。他的新公式声称：“无法证明哥德尔数为的公式”。我们将此新公式称为。

自然，也有一个哥德尔数。那么它的值是什么呢？哇哦，它肯定是！根据定义，是下面公式的哥德尔数，它是通过将哥德尔数为的公式中对应哥德尔数为17的符号用替代所得到的。而正是这个公式！由于素数分解的唯一性，我们现在看到所讨论的公式就是本身。

译者注：这又是一个难点。我们更仔细的叙述如何计算。回忆我们前面的注，我们的第一步就是要解码所对应的公式。根据前文，我们知道这对应了语句“无法证明哥德尔数为的公式”。第二步，我们要找到17所对应的符号，也就是的所有位置，我们将找到的位置加个框：“无法证明哥德尔数为的公式“。第三步，我们要把框的位置替换成，也就是“无法证明哥德尔数为的公式“，而这正是公式。

断言自己无法被证明。

但是能被证明吗？如果是的话，则意味着存在某个公式序列，可以证明哥德尔数为的公式。但这恰好与相反，即断言不存在这样的证明。相反的语句和在一致的公理体系中不可能同时为真。因此，的正确与否必然无法被判定。

然而，尽管是无法被判定，它显然是对的。意思是“无法证明哥德尔数为的公式”，而这正是我们所发现的事实。既然是正确的，还是在此公理体系内构造的一个无法被判定的语句，说明了这个系统是不完备的。

你可能认为你可以提出一些额外的公理，使用它们证明并解决悖论。但是你不能。哥德尔说明了对于增强的公理系统将允许构建新的正确的公式（根据与之前的方法类似），而该公式无法在新的增强系统中得到证明。在努力建立完备的数学系统时，你永远无法摆脱困境。

没有一致性的证明

我们学到了如果公理集是一致的，则它是不完备的。这是哥德尔第一不完备定理。第二定理，即没有一套公理可以证明其自身的一致性，由此易得。

如果公理集可以证明它永远不会产生矛盾，那意味着什么？这意味着存在根据这些公理构建的一系列公式，证明了这个含义为“这组公理是一致的”的元数学公式。由第一定理，这个公理集必然是不完备的。

但是，“公理集是不完备的”与“有一个无法被证明的正确的公式”含义相同。这个语句等价于我们的公式。我们知道公理不能证明。

因此，哥德尔创造了一个矛盾的证明：如果公理集可以证明其自身的一致性，那么我们将能够证明。但是我们不能。因此，没有一组公理可以证明其自身的一致性。

哥德尔的证明扼杀了对一个一致和完备的数学系统的追求。内格尔和纽曼在1958年写道，不完备性的含义“还没有被完全理解”。直到今天仍然如此。

转一段清华大学赵昊彤博士的解读，我认为算是简单清晰准确。

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

【中文网上深入介绍哥德尔不完备定理的文章很少，我这篇文章写得很长，花了不少时间打磨它，希望能帮助到爱好数学与逻辑的人。文章把理解哥德尔不完备定理分为了五重，建议只是想初步了解的读者，可以重点看第一重；希望了解一些背景的读者，可以修炼到第二重；希望较深入理解哥德尔证明思路的读者，建议修炼到第三重；如果确实感兴趣，希望详细了解哥德尔证明过程以及其严谨性的读者，可以修炼到第四重；如果还想多知道一些知识的读者，可以练到第五重。

——— 作者】

1931年，库尔特∙弗雷德里希∙哥德尔（KurtFriedrich
Gödel）发表了一篇影响深远的论文“On formally undecidablepropositions of Principia
Mathematica and related systems I”[1]（论文的原文是用德文发表的，这里给出的是英译名）。今天，我们一般笼统的把论文中提出的定理称为“哥德尔不完备定理”。80多年过去了，“哥德尔不完备定理”的影响仍然持续、深远，特别是引起了很多非数学界人士的兴趣，引发了各种各样的解读。很遗憾，有一些解读是不准确的，甚至是错误的；更为严重的是，有一些人出于对“哥德尔不完备定理”的一知半解，甚至开始怀疑、批判人类的理性，以至于发展到相信、鼓吹不可知论。近期，我在认真研读了哥德尔论文原文（英译版，本人实在是不懂德文）和相关资料的基础上，加深了自己的认识，同时也很希望尽自己绵薄之力，分享对“哥德尔不完备定理”的理解，厘清对“哥德尔不完备定理”的误解。

“哥德尔不完备定理”是数学、逻辑学领域的划时代成果，使人们对于数学研究基础的认识更加深刻、准确，同时它也是现代逻辑史上的重要里程碑。“哥德尔不完备定理”虽然伟大、深刻，但是个人认为它并不深奥。对于一个普通人，只要愿意动脑，都可以在一定程度上准确理解它。当今的互联网时代，网上有不少对“哥德尔不完备定理”的介绍和解读；60多年前，两位美国作家欧内斯特·内格尔（Ernest
Nagel）和詹姆士 R. 纽曼（James R.
Newman）撰写的的著作《哥德尔证明》更是科普“哥德尔不完备定理”的重要作品。如今网上能看到的中文介绍“哥德尔不完备定理”的文章，绝大部分是转述《哥德尔证明》这本书的内容的。不过这本书撰写太早，有些新的结论当年尚不了解；另外这本书在普及哥德尔证明的时候，更多的是讲解背景、思路，并用作者自己的理解来讲述哥德尔的证明，个别地方不够严谨，一些讲述方式也不够准确。本文则全部基于哥德尔论文的原文来介绍“哥德尔不完备定理”的证明，并适当融入一些80多年来新的认识和结论，希望能帮助数学、逻辑学爱好者了解并理解“哥德尔不完备定理”。

为了帮助更多人在各自需要的层面上理解“哥德尔不完备定理”，下面的介绍把理解“哥德尔不完备定理”分为了五重，从对定理的基本含义的理解一直到对核心证明的了解都包括了进来。读者可以像修习“乾坤大挪移”神功一样，依照自身内力基础，修炼到适合自己的层面即可。祝愿大家都能练成“哥德尔不完备定理”第五重神功！

第一重：“庐山真面目”——准确了解“哥德尔不完备定理”

赏玩一块美玉的时候，首先不应该是听各类专家讲这块玉多么晶莹剔透、多么价值连城，而应该是首先把玉拿出来让大家看看，有个感性认识。在哥德尔的论文中，我们一般所说的“哥德尔不完备定理”（有时候也被叫做“哥德尔第一不完备定理”）是指论文中的定理VI，原文如下：

TheoremVI:
For every ω-consistent primitive recursive class κ of formulae, there
is aprimitive recursive class-sign r , such that neither forall(v,r)
nornot(forall(v,r)) belongs to Conseq(κ) (where v is the free variable
of r).

尽量原汁原味的翻译如下：

定理VI：对于任意一个ω一致（第四重）的原始递归公理集合κ，一定存在一个原始递归（第三重、第四重）的表达式r，使得无论是“r总成立”这个命题，还是“r不总成立”这个命题，都不属于通过κ可推导出来的定理的集合（原文中的Conseq(κ)）。

补充说明一点，哥德尔论文中的κ所代表的公理集合，是指蕴含了皮亚诺算术公理（Peano Axioms）的集合，这是在哥德尔论文的前面明确了的，所以在阐述定理VI时就没有再特意强调。

修炼第一重神功的读者可能会问了“大哥，你说的这些都是啥？”。别担心，修炼第一重神功没那么复杂。

让我们先从公理说起，公理其实就是无需证明而被认定为成立的命题。公理体系是指一组公理的集合。通过这些公理和基本的逻辑关系，可以推导出更多成立的命题，称为定理。公理体系一般被认为发源于2300多年前欧几里德撰写的《几何原本》。在现代科学形成的过程中，人们发现通过定义一组公理再加上合理的逻辑推演，可以证明很多命题或结论。公理体系是当今数学研究和科学研究的基础，数学研究成果就是（或者说在极大的程度上依赖于）一组公理体系的推演，而其它科学研究除了依赖公理体系进行推演外，还需要通过系统的实验来进行验证。

“哥德尔不完备定理”是针对公理体系的一项结论，它之所以如此伟大且深刻，正是因为它撼动的是一切科学的研究基础——公理体系。修炼第一重神功的时候，我们简要理解“哥德尔不完备定理”说的是：一个足够复杂的公理体系（至少蕴含了皮亚诺算术公理），如果它是一致的（相容的，无矛盾的），那么它就是不完备的。这里的完备，指的是“对于任何可在这个公理体系内描述的命题，都可以在这个公理体系内得到判定，要么是正确的，要么是错误的”。

再用大白话解释一下，就是说，一个没有矛盾的公理体系内，总有一些命题是说不清楚对还是错的（务必注意，这是指在这个体系内说不清楚，不是说永远都说不清楚了）。也许有人说了，既然没矛盾的公理体系有问题，那就搞个有矛盾的公理体系呗。如果设想一个公理体系，一会儿告诉我们“1+1=2”，一会儿又告诉我们“1+12”，相信不会再有人把这个公理体系当回事。有矛盾的公理体系会导致彻底的无意义和虚无，修炼第二重神功的时候会详细阐明这一点。

上述结论听起来是比较可怕的，公理体系必须没有矛盾，可是没有矛盾的公理体系又会导致出现一些命题说不清楚对错。于是开始出现了各种各样的解读，比如“哥德尔定理告诉了我们数学和逻辑的极限，这也几乎是人类理性的极限。它证明理性不是无所不能的”、“哥德尔定理告诉我们，人类不可能真正认识这个世界，永远不可能理解宇宙的真理”等等。相信作为人类理性智慧光辉代表之一的哥德尔，如果听到这些说法，可能也会很无奈吧。

第一，“哥德尔不完备定理”不仅不是所谓人类理性的极限，恰恰相反，它是人类理性智慧的重大成果。它告诉了我们，正是由于有了人类理性的智慧，才有可能认识到这样深刻的结论。哥德尔是通过构造出了一个无法在这个公理体系内证明的命题来证明出“哥德尔不完备定理”的。这个命题的内容说的正是“命题自身无法在此公理体系内被证明”，既然哥德尔已经清楚的证明了这一点，说明这个命题毫无疑问是正确的。所以，“哥德尔不完备定理”的证明过程其实告诉了我们，存在一个可在这个公理体系内表达的正确的命题，但是在这个公理体系内却既不能证明它，也无法证伪它。如果说“哥德尔不完备定理”阐明了什么极限的话，那它阐明的也只是“某类公理体系的极限”，而不是“数学、逻辑的极限”，更不是什么“人类理性的极限”。

第二，“哥德尔不完备定理”不仅不会告诉我们“人类不可能真正认识这个世界”，反而是在更深刻的层面上告诉了我们人类应该如何去认识世界、探索真理。譬如在数学上，如果发现一个命题通过现有的方法、公理和定理一直得不到证明，我们就可以尝试扩展现有的方法和公理体系来进一步研究；费马大定理、黎曼猜想等命题被称为“会下金蛋的母鸡”就是这个道理。物理学上，广义相对论的发现过程，也是因出现了平直空间中狭义相对论某些推论难以解释（如高速旋转的圆盘会发生扭曲），爱因斯坦提出了等效原理并毅然拓展了平直空间的假设，创建了广义相对论这个伟大的理论。值得一提的是，哥德尔和爱因斯坦在普林斯顿大学成为了非常好的朋友。晚年的爱因斯坦曾经说过，之所以他每天还会经常坚持去办公室上班，是因为可以在路上和哥德尔聊聊天；而爱因斯坦的去世也曾给哥德尔的情绪以很大打击。

第三，“哥德尔不完备定理”也没有给出人类认识真理的上限。如果一个命题在某个公理体系内无法判定，那也不是意味着这个命题就是无法判定的了。对于这类命题，如果属于科学范畴的，可以通过科学实验加以判定，从而扩展现有的公理体系，发现新的科学规律；如果属于数学范畴的，可以通过寻找新的数学工具、数学方法或者数学理论来直接拓展现有公理体系，从而准确的判定这个命题，进而扩大人类研究的深度和广度。

还有人了解到，数学研究已经证明了“不存在一个通用的算法，能够判定一个给定的命题在某个确定的公理体系内是否是可判定的”。由此认为既存在着不可判定的命题，又不存在“能够判定某个命题是否不可判定的方法”，显然我们没法准确认识这个世界了。这种观点是不准确的。虽然我们的确证明了不存在通用的判定算法，但是人类认识世界不是只依靠某组公理体系和确定的逻辑与算法的，人类的思维也不可能只局限在某个或者某组公理体系之内。虽然我们无法设计出一个通用算法，来判定一个命题是否在某个公理体系内可判定，但是这并不必然导致我们无法认知这个命题。举个比较简单的例子，“Goodstein定理”（这个定理相对简单易懂，修炼到第五重的时候会详细说明这个例子）就是一个在皮亚诺公理体系里无法判定的命题，但是在集合论中，利用序数知识可以非常简单的证明它。

“哥德尔不完备定理”揭示了公理体系内在而深刻的性质和固有局限性，告诉我们不要奢望仅仅通过若干组公理出发，机械地利用基本逻辑规则进行推导，就能够对全部的命题进行判定。从这个意义上讲，无论是数学还是其它科学，都需要不断的完善、扩充自身的公理体系（或者基本规律），只有这样才能不断认知更加深刻复杂的客观世界。或者说，哥德尔真正严格证明了这句格言——“科学研究是永无止境的”。

这是解读的第一重，属于最通俗易懂的，后面还有四重。需要的可去原文学习。

科学网-“哥德尔不完备定理”到底说了些什么？--（一） - 赵昊彤的博文

mathiq-galory 网友的相关建议:

三峡

有了它很多长江生物灭绝了或正在灭绝。

如何简单清晰地解释哥德尔不完备定理？的其他答案点击这里

如何简单清晰地解释哥德尔不完备定理？第1页

哥德尔证明的原理

热门评论翻译

转一段清华大学赵昊彤博士的解读，我认为算是简单清晰准确。

相关话题

前一个讨论

下一个讨论

相关的话题

如何简单清晰地解释哥德尔不完备定理？ 第1页

哥德尔证明的原理

热门评论翻译

转一段清华大学赵昊彤博士的解读，我认为算是简单清晰准确。

相关话题

前一个讨论

下一个讨论

相关的话题

如何简单清晰地解释哥德尔不完备定理？第1页