第3卷 第7章 对角论证法

学习目标

• 能用双射和显式编号区分有限、可数与不可数，并说明整数、有理数为什么可数
• 能按“假设列表完整→翻转对角线→留在目标集合→逐行排除”的顺序完成康托对角论证
• 能解释对角构造在有理数上失效的闭包原因，并区分相容、完备与不可判定
• 能用哥德尔编码、可证明性谓词和对角化描述形式系统如何获得自指结构

从“数列的数列”开始

第3卷第7章由村木老师的卡片开始：

$$\text{证明实数集 }\mathbb R\text{ 不是可数集。}$$

也就是：实数集R不是可数集。

先预测：自然数本身有无穷多个，为什么仍不够给所有实数编号？每个小数位只有10种选择，为什么不能逐位列完？对角线构造出的新数为什么必定不在任何一行？把“实数”换成“有理数”，同样的证明又会在哪里断裂？

后半章把“对角”从实数表格搬进形式系统：公式先变成数，数再作为数项回到公式，由此让一个语句谈论自己的可证明性。

7.1.1 可数集：能逐一编号才算

集合S若能与自然数的某个子集建立双射，就称为可数集。原章把有限集也纳入可数；有些教材用“可数”专指可数无限，并把两者合称“至多可数”，使用前应确认约定。

整数的编号

整数看似向正负两边无限延伸，却可按：

$$0,1,-1,2,-2,3,-3,\ldots$$

排列。显式双射可写成：

$$z_n= \begin{cases} \frac n2,&n\text{ 为偶数},\\ -\frac{n-1}{2},&n\text{ 为奇数}. \end{cases}$$

每个整数在有限位置出现一次，所以\mathbb Z可数。

有理数的编号

正有理数写成p/q。把正整数格点(p,q)按p+q递增沿对角线扫描，并跳过\gcd(p,q)\ne1的重复分数，就能列出每个正有理数一次。再插入0并交替正负，得到整个\mathbb Q的编号。

“有无穷多个元素”与“可数”并不冲突。关键不是列表没有终点，而是任意指定元素都能在某个有限编号处被找到。

挑战：逐位给实数编号

一个看似合理的方案是：

1. 先列小数点后一位的所有小数；
2. 再列两位、三位；
3. 对任意有限位数都能列完；
4. 因此所有小数都能列完。

前三步只覆盖。它们确实可数，因为：

$$\bigcup_{k=1}^{\infty} \{\text{至多 }k\text{ 位的小数}\}$$

是可数个有限集的并。可是1/3=0.333\ldots和\pi/10都没有有限位数。不存在“位数等于无穷”的自然数层可供第四步列出。

7.1.2 Cantor对角论证法

开区间(0,1)与全体实数等势。例如：

$$h(x)=\tan\left(\pi\left(x-\frac12\right)\right)$$

给出从(0,1)到\mathbb R的双射。因此只需证明(0,1)不可数。

使用反证法，假设它可以完整列成：

$$A_1,A_2,A_3,\ldots$$

统一采用不以无限多个9结尾的十进制表示，排除：

$$0.1999\ldots=0.2000\ldots$$

造成的双重写法。把第n行第k位数字记为a_{n,k}：

$$A_n=0.a_{n,1}a_{n,2}a_{n,3}\ldots$$

列表形成一个无限数字矩阵。

读取并翻转对角线

读取：

$$a_{1,1},a_{2,2},a_{3,3},\ldots$$

并定义：

$$b_n= \begin{cases} 1,&a_{n,n}\text{ 为偶数},\\ 2,&a_{n,n}\text{ 为奇数}. \end{cases}$$

于是对每个自然数n：

$$b_n\ne a_{n,n}.$$

构造反对角数B：

$$B=0.b_1b_2b_3\ldots$$

因为b_n只取1或2，B位于(0,1)，也不会产生尾部全9的表示歧义。

与每一行都不同

若列表完整，必存在某个m使：

$$B=A_m.$$

那么两者第m位应相等：

$$b_m=a_{m,m}.$$

但反对角构造同时保证：

$$b_m\ne a_{m,m}.$$

矛盾。因此不存在覆盖(0,1)全部实数的自然数列表，进而：

$$|\mathbb R|>|\mathbb N|.$$

这叫。它不是在列表末尾找遗漏，而是对第n行选择第n个证据，一次性证明新对象不同于每一行。

7.1.3 挑战：给实数编号

村木老师的挑战把“所有有限小数可列”偷换成“所有实数可列”。错误发生在量词：

