哥德尔证明是如何起作用的

1931年，奥地利逻辑学家库尔特·哥德尔(Kurt Gödel)取得了可以说是历史上最令人惊叹的智力成就之一。

那个时代的数学家为数学寻找坚实的基础：一套基本的数学事实或公理，既是一致的-永远不会导致矛盾-又是完整的，作为所有数学真理的基石。

但哥德尔在25岁时发表的令人震惊的不完全性定理粉碎了这一梦想。他证明，任何一组你可以假设为数学基础的公理都不可避免地是不完整的；关于数字，总会有一些真实的事实无法用这些公理来证明。他还指出，没有一套公理能够证明自己的一致性。

他的不完全性定理意味着一切都不可能有数学理论，什么是可证明的，什么是真实的，不可能是统一的。数学家能证明什么取决于他们最初的假设，而不是所有答案都来自的任何基本真理。

在哥德尔发现后的89年里，数学家们偶然发现了他的定理所预言的那种无法回答的问题。例如，哥德尔自己帮助确立了与无穷大大小有关的连续体假说是不可判定的，停顿问题也是如此，停顿问题是问一个随机输入的计算机程序是永远运行还是最终停机。在物理学中甚至出现了无法决定的问题，这表明哥德尔式的不完备性不仅困扰着数学，而且--以某种难以理解的方式--困扰着现实。

哥德尔的主要策略是将关于公理系统的陈述映射到系统内的陈述上--也就是说，映射到关于数字的陈述上。这种映射允许公理系统有力地谈论其自身。

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

欧内斯特·内格尔(Ernest Nagel)和詹姆斯·纽曼(James Newman)在1958年出版的“哥德尔的证明”(Gödel‘s Profect)一书中提出了对哥德尔方案稍加修改的版本，从12个基本符号开始，这些符号用作表达一组基本公理的词汇表。例如，某物存在的说法可以用符号∃表示，而加法则用+表示。重要的是，表示“后继者”的符号s提供了一种指定数字的方法；例如，ss0表示2。

接下来，表示变量的字母(以x、y和z开始)映射到大于12的素数(即13、17、19、…)。。

然后，这些符号和变量的任何组合-即可以构造的任何算术公式或公式序列-都会得到它自己的Gödel数。

例如，假设0=0。公式的三个符号对应于哥德尔数字6、5和6。哥德尔需要将这个由三个数字组成的序列变成一个唯一的数字-这个数字是任何其他符号序列都不会生成的。为此，他取前三个素数(2、3和5)，将每个素数提高到序列中相同位置的符号的Gödel数，然后将它们相乘。因此，0=0变成2 6×3 5×5 6，或2 43,000,000。

这种映射之所以有效，是因为不会有两个公式以相同的Gödel数结束。Gödel数是整数，整数只能以单一的方式因式成素数。因此，243,000,000的唯一素因式分解是2 6×3 5×5 6，这意味着只有一种可能的方法来解码Gödel数：公式0=0。

然后，戈德尔更进一步。数学证明由一系列公式组成。所以Gödel也给每个公式序列一个唯一的Gödel数。在本例中，他像以前一样从素数列表开始-2、3、5等等。然后，他将每个素数提升到序列中相同位置的公式的Gödel数(2 243,000,000×…。，例如，如果0=0优先)并将所有内容相乘。

真正的好处是，即使是关于算术公式的语句，称为元数学语句，本身也可以转换成具有自己的Gödel数的公式。

首先考虑公式~(0=0)，意思是“零不等于零”。这个公式显然是错误的。然而，它有一个Gödel数：2的幂为1(符号~的Gödel数)，再乘以3的8次方(“左圆括号”符号的Gödel数)，依此类推，得到2？×3 8×5 6×7 5×11 6×13 9。

因为我们可以为所有公式生成Gödel数，即使是错误的公式，我们也可以通过讨论它们的Gödel数来明智地讨论这些公式。

考虑这样一句话：“公式~(0=0)的第一个符号是波浪号。”这个关于~(0=0)的(真的)元数学陈述转化为关于公式的Gödel数的陈述-也就是说，它的第一个指数是1，即波浪符号的Gödel数。也就是说，我们的说法是，2²×3 8×5 6×7 5×11 6×13 9只有一个因子2，如果~(0=0)以除波浪符号以外的任何符号开始，那么它的Gödel数至少有两个因子2，所以更准确地说，2是2？×3 8×5 6×7 5×11 6×13 9的因子，但2 2不是因子。

