paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the computational content of Zorn's lemma

论 Zorn 引理的计算内容
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 论文属于证明论与形式语义,研究 Zorn 引理的计算解释和非良基偏序递归,与用户关注的 LLM/Agent 与静态分析、浮点程序分析、贝叶斯程序分析等方向没有直接交集;仅在形式验证的理论基础层面有很弱的关联。引用 3 inbox
Thomas Powell
crossref: 2026-09-12

AI 速览

一句话:通过Gödel函数解释为有限类型算术中的Zorn引理抽象实例给出计算解释,并引入非良基偏序上的新递归形式。

本文研究如何为在有限类型算术中表述为良基性原理的 Zorn 引理抽象实例赋予计算内容。作者采用 Gödel 函数解释(dialectica 解释)来提取 realizer,并为此引入一种在非良基偏序上的新型递归。该递归在全连续泛函模型中的存在性通过域论技术加以证明。作为主要结果的应用,作者进一步得到序列字典序上开放归纳(open induction)的函数解释 realizer。工作属于证明论与语义学的理论贡献,不涉及实现或实验评估。

问题
如何为以良基性原理表述的 Zorn 引理抽象实例提供计算解释,并提取其函数解释的 realizer。
方法
使用 Gödel 函数解释,引入非良基偏序上的新递归形式,并借助域论在全连续泛函模型中证明该递归存在。
评估
以构造性证明和语义模型论证为主;并将结果应用于序列字典序上的开放归纳,导出其 realizer。
原文摘要(Abstract)

We give a computational interpretation to an abstract instance of Zorn's lemma formulated as a wellfoundedness principle in the language of arithmetic in all finite types. This is achieved through Gödel's functional interpretation, and requires the introduction of a novel form of recursion over non-wellfounded partial orders whose existence in the model of total continuous functionals is proven using domain theoretic techniques. We show that a realizer for the functional interpretation of open induction over the lexicographic ordering on sequences follows as a simple application of our main results.

链接与引用

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

BibTeX
@inproceedings{paperbot5492,
  title = {On the computational content of Zorn's lemma},
  author = {Thomas Powell},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394745}
}