动机
有限集合用自然数计数;无限集合则先比较映射。两个集合可以双射配对时,称它们大小相同。真子集可能与母集合等势,所以有限计数的直觉需要重新检查。
公理也影响论证。给出一个枚举,和知道每个集合各自存在某个枚举后,再为整族集合同时选取枚举,是不同的步骤。后者可能涉及选择原则。本节在 ZF 中证明主要比较结果,并指出可数性证明中隐藏选择的位置。
定义
定义 2.1.1
(大小比较与可数性)
存在双射 记为 ;存在单射记为 。若前者不成立而后者成立,记为 。符号 可理解为这种大小比较,不必预设每个集合都对应某个最小等势序数。
能单射到 的集合称为至多可数,与 双射的称为可数无限。非空的至多可数集合是某序列的值域:在单射的像上取逆,未使用的指标填入一个固定元素。反过来,若 满射,把每个元素送到首次出现的指标,就得到到 的单射。所以枚举允许重复。
对可良序集合,最小的等势序数称为初始序数,也称基数。 是第一个无限基数,记为 。没有选择公理时,不应默认任意集合都可良序。
命题 2.1.2
(大小比较的基本法则)
对任意集合 :
- 具有自反性、对称性和传递性; 具有自反性和传递性。
- 若 ,则 。若 且 ,则 当且仅当 。
- 若 且 ,则存在满射 。
- 若 且 ,则 。
证明
(复合、限制,并用一个固定点补足)
恒等映射给出自反性。双射的逆仍是双射,单射(或双射)的复合仍是单射(或双射)。这证明了第 1 项。第 2 项中,包含映射 是单射。若 、 是双射, 是单射,则 是单射;反方向同理。
第 3 项中,固定单射 及一个元素 。从一个非空集合中固定一个元素只是一次存在例示,不是使用选择公理。定义 :当 时, 是满足 的唯一 ;否则 。其图像可从 中分离出来,而且 ,所以 是满射。
第 4 项中,传递性给出 。若 ,则 ,再加上 ,由下文的 Cantor–Schröder–Bernstein 定理得 ,与 矛盾。
没有选择公理时,第 3 项的逆命题可能不成立;见常见错误中关于反转满射的一条。另有两点需要注意。第一, 在相差 的意义下具有反对称性,完全依赖 Cantor–Schröder–Bernstein 定理,而这需要证明。第二,ZF 不能证明任意两个集合都可比较。事实上,“对任意集合 ,都有 或 ”等价于选择公理;选择一章将把集合与它的 Hartogs 序数比较,以证明这一点。
定理/命题
定理 2.1.3
(Cantor–Schröder–Bernstein 定理)
若存在单射 和 ,则 。不需要选择公理。
定理 2.1.4
(Cantor 定理)
对每个集合 ,不存在满射 ,所以 。
概念视角组合
把 Cantor 对角论证看成一张表
通过第二道练习的双射 ,映射 就是一张表:每个 对应一行,每个 对应一列,元素为 。对角集 的示性函数,就是读出对角元素 后把每一个翻转所得。这个新行在第 列与第 行不同,所以它不是表中任何一行。当 时,这正是二元序列列表的熟悉图景。
定理 2.1.5
(已给枚举的并)
若同时给定每个非空 的满射 ,则 至多可数。在 ZF 中,仅说每个 至多可数,尚未提供该证明所用的整列枚举。
证明思路
证明
(以从 出发的链分割)
令 ,递归定义 ,并令 。定义
第二分支有定义,因为 ,且 单射。每个分支单射;若 ,其中 、,则 ,矛盾,所以两分支的像不交。对任意 ,若 ,第二分支取到 ;若 ,它不在 ,故属于某个 。由 的单射性,,其中 ,所以第一分支取到 。这证明双射。
证明透视
链的起点与反向分支的定义域
集合 收集了从 出发、反复作用 所能到达的每一点。证明依赖 的三个性质。第一,,所以 以外的每一点都属于 ,分支 在那里有定义。第二, 在 下封闭;这正是两个分支不会相撞的原因,因为一旦相撞, 以外的某点就会落入 。第三, 的每一点都形如 ,其中 ,这正是满射性所需。
整个论证只用到 、 的单射性、 上的普通递归和分离公理。每个 都唯一确定,所以没有作任何选择。在 本身已是满射的边界情形,、,而 。
证明
(对角集合)
假设 满射。分离构造
若 ,便有 ,矛盾。另一方面 单射;双射必为满射,已被排除。此证明也适用于空集。
证明
(配对各个枚举)
从 满射到并集,而
把第 条对角线依次排列,给出到 的双射。复合后再取首次出现指标,即得可数性。若允许空 ,按自然顺序枚举非空指标;若全空,并集为空。关键是已经给出整族枚举。
例题
例题 2.1.6
(枚举有理数)
每个有理数有唯一既约表示 ,其中 、 为正整数。 显式枚举整数,配对函数枚举整数与正整数的所有配对,再送到 。重复无妨。又有 ,故由 Cantor–Schröder–Bernstein 定理或首次出现构造得 。
例题 2.1.7
(有限字符串与无限序列)
二进制有限字符串按长度、同长度按字典序排列,每个长度 有 个,所以每个字符串出现在有限位置。用固定有限字母表书写的程序只是有限字符串,合法程序集合至多可数。无限二进制序列则对应 ,由 Cantor 定理不可枚举。这里各长度的顺序已明确,无需逐项任意选择。
例题 2.1.8
(实数与幂集等势)
映射 将 单射到 :有理数稠密保证不同实数的下割不同。固定有理数枚举后,其幂集与 等势。反向把 送到
若两集合首次在 不同,该项差的绝对值为 ,后续项总差至多 ,所以值不同。Cantor–Schröder–Bernstein 定理给出 。这个构造避开而非忽视小数表示不唯一的问题。
例题 2.1.9
(区间与整条直线等势)
映射 是双射 。它在 上从 递增趋于 ,在 上从 递增趋于 ,逆映射是 :事实上 ,所以 。每个满足 的开区间 都可经仿射映射与 双射。因此每个非空开区间都与 等势。
闭区间还需要再走一步,因为不存在连续双射 。沿一个指定序列移位就足够了。定义 为
记 、,以及当 时 ;这个映射把每个 送到 ,即把序列向后移两位,映到 ,其他点全部固定。所以 是双射。这与下文 Dedekind 无限例子中的移位是同一手法,只是用在一个明确给出的序列上。另一种做法是:包含关系 与单射 (从 到 )经 Cantor–Schröder–Bernstein 定理给出同一结论,只是没有把双射写出来。
例题 2.1.10
(平面、序列与整数序列都具有连续统大小)
用 表示上文证明中的配对双射。由此得到三个双射。
- 。把由 的子集组成的序列 送到 。逆映射把 送到第 项为 的序列。两个方向都由公式给出,不涉及选择。
- 。把 送到 ;偶数和奇数重新把两个坐标分开。
- 。映射 把 单射到 。反方向, 是单射,因为 是双射,而函数由其图像决定。Cantor–Schröder–Bernstein 定理完成论证。
现在固定一个双射 ,它的存在由上文关于实数的例题保证。逐坐标应用 ,就可转移前两个双射,所以 且 。一个平面,甚至全体实数序列,点数都不比一条直线多。这里只用了一个固定的双射,并非对每个坐标分别作选择。这种比较只涉及大小。双射 不可能连续,因为它在一个圆上的限制会是从圆到 的连续单射,而介值定理排除了这种情形。拓扑能区分这两个集合,基数却不能。
例题 2.1.11
(代数数与超越数)
整系数多项式是有限整数串,按长度和系数界可显式枚举。每个非零多项式只有有限多个复根;先按实部、相同实部再按虚部排列,可规范地枚举根,不必任意选择。因此代数复数至多可数。实数不可数,故存在超越实数;这个存在证明没有指出某个具体常数。
例题 2.1.12
(可数网格与有限记录)
配对函数给出 ,迭代该公式可枚举任意固定有限长度的自然数元组。长度可变的有限元组也能显式排列:以“长度加各项之和”为权重,按权重递增排列,同权重内按字典序。权重固定时长度和每项均有界,所以只有有限多个元组。空元组置于权重零。每个有限元组最终都会出现,这完全指定了枚举过程。
因此,由有限多个整数标签、自然数地址及有限控制符号组成的有限记录,只要各部分编码预先固定,就至多可数。这解释了有限证明、程序及数学表达式为何可编码为自然数;它没有把无限记录或任意实参数也变成可数。把有限有理系数串换成无限二进制序列,会改变可用数据的基数。
例题 2.1.13
(Dedekind 无限性揭示隐藏假设)
集合若与自身的一个真子集双射,称为 Dedekind 无限。在 ZF 中,这等价于包含可数无限子集。若 是不同元素,把 移到 ,其余点固定,就给出 到 的双射。
反过来,若单射 遗漏 ,令 。若 且 ,逐次用单射性消去 ,便有 ,把 放回 的像,矛盾。因此这些值互异,形成可数无限子集。这里只固定一个点,其他点均由迭代唯一确定,没有同时任意选择。
有限鸽巢原理排除有限集合具有此性质。在 AC 下,无限集合可以良序,再每次取最小剩余元素,便得到所需序列;若有限步就取尽,原集合本来就有限。但 ZF 中“无限”的定义只是与任何有限序数都不等势,不能默默换成“含可数无限子集”。熟悉的 Hilbert 旅馆移位需要的是已给出的无重复序列。序列一旦有了,移位完全正确;需要辨别的是该序列的存在性是否已获保证。这个例子也说明,某个明确的组合构造可以不使用选择,而在所有无限集合上统一断言该构造的输入可用,却可能涉及更强公理。
反例模式
等势不保持原来的次序
一个貌似合理的错误推论是:两个有序集合等势,就有相同序型。把最后一点 送到 、把每个有限 送到 的双射 已反驳它。前者有最大元素,后者没有;序同构必保持“最大”这个性质,所以任何双射在这里都不可能是序同构。
正确修复要说明映射必须保持什么。比较基数只要求单射和满射,不要求次序;比较序型则要保持前驱关系。同一个底集可以赋予不同次序,同一个可数基数也容纳这两个不同序型。配对函数把无限网格排成一列也是如此:它无需保存平面位置,也无需保存原先指定的字典序,所证明的只是每个点恰出现一次。
因此读到“相同”“可编码”或“同构”时,必须问保留的是哪些结构。字符串编码为自然数只是集合间的有效对应,不会把字符串的前缀关系变成自然数的通常大小关系。忘记保留条件,往往会把一个正确的可数性证明误用为错误的序数结论。
常见错误
常见错误
(单向单射不是双射)
只有一个方向的单射不足以证明双射: 单射到 ,反方向的比较却不可能。
常见错误
(反转满射可能需要选择)
ZF 中满射也不自动给出反向单射,因为从每个纤维选一个点可能需要选择。以首次出现选取元素能成功,是因为 有指定良序。
常见错误
(对角化需要指明列表)
对角化必须指明假定的列表,再构造不在列表中的对象。“无限太大”不是矛盾。
的序数值不同于 ,但基数仍可相同。
总结
相互单射通过明确分区给出双射。幂集经对角化严格增大。可数性依靠可用的枚举;任意同时选择则是选择一章单独研究的原则。
练习
快速检查
(显式枚举 的全部有限子集,并说明任意子集为何更多。)
解答 · 答案
是有限子集到 的双射,空集对应零;二进制表示唯一。全部子集构成的 则由 Cantor 定理不可数。两类子集不能混淆。
快速检查
(证明 ,其中后者表示所有函数 组成的集合。)
解答 · 答案
取 ,其中恰在 上取值 ;逆映射为 。两个复合都是恒等,因此不经选择便得到双射。
快速检查
(由 证明 。Cantor 定理是否推出 总给出 ?)
解答 · 答案
设 单射,则 单射,因为像相等时可用 的单射性恢复元素。严格性并不由 Cantor 推出;该定理比较集合与自身幂集。此证明没有严格比较两个不同无限集合的幂集大小;那需要另外的论证或附加假设。
快速检查
(不用选择公理证明 的每个无限子集可数无限。)
解答 · 答案
取 ,。无限性保证每步剩余非空。序列严格递增;若遗漏 ,最小剩余规则不允许越过 ,而有限集合 又不能容纳无限多个不同前项,矛盾。因此它双射到 ;每步值都唯一。
快速检查
(用不动点给出 Cantor–Schröder–Bernstein 定理的第二个证明。对单射 与 ,对 令 。证明 有不动点 ,并且 给出一个双射。)
解答 · 答案
若 ,则 ,所以 ,从而 。令 ,它包含 ;再令 。对每个 都有 ,故 ;因此 。再由单调性得 ,所以 ,即 。于是 。这就是 上单调映射的 Knaster–Tarski 不动点论证。
不动点等式说明 。在 上令 ,在 上令 。第一支把 双射到 ;由于 是单射,第二支把 双射到 。这两个像分划 ,所以 是双射。由于 是单射,,而这样得到的最小不动点正是链证明中的集合 。两个证明构造的是同一个双射。
快速检查
(利用 Cantor 定理及大小比较的基本法则,再证明一次不存在由所有集合组成的集合。)
解答 · 答案
假设 是包含每个集合的集合。 的每个子集都是集合,所以 ,从而 。由于 非空(它包含 ),基本法则第 3 项给出满射 ,这是 Cantor 定理所禁止的。事实上每个集合都是 的子集,所以由包含映射构造出的满射就是恒等映射,其对角集合正是 Russell 集合 。
快速检查
(证明由连续函数 组成的集合 满足 ,尽管所有函数 组成的集合严格大于 。)
解答 · 答案
常值函数给出 。反方向,把 送到其限制 。这是单射:给定 ,有理数 组成一个指定的、收敛到 的序列,所以由连续性得 ;两个在 上相同的连续函数处处相同。固定 的一个枚举,就把 等同于 ,而由序列的例题,。因此 ,Cantor–Schröder–Bernstein 定理给出 。所有函数 包含所有函数 ;后者与 等势,由 Cantor 定理及基本法则第 4 项,它严格大于 。
快速检查
(证明所有双射 组成的集合与 等势。)
解答 · 答案
双射 组成 的子集;由例题, 与 等势,所以这些双射单射到 。反过来,对 ,令 对每个 交换 与 ,并固定其他所有数。每个 都是自身的逆,因此是双射。若 ,则 而 ,所以 是单射。Cantor–Schröder–Bernstein 定理完成证明。特别地,可数集合有不可数多个置换。