请先读单射、初始序数、选择公理及共尾性。良序集合的平方定理可在 ZF 中证明;把它用于任意无限集合则使用选择公理。后续不加限制的基数比较均在 ZFC 中进行。
动机
配对函数说明两个自然数坐标仍只有可数多种可能。对每个无限基数都成立的对应结论却没有那么直接:若天真地把不可数平方逐行排列,初始段可能过大。正确次序先处理最大坐标较小的对,使每个较早的部分都受一个更小的平方控制。
加法和乘法随后大幅简化,指数却不能同样压缩。Cantor 对角法已给出 。König 对角法分析另一障碍:即使候选列表分成许多部分,只要每个对应坐标比那部分更大,乘积中仍有元素能避开整个列表。这会说明连续统不可能有可数共尾性,却不会决定连续统的基数。
定义
定义 2.4.1
(基数的和、积与幂)
集合 的基数加法是带标签不交并的大小,乘法是笛卡尔积(Cartesian product)的大小,指数是函数集的大小:
双射说明这些定义不依赖代表集合。对集合族, 指 的大小, 指相应选择函数集的大小。选择公理使每个集合都以某个初始序数作为基数,因此这些量能够比较。没有选择公理时,一般集合未必可良序。
以 记二元集合,特征函数给出 。基数 的后继基数 是严格较大的最小基数,不是序数后继 。无限基数 的 是映入序数 的共尾映射所需的最小基数长度,定义见前章。
定理/命题
定理 2.4.2
(无限平方定理)
在 ZF 中,每个无限良序基数 都满足 。因此在 ZFC 中,每个无限集合都与自身的笛卡尔平方等势。若非零良序基数 至少一个无限,则
定理 2.4.3
(König 不等式)
在 ZFC 中,若每个 都有基数 ,则
比较的是整个不交和与整个乘积,而非两个相应的和。
定理 2.4.4
(幂集的共尾性不能太小)
在 ZFC 中,对每个无限基数 ,
特别地,。这限制共尾性,并未证明连续统假设。
证明思路
证明
(以最大坐标优先排列平方)
先说明无限初始序数是极限序数。无限序数 与 等势:把新增的最后一点送到零,将每个自然数 送到 ,其余点保持不动。因此无限后继序数不能是其基数的最早代表。
反设平方定理失败,取最小的反例无限基数 。将 按 优先、再按 、最后按 比较。任意非空子集依次最小化这三个序数坐标,便得到最小对,所以这确为良序。最大坐标为 的对之前的所有对,都落在 中。由于 ,令 。若 有限,平方仍有限;若无限,由反例最小性有 。故该良序的每个真初始段基数都小于 。
设它的序型为 。若 ,序型为 的初始段就有基数 ,矛盾。因此 ,给出平方到 的单射;反向有 。Cantor–Schröder–Bernstein 定理给出等势,反例不存在。整个论证只处理已良序的集合,没有暗中把任意集合良序化。
令 。乘积单射到 ,而两因子非空使较大的因子也单射到乘积。不交和单射到 ,又包含较大加数的一份副本,故两个公式均成立。
无限良序字母表大小为 时,全部有限字符串也有大小 。归纳得每个正有限次幂大小为 。固定一个配对双射,反复使用它,就能为所有长度统一编码;再以 标记长度,应用 。空字符串仅增加一点。长度标签不可省略,否则不同长度的字符串可能得到相同编码。
证明
(König 对角线论证)
对 König,直接取初始序数为各坐标集合。假设存在满射
对每个 ,集合 的基数至多为 ,因而漏掉 中某点。取最小的漏值 。函数 与每个 至少在第 坐标不同,所以不在值域内,矛盾。在 ZFC 的基数可比性下,不存在满射便推出所述严格不等式。若 空,和为零,乘积为单点集,不等式仍成立。
证明透视
对列表的一整个部分作对角化
Cantor 证明给每个列出的函数指定一个禁用坐标。这里许多输入共用坐标 ,但只有 个输入,少于可用的 个值。因此能选一个避开整部分的坐标值。不交和的标签告诉我们用哪一坐标击败输入,并未假设已经枚举整个乘积。
应用不等式前,先把指数律理解成函数的重排。不交并上的函数恰好对应一对函数;以函数为值的函数恰好对应两个变量的函数。因此
这是基数公式,不是对序数指数作同样断言。
证明
(短共尾族与 König 不等式矛盾)
令 ,反设 。取共尾族 ,,令 。这些基数的不交和恰好为 。上界方面,选定代表双射后,不交和单射到 ,后者大小为 。下界方面,由 是极限序数且该族共尾,每个 都严格小于某个 ;用最小的这种指标,并利用代表双射,把 编入带标签的和,得到从 出发的单射。
每个 。现在 König 与指数律给出
矛盾。 的比较,是将 单射入 ,并在新增自变量处补零。这里先证明了平方定理与函数重排,再用它们完成推导。
证明透视
使幂集与众不同的那条恒等式
论证分两半。共尾性至多 ,就能把 写成 个较小基数之和;König 不等式使这个和严格小于 个因子之积,而每个因子至多 。矛盾最终只依靠一条恒等式 ,它成立是因为 且 。若取 、,前一半仍然成立,却只得到 ,并无矛盾,正符合 。选择公理通过代表双射和基数可比较性进入论证。
例题
例题 2.4.5
(可数序数的对)
的基数为 。这不表示序数乘法 等于 :前者在第一整块后还有第二块。基数运算忘掉次序,只问是否存在双射。优先最大坐标的良序控制前面的对,并未声称同一集合的各种良序有相同序型。
例题 2.4.6
(有限描述与无限串流)
可数无限字母表上的有限字符串全体可数,但二进无限串流的基数为 。因此有限程序可数,并不表示全部无限输出或实数都可计算。可变的有限长度对应可数并;无限长度对应函数集。混淆两者便丢失了对角障碍。
例题 2.4.7
(可数并需要统一选取编码)
在 ZFC 中,若每个 可数,可同时选单射 。对并集中的元素,取它所属的最小指标 ,再送到 ,便把并集单射到 ,故并集可数。在 ZF 中,逐个知道单射存在,并不自动提供整族单射。若这些单射本已作为数据给定,同一个证明无需新的选择。区别在编码族的选取,而不在最后的配对公式。
例题 2.4.8
(连续统不能取的一个值)
前面的序数章证明了 ,故新定理在 ZFC 中排除 。它不决定 是否成立,也不决定所有尚未被此必要条件排除的值。这里没有使用力迫或相容性定理。
常见错误
常见错误
(无限基数不能消去)
无限基数能吸收自身的另一副本,因此消去律与减法不能照搬有限算术。从大小为 的集合中删去同样大小的子集,可能剩空集、一个点,或仍有 个点。只知道两个大小,不能决定余集。
常见错误
(对所有集合的平方定理要用选择公理)
ZF 中的平方证明针对可良序集合。推广至所有无限集合使用良序原理,也就是选择公理。可数并论证也应说明整族枚举从何而来。
反例模式
König 需要每个坐标都严格
声称:若每个 都有 ,则 。取 ,并令 。和是集合 的大小,即 。乘积是 上取值都属于 的函数全体,唯一的元素是 。因此
连非严格不等式也不成立。在证明中,集合 此时就是整个 ,不存在最小的遗漏值 。修正后的假设正是定理所述:每一个坐标都有 。
基数指数计算函数,序数指数描述超限次序构造;符号相近,运算并不相同。
总结
优先最大坐标的次序,在无选择情况下证明良序无限基数的平方定理,由此得到非零和积的最大值规则与有限字符串编码。函数重排给出指数律,König 的逐坐标对角法给出严格障碍。把它应用于假想的短共尾族,就得到 ,但不解决连续统假设。
练习
快速检查
(对无限良序基数 ,证明 ,写出双向比较并指出平方定理的作用。)
解答 · 答案
由 得 。又由 得 。中间一步重排两个自变量,最后一步用平方定理。再由 Cantor–Schröder–Bernstein 得等号。
快速检查
(在 ZFC 中,设 无限,每个非空 的大小至多为无限基数 。证明 ,并说明何时必有等号。)
解答 · 答案
选择公理同时选出单射 ,并良序化 。每个并集元素选最小所属指标,再送到 ,所以并集单射到 ,大小不超过所述最大值。若并集含有该最大大小的子集,便有等号;否则未必,例如所有非空 可以都是同一个单点集,即使指标集很大。在 ZFC 中,两两不交且非空的成员迫使并集大小至少为 ,而一个大小为 的成员迫使另一相应下界。
快速检查
(直接用 König 证明 。计算左侧,并以 给右侧上界。)
解答 · 答案
每个 ,故 König 可用。令 。和不超过 ,又不小于每个 ,因此不小于其上确界 。故 ;上界把每个乘积元素视为取值于 的函数。这给出奇异基数处的严格指数界,没有计算该指数的确切值。
快速检查
(说明大小为 的集合,不能由一个递增可数族并成,而各成员基数都严格小于 。不要预设统一大小上界。)
解答 · 答案
令 ,设并集大小为 ,但 。若 ,可取一个无限基数 统一控制所有大小,于是并集大小至多为 ,矛盾。因此 ,给出序数 的可数共尾族,与 冲突。有限上界情形可扩大为 。事实上不需要递增性。
快速检查
(构造 与 间的双射,推出 。解释为何这不提供一般公式 。)
解答 · 答案
将 送到 ;逆映射取这些带标签截面的并。二者互逆,空定义域也适用。基数 表示额外不交的一点,拆分指数的定义域给出 。若 无限,这个乘积与基数和 碰巧都等于 ,但理由是无限运算,而不是指数一般地对加法分配。有限例 已有 。