paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Failure of Normalization in Impredicative Type Theory with Proof-Irrelevant Propositional Equality

带证明无关命题等式的非直谓类型论中归一化失败
LMCS vol.Volume 16, Issue 22020匹配度 2/10 · 该论文属于纯类型论/证明论基础研究,讨论非直谓类型论中归一化失败,与用户核心关注点(LLM/Agent 与静态分析、形式化验证的交叉,浮点或贝叶斯程序分析)几乎没有直接交集;仅在最宽泛的 PL/形式化验证理论背景上略有相关性,且不涉及 LLM、Agent、工程落地或 benchmark。引用 17 inbox
Andreas Abel, Thierry Coquand
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:构造反例证明带证明无关命题等式的非直谓类型论不满足归一化,反驳 Werner 猜想。

本文研究非直谓命题宇宙与证明无关命题等式并存时类型论的归一化性质。作者将 Girard 针对带有类型相等判定器的 System F 的归一化反例加以改造,构造出在该类型论中破坏归一化的项,从而证明归一化不可用。该结果构成 Werner 在 LMCS 2008 中提出的归一化猜想的反例,说明在这些假设下不能期望所有项归约到范式,也揭示了证明无关等式与非直谓性组合的证明论强度。

问题
在同时具有非直谓命题宇宙和证明无关命题等式的类型论中,归一化是否成立?
方法
改造 Girard 关于带类型相等判定器的 System F 归一化反例,构造出反例项。
评估
以理论反例证明归一化失败,并反驳 Werner 的归一化猜想。
原文摘要(Abstract)

Normalization fails in type theory with an impredicative universe of propositions and a proof-irrelevant propositional equality. The counterexample to normalization is adapted from Girard's counterexample against normalization of System F equipped with a decider for type equality. It refutes Werner's normalization conjecture [LMCS 2008].

链接与引用

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

BibTeX
@article{AbelC20,
  title = {Failure of Normalization in Impredicative Type Theory with Proof-Irrelevant Propositional Equality},
  author = {Andreas Abel and Thierry Coquand},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 2},
  year = {2020},
  doi = {10.23638/lmcs-16(2:14)2020}
}