Skip to content

宇宙类型

Universe type · Type universe

在分层类型论中容纳小类型并允许对类型量化,同时避开自包含宇宙悖论的类型形成子。

条目类型
定义

形式陈述

宇宙把一类“小类型”收进类型论内部,使它们可以作为项被量化和计算。本文选用 Russell 风格记法,并显式标注层级:

ΓUitype,ΓUi:Ui+1,ΓA:UiΓAtype.

这里最后一式把 Ui 的元素直接读作类型,是对基础类型判断的分层扩展。宇宙还需说明闭包规则。例如若 ΓA:UiΓ,x:AB:Uj,通常可形成

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

Σ 类型与恒等类型有相应闭包;具体层级上是否隐式提升,要由累积政策决定。所有规则在替换下稳定:A:Ui 经良型替换 σ 后得到 A[σ]:Ui,类型族中的层级不能因代入任意改变。

另一种同样标准的 Tarski 风格不把宇宙元素直接当类型,而采用代码 a:Ui 与解码 Eli(a)type;Π、Σ 等闭包由代码构造器表达。两种口径可以有紧密模型联系,却不能在一套公式里一会儿省略 El、一会儿又把元素称为代码。本文后续始终沿用 Russell 口径。

直觉

没有宇宙时,类型只出现在判断的右侧,程序不能接收“一个类型”再返回以它为参数的结构。宇宙像经过尺寸分区的类型目录:Ui 列出第 i 层允许谈论的小类型,而目录本身太大,必须放进更高层 Ui+1。这样既可写多态程序,又不让目录把自己作为普通条目吞进去。

“小”不是元素个数少,而是相对于当前宇宙层级可编码。自然数、有限类型、由小类型形成的 Π/Σ 往往仍小;Ui 自己相对于本层则是大类型。层级因此承担逻辑防火墙的角色,也为实现中的 universe constraint 留出精确含义。

例子与边界

多态恒等函数可写成

id:Π(A:U0).AA,id=λA.λx.x.

由于量化变量 A 的定义域是 U0:U1,整个 Π 类型一般位于 U1,而不是仍在 U0。实例化给出

idBooltruetrue:Bool

只要 Bool:U0。这个推导展示宇宙的实际用途:A 在项位置被传入,随后又在余类型中充当类型。

核心禁区是 U:U。把包含自身、并对依赖函数封闭的宇宙与足够强的类型构造结合,会触发 Girard 悖论;因此不能为了省略层级而把 Ui:Ui 写成 harmless shorthand。层级多态可以让源码省略具体下标,但内核仍要生成并求解 i<jmax(i,j) 等约束。宇宙也不是集合论的冯·诺伊曼累积层级:两者都有分层思想,元素关系、相等概念和闭包规则却不同。

推论与应用

宇宙使泛型库、类型族和内部化语义成为可能。容器可按 A:Ui 参数化,解释器可把语法代码映到 Ui 中的意义,较高宇宙还能容纳“小类型范畴”一类整体结构。证明助理据此检查用户定义究竟是 universe-polymorphic,还是只在某个固定层可用;错误的层级约束会在形成类型时暴露,而非演化成逻辑矛盾。

宇宙本身不决定累积性、不可达基数式闭包、命题宇宙或 resizing 原理。非累积系统可要求显式 lifting;累积系统可允许低层类型在高层重用;Tarski 系统可能把 lifting 表示为代码函数。每种扩展都改变 formation 与 conversion 的细节,相关正规化和一致性结论必须针对选定规则重新建立。

参考资料
  • Per Martin-Löf, Intuitionistic Type Theory, Bibliopolis, 1984,Universes 讲义及类型形成规则。
  • Bengt Nordström, Kent Petersson, and Jan M. Smith, Programming in Martin-Löf’s Type Theory, Oxford University Press, 1990,universes、sets 与类型依赖编程。
  • The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study, 2013,§§1.3、2.10,Russell-style universes 与层级约定。
  • Thierry Coquand, “An Analysis of Girard’s Paradox,” Proceedings of the First IEEE Symposium on Logic in Computer Science, 1986, pp. 227–236,type-in-type 风险的结构分析。
关系图谱11 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

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