“当 $n$ 化为具体数值时,两端也许最终判断相等,运输随证明的具体形状继续计算;当 $p n$ 保持抽象时,cast 可能留在规范形中。这份显式痕迹正是内涵与外延类型论在使用体验上的区别。”
形式陈述 ​
一种典型的外延 Martin-Löf 类型论在依赖类型论上加入 equality reflection:
于是对象层恒等证明可以扩张判断相等,conversion 随当前语境中的证明而变化。若
规则仍需覆盖形成、引入、消去和计算,且相等反映必须在替换下稳定:把
直觉
外延纪律把“已经证明相等”视作“此后内核可无痕当作相同”。这很符合普通数学书写:证明两个集合或函数相同后,读者往往不再标记每一次运输。依赖类型中的索引改写因而更顺滑,quotient 与函数外延原则也更接近日常推理。
代价是转换不再是一台只执行固定化简规则的计算器,而会读取证明环境。类型检查某个看似局部的应用,可能依赖远处是否能建立一个等式定理。外延性改善对象语言的等式体验,却把相当一部分证明搜索推入了 judgmental equality;这正是它与内涵类型论的工程分界,而不是价值高低之分。
例子与边界
仍取按首参数递归的加法,并由归纳得到
在含
因此
边界之一是运行语义:无痕转换不意味着
推论与应用
外延类型论适合把 quotient、集合式函数外延和等式替换直接融入数学语法。范畴语义可把 judgmental equality 解释为模型中的严格等同,或者借助 quotient/completion 把内涵呈现的证据压平。对用户而言,这减少了 transport 堆叠和 setoid bookkeeping;对实现而言,则常需把外延表面理论 elaboration 到可判定的内涵核心,或接受交互式、非完全算法化的 checking。
相等反映也改变元理论证明的方法。不能仅凭一个归约器宣称 conversion 完备,更不能把普通内涵 MLTT 的 normalization 决定过程原封不动搬来。若通过两层系统、显式 coercion 或 observational equality 恢复算法性,应把那套实现称为对外延概念的表示,而不是声称原始 reflection 规则突然变得语法可判定。
参考资料
- Martin Hofmann, Extensional Concepts in Intensional Type Theory, PhD thesis, University of Edinburgh, 1995, Technical Report ECS-LFCS-95-327,equality reflection、quotients 与外延概念。
- Per Martin-Löf, Intuitionistic Type Theory, Bibliopolis, 1984,extensional equality presentation 与判断式规则背景。
- Thomas Streicher, Semantics of Type Theory: Correctness, Completeness and Independence Results, Birkhäuser, 1991,内涵相等与外延模型的语义边界。