将一阶模态逻辑嵌入Isabelle/HOL,实现深层与浅层形式的自动保真验证。
First-Order Modal Logic in HOL: Deep and Shallow Embeddings with Automated Faithfulness (Extended Preprint)

- 提出三种嵌入方式:深层、重型浅层与轻量浅层,支持一阶模态逻辑。
- 证明最小浅层嵌入在可数域下等价于深层有效性,解决不可数个体域的映射问题。
- 构建完整变量替换机制,首次实现一阶模态逻辑的自动化保真证明。
我们在Isabelle/HOL中将先前仅限命题逻辑的深-浅嵌入方法扩展至具有常量域克里普克语义的一阶模态逻辑(FML)。并行提供三种将FML嵌入经典高阶逻辑(HOL)的方法:深层嵌入、重型最大浅层嵌入和轻量最小浅层嵌入。最小浅层嵌入以Isabelle/HOL本地形式定义,参数包括可达关系、世界索引解释、世界集合及变量赋值;其结构支持全局保真定理,即对所有最小浅层解释进行量化时,恰好恢复深层有效性。核心技术贡献是针对常量域克里普克语义下的(可数)向下洛文海姆-斯科莱姆定理的形式化,该定理支撑了深-浅嵌入间保真证明的自动化。通过在最小浅层本地扩展中应用此定理,解决了不可数个体域下的满射难题——因变量赋值域为可数集V = nat,无法覆盖全体个体,从而实现了全个体域上的保真性。由于前人工作仅处理命题片段,本文首次建立一阶量词所需替换机制:自由/约束变量谓词、新变量函数、避免捕获的替换、字母重命名、可替换性谓词、替换引理及基于大小的归纳原理。
原文摘要 · Abstract (English)
We extend, in Isabelle/HOL, the deep-and-shallow embedding methodology of our prior work from propositional to first-order modal logic (FML) with constant-domain Kripke semantics. Three embeddings of FML into classical higher-order logic (HOL) are provided side by side: a deep embedding, a heavyweight maximal-shallow embedding, and a lightweight minimal-shallow embedding. The minimal-shallow embedding is presented as an Isabelle/HOL locale, parametrised by an accessibility relation, a world-indexed interpretation, a universe of worlds, and a variable assignment; the locale form admits a global faithfulness theorem, stating that quantifying over all minimal-shallow interpretations recovers exactly deep validity. A central technical contribution is a mechanisation, for FML under constant-domain Kripke semantics, of the (countable) downward Löwenheim-Skolem theorem, which underpins the automation of our faithfulness proof between the deep and minimal-shallow embeddings. Deploying it inside an extension of the minimal-shallow locale resolves the surjectivity problem that arises against an uncountable domain of individuals -- where the locale's variable assignment, having countable domain V = nat, cannot be surjective onto the domain -- and thereby yields faithfulness over the full domain. Since prior work treats only the propositional fragment, we develop here the substitution machinery (free/bound-variable predicates, the fresh-variable function, capture-avoiding substitution, alphabetic renaming, the substitutability predicate, the substitution lemma, and size-based induction principles) needed for the first-order quantifiers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。