希尔伯特纲领提出的数学之完备性、一致性、可判定性和哥德尔第一不完备性定理

· · 学习·文化课

下文中，P_i 表示第 i 个质数。

上世纪，希尔伯特提出了“希尔伯特纲领”，提出数学具有完备性、一致性和可判定性。

具体来说，先在各数学领域定义若干公理。

则所有真命题都可以从公理出发证明，称为完备性。

数学体系不存在矛盾，称为一致性。

存在一种算法可以判断一个命题是否可以从公理出发证明，称为可判定性。

然而，哥德尔证明了：若数学有一致性，则其没有可判定性。

首先，建立哈希表：

符号 读作 哥德尔数
\neg 非 1
\vee 或 2
\Rightarrow 如果，那么 3
\exists 存在 4
= 等于 5
0 零 6
\mathrm{s} 后继 7
( 左括号 8
) 右括号 9
, 逗号 10
+ 加号 11
\times 乘号 12
x x 13
y y 17

然后，建立命题与哥德尔数的关系。

设命题 p = (s0 + s0 = ss0)。

我们取其每一个字符，在哈希表中找到其对应的哥德尔数，然后以质因数分解形式将其作为指相乘。

即设该命题长度为 n，第 i 个字符哥德尔数为 g_i，则其哥德尔数为 \displaystyle \sum_{i = 1}^{n}g_iP_i。

例如，p 的哥德尔数 \mathrm{Godel}(p) = 2^8 + 3^7 + 5^6 + 7^{11} + \ldots。

由算术基本定理得，命题与哥德尔数满足双射。

我们要明确一个概念，命题的哥德尔数是用 \mathrm{Godel} 的方式算出来的，而字符的哥德尔数是通过查表得到的，是 \mathrm{Godel} 的基础。

现设方法 \mathrm{sub}(a, b, c)，表示在 \mathrm{Godel}(p) = a 的 p 中将所有哥德尔数为 c 的字符替换为哥德尔数为 b 的字符。

设 y, n \in \mathbb{N}，满足 n 为不能证明 \mathrm{sub}(y, y, 17) 的哥德尔数。

现令 p 为不能证明 \mathrm{sub}(n, n, 17)。

显然，\mathrm{sub}(n, n, 17) = n。

现设 p 为假命题，则 \neg p 为真，\mathrm{sub}(n, n, 17) 为真，但这与 p 为假矛盾。因为数学具有一致性，所以该假设不成立，p 为真。

当 p 为真时，\mathrm{sub}(n, n, 17) 为真，但其不能被证明。

故而数学不能同时拥有一致性和完备性。\square

现假设可以证明数学具有一致性，则可以证明无法证明 \mathrm{sub}(n, n, 17)，矛盾，故而不能证明数学具有一致性。\square