“检查一个函数 $f:\Pi(n:\mathbb N).\mathsf{Vec}(A,n)\to C(n)$ 时,匹配 会产生约束 $n\equiv0$,匹配 会产生 $n\equiv\mat…”
形式陈述 ​
恒等类型的通用消去规则以同时依赖两个端点和路径的 motive 为核心。若
且在反身情形有
则可形成
其 computation rule 精确地落在反身构造子上:
这条判断式 β-rule 与 motive 的端点、路径参数都不可省略;若把
得到
J 是一般消去子与归纳原理针对恒等类型的实例;其类型中大量使用依赖函数类型来量化端点、路径和证据。结构代入必须同时作用于
直觉
J 的思路是:若一项构造对“一个点到自身的反身路径”已经定义好,那么它可以一致地延伸到任意恒等证明。这里不是先检查路径的内部表示再分支;使用者只能通过反身生成原则观察它。motive 像一张随起点、终点和所走路径变化的任务单,反身分支则是在唯一基本施工现场完成的样板。
路径归纳之所以比普通模式匹配微妙,是因为匹配
例子与边界
给定族
反身分支取
若
类似地,对
J 不是 K 原理。K 允许在固定端点的自等式族上证明任意 without-K 风格系统会限制某些匹配。也不能把 β-rule 扩展成“J 对任意抽象
推论与应用
J 系统地产生相等替换、运输、同余、对称和传递,并使 Leibniz 式“相等者可在性质中替换”成为类型论内部的可计算程序。证明助理的 rewrite、subst 与依赖 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 与基点版本。