Skip to content

高阶归纳类型

Higher inductive type · HIT

同时由点构造子、路径构造子及更高相干构造子生成数据与恒等结构的类型形成机制。

条目类型
定义

形式陈述

高阶归纳类型(HIT)扩展普通归纳类型的构造签名:除点构造子产生类型居民外,还允许路径构造子产生恒等类型居民,乃至以已有路径为端点的二维及更高构造子。圆周的典型声明为

base:S1,loop:IdS1(base,base).

其非依赖递归原理说:给定 B:Ub:B:b=Bb,存在 f:S1B,满足

f(base)b,apf(loop)=.

其依赖归纳原理更精确。给定 P:S1Ub:P(base)

:transportP(loop,b)=P(base)b,

得到 s:Π(x:S1).P(x);点计算为 s(base)b,路径上的 dependent action 与 相符。在 HoTT Book 的公理式口径,点构造子的 β-rule 通常取 judgmental,路径构造子的 computation 通常只给命题式路径。ap、transport 与 dependent action 的定义最终使用路径归纳,但 HIT 的新路径构造子不是 J 的推论。

直觉

普通归纳声明规定“有哪些点”;HIT 还能在生成点的同时规定“哪些点由指定路径粘在一起”,并继续规定路径之间的面或更高相干。圆周不是先生成一个点再从外部证明某条自等式,而是把基本回路列为生成结构。消去一个 HIT 时,目标不仅要接收每个点构造子,还要证明所给分支尊重所有粘合路径。

这使 quotient、截断和拓扑空间获得统一的内部描述。商类型可用点构造子注入元素,再用路径构造子识别关系中的两点;集合截断还要加入更高构造,压平任意平行路径。构造签名决定最小自由对象,归纳原理则表达从该自由对象映出时必须保存的全部结构。

例子与边界

用圆周递归原理定义二次绕圈映射 d2:S1S1。点数据取 d2(base)=base,路径数据取回路连接

looploop:base=S1base.

于是递归原理给出 d2,并有

apd2(loop)=looploop.

这不是把输入点复制两次;圆周只有一个生成点,映射的“次数”完全记录在它对生成路径的作用上。若只给 d2(base) 而漏掉回路证据,定义不完整,因为目标点可带许多不同自路径。

边界首先是 computation strength。公理式 HIT 的路径 β-law若只有 propositional equality,包含该消去子的闭项不一定按判断归约暴露预期路径;模型一致性也不自动带来严格 canonicity。立方类型论能为圆周、悬挂、pushout 等许多 HIT 提供计算规则,但需要 composition/coherence machinery,不能据此断言任意写下的高阶构造签名都被实现。边界其次是严格正性与相干:负位置递归、端点引用尚未合法生成的数据或缺失高维 coherence,可能使形成规则不良。

推论与应用

HIT 可内部构造圆周、球面、悬挂、pushout、quotient 与 truncation,并通过其归纳原理推导同伦群、encode–decode 证明和结构同一原则。程序层面,它为“数据加方程”提供高阶版本:计算不仅按点构造器分支,还要证明函数尊重生成等式,避免把 quotient representative 的选择泄露到结果。

HIT 与单价性经常共同出现,却没有 special-case 关系。单价性描述宇宙中等价与路径的联系;HIT 描述由点和路径自由生成新类型。可以研究带 HIT 而不公设 univalence 的理论,也可以先讨论单价宇宙而不加入一般 HIT。任何实现都应分别列出支持哪些构造签名、点/路径 computation 是判断式还是命题式,以及相应 normalization/canonicity 已证明到何种范围。

参考资料
  • The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study, 2013,Ch. 6,circles、suspensions、pushouts 与 truncations。
  • Peter LeFanu Lumsdaine and Michael Shulman, “Semantics of Higher Inductive Types,” Mathematical Proceedings of the Cambridge Philosophical Society 169(1), 2020, pp. 159–208,HIT signatures、models 与 elimination semantics。
  • Cyril Cohen, Thierry Coquand, Simon Huber, and Anders Mörtberg, “Cubical Type Theory: A Constructive Interpretation of the Univalence Axiom,” LIPIcs TYPES 2015 69, 2018, Article 5,cubical computation 与若干高阶归纳构造的背景。
关系图谱9 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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