读书笔记：《数学女孩 3：哥德尔不完备定理》 | 数理逻辑没入门

luogu_gza · 2026-03-25 22:14:46 · 学习·文化课

本文内容大多抄录自结城浩《数学女孩 3：哥德尔不完备定理》，带有少量的我的见解。

这本书中有若干个错误……我也给他修正了……

本文承认排中律。

本文纯理性愉悦，请勿认真对待。

我们将创造一个形式系统 P，并证明它是不完备的。

诶？不完备是什么意思？意思是存在一个语句 A 使得在其中不存在 A 或 \neg A 的证明。

形式系统 P 的定义

我们这里是在定义一个另类的数学系统（这个表述很不准确！），因此请将你的脑子丢掉。

常量

• 常量 I 0 是常量
• 常量 II \texttt{f} 是常量
• 常量 III \neg 是常量
• 常量 IV \lor 是常量
• 常量 V \forall 是常量
• 常量 VI \texttt{(} 是常量
• 常量 VII \texttt{)} 是常量

变量

• 第 1 型变量：x_1,y_1,z_1,\cdots 是用于数的变量，将其称为第 1 型变量
• 第 2 型变量：x_2,y_2,z_2,\cdots 是用于数的集合变量，将其称为第 2 型变量
• 第 3 型变量：x_3,y_3,z_3,\cdots 是用于数的集合的集合变量，将其称为第 3 型变量

以此类推。

数项和符号

这里我们用类似于皮亚诺公理的方法来表示数。

• 用数项 0 表示 0
• 用数项 \texttt{f0} 表示 1
• 用数项 \texttt{ff0} 表示 2
• \cdots\cdots

我们把 \texttt{0,f0,ff0,}\cdots 称为数项。

符号

我们将 \texttt{0,f0,ff0},\cdots 或 \texttt{x,fx,ffx,}\cdots 称为第 1 型符号，此处设 x 是第 1 型变量。

我们将第 2 型变量称为第 2 型符号。

我们将第 3 型变量称为第 3 型符号。

以此类推第 n(n \geq 4) 型符号的定义。

基本逻辑公式

我们把 \texttt{a(b)} 这种形式的符号序列称为基本逻辑公式。这里设 \texttt{a} 是第 n+1 型符号，\texttt{b} 是第 n 型符号。例如 x_2\texttt{(}0\texttt{)}、y_2\texttt{(ff}x_1\texttt{)}、z_{114}\texttt{(ffff}x_{113}\texttt{)}，他们都是基本逻辑公式。

感性理解一下，就是集合和元素的关系。这也是为什么我们在定义变量的时候强调了它们是【用于数的变量】【用于数的集合变量】【用于数的集合的集合变量】。

逻辑公式

• 逻辑公式 I 基本逻辑公式是逻辑公式

• 逻辑公式 II 若 \texttt{a} 是逻辑公式，则 \neg\texttt{(a)} 也是逻辑公式

• 逻辑公式 III 若 \texttt{a} 和 \texttt{b} 都是逻辑公式，则 \texttt{(a)}\lor\texttt{(b)} 也是逻辑公式。

• 逻辑公式 IV 若 \texttt{a} 是逻辑公式且 x 为变量，则 \forall x\texttt{(a)} 也是逻辑公式。

• 逻辑公式 V 只有满足上述条件的才是逻辑公式

省略形式

• 省略形式 I 将 \texttt{(a)} \to \texttt{(b)} 定义为 \texttt{(}\neg\texttt{(a))}\lor\texttt{(b)}

• 省略形式 II 将 \texttt{(a)}\land\texttt{(b)} 定义为 \neg\texttt{((}\neg\texttt{(a))}\lor\texttt{(}\neg\texttt{(b)))}

• 省略形式 III 将 \texttt{(a)}\leftrightarrows\texttt{(b)} 定义为 \texttt{((a)}\to\texttt{(b))}\land\texttt{((b)}\to\texttt{(a))}

• 省略形式 IV 将 \exist x\texttt{(a)} 定义为 \neg\texttt{(}\forall x\texttt{(a)))}

• 括号的省略 为了看起来方便，后面我们会省略冗长的括号

公理

首先是皮亚诺公理。

