哥德尔不完备性定理的证明

如果理发师给自己理发，他就属于「给自己理发的人」，但他不能给这类人理发，矛盾；如果他不给自己理发，他就属于「不给自己理发的人」，但他必须给这类人理发，也矛盾。

英国哲学家罗素（Russell）最早发现了这类悖论。罗素悖论的具体形式还有很多，比如：

• 我正在说的这句话是假话。
• 一张明信片的正面写「背面的话是真的」，背面写「正面的话是假的」。
• 一本书要列出所有「不列出自己书名的书」，这本书是否应该列出它自己？

这些悖论都能以「朴素集合论」的形式概括：

设集合 $A=\{x\mid x\not\in A\}$

• 若 $x\in A$，则 $x\not\in A$
• 若 $x\not\in A$，则 $x\in A$

罗素最终构建了一个新的集合论系统 $\text{ZF(C)}$，取代了朴素集合论。$\text{ZF(C)}$ 通过对集合概念的限定，将 $A=\{x\mid x\not\in A\}$ 这种异端从集合的名单里剔除出去，从而规避了集合论中的罗素悖论。

但是，当我们离开集合论，来到自然数公理系统时，事情似乎变得更加复杂。

1931年，德国数学家库尔特·哥德尔（Kurt Gödel）在他的论文中提出了一个惊为天人的定理：

此定理揭示了公理系统的巨大的缺陷。此缺陷至今未被修复。

哥德尔在皮亚诺公理的环境下找到了一个「 罗素悖论」式的数学命题：

$$A:\neg A$$

• 若 $A$ 是真的，则 $A$ 是假的。
• 若 $A$ 是假的，则 $A$ 是真的。

命题 $A$ 就是「既不能证明，又不能证伪」的数学命题。

那么命题 $A$ 到底是什么？哥德尔是如何找到命题 $A$ 的？

哥德尔创造了一种编码算法，将数学语句编码为自然数。

首先，哥德尔给公理系统的 $12$ 种符号分配了 $12$ 个哥德尔数。变量 $x,y,z,\cdots$ 分配到了 $12$ 以后的质数。

以数学语句 $0=0$ 为例。首先将各个符号转换为哥德尔数：

$$6,5,6$$

再以前 $3$ 个质数为底数，以这些哥德尔数为指数，全部相乘：

$$2^6\times 3^5\times 5^6$$

这样就得到了 $0=0$ 的哥德尔数，记作 $G(“0=0”)=2^6\times 3^5\times 5^6$。

类似地，还有：

$$G(“\neg(0=s0)”)=2^1\times 3^8\times 5^6\times 7^5\times 11^7\times 13^6\times 17^9$$

由算术基本定理² 可知，每个自然数都能解码出唯一的数学语句。例如：

$$G^{-1}(15932)=G^{-1}(2^6\times 3^5\times 5^6)=“0=0”$$

此外，数学证明过程也可编码为哥德尔数。

$$G(“A\intro B\intro C\intro D”)=2^{G(A)}\times 3^{G(B)}\times 5^{G(C)}\times 7^{G(D)}$$

考虑一类命题：

• 命题 $“\neg(0=s0)”$ 的第一个字符是 $“\neg”$。
• 命题 $“\neg(0=s0)”$ 有 $7$ 个字符。
• 哥德尔数为 $a$ 的命题不能被证明。

这类陈述数学命题性质的命题称作「元数学（meta-math）命题」，简称「元命题」。

我们可以利用 哥德尔编码 明智地讨论这些元命题。例如，上述前两个命题等价于：

• $G(“\neg(0=s0)”)$ 有且仅有一个 $2$ 因子。
• $G(“\neg(0=s0)”)$ 能被 $17$ 整除，但不能被 $19$ 整除。

对于第三个命题，哥德尔另外定义了一个命题形式 $\text{Dem}(a,b)$，表示「哥德尔数为 $a$ 的命题」可以证明「哥德尔数为 $b$ 的命题」。

