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

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

哥德尔证明的原理

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

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

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

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

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

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

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

哥德尔数

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

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

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

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

\begin{array}[b] {|c|c|} \hline 符号 & 哥德尔数& 含义\\ \hline \sim & 1 & 非 \\ \hline \vee & 2 & 或 \\ \hline \supset & 3 & 如果...则... \\ \hline \exists & 4 & 存在 \\ \hline = & 5 & 等于 \\ \hline 0 & 6 & 零 \\ \hline s & 7 & 后继 \\ \hline ( & 8 & 标点符号 \\ \hline ) & 9 & 标点符号 \\ \hline , & 10 & 标点符号 \\ \hline + & 11 & 加 \\ \hline \times & 12 & 乘 \\\hline \end{array}\\

下一步，用字母表示变量，从 x,y,z 开始，映射到大于12的素数（即 13,17,19,... ）。

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

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

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

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

算数元数学

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

首先考虑公式 \sim(0=0) ，意思是“零不等于零”。这个公式显然的错误的。不过它依然有哥德尔数：2的1次幂（符号 \sim 的哥德尔数是1），乘以3的8次幂（“左括号”的哥德尔数是8），依次类推，得到 2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9 。

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

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

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

对于好奇的读者，这个语句可以读作“存在一个整数 x 使得 x 乘以2等于 2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9 ，且不存在一个整数 x 使得 x 乘以4等于 2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9 ”。对应的公式为 (\exists x)(x \times ss0 = sss … sss0) \cdot \sim(\exists x)(x \times ssss0 = sss … sss0)\\ 其中 sss … sss0 表示有 2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9 个后继符号 s 。符号 \cdot 意思是“且”，是基本词汇中较长表达的简写： p\cdot q 可以用 \sim(\sim p\vee \sim q) 替代。

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

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

G 自身

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

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

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

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

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

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

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

现在进行最后一轮替换：哥德尔通过将数字 n 替换先前公式中 y 的位置来创建一个新公式。他的新公式声称：“无法证明哥德尔数为 \mathrm{sub}(n,n,17) 的公式”。我们将此新公式称为 G 。

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

