paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A program for the full axiom of choice

完全选择公理的一个程序
LMCS vol.Volume 17, Issue 32021匹配度 1/10 · 论文属于经典可实现性与证明提取,为完全选择公理给出显式程序,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关联,仅在形式化验证/PL 理论边缘相关。引用 2 inbox
Jean-Louis Krivine
crossref: 2026-09-10

AI 速览

一句话:在经典可实现性框架下,首次给出对应于完全选择公理(AC)的显式程序。

经典可实现性为 Curry-Howard 对应提供了一种框架,可将 Zermelo-Fraenkel 集合论中的每个证明关联到一个程序。然而,物理学、概率论和统计学等数学应用通常依赖分析学,即依赖选择(DC)甚至完全选择公理(AC),因此需要为这些公理找到显式程序。此前 DC 已有若干方案,例如称为 bar recursion 的 lambda 项或 LISP 的 quote 指令。本文在经典可实现性框架下构造出完全选择公理的首个程序,从而将 Curry-Howard 对应扩展到使用 AC 的经典数学证明,为从此类证明中提取计算内容提供了基础。摘要未报告实验评估,工作属于理论构造与证明。

问题
如何为 ZF 集合论中依赖完全选择公理(AC)的经典数学证明找到显式程序,是经典可实现性/Curry-Howard 对应需要解决的问题。
方法
在经典可实现性框架下构造一个实现完全选择公理的程序(项),沿用以 bar recursion 或 LISP quote 实现 DC 的思路,但首次处理 full AC。
评估
论文为理论工作,摘要未涉及实验或基准评估;其贡献体现为在经典可实现性框架中给出 AC 的显式程序构造。
原文摘要(Abstract)

The theory of classical realizability is a framework for the Curry-Howard correspondence which enables to associate a program with each proof in Zermelo-Fraenkel set theory. But, almost all the applications of mathematics in physics, probability, statistics, etc. use Analysis i.e. the axiom of dependent choice (DC) or even the (full) axiom of choice (AC). It is therefore important to find explicit programs for these axioms. Various solutions have been found for DC, for instance the lambda-term called "bar recursion" or the instruction "quote" of LISP. We present here the first program for AC.

链接与引用

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

BibTeX
@article{paperbot1282,
  title = {A program for the full axiom of choice},
  author = {Jean-Louis Krivine},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 3},
  year = {2021},
  doi = {10.46298/lmcs-17(3:21)2021}
}