$$\forall k\in\mathbb N,\quad \text{长度不超过 }k\text{ 的小数可列}$$

不能推出存在一个自然数\infty使所有无限小数位于该层。自然数编号必须是有限自然数；“编号要等无限位全部写完才出现”就没有给出编号。

这也是为什么“听说过对角论证”不等于理解。能复述结论只是记忆，能定位相邻错误论证中的量词跳跃，才说明掌握了证明边界。

7.1.4 挑战：有理数和对角论证法

若把实数列表换成包含(0,1)全部有理数的列表，仍可沿对角线构造B，也仍有：

$$B\ne A_n \qquad \text{对每个 }n.$$

为什么这不证明\mathbb Q不可数？因为结论“B属于目标集合”失效了。

有理数的十进制展开最终循环；反对角逐位修改可能得到不循环小数。因此：

$$B\in\mathbb R$$

有保证，但：

$$B\in\mathbb Q$$

没有保证。若B不在\mathbb Q，它不在有理数列表中完全正常，并不与列表完整性矛盾。

是对角证明不可跳过的一步：构造不只要逃出列表，还必须留在论证的宇宙内。

7.2 形式系统的形式系统

对角思想接下来不再修改小数位，而是让形式语句获得谈论自身的能力。为此先整理系统性质。

7.2.1 相容性和完备性

形式系统T若不存在公式\varphi使：

$$T\vdash\varphi \qquad\text{且}\qquad T\vdash\neg\varphi,$$

就称为相容性（或一致）。

不含自由变量的逻辑公式称为。若对每个语句\varphi：

$$T\vdash\varphi \qquad\text{或}\qquad T\vdash\neg\varphi,$$

至少一方成立，就称T在句法意义下。

若某个语句满足：

$$T\nvdash\varphi \qquad\text{且}\qquad T\nvdash\neg\varphi,$$

它叫不可判定语句，系统因此不完备。

相容只排除“两边都可证”；它不保证“至少一边可证”。漏掉“两边都不可证”的可能，正是泰朵拉在原章中的关键误判。

7.2.2 哥德尔第一不完备定理

现代常用表述是：每个相容、可有效公理化、并能表达足够基础算术的形式理论，都不完备。也就是说，存在语句\varphi满足：

$$T\nvdash\varphi, \qquad T\nvdash\neg\varphi.$$

“满足某个条件”不能删掉。弱系统、不可有效描述的理论或不相容系统并不自动落入同一结论。原始Gödel证明与Rosser改进对假设的精确强度也不同，后续章节会进一步拆解。

7.2.3 算术：把符号交给自然数

算术形式系统需要自然数常量、后继、加法、乘法、相等、量词和变量等符号。符号外形本身没有魔力，只要能彼此区分，就可为每个符号分配一个自然数代码：

$$\sigma_1\mapsto c_1,\quad \sigma_2\mapsto c_2,\quad\ldots$$

于是公式这个有限符号序列变成自然数有限序列：

$$(\sigma_{i_1},\ldots,\sigma_{i_k}) \longmapsto (c_{i_1},\ldots,c_{i_k}).$$

选择自然数，是因为它们能被算术形式系统自身处理。

7.2.4 哥德尔数：形式系统的形式系统

将序列(s_1,\ldots,s_k)打包成一个自然数：

$$\ulcorner s_1,\ldots,s_k\urcorner = 2^{s_1}3^{s_2}5^{s_3}\cdots p_k^{s_k},$$

其中p_k是第k个素数。算术基本定理保证质因数分解唯一，所以编码可解码。

这类哥德尔数使：

$$\text{公式} \longleftrightarrow \text{自然数},$$

形式证明作为公式的有限序列，可再编码一次成为单个自然数。

随后可以用算术关系描述句法：

• Formula(y)：y是否为合法公式的编码；
• Axiom(y)：y是否为公理编码；
• Proof(p,y)：p是否编码了以语句编码y结尾的形式证明；
• Prov(y):=\exists p\,Proof(p,y)：编码为y的语句是否可证。

前三类有限结构检查可机械执行。Prov通过“存在证明编码”在算术中定义，但一般没有总能停机的可证明性判定器；原章也提醒“测定仪”只是帮助理解的比喻。

由此形成往返：

$$\text{形式系统} \longrightarrow \text{算术编码} \longrightarrow \text{算术中的句法谓词} \longrightarrow \text{形式系统内部的算术公式}.$$

用形式系统表示算术，再用算术表示形式系统，这就是“形式系统的形式系统”。

7.2.5 词汇的整理

原章用两栏表防止层级混乱：

