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

假设楼主没有任何形式逻辑基础, 那么我借用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，很有趣, 链接在这里：

前些天，我最喜欢的数学科普频道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年写道，不完备性的含义“还没有被完全理解”。直到今天仍然如此。

热门评论翻译

@Robert Filman：“他还说明甚至没有任何一个公理集能够证明其自身的一致性”这句话并不完全正确。 公理集必须足够丰富，例如，关于带有乘法和加法的算术公理是不完备的，但是只有加法的公理（Presburger算术）是可判定的。

作者回复：谢谢Robert，你是对的。上下文确实含义不清，我们的意思是这个公理集可以作为数学的基础，而不是任意一个公理集。 我们在这个句子中添加了“候选”一词，以解决此问题。

@jfresh：这篇文章中缺少了对下面这段话的举例：
“对于元数学语句，转换为符号依然是可能的：“存在某个哥德尔数为 的公式序列，可以证明哥德尔数为 的公式”，或者简言之，“哥德尔数为 的公式可以被证明”。将此类语句“算术化”的能力为解决这个难题奠定了基础。”
如何将“可以被证明 / 不可以被证明”表示为哥德尔数？

作者回复：你好，jfresh。谢谢你的评论。这个要点与关于波浪号的示例有些相似。如果存在一个哥德尔数为 的公式序列证明了哥德尔数为 的公式，则意味着哥德尔数为 的公式是哥德尔数为 的公式序列的最后一个公式（也就是这是证明的结论行）。换句话说，将元数学语句转换为关于 的素因式分解的最后一个素数的指数是 。 不知道这是否给了点启发？也许其他读者可以说更多。

作者二次回复：另一位读者挖掘了有关哥德尔语句的显式构造的讨论，看起来有点意思：https://math.stackexchange.com/questions/860603/has-the-g%c3%b6del-sentence-been-explicitly-produced。你会看到该讨论中的一位参与者在这个页面的底部构造了两个不同的对语句的符号编码：http://www.von-eitzen.de/math/tntrep.xml。你会看到这是一个怪物般的表达式。

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

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

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

——— 作者】

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定理”（这个定理相对简单易懂，修炼到第五重的时候会详细说明这个例子）就是一个在皮亚诺公理体系里无法判定的命题，但是在集合论中，利用序数知识可以非常简单的证明它。

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

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

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