Skip to content

集合的秩

Rank of a set · Set-theoretic rank

以集合首次进入累积层级的位置度量其成员结构的良基高度。

条目类型
定义

形式陈述

在 ZF 中,集合 x定义为

rank(x)=min{α:xVα}.

等价地,它是使 xVα+1 成立的最小序数 α。这里 Vα累积层级。正则公理保证成员关系良基,替换公理保证成员秩的像构成集合,于是良基递归给出更便于计算的公式

rank(x)=sup{rank(y)+1:yx},

其中空集上的上确界为 0。因此

yxrank(y)<rank(x).

秩是序数,不是基数;它记录成员树最长能下降多深,而不记录一层上有多少成员。对每个序数 αrank(α)=α;对层级本身,rank(Vα)=α

直觉

把集合展开成一棵向下的成员树:根是 x,下一层列出 x 的元素,再下一层列出这些元素的元素。秩给每个节点贴上一个严格高于全部子节点的最小序数标签。有限深度时它就是熟悉的树高;存在任意有限深路径时,高度达到 ω;更复杂的良基结构则需要更大的序数。

“首次进入 V 的哪一层”与递归公式说的是同一件事。若所有成员都已在 Vα,那么 xVα 的一个子集,于是下一次取幂集时被收入;反过来,x 若已经在某个后继层,其全部成员必然来自更早层。这个对应把全局层级位置化成可以逐个成员计算的局部不变量。

例子与边界

空集没有成员,所以 rank()=0。令

a={},b={,{}}.

rank(a)=1,而

rank(b)=sup{0+1,1+1}=2.

集合 b 恰好是 von Neumann 序数 2,也具体展示了序数的秩等于自身。再看 ω:每个 nω 的秩是 n,故

rank(ω)=supn<ω(n+1)=ω.

秩相同不意味着集合相同、等势或同构。例如 {}{{}} 的基数都为一,但秩分别为 12;另一方面,许多彼此不同的集合可以共享同一秩。秩也不是公式复杂度:一个定义很短的集合可以具有很高秩,一个定义冗长的有限集合仍只有有限秩。

若放弃正则公理并允许 Quine 原子 q={q},递归式会要求 rank(q)>rank(q),不可能成立。因而秩只直接适用于良基成员关系。对一个外部看来不良基的非标准模型,模型内部可能仍声称每个“集合”有秩;这是内部满足关系与外部真实良基性的差别,不能混为一谈。

推论与应用

秩把对任意集合的证明化为超限归纳:若某性质对 x 的全部成员成立便能推出对 x 成立,就按 rank(x) 归纳即可。这是良基递归、传递闭包、Mostowski 坍缩以及按名字秩定义力迫语义的共同证明骨架。

对任意集合 A,替换给出秩集合 {rank(x):xA},取其上确界后可找一个统一的 Vα 容纳 A 的全部元素,继而容纳 A。这个简单事实说明为什么任何集合大小的数据都只占据宇宙的某个有界高度,也解释了“全部序数”不能构成集合:若它们构成集合,其秩应有一个序数上界,却又包含超过该上界的序数。

秩还能辨认绝对性边界。传递模型正确计算其元素的秩,只要模型含有计算中需要的序数与替换实例;非传递模型则可能把伪序数、伪成员链当作真实对象。秩提供诊断工具,但不自动使一个模型传递,也不保证某个 Vα 满足完整 ZF。

参考资料
  • Herbert B. Enderton, Elements of Set Theory, Academic Press, 1977, Chapter 7, section “Rank”。
  • Thomas Jech, Set Theory, 3rd millennium ed., Springer, 2003, Chapter 6, rank and the Axiom of Regularity。
  • Kenneth Kunen, Set Theory, College Publications, 2011, Chapter I, well-founded recursion and rank。
关系图谱8 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组