Skip to content

恒等类型消去子

Identity type eliminator · J eliminator · Path induction

以反身路径分支消去任意恒等证明,并由 motive 控制端点与路径依赖的 J 原理。

条目类型
原则

形式陈述

恒等类型的通用消去规则以同时依赖两个端点和路径的 motive 为核心。若

Γ,x:A,y:A,p:IdA(x,y)C(x,y,p)type

且在反身情形有

Γ,z:Ad(z):C(z,z,reflz),

则可形成

Γ,x:A,y:A,p:IdA(x,y)JC(d,x,y,p):C(x,y,p).

其 computation rule 精确地落在反身构造子上:

JC(d,z,z,reflz)d(z):C(z,z,reflz).

这条判断式 β-rule 与 motive 的端点、路径参数都不可省略;若把 C 误写成只依赖 p,许多运输和异端点结论将根本无法定型。固定左端点 a:A 后还有 based path induction:给定

y:A,p:IdA(a,y)D(y,p)type,d:D(a,refla),

得到 JDa(d,y,p):D(y,p),并在 (a,refla) 上计算为 d。两种形式可互相导出,但推导要显式安排 motive,不能只靠改名变量。

J 是一般消去子与归纳原理针对恒等类型的实例;其类型中大量使用依赖函数类型来量化端点、路径和证据。结构代入必须同时作用于 A,C,d,由此保证消去结果在替换语境后仍具有替换后的 motive。

直觉

J 的思路是:若一项构造对“一个点到自身的反身路径”已经定义好,那么它可以一致地延伸到任意恒等证明。这里不是先检查路径的内部表示再分支;使用者只能通过反身生成原则观察它。motive 像一张随起点、终点和所走路径变化的任务单,反身分支则是在唯一基本施工现场完成的样板。

路径归纳之所以比普通模式匹配微妙,是因为匹配 p 后,端点 y 的类型信息也要随之精化为 x。J 把这种精化写进结论 C(x,y,p),β-rule 再说明反身时精化具有实际计算效果。它既是等式推理规则,也是依赖程序中的安全运输机制。

例子与边界

给定族 B:AU,令 motive 为

C(x,y,p)=B(x)B(y),

反身分支取 d(x)=λu.u。J 随即给出

transportB(x,y,p):B(x)B(y),transportB(x,x,reflx,u)u.

B(n)=Vec(X,n)p:m=Nn,运输把 v:Vec(X,m) 送到 Vec(X,n)。若把 motive 错写成固定返回 B(x),就只能得到原类型中的值,无法解释目标纤维 B(y),这是一项可直接由 typing judgment 检出的错误。

类似地,对 f:AB 取 motive C(x,y,p)=IdB(f(x),f(y)),反身分支为 reflf(x),得到 apf(p)。再以 J 定义路径逆与连接,可以证明单位律和结合律;普通内涵理论中这些律一般由更高恒等项见证,不必判断式成立。

J 不是 K 原理。K 允许在固定端点的自等式族上证明任意 p:a=Aarefla 相等,从而导向 UIP;它并不把抽象 p 判断式归约为 refla,也不能由标准 J 无条件推出。表面 dependent pattern matching 若允许在相等证明上任意细化,可能暗中获得 K,因此 without-K 风格系统会限制某些匹配。也不能把 β-rule 扩展成“J 对任意抽象 p 都约简”:只有主参数明显为 refl 时才有该判断式计算。

推论与应用

J 系统地产生相等替换、运输、同余、对称和传递,并使 Leibniz 式“相等者可在性质中替换”成为类型论内部的可计算程序。证明助理的 rewritesubst 与依赖 cast 最终都要产生等价的核心消去项;自动化可以隐藏 motive 推断,却不能绕开其良构性。

在高阶类型论中,J 还为路径群胚结构奠基:对路径再做 J,可处理路径之间的路径。它没有预设所有高阶结构平凡,因而既兼容集合式模型,也给同伦模型留下空间。加入额外相等原则时,应分别记录它们是新公理、命题式定理还是带判断式计算的新类型论规则。

参考资料
  • Per Martin-Löf, Intuitionistic Type Theory, Bibliopolis, 1984,propositional equality elimination 与 computation rule。
  • Per Martin-Löf, “An Intuitionistic Theory of Types: Predicative Part,” in Logic Colloquium ’73, North-Holland, 1975, pp. 73–118,恒等类型消去与 predicative type theory。
  • The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study, 2013,§1.12,path induction、transport 与基点版本。
关系图谱8 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。

类型化关系