• 公理 I-I \neg\texttt{(f}x_1=\texttt{0)}
• 公理 I-II \texttt{(f}x_1=\texttt{f}y_1\texttt)\to\texttt(x_1=y_1\texttt)
• 公理 I-III x_2\texttt{(0)}\land\forall x_1\texttt(x_2\texttt(x_1\texttt)\to x_2\texttt{(f}x_1\texttt{))}\to\forall x_1\texttt(x_2\texttt(x_1\texttt{))}

诶？= 是什么？

• 等于 x_1=y_1\overset{\text{def}}{\Longleftrightarrow}\forall u\texttt(u\texttt(x_1\texttt)\to u\texttt(y_1\texttt{))}

诶？\overset{\text{def}}{\Longleftrightarrow} 是什么？这是将左边的式子定义为右边的式子的意思。

其次是命题逻辑的公理。

• 公理 II-I p\lor p\to p
• 公理 II-II p\to p\lor q
• 公理 II-III p\lor q\to q\lor p

• 公理 II-IV \texttt(p\to q\texttt)\to\texttt(r\lor p\to r\lor q\texttt)

  我也不知道怎么描述这四条公理（大笑）

再次是谓词逻辑的公理。

• 公理 III-I \forall v\texttt{(}a\texttt{)}\to\texttt{subst(}a,v,c\texttt{)}

诶？\texttt{subst} 是什么？

关于自由的与受约束的可以理解为变量与有一定限制条件的变量，在后续我们还会对这一概念做更详细的解释，此处先按下不表。

这里举一这个函数的例子，\texttt{subst(}\neg\texttt(x_2\texttt(x_1\texttt{))},x_1,\texttt{f0}\texttt) 即为 \neg\texttt(x_2\texttt{(f0}\texttt{))}。

• 公理 III-II \forall\texttt(b\lor a\texttt)\to b\lor \forall v\texttt(a\texttt)

这里假设 v 是任意变量，b 中不出现自由的 v。

然后是集合的内涵公理。

• 公理 IV \exist u\texttt(\forall v\texttt(u\texttt(v\texttt)\leftrightarrows a\texttt)\texttt)

这里假设：

• a$ 中不出现自由的 $v

聪明的同学，可以发现这其实是集合的内涵定义……可以理解为"逻辑公式 a 决了集合 u"。

最后是集合的外延公理。

• 公理 V \forall x_1\texttt( x_2\texttt( x_1 \texttt) \leftrightarrows y_2\texttt( x_1 \texttt) \texttt) \to \texttt(x_2=y_2\texttt)

我们将这个逻辑公式进行”形式提升“后的逻辑公式也定为公理，也就是说下面一串逻辑公式都是公理。

• \forall x_1\texttt( x_3\texttt( x_1 \texttt) \leftrightarrows y_3\texttt( x_1 \texttt) \texttt) \to \texttt(x_3=y_3\texttt)
• \forall x_1\texttt( x_4\texttt( x_1 \texttt) \leftrightarrows y_4\texttt( x_1 \texttt) \texttt) \to \texttt(x_4=y_4\texttt)
• \cdots\cdots

可以理解为“集合中的元素表述了集合”。

推理规则

• 推理规则-I 根据 a 和 a\to b 得到 b
• 推理规则-II 根据 a 得到 \forall v\texttt(a\texttt)，这里的 v 是任意变量，可以理解为【既然任意情况下可以导出 a，那么加上 \forall v 也能导出 a】。

哥德尔数

终于，我们要开始研究这个形式系统了！

请注意，我们已回归到普通的数学世界，所以请让你的脑子回来吧。

所谓哥德尔数，就是构建一种符号序列到正整数的映射（但是每个正整数只对应一个符号序列）。

通过这种方法，我们可以将抽象的逻辑符号转换为更方便研究的数字，但我也不知道这样做的动机是什么，可能是因为人们对于数字有更长久更深刻的研究吧！

下文数字均为自然数。

基本符号的哥德尔数

我们将不大于 13 的奇数分配给常量。

我们将大于 13 的质数分配给第 1 型变量。

我们将大于 13 的质数的平方分配给第 2 型变量。

我们将大于 13 的质数的立方分配给第 3 型变量。

