可数 — 两种无穷,一种数得过来,一种无论怎么编号都会漏
这一章讲三件事: 「个数」这个词在无穷面前怎么重新定义; 哪些东西能一个个编上号(有些结果会让你意外); 以及有一类东西,无论用什么规律编号,都一定会漏掉其中某一个。
它在全书链条里的位置: 第 13 章说有些问题「跑不完」, 这一章要给出的是一条更硬的界:有些事情在数量级上就不够。 第 17 章那个「谁都写不出来的程序」,靠的正是这一章的数数结果。 需要的基础: 第 15 章的反证法。
1. 先看现象:偶数和整数,哪个多
「0 以上的偶数」是「0 以上 的整数」的一部分——0、2、4、6…… 只占一半。 所以偶数比整数少,对吧?
原书让学生问了这个问题,老师的回答是:可以一一对应——而这正是无限集合特有的一件事1。
编号: 1 2 3 4 5 6 …
偶数: 0 2 4 6 8 10 …
图说:每个编号对着一个偶数,每个偶数也对着一个编号,不漏不重。
所以从「能不能一一对上」这个角度看,它们一样多。
这一节要你先接受一件不舒服的事:在无穷这里,「整体比部分多」不成立。 下面几节就是把这件事讲成可操作的规矩。
2. 「个数」在无穷面前要重新定义
这一节回答:那到底该怎么比较两堆无穷的东西。
平常说「个数」都以「数得完」为前提2。数不完就不知道有多少个, 所以对无穷的东西,不能沿用「数完」这个动作。
原书的替代办法只有一句:不去数它,而是把两堆东西一一对应起来; 能一一对应,就规定它们的「个数」相同3。
「一一对应」这四个字要认真读:它就是第 02、09 章那两条底线—— 既无遗漏,也无重复4。
这里要先补一个词:一堆东西凑在一起,数学上管它叫一个集合,里面的每一样东西叫它的元素。 上一节那张图里的两排数——编号那一排、偶数那一排——各是一个集合。
有了这个词,「可数」就定得出来了:一个集合如果元素个数有限, 或者所有元素都能和正整数一一对应,就叫作可数5。
说白了:能像「第 1 个、第 2 个、第 3 个……」这样按顺序数下去的,就是可数的6。 注意 它不要求你真的数完——只要求存在一条规律, 让每个元素都能既不漏也不重地被编上号7。
3. 三个可数的例子
这一节另起一处走查,把「编号」这件事做三遍。
① 0 以上的偶数8。上一节那张表就是,规律是「第 k 号是 2 × (k − 1)」。
② 全体整数(含负数)9。这个稍微要点技巧:
编号: 1 2 3 4 5 6 …
整数: 0 +1 −1 +2 −2 +3 …
图说:关键在于正负交错着编。
如果先把所有正整数编完再编负数,就永远轮不到负数 ——
因为正整数本身就是无穷的。
③ 全体有理数(能写成分数的数)10。这个最反直觉: 分数看起来「密密麻麻」,任意两个分数之间还夹着无穷多个分数。
但照样能编号。 原书的办法是把所有分数摆成一张二维表—— 横着排分子、竖着排分母——然后沿着斜线走,一个一个编号, 碰到已经出现过的(比如 2/4 和 1/2 是同一个数)就跳过11。
这三个例子的共同点:难的不是数,是设计那条「不漏不重」的编号规律。
4. 意外的一个:所有程序的集合也是可数的
这一节另起第二处走查,而它是通向第 17 章的关键一步。
程序有无穷多种。可「所有程序的集合」是可数的12。
理由是这样13:
① 一个程序,说到底是一串字符 —— 而写程序能用的字符种类是有限的
(26 个小写、26 个大写、10 个数字、几十个符号,加上空格和换行)
② 于是可以按长度从短到长排:1 个字符的、2 个字符的、3 个字符的……
每一档里再按字符编码的顺序排
③ 中间那些不符合语法的字符串当作错误剔掉,剩下的挨个编号
→ 每一个程序都拿到了一个编号,不漏也不重
图说:这里的「一串字符」就是所谓字符串 —— 一段按顺序排好的文字。
整个论证的钥匙只有一句:能用的字符种类是有限的。
(上面那句「一串字符」就是字符串:一段按顺序排好的文字。)
这个结论要记牢:能写出来的程序,可以一个一个编上号。 换句话说,程序的「个数」不比正整数多。
原书还挂了一条脚注,给了另一条更快的路: 把程序看成一串 0 和 1、当成一个二进制数来看,同样能得出程序可数14。
5. 主走查:所有整数数列的集合,数不过来
这一节是全章的主走查。
先说清对象:「无穷个整数排成一排」叫一个整数数列15。比如:
| 名字 | 前几项 |
|---|---|
| 0 以上的整数数列 | 0、1、2、3、4、5…… |
| 0 以上的偶数数列 | 0、2、4、6、8、10…… |
| 1 以上的奇数数列 | 1、3、5、7、9、11…… |
| 斐波那契数列(第 12 章) | 0、1、1、2、3、5…… |
| 全 0 数列 | 0、0、0、0、0、0…… |
| 圆周率各位数字组成 的数列 | 3、1、4、1、5、9…… |
要证的是:所有整数数列的集合不可数16。用第 15 章的反证法。
步骤 1:假设它可数。 那就意味着能给所有整数数列编号, 于是可以排成一张无穷大的表——第 k 个数列排在第 k 行17。
步骤 2:从这张表造出一个不在表里的数列。 办法是只看对角线:取第 1 行第 1 个数、第 2 行第 2 个数、第 3 行第 3 个数…… 每个都加 118。
第1个 第2个 第3个 第4个 第5个 第6个
1号: [0] 1 2 3 4 5 ← 取第 1 个:0
2号: 0 [2] 4 6 8 10 ← 取第 2 个:2
3号: 1 3 [5] 7 9 11 ← 取第 3 个:5
4号: 0 1 1 [2] 3 5 ← 取第 4 个:2
5号: 0 0 0 0 [0] 0 ← 取第 5 个:0
6号: 3 1 4 1 5 [9] ← 取第 6 个:9
对角线上的数: 0 2 5 2 0 9
各加 1 之后: 1 3 6 3 1 10 …… ← 造出来的新数列
图说:方括号里的就是对角线。加 1 是为了「和那一行至少差一处」。
新数列是 1、3、6、3、1、10…… 它在这张表里吗?不在19。
为什么不在?挨行检查一遍:
- 和 1 号数列比:第 1 个数不同(1 ≠ 0)——所以不是 1 号;
- 和 2 号数列比:第 2 个数不同(3 ≠ 2)——所以不是 2 号;
- 和 k 号数列比:第 k 个数一定不同(因为它就是照着第 k 个数加 1 造的)。
所以它和表里的每一行都至少差一处,它不在表里20。
可这张表号称「包含所有整数数列」——矛盾。 所以最初的假设错了:所有整数数列的集合是不可数的21。主走查走完了。
这套论证叫对角论证法,是康托尔提出的22。
6. 学生的追问:把它补进表里不就行了
这一节回答一个每个人都会想到的问题,而原书用师生对话答了。
学生问:既然造出来的那个数列不在表里,把它补进去、再做一版新表不就行了?
老师的回答是:不行23。因为对新表再做一次同样的操作, 又会造出一个不在新表里的数列。
这就是「不可数」的真正含义:不是「这张表漏了一个」, 而是「不管你怎么做表,一定会漏」24。
注意这里的落点:结论不是关于某一张表的,是关于「所有可能的编号规律」的。
7. 这一招的边界:对有理数就不灵
这一节交代最容易用错的地方,而原书同样用师生对话讲了。
学生又问:有理数也能写成小数,那用对角论证法是不是能证明有理数不可数?
老师说:不能25。
理由: 对角线改出来的确实是一个小数,但不能保证它是有理数26。 有理数写成小数一定是循环小数,而新造出来的那个小数不一定循环。
对角论证法真正证明的是:「造出来的那个东西不在表里」。
它要成立,还差一步 —— 「造出来的东西必须属于你正在讨论的那一类」。
整数数列:对角线加 1 之后仍然是整数数列 ✓ → 论证成立
有理数: 对角线改完之后不一定是有理数 ✗ → 论证不成立
图说:这就是这一招唯一的坑,而它在第 17 章还会再出现一次。
这条边界非常要紧,第 17 章有一道思考题专门考它。
8. 顺带一个:函数的集合也不可数
这一节把结论推到第 17 章要用的那个形式。
「输入一个正整数、输出一个整数」的函数,有多少个? 答案是:和整数数列一样多——所以也不可数27。
理由是一一对应28:
函数「给定整数加 1」 ←→ 数列 2、3、4、5、…
函数「给定整数求平方」 ←→ 数列 1、4、9、16、…
函数「是质数就输出 1,否则 0」←→ 数列 0、1、1、0、1、0、…
图说:一个函数,把它在 1、2、3、… 上的输出依次写出来,就是一个整数数列;
反过来,一个整数数列也决定了一个函数。两边一一对应。
把第 4 节和这一节并排放,就是第 17 章的地基:
| 可数吗 | |
|---|---|
| 所有程序 | 可数——能一个个编号 |
| 所有函数 | 不可数——无论怎么编号都会漏 |
编得完的东西,盖不住编不完的东西。第 17 章就从这里开始。
9. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 无穷集合的「个数」用一一对应来定 | 给了理由:数不完,所以不能用「数完」这个动作 |
| 偶数、整数、有理数都可数 | 给了三条编号规律,不是断言 |
| 程序的集合可数 | 给了完整论证(字符种类有限 → 按长度排 → 编号) |
| 整数数列的集合不可数 | 给了完整走查(对角线 + 1),并回答了「补进去行不行」 |
| 对角论证法对有理数不灵 | 给了理由(造出来的小数不一定循环),而且是用师生对话点破的 |
判断(我们的,不是书里的):这一章的价值不在「数学上有两种无穷」, 在于它示范了一种非常硬的论证形式——「无论你怎么做,都一定会漏」。 平时我们说「做不到」,多半意思是「我没想到办法」; 而这一章的「做不到」是对所有可能的办法一次性封死的。 能分清这两种「做不到」,是这一章唯一要带走的东西。 如果错,会错在: 这种论证有个前提——你得先把「所有可能的办法」刻画清楚 (这里是「所有编号规律」)。刻画不清,封不死。判据是: 你能不能说出「任意一种办法」长什么样。
这一章的边界:
- 没有讲「基数」这套概念的正式体系(原书只在师生对话里提了一句这个词);
- 没有讲实数不可数的完整证明,只说了「0 到 1 之间的实数也不可数」和做法;
- 没有讲连续统假设之类的后续问题;
- 程序可数的论证依赖「字符种类有限」,原书没讨论无限字符集的情形;
- 对角论证法这一节严重依赖那张表,原书是用图给的,我们照文字重画了一张。
10. 可带走的
- 在无穷面前,「整体比部分多」不成立:偶数和整数能一一对应;
- 比较两堆无穷,不数它们,而是看能不能一一对应——能对应就规定「个数」相同;
- 一一对应 = 不漏 + 不重,还是第 02 章那两条底线;
- 能一个个编上号的,叫可数;不要求真的数完,只要求存在那条编号规律;
- 偶数、全体整数、有理数都可数;整数要正负交错编,有理数要沿斜线走并跳过重复;
- 所有程序的集合也可数——因为程序是有限种字符排成的有限长字符串;
- 所有整数数列的集合不可数:取对角线上的数各加 1,造出来的那个必定不在表里;
- 「不可数」不是「这张表漏了一个」,是「不管怎么做表都会漏」;
- 这一招叫对角论证法,是康托尔提出的;
- 它有一个坑:造出来的东西必须仍然属于你讨论的那一类——对有理数就不成立;
- 程序可数、函数不可数——这一条是第 17 章的地基。
11. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 整体与部分能一一对应 | 第8章 不可解问题 | text/13-ch08.txt:165(搜「都是「1 以上的整数」的一部分」) · :171(搜「这正是无限集合的特征」) |
| 可数的定义 | 第8章 不可解问题 | text/13-ch08.txt:131(搜「被定义为可数」) · :138(搜「简而言之」) · :143(搜「元素可按一定规律既无」) |
| 偶数、整数、有理数的编号 | 第8章 不可解问题 | text/13-ch08.txt:156(搜「0 以上的所有偶数的集合是可数的」) · :180(搜「重点在于正数和负数的交互编号」) · :190(搜「所有有理数的集合是可数的」) |
| 程序的集合可数 | 第8章 不可解问题 | text/13-ch08.txt:271(搜「符合编程语言语法的有限字符的排列」) · :290(搜「可以按从短到长的顺序排列」) · :293(搜「因此，程序的集合是可数的」) |
| 整数数列与对角论证法 | 第8章 不可解问题 | text/13-ch08.txt:312(搜「现将」) · :338(搜「是不可数的」) · :411(搜「设第 1 个整数数列的第 1 个数 +1」) · :420(搜「至少有 1 处不同」) |
| 康托尔 | 第8章 不可解问题 | text/13-ch08.txt:430(搜「这种论」) · :431(搜「对角论证法是康托尔」) |
| 补进表里行不行 | 第8章 不可解问题 | text/13-ch08.txt:436(搜「再做一版」) · :441(搜「所以肯定会存在」) |
| 对有理数不灵 | 第8章 不可解问题 | text/13-ch08.txt:484(搜「能证明」) · :489(搜「但是不能保证这个小数肯定是」) |
| 函数的集合不可数 | 第8章 不可解问题 | text/13-ch08.txt:501(搜「所有函数的集合也是不可数的」) · :504(搜「给定整数加 1 的函数」) |