paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Ordinal Exponentiation in Homotopy Type Theory

同伦类型论中的序数指数运算
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 2/10 · 该论文是纯同伦类型论中的构造性序数指数研究并在 Agda 中形式化,属于证明工程/形式化验证的数学基础工作,与用户关注的静态分析、LLM/Agent 交叉、浮点或贝叶斯程序分析均无直接关系,仅与“形式化验证”这一大领域有微弱交集。引用 1 inbox
Tom De Jong, Nicolai Kraus, Fredrik Nordvall Forsberg, Chuangjie Xu
crossref: 2026-09-12

AI 速览

一句话:在同伦类型论中给出构造性序数指数的两种定义,证明其等价并形式化验证代数律与可判定性。

本文研究构造性序数指数运算。作者将序数视为集合上传递、外延且良基的序关系,在同伦类型论框架下提出两种看似不同的定义:一种抽象定义通过序数的上确界给出,仅由期望满足的等式驱动;另一种具体定义基于递减列表,可视为 Sierpiński 以有限支撑函数为基础的经典构造的构造性版本。作者证明这两种方法在问题有意义时等价,并利用该等价证明指数运算的代数律与可判定性性质。全部结果均在证明助手 Agda 中形式化,展示了同伦类型论与机器化证明在构造性序数理论中的应用。

问题
如何在构造性数学与同伦类型论中定义序数指数运算,并刻画其代数性质与可判定性?
方法
将序数表示为集合上的传递、外延、良基序,分别用上确界和递减列表给出抽象与具体的指数定义,并证明二者等价。
评估
在证明助手 Agda 中形式化全部定义、等价性证明以及代数律和可判定性结果。
原文摘要(Abstract)

We present two seemingly different definitions of constructive ordinal exponentiation, where an ordinal is taken to be a transitive, extensional, and wellfounded order on a set. The first definition is abstract, uses suprema of ordinals, and is solely motivated by the expected equations. The second is more concrete, based on decreasing lists, and can be seen as a constructive version of a classical construction by Sierpiński based on functions with finite support. We show that our two approaches are equivalent (whenever it makes sense to ask the question), and use this equivalence to prove algebraic laws and decidability properties of the exponential. Our work takes place in the framework of homotopy type theory, and all results are formalized in the proof assistant Agda.

链接与引用

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

BibTeX
@inproceedings{paperbot8653,
  title = {Ordinal Exponentiation in Homotopy Type Theory},
  author = {Tom De Jong and Nicolai Kraus and Fredrik Nordvall Forsberg and Chuangjie Xu},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00027}
}