paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Idempotents in intensional type theory

内涵类型论中的幂等元
LMCS vol.Volume 12, Issue 32017匹配度 2/10 · 该论文是内涵类型论/同伦类型论中的纯理论工作,虽在 Coq 中形式化,但与用户关注的静态分析、LLM/Agent 交叉、浮点程序分析或贝叶斯程序分析均无直接关联;仅与形式化验证的底层理论有微弱联系。引用 11 inbox
Michael Shulman
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:研究内涵类型论中幂等元的分裂问题,给出可分裂的相干条件并构造不可分裂反例。

本文研究内涵 Martin-Löf 类型论中幂等元何时可分裂。作者证明:在命题截断与 Voevodsky 单值公理下,存在不可分裂的幂等元,因此纯 MLTT 不能证明所有幂等元都分裂;而仅假设函数外延性时,幂等元可分裂当且仅当其幂等性见证满足一个额外相干条件。证明受 Lurie 高阶范畴论启发。作者还证明幂等性见证可从分裂恢复,但该相干条件一般不能,并通过分裂部分相干幂等元类型上的幂等元构造“完全相干幂等元类型”。结果已在 Coq 中形式化验证。

问题
在内涵 Martin-Löf 类型论中,幂等元何时可以分裂?是否所有幂等元都可被证明分裂?
方法
利用命题截断与单值公理构造反例,在函数外延性下刻画分裂所需的额外相干条件,并借鉴 Lurie 的高阶范畴论结果;全部结论在 Coq 中形式化。
评估
通过 Coq 证明助手对主要定理与构造进行机器化验证。
原文摘要(Abstract)

We study idempotents in intensional Martin-L\"of type theory, and in particular the question of when and whether they split. We show that in the presence of propositional truncation and Voevodsky's univalence axiom, there exist idempotents that do not split; thus in plain MLTT not all idempotents can be proven to split. On the other hand, assuming only function extensionality, an idempotent can be split if and only if its witness of idempotency satisfies one extra coherence condition. Both proofs are inspired by parallel results of Lurie in higher category theory, showing that ideas from higher category theory and homotopy theory can have applications even in ordinary MLTT. Finally, we show that although the witness of idempotency can be recovered from a splitting, the one extra coherence condition cannot in general; and we construct "the type of fully coherent idempotents", by splitting an idempotent on the type of partially coherent ones. Our results have been formally verified in the proof assistant Coq.

链接与引用

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

BibTeX
@article{Shulman15,
  title = {Idempotents in intensional type theory},
  author = {Michael Shulman},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 12, Issue 3},
  year = {2017},
  doi = {10.2168/lmcs-12(3:9)2016}
}