含义世界	形式世界
自然数算术	算术形式系统
谓词	含自由变量的逻辑公式
命题	不含自由变量的语句
自然数	数项
关于证明的事实	Proof等算术公式

编码把形式对象带到自然数世界，又把自然数带回形式世界。例如自然数17在含义世界是一个数，在形式系统中则由0和17次后继构成的项\overline{17}表示。

混淆数字17、字符“17”、数项\overline{17}与它们各自的Gödel码，会让自指看似神秘；分层后，每一步都只是明确映射。

7.2.6 数项与7.2.7 对角化

设\varphi(x)是只含一个自由变量的公式，其Gödel码为：

$$e=\ulcorner\varphi\urcorner.$$

把表示e的数项\overline e代入自由变量：

$$\varphi(\overline e).$$

这个结果不再含自由变量，是一个语句。原章把这种“把一变量公式的自身编码数项代回自己”的操作称为。

更完整的固定点引理说明：对任意一变量公式\psi(x)，可构造语句G使系统证明：

$$G \leftrightarrow \psi(\ulcorner G\urcorner).$$

取：

$$\psi(y)=\neg Prov(y),$$

便得到形式上表达“本语句不可证”的G：

$$G \leftrightarrow \neg Prov(\ulcorner G\urcorner).$$

这不是把中文句子硬写成自指，而是先编码句法，再用数项代入和固定点构造完成。第一不完备定理还需证明该语句在给定假设下两边都无形式证明，本章只揭示建筑结构。

互动实验：对角线的两个边界

先预测：如果只改第 r 行第 r 位，为什么能保证新数避开第 r 行？把目标列表换成有理数时，哪一条性质不再自动成立？拖动行号，观察“局部翻转”如何组成“全局排除”。

Diagonal Lab

选择一行，完成一次局部排除

可交互

选择对角线行号：1

当前只排除一行；把 `n` 取遍自然数，才得到与每一行都不同的完整反对角数。

重置实验

7.2.8 数学的定理

哥德尔证明的广度在于从素数编码走到证明谓词，深度在于通过对角化生成自指结构。它像程序：数据是公式编码，检查器是算术谓词，自代入产生固定点。

但结论仍必须留在数学语境。不完备定理研究形式系统的能力边界，也催生可计算性、证明论和模型论的大量成果；它不等于一句可以绕过条件的“任何真理都不可证明”。

米尔嘉决定下次到双仓图书馆继续，并把仍在初中的尤里也叫来。学校边界不应成为讨论边界。

7.3 失物的失物

几天后的游乐园里，米尔嘉与“我”用积木搭Sierpinski三角形和Klein瓶，登上编号17的摩天轮座舱。那个能冷静拆解形式系统的人也会恐高，也会害怕别的事。

章末她借Cinderella提出问题：王子寻找的究竟是丢失的玻璃鞋，还是拥有那只鞋的女孩？这与本章的层级呼应。编码、公式和证明是可操作的“鞋”，数学对象与赋予它们意义的人却不能被编码本身替代；形式相同也不意味着关系与含义相同。

互动路径：把反对角线搬进形式系统

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 先做可数性分类

从“能否给每个对象一个有限编号”开始，分开整数、有理数与实数的证据。

上一步播放下一步

本章回顾：沿对角线跨越两个世界

1. 可数要求存在不重不漏的自然数编号，不只是元素数量“无穷”。
2. 整数可交替正负编号，有理数可沿分子分母格点对角线编号并去重。
3. 所有有限小数可数，但无限小数不属于任何有限长度层。
4. (0,1)与全体实数等势，因此证明前者不可数即可。
5. 反对角数在第n位与第n行不同，所以与列表每一行都不同。
6. 只使用数字1与2可避开十进制尾9双重表示。
7. 追加反对角数只会产生新列表，新列表仍有新的反对角数。
8. 对有理数表做同样构造时，新数未必循环，闭包检查失败。
9. 相容排除公式与其否定双边可证，完备要求每个语句至少一边可证。
10. 语句与否定都不可证时，语句不可判定，系统不完备。
11. 第一定理只适用于相容、有效且足以表达基础算术的形式理论。
12. Gödel编码用自然数和唯一质因数分解表示公式与证明。
13. Proof和Prov把句法事实变成算术关系，使系统能够讨论证明编码。
14. 数项把含义世界的自然数重新带回形式语言。
15. 对角化把公式自身编码的数项代回自由变量，固定点由此谈论自身可证明性。
16. 不完备定理是有明确前提的数学定理，不是泛化的理性宣言。
17. 游乐园收束提醒：形式对象、数学含义与使用它们的人处在不同层级。

