“代价是转换不再是一台只执行固定化简规则的计算器,而会读取证明环境。类型检查某个看似局部的应用,可能依赖远处是否能建立一个等式定理。外延性改善对象语言的等式体验,却把相当一部分证明搜索推入了…”
形式陈述 ​
本文所说内涵类型论是在Martin-Löf 依赖类型论核心上保持两层相等分离的系统。它既有判断
也有对象类型
因此 conversion 只使用判断相等,而恒等证明要通过 rewrite、transport 或消去子显式影响依赖类型。这里“内涵”描述相等纪律,不等于一套唯一语法:理论可以选择函数 η、宇宙累积、归纳族或函数外延性公理。要从这套规则得到可判定类型检查,还需证明判断相等可判定,常见充分路线是强正规化、合流与可比较规范形;名称本身不是这项元定理。
同样,UIP/K 既不是内涵理论定义的一部分,也不由 J 自动产生。可以在集合式内涵理论中额外公设 UIP,亦可在同伦取向的内涵理论中保留非平凡高阶恒等。加入公理而不扩充判断计算时,转换算法可能保持原样,但 canonicity、程序抽取或某些规范形定理仍可能改变,必须逐一分析。
直觉
内涵纪律把“算出来一样”和“有理由相信相等”分开。前一种相等由内核机械执行,像把两个表达式归约到同一结果;后一种相等是一份可传入函数、可组合、可在族之间运输的数据。这样做牺牲了一些无痕改写的便利,却让类型检查不必在每次 conversion 时解决任意数学定理。
名称中的 intensional 还提示:两个对象即使在外部观察上无法区分,若没有对应的计算规则或恒等项,也不会自动被判断式识别。它不是“只看语法、完全不看意义”,因为正规化语义、逻辑关系和模型仍可证明丰富结果;它只是把哪些意义相等进入内核判断这件事控制得很严格。
例子与边界
设自然数加法按第一个参数递归。归约直接给出
若
当
边界不能简化成“内涵必然可判定、外延必然不可执行”。带无约束递归或不可判定重写的内涵理论照样会失去转换可判定性;带额外公理但无计算规则的核心也可能保留 type checking,却让某些闭项停在公理常量上,从而破坏朴素 canonicity。反过来,内涵理论可通过 quotient、setoid 或高阶路径表达外延数学,只是改写发生在对象层,并需要相应证明工程。
推论与应用
相等分层让小型可信内核成为可能:elaborator 可以搜索等式证明、插入 transport,最终只把显式核心项交给内核;内核的 conversion 不必信任搜索策略。正规化与 NbE 可为特定内涵核心提供判断相等算法,恒等类型则承载超出该算法的代数定律、函数外延性或同伦结构。
实践中的 Agda、Coq 及许多依赖核心都以某种内涵纪律为基础,但它们在 η、proof irrelevance、宇宙和归纳计算上并不相同。评价一个系统时应列出完整规则,而不是仅凭 ITT 标签推断 UIP、强正规化或 canonicity。内涵与外延也不是“弱逻辑/强逻辑”的排名:前者常以显式证据换取算法边界,后者则把更多已证明相等交给 conversion。
参考资料
- Thomas Streicher, Semantics of Type Theory: Correctness, Completeness and Independence Results, Birkhäuser, 1991,intensional identity types 与独立性模型。
- Martin Hofmann, Extensional Concepts in Intensional Type Theory, PhD thesis, University of Edinburgh, 1995,内涵/外延相等、quotient 与 extensional principles。
- The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study, 2013,Chs. 1–2,内涵恒等类型与高阶路径解释。