动机
数一个集合有多少个元素,结果不应取决于先数哪一个。这句熟悉的话其实包含一个定理:两个不同的自然数之间不可能有双射。同一个证明还会说明,为什么有限集到自身的单射必定是满射,以及集合变成无限集后,论证在哪里不再适用。
本节在 ZF 中工作,使用已经构造的自然数及其算术。这里 表示有限序数 ,因此 。需要可数选择时会明确说明。本节补足基数章节的初等论证依赖。
计数与抽屉原理
定义 2.3.1
(有限集与无限集)
若某个 与集合 之间存在双射 ,就称 为有限集。若不存在这样的自然数,就称 为无限集。此时我们尚未证明这个 唯一。有限序数自带特定的顺序;一个任意给定的有限集则未必附有顺序或首选的枚举。
定理 2.3.2
(有限抽屉原理)
对每个自然数 ,都不存在单射 。更一般地,若存在单射 ,则必有 。
证明
(以交换作归纳)
对 归纳。非空集 到空集 连函数都不存在。归纳步骤中,假定不存在单射 ,却存在单射 。令 。在目标集合 上,定义置换 :交换 与 ,其余元素不动;若 ,则取恒等置换。于是 仍是单射,且 。
由于单射性,其他输入都不能映到 。把 限制在输入 上,就得到单射 ,与归纳假设矛盾。第一项结论得证。若 ,把任何假定的单射 限制在前 个输入上,又会违反第一项结论。
证明中的交换不是多余步骤:它把一个已占用的目标位置移到最后,使我们删去最后一个输入时,也能删去最后一个目标位置。随意各删一个输入与目标,并不能保证剩下的映射具有所需的陪域。
如果 和 都是双射,用其中一个的逆与另一个复合,就得到 与 之间的双射。定理给出 和 ,所以 。现在才能无歧义地写有限集的基数 。特别地,空集的基数是零,而非空集的基数不可能是零。
子集、像与有限集的自身映射
先证明一条不会循环使用待证结论的封闭性质:有限集的每个子集都是有限集。只需考虑 ,并对 归纳。 时只有空子集。对 ,令 ;由归纳假设, 有限。若 ,则 。若 ,取双射 ,再把新输入 映到 ,就把它延伸成双射 。对任意有限的母集,沿着它的一个枚举把结论转移过去即可。
基数为 的集合,其真子集的基数严格小于 。为证明严格性,设 ,取 。此时 ;交换 与 后再限制,得到双射 。因此 单射到 。 已知有限,抽屉原理便给出 。 时根本没有真子集。
有限集的像也有限。给定 ,对每个 取它在 中的最小原像。这些最小原像组成子集 ,而 是双射。由子集的结论,像是有限集。最小原像由现成的有限顺序唯一指定,不需要选择公理。
定理 2.3.3
(有限集的自身映射:单射当且仅当满射)
若 有限且 ,则 为单射当且仅当它为满射。
证明
(两个方向都化为抽屉原理)
用一个枚举及其逆把问题转成 。若 单射却遗漏了某个元素,其像便是真子集,基数为某个 。再把像双射到 ,就得到单射 ,与抽屉原理矛盾。
反之,设 满射。令 包含每个目标的最小原像,则 双射到 。若 不单射,某个纤维中至少有两个不同的输入,只有最小的那个属于 ,故 是真子集。它的基数便小于 ,与存在双射 矛盾。这也包括 :空的自身映射既单射又满射。
例题 2.3.4
(无限集上的两个反例)
位移 定义为 ,它是单射,却遗漏零。另一方面,令 ,并令 。这个映射满射,因为每个 都是 ;它却不单射,因为 。有限定理的两个方向分别由两个不同的映射推翻了。单射与满射的定义并没有改变。
哪些构造保持有限性
设 、,固定枚举 和 。在一个证明中取两个存在性见证是有限的逻辑操作,不是使用选择公理。
带标记的不交并 与 双射:前 个位置用于第一种标记,其后 个位置用于第二种标记。忘掉标记就得到从这个有限集到 的满射,所以普通并集有限,基数至多为 。如果 与 有交叠,等号未必成立。
积 的基数是 。若某个因子为空,结论直接成立。否则,以编号 枚举 ,其中 。带余除法为每个小于 的编号给出唯一的逆像。再与 复合,就得到所需双射。归纳可知,由有限集作指标的一族有限集,其并与积仍有限。初始情况分别是空并集与空积:前者为空集,后者只有空函数这一个元素。这里的归纳证明每个有限枚举族的存在,并没有选出一个无限的枚举族。
的幂集基数为 。从 开始,它有 个元素。若 ,则 的每个子集恰有一种形式:或者是 ,或者是 ,其中 。两种形式互不混淆,所以新幂集与 双射。归纳给出 。
概念视角组合
把子集看成二元记录
子集 与它的示性函数 携带相同的信息;这里 当且仅当 。映射 是从 到全体函数 的双射,其逆映射为 。通过一个枚举 ,这样的函数就是 个二元位置的记录。加入一个新元素就多出一个位置,这正是上面归纳中的因子 。
例题 2.3.5
(交叠会改变计数)
取 、。带标记的不交并有五个元素,普通并集 却只有四个。积有六个元素,其中 与 是不同的有序对。 的幂集为 、、、,共有四个元素。这些构造虽然从同样的两个有限集开始,得到的对象并不相同。
例题 2.3.6
(每条记录有限,不表示所有记录组成有限集)
每个函数 的图都恰有三个有序对,因为 是到该图的双射。然而所有这些函数组成的集合是无限集:对每个 ,常值函数 都给出不同的函数。有限的定义域使每条记录有限;要使全部可能记录组成有限集,还需要每个位置只有有限种取值,并且位置数也有限。
从无限的像中去除重复
给定一个无限集,与给定一个访问其中无限多个元素的序列,是两种不同的信息。不过,一旦序列已经给定,就可以不用选择公理去掉重复。
定理 2.3.7
(无限的像包含一个由序列确定的可数子集)
若 的像是无限集,就能仅由 定义一个单射 。
证明
(保留每个值的首次出现)
只保留每个值首次出现的位置。准确地说,由分离公理得到
像中的每个元素都有最小的出现下标,因此 是 到该像的双射。若 有限,由有限像结论可知 的像也有限,矛盾。因此 是 的无限子集。
的每个无限子集都无上界,否则它会落在某个有限序数内。定义 ,并递归定义 。无上界保证每次取最小值的集合都非空。各步的值唯一确定,普通递归与替换公理便构成完整函数 。最后令 。这些下标严格递增且属于 ,所以对应的值两两不同。
证明透视
取最小值已经指定了规则
证明中取了无限多次最小值,但并未调用一个保证任意同时选择存在的公理。每一步中, 已有的顺序都指定了唯一的下一个下标;递归作用于这个单值规则。这就说明,一个像无限的序列为何提供了比“母集无限”更多的信息:它提供了有序的位置,使首次出现规则能够实际运作。
若 ,首次出现的位置是 ,构造得到 。
反例模式
无限多个位置不足以给出单射
声称:首次出现构造能把每个序列 变成单射 。取 ,当 为偶数时 ,为奇数时 。下标 是首次出现;下标 也是,因为 。每个 都重复了值 。因此
递归在第三步就停止。任何其他构造也不会成功:单射 限制到 上,就是单射 ,与抽屉原理矛盾。修正后的命题正是定理本身:像无限使 无限,从而无上界,所以每次取最小值的集合都非空。
可数选择准确用在哪里
定义 2.3.8
(可数选择)
可数选择 断言:每个非空集序列 都有函数,从每个 中选出一个元素。这些 自身不必有限,也不必可数。
在 ZF 中,已经可以证明:若 无限,则对每个有限的 都存在单射 。从空函数开始;一个有限像的单射不能穷尽 ,否则 就有限。因此可以取一个不在该像中的元素,把有限单射延长一格。归纳给出每个 对应的独立存在性结论。
这项归纳并没有产生一个相容选择的无限序列。命题 本身也不是一个已经给定的函数,不能直接为每个 指定合适的 。
定理 2.3.9
(可数选择给出无限集的可数子集)
在 ZF 加上 后,每个无限集都包含一个可数无限子集。
证明
(选取元组,而非相容的序列)
对每个 ,令 为所有单射 组成的集合。函数集已经是集合, 是其子集;前面的有限归纳证明了 。替换公理构成由定义唯一确定的序列 。可数选择再从每个 中选出一个 。
这些元组 不必彼此延长。令 。它是集合,而且无限:若 ,单射 就违反抽屉原理。为构造满射到 的序列,固定 ,定义
这是 到 的满射。使用一个固定的配对双射 ,就得到一个像为 的序列。前一定理去掉重复后,给出单射 ;其像就是所需的可数无限子集。
证明透视
为什么互不相容的元组仍给出无限集
选出的元组可以处处不一致: 未必延伸 。证明只需要它们的像合起来不是有限集;一旦假设大小为 ,抽屉原理仅凭一个成员 就给出矛盾。填充值 使 在整个 上有定义,而不必再作第二次选取;它存在,因为 有一个输入。其余步骤的次序是被迫的:去除重复需要一个序列,所以先通过固定的配对把并集枚举出来,然后首次出现定理才给出单射。
只有选出整个族 的那一步使用了可数选择。我们没有假定依赖选择、 的良序,或元组间的相容性。无限像的论证解释了为何不需要相容性。
前面的基数笔记已在 ZF 中证明:存在单射 ,等价于 与自己的某个真子集双射;后者称为 Dedekind 无限性。因此本节证明,在 下,每个无限集都是 Dedekind 无限集。我们证明的是这个蕴含,并没有证明它与 等价,也没有构造无选择公理的反模型。只在 ZF 中论证时,不可未经说明就把“无限”替换成“Dedekind 无限”。
常见错误
常见错误
(有限归纳不会收集无限多个见证)
有限归纳可以处理每次固定的有限次存在性选择,却不会自动收集无限多个见证。另一方面,无限递归也不一定需要选择:上面的最小下标构造在每一步都已指定唯一输出。
常见错误
(无限集到自身的单射不必满射)
映入无限集的单射不必满射,即使定义域就是同一个集合。有限自身映射定理依赖有限抽屉原理。
常见错误
(每个成员有限,不等于已有枚举)
知道一族集合中每个成员有限,不等于已经同时得到它们的枚举。后面的练习会说明一种足以完成这项额外任务的选择原则。
练习
快速检查
(对自然数 ,准确刻画何时存在单射 、何时存在满射 。包括定义域或陪域为空的情况。)
解答
单射存在当且仅当 :包含映射给出充分性,抽屉原理给出必要性。满射存在当且仅当 ,或 。后一种情况中,把 映到自己,其余输入映到零。必要性可由每个目标的最小原像构成的单射 得到。若 ,连函数都不存在;若 ,空函数不是满射。
快速检查
(证明有限集不可能与自己的真子集双射。指出位移 在哪里避开了你的论证。)
解答
若 且 ,由真子集结论知 。双射 便与有限基数唯一性或抽屉原理矛盾。取 时,真子集 并没有落在某个有限序数内,因此证明有限基数严格不等式的归纳不适用。
快速检查
(令 。求首次出现集合 及无限像定理构造出的单射。说明为何不能把该定理用于常值序列。)
解答 · 答案
每个值 首次出现于 ,所以 、,且 。常值序列只有一个值,;零之后没有下一个首次出现下标。保证这些后继下标存在的假设已经缺失。
快速检查
(在 ZF 中证明: 无限,当且仅当对每个 都存在单射 。说明这个命题为何还不是单射 的构造。)
解答 · 答案
若 无限,就按正文的方法一次延长一个有限单射;归纳证明每种有限长度的单射存在。反之,若 与 双射,把单射 与该双射的逆复合,就违反抽屉原理。独立见证未必相容,也尚未被选成一个族。量词 不是已经给定的关于 的函数。
快速检查
(假设 ,证明一个有限集序列的并至多可数。不得预先假定枚举已经同时给定,并处理空并集的情况。)
解答
对每个 ,令 是 唯一的有限基数。唯一性与替换公理给出函数 。令 为双射 的集合,它非空;当 时,其中有空双射。可数选择同时选出 。设 。若 为空,空函数就是它到 的单射。否则固定一个 :当 时把 映到 ,其余情况映到 。这给出 到 的满射。配对得到满射到 的序列,再把每个值映到其最小出现下标,就得到单射 。最后一步对有限或无限的 都成立。
快速检查
(若 不与自己的任何真子集双射,就称它 Dedekind 有限。利用前面的 Dedekind 等价刻画与本节的无限像定理,证明每个函数 都只有有限的像。再证明逆命题。)
解答 · 答案
若某个 有无限的像,由定理便有单射 ,再由前面的等价刻画, 是 Dedekind 无限集,矛盾。因此所有这类像都有限。反之,若 是 Dedekind 无限集,同一等价刻画给出单射 ,其像由抽屉原理不可能有限。 时不存在函数 ;关于所有像都有限的条件自然为空真,正合所需。