哥德尔不完备性定理

不完备性定理证明

Typographical Number Theory

印符数论（Typographical Number Theory，TNT）是一个形式系统，下面介绍如何构建 TNT。

自然数用类似皮亚诺自然数的方法构建：

\(0\) 表示 \(0\)
\(S0\) 表示 \(1\)
\(SS0\) 表示 \(2\)
……

为了简单，规定只能用 \(a\)、\(b\)、\(c\)、\(d\)、\(e\) 五个字母当变量，如果需要更多变量则用撇号表示，例如 \(a’\)、\(a’’\)。

TNT 包含了以下符号：

加法和乘法：\(+\)、\(\cdot\)
括号：\((\)、\()\)
等号：\(=\)
\(\neg\)；\(\rightarrow\)；\(\wedge\)；\(\vee\)
存在量词符号 \(\exists\)，全称量词符号 \(\forall\) 和表示量词约束的 \(:\)

基于上面的符号，就可以表示一些命题了。例如费马大定理：

\[ \neg \exists a : \exists b : \exists c : ((a \cdot a) \cdot a) + ((b \cdot b) \cdot b) = ((c \cdot c) \cdot c) \]

仿照皮亚诺算术的公理，为 TNT 系统定义下述的公理：

\(\forall a : \neg Sa = 0\)：没有任何自然数的后继是零
\(\forall a : (a + 0) = 0\)：任何数加零都等于它本身
\(\forall a : \forall b : (a + Sb) = S(a + b)\)：自然数的加法
\(\forall a : (a \cdot 0) = 0\)：任何自然数乘以零都为零
\(\forall a: \forall b:(a \cdot Sb)=((a \cdot b) + a)\)：自然数的乘法

以及下面的推导规则：

特称规则：如果 \(u\) 是出现在印符串 \(x\) 中的变元，\(\forall u : x\) 是一个定理，那么 \(x\) 也定理，且对 \(x\) 中的 \(u\) 做任何替换得到的新印符串也是定理（不能替换为已经被量化的变元）
概括规则，如果 \(x\) 是定理，且 \(u\) 在 \(x\) 中自由出现，则 \(\forall u : x\) 也是定理
互换规则：如果 \(u\) 是变元，则 \(\forall u : \neg\) 与 \(\neg \exists u :\) 可互换
存在规则：如果一个项在定理中出现，则可以用一个变元代替这个项，并在前面加上存在量词

等号规则：

对称性：如果 \(r = s\) 是定理，则 \(s = r\) 也是定理
传递性：如果 \(r = s\) 和 \(s = t\) 是定理，则 \(r = t\) 也是定理

后继规则：

如果 \(r = t\) 是定理，则 \(Sr = St\) 也是定理
如果 \(Sr = St\) 是定理，则 \(r = t\) 也是定理

\(\omega\) 不完全与归纳规则

如果一系列无穷的串都是定理，而其全称概述却不是定理，则称之为 \(\omega\) 不完全。

在上面的印符系统中不难证明：

(0 + 0) = 0
(0 + S0) = S0
(0 + SS0) = SS0
……

但是无法直接证明 \(\forall a : (0 + a) = a\)，也无法证明 \(\neg \forall a : (0 + a) = a\)。

因此还需要加上最后一条规则（代表数学归纳法）：

归纳规则：如果 \(u\) 是印符串 \(X\) 中的一个变元，记为 \(X\ u\)。如果把 \(u\) 替换为 \(0\) 时成立，且有 \(\forall u : X\ u \rightarrow X\ Su\)，那么 \(\forall u : Xu\) 是一个定理

加上这些规则后，TNT 已经和一个皮亚诺算术系统等价了。

构造哥德尔数

首先将所有推理规则转换成数字，例如将 \(\forall\) 用 1 表示，\(=\) 用 2 表示，\(0\) 用 3 表示，\(S\) 用 4 表示……由于符号是有限的，因此这一过程可以完成。

对于一个印符串，下面计算它的哥德尔数：

将符号翻译成数字
按顺序将翻译出的数字作为从小到大排列的质数的指数
将得到的幂相乘

例如 \(\forall a\) 就是 \(2^1 * 3^2 = 18\)。由于任何数字可以唯一分解成质数乘积，因此印符串和哥德尔数是一一对应的。那么所有的自然数命题都可以用哥德尔数表示。

然后再引入一个数论谓词：「哥德尔数为 \(a\) 的命题能被证明」。例如 TNT 的五条公理所代表的数字一定是一个哥德尔数。这个谓词的否定形式为「哥德尔数为 \(\neg a\) 的命题能被证明」。