以及类推第 n(n\geq 4) 型变量的哥德尔数。

序列的哥德尔数

我们思考形如 n_1,n_2,\cdots,n_m 的哥德尔数序列，定义其哥德尔数为：

其中 \text{prime}_i 为从小到大排列第 i 个质数。

举个例子！如表示 2 的数项 \texttt{ff0}，其对应的哥德尔数序列为 3,3,1，那么它的哥德尔数就是 2^3 \times 3^3 \times 5^1=1080。

符号序列的序列的哥德尔数也类似。

可以发现一些哥德尔数的性质。

• 如果哥德尔数是偶数就表示序列，反之就不表示序列
• 如果哥德尔数质因数分解中 2 的个数是奇数就表示符号序列，如果是偶数就是符号序列的序列

想到用唯一分解定理来保证哥德尔数对应序列的唯一，哥德尔也真是个天才呢

原始递归性

原始递归定义

举个例子 \texttt{factorial}(n)，可以将其定义为：

事实上计算这个式子还需要用到乘法和加法，所以我们稍微深入一下。

如下定义函数 F 时，我们称函数 F 是由函数 G 和 H 经原始递归定义的：

但是实际应用场景中我们的函数可能不止两个变量，因为用下列形式，由函数 G 和 H 定义的函数 F 也是经原始递归定义的：

其中 \vec x 是 x_1,x_2,\cdots,x_{N-1} 的省略形式。

原始递归函数

在定义了【经原始递归定义】这个概念后，我们来定义一下原始递归函数：

• 常量函数是原始递归函数
• 求后继数的函数是原始递归函数
• 由两个原始递归函数经原始递归定义的函数是原始递归函数
• 往原始递归函数的变量里面带入原始递归函数后得到的函数是原始递归函数
• 像 F(\vec x)=x_k 这样的【提取变量值】的投影函数是原始递归函数
• 只有符合上述条件的是原始递归函数

接下来我们来定义原始递归谓词。

• 存在满足 R(n,\vec x) \iff F(n,\vec x)=0 的原始递归函数 F(n,\vec x) 的谓词 R(n,\vec x) 叫做原始递归谓词。

意思大概是 R(n,\vec x) 在对于 F(n,\vec x)=0 做出判定。

原始递归函数的定理

原始递归函数有如下定理：

• 往原始递归函数（谓词）的变量里带入原始递归函数后，所得结果也是原始递归函数（谓词）
• 若 R 和 S 是原始递归谓词，则 \neg R，R\land S，R \lor S 也是原始递归谓词。
• 若 F 和 G 是原始递归函数，则 F=G 是原始递归谓词
• 若 M 是原始递归函数，R 是原始递归谓词，则 S 是原始递归谓词

这里谓词 S 的含义是【对于所有小于等于 M(\vec x) 的 n 都有 R(n,\vec y)】

此处 \vec x,\vec y 分别表示有限个变量序列。

• 若 M 是原始递归函数，R 是原始递归谓词，则 T 是原始递归谓词

这里谓词 T 的含义是【存在小于等于 M(\vec x) 的 n 有 R(n,\vec y)】

此处 \vec x,\vec y 分别表示有限个变量序列。

• 若 M 是原始递归函数，R 是原始递归谓词，则 F 是原始递归函数

这个函数用来求最小的 n \leq M(\vec x) 满足 R(n,\vec y)

此处若合法的 n 不存在，函数值被定义为 0。

表现定理

书中没有提到其证明，我在这里也偷偷略过了！

若 R 是包含两个变量的原始递归谓词，则对于任意数 m,n，都存在包含两个变量的逻辑公式 r，使得以下关系成立：

这里 r\langle \overline{m},\overline{n}\rangle 的意思是把 r 中的变量替换为数项 \overline m,\overline n。

通往证明的漫漫长路

从现在开始，我们要构造谓词【p 是 x 的形式证明】，准备好吧！

首先说明几个定义……

• \forall x \leq M [\cdots]\overset{\text{def}}{\Longleftrightarrow} \forall x[x \leq M \Rightarrow \cdots]
• \exist x \leq M [\cdots]\overset{\text{def}}{\Longleftrightarrow} \exist x[x \leq M \Rightarrow \cdots]
• \min x \leq M [\cdots]\overset{\text{def}}{=} \min x[x \leq M \Rightarrow \cdots]