译者注：这又是一个难点。我们更仔细的叙述如何计算 \mathrm{sub}(n,n,17) 。回忆我们前面的注，我们的第一步就是要解码 n 所对应的公式。根据前文，我们知道这对应了语句“无法证明哥德尔数为 \mathrm{sub}(y,y,17) 的公式”。第二步，我们要找到17所对应的符号，也就是 y 的所有位置，我们将找到的位置加个框：“无法证明哥德尔数为 \mathrm{sub}(\bbox[#EEF, 5px, border: 2px solid red]{y},\bbox[#EEF, 5px, border: 2px solid red]{y},17) 的公式“。第三步，我们要把框的位置替换成 n ，也就是“无法证明哥德尔数为 \mathrm{sub}(n,n,17) 的公式“，而这正是公式 G 。

G 断言自己无法被证明。

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

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

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

没有一致性的证明

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

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

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

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

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

热门评论翻译

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

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

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

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

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

目录：

1、不完备定理的内容

2、不完备定理的证明

1.哥德尔不完备定理的内容——它为什么惊人

不完备定理的内容很容易理解。有很多版本。我说一个最简单的。“对任何关于自然数结构的有限个公理\Sigma，存在一个关于自然数的命题\phi，\phi是真的，但\phi不能由\Sigma推出（证明）”。这个定理让数学家震惊的原因很容易理解。一个数学命题，如果认为它对，我们必须证明。这是所有数学家的共识（从古希腊时期就被明确提出并一直延续至今，并且仍然是数学家研究数学的基础。另外，请回顾你做的每个数学题）。另一个共识是，总有些命题，我们必须不加证明的承认，并作为公理（要证明A，你用到命题B，要证明B你用到命题C……用A证明A自己，显然不算非平凡的证明，所以总还是需要公理）。而哥德尔定理说，我们最熟悉的数学对象，自然数，不论添加多少关于自然数的公理，永远有为真（在自然数结构中为真）但无法用当前的公理系统证明的命题。于是永远需要凭借直觉寻找新的公理。

上面说的不完备定理是最容易理解的一个版本。你可能会问，对自然数结构是这样的，对其他数学对象是否如此？它的更确切的内容说，这是一个普遍现象。凡是足够复杂的语言加上公理所导致的结构，只要无矛盾且足够复杂（能够解释自然数论），不完备定理都成立，就是说存在即不能被当前公理系统证明，也不能被其证伪的命题。无矛盾很容易理解，就是不可能同时推出一个命题和它的否命题。所谓用一个数学结构编码（解释）另一个数学结构，可以举一个例子，用自然数的子集可以表示实数。把每个[0,1]上的实数写成2进制，就得到一个0-1序列，而一个0-1序列可以有一个显然的自然数子集来表示，这个集合恰好包含该实数2进制展开为1的数位。不完备定理严格来说针对这样的公理系统，这个公理系统能够解释自然数论。解释和编码的区别类似于语言+公理和结构的区别（但我不觉得这是对自然数公理系统的扩充。集合论是自然数论的扩充？二阶算数理论是对实数公理系统的扩充？）。

在上述意义下，几乎所有的数学命题（包括你学的微积分中的各个定理，实数的所有公理）都能在自然数论（二阶自然数论，也就是包含自然数和自然数子集的结构）中得到表示。20世纪初，数学家希尔伯特提出一个纲领，要给全部数学一个基础，一个他认为用公理化框架配合一些关于自然数论或集合论的公理，便可以使得每个数学命题都能从中推出（他的这个观点——认为这样做可行，来自于哲学上的形式主义）。（集合论是比自然数论更复杂（丰富）的结构，它能够表示自然数论，并且目前所有数学命题都能在集合论中表示）。当时许多数学家（包括冯诺依曼、哥德尔等）致力于希尔伯特计划，他们a)要证明自然数论当时的公理系统（皮亚诺公理系统，包括加法交换律，归纳法等等）无矛盾，甚至证明集合论的公理系统（ZF公理系统）无矛盾；b)要证明每个自然数论或集合论命题都能从相应的公理系统推出。当时的设想是，这个计划实现后，要研究一个数学命题，所要做的不过是从当前的一组公理出发，不断的机械的推导下去，早晚会得到这个命题或它的否命题。但哥德尔的不完备定理证明了，希尔伯特计划无法实现。而第二不完备定理就说，这个系统的无矛盾性，便是无法从这个系统推出的命题之一。我的另一个答案，详细写了哥德尔定理的哲学上的影响，以及如果有为真但无法证明的命题，我们如何确认它为真。

2.不完备定理的证明。

哥德尔构造了这样的一个命题：“我无法被公理\Sigma证明”。如果你证明了这个命题，那么这个命题的内容便是不对的，或者说该命题为假。于是系统是有矛盾的。如果这个命题为真，根据它的内容，你无法证明它。

这只是最直观的理解。但与严格的证明还有差距。例如，我们需要这个命题是你事先规定的那个语言（比如自然数的语言，包含+，*，<三个关系，和常数0,1）中的命题，这个命题必须用这个语言来叙述。“我无法被证明”如何用自然数的语言叙述？实际上这是证明的主要技术性部分。

另外你可以思考这样两个问题。

如果我们无法证明这个命题为真，我们如何确定它是真的？

如果你再有一些数学的基础知识就知道，一个命题为真指的是在某个结构中为真，既然公理系统\Sigma无法推出也无法证伪\phi，那么（根据逻辑学的完备性定理）一定存在某个\Sigma的结构，其中哥德尔构造的那个命题为假，那么哥德尔构造的命题，是在哪个结构中为真？