练习：检查列表、宇宙与编码

练习

问题 1　说明整数和有理数为什么可数，并指出“无限多个元素”与“可数”之间的区别。

查看答案

整数可按 0,1,-1,2,-2,... 排列；有理数可用分子分母格点的对角线扫描，再约分去重并插入正负。可数要求每个元素在某个有限编号出现，不要求列表有最后一项。

问题 2　给出一个三行小数表 0.135...、0.246...、0.357...，按本章规则写出反对角数的前三位，并说明它与第几行在哪一位不同。

查看答案

对角位是 1,4,7，分别按奇偶翻转为 2,1,2，所以前三位可以写成 0.212...。它在第 n 行的第 n 位与该行不同，因而不可能等于任意一整行。

问题 3　为什么同样的逐位翻转不能直接证明有理数不可数？请写出缺失的集合归属条件。

查看答案

逐位翻转只保证新数是实数；它可能是无限不循环小数，因此不保证属于有理数。要反证有理数列表不完整，必须同时证明 B∈ℚ 与 B≠A_n，而前者通常无法由逐位规则得到。

问题 4　用一句话区分相容、完备与不可判定，再说明哥德尔编码为什么需要质数指数编码。

查看答案

相容排除语句与否定同时可证，完备要求每个语句至少一边可证，不可判定语句则两边都不可证；质数指数编码依靠唯一分解把有限符号序列压成可逆自然数。

概念核对：从集合边界到自指结构

对角论证法用第 n 行的第 n 位制造差异；数列的数列把每行看成一个无限数字序列；可数集要求存在不重不漏的自然数编号。

整数可数来自正负交替编号；有理数可数来自格点对角扫描与约分去重；给实数编号的尝试会在无限位展开处暴露边界。

有限小数属于某个有限长度层；无限小数不属于任何有限位数层；实数集不可数正是所有自然数列表都会被反对角数避开的结论。

开区间与实数等势让我们可以只研究 (0,1)；反证法先假设存在完整列表；实数数字矩阵把每行的每一位放进同一张表。

对角线a_n,n指定第 n 行的第 n 位；反对角数B在这些位置逐一翻转；十进制双重表示提醒我们避开尾部全9的同一实数两种写法。

追加B仍不完整说明把新数加入列表也不会终结过程；挑战给实数编号检验的是量词是否偷换；有限位与无限位区分有限长度层与真正的无限序列。

挑战有理数和对角论证法要求检查目标集合闭包；有理数最终循环是有理数十进制展开的结构特征；反对角数未必有理解释了有理数版本的关键断点。

形式系统的形式系统让算术描述句法；相容性只排除两边同时可证；完备性则要求每个语句至少有一边可证。

自由变量与语句区分带参数的公式和不含自由变量的句子；不可判定语句及其否定都不可证；哥德尔第一不完备定理只在明确假设下给出这样的存在性结论。

算术形式系统提供编码的承载语言；符号用自然数表示把有限字母表变成数字表；哥德尔数把符号序列压缩成一个可逆的自然数。

质数指数编码依靠唯一质因数分解；逻辑公式测定仪检查编码是否对应合式公式；公理测定仪检查编码是否属于公理集合。

证明测定仪检查有限序列是否按规则生成；可证明性测定仪表达“存在某个证明编码”；词汇的整理用两栏表防止数字、数项与编码混层。

数项把自然数重新写回形式语言；对角化把自身编码的数项代回自由变量；自指语句因此能谈论自己的证明性质。

数学的定理必须连同定义域和假设理解；理性的界限误用把条件定理夸大成泛化宣言；失物的失物借故事提醒形式对象不等于对象的意义。

Sierpinski三角形展示递归结构；Klein瓶展示局部方向与整体拓扑的张力；玻璃鞋还是女孩把“编码”与“被编码者”之间的层级差带回叙事。

术语表

名词解释

本章出现的专业名词，用大白话再讲一遍。

可数集

能与自然数某个子集建立双射的集合；每个元素都有一个有限编号。

反证法

先假设结论的反面成立，再由该假设推出矛盾的证明方法。

反对角数B

在列表第 n 行第 n 位改变数字后构造出的、逐行不同于列表的新实数。

相容性

系统不会同时证明某个语句及其否定；它不等于完备或可判定。

不可判定语句

一个语句和它的否定在给定形式系统中都没有形式证明的语句。

哥德尔数

用自然数和唯一质因数分解对符号、公式与证明进行的可逆编码。