动机
自然数归纳之所以成立,是因为非空反例集合有最小成员。同样的原理适用于任意良序,包括所有有限阶段之后的阶段。序数为这些位置提供标准表示:一个序数恰好包含所有更早的位置,成员关系本身就记录了次序。
无限过程不必以加上最后一步作结。极限阶段没有紧接在前的一步。定义过程必须说明极限处如何处理,通常是收集全部较早阶段。归纳用于证明命题,递归用于定义对象;两者关系密切,却不能互相替代。
定义
定义 3.1.1
(良序、初始段与传递集合)
集合 上的严格良序是反自反、传递的线性序,且每个非空子集都有最小元素。若 且 总推出 ,则 是初始段。集合 称为传递的,若 推出 ,等价地每个成员都是 的子集。
定义 3.1.2
(序数、后继与极限)
序数是被 良序排列的传递集合。记 为 。最初的序数是 、、、。后继为 。不是后继的非零序数称为极限序数。
概念视角结构
序数即由传递集合组成的传递集合
在基础公理下,序数恰好是所有成员都传递的传递集合。在这种集合中,由 及 传递得 ;基础公理给出反自反性与最小元。至于线性,取一个有不可比较配对的 -极小 ,再取这种配对中极小的 ;把各自的成员与对方比较,得到 且 ,于是 ,两者其实可比较。若没有基础公理,满足 的集合会符合条件,却不是序数。
无穷公理给出一个归纳集合 。在 内分离出属于每个归纳子集的元素,得到最小归纳集合 。它确实归纳;把任意归纳集合与 相交,又可证明它包含于任何归纳集合。其成员正是有限 von Neumann 序数。每个有限序数的后继仍在 内,所以 是极限序数。
定义 3.1.3
(序数集合的上确界)
序数集合 的上确界为 。它是序数,每个 的成员都包含于其中,而且它包含于任何序数上界。上确界未必属于 ,也未必严格大于每个成员。
定理/命题
定理 3.1.4
(序数的比较)
对序数 ,、、 恰有一个成立。并且 当且仅当 。序数的每个成员都是序数;每个良序集合与唯一序数序同构。
定理 3.1.5
(超限归纳)
设 为序数。若对每个 ,都有
则 对所有 成立。若 是公式且此条件对每个序数成立,也可对全体序数归纳。
定理 3.1.6
(集合长度的超限递归)
假设可定义规则 对每个以序数为定义域的集合函数指定唯一的集合值。对每个序数 ,存在唯一函数 ,定义域为 ,满足
唯一指定的下一值不需要选择公理;收集较早阶段则需要替换。
证明思路
证明
(初始段迫使可比较)
若 ,传递性给出 。若 ,这些位置都在 中,其成员序的传递性给出 。所以 传递,且限制的良序仍良序,故 是序数。序数的每个真初始段都恰好是最小遗漏元素 的前驱集,亦即 本身。
是两者的初始段。若在两者中都为真初始段,它等于两者的某个成员。记该集合为 ,就有 ,与严格良序矛盾。因此其中一个序数是另一个的初始段,比较定理及包含判据随即成立。严格良序没有循环,故三个可能互斥。序数的并是传递的;比较使其成员线性排列。非空子集的最小元可通过先取一个成员,再在其前驱中寻找最小候选得到。这也证明并集是序数及上确界。
证明透视
为什么一个交集就能决定比较
整个比较只依赖一个集合 。它是两个序数各自的初始段,而序数的真初始段就是它的某个成员。若它在两边都是真初始段,集合 就同时属于 与 ,从而属于 ,与反自反性矛盾。所以它等于其中一个序数,而该序数就是另一个的初始段。整个证明从未构造两个序之间的同构。
证明
(最小反例)
对 内的归纳,若有反例,分离出反例集,其最小成员违背归纳条件。对全体序数,不必收集所有反例:任取反例 ,在集合 内找最小反例即可。
证明
(相容近似与替换)
递归中,把在定义域 上满足规则的函数称为近似。两个近似在共同定义域上必相等:若有最小分歧点,此前限制相同,规则就给出相同下一值。对 归纳构造近似。零阶段取空函数;后继阶段加入唯一指定的值;极限阶段用替换收集所有较短的唯一近似,再取并。兼容性保证并是函数,且满足规则。这个论证同时证明存在、唯一性和极限处的集合存在性。
证明透视
极限阶段的两项工作
递归证明同时有逻辑任务和集合存在任务。唯一性保证两个部分构造在共同定义域上相等,因而它们的并单值;替换则为每个较短长度收集唯一近似,保证准备取并的族是集合。两项任务不能互相取代。
后继只增加一个图像有序对,极限却同时需要全部较早阶段。若某步的规则不唯一,兼容性就不再自动成立;若指标不限制在一个序数内而遍历所有序数,替换也不再给出全部阶段的集合。定理用唯一输出规则处理前一个问题,用每个集合大小的界分别构造处理后一个问题。随后可写对所有序数适用的可定义类记号,但它不表示定义域包含全体序数的单个集合函数。检查递归时,先看兼容,再看收集,最后才取并;这也解释了极限步骤为何需要超出普通后继归纳的论证。
证明
(用序数分类良序)
对一般良序 ,沿此前驱初始段作同样的良基递归,定义 。替换收集这些值。沿 归纳可证各值都是序数,且 等价于 。值域是传递的序数集合,因而是序数, 即所需序同构。两个序数之间的序同构由归纳逐点固定成员,所以序数唯一。
例题
例题 3.1.7
(极限不是最大的有限数)
的上确界是 ,但没有最大项。 有最后元素 ,而 没有,所以二者不序同构。不过把额外点 送到 、有限 送到 ,就得到集合之间的双射。
例题 3.1.8
(加法保留次序)
对第二个变元递归定义
其中 为非零极限。这表示先排一个 ,再排一个 。于是 ,但 。前者没有最后一点,后者有。序数加法不交换,不能用基数加法替代。
例题 3.1.9
(乘法也保留排列)
定义 、,极限处取上确界。故 ,但 。后者有连续排列的两个无限块;在两块交界处,第一块没有最后一点,第二块却有第一点。这里 是依次排列 个 。
例题 3.1.10
(全体序数不构成集合)
若它们构成集合 ,则 是序数。 也应属于 ,从而 ,违背比较。可以对全体序数量化,却不能把它们全体当成替换的输入集合。
反例模式
只有基础与后继步骤并不足够
断言:在零成立、并由每个序数传到其后继的性质,对所有序数成立。考虑“此序数有限”这个性质。零满足它;只要 满足, 也满足,但 不满足。故起点与后继步骤不构成超限归纳。完整条件要求:若极限之前的每个位置都满足,极限自身也必须满足。本例恰在 缺少这项条件。
例题 3.1.11
(累积层级的后继与极限步骤)
真正的极限论证通常用并集代替最后一步。对 层级,可同时证明每层传递,且 时 。若 传递,每个成员都包含于 ,所以 。其幂集也传递: 推出 ,再由传递性得 ,即 。极限时,递增传递集合族的并仍传递,因为 先把 放在某层,该层传递性又把 放在那里。这些分别检查了后继与极限机制,而不是只画不断变大的集合。
例题 3.1.12
(不存在无限严格下降序列)
假设已有函数 ,从 取序数值。替换把值域收集为非空序数集,所以有最小成员 ;但 更小且仍在值域,矛盾。证明处理的是已经给出的下降序列。如果只说每次都能找一个更小元素,还须解释如何把这些存在性选择转成整条序列;唯一或规范规则可以避免额外选择。
递归方向也由此清楚。超限递归使用较小指标的全部值,是因为前驱形成良基范围。依赖未来值的方程是另一个问题,未必存在解,也未必唯一。例如只要求二值序列为常数,就有两个解;这不是定理中由以前数据唯一指定下一值的规则。证明与定义时都应先写清依赖方向及定义域。
以拼接理解算术
加法与乘法的递归条款便于计算,但结合律、消去律、分配律这些常用规律很难直接从条款中读出。换成图像就清楚得多: 是一份 之后接一份 , 则是 份 首尾相接。下面把这幅图像写成定理,再从中读出各条规律。下一单元 3.2 序数乘方、Cantor 正规形与共尾数 会直接使用这些规律。
定义 3.1.13
(有序和与有序积)
设 、 为良序。有序和 是集合 ,其中每个标记为 的点都排在每个标记为 的点之前,标记相同的两点则按 或 的序比较。有序积 是集合 ,规定 当且仅当 ,或 且 :先比较 坐标。对良序 ,记 为与 序同构的唯一序数。
两者都是线性序,而且都是良序。 的非空子集若含标记为 的点,最小元就是其中最小的标记 点,否则是最小的标记 点。对 的非空子集,先取其中出现的最小第二坐标 ,再取使 属于该子集的最小 。逐坐标套用序同构,可见序同构的加项或因子给出序同构的和与积;因此 与 只依赖 与 。
定理 3.1.14
(递归算术计算的是序型)
对所有序数 ,
证明
(两边满足同一递归)
证明依靠序型的两个事实。
(i) 若良序 有最后元素 ,则 。把 到序数 的序同构以 延拓,就得到 到 的序同构。
(ii) 若良序 是初始段集合 的并,则 。设 为序同构。它把每个 映到序数 的一个初始段;这个初始段若不是整个序数,便是它的某个成员,总之是序数,并由序型的唯一性等于 。这些像的并是 ,而序数集合的并就是其上确界。
固定 ,令 。当 时 ,且 是 的初始段。 是 的一份副本,故 。 的最后元素是 ,删去后剩下 ,由 (i) 得 。设 为非零极限。 的每一点都落在某个 的 中:点 落在 中,且 ;标记为 的点落在 中。于是 (ii) 给出 。这正是定义 的三条条款,对 归纳即得 。
乘法方面,令 。由于 ,。 是 之后再接区块 ,后者是 的一份副本;所以它与 序同构,由加法情形得 。在非零极限 处,每点 都落在初始段 中,且 ,故 (ii) 给出 。再对 归纳便完成证明。
定理 3.1.15
(序数算术的规律)
对所有序数 :
- ,且 。
- 若 ,则 。因此 推出 。
- 若 ,则 。
- 。
- 若 ,则恰有一个序数 使 。
- 若 且 ,则 。若 ,则 。
- ,且 。
证明
(每条规律都是拼接之间的序同构)
全程用到良序的两个观察。第一,良序 的真初始段 序型严格较小:序同构 把 映成一个序数的真初始段,即该序数的成员。第二,若有严格递增映射 ,则 。与序同构复合后得到序数之间的严格递增映射 ;下面关于递增映射的练习给出每个 都有 ,故 。
(1) 与 都是 的副本, 与 亦然。
(2) 若 ,则 是 中遗漏 的初始段,因而是真初始段,序型较小。若 ,比较定理给出 或 ,两种情况下两个和都不相等。
(3) 由于 ,从 到 的包含映射严格递增。
(4) 与 都是先一份 、再一份 、再一份 。具体地,、、 定义一个序同构。和的序型只依赖加项的序型,所以前者序型为 ,后者为 。
(5) 令 ,赋予 的序,并令 。 的每个成员都小于 的每个成员,且 ,所以 、 定义序同构 。故 ;唯一性就是 (2) 中的消去律。
(6) 若 且 ,则 是 中遗漏 的初始段。至于第二个断言,从 到 的包含映射严格递增。
(7) 与 定义序同构 :两个序都先比较标记,再比较 或 坐标,最后比较 坐标。同样, 是序同构 ,因为两个序都依次比较 、、。
反例模式
双边规律不成立
声称:序数算术满足自然数算术的其余规律。以下每一条都不成立。
- 交换律:,且 。
- 右消去律,以及对左变元的严格递增:,但 。同样 。
- 右分配律:,而 。
每个例子中,加在左边的部分都被一个没有最后点的无限区块吸收。在 中,新的首点之后接一份 ,整体序型仍是 。保留下来的正是单边规律 (2)、(3)、(6)、(7)。
例题 3.1.16
(用规律计算)
由规律 (1) 及递归,。于是由结合律及 ,
其次,每个有限 都有 : 是规律 (1),而
在极限处,。由于 ,这个上确界等于 。若右分配律成立,结果应是 ,但由规律 (2) 它严格更大。每个区块多出的最后一点都被下一个区块吞没。
常见错误
常见错误
(传递集合未必是序数)
传递集合未必是序数。例如 传递,但其成员 与 在成员关系下不可比较。
允许相等, 不允许。只证明后继步骤会遗漏极限阶段。
常见错误
(序数相等不等于存在双射)
双射不能证明序数相等:序数按序同构分类良序,基数才按双射分类集合。
常见错误
(“一直继续”不是递归)
“一直继续”不构成递归证明;极限时须说明此前数据构成集合且兼容。
总结
序数以所有前驱表示良序位置。最小反例证明超限归纳;兼容近似与替换证明超限递归。有序和与有序积把递归运算等同于良序的拼接,单边规律、减法与带余除法都可从这幅图像读出。极限及不交换的算术表明,无限序不能直接照搬有限直觉。
练习
快速检查
(后继的上确界)
证明非空序数集的并若为后继,则该集合有最大成员。反向成立吗?
解答 · 答案
若 ,则存在 使 。于是 ,迫使相等,故 最大。反向不成立: 有最大成员,但其并是极限 。有最大成员时,并等于这个成员,可以是零、后继或极限。
快速检查
(被 吸收)
证明有限 满足 ,并依递归定义计算 。
解答 · 答案
有限归纳给出 有限,而且这些值在 中无界,故上确界为 。有限 满足 ,取上确界得到 。
快速检查
(最初几个层级)
递归定义 ,计算 。
解答 · 答案
定义 、,非零极限处 。每步唯一指定一个集合,故可在任意序数界内递归。前三项是 、、,而 。
快速检查
(递增映射不小于恒等映射)
证明序数之间的严格递增函数 对每个 满足 。
解答
假设对 都有 。严格递增给出 ,故每个 都属于 。因此 ,比较定理给出所需不等式。超限归纳完成证明;尤其较大的序数不能严格递增地嵌入较小序数。
快速检查
(哪些序数在左边吸收一点?)
求所有满足 的序数 。
解答 · 答案
恰好是所有 。在有限序数上,加法递归就是自然数的递归,由构造自然数、整数与有理数可知它可交换;所以有限 满足 。若 ,规律 (5) 把 写成 ,结合律给出 。
快速检查
(带余除法)
设 。证明每个序数 都可以唯一地写成 ,其中 。
解答
存在性。由规律 (6) 与 (1),,所以有最小的序数 使 。它不是 ,因为 。它也不是极限:否则 ,因为由最小性每个 。故 ,且 。规律 (5) 给出 使 ,再由规律 (2), 化为 。
唯一性。设 ,其中 。若 ,则 ,矛盾;对称情况相同。故 ,再由消去律 (2) 得 。例如 除以 ,商为 、余数为 ;而 除以 ,商为 、余数为 。