动机
序数递归之所以可行,是因为每个阶段的前驱都构成一个良序集合。许多构造具有不同的依赖模式:一个对象可以依赖若干更早的对象,而这些对象并不位于同一个线性序中。有限的表达式树就是一个初等的例子。正确的要求是:每个由尚未完成的对象组成的非空集合,都含有一个其依赖对象已全部落在该集合之外的元素。
集合的属于关系提供了最重要的实例。基础公理说明,非空集合含有一个在其内部没有前驱的成员。这使我们能够给每个集合指定一个序数高度,即它的秩。在此之前,我们先证明使这类指定合法的一般递归原理。同一原理还把一个抽象的、良基且外延的关系,变成传递集合上真正的属于关系。因此,坍缩与秩这两个构造表达了两个互补的想法:由前驱结构恢复出一个典范的集合,以及度量该结构向下延伸多远。
定义
定义 1.2.1
(良基关系与外延关系)
设 是集合上的一个关系。当 是 的直接前驱时记作 ,并令 。若每个非空的 都含有某个 使得 ,则称该关系是良基的。若 蕴含 ,则称它是外延的。
定义 1.2.2
(向下封闭)
若 蕴含 ,则称集合 是向下封闭的。令 包含 以及沿前驱方向经过有限步所到达的所有对象。具体地,从 出发,令 ,并取 。由替换公理与并集公理,它是一个集合;它是包含 的最小向下封闭子集。
定义 1.2.3
(传递集合与累积层级)
若 蕴含 ,则称集合 是传递的。累积层级定义为 ,,并在非零极限序数处令 。序数一章已经证明了集合长度的超限递归,并验证了这些阶段是传递的且递增的。
在本章中,所有关系都定义在集合上。真类上的一般递归需要额外的集合性假设,这里并不隐含地包括它。
定理/命题
定理 1.2.4
(良基归纳与递归)
对集合 上的良基关系,若一个公式在 处成立的条件是它在每个 处成立,则它在整个 上成立。此外,设可定义的规则 在 且 是 上的函数时指定唯一的集合。则恰好存在一个 上的函数 满足
不需要选择公理。收集递归数据所依靠的是唯一取值条件与替换公理,而不是任意的同时选取。
定理 1.2.5
(集合关系的莫斯托夫斯基(Mostowski)坍缩)
若 上的 是良基且外延的,则存在唯一的传递集合 与唯一的同构 。它们由下式给出:
这里的同构指满足 的双射。外延性对单射性是必要的;良基性对递归构造是必要的。
概念视角结构
坍缩作为完全不变量
对良基且外延的关系, 当且仅当两者的坍缩有相同值域。若 是同构,则 是 到传递集合 上的同构,由唯一性得 ,值域相等。反过来,值域相等就给出同构 。由于带属于关系的传递集合就是自身的坍缩,这类结构在同构意义下恰好与传递集合一一对应。
定理 1.2.6
(秩与累积层级)
在 ZF 中,每个集合 都有唯一确定的序数秩
对每个序数 ,
因此每个集合都属于某个层级阶段。但这并不表示整个宇宙或整个层级是一个集合。
证明思路
证明
(极小反例与可容许点)
归纳法由分离公理得出:由反例组成的非空集合会有一个 -极小成员,这与假设矛盾。该论证既不需要线性序,也不要求每个非极小点都有一个直接前驱。
下面是递归的集合存在性证明。一个良好的部分函数,其定义域是向下封闭的,并且在该定义域上满足所要求的等式。两个良好函数在它们的公共定义域上一致。否则,它们不一致之处所组成的集合会有一个 -极小成员,其前驱上的限制一致,从而迫使下一个取值也一致。
若在 上存在良好函数,则称 是可容许的。由上述相容性论证,这样的函数是唯一的。若存在由不可容许点组成的非空集合,取其中一个 -极小者 。每个 都是可容许的。因此,替换公理收集集合 上唯一的良好函数;不需要选取见证。它们的并是 上一个相容的良好函数。此定义域包含 的每个前驱,而不包含 ,因为一条有限的回路会与良基性矛盾。再添上在 处唯一被指定的值。新的定义域恰为 ,这与 的不可容许性矛盾。因此所有点都是可容许的。替换公理把它们唯一的局部取值收集成 上的一个函数,而相容性证明了它满足等式并且是唯一的。
证明透视
相容性不能代替收集
在递归证明的极小坏点处,相容性保证局部图在重叠处一致。替换公理另外保证,这些唯一确定的图构成一个以前驱集合为指标的集合。只有这样才能取它们的并。这与在序数极限处所作的两部分检验相同,只是现在应用于非线性有序的依赖结构。
证明
(前驱像与单射性)
对于坍缩,将递归应用于 。替换公理使这个像成为集合。值域 是传递的,因为 的每个元素都是某个满足 的 。我们仍需证明单射性:前驱像的集合相等,并不经过论证就使原来的标签相同。
对 作归纳,证明对每个 , 蕴含 。假设该断言对每个 成立,并设 。对于 ,由 得到某个 使 ;在 处的归纳假设给出 。反过来,对于 ,像集合相等提供了某个 使 ,同样的假设给出 。于是 ,由外延性得 。单射性使 成为到 上的同构。若另有一个同构,其值域是传递的,则 的像的每个成员都是某个前驱的像,因此它满足同样的递归。递归的唯一性使这两个映射及其值域重合。
证明透视
单射性的归纳为什么带着全称量词
归纳只对 进行,但所传递的命题是“对每个 , 蕴含 ”。我们对配对的 一无所知,所以在每个 处的假设必须已经涵盖所有可能的配对 。像相等使前驱在两个方向上互相匹配,假设把每次匹配变成标签相等,而外延性只用一次,把前驱集合相等变成 。良基性只通过归纳本身进入证明。
证明
(在传递界上递归定义秩)
对于秩,固定集合 。从 出发,反复添加并集,得到包含 的传递集合 。基础公理使限制在 上的属于关系是良基的:把它应用于 的任何非空子集即可。在这个集合关系上作递归,指定 。归纳法表明所有取值都是序数;于是该公式恰好就是 。两个包含 的传递集合给出相同的值,因为它们的递归函数在其向下封闭的交集上一致。这样定义的 与所选的上界无关。
对 作超限归纳以证明层级公式。在零处是显然的。在后继处,
最后的等价由取后继秩的上确界得到,并且对空集 也成立。在非零极限处,属于并集意味着属于某个更早的阶段。这等价于秩小于该极限,因为任何更小序数的后继仍然小于该极限。子集公式由后继情形得出。特别地,。对所有序数阶段取并是类的记号,并不是被允许的以集合为指标的并。
例题
例题 1.2.7
(坍缩不一定是序数)
取三个相异的标签 以及关系 、,没有其他的序对。它是良基且外延的。坍缩为 ,,。其传递值域为 ,它不是序数:其成员 与 按属于关系不可比较,并且该关系不是传递的。坍缩产生的是传递集合,而不一定自动是线性有序的传递集合。
反例模式
删去坍缩的任一假设
断言:集合上任何良基关系,或任何外延关系,都同构于某个传递集合上的属于关系。对于两个相异的孤立标签,该关系是良基的但不是外延的:两个前驱集合都是空集。递归把两者都送到 ,所以它不是单射。对于带有一个自环的单一标签,该关系是外延的但不是良基的。坍缩将要求 ,从而 ,这与基础公理相违。这两个例子分离出不同的失败方式,而不是把两个假设视为可互换的。
例题 1.2.8
(秩不是成员的个数)
空集的秩为零,并且 。每个有限序数 的秩为 ,而超限归纳给出对每个序数都有 ,因为 。因此 的秩为 ,而它的单元素集的秩为 。单元素集尽管永远只含一个元素,其秩却可以任意大。秩度量的是属于关系的深度,而不是基数。
例题 1.2.9
(集合首次被包含的阶段要晚一步)
设 ,即序数二。它的秩为二,所以 但 ;它首次被包含的阶段是 。对于库拉托夫斯基(Kuratowski)有序对 ,单元素集与二元集的公式给出
所增加的两个后继阶段来自两层花括号,包括 的情形。把属于与包含区分清楚,可以避免这两个计算中差一的错误。
例题 1.2.10
(无限高度不需要无限下降道路)
取 ,其中 。自然数之间令 当且仅当 ,并对每个自然数规定 。关系良基:非空子集若遇到 ,便有最小自然数成员;否则只有 。坍缩把 送到 ,把 送到 。
从 向下走,第一步先到某个有限自然数,再在自然数间严格下降,所以不能无限继续。但有限下降道路的长度没有统一界, 处坍缩集合的秩为 ,不是有限数。故没有无限下降道路并不意味着高度有限。秩取所有前驱高度的上确界,无限多个分别有限的高度可以有极限上确界。这也说明只计算几个有限依赖图,不足以证明一般递归定理。
常见错误
常见错误
(用“没有下降序列”取代良基性)
在 ZF 的证明中,不应当悄悄地用“没有无穷下降序列”来替代良基性的子集定义。给定一个无穷下降序列,取其值域即与良基性矛盾。但从一个每个点都有某个前驱的集合出发去构造这样的序列,则可能需要依赖选择原理。极小反例的定义避免了这一隐藏的选取步骤。
常见错误
(外延性关乎前驱集合)
的外延性涉及的是** 之内**的前驱集合。它不是标签的通常相等,也不是关于 是传递的断言。此外,在本文的展开中,秩依赖于基础公理;同样的论证不能用来给任意循环的属于结构指定秩。
总结
良基递归可以解决具有唯一指定输出的集合大小的依赖图。外延性使前驱像递归成为单射,从而得到莫斯托夫斯基(Mostowski)坍缩。随后,基础公理与传递闭包给每个集合指定一个秩,而层级公式确切说明了它何时进入累积层级。
练习
快速检查
(四点坍缩)
对 上的一个关系作坍缩,其前驱集合依次为 、、 与 。它的值域是序数吗?
解答 · 答案
像依次为 、、 与 。值域是传递的,因为每个所列集合的每个成员都出现在这些像之中。它不是序数: 与 仍然不可比较。相异的前驱集合与所列出的无环依赖图验证了这些假设。
快速检查
(属于与包含下的秩)
证明 蕴含 。 是否蕴含严格不等式?
解答 · 答案
定义中的上确界至少为 ,这就证明了严格性。包含关系则只给出 ,这通过比较两族后继秩得到。即使对真子集,它也不一定是严格的:偶数自然数构成 的真子集,其秩同样为 ,因为它们的有限后继秩在 中是无界的。
快速检查
(并集的秩)
证明 ,包括空集的情形,并推出以 表示的上界。
解答
展开两个上确界:
空上确界为零,所以该公式包括 与空成员的情形。由于右边的每个秩都以 为界,所以并集的秩至多是该秩。它可能更小: 的秩为一,但它的并集的秩为零。
快速检查
(没有外延性的同构)
解释为什么一个没有边的两标签关系,可以与配备限制属于关系的集合之间有许多同构,尽管坍缩递归在每个标签处只有一种可能的输出。
解答 · 答案
一个合适的目标是 ,其中 :两个成员都不属于对方,也都不属于自身。特别地, 的唯一成员是 ,它不同于 。它的两个标签可以按任一顺序双射地指派,从而给出空关系的两个同构。这个 不是传递的。坍缩定理要求值域是传递的且源关系是外延的;空的两标签关系不满足外延性,其递归把两个标签都送到零,而不是给出一个双射。