本文以英文撰写。中文版由 DeepSeek 翻译。原文请参阅 英文版。

引言

有两个有趣的悖论与哥德尔不完备定理密切相关：罗素悖论和贝里悖论。

罗素悖论：
$\text{设 } R = \{ x | x \notin x \}$

罗素悖论的一个更普遍的形式是：

一个理发师只给那些不自己刮胡子的人刮胡子。理发师会给自己刮胡子吗？

很容易推导：
理发师给自己刮胡子 $\Leftrightarrow$ 理发师不给自己刮胡子。
如果 $R \in R$，那么 $R \notin R$；如果 $R \notin R$，那么 $R \in R$。
$R \in R \Leftrightarrow R \notin R$ 导致矛盾。

贝里悖论：

所有正整数都可以用少于六十个字母定义。

设 $n$ 为不能用少于六十个字母定义的最小正整数。那么 $n$ 可以用少于六十个字母定义，导致矛盾。

这两个悖论都包含自我引用，这是哥德尔不完备定理的关键。

希尔伯特计划

希尔伯特计划的主要目标是建立一些基本公理，然后将这些公理用形式语言表达，以便能够证明所有数学定理。

希尔伯特希望证明这个系统具有以下美妙性质：

1. 一致性：系统不应该能够证明矛盾。
2. 完备性：系统应该能够证明所有真实的数学命题。
3. 可判定性：系统应该能够确定一个命题是真是假。
4. 保守性：系统应该能够在不添加新公理的情况下证明所有真实的数学命题。

如果希尔伯特计划能够完成，那么所有数学问题都可以通过计算机解决，数学将变得无懈可击。

我们必须知道，我们必将知道。
— 大卫·希尔伯特

哥德尔第一不完备定理

哥德尔第一不完备定理指出，存在真实的数学命题在系统中无法被证明。

哥德尔第一不完备定理的证明基于一个自我引用悖论。

以下是哥德尔证明其定理的简化、非正式概述。

哥德尔编码

哥德尔编码是一种将数学命题编码为数字的方法。

1. 为每个符号分配一个唯一的数字。
   整个符号表如下：

   常量符号	哥德尔数	通常含义
   \~{}	1	非
   $\lor$	2	或
   $\supset$	3	如果…那么…
   $\exists$	4	存在一个…
   $=$	5	等于
   $0$	6	零
   $S$	7	后继
   $($	8	左括号
   $)$	9	右括号
   $,$	10	逗号
   $+$	11	加
   $\times$	12	乘

2. 为表示变量的字母分配大于12的质数。
   对于 $x, y, z, \ldots$，分配13, 17, 19, $\ldots$。

然后，这些符号和变量的任何组合——即可以构造的任何算术公式或公式序列——都会获得自己的哥德尔数。

要将公式映射到数字，可以使用以下公式：
$\text{哥德尔数} = 2^{a_1} \times 3^{a_2} \times 5^{a_3} \times \ldots \times p_n^{a_n}$
其中 $a_1, a_2, \ldots, a_n$ 是公式中符号的哥德尔数。

以公式 $x \times 0 = 0$ 为例：

$x \times 0 = 0$ 的哥德尔数为 $2^{13} \times 5^{6} \times 12^{11} \times 6^{6} \times 5^{6}$。

这种构造方法确保系统中的所有公式都可以编码为唯一的一串质数的乘积。

由于所有数字都可以唯一地分解为质数，我们可以通过分解哥德尔数轻松地将数字解码为唯一的原始公式。

元数学的算术化

真正的好处是，即使是关于算术公式的陈述，称为元数学陈述，也可以被翻译成具有自己哥德尔数的公式。

例如，陈述“公式 ~(0 = 0) 的第一个符号是波浪号。” 这个关于 ~(0 = 0) 的（真实）元数学陈述被翻译成关于公式哥德尔数的陈述——即，它的第一个指数是1，波浪号的哥德尔数。换句话说，我们的陈述说 $2^1 \times 38 \times 56 \times 75 \times 116 \times 139$ 只有单个因子2。如果 ~(0 = 0) 以波浪号以外的任何符号开头，它的哥德尔数将至少有两个因子 $2$。因此，更准确地说，$2$ 是 $2^1 \times 38 \times 56 \times 75 \times 116 \times 139$ 的因子，但 $2^2$ 不是。通过这种映射，我们可以将元数学陈述翻译成关于哥德尔数的陈述。

对于元数学陈述，“存在一个哥德尔数为x的公式序列，证明哥德尔数为k的公式”——或者简而言之，“哥德尔数为k的公式可以被证明。” 这种陈述的“算术化”能力为哥德尔的证明奠定了基础。

值得注意的是，映射方法并不是哥德尔不完备定理的关键，但它是证明的基础。利用任何其他映射方法，仍然可以进行证明。我们不需要关心所有数学陈述是否可以编码为数字。

证明

取、找、替换

哥德尔第一不完备定理的整个证明基于一个自我引用悖论。自我是让所有魔法发生的关键。

为了更容易理解，我构造了一个陈述 $M$，它说，$(\exists x)(x=sy)$。$M$ 的哥德尔数标记为 $m$。