下面我们尝试让 TNT 描述自身：有一个印符串「0」，其在 TNT 中的描述为 \(0\)，对应的哥德尔数为 \(2^3=8\)，那么「\(0\) 能被证明」在 TNT 中的描述为：

\[ 8\text{ can be proved} \]

如果给「哥德尔数为 x 的命题能被证明」分配一个编码 5（设 \(0\) 对应 3，\(S\) 对应 4），那么上面这个这个命题对应表示为：

\[ \underbrace{SSSSSSSS}_{8 \times S}0 \text{ can be proved} \]

对应的哥德尔数为

\[ 2^4 * 3^4 * 5^4 * 7^4 * 11^4 * 13^4 * 17^4 * 19^4 * 23^3 * 29^5 \approx 2.2 * 10^{39} \]

不难发现，「能被证明」这个谓词让 TNT 能够描述自身：TNT 中的串能用自然数表示，而自然数又能用 TNT 描述。

构造自我指涉

最后，我们在 TNT 中构建自我指涉。

首先介绍 \(\mathtt{sub}\) 函数，这是一个用来表示符号替换并计算哥德尔数的函数。对于 \(\mathtt{sub}(a, b, c)\)

这个函数一共有 3 个输入，他们都是正整数
\(a\) 表示原公式，\(b\) 表示替换进去的数字，\(c\) 表示被替换的符号
因此上面公式的含义为：将第一个参数 \(M\) 解码成公式，在其中找哥德尔数为 9 的符号，并将这样的符号替换为符号 \(M\)，替换完成后计算哥德尔数

假设有一个命题 \(x = y\)，设 \(x\) 用 8 表示，\(y\) 用 9 表示。我们将其表示为哥德尔数 \(M = 2^8 * 3^2 * 5^9 = 4500000000\)。现在用 \(M\) 代替 \(y\)，可以得到命题 \(x = 4500000000\)。我们把新公式的哥德尔数记作 \(\mathtt{sub}(M, M, 42)\)，即 \(\mathtt{sub}(4500000000, 4500000000, 42)\)

现在考虑一个自我描述的命题 \(N\)：「哥德尔数为 \(\neg \mathtt{sub}(y, y, 9)\) 的命题能被证明」。这个命题的含义以及真假并不重要，但是这个命题肯定可以用哥德尔数表示，不妨设为 \(N\)。

最后再构建一个命题 \(G\)：「哥德尔数为 \(\neg \mathtt{sub}(N, N, 9)\) 的命题能被证明」（\(N\) 是数字）。那么 \(G\) 也有一个哥德尔数，且 \(G\) 的哥德尔数恰好是 \(\mathtt{sub}(N, N, 9)\)！

命题 \(G\)：「哥德尔数为 \(\neg \mathtt{sub}(N, N, 9)\) 的命题能被证明」的哥德尔数为 \(\mathtt{sub}(N, N, 9)\)。

下面通过计算 \(\mathtt{sub}(N, N, 9)\) 来证明这个命题。

\(N\) 解码为「哥德尔数为 \(\neg \mathtt{sub}(y, y, 9)\) 的命题能被证明」。因此为了计算 \(\mathtt{sub}(N, N, 9)\)，需要找到其中所有哥德尔数为 9 的符号的位置，也就是两个 \(y\)。将两个 \(y\) 替换成数字 \(N\)，得出命题「哥德尔数为 \(\neg \mathtt{sub}(N, N, 9)\) 的命题能被证明」，即命题 \(G\)。然后对替换后得到的命题（即命题 \(G\)）计算哥德尔数，其结果即为 \(\mathtt{sub}(N, N, 9)\) 的值。

因此命题得证。

这个过程实际上构造了一个不动点：设函数 \(g(P)\) 定义为计算命题「哥德尔数为 \(\neg P\) 的命题能被证明」的哥德尔数，那么 \(g(\mathtt{sub}(N, N, 9)) = \mathtt{sub}(N, N, 9)\)。

第一不完备性证明

下面考虑 \(G\) 是否能被证明：

假设 \(G\) 能被证明，那么意味着能证明哥德尔数为 \(\mathtt{sub}(N, N, 42)\) 的命题，与 \(G\) 矛盾，因此 TNT 不一致
假设 \(G\) 不能被证明，这与 \(G\) 的描述一致，即命题 \(G\) 为真。\(G\) 为真，且能被 TNT 描述，但是不能在 TNT 中被证明，这说明 TNT 是不完备的

因此一个包含了皮亚诺算术的体系必然不能既一致又完备。

需要注意的是，上面的证明与罗素悖论无关——即没有产生矛盾，两种情况下的逻辑都是成立的。