Skip to content

内涵类型论

Intensional type theory · ITT

将判断相等限制为受控计算、把一般相等保留为恒等类型证据的依赖类型论取向。

条目类型
模型

形式陈述

本文所说内涵类型论是在Martin-Löf 依赖类型论核心上保持两层相等分离的系统。它既有判断

Γab:A,

也有对象类型 IdA(a,b);前者由 β/η(若采用)、归纳计算、展开和同余等明确规则生成,后者由 refl 与 J 消去。决定性的非规则是

Γp:IdA(a,b)Γab:A并不成立。

因此 conversion 只使用判断相等,而恒等证明要通过 rewrite、transport 或消去子显式影响依赖类型。这里“内涵”描述相等纪律,不等于一套唯一语法:理论可以选择函数 η、宇宙累积、归纳族或函数外延性公理。要从这套规则得到可判定类型检查,还需证明判断相等可判定,常见充分路线是强正规化、合流与可比较规范形;名称本身不是这项元定理。

同样,UIP/K 既不是内涵理论定义的一部分,也不由 J 自动产生。可以在集合式内涵理论中额外公设 UIP,亦可在同伦取向的内涵理论中保留非平凡高阶恒等。加入公理而不扩充判断计算时,转换算法可能保持原样,但 canonicity、程序抽取或某些规范形定理仍可能改变,必须逐一分析。

直觉

内涵纪律把“算出来一样”和“有理由相信相等”分开。前一种相等由内核机械执行,像把两个表达式归约到同一结果;后一种相等是一份可传入函数、可组合、可在族之间运输的数据。这样做牺牲了一些无痕改写的便利,却让类型检查不必在每次 conversion 时解决任意数学定理。

名称中的 intensional 还提示:两个对象即使在外部观察上无法区分,若没有对应的计算规则或恒等项,也不会自动被判断式识别。它不是“只看语法、完全不看意义”,因为正规化语义、逻辑关系和模型仍可证明丰富结果;它只是把哪些意义相等进入内核判断这件事控制得很严格。

例子与边界

设自然数加法按第一个参数递归。归约直接给出 0+nn,而对变量 nn+0 不再展开。通过归纳可以构造

pn:IdN(n+0,n).

v:Vec(A,n+0),内涵内核不能只因 pn 存在就用 conversion 接受 v:Vec(A,n);程序需形成

transportλk.Vec(A,k)(pn,v):Vec(A,n).

n 化为具体数值时,两端也许最终判断相等,运输随证明的具体形状继续计算;当 pn 保持抽象时,cast 可能留在规范形中。这份显式痕迹正是内涵与外延类型论在使用体验上的区别。

边界不能简化成“内涵必然可判定、外延必然不可执行”。带无约束递归或不可判定重写的内涵理论照样会失去转换可判定性;带额外公理但无计算规则的核心也可能保留 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,内涵恒等类型与高阶路径解释。
关系图谱10 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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