我们用形如 \boxed{(} 的方式来指代这个字符的哥德尔数。

具体的：

• \boxed{0} \overset{\text{def}}{\Longleftrightarrow} 1
• \boxed{\texttt{f}} \overset{\text{def}}{\Longleftrightarrow} 3
• \boxed{\neg} \overset{\text{def}}{\Longleftrightarrow} 5
• \boxed{\lor} \overset{\text{def}}{\Longleftrightarrow} 7
• \boxed{\forall} \overset{\text{def}}{\Longleftrightarrow} 9
• \boxed{(} \overset{\text{def}}{\Longleftrightarrow} 11
• \boxed{)} \overset{\text{def}}{\Longleftrightarrow} 13

数论

先列出一些基础的数论方面的函数，用来简化后续式子。

• 公理 I-II \texttt{(f}x_1=\texttt{f}y_1\texttt)\to\texttt(x_1=y_1\texttt)
• 公理 I-III x_2\texttt{(0)}\land\forall x_1\texttt(x_2\texttt(x_1\texttt)\to x_2\texttt{(f}x_1\texttt{))}\to\forall x_1\texttt(x_2\texttt(x_1\texttt{))}

• 公理 II-II p\to p\lor q
• 公理 II-III p\lor q\to q\lor p
• 公理 II-IV \texttt(p\to q\texttt)\to\texttt(r\lor p\to r\lor q\texttt)

这里假设 v 是任意变量，b 中不出现自由的 v。

这里假设：

• a$ 中不出现自由的 $v

由 Q 的定义可得：

• A1：\texttt{Proves}(m,n \langle \overline n\rangle) \Rightarrow \texttt{IsProvable}(\texttt{not}(q\langle \overline m,\overline n \rangle))

其中 n \langle \overline n \rangle 定义为 \texttt{subst}(n,\boxed{y_1},\overline{n})。

运用表现定理 I 可以得到：

• B0：Q(m,n) \Rightarrow \texttt{IsProvable}(q\langle \overline m,\overline n \rangle)

由 Q 的定义可得：

• B1：\neg \texttt{Proves}(m,n \langle \overline n\rangle)) \Rightarrow \texttt{IsProvable}(q\langle \overline m,\overline n \rangle)

我们定义 p：

我们将这个 p 记作 p \langle \boxed{y_1} \rangle，有：

• C1：p \langle \boxed{y_1} \rangle=\texttt{forall}(\boxed{x_1},q \langle \boxed{x_1},\boxed{y_1} \rangle)

用 \overline p 代换 \boxed{y_1}，有：

• C2：p \langle \overline p \rangle=\texttt{forall}(\boxed{x_1},q \langle \boxed{x_1},\overline p \rangle)

这里设 p \langle \overline p \rangle 为 \texttt{subst}(p,\boxed{y_1},\overline p)。

我们定义 r。

• C3：r \langle \boxed{x_1} \rangle \overset{\text{def}}{=} q \langle \boxed{x_1},\overline p \rangle

用 \overline m 代换 x_1，有：

• C4：r \langle \overline m \rangle \overset{\text{def}}{=} q \langle \overline m,\overline p \rangle

我们重新拾起 A1。

• A1：\texttt{Proves}(m,n \langle \overline n\rangle) \Rightarrow \texttt{IsProvable}(\texttt{not}(q\langle \overline m,\overline n \rangle))

用 p 代换 n，有：

• A2：\texttt{Proves}(m,p \langle \overline p\rangle) \Rightarrow \texttt{IsProvable}(\texttt{not}(q\langle \overline m,\overline p \rangle))

由 A2 与 C2 有：

• A3：\texttt{Proves}(m,\texttt{forall}(\boxed{x_1},q \langle \boxed{x_1},\overline p \rangle)) \Rightarrow \texttt{IsProvable}(\texttt{not}(q\langle \overline m,\overline p \rangle))

由 A3 与 C3 有：

• A4：\texttt{Proves}(m,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) \Rightarrow \texttt{IsProvable}(\texttt{not}(q\langle \overline m,\overline p \rangle))

