Self Reference

哥德尔不完备定理

参考 Nagel 与 Newman 的 Godel’s Proof，简单证明如下定理：

任意蕴含鲁滨逊算数的、公理递归可枚举的、一致的形式系统是不完备的。

命题逻辑是最简单的形式系统，其通过逻辑运算符，如 $\lnot$、$\lor$、$\land$、$\to$、$\leftrightarrow$，以及辅助符号，对命题进行组合与推理。

使用两个特定运算符，如 $\lnot$ 和 $\lor$，就能表示其他所有运算符，如 $\lnot p \lor q$ 表示 $p \to q$，甚至单个特定运算符，如 $\uparrow$，也能表示其他所有运算符。

参考 Russell 与 Whitehead 的 Principia Mathematica，给出一个经典的形式系统，包含推理规则 $p, p\to q \vdash q$ 与如下公理：

• $(p \lor p) \to p$
• $q \to (p \lor q)$
• $(p \lor q) \to (q \lor p)$
• $(q \to r) \to ((p \lor q) \to (p \lor r))$

一阶逻辑是更强大的形式系统，其在命题逻辑的基础上引入了量词 $\exist$ 和 $\forall$，以及变量，还可以定义谓词，如 $=$，以及函数，如 +，常见的皮亚诺算数与 ZFC 集合论都属于一阶逻辑。

在一阶逻辑中可以定义一个谓词表示证明的概念，在此基础上定义一致性与完备性。

• 一致性：不能证明 $p$ 且证明 $\lnot p$
• 完备性：可以证明 $p$ 或证明 $\lnot p$

哥德尔证明的核心在于哥德尔数，将系统内的命题编码为数字，就可以构造出一个自我指涉的、断言自身不可证的命题 $G$。

首先定义如下符号：

对命题中的变量符号，定义它们的哥德尔数为大于 $12$ 的素数，如 $x$、$y$、$z$ 定义为 $13$、$17$、$19$，以此类推。

对命题中的自然数，则用符号串表示，如 $1$、$2$、$3$ 用 $s0$、$ss0$、$sss0$ 表示，以此类推。

使用表中定义的符号，可以表示一阶公理，如鲁滨逊算数：

• $\lnot(sx = 0)$
• $(sx = sy) \to (x = y)$
• $\lnot(x = 0) \to (\exists y)(x = sy)$
• $x + 0 = x$
• $x + sy = s(x + y)$
• $x \times 0 = 0$
• $x \times sy = x \times y + x$

对表中未定义的符号，可以使用已定义的符号表示。

考虑数学命题，如：$0 = 0$，其符号对应的哥德尔数依次为 $6$、$5$、$6$，将它们作为素数序列的指数并相乘，得到 $2^6 \times 3^5 \times 5^6$，即此命题对应的哥德尔数为 $243000000$，以此类推，所有数学命题都有对应的哥德尔数。

数学证明由一系列数学命题组成，考虑数学证明，如：$1+1=2$，粗略地由命题 $s0 + s0 = s(s0 + 0)$、$s(s0 + 0) = ss0$、$s0 + s0 = ss0$ 组成，设命题对应的哥德尔数分别为 $a$、$b$、$c$，则此证明对应的哥德尔数为 $2^a \times 3^b \times 5^c$，以此类推，所有数学证明都有对应的哥德尔数。

元数学命题是讨论数学命题的命题，考虑元数学命题，如：$0 = 0$ 以 $0$ 开头，翻译就是命题 $0 = 0$ 的哥德尔数能被 $2^6$ 整除而不能被 $2^7$ 整除，其形式化表示为 $(\exists x)(x \times 64 = 243000000)$ $\land$ $\lnot(\exists x)(x \times 128 = 243000000)$，对应一个更大的哥德尔数。

考虑元数学命题：哥德尔数为 $y$ 的命题不可证，其形式化表示为 $\lnot(\exists x)\text{Dem}(x, y)$，其中 $\text{Dem}(x, y)$ 定义了一个递归谓词，负责检查哥德尔数为 $x$ 的证明是否符合公理和推理规则且以哥德尔数为 $y$ 的命题结尾。

定义递归函数 $\text{sub}(y, 17)$：取哥德尔数为 $y$ 的命题，找到其中所有自由出现的哥德尔数为 $17$ 的符号，替换为代表自然数 $y$ 的符号串，计算新命题的哥德尔数为 $\text{sub}(y, 17)$ 赋值。

