你的数学老师可能向你提及过『哥德巴赫猜想』。这个猜想认为，任何一个大于 2 的偶数，都可以表示成两个质数之和。这个猜想自 1742 年提出，尽管未能找到任何反例，但没有人能证明它。是否存在这样一种可能，即虽然哥德巴赫猜想是一个真命题，但是我们永远都无法证明它呢？哥德尔向世人展示，这种可能性是存在的。
哥德尔证明了，在一个定义了自然数（非负整数）、加法和乘法的数学体系中，假设这个体系没有矛盾，也就是不存在既真又假的数学命题，那么一定存在无法被证明的真命题。这一结论被称作『哥德尔不完备定理』。所谓的不完备，是指无法从几条有限的公理出发，推导出所有真命题。也就是说，我们可能无法从自然数公理出发，证明哥德巴赫猜想。哥德尔不完备定理的证明过程十分巧妙，本文将向读者展示，哥德尔是怎么做到的。
自然数、加法、乘法
哥德尔研究的对象是自然数、加法和乘法，这些是数学中最基础的数和运算。为了后文论述方便，这里先介绍相关的背景知识。
我们不加定义地使用下面三个含义确定的词：『数』、『零』、『直接后继』。自然数由下面五条公理确立：
- 零是一个数。
- 一个数的直接后继也是一个数。
- 零不是任何一个数的直接后继。
- 不会有两个不同的数有同一个直接后继。
- 如果零有某种性质，并且有此性质的数的直接后继也有这个性质，则所有的数都有此性质。
第五条公理也被称作『数学归纳法』。
从自然数的五条公理不难看出，我们可以使用零和直接后继这两个概念表示所有的自然数。我们把零写作 \(0\)，并且把 \(s\) 写在一个数的前面表示这个数的直接后继。于是，我们就得到了一系列自然数 \(0\), \(s0\), \(ss0\), \(sss0\),... 因为写这么多 \(s\) 实在是太麻烦，因此又引入了额外的助记符号，将 \(s0\) 写作 \(1\)，\(ss0\) 或者 \(s1\) 写作 \(2\)，\(sss0\) 写作 \(3\) 等等，于是就有了我们熟知的自然数。
根据 \(s\) 在数中出现的次数，我们可以定义加法和乘法。例如，我们可以认为，加法是一种把两个数中出现的 \(s\) 拼接起来的数学运算。例如 \(s0 + ss0\)，第一个数有一个 \(s\)，第二个数有两个 \(s\)，拼接起来一共有三个 \(s\)，所以 \(s0 + ss0 = sss0\)，用助记符号表示就是 \(1 + 2 = 3\)。乘法运算也可以通过类似的方式得到。
定义了加法和乘法之后，人们进一步研究乘法的性质，把大于 1 的自然数分成『质数』与『合数』两类。关于质数与合数，有一个至关重要的结论，会在哥德尔证明中用到：
每个大于 1 的自然数，要么本身就是质数，要么可以写为两个或以上的质数的乘积，而且这些质因子按大小排列之后，写法仅有一种方式。
这个结论被称作『算术基本定理』。
命题演算符号
在数学命题中，我们需要使用一些演算符号，来表达数、变量或表达式之间的关系。常用的符号包括，使用波浪号 \(\sim\) 表示『非』，使用类似 V 型的符号 \(\lor\) 表示『或者』，使用 \(\supset\) 表示『如果……那么……』，使用倒写的字母 \(\exists\) 表示『存在』，等等。使用这些符号，可以方便地书写数学命题。例如
\[
(\exists x) (x = s0)
\]
表示数学命题『存在一个数 \(x\) 是 \(0\) 的直接后继』。很显然这是一个真命题。
哥德尔数
数学命题的内容可以是灵活多样的。在一个仅仅定义了自然数、加法、乘法的体系中，怎么去研究千变万化的数学命题呢？哥德尔创造性地提出了一种方法，可以将任何一个数、变量、表达式、命题（公式）和证明（公式序列）映射为一个确定的自然数。这个数也被称作上述变量、公式等的『哥德尔数』。这样，我们研究数学命题的性质，就可以转化为研究哥德尔数的性质。我们会在后文给出一个具体的例子。在此之前，让我们来看一下哥德尔数是如何计算的。
首先我们定义下面 12 个基本符号的哥德尔数 [1]
| 符号 | 意义 | 哥德尔数 |
|---|---|---|
| \(\sim\) | 非 | 1 |
| \(\lor\) | 或 | 2 |
| \(\supset\) | 如果……那么…… | 3 |
| \(\exists\) | 存在…… | 4 |
| \(=\) | 等于 | 5 |
| \(0\) | 零 | 6 |
| \(s\) | ……的直接后继 | 7 |
| \((\) | 标点符号 | 8 |
| \()\) | 标点符号 | 9 |
| \(,\) | 标点符号 | 10 |
| \(+\) | 加 | 11 |
| \(\times\) | 乘 | 12 |
在数学命题中会用到数字变量如 \(x\), \(y\), \(z\) 等。数字变量可以用数字如 \(ss0\) 或者表达式如 \(x + y\) 等代入。此外，还会遇到命题变量如 \(p\), \(q\), \(r\) 等可以用命题（公式）代入。对每一个不同的数字变量，赋予一个大于 12 的不同质数作为哥德尔数。类似的，对每一个不同的命题变量，赋予一个大于 12 的不同质数的平方数作为哥德尔数。下面展示了一种可能的赋予哥德尔数的结果
| 符号 | 哥德尔数 |
|---|---|
| \(x\) | \(13\) |
| \(y\) | \(17\) |
| \(z\) | \(19\) |
| \(p\) | \(13^2\) |
| \(q\) | \(17^2\) |
| \(r\) | \(19^2\) |
我们刚刚定义了单个符号的哥德尔数。接下来，怎么计算一个数学命题（公式）的哥德尔数呢？这里来看一个例子。假设我们想要计算的公式是
\[
(\exists x) (x = sy)
\]
这个公式一共用到了 10 个符号，分别是左括号、存在、\(x\)、右括号、左括号、\(x\)、等号、直接后继、\(y\)、右括号。假设数字变量 \(x\) 和 \(y\) 的哥德尔数分别是 13 和 17，那么这 10 个符号对应的哥德尔数分别是 8, 4, 13, 9, 8, 13, 5, 7, 17, 9。我们取从小到大排列的前 10 个质数，每一个质数添加一个对应位置的符号的哥德尔数作为指数，并将他们相乘的结果作为整个公式的哥德尔数。因此，上述公式对应的哥德尔数是
\[
2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9
\]
这是一个非常巨大的数字！
为什么要使用这样的方式计算一个公式的哥德尔数呢？在上一节，我们讲到了算术基本定理。给定一个公式的哥德尔数，我们通过质因数分解，可以唯一确定地还原其公式。也就是说，每一个公式都和某一个自然数构成一一对应的关系。
好几个公式组合起来的序列可以构成对一个命题的证明。例如下面的两个公式
\[
(\exists x) (x = sy)
\]
\[
(\exists x) (x = s0)
\]
第一个公式是一个真命题。将 \(0\) 代入 \(y\) 可以得到第二个公式。因此，这两个公式构成的序列是对第二个公式的证明。我们用类似的方法定义一个证明的哥德尔数。假设第一个公式的哥德尔数是 \(m\)，第二个公式的哥德尔数是 \(n\)，则这个证明的哥德尔数是
\[
2^m \times 3^n
\]
这个数字虽然过分巨大，但我们不必计算它的值。我们只需要知道，通过这种方法，可以为任意一个变量、命题和证明赋予一个对应的哥德尔数，就可以了。
[1] 在哥德尔的原始证明中仅仅使用了 7 个符号。使用不同的符号集会影响哥德尔数的大小，但是不影响证明过程。
谈论数学命题的数学命题
我们来研究下面这个简单的数学命题
\[
\sim (0 = 0)
\]
它表达的意思是 \(0\) 不等于 \(0\)。这是一个假命题。接下来，我们提出第二个数学命题：『公式 \(\sim (0 = 0)\) 的第一个符号是波浪号』。第二个命题谈论的对象是第一个命题，因此它也被称作是『元命题』。不难看出，第二个命题是真的。我们的问题是，如何使用符号把第二个命题的数学公式写出来。
为了解决这个问题，我们来研究第一个命题（公式）的哥德尔数。它的哥德尔数是
\[
2^1 \times 3^8 \times 5^6 \times 7^5 \times 11^6 \times 13^9
\]
我们把这个哥德尔数记作 \(a\)。
一个公式的第一个符号由质因子 2 的指数决定。因为波浪号的哥德尔数是 1，所以我们可以把第二个数学命题转化为一个等价命题：\(2\) 是 \(a\) 的一个因子，但 \(2^2\) 不是。这个等价命题用公式写出来就是
\[
(\exists z) (sss...sss0 = z \times ss0) \land \sim (\exists z) (sss...sss0 = z \times ss0 \times ss0)
\]
其中使用了省略号的数字里 \(s\) 的个数为 \(a\)。这里我们引入了一个新的符号 \(\land\) 表示『并且』。它只是一个助记符号，因为它的意义可以用 \(\sim\) 和 \(\lor\) 表达出来，所以我们不需要为这个新符号分配哥德尔数。
现在，我们意识到，有了哥德尔数之后，构造和分析元命题变成了一件可行的事。我们称『公式 \(\sim (0 = 0)\) 的第一个符号是波浪号』这样的命题为『元命题』，而上面的一大串公式为『形式化的元命题』。
最后再讲两个重要概念
在展示哥德尔的证明过程之前，我们还需要理解两个重要概念。
第一个概念是一个元命题：『具有哥德尔数 \(x\) 的公式序列，是哥德尔数为 \(z\) 的公式的证明』。回想一下之前的例子，具有哥德尔数 \(2^m \times 3^n\) 的公式序列，是哥德尔数为 \(n\) 的公式的证明。这两个哥德尔数之间的算术关系，比判定第一个符号是波浪号要复杂一些，不过我们总是可以使用类似的方法把这个元命题写成形式化的公式。为了表述方便，我们把这个命题简写作 \(dem(x, z)\)，并且把对应的形式化的公式写作 \(Dem(x, z)\)。如果 \(dem(x, z)\) 是真命题，那么 \(Dem(x, z)\) 是一个数学定理；如果 \(dem(x, z)\) 是一个假命题，那么 \(\sim Dem(x, z)\) 是一个数学定理。
第二个概念是一个数学运算：『将一个公式的哥德尔数代入该公式的一个变量，并计算代入后的哥德尔数』。举上文用到的一个例子，公式 \((\exists x) (x = sy)\) 的哥德尔数是 \(m\)。这个公式有一个自由变量 \(y\)。如果将数值 \(m\) 代入 \(y\)，我们会得到一个不含有自由变量的新公式
\[
(\exists x) (x = sss...sss0)
\]
其中使用了省略号的数字里有 \(m + 1\) 个 \(s\)。我们使用记号 \(sub(m, 17, m)\) 来表示这个新公式的哥德尔数。这个记号可以理解为，在一个哥德尔数为 \(m\) 的公式中，把哥德尔数为 \(17\) 的变量替换成 \(m\)，从而得到新公式的哥德尔数。类似的，我们使用 \(Sub(m, 17, m)\) 表示新公式的哥德尔数的形式化写法。事实上，\(Sub(m, 17, m)\) 由超级长的一串 \(s\) 符号和一个 \(0\) 构成。
在刚刚给出的例子中，\(m\) 是一个确切的数值。不过我们也可以在 \(m\) 的位置上使用一个自由变量 \(w\)。这样，我们构造出来了一个自变量为 \(w\)，因变量为 \(sub(w, 17, w)\) 的函数。需要注意的是，在代入任何确切的数字之前，数字变量 \(w\) 有一个被赋予的哥德尔数（类似于 \(x\) 的哥德尔数是 13，\(y\) 的哥德尔数是 17），这也就意味着，尽管 \(w\) 是一个变量，形式化的公式 \(Sub(w, 17, w)\) 会有一个确定的哥德尔数。
哥德尔证明
我们来研究下面的形式化公式
\[
(\exists x) Dem(x, z)
\]
这个公式表达的意思是，哥德尔数为 \(z\) 的公式是可以证明的。
与之相对，形式化公式
\[
\sim (\exists x) Dem(x, z)
\]
的意思是，找不到哥德尔数为 \(z\) 的公式的证明。这里可能会有两种情况。第一种情况是，哥德尔数为 \(z\) 的公式描述的是一个假命题，例如 \(\sim (0 = 0)\)，这样当然不可能找到一个证明。第二种情况是，哥德尔数为 \(z\) 的公式描述的是一个真命题，但是这个真命题不可证。
我们应该考察一个怎样的 \(z\) 呢？先观察下面的公式（称为公式 \(F\)）：
\[
\sim (\exists x) Dem(x, Sub(w, 17, w))
\]
公式 \(F\) 表述的意思是，找不到哥德尔数为 \(sub(w, 17, w)\) 的公式的证明。不过这里面，因为 \(w\) 是一个自由变量，所以哥德尔数为 \(sub(w, 17, w)\) 的公式不是一个确切的公式，我们也就没有办法判定这个命题的真假。下一步，给 \(w\) 代入什么具体的数值好呢？
由上一节的讨论可知，因为公式 \(Sub(w, 17, w)\) 有一个确定的哥德尔数，所以公式 \(F\) 同样有一个确定的哥德尔数，我们将这个数字记为 \(k\)。
接下来，我们将公式 \(F\) 的哥德尔数 \(k\) 代入公式 \(F\) 的变量 \(w\)，得到下面的新公式（称为公式 \(G\)）：
\[
\sim (\exists x) Dem(x, Sub(k, 17, k))
\]
公式 \(G\) 的哥德尔数记为 \(g\)，请问，\(g\) 的大小是多少呢？
回忆一下从公式 \(F\) 生成公式 \(G\) 的过程，不就是『将一个公式的哥德尔数代入该公式的一个变量，并计算代入后的哥德尔数』吗？所以
\[
g = sub(k, 17, k)
\]
发现了什么？公式 \(G\) 的意思是，找不到哥德尔数为 \(sub(k, 17, k)\) 的公式的证明。因为这个 \(sub(k, 17, k)\) 等于 \(g\)，所以这句话可以变成，找不到哥德尔数为 \(g\) 的公式的证明。又因为公式 \(G\) 的哥德尔数就是 \(g\)，所以公式 \(G\) 的意思可以进一步表示为：『找不到公式 \(G\) 的证明』。
找不到一个公式的证明，可能因为它本身是假命题，也有可能它是真命题但不可证。那么，公式 \(G\) 是否是一个假命题呢？这里可以用反证法。我们假设公式 \(G\) 是一个假命题，也就是说，能找到公式 \(G\) 的证明。此时，一定找不到公式 \(\sim G\) 的证明。而 \(\sim G\) 代表的意思是『能找到公式 \(G\) 的证明』，找不到能找到公式 \(G\) 的证明，合并起来就是，找不到公式 \(G\) 的证明，而这正是公式 \(G\) 的意思。从假设公式 \(G\) 是假命题出发，结果得出公式 \(G\) 是真命题，引发矛盾。如果自然数公理体系没有矛盾，那么公式 \(G\) 不可能为假命题，它一定为真命题。
哥德尔通过列举了公式 \(G\) 这个例子，证明了自然数公理体系中，存在无法被证明的真命题。
最后，可能会有人问，如果自然数公理体系有矛盾怎么办？如果真的发生这种事，人类的几乎全部数学知识就要推倒重来了。我们还是乐观地相信这种事不会发生比较好。