动机
而 ,说明无限序保留了基数所遗忘的信息。乘方把位置组织成更大的块;Cantor 正规形把每个非零序数写成有限个递减的 幂之和,并带有正的有限系数。
这里的“有限”需要解释:项数有限,指数自身却可能是很大的序数。继续展开每个指数,未必得到只用自然数写出的有限表达式。共尾数研究另一件事:从下方趋近一个序数,需要多少个位置?很大的序数也可能有很短的共尾序列。只有把序数算术、集合大小与共尾数分开,这些现象才不会显得矛盾。
定义
定义 3.2.1
(序数幂)
对正序数 ,沿指数递归定义
其中最后一式适用于非零极限。正规形定理使用底数 。加法与乘法均为序数运算,因此 是依次排列 个 ;系数写在右边。
定义 3.2.2
(Cantor 正规形)
Cantor 正规形是
其中 为正的有限数,各 为正自然数。零用空和表示。
定义 3.2.3
(共尾子集与共尾数)
若 ,且每个 都不大于某个 的成员,则称 共尾于 。定义共尾数 为使某个函数 的值域共尾的最小初始序数 。由于 可良序,这样的初始序数存在。规定 ;后继序数有最大前驱,故共尾数为一。非零极限没有有限共尾子集,所以其共尾数无限。
定义 3.2.4
(正则基数与奇异基数)
无限初始序数 若满足 ,称为正则基数,否则称为奇异基数。这两个形容词针对基数;不能仅因为某个普通序数的共尾数比其序型小,就把它叫作奇异基数。除非另作说明,本节不假设选择公理。
以下使用由有序拼接直接得到的基本算术性质:加法结合,对第一变元单调不减,对第二变元严格递增且在非零极限连续。三块拼接改变括号而不改变位置,便给出结合律。有限倍数满足 ,并有 。
定理/命题
定理 3.2.5
( 的幂与加法不可分解性)
函数 严格递增,在非零极限连续,并满足 。对任意 ,若 ,则 。当 时,还得到
定理 3.2.6
(Cantor 正规形的存在唯一性)
每个非零序数恰有一个 Cantor 正规形。构造反复取出最大 幂、唯一正有限系数及更小余项。若过程不在有限步结束,就产生指数的无限严格下降序列,所以它必终止。
概念视角算法
通过正规形比较序数
正规形也提供比较序数的程序。比较两个非零序数时,先比较领先指数;若相同,再比较领先系数;若两者都相同,就用同样方法比较余项。这是正确的,因为领先指数 与系数 把序数放在从 起、不含 的区间内;领先项相同时,加法对第二项严格递增,把比较转移到余项。因此 ,尽管左边的项更多。
定理 3.2.7
(共尾数本身是正则基数)
对每个非零极限序数 , 有严格递增共尾映射 ,并满足 。这些结论在 ZF 中成立,但没有断言每个序数或每个无限基数都正则。
证明思路
证明
(递增、连续与加法不可分解)
后继幂严格增加,因为正序数后面再排一个自身副本就更大,而 至少包含两个副本。在极限处,每个较早幂之后还有更大的幂出现在上确界中。超限归纳遂给出 :后继至少增加一,极限则支配所有较早指标。
对 归纳证明加法不可分解性。零指数时,唯一小于一的序数是零。若 ,令 。由于 ,可取正有限 使 、,于是
极限时,把两序数同时界在一个更早的幂之下,应用归纳假设。当 , 是极限;加法对第二变元的连续性及刚证明的界给出 。另一方向由第一变元的单调性及 得到。这就是吸收公式。
右边加数是 的幂这一假设,不能减弱为它是极限序数。
反例模式
极限序数不一定吸收较小加数
断言:若 是非零极限序数且 ,则 。取 、。有限倍数的左分配律给出 ,而 ,所以吸收失败。对加法封闭也失败:,但 并不小于 。定理只适用于 ;这里 严格介于 与 之间,不是这样的幂。
证明
(用首项幂作除法)
固定 。存在最小 使 ,因为 给出集合大小的搜索界。这个 不是零,也不是极限:若为极限,此前各幂都至多为 ,其上确界也至多为 。所以 ,且
令 ,取第一个严格大于 的有限倍数,就得到唯一正有限 满足 。初始段 之后的良序尾部有唯一序型 ,从而 。加法对第二变元严格递增,保证余项唯一;又必有 ,否则下一个有限倍数已不大于 。
若余项非零,就继续同一构造。余项小于先前的领先幂,因此新指数严格变小。若永不终止,普通递归会给出真正的无限下降序列;其值域的最小成员又有更小的下一项,矛盾。因此展开只有有限项。
任意候选正规形的领先项之后,尾部都小于其领先幂。每个较低指数的有限倍数都小于该幂,而加法不可分解性保证有限个这样的项之和仍较小。所以整个形式准确落在相邻幂之间,再准确落在相邻有限倍数之间。领先指数、系数及余项因此与上述构造相同。对有限尾部继续比较,便得唯一性。
证明透视
终止证明排除的是哪条序列
证明中的下降序列,是各次余项的领先指数,不是不断展开某一项内部的指数。后一过程可在不动点回到同一序数,如 例子所示。前一过程则在每个未结束步骤严格下降,因为新余项小于先前幂。各值已由除法论证唯一指定,所以若过程不停,普通递归便给出整条序列,没有暗中作依赖选择。这才是最小元论证所排除的具体无限下降。
证明
(最小长度的递增共尾映射)
对共尾数,固定见证最小初始序数的共尾映射 。 为极限,所以 无限。无限初始序数必为极限序数:无限后继序数可通过移动最初 个位置并把额外点放到起点,与其前驱建立双射。每个 的基数小于 ,因此由这些指标取得的值不可能已经共尾,否则更小基数就成为见证。
递归定义
较早值域的基数小于 ,故在 中有界;由于 是极限,显示的后继上确界仍小于 。构造于是始终留在目标内,严格递增,并因支配 而共尾。若某个更小基数 有共尾映射 ,则递增性保证 共尾于 ,违背 的最小性。恒等映射本来就共尾于 ,故 。没有一步为任意集合族同时挑选枚举。
证明透视
共尾数的最小性如何用了两次
递归取给定值 与一个严格越过所有较早值的累进界两者中的较大者。 的最小性用了两次。第一,每个较早值域都由某个基数较小的 编号,所以在 中有界;又因 是极限,累进界仍留在 内。第二,若有更短的共尾映射进入 ,与递增的 复合就得到进入 的更短共尾映射。支配 提供共尾性;加上的后继则提供严格递增。
例题
例题 3.2.8
(相加会删除较低的尾部)
令 、。吸收公式给出
第一式中,右边的 开始时吞掉 ,但不吞掉较大的 。第二式中整个左加数小于 ,所以都被吞掉。正规形显示运算次序,并没有把加法变成逐项系数相加。
下面的互动图让你输入两个小于 的 Cantor 正规形序数,按任一次序相加或相乘,并看到哪些较低的项被吞掉,以及运算对象的次序是否影响结果。
正规形显示序数加法吞掉哪些较低的项
把两个小于 ω^ω 的序数写成 Cantor 正规形,选择运算,逐项阅读结果:被吞掉的项会加上删除线,保留的项照旧,并比较两种运算次序。
每个运算元有四个项位置。不用的位置会被忽略;计算前先合并相同指数,并把指数由大到小排列。
| 算式 | 正规形 |
|---|---|
| α | ω^4·2+ω^2·3+5 |
| β | ω^3+ω·2+7 |
α+β: ω^4·2+ω^2·3+5 + ω^3+ω·2+7 = ω^4·2+ω^3+ω·2+7
加上删除线的项已被吞掉,不会出现在结果中。
规则:由右加数的领先指数 e 决定一切。左边指数高于 e 的项保留,低于 e 的项消失,左边在 e 处的系数加到右边的领先系数上,然后接上右加数其余各项。
- 右加数的领先指数:e = 3。
- 左边高于 e 的项,保留:ω^4·2。
- 左边低于 e 的项,被吞掉:ω^2·3+5。
- 左加数在指数 3 处没有项,所以右边的领先系数 1 不变。
| 算式 | 正规形 | 被吞掉的项 |
|---|---|---|
| α+β | ω^4·2+ω^3+ω·2+7 | ω^2·3+5 |
| β+α | ω^4·2+ω^2·3+5 | ω^3+ω·2+7 |
序型图(每个 ω 块只画出前三个点)
只有当所有序数都具有 ω·a+n 的形式时才显示图。
- α
- ω^4·2+ω^2·3+5
- β
- ω^3+ω·2+7
- 原来次序: α+β
- ω^4·2+ω^3+ω·2+7
- 对调次序: β+α
- ω^4·2+ω^2·3+5
- 对这些运算元可交换
- 否
α+β = ω^4·2+ω^3+ω·2+7,但 β+α = ω^4·2+ω^2·3+5,而且 ω^4·2+ω^3+ω·2+7 > ω^4·2+ω^2·3+5:运算元的次序改变了结果,所以这个运算不可交换。
为何会出现吞掉
若 ξ < ω^γ 且 γ > 0,则 ξ + ω^γ = ω^γ:序型为 ξ 的一块放在 ω^γ 前面会被吞掉,因为 ω^γ 在加法下不可分解。
所以在 α+β 中,α 内低于 β 的领先幂 ω^e 的每一项都被吞掉,高于 ω^e 的项则不受影响;这就是 1+ω = ω 而 ω+1 > ω 的原因。
运算元的指数取 0 至 6,系数取 1 至 9,每个至多四项。乘积的指数可达 12。所有比较都是精确的:序数以整数对的列表表示,不使用小数。
例题 3.2.9
(序数幂与基数幂回答不同问题)
序数幂 ,因为有限幂在自然数中无界。基数记号 则计数全部二值函数,等价于全部自然数子集,由 Cantor 定理不可数。看似相同的乘方记号,一处是有序递归极限,另一处是函数集合的大小,必须先看所属的定义。
例题 3.2.10
(有限正规形可以含有不动点指数)
令 、,并取 。序列严格递增;连续性及该序列的共尾性给出
这是最小正不动点:若 且 ,则它界住 ,归纳界住每个 ,故界住 。通常记为 。其正规形仅一项 。因此“有限正规形”不保证反复展开指数后会得到只用自然数构成的有限表达式。显示的共尾序列还给出 。
例题 3.2.11
(带有指定共尾序列的奇异基数)
定义 , 为下一个初始序数,其存在由 Hartogs 保证,令 。此上确界仍是初始序数:任意较小序数都落在某个 之下,不可能与整个上确界等势。指定序列共尾,而有限集不可能共尾于极限,故 ,它是奇异基数。序列由唯一的序数规则指定,没有任意的同时选择。
常见错误
常见错误
(不合规范的正规形)
正规形系数在右,指数严格递减。留有零系数或相等的相邻指数,就没有写成规范形式。正规形也不让序数算术交换,更不表示基数决定序数。
常见错误
(共尾数不是单调的)
较大序数的共尾数未必更大: 的共尾数为 , 却为一。
常见错误
(共尾映射不必递增)
原共尾映射不必递增,定理在最小基数长度上构造递增版本。最后,在 ZF 中必须区分明确指定的序数列与为任意集合族逐项挑选枚举。
总结
的幂递增、连续且加法不可分解。反复取领先幂及余项给出唯一有限 Cantor 正规形。共尾数度量极限的另一面,它本身是正则基数,而原来的基数可能奇异。其他正则性论证中的选择假设仍须明确指出。
练习
快速检查
(两种次序的正规形相加)
计算 与 按两个次序相加的结果。
解答 · 答案
记两者为 ,则 ,因为 被吸收;,因为 。被吸收项的有限尾部不会在最后再次相加。
快速检查
(两个等于 的共尾数)
给出共尾映射,证明 、,并说明有限长度不够。
解答 · 答案
与 分别由乘法及乘方的极限定义给出共尾值域。两目标都是非零极限,有限值域有最大元而遗漏更大前驱,所以共尾数恰为 。
快速检查
(没有统一上界的终止)
为什么正规形构造总能停止,却没有适用于全部输入的固定有限项数界?给出项数任意多的例子。
解答 · 答案
不停止就会给出定义域为 的严格递减序数函数,违背最小元性质。但对每个有限 , 都有 项。逐个输入的终止证明不需要提供全部输入共用的有限界。
快速检查
(递增共尾序列)
为什么可用最小基数长度的递增共尾序列,而不改变 ?证明中的哪项构造提供该序列?
解答 · 答案
定义已给出某个从 出发的共尾映射,并排除更小基数。递归的运行上界 严格递增、留在 内且支配原映射,所以仍有同一个最小定义域基数。较早值域已经是已给序数指标集的像,不需要另为它选枚举。
快速检查
(奇异基数)
奇异为何不违背共尾数的正则性定理?
解答 · 答案
定理应用于 时,指出它的共尾数是正则基数 ,没有把 等同于 。两者的差距正是此处“奇异”的含义。指定的 aleph 序列使这两项结论同时成立。