Skip to content

恒等类型

Identity type · Propositional equality type

将两个同型项的相等性内化为可拥有居民、可依赖消去的类型族。

条目类型
定义

形式陈述

作为一种以端点为索引的依赖类型,恒等类型在 A 为类型且 a,b:A 时具有如下 formation 与 introduction 规则:

ΓAtypeΓa:AΓb:AΓIdA(a,b)type,Γa:AΓrefla:IdA(a,a).

一般消去由J 消去子或路径归纳承担:要处理任意 p:IdA(a,b),只需在端点重合且 prefl 时给出依赖分支;对应 β-rule 在该反身情形按定义计算。替换规则把三项一起改写:

IdA(a,b)[σ]IdA[σ](a[σ],b[σ]).

记号 a=Ab 通常是 IdA(a,b) 的缩写。它是一个类型,居民 p 是对象语言中的项;与之相对,定义相等 Γab:A 是判断层的计算性识别,不产生可被程序检查或传递的 p。若 ab:A,转换规则通常允许 refla 具有 IdA(a,b);反向从任意 p 推出 ab 则是相等反映,标准内涵理论并不采纳。

直觉

恒等类型把“相等的证据”放进类型世界。定义相等像排字阶段发现两段表达式计算后本就是同一行,不需要票据;恒等类型则像一条可携带、可组合的路径,即使两个端点没有化成相同语法,也可能有项证明它们相连。路径归纳说明所有这类证据的合法使用最终由反身路径生成,但这并不宣告所有路径彼此判断相等。

这种区分让等式既有计算内容又不吞没类型检查。程序可接收 p:a=Ab,沿 p 把依赖于 a 的数据运输到依赖于 b 的位置;内核仍只用受控的判断相等核对每一步类型。高阶解释还允许路径之间再有恒等类型,因而同一端点间可能保留非平凡结构。

例子与边界

给定类型族 B:AU,可由 J 定义运输

transportB:Π(a,b:A).IdA(a,b)B(a)B(b),

并满足

transportB(refla,u)u:B(a).

A=NB(n)=Vec(X,n)。若 p:IdN(m,n)v:Vec(X,m),则 transportB(p,v):Vec(X,n);没有 p 时,不能把长度 m 的向量无条件当作长度 n 的向量。若 p 恰为 reflm,运输判断式地化为 v;对抽象变量 p,运输通常保持为中立项,不会凭空约简。

一个具体边界来自自然数加法。若递归定义在第一个参数上,0+nn 可能直接计算,而 n+0=n 对变量 n 通常需要归纳产生恒等项;后者成立不使两端自动成为判断相等。标准 J 也不推出 UIP 或 K,即不保证任意 p,q:a=Ab 都相等;加入这类原则会排除某些高阶路径模型,并与通常的 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。
关系图谱13 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

并列辨析