paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Gödel-McKinsey-Tarski and Blok-Esakia for Heyting-Lewis Implication

Heyting-Lewis 蕴涵的 Gödel-McKinsey-Tarski 与 Blok-Esakia
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 该论文属于纯数理逻辑与形式语义研究,聚焦 Heyting-Lewis 逻辑的对偶理论、Blok-Esakia 定理与可判定性,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户当前研究画像几乎无直接交集。引用 0 inbox
Jim de Groot, Tadeusz Litak, Dirk Pattinson
crossref: 2026-09-12

AI 速览

一句话:为 Heyting-Lewis 逻辑建立描述性框架对偶,并借经典模态翻译证明 Blok-Esakia 定理与可判定性。

Heyting-Lewis 逻辑在直觉主义命题逻辑上加入严格蕴涵连接词,其变体出现在 Haskell 风格箭头、Heyting 算术保持性逻辑、守卫(余)递归证明论以及直觉主义认知逻辑中。论文利用带二元关系的直觉主义 Kripke 框架解释严格蕴涵,定义描述性框架(Esakia 空间的推广),并建立代数语义与框架语义之间的范畴对偶。作者还改写 Wolter 与 Zakharyaschev 的变换,将 Heyting-Lewis 逻辑翻译为带两个一元算子的经典模态逻辑,由此证明 Blok-Esakia 定理,并导出已知和新的典范性、对应性定理,以及一大类 Heyting-Lewis 逻辑的有限模型性质与可判定性。

问题
如何为 Heyting-Lewis 逻辑给出统一的框架与代数语义,并系统迁移经典模态逻辑中的 Blok-Esakia、典范性和对应性结果。
方法
定义描述性框架与范畴对偶,并经由 Wolter-Zakharyaschev 式翻译将其归约到带两个一元算子的经典模态逻辑。
评估
以理论证明为主:建立对偶与 Blok-Esakia 定理,并据此证明有限模型性质和可判定性等元定理。
原文摘要(Abstract)

Heyting-Lewis Logic is the extension of intuitionistic propositional logic with a strict implication connective that satisfies the constructive counterparts of axioms for strict implication provable in classical modal logics. Variants of this logic are surprisingly widespread: they appear as Curry-Howard correspondents of (simple type theory extended with) Haskell-style arrows, in preservativity logic of Heyting arithmetic, in the proof theory of guarded (co)recursion, and in the generalization of intuitionistic epistemic logic.Heyting-Lewis Logic can be interpreted in intuitionistic Kripke frames extended with a binary relation to account for strict implication. We use this semantics to define descriptive frames (generalisations of Esakia spaces), and establish a categorical duality between the algebraic interpretation and the frame semantics. We then adapt a transformation by Wolter and Zakharyaschev to translate Heyting-Lewis Logic to classical modal logic with two unary operators. This allows us to prove a Blok-Esakia theorem that we then use to obtain both known and new canonicity and correspondence theorems, and the finite model property and decidability for a large family of Heyting-Lewis logics.

链接与引用

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

BibTeX
@inproceedings{paperbot6202,
  title = {Gödel-McKinsey-Tarski and Blok-Esakia for Heyting-Lewis Implication},
  author = {Jim de Groot and Tadeusz Litak and Dirk Pattinson},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470508}
}