Skip to content

累积宇宙层级

Cumulative universe hierarchy

允许低层小类型在高层宇宙中复用,同时保持宇宙自身严格分层的层级政策。

条目类型
定义

形式陈述

给定一列宇宙类型 U0,U1,,累积性是一条额外的层级规则,而不是“有多个宇宙”的同义词。本文沿 Russell 风格表述:

ΓUi:Ui+1,ΓA:UiijΓA:Uj.

因此低层类型可在需要高层类型的位置使用。与此相伴的 Π-formation 可取层级上确界:

ΓA:UiΓ,x:AB:UjΓΠ(x:A).B:Umax(i,j).

Σ、恒等类型和归纳类型也各有封闭规则。无论实现把提升视为隐式 coercion、子类型判断 UiUj,还是类型归属的 admissible rule,都不能把累积性写成 UiUj:两个宇宙仍处在不同层,前者只是可嵌入后者。

在 Tarski 风格中,a:Ui 是类型代码。跨层常由 Lifti,j(a):Uj 表示,并要求解码后 Elj(Lifti,j(a))Eli(a) 有适当相等;代码本身是否判断相等属于另一项设计选择。层级规则也要在替换下稳定,且提升复合应满足从 ik 与先到 j 再到 k 的一致性。

直觉

累积层级像逐层扩大的图书馆:高层阅览室收录低层全部书目,还额外容纳低层目录本身。一本位于 U0 的书不因被拿到 U1 使用就变成另一种内容;但两间阅览室绝不是同一个房间。这个区别让用户能自然复用小类型,同时让内核保留阻止自包含悖论所需的尺寸信息。

非累积系统则要求每次跨层明确装箱或 lifting。两种政策都能保持一致,只是在项语法、转换规则和错误信息上承担不同成本。典型歧义和 universe polymorphism 可以隐藏下标,却只是在约束求解后选择合适层级,并没有抹去层级。

例子与边界

Bool:U0N:U0。累积性立即允许把两者当作 U1 中的类型,所以异层依赖对

P=Σ(A:U0).(AU0)

可在 U1 中形成:定义域 U0 本身位于 U1,每个余类型 AU0 也至多需要 U1。具体居民可以取 (Bool,λ_.N)。若一个函数要求参数 X:U1,便可直接传入 Bool;这一步是层级提升,不是证明 BoolU1 相等。

反例是从 A:U1 反推 A:U0。累积关系只有向上方向;一个以 U0 为元素的“大”类型通常没有低层表示。也不能由 Ui:Ui+1 和累积性推出 Ui:Ui,因为规则要求起始归属层不高于目标层,不能把 i+1 降为 i。若约束生成同时要求 i<jji,正确结果是层级不一致,而非悄悄选取无限层。

推论与应用

累积性让大型库免于在每个组合点插入显式 lift。一个对 A:Uj 定义的容器可接收任何 A:Uiij);包含小范畴、模型或语法解释的结构也可逐级上移。实现通常收集不等式约束,再求一个满足所有 max、后继和严格不等式的层级赋值;层级多态把这一过程参数化,使同一定义可在多层实例化。

便利也带来元理论义务。转换检查必须决定不同提升路径是否相同,归纳类型的大消去要说明目标宇宙许可范围,resizing 原理则可能把原本只可向上的信息重新压低,因而不是累积性自身的推论。本页的层级政策与集合论的累积层级只有类比关系:后者按秩构造集合,前者控制类型形成与量化的大小。

参考资料
  • Per Martin-Löf, Intuitionistic Type Theory, Bibliopolis, 1984,宇宙层级与 predicativity。
  • Bengt Nordström, Kent Petersson, and Jan M. Smith, Programming in Martin-Löf’s Type Theory, Oxford University Press, 1990,universe formation 与跨层使用。
  • The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study, 2013,§1.3,cumulative Russell-style universe convention。
关系图谱4 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

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