这俩问题是统一的。哥德尔构造的命题在标准自然数结构中为真(原因在后面)。针对一般的语言L上的公理系统\Sigma，它解释自然数论的方式自然的诱导的它的结构编码自然数结构的方式（解释和编码的区别，就像语言+公理，和结构的区别），哥德尔构造的自然数论命题，按照\Sigma解释自然数论的方式自动地转换为语言L表述的命题A，A在编码标准自然数结构的\Sigma的结构中为真。

为了把“我无法被证明”表述成自然数的命题。首先哥德尔用自然数表示命题，用自然数论可定义的关系表示命题与命题之间的逻辑关系。举个例子，用n表示命题A，用m表示命题B，那么用n+m表示命题“A且B”。当然，实际的表示没这么简单，表示"A且B"的自然数是n和m的一个函数，而这个函数是通过自然数论能够定义（通俗的说就是通过+,*等基本运算，可能还配合逻辑量词，组合而成）。总之哥德尔通过用自然数结构表示了（编码了）“证明”，命题间的关系等等关于形式系统\Sigma的命题。然后，他证明他的这个表示（编码）是有效的（忠实的），也就是说，如果把命题“命题A无法被\Sigma证明”按照他的编码方式转换成自然数论的命题A'的时候，如果在自然数结构中A'为真，那么一定真的不存在从\Sigma到A'的一个证明。更严格的说，编码的有效性指，一个关于形式系统\Sigma的命题为真时，当且仅当相应的自然数论命题在标准自然数结构中为真。（这就是为什么哥德尔构造的命题，在标准自然数结构中成立）于是，你如果证明了“我无法被公理系统\Sigma证明”（通过公理系统\Sigma），那么根据编码的有效性，这个命题在标准算数模型中是假的，但这矛盾于它被\Sigma证明，且标准算数模型也是\Sigma的结构。如果这个命题在标准算数模型中是假的，那么根据编码有效性，就真的存在从\Sigma推出该命题的一个证明，但这又矛盾于该命题在\Sigma的一个结构（标准算数模型）中为假。因此只有一种可能，该命题在标准自然数结构中为真，且无法被\Sigma证明。

在构造了这样一种编码并证明其有效性后，哥德尔接着构造命题“我无法被证明”。这个构造并不是非平凡的。因为它是自引用的。命题中"我"指的是命题本身，而这个命题在叙述之前就用“我”引用了它自己，这是非构造性的定义。这个命题的构造非常巧妙，是证明的另一个技术性细节。它类似于打印出自己的代码的一个程序（题主可以试着用不同的程序语言实现一下，就知道是非平凡的了）。如果最初的程序代码只有hellow world，你写下程序“打印'hellow world'”，但这时会发现程序的代码变了（变成“打印'hellow world'”），不得不修改打印的内容，而修改打印的内容会进一步导致程序代码的改变，于是又需要修改打印的内容……冯诺依曼发明了这样的一个程序。他构造的程序分两个部分，A和B。B: 当运行到它时，如果纸上显示内容"C"，那么打印出这样一个程序的代码，这个程序是“打印出内容’C‘ ”。 A: 在纸上打印出B的代码。注意到，A和B都不涉及自引用,而A,B相互打印出了对方的代码。但哥德尔的构造我暂时无法用简单易懂的方式描述。这类自引用的例子有很多，另一个著名的例子是罗素悖论“一个给所有不给自己理发的人理发的理发师”（该理发师是否给自己理发呢）。

额外补充：

的答案也具体描述了哥德尔构造的命题的逻辑形式。

引用他的描述（再加以扩充）。哥德尔构造的命题写作：

对任意x，不存在复杂度在x以内的从公理系统\Sigma出发到\forall n\phi(n)的证明。

其中\phi(n)表示：不存在复杂度在n以内的从公理系统\Sigma出发到命题\forall m \phi(m)的证明。

这里可以看到明显的自引用。复杂度可以是，例如，证明的长度等。哥德尔的命题是一阶的，即用了一个量词“任意”。