然后我们将 $M$ 中的 $y$ 替换为 $m$，得到一个新的陈述 $N$，它说，$(\exists x)(x=sm)$。$N$ 的哥德尔数标记为 $n$。

现在我们可以定义一个特殊函数 $\mathrm{sub}(a, b, c)$。$\mathrm{sub}(a, b, c)$ 的结果是一个新命题的哥德尔数。

$\mathrm{sub}(a, b, c)$ 的新命题的构造包含三个步骤：

1. 取哥德尔数为 $a$ 的命题，标记为 $A$。
2. 找命题 $A$ 中哥德尔数为 $c$ 的符号的位置。
3. 替换该位置为数字 $b$。

让我们继续使用上面的例子，我们想知道哥德尔数为 $\mathrm{sub}(m, m, 17)$ 的命题是什么。

我们遵循TFR三个步骤：

1. 取哥德尔数为 $m$ 的命题。
   命题是 $(\exists x)(x=sy)$，标记为 $M$。
2. 找命题中哥德尔数为 $17$ 的符号的位置。
   哥德尔数为 $17$ 的符号是 $y$。
3. 将该位置替换为数字 $m$。
   命题变为 $(\exists x)(x=sm)$。

自我引用命题的构造

首先，我们构造一个新的命题，它说，“无法证明哥德尔数为 $\mathrm{sub}(y, y, 17)$ 的命题”。我们将这个命题标记为 $N$，哥德尔数为 $n$。

这里可能会引起一些混淆。我们仍然使用TFR三个步骤来找到哥德尔数为 $\mathrm{sub}(y, y, 17)$ 的命题：

1. 取哥德尔数为 $y$ 的命题。
   命题标记为 $Y$。命题可能包含许多符号，包括 $y$，它是哥德尔数为 $17$ 的符号。
2. 找命题 $Y$ 中哥德尔数为 $17$ 的符号的位置，即 $y$。
3. 将该位置替换为数字 $y$。

令人困惑的部分是，$y$ 有时作为符号，有时作为数字。在步骤2中，我们需要在命题 $Y$ 中找到哥德尔数为 $17$ 的符号的位置。但在步骤3中，我们需要将该位置替换为原始 $\mathrm{sub}(y,y,17)$ 中的数字 $y$。

符号 $y$ 在这里扮演了不同的角色，但它们本质上是相同的。

之前，我们有一个命题 $N$，它说，“无法证明哥德尔数为 $\mathrm{sub}(y, y, 17)$ 的命题”。$N$ 的哥德尔数为 $n$。

我们继续我们的构造，得到一个新的命题 $P$，它说，“无法证明哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题”。

专注于 $P$ 中的哥德尔数 $\mathrm{sub}(n, n, 17)$，我们仍然使用TFR三个步骤来找到哥德尔数 $\mathrm{sub}(n, n, 17)$ 的命题：

1. 取哥德尔数为 $n$ 的命题。
   命题是 $N$，它说“无法证明哥德尔数为 $\mathrm{sub}(y, y, 17)$ 的命题”。
2. 找命题中哥德尔数为 $17$ 的符号的位置。
3. 将该位置替换为数字 $n$。

最后，我们得到哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题，它说，“无法证明哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题”。这个命题的哥德尔数恰好是 $\mathrm{sub}(n, n, 17)$。

让我们仔细看看哥德尔数 $\mathrm{sub}(n, n, 17)$ 和它的命题 $P$。命题说，“无法证明哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题”。

如果 $P$ 是假的，这意味着可以证明哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题，那么哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题是真实的。但哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题说，“无法证明哥德尔数为 $\mathrm{sub}(n, n, 17)$ 的命题”。这导致矛盾。

唯一解决悖论的方法是命题 $P$ 是真实的。

因此，命题 $P$ 成为一个真实但无法证明的命题，这证明了希尔伯特的完备性属性是不可能的。

这就是哥德尔第一不完备定理的核心。

任何一致的、能够进行一定量初等算术的形式系统 $F$ 都是不完备的；即，存在 $F$ 语言中的命题，这些命题在 $F$ 中既不能被证明，也不能被否定。

哥德尔第二不完备定理

对于任何一致的、能够进行一定量初等算术的形式系统 $F$，$F$ 的一致性不能在 $F$ 自身中证明。

我们证明第一不完备定理的唯一条件是系统的一致性。

第二不完备定理是第一不完备定理的直接结果。如果 $F$ 的一致性可以在 $F$ 中证明，那么我们可以在 $F$ 中证明命题 $P$。但命题 $P$ 在 $F$ 中无法被证明。这导致矛盾。

唯一解决悖论的方法是 $F$ 的一致性不能在 $F$ 自身中证明。

顺便提一下，哥德尔于1947年移民到美国。当他参加公民身份测试时，他发现了美国宪法中的一个矛盾，并告诉了阿尔伯特·爱因斯坦。然而，他并没有向其他人指出这一点。

图灵的停机问题

哥德尔不完备定理指出，形式系统的一致性和完备性不能在系统自身中证明。图灵的停机问题进一步证明了数学是不可判定的。