💻 computer science

Interpolation in Proof Theory

本章全面概述了利用马哈拉（Maehara）方法和皮茨（Pitts）方法等证明论技术，在经典、直觉、模态及次结构逻辑中建立克雷格插值与均匀插值性质的构造性、模块化及语法驱动方法，并揭示了这些性质与通用证明理论框架下良好证明系统构建之间的深刻联系。

原作者： Iris van der Giessen, Raheleh Jalali, Roman Kuznets

发布于 2026-02-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Iris van der Giessen, Raheleh Jalali, Roman Kuznets

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文就像是一本**“逻辑世界的建筑蓝图与施工手册”**。

想象一下，逻辑学家们正在建造一座座宏伟的“逻辑大厦”（比如经典逻辑、直觉逻辑、模态逻辑等）。在这些大厦里，有一个非常重要的特性叫做**“插值性”（Interpolation）**。

1. 什么是“插值”？（核心概念）

让我们用一个**“翻译官”**的比喻来理解：

假设你有两个朋友，阿明（代表前提 $\phi$ ）和阿强（代表结论 $\psi$ ）。

阿明说了一堆话，阿强听懂了，并且说：“既然你这么说，那我也能得出那个结论。”
但是，阿明和阿强之间有很多私密的暗号（特定的变量），阿强并不想把这些暗号透露给外人，或者阿明不想让阿强知道某些细节。
插值就是要在他们中间找一个**“中间人”（插值公式 $\theta$ $θ$ ）**。
- 这个中间人只说阿明和阿强共同知道的事情（不包含私密的暗号）。
- 阿明对中间人说：“我同意你的话。”
- 中间人对阿强说：“基于我的理解，你的结论也是成立的。”
- 这样，阿明和阿强就通过一个**“干净、无秘密”**的中间人完成了沟通。

这篇论文的核心任务就是：如何设计一套“施工规则”，确保在任何逻辑大厦里，我们都能自动找到这个完美的“中间人”。

2. 两种主要的“施工方法”

论文主要介绍了两种经典的“施工方法”，用来证明这种“中间人”一定存在，并且能把它造出来。

方法一：Maehara 的“分治法”（像切蛋糕）

原理：想象你在切一个证明过程的蛋糕。Maehara 的方法就像是在蛋糕中间切一刀，把证明过程分成“左边”和“右边”。
操作：
- 左边是阿明的部分，右边是阿强的部分。
- 算法沿着证明的每一步（就像沿着蛋糕的纹理切下去），在每一层都提取出一点“公共信息”。
- 最后，把这些公共信息拼起来，就得到了那个“中间人”。
优点：非常灵活，适用于很多种逻辑（经典、直觉、模态等）。它是构造性的，意味着它不仅能告诉你“中间人存在”，还能直接算出中间人是谁。
缺点：有时候，如果证明过程太复杂（比如需要用到“切割”规则），这个方法可能会漏掉一些可能的“中间人”，或者算出来的中间人不够完美（比如没能保留某些变量的正负极性）。

方法二：Pitts 的“逆向搜索法”（像寻宝游戏）

原理：这种方法更高级，专门用于解决**“均匀插值”**（Uniform Interpolation）。
什么是均匀插值？ 想象阿明说了一句话，不管阿强后面接什么话，只要这句话是阿明说的，中间人就能搞定。这就像是一个**“万能钥匙”**，不需要针对每一个具体的结论重新找中间人。
操作：Pitts 的方法不是顺着证明走，而是倒着走。它像是一个寻宝游戏，从结论出发，反向搜索，把不需要的变量（秘密）一点点“擦除”掉，直到只剩下最核心的、通用的部分。
应用：这种方法在直觉逻辑中非常成功，甚至被写进了计算机程序（Coq），可以自动算出这个“万能钥匙”。

3. 当普通工具不够用时：升级“施工设备”

论文还讨论了一个有趣的问题：有时候，普通的“切蛋糕”工具（标准序列演算）不够用了，因为有些逻辑大厦结构太复杂，切不开，或者切了之后找不到完美的中间人。

这时候，建筑师们发明了**“升级版工具”**：

带标签的序列（Labelled Sequents）：
- 比喻：普通的序列就像是一张白纸，上面写着公式。带标签的序列就像是在公式旁边贴上了**“世界标签”**（比如“世界 A"、“世界 B"）。
- 作用：在模态逻辑（涉及“可能”、“必然”的逻辑）中，不同的世界有不同的规则。贴上标签就像是在地图上标记了不同的地点。这样，插值算法就能更精确地知道哪些信息是“本地”的，哪些是“全球”通用的，从而算出更精准的中间人。
超序列（Hypersequents）和嵌套序列（Nested Sequents）：
- 比喻：这就像是从“单张纸”升级到了“活页夹”或者“俄罗斯套娃”。
- 作用：当逻辑结构像树一样层层嵌套时，普通的序列就乱了。这些新结构允许我们在不同的层级上同时处理信息，就像在多层建筑里同时施工，互不干扰。