由 A4 与 C4 有：

• A5：\texttt{Proves}(m,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) \Rightarrow \texttt{IsProvable}(\texttt{not}(r \langle \overline m \rangle))

我们重新拾起 B1。

• B1：\neg \texttt{Proves}(m,n \langle \overline n\rangle)) \Rightarrow \texttt{IsProvable}(q\langle \overline m,\overline n \rangle)

用 p 代换 n：

• B2：\neg \texttt{Proves}(m,p\langle \overline p\rangle)) \Rightarrow \texttt{IsProvable}(q\langle \overline m,\overline p \rangle)

由 B2 和 C2 有：

• B3：\neg \texttt{Proves}(m,\texttt{forall}(\boxed{x_1},q \langle \boxed{x_1},\overline p \rangle)) \Rightarrow \texttt{IsProvable}(q\langle \overline m,\overline p \rangle)

由 B3 和 C3 有：

• B4：\neg \texttt{Proves}(m,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) \Rightarrow \texttt{IsProvable}(q\langle \overline m,\overline p \rangle)

由 B4 和 C4 有：

• B5：\neg \texttt{Proves}(m,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) \Rightarrow \texttt{IsProvable}(r \langle \overline m \rangle)

我们定义 g。

接下来我们将证明 \neg \texttt{IsProvable}(\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) 与 \neg \texttt{IsProvable}(\texttt{not}(\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)))。

先做一个假设。

• D0：形式系统 P 是相容的。

相容的意思是不存在一个命题 S 使得 S 与 \neg S 都存在形式证明。

我们想要证明 \neg \texttt{IsProvable}(g)，使用反证法，假设 D1 成立。

• D1：\texttt{IsProvable}(\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle))

假设其形式证明为 s，则有：

• D2：\texttt{Proves}(s,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle))

用 s 代换 A5 中的 m，有：

• D3：\texttt{Proves}(s,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) \Rightarrow \texttt{IsProvable}(\texttt{not}(r \langle \overline s \rangle))

由 D2 和 D3 有：

• D4：\texttt{IsProvable}(\texttt{not}(r \langle \overline s \rangle))

由 D1 可知，\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle) 是一个定理，根据公理 III-I，有：

• D5：\texttt{IsProvable}(r \langle \overline s \rangle)

D4 与 D5 可以推出这个形式系统是矛盾的，与 D0 相悖，因此假设 D1 不成立，有：

• D6：\neg \texttt{IsProvable}(\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle))

先做一个假设。

• E0：形式系统 P 是 \omega 相容的。

先来解释一些概念！\omega 矛盾的意思是对于单变量逻辑公式 f \langle \boxed{x_1} \rangle 而言，下面两个条件有能成立。

根据 B5，我们有 E2 对于任意 t 成立。

• E2：\neg \texttt{Proves}(t,\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)) \Rightarrow \texttt{IsProvable}(r \langle \overline t \rangle)

由 E1 和 E2 可得 E3 对于任意 t 成立。

• E3：\texttt{IsProvable}(r \langle \overline t \rangle)

运用反证法，假设 E4 成立。

• E4：\texttt{IsProvable}(\texttt{not}(\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)))

根据 E3 与 E4 可得形式系统 P 存在 \omega 矛盾，与 E0 相悖，因此假设 E4 不成立，有：

• E5：\neg \texttt{IsProvable}(\texttt{not}(\texttt{forall}(\boxed{x_1},r \langle \boxed{x_1} \rangle)))

根据 D6 和 E5，我们可以得到：

• F1：形式系统 P 是不完备的。

以上便是第一不完备定理的证明了，请读者休息休息吧！

第一不完备定理所表述的是，任何 \omega 相容的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题。

这里有些奇怪的是我在网上搜到的表述全都是，任何相容的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题，但是我们在 E0 中使用到了形式系统是 \omega 相容的，但是这篇文章本来就是理性愉悦，所以也无所谓了！

2026.3.31 添加注：\omega 相容其实是一个挺普遍的条件，如果一个形式系统存在 \omega 矛盾，那么它就会有某种程度上的矛盾（即会出现有点违背逻辑的结果），因此第一完备性定理并不是什么只针对很特殊的形式系统的结论！