“空语境良构;若 $\Gamma;\mathsf{ctx}$ 且 $\Gamma\vdash A;\mathsf{type}$,便可扩张为 $\Gamma,x:A;\mathsf{ctx}$。…”
形式陈述 ​
宇宙把一类“小类型”收进类型论内部,使它们可以作为项被量化和计算。本文选用 Russell 风格记法,并显式标注层级:
这里最后一式把
Σ 类型与恒等类型有相应闭包;具体层级上是否隐式提升,要由累积政策决定。所有规则在替换下稳定:
另一种同样标准的 Tarski 风格不把宇宙元素直接当类型,而采用代码
直觉
没有宇宙时,类型只出现在判断的右侧,程序不能接收“一个类型”再返回以它为参数的结构。宇宙像经过尺寸分区的类型目录:
“小”不是元素个数少,而是相对于当前宇宙层级可编码。自然数、有限类型、由小类型形成的 Π/Σ 往往仍小;
例子与边界
多态恒等函数可写成
由于量化变量
只要
核心禁区是
推论与应用
宇宙使泛型库、类型族和内部化语义成为可能。容器可按
宇宙本身不决定累积性、不可达基数式闭包、命题宇宙或 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 风险的结构分析。