关键发现：使用这些“升级版工具”，有时候能解决普通工具解决不了的问题。比如，对于某些复杂的模态逻辑（如 S5），普通方法只能算出普通的中间人，但用“带标签”的方法，不仅能算出中间人，还能算出**“带极性”的中间人**（Lyndon 插值），这就像不仅找到了中间人，还确认了中间人的性别和性格完全符合要求。

4. 通用证明理论：寻找“好规则”的指南针

论文的最后部分（第 4 章）把视野拔高了，进入了**“通用证明理论”**的领域。

核心思想：我们能不能找到一套**“好规则”**的标准？
比喻：就像建筑规范一样。如果一套施工规则（序列演算）符合“半分析性”（Semi-analytic）的标准（即规则清晰、不随意引入新变量、结构良好），那么这座逻辑大厦一定拥有“插值性”。
反向思考：如果一座逻辑大厦没有“插值性”，那就说明它不可能有一套符合“好规则”标准的施工图纸。
意义：这就像是一个过滤器。它告诉我们，大多数复杂的逻辑（比如某些中间逻辑或模糊逻辑）之所以很难处理，是因为它们天生就不具备“好规则”的结构。这解释了为什么有些逻辑很难找到完美的“中间人”。

总结

这篇论文就像是一本**“逻辑插值大师指南”**：

教我们怎么找“中间人”：介绍了 Maehara（切蛋糕）和 Pitts（逆向搜索）两大经典算法。
升级工具箱：展示了当普通工具不够用时，如何使用“带标签”、“超序列”等高级工具来应对更复杂的逻辑大厦。
制定建筑规范：通过“通用证明理论”，告诉我们什么样的逻辑大厦天生就适合找“中间人”，什么样的则注定困难重重。

一句话概括：它提供了一套系统的方法，让我们不仅能证明“中间人”存在，还能像搭积木一样，一步步把“中间人”搭建出来，无论这座逻辑大厦是简单的平房还是复杂的摩天大楼。

这篇论文《证明论中的插值》（Interpolation in Proof Theory）由 Iris van der Giessen、Raheleh Jalali 和 Roman Kuznets 撰写，旨在全面概述利用证明论方法（特别是基于 sequent 演算及其推广形式）为各类逻辑（包括经典逻辑、直觉主义逻辑、模态逻辑和亚结构逻辑）建立插值性质的技术。

以下是该论文的详细技术总结：

1. 研究问题 (Problem)

插值性质（Interpolation Properties, IPs）是逻辑系统中的核心元性质，主要包括：

克雷格插值性质 (CIP)：如果 $\vdash \phi \to \psi$ ，则存在一个插值公式 $\theta$ ，其变量仅出现在 $\phi$ 和 $\psi$ 的公共部分，且满足 $\vdash \phi \to \theta$ 和 $\vdash \theta \to \psi$ 。
林登插值性质 (LIP)：CIP 的加强版，要求插值公式 $\theta$ 中命题变量的极性（正/负）必须与 $\phi$ 和 $\psi$ 中的极性一致。
均匀插值性质 (UIP)：更强的性质，要求插值公式仅依赖于前提（或结论）的一部分，能够解释命题量词。

核心挑战：

许多逻辑系统（特别是中间逻辑和模态逻辑）缺乏 CIP 或 UIP。
传统的语义方法（如模型论）虽然能证明存在性，但通常是构造性的缺失，无法提供具体的插值公式。
现有的证明论方法（如 Maehara 方法）在处理某些复杂逻辑（如 S5、非正规模态逻辑）或需要证明 LIP 时存在局限性（例如，某些带有割规则的演算无法保持极性）。
需要一种系统化的框架，将插值性质的存在性与证明系统的结构特征联系起来。

2. 方法论 (Methodology)

论文主要围绕三种核心证明论技术展开，并探讨了它们在通用证明论（Universal Proof Theory）框架下的应用：

A. 基于标准 Sequent 演算的方法

Maehara 方法 (针对 CIP/LIP)：
- 通过分裂 sequent (Split Sequent) $\Gamma; \Gamma' \Rightarrow \Delta; \Delta'$ 将证明树中的公式来源（来自 $\phi$ 或 $\psi$ ）区分开。
- 通过归纳法在证明树的叶节点和规则步骤上构造插值公式。
- 局限性：对于某些逻辑（如 GL），标准的 cut-free sequent 演算无法直接证明 LIP；且该方法通常依赖于 cut-free 系统，而某些逻辑（如 S5）缺乏 cut-free 的普通 sequent 演算。
Pitts 方法 (针对 UIP)：
- 针对直觉主义逻辑 IPC，利用强终止 (Strongly Terminating) 的 sequent 演算。
- 通过证明搜索 (Proof Search) 而非给定的证明，递归地构造均匀插值算子（如 $\forall p \phi$ ）。
- 该方法已被形式化并用于自动计算均匀插值。

B. 受限割规则 (Restricted Cuts)

为了处理缺乏 cut-free 演算的逻辑（如 S5），论文引入了分析割 (Analytic Cut)、半分析割 (Semi-analytic Cut) 和单色割 (Monochromatic Cut)。
这些规则限制了割公式的变量来源，使得 Maehara 方法在包含这些规则的非 cut-free 演算中依然有效。

C. 通用证明论 (Universal Proof Theory)

引入了半分析规则 (Semi-analytic Rules) 和聚焦公理 (Focused Axioms) 的概念。
核心定理：如果一个逻辑拥有一个（完全终止的）半分析演算，则该逻辑具有 CIP（或 UIP）。
负面结果：利用插值性质的稀缺性，证明了大多数中间逻辑和模态逻辑不存在这样的“良好”证明系统（即不存在半分析演算）。

D. 广义 Sequent 演算 (Generalizations of Sequent Calculi)

针对普通 sequent 演算无法处理 LIP 或缺乏 cut-free 系统的逻辑，论文转向了更强大的结构：
- 标记 Sequent (Labelled Sequents)：引入 Kripke 语义中的世界标签（如 $i:\phi$ ）和关系原子（如 $iRj$）。插值对象从公式扩展为多公式 (Multiformulas)（即带标签的公式的布尔组合）。
- 超 Sequent (Hypersequents) 和 嵌套 Sequent (Nested Sequents)：通过结构连接词或树状结构模拟 Kripke 框架。
逆向工程策略：通过分析规则的形状（局部、合取、析取、 $\square$ -型、 $\diamond$ -型），系统性地构造插值变换规则。

3. 主要贡献与结果 (Key Contributions & Results)

理论贡献

系统化构造算法：提供了一套通用的“手册”，指导如何根据证明系统的规则形状构造插值公式。对于标记 sequent，定义了处理新标签（fresh labels）的复杂变换（如 $\square$ -like 和 $\diamond$ -like 变换）。
通用证明论框架：建立了逻辑性质（CIP/UIP）与证明系统结构（半分析性）之间的双向联系。
- 正面：若存在半分析演算 $\to$ 存在插值。
- 负面：若不存在插值 $\to$ 不存在半分析演算。这解释了为什么许多逻辑（如模糊逻辑、相关逻辑的某些扩展）没有良好的证明系统。
LIP 的突破：证明了标记 sequent 演算在证明林登插值（LIP）方面比普通 sequent 演算更具优势。例如，对于模态逻辑 S5，普通演算配合分析割只能证明 CIP，而标记演算可以直接证明 LIP。

具体逻辑结果

中间逻辑：确认了只有 7 个一致的中间逻辑具有 CIP/UIP，并证明了其他大多数中间逻辑不存在半分析演算。
模态逻辑：
- 证明了 K, T, D, K4, S4, GL, S5 等逻辑的 CIP 和 LIP。
- 利用标记演算证明了 S5 的 LIP。
- 证明了非正规模态逻辑（如 E, M, K）和条件逻辑的 ULIP（均匀林登插值）。
- 指出了 CKCEM 和 CKCEMID 具有 UIP 但不具有 ULIP，因此不存在完全终止的半分析演算。
亚结构与线性逻辑：将结果推广到线性逻辑（MALL, ILL 等）和模糊逻辑（MTL, BL 等），揭示了哪些逻辑具有插值性质，哪些没有。

4. 意义 (Significance)

构造性与算法性：与语义证明不同，这些方法提供了构造性的算法，能够实际计算出插值公式。这对于自动推理、程序验证（如 Horn 子句提取）和知识表示至关重要。
证明系统的分类学：通过插值性质作为“过滤器”，为逻辑系统的分类提供了强有力的工具。它揭示了“良好”的证明系统（如 cut-free, 半分析）是稀缺的，大多数逻辑无法拥有此类系统。
方法论的统一：论文成功地将 Maehara 方法、Pitts 方法以及现代标记/嵌套/超 sequent 技术统一在一个框架下。特别是展示了如何通过“逆向工程”规则形状来设计插值变换，为研究新逻辑的插值性质提供了可操作的指南。
解决长期难题：解决了某些逻辑（如 S5 的 LIP）在普通 sequent 演算中难以证明的问题，展示了广义 sequent 演算（标记、嵌套等）在证明论中的优越性。

总结

该论文不仅是对插值证明论技术的全面综述，更是一个方法论的指南。它强调了证明系统结构（如规则是否半分析、是否强终止、是否使用标记）直接决定了逻辑系统是否具备插值性质。通过引入标记 sequent 和通用证明论框架，作者不仅扩展了已知具有插值性质的逻辑范围，还深刻揭示了缺乏这些性质的逻辑在证明论层面的根本原因（即缺乏“良好”的证明系统）。