paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Path Spaces of Higher Inductive Types in Homotopy Type Theory

同伦类型论中高阶归纳类型的路径空间
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 1/10 · 该论文是纯同伦类型论与高阶归纳类型路径空间的理论结果,并在 Lean 中形式化,属于类型论/证明工程,不涉及静态分析、ML/Agentic 程序、LLM 改进形式化验证、浮点程序分析或贝叶斯程序分析。引用 2 inbox
Nicolai Kraus, Jakob von Raumer
crossref: 2026-09-12

AI 速览

一句话:证明高阶归纳类型等式类型的通用路径空间定理,并在 Lean 中形式化。

在 Homotopy Type Theory 中,等式类型的刻画是核心问题,但通常较为困难,已有 encode-decode 等多种方法。本文针对 coequalizer 与 pushout 的等式类型证明了一个类似归纳原则的定理,且不对截断层级施加限制。该结果使得可以直接推理某些等式类型,并消除辅助构造以简化既有证明。作者用它给出了圆周基本群计算的极短论证,证明了 pushout 保持 embedding,并提示了高阶 Seifert–van Kampen 定理:经 set-truncation 后可退化为标准版本。主要技术结果已在证明助手 Lean 中形式化。

问题
同伦类型论中刻画高阶归纳类型(如 coequalizer、pushout)的等式类型/路径空间通常依赖技巧性方法,缺少通用且不受截断层级限制的推理原则。
方法
证明关于 coequalizer 和 pushout 的等式类型定理,形式类似归纳原则,可支持对路径空间的直接推理;并在 Lean 中形式化主要技术结果。
评估
通过重新导出圆周基本群计算的简短证明、pushout 保持 embedding 的事实,以及高阶 Seifert–van Kampen 定理与其 set-truncation 版本,展示该定理的实用性与简化能力。
原文摘要(Abstract)

The study of equality types is central to homotopy type theory. Characterizing these types is often tricky, and various strategies, such as the encode-decode method, have been developed. We prove a theorem about equality types of coequalizers and pushouts, reminiscent of an induction principle and without any restrictions on the truncation levels. This result makes it possible to reason directly about certain equality types and to streamline existing proofs by eliminating the necessity of auxiliary constructions. To demonstrate this, we give a very short argument for the calculation of the fundamental group of the circle (Licata and Shulman [1]), and for the fact that pushouts preserve embeddings. Further, our development suggests a higher version of the Seifert-van Kampen theorem, and the set-truncation operator maps it to the standard Seifert-van Kampen theorem (due to Favonia and Shulman [2]). We provide a formalization of the main technical results in the proof assistant Lean.

链接与引用

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

BibTeX
@inproceedings{paperbot4990,
  title = {Path Spaces of Higher Inductive Types in Homotopy Type Theory},
  author = {Nicolai Kraus and Jakob von Raumer},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785661}
}