考虑元数学命题：哥德尔数为 $\text{sub}(y, 17)$ 的命题不可证，其形式化表示为 $\lnot(\exist x)\text{Dem}(x, \text{sub}(y, 17))$，记哥德尔数为 $n$。

替换得到新命题：哥德尔数为 $\text{sub}(n, 17)$ 的命题不可证，其形式化表示为 $\lnot(\exist x)\text{Dem}(x, \text{sub}(n, 17))$，其哥德尔数恰好为 $\text{sub}(n, 17)$，设此命题为 $G$。

在一致的系统内，假设 $G$ 可证，即哥德尔数为 $\text{sub}(n, 17)$ 的命题可证，满足可证性条件，故 $(\exist x)\text{Dem}(x, \text{sub}(n, 17))$ 可证，即 $\lnot G$ 可证，此时不满足一致性，所以假设不成立，即 $G$ 不可证。

在 $\omega$ 一致的系统内，假设 $\lnot G$ 可证，即 $(\exist x)\text{Dem}(x, \text{sub}(n, 17))$ 可证，已知 $G$ 不可证，故对每个自然数 $m$ 都有 $\lnot\text{Dem}(m, \text{sub}(n, 17))$ 可证，不满足 $\omega$ 一致性，所以假设不成立，即 $\lnot G$ 不可证。

Rosser 改进了上述证明，通过构造 $(\exist x)(\text{Dem}(x, y) \land (\forall z < x)\lnot\text{Dem}(z, \widetilde{y}))$ 表示哥德尔数为 $y$ 的命题可证且不存在其否定的更小证明，将条件 $\omega$ 一致性削弱为一致性。

以上，基于句法给出了一个简洁的、不严谨的证明，没有真值等语义概念。

何物为真

实际上，塔斯基不可定义定理表明，以上编码不能对真值等概念进行，否则就会出现说谎者悖论，例如：此命题非真。

$G$ 在鲁滨逊算术中不可证是一个句法层面的事实，但其真值并非绝对，而是依赖于选择的数学模型。例如，在标准模型中 $G$ 为真，而在某些包含无限大元素的非标准模型中则相反。

真理是相对的还是绝对的？

形式主义：发明数学

形式主义认为，数学是依据公理和推理规则对符号进行操作的形式系统，其真理性在于内部逻辑的自洽，而与符号是否指代外部实在无关。

例如，形式主义认为集合论基于一阶逻辑，而不关心符号串是否表达了集合论或一阶逻辑本身。

例如，形式主义认为连续统假设的独立性即是其问题的解答，可以自由选择连续统的值，从而构建出不同的数学体系。

实在论：发现数学

实在论认为，数学是独立于人类心智的客观实在，其命题具有唯一的确定真值，数学家的任务在于发现并描述这一实在的内在结构与真理。

例如，实在论认为集合论与一阶逻辑并非人为的构造关系，而是对相同数学实在的不同描述。

例如，实在论认为连续统假设尚未解决，连续统具有唯一的真值，而人类当下的模型只是尚未足够取得这一真值。

对于数学实在的认识论问题，哥德尔给出了类似先验哲学的解释：数学是先天综合的，我们存在数学直观从而感知数学实在。

我们的一切知识都是以经验开始的，却并不因此就都是从经验中发源的。

先天的知识，区别于后天的，即在经验中有其来源的经验性的知识，具有必然性和严格普遍性。

综合的判断，区别于分析的，即谓词的概念已经包含在主词之中的判断，能够拓展我们的知识。

一种知识不论以何种方式和通过什么手段与对象发生关系，它借以和对象发生直接关系、并且一切思维作为手段以之为目的的，还是直观。但直观只是在对象被给予我们时才发生；而这种事至少对我们人类来说又只是由于对象以某种方式刺激内心才是可能的。通过我们被对象所刺激的方式来获得表象的接受能力，就叫作感性。所以，借助于感性，对象被给予我们，且只有感性才给我们提供出直观；但这些直观通过知性而被思维，而从知性产生出概念。但一切思维必须无论是直接地还是间接地借助于某些标志最终与直观、因而对我们人类来说与感性发生关系，因为以别的方式不可能有任何对象给予我们。

最后有理由相信：物理实在即数学实在。

参考 Tegmark 的 The Mathematical Universe，我们的物理现实并非仅仅被数学所描述，它本身就是一个数学结构，而所有自洽的数学结构都对应着一个真实存在的平行宇宙。