我们可以把最后一句话转换成一个精确的算术公式，我们可以用初等符号写下来。这个公式当然有一个Gödel数，我们可以通过将它的符号映射到素数的幂上来计算它。

内格尔和纽曼写道，这个例子“体现了一个非常普遍而深刻的洞察力，这是哥德尔发现的核心：通过谈论大整数的素因式分解的性质，可以间接但完全准确地谈论长符号链的排版性质。”

元数学语句也可以转换成符号，“存在一些Gödel数为x的公式序列，可以证明Gödel数为k的公式”--或者简而言之，“Gödel数为k的公式可以证明。”将这类语句“算术”的能力为政变铺平了道路。

戈德尔的额外洞察力是，他可以在公式本身中替换一个公式自己的Gödel数，这会带来无穷无尽的麻烦。

要了解替代是如何起作用的，请考虑公式(∃x)(x=sy)。(它的意思是，“存在某个变量x，它是y的后继者”，或者简而言之，“y有一个后继者”。)。像所有公式一样，它有一个Gödel数--我们称之为m的某个大整数。

现在让我们在公式中引入m来代替符号y，这就形成了一个新的公式：∃x(X)(x=sm)，意思是“m有一个后继者。”我们应该把这个公式的Gödel数叫做什么呢？有三条信息要传达：我们从具有Gödel数m的公式开始。在该公式中，我们用m代替符号y。根据前面介绍的映射方案，符号y具有Gödel数17。因此，让我们指定新公式的Gödel数sub(m，m，17)。

他考虑了这样一种元数学陈述：“哥德尔数SUB(y，y，17)的公式不能证明。”回想我们刚刚学过的符号，Gödel数SUB(y，y，17)的公式是这样得到的：取Gödel数为y(某个未知变量)的公式，并在有Gödel数为17的符号(即，有y的任何地方)的任何地方代入这个变量y。

事情变得越来越复杂，但尽管如此，我们的元数学陈述--“不能证明具有Gödel数sub(y，y，17)的公式”--肯定会转化为具有唯一Gödel数的公式。我们称它为n吧。

现在，最后一轮替换：Gödel创建了一个新公式，将前一个公式中任何有y的地方都替换为数字n。他的新公式是这样写的：“Gödel数为sub(n，n，17)的公式不能证明。”我们称这个新公式为G。

当然，G有一个Gödel数。它的价值是多少？瞧，它一定是sub(n，n，17)。根据定义，SUB(n，n，17)是公式的Gödel数，它是将Gödel数为n的公式取而代之，只要有一个Gödel数为17的符号，就代之以n。G就是这个公式！由于素因式分解的唯一性，我们现在看到，现在谈论的公式G不是别人，正是G本身。

但是G能被证明吗？如果是这样的话，这将意味着有一些公式序列可以证明具有Gödel数sub(n，n，17)的公式。但这与G相反，G说不存在这样的证据。相反的陈述，G和~G，在一致的公理系统中不可能都是真的。所以G的真相一定是无法判断的。

然而，尽管G是无法决定的，但它显然是正确的。G说，“Gödel数为sub(n，n，17)的公式不能证明，”而这正是我们发现的情况！由于G是真的，但在构造它的公理系统中是不可判定的，所以该系统是不完整的。

你可能认为你可以假设一些额外的公理，用它来证明G，并解决悖论。但你不能。哥德尔证明，扩充的公理系统将允许构造一个新的、真实的公式Gʹ(根据与以前类似的蓝图)，而这个公式在新的扩充系统中是无法证明的。在争取一个完整的数学体系的过程中，你永远抓不住自己的尾巴。

我们已经了解到，如果一组公理是一致的，那么它就是不完整的。这是哥德尔的第一个不完全性定理。第二个问题--没有一套公理能证明自己的一致性--随之而来。

如果一套公理可以证明它永远不会产生矛盾，这意味着什么呢？这意味着存在一系列从这些公理建立起来的公式，它证明了这个公式，从元数学的角度来说，这意味着“这组公理是一致的。”根据第一个定理，这组公理必然是不完整的。

但是“这套公理是不完整的”等同于说，“有一个真实的公式是无法证明的。”这个陈述等价于我们的公式G，我们知道公理不能证明G。

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

哥德尔的证明扼杀了对一致的、完整的数学系统的探索。Nagel和Newman在1958年写道，不完整的含义“还没有完全弄清楚”。这一点在今天仍然是正确的。