Skip to content

外延类型论

Extensional type theory · ETT

通过相等反映把恒等证明纳入判断转换、以无痕改写换取更强外延识别的类型论变体。

条目类型
模型

形式陈述

一种典型的外延 Martin-Löf 类型论在依赖类型论上加入 equality reflection:

Γp:IdA(a,b)Γab:A.

于是对象层恒等证明可以扩张判断相等,conversion 随当前语境中的证明而变化。若 B 是类型族,p:a=Ab 使 B(a)B(b),故 u:B(a) 可直接作为 B(b) 使用,而不必在核心项中保留 transport。许多标准外延呈现还采用 identity proof irrelevance 或 equality uniqueness,使同型恒等证明判断相等,并由此验证 UIP/K;但这些规则应明确列出,不能仅从 reflection 一式偷偷推出每一种证明无关结论。

规则仍需覆盖形成、引入、消去和计算,且相等反映必须在替换下稳定:把 Γ 中的等式证明实例化后,相应的判断相等也随替换成立。问题在于 不再只由语法归约生成。要判断 ab,原则上可能需要发现某个 IdA(a,b) 居民;在足够强的理论里这包含一般定理证明,因而标准外延类型论没有仅靠规范化完成的可判定 type checking。

直觉

外延纪律把“已经证明相等”视作“此后内核可无痕当作相同”。这很符合普通数学书写:证明两个集合或函数相同后,读者往往不再标记每一次运输。依赖类型中的索引改写因而更顺滑,quotient 与函数外延原则也更接近日常推理。

代价是转换不再是一台只执行固定化简规则的计算器,而会读取证明环境。类型检查某个看似局部的应用,可能依赖远处是否能建立一个等式定理。外延性改善对象语言的等式体验,却把相当一部分证明搜索推入了 judgmental equality;这正是它与内涵类型论的工程分界,而不是价值高低之分。

例子与边界

仍取按首参数递归的加法,并由归纳得到

pn:IdN(n+0,n).

在含 pn 的语境中,reflection 给出 n+0n:N,同余进一步给出

Vec(A,n+0)Vec(A,n)type.

因此 v:Vec(A,n+0) 可通过 conversion 直接获得类型 Vec(A,n),生成的项仍是 v;内涵系统则通常留下显式 transport。若随后替换 n:=2,整条相等推导和 v 的类型同步实例化,说明 reflection 不是一次非类型化强制转换。

边界之一是运行语义:无痕转换不意味着 pn 被“执行并返回 true”,也不自动给未知函数等式一个计算规则。项的 β/ι 归约可能仍强正规化,但 judgmental equality 的可判定性已不再等同于求规范形。边界之二是 UIP/K:某些 ETT 把证明无关性内建为判断规则,另一些只加入 reflection;讨论路径唯一性时必须注明版本。边界之三是 extensional 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,内涵相等与外延模型的语义边界。
关系图谱10 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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