paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Integers as a Higher Inductive Type

作为高阶归纳类型的整数
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 2/10 · 该论文是 HoTT 中高阶归纳类型表示整数的纯类型论基础工作,虽涉及形式化验证(cubical Agda),但完全不涉及 LLM/Agent 与静态分析/形式化验证的交叉,也与浮点或贝叶斯程序分析无关,与用户研究方向核心匹配度很低。引用 11 inbox
Thorsten Altenkirch, Luis Scoccola
crossref: 2026-09-12

AI 速览

一句话:在 HoTT 中用高阶归纳类型表示整数,避免集合截断并验证其与带符号自然数表示等价。

在 Homotopy Type Theory 中定义整数时,带符号自然数(余积)的归纳原理会导致大量情况分支,而集合商需要 set-truncation,所得递归原理只能定义到集合的函数。本文提出用高阶归纳类型表示整数,分别基于小宇宙(small universe)与 bi-invertible maps 两种构造,从而无需显式 set-truncation。作者证明这些类型与通常的余积表示等价,并说明该例子如何体现 HoTT 中 coherence 问题的处理。所有证明已在 cubical Agda 中机器验证,并讨论了由此引发的若干开放问题。

问题
如何在 HoTT 中定义整数,使其归纳/递归原理便于使用,同时避免集合商所需的 set-truncation 限制。
方法
使用基于小宇宙或 bi-invertible maps 的高阶归纳类型来刻画整数,并在 cubical Agda 中形式化证明。
评估
证明新表示与带符号自然数(余积)表示等价,并形式化验证全部证明;讨论开放问题。
原文摘要(Abstract)

We consider the problem of defining the integers in Homotopy Type Theory (HoTT). We can define the type of integers as signed natural numbers (i.e., using a coproduct), but its induction principle is very inconvenient to work with, since it leads to an explosion of cases. An alternative is to use set-quotients, but here we need to use set-truncation to avoid non-trivial higher equalities. This results in a recursion principle that only allows us to define function into sets (types satisfying UIP). In this paper we consider higher inductive types using either a small universe or bi-invertible maps. These types represent integers without explicit set-truncation that are equivalent to the usual coproduct representation. This is an interesting example since it shows how some coherence problems can be handled in HoTT. We discuss some open questions triggered by this work. The proofs have been formally verified using cubical Agda.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot5542,
  title = {The Integers as a Higher Inductive Type},
  author = {Thorsten Altenkirch and Luis Scoccola},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394760}
}