Contents 4 sections
怎样比较两个无穷集合
两个有限集合谁大谁小,数一数就知道。无穷集合数不完,Cantor 换了一个不需要「数」的办法:一一对应。
若存在从集合 到集合 的双射(一一对应),就称 与 等势,记作 。若存在从 到 的单射,就记 。
按这个定义,许多结论初看很奇怪:
- 正整数和偶数一样多: 是双射,尽管偶数只是正整数的「一半」。
- 正整数和全体整数一样多:按 的顺序排成一列即可。
- 正整数和有理数一样多:把正有理数 排进一张无穷表格,第 行第 列,然后沿着斜线逐条走,跳过已经出现过的值(比如 ),每个正有理数迟早都会被走到。
能和正整数一一对应的集合叫作可数集,也就是能排成一个无穷长队列 的集合。看起来,似乎所有无穷集合都是可数的。
对角线论证
区间 中的实数不可数。
用反证法。假设 中的实数可以排成一列 ,每个实数都出现在某个位置上。把它们写成十进制小数:
现在沿对角线 构造一个新的数 ,规则是
在 中。但对每个 , 的第 位与 的第 位不同,所以 。于是 不在这个列表里,与假设矛盾。
∎证明里有一个容易忽略的细节:有些实数有两种十进制写法,比如 。如果 恰好是这样的数,「第 位不同」就不足以说明 。只有以全 0 或全 9 结尾的小数才有两种写法。这里只用数字 5 和 6 构造 ,它不含 0 和 9,写法唯一,这个问题就不会出现。
同一个想法,换一种说法
对角线论证的核心是:列表里第 个对象,在第 个位置上被故意避开。把「十进制小数」换成任意集合,就得到一个更一般、也更简洁的定理。
对任意集合 ,不存在从 到其幂集 ( 的全部子集组成的集合)的满射。因此 。
设 是任意映射。考虑子集
假设 对某个 成立,问: 在不在 里?
- 若 ,按 的定义 ,矛盾;
- 若 ,即 ,按定义又应有 ,矛盾。
所以 不在 的像中, 不是满射。另一方面 是单射,故 且两者不等势。
∎集合 就是那条「对角线」: 是否属于 ,恰好和 是否属于 相反。
由 定理 2 立即得到一串越来越大的无穷:
无穷没有最大的。 而且 恰好等于 ,这一点要在本系列下一篇里用 Schröder–Bernstein 定理来证明。
留下的问题
在 和 之间,还有没有别的大小?Cantor 猜测没有,这就是连续统假设。它的结局出人意料:Gödel 在 1940 年证明,从通常的集合论公理(ZFC)出发无法否定它;Cohen 在 1963 年证明,也无法证明它。在 ZFC 里,连续统假设既不能证明,也不能否定。