$$\text{Dem}(a,b): G^{-1}(a)\Rightarrow G^{-1}(b)$$

于是「哥德尔数为 $a$ 的命题不能被证明」这样的元命题便可以转化为普通数学命题：

$$(\forall x) \neg\text{Dem}(x,a)$$

根据黑格尔（Hegel）的三段论，上述元命题甚至也能编码为哥德尔数。至于具体是怎么做到的，以后我会出一篇文章细说。

哥德尔证明的核心在于「替换」。

哥德尔定义了一个替换函数 $\text{sub}(a,b,c)$，其算法如下：

1. 将自然数 $a,b$ 解码成数学语句：$A=G^{-1}(a),B=G^{-1}(b)$；
2. 将 $A$ 中的所有 $B$ 替换为自然数 $c$，得到 $A’$；
3. 以 $G(A’)$ 为函数值。

考虑一个关于变量 $y$ 的 元命题 $M$：

$$M:\text{哥德尔数为} \ \text{sub}(y,17,y) \ \text{的命题不能被证明}$$

设 $m=G(M)$。将命题 $M$ 中的符号 $“y”$ 替换为数字 $m$，得到新命题 $N$：

$$N:\text{哥德尔数为} \ \text{sub}(m,17,m) \ \text{的命题不能被证明}$$

那么「哥德尔数为 $\text{sub}(m,17,m)$ 的命题」是什么？哇哦，它居然也是 $N$！

也就是说，命题 $N$ 等价于：

$$N:\text{命题} \ N \ \text{不能被证明}$$

命题 $N$ 就是我们要找的「既不能证明，又不能证伪」的命题。

1994 年，逻辑学家乔治·布洛斯（George Boolos）给出了一个更简单的证明。该证明沿用了 哥德尔编码 方法。

$f$ 是全函数，当且仅当 $f$ 定义在全体自然数上，即 $D(f)=\mathbb{N}$。

对于集合 $A$，若存在算法满足：

• 输出的均为 $A$ 中的元素。
• $A$ 中的任意元素，在有限时间内一定会被输出。

则 $A$ 是可枚举集。

令 $S$ 为所有全函数的 哥德尔编码 集合，即：

$$S=\{G(f)\mid D(f)=\mathbb{N}\}$$

考虑如下命题：

$$M:S \ \text{是可枚举集}$$

假设 $M$ 成立，由引理得，存在全函数 $F,R(F)=S$。

令函数 $g(n)=G^{-1}[F(n)] (n)$。注意到 $R(F)=S$，所以 $F(n)$ 是某个全函数的哥德尔数，则 $G^{-1}[F(n)]$ 是一个全函数，即 $g$ 是全函数。也就是说：

$$\begin{aligned} &\forall n,g(n)=G^{-1}[F(n)](n) \\[5pt] \eq & \forall n,\exists x=n,g(x)=G^{-1}[F(n)](x) \\[5pt] \eq & \forall n,g \ \text{与} \ G^{-1}[F(n)] \ \text{有交点} \end{aligned}$$

由于 $\forall n,G^{-1}[F(n)]$ 涵盖了所有的全函数，上述命题实际上是说 $g$ 与所有全函数都有交点。但这显然不可能。$g$ 是全函数，$g+1$ 也是全函数，但 $g$ 与 $g+1$ 没有交点。故 命题 $M$ 不成立。

现在从另一个角度出发。我们可以按照句子长度一个个枚举字符串，一旦发现字符串对应的函数是全函数，就输出它的哥德尔数。如此一来，我们构建了这样的算法：

• 输出的均为全函数的哥德尔数。
• 任意全函数的哥德尔数，在有限时间内一定会被输出。

此算法符合可枚举集的定义，故 $S$ 是可枚举集，命题 $M$ 成立。

命题 $M$ 就是「既不能证明，又不能证伪」的命题。