INFO

所有变量默认为自然数。

罗素悖论

QUESTION

一个理发师要给所有「不给自己理发的人」理发，不给「给自己理发的人」理发，他是否应该给自己理发？

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

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

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

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

设集合 $A=\{x\mid x\notin A\}$

• 若 $x\in A$，则 $x\notin A$；
• 若 $x\notin A$，则 $x\in A$。

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

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

哥德尔不完备性定理

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

QUOTE

在蕴含 皮亚诺公理（自然数公理） 的公理系统中，必然存在一个「既不能证明，又不能证伪」的命题。

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

哥德尔的证明

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

$$A:\mathrm{\neg }A$$

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

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

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

哥德尔编码

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

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

符号	哥德尔数	含义	符号	哥德尔数	含义
$\mathrm{\neg }$	$1$	否定	$($	$8$	左括号
$\vee$	$2$	或	$)$	$9$	右括号
$\supset$	$3$	如果 ... 则 ...	$,$	$10$	逗号
$\mathrm{\exists }$	$4$	存在	$+$	$11$	加号
$=$	$5$	等号	$\times$	$12$	乘号
$0$	$6$	零	$x$	$13$	变量
$s$	$7$	后继[1]	$y$	$17$	变量

以数学语句 $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(“\mathrm{\neg }(0=s0)”)=2^1\times 3^8\times 5^6\times 7^5\times {11}^7\times {13}^6\times {17}^9$$

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

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

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

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

元数学命题

考虑一类命题：

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

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

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

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

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

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

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

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

根据黑格尔（Hegel）的三段论，上述元命题也能编码为哥德尔数。

sub 函数

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

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

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

EXAMPLE

以 $\mathrm{sub}(15932,6,1)$ 为例：

1. $A=G^{-1}(15932)=“0=0”,B=G^{-1}(6)=“0”$；
2. 将 $A$ 中的 $“0”$ 替换为自然数 $“1”$（即 $“s0”$），得到 $A^{\prime }=“s0=s0”$；
3. 以 $G(A^{\prime })=2^7\times 3^6\times 5^5\times 7^7\times {11}^6$ 为函数值。

即 $\mathrm{sub}(15932,6,13)=2^7\times 3^6\times 5^5\times 7^7\times {11}^6$。

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

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

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

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

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

EXAMPLE

我们走一遍 $\mathrm{sub}(m,17,m)$ 函数的算法：

1. $G^{-1}(m)=M$，$G^{-1}(17)=“y”$；
2. 将 $M$ 中的符号 $“y”$ 替换为自然数 $m$，得到的恰好是 $N$；
3. 以 $G(N)$ 为 $\mathrm{sub}(m,17,m)$ 的函数值。

容易发现，「哥德尔数为 $\mathrm{sub}(m,17,m)$ 的命题」就是 $N$。

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

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

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

布洛斯的证明

INFO

下文以 $D(f),R(f)$ 指称函数 $f$ 的定义域和值域。

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

全函数

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

INFO

此处引入的是狭义上的全函数。广义上的全函数 $f$ 满足 $D(f)\supseteq \mathbb{N}$。

可枚举集

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

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

则 $A$ 是可枚举集。

引理

$A$ 是 可枚举集 $\Rightarrow f$ 是 全函数，$R(f)=A$

充分性证明

若 $A$ 是可枚举集，由定义知，存在一个与之对应的算法。令 $f(n)$ 为此算法的第 $n$ 个输出元素（$n$ 从 $0$ 记起），则 $f$ 是全函数且 $R(f)=A$。

必要性证明

考虑如下算法：逐个计算并输出 $f(0),f(1),f(2),\cdots$ 此算法满足：

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

即得 $R(f)=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{array}{rl}& \mathrm{\forall }n,g(n)=G^{-1}[F(n)](n)\\ \Rightarrow & \mathrm{\forall }n,\mathrm{\exists }x=n,g(x)=G^{-1}[F(n)](x)\\ \Rightarrow & \mathrm{\forall }n,g\text{与}{G}^{-1}[F(n)]\text{有交点}\end{array}$$

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

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

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

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

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

---

1. 符号 $s$ 表示「后继」，$s0=1,ss0=2$，以此类推。 ↩︎

2. 算术基本定理：每个数都有唯一的质因数分解形式，如 $300=2^2\times 3^1\times 5^2$。 ↩︎