paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Converse extensionality and apartness

逆外延性与分离性
LMCS vol.Volume 18, Issue 42022匹配度 1/10 · 论文研究构造性数学与范畴论语义,围绕逆外延性和分离关系,属于纯形式语义理论;与用户关注的 LLM/Agent 静态分析、浮点程序分析、贝叶斯程序分析及 AI↔PL 交叉方向几乎没有交集。引用 1 inbox
Benno van den Berg, Robert Passmann
crossref: 2026-09-10

AI 速览

一句话:利用分离关系为逆外延性提供计算解释,并构造装配范畴模型。

本文研究强外延性形式——逆外延性(converse extensionality)的计算解释。该原理来自外延性公理的 Dialectica 解释,最早由 Howard 研究。为解释它,作者重新审视 Brouwer 的分离关系(apartness),即构造性不等式的强形式。方法上,他们给出一个范畴构造,为每个类型组合代数配备分离关系;并利用函数不仅保持相等而且还反射分离这一性质,证明由此得到的装配(assemblies)范畴模型满足逆外延性原理。这一结果为强外延性提供了计算语义,并展示了分离关系在类型论与范畴语义中的作用。

问题
如何为一种强外延性形式——逆外延性——提供计算解释?该原理来自外延性公理的 Dialectica 解释,最早由 Howard 研究。
方法
通过范畴构造为每个类型组合代数赋予 Brouwer 分离关系,并利用函数反射分离且保持相等的性质,构造装配范畴。
评估
作者在范畴语义框架下证明所得装配范畴模型满足逆外延性原理;本文为理论工作,不涉及经验性评估。
原文摘要(Abstract)

In this paper we try to find a computational interpretation for a strong form of extensionality, which we call "converse extensionality". Converse extensionality principles, which arise as the Dialectica interpretation of the axiom of extensionality, were first studied by Howard. In order to give a computational interpretation to these principles, we reconsider Brouwer's apartness relation, a strong constructive form of inequality. Formally, we provide a categorical construction to endow every typed combinatory algebra with an apartness relation. We then exploit that functions reflect apartness, in addition to preserving equality, to prove that the resulting categories of assemblies model a converse extensionality principle.

链接与引用

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

BibTeX
@article{paperbot1636,
  title = {Converse extensionality and apartness},
  author = {Benno van den Berg and Robert Passmann},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 4},
  year = {2022},
  doi = {10.46298/lmcs-18(4:13)2022}
}