paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Internal ∞-Categorical Models of Dependent Type Theory : Towards 2LTT Eating HoTT

依赖类型理论的内部 ∞-范畴模型:迈向 2LTT 吞食 HoTT
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 该论文属于纯类型论/HoTT 与高阶范畴形式语义,讨论内部依赖类型论模型,与用户关注的 PL+AI、静态分析、浮点/贝叶斯程序分析以及 LLM/Agent 交叉方向均无直接关联,仅在最宽泛的形式化验证基础层面有非常微弱的联系。引用 4 inbox
Nicolai Kraus
crossref: 2026-09-12

AI 速览

一句话:提出 ∞-CwF,在二层级类型论中为无 UIP 的 HoTT 提供内部依赖类型论模型。

本文研究依赖类型理论能否形式化自身(“类型理论吞食自身”),指出在缺少 UIP 的同伦类型论(HoTT)中,传统基于 1-范畴(如 CwF)的模型不足以刻画语法。作者引入 ∞-范畴 with families(∞-CwF),基于半 Segal 类型并给出新的同一性替换构造,支持 univalent 与非 univalent 变体;为避免半单纯类型构造这一未解决问题,定义在二层级类型论(2LTT)中表述。作者展示类型论宇宙与内部化的集合层语法可构成模型,但后者是否初始仍为猜想;还讨论了无 UIP 时 1-范畴的局限及内部高维范畴的困难与途径。

问题
在无 UIP 的同伦类型论中,依赖类型理论能否作为自身元语言进行内部形式化;传统 1-范畴模型(如 CwF)不足以刻画此类语法。
方法
提出 ∞-CwF,基于半 Segal 类型与新的同一性替换构造,并在二层级类型论(2LTT)中给出定义以绕开半单纯类型构造问题。
评估
以类型论宇宙和内部化集合层语法为模型实例进行理论验证;该语法模型的初始性仍为猜想,未报告实验评估。
原文摘要(Abstract)

Using dependent type theory to formalise the syntax of dependent type theory is a very active topic of study and goes under the name of "type theory eating itself" or "type theory in type theory." Most approaches are at least loosely based on Dybjer's categories with families (CwF's) and come with a type Con of contexts, a type family Ty indexed over it modelling types, and so on. This works well in versions of type theory where the principle of unique identity proofs (UIP) holds. In homotopy type theory (HoTT) however, it is a long-standing and frequently discussed open problem whether the type theory "eats itself" and can serve as its own interpreter. The fundamental underlying difficulty seems to be that categories are not suitable to capture a type theory in the absence of UIP. In this paper, we develop a notion of ∞-categories with families (∞-CwF's). The approach to higher categories used relies on the previously suggested semi-Segal types, with a new construction of identity substitutions that allow for both univalent and non-univalent variations. The type-theoretic universe as well as the internalised (set-level) syntax are models, although it remains a conjecture that the latter is initial. To circumvent the known unsolved problem of constructing semisimplicial types, the definition is presented in two-level type theory (2LTT). Apart from introducing ∞-CwF's, the paper explains the shortcomings of 1-categories in type theory without UIP as well as the difficulties of and approaches to internal higher-dimensional categories.

链接与引用

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

BibTeX
@inproceedings{paperbot6161,
  title = {Internal ∞-Categorical Models of Dependent Type Theory : Towards 2LTT Eating HoTT},
  author = {Nicolai Kraus},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470667}
}