形式陈述
作为一种以端点为索引的依赖类型 公理库 依赖类型 Dependent type 类型表达式可依赖项值的类型系统构造。 ,恒等类型在 A 为类型且 a , b : A 时具有如下 formation 与 introduction 规则:
Γ ⊢ A type Γ ⊢ a : A Γ ⊢ b : A Γ ⊢ Id A ( a , b ) type , Γ ⊢ a : A Γ ⊢ refl a : Id A ( a , a ) . 一般消去由J 消去子或路径归纳 公理库 恒等类型消去子 Identity type eliminator · J eliminator · Path induction 以反身路径分支消去任意恒等证明,并由 motive 控制端点与路径依赖的 J 原理。 承担:要处理任意 p : Id A ( a , b ) ,只需在端点重合且 p 为 refl 时给出依赖分支;对应 β-rule 在该反身情形按定义计算。替换规则把三项一起改写:
Id A ( a , b ) [ σ ] ≡ Id A [ σ ] ( a [ σ ] , b [ σ ] ) . 记号 a = A b 通常是 Id A ( a , b ) 的缩写。它是一个类型,居民 p 是对象语言中的项;与之相对,定义相等 公理库 定义相等 Definitional equality · Judgmental equality · Conversion equality 由计算、展开与同余规则生成并供类型转换使用的判断层等同关系。 Γ ⊢ a ≡ b : A 是判断层的计算性识别,不产生可被程序检查或传递的 p 。若 a ≡ b : A ,转换规则通常允许 refl a 具有 Id A ( a , b ) ;反向从任意 p 推出 a ≡ b 则是相等反映,标准内涵理论并不采纳。
直觉
恒等类型把“相等的证据”放进类型世界。定义相等像排字阶段发现两段表达式计算后本就是同一行,不需要票据;恒等类型则像一条可携带、可组合的路径,即使两个端点没有化成相同语法,也可能有项证明它们相连。路径归纳说明所有这类证据的合法使用最终由反身路径生成,但这并不宣告所有路径彼此判断相等。
这种区分让等式既有计算内容又不吞没类型检查。程序可接收 p : a = A b ,沿 p 把依赖于 a 的数据运输到依赖于 b 的位置;内核仍只用受控的判断相等核对每一步类型。高阶解释还允许路径之间再有恒等类型,因而同一端点间可能保留非平凡结构。
例子与边界
给定类型族 B : A → U ,可由 J 定义运输
transport B : Π ( a , b : A ) . Id A ( a , b ) → B ( a ) → B ( b ) , 并满足
transport B ( refl a , u ) ≡ u : B ( a ) . 取 A = N 、B ( n ) = Vec ( X , n ) 。若 p : Id N ( m , n ) 且 v : Vec ( X , m ) ,则 transport B ( p , v ) : Vec ( X , n ) ;没有 p 时,不能把长度 m 的向量无条件当作长度 n 的向量。若 p 恰为 refl m ,运输判断式地化为 v ;对抽象变量 p ,运输通常保持为中立项,不会凭空约简。
一个具体边界来自自然数加法。若递归定义在第一个参数上,0 + n ≡ n 可能直接计算,而 n + 0 = n 对变量 n 通常需要归纳产生恒等项;后者成立不使两端自动成为判断相等。标准 J 也不推出 UIP 或 K,即不保证任意 p , q : a = A b 都相等;加入这类原则会排除某些高阶路径模型,并与通常的 univalence 解释冲突。反之,证明无关性若只针对命题层,也不能未经规则说明推广到所有恒等类型。
推论与应用
由路径归纳可定义对称、连接、函数作用于路径 ap ,并证明它们满足群胚律;这些律在普通内涵理论中多位于更高恒等类型,而非全部成为判断等式。运输则是改写、类型安全强制转换和索引精化的统一核心:等式证明不仅说明两个值相同,还解释依赖数据怎样随端点移动。
在程序验证中,恒等类型表达代数定律、数据结构不变量和程序等价;在同伦类型论中,它被解释为空间中的路径,迭代恒等类型记录高阶同伦。两种用途共享同一形成—反身—消去规则,但额外采用 UIP、函数外延性或 univalence 会改变可证明结构,必须清楚标注。
参考资料
Per Martin-Löf, Intuitionistic Type Theory , Bibliopolis, 1984,propositional equality 的 formation、introduction 与 elimination rules。
Per Martin-Löf, “An Intuitionistic Theory of Types: Predicative Part,” in Logic Colloquium ’73 , North-Holland, 1975, pp. 73–118,恒等类型与 predicative universes 的早期正式表述。
The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics , Institute for Advanced Study, 2013,§1.12 与 Ch. 2,identity types、transport 与 path structure。