💻 computer science

Interpolation in Proof Theory

This chapter offers a comprehensive overview of constructive, syntax-driven proof-theoretic methods, specifically Maehara's and Pitts' techniques, for establishing Craig and uniform interpolation properties across classical, intuitionistic, modal, and substructural logics within the framework of universal proof theory.

Original authors: Iris van der Giessen, Raheleh Jalali, Roman Kuznets

Published 2026-02-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Iris van der Giessen, Raheleh Jalali, Roman Kuznets

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery. You have a Premise (the clues you found, let's call it A) and a Conclusion (the verdict you reached, let's call it B). You know that if A is true, then B must be true.

Now, imagine a third person, a Mediator, who needs to explain why A leads to B, but this Mediator is only allowed to use words that appear in both A and B. They cannot use any secret jargon from A that isn't in B, and they can't use any legal terms from B that aren't in A.

The Interpolant is that perfect, middle-ground explanation. It's the "bridge" that connects the two sides using only shared vocabulary.

This paper is a massive Instruction Manual for Building Bridges. It teaches logicians (the detectives) how to construct these bridges using different types of Proof Systems (the tools of the trade).

Here is a breakdown of the paper's main ideas using simple analogies:

1. The Two Main Construction Crews

The paper focuses on two famous teams of builders who have different ways of constructing these bridges.

Team Maehara (The "Split" Crew):
- How they work: They look at the whole proof (the journey from A to B) and split it right down the middle. They trace every step of the journey, looking at the clues on the left and the verdict on the right.
- The Magic Trick: As they walk backward from the verdict to the clues, they build the bridge piece by piece. If a step uses a word only on the left, they discard it. If it uses a word only on the right, they discard it. If it uses a shared word, they keep it.
- The Result: They produce a bridge that works for any specific case (Craig Interpolation).
- The Upgrade: Sometimes, they can also tell you if the shared words are being used positively (as a strength) or negatively (as a weakness). This is called Lyndon Interpolation.
Team Pitts (The "Universal" Crew):
- How they work: They are even more ambitious. They don't just want a bridge for this specific A and B. They want to build a Universal Bridge that works for any B, as long as A stays the same.
- The Magic Trick: They act like a master architect who can "delete" a specific variable (a specific word) from a formula and replace it with a new, simplified formula that captures everything that word could have meant.
- The Result: This is called Uniform Interpolation. It's like having a "plug-and-play" adapter that fits any socket.

2. The Problem: Old Tools Don't Always Fit

For a long time, logicians only had one type of tool: the Standard Sequent Calculus. Think of this as a standard, flat piece of paper where you write formulas in rows.

The Issue: For some complex logics (like certain types of modal logic or fuzzy logic), trying to build a bridge on a flat piece of paper is impossible. The paper keeps tearing, or the bridge collapses.
The Paper's Solution: The authors say, "Let's upgrade our tools!" They introduce Generalized Sequent Calculi.

3. The New Tools: 3D Printing and Labeled Maps

To build bridges for the hardest logics, the paper suggests using three advanced construction methods:

Labelled Sequents (The "Map" Method):
- Imagine instead of just writing formulas, you attach a GPS coordinate (a label) to every single sentence.
- Analogy: Instead of saying "It is raining," you say "At location 1, it is raining."
- This helps the builders track exactly where a fact is true. If the logic involves "possibility" or "necessity" (like "It might rain tomorrow"), the labels act like a map showing different possible worlds. This makes it much easier to build the bridge because you can see the terrain clearly.
Hypersequents (The "Multi-Page" Method):
- Imagine you have a stack of papers instead of just one. You can write different parts of the argument on different pages and connect them.
- Analogy: It's like having a spreadsheet with multiple tabs. If one tab gets too crowded, you move the overflow to the next tab. This flexibility allows you to build bridges for logics that are too complex for a single page.
Nested Sequents (The "Russian Doll" Method):
- Imagine putting a proof inside a box, and that box inside another box.
- Analogy: It's like a set of nesting dolls. You can have a statement about a world, inside a statement about a world within that world. This is perfect for handling deep layers of "what if" scenarios.

4. The "Universal Proof Theory" (The Blueprint Check)

The paper also discusses a high-level concept called Universal Proof Theory.

The Idea: Instead of checking every single logic one by one to see if a bridge can be built, the authors created a Blueprint Checklist.
The Rule: If a logic's rules look "nice" (mathematically speaking, they are "semi-analytic"), you can guarantee a bridge exists. If the rules are "messy," you know immediately that no bridge can be built.
The Surprise: This checklist revealed that for many famous logics, no nice, clean proof system exists. It's like realizing that for some very complex buildings, you simply cannot build them with standard bricks; you need a custom, messy, or 3D-printed structure.

5. Why Does This Matter?

You might ask, "Why do we care about building these logical bridges?"

Computer Science: It helps verify that software is safe. If a program has a bug (Premise) that leads to a crash (Conclusion), the bridge (Interpolant) tells you exactly which part of the code caused the crash without needing to read the whole manual.
Artificial Intelligence: It helps AI systems explain why they made a decision in a way that humans can understand, using only the concepts the human already knows.
Mathematics: It proves that certain mathematical structures are "well-behaved" and predictable.

Summary

This paper is a comprehensive guidebook for logicians. It says:

Here is how to build bridges (interpolants) using old, standard tools (Maehara and Pitts).
Here is what to do when the standard tools break: use Labels, Stacks, or Nesting (Labelled, Hyper, and Nested sequents).
Here is a Checklist to tell you in advance if a logic is even capable of having a bridge, or if it's too chaotic to ever be tamed.

It turns the abstract, dusty work of mathematical logic into a practical, constructive engineering task.

1. Problem Statement

The paper addresses the challenge of establishing Interpolation Properties (specifically Craig Interpolation - CIP, Lyndon Interpolation - LIP, and Uniform Interpolation - UIP) across a wide spectrum of non-classical logics, including classical, intuitionistic, modal, and substructural logics.

While semantic methods exist, they often lack constructivity. The paper focuses on proof-theoretic methods, which are constructive and algorithmic. However, traditional methods face limitations:

Maehara's method (based on sequent calculi) is constructive but often fails to prove Lyndon interpolation (polarity preservation) for logics without cut-free sequent calculi or where standard cuts disrupt polarity.
Pitts' method (for uniform interpolation) requires specific termination properties that many standard calculi lack.
Many logics (e.g., S5, Gödel-Dummett) do not admit standard cut-free sequent calculi, making traditional interpolation proofs difficult or impossible.
There is a lack of a unified framework to determine which logics possess interpolation properties and why some well-behaved proof systems fail to yield them.

2. Methodology

The authors employ a multi-faceted proof-theoretic approach, moving from standard sequent calculi to generalized structures and a meta-theoretical framework:

A. Maehara's Method (Split Sequents)

Core Idea: Instead of interpolating between antecedent and succedent, the method interpolates between a "left split" and a "right split" of a sequent ( $\Gamma; \Gamma' \Rightarrow \Delta; \Delta'$ ).
Mechanism: Given a proof of $\varphi \to \psi$ , the method constructs an interpolant $\theta$ by induction on the proof tree. The split tracks the origin of formulas (from $\varphi$ or $\psi$ ) to ensure the variable condition ( $Var(\theta) \subseteq Var(\varphi) \cap Var(\psi)$ ).
Extensions: The paper discusses Restricted Cuts (Analytic, Semi-analytic, Monochromatic) to handle logics like S5 that lack cut-free calculi, though these often fail to preserve polarity for LIP.

B. Pitts' Method (Uniform Interpolation)

Core Idea: Constructs uniform interpolants ( $\exists p \varphi, \forall p \varphi$ ) that work for any context, effectively interpreting propositional quantification within the logic.
Mechanism: Relies on strongly terminating sequent calculi. The interpolant is constructed via a bottom-up proof search (even for unprovable sequents), defining the interpolant recursively based on the rule applied.
Constraint: Requires calculi where rule applications strictly decrease a weight measure (e.g., avoiding contraction in the principal formula).

C. Universal Proof Theory

Framework: Introduces Semi-analytic Rules and Focused Axioms.
Logic: A logic has CIP/UIP if it admits a semi-analytic calculus. If the calculus is fully terminating, it guarantees UIP.
Significance: This provides a syntactic criterion to prove the non-existence of well-behaved proof systems for logics that lack interpolation (e.g., most intermediate logics).

D. Generalized Sequent Calculi (Labelled, Hyper-, Nested)

Motivation: For logics where standard sequents fail (e.g., S5, GL), the authors utilize Labelled Sequent Calculi (incorporating Kripke semantics directly into the syntax via labels $i: \varphi$ and relations $iRj$).
Labelled Interpolation: Interpolants are not just formulas but multiformulas (Boolean combinations of labelled formulas).
Reverse Engineering Strategy: The authors categorize rules into Local, Conjunctive, and Disjunctive types based on their semantic behavior.
- Local: Interpolant is preserved.
- Conjunctive/Disjunctive: Interpolants are combined via $\land$ or $\lor$ .
- Modal ( $\square$ / $\diamond$ ): Requires complex transformations to handle fresh labels introduced in premises (e.g., converting $j:\varphi$ to $i:\square\varphi$ ).

3. Key Contributions

Comprehensive Survey & Unification: The paper unifies Maehara's and Pitts' methods, demonstrating how they extend to modal and substructural logics.
Labelled Interpolation Framework: It provides a robust, constructive method for proving Lyndon Interpolation (LIP) using labelled sequents. This is a significant improvement over standard sequent methods, which often fail to preserve polarity for logics like S5.
Universal Proof Theory Results:
- Positive: Identifies that logics with semi-analytic, fully terminating calculi possess UIP.
- Negative: Proves that most intermediate logics and many modal logics (e.g., extensions of S4, K4) cannot have semi-analytic sequent calculi because they lack interpolation. This establishes a deep link between the existence of "nice" proof systems and interpolation properties.
Algorithmic Construction: The paper details algorithms for constructing interpolants for:
- Classical/Intuitionistic logic (Maehara).
- Modal logic K (Pitts).
- Logics defined by Horn-clause frame conditions (via labelled sequents).
Handling Non-Interpolable Rules: It clarifies that the existence of a cut-free calculus does not guarantee interpolation; specific rule structures (like those in Gödel-Dummett logic) may require more complex calculi (hyper/nested) to prove interpolation.

4. Key Results

Modal Logics:
- Proved CIP and LIP for the entire Modal Cube (K, T, D, K4, S4, S5, etc.) using labelled sequents.
- Demonstrated that S5 admits LIP via labelled sequents, whereas standard Maehara methods with analytic cuts fail to prove LIP for S5.
- Showed that logics like GL (Gödel-Löb) have CIP but require cyclic proofs or specific treatments for LIP.
Intermediate Logics:
- Confirmed that only 7 consistent intermediate logics (IPC, LC, KC, Bd2, Sm, GSc, CPC) have CIP/UIP.
- Used this to prove that no other intermediate logic admits a semi-analytic sequent calculus.
Substructural & Linear Logics:
- Extended results to logics like MALL, ILL, and fuzzy logics (MTL, BL).
- Identified families of logics (e.g., certain extensions of MALL, relevance logics) that lack CIP and thus cannot have semi-analytic calculi.
Uniform Interpolation:
- Provided the first proof-theoretic proof of Uniform Lyndon Interpolation (ULIP) for logic K5.
- Formalized the construction of uniform interpolants in Coq/Rocq for IPC, K, GL, and iSL.

5. Significance

Constructive Nature: Unlike semantic proofs, these methods provide explicit algorithms to compute interpolants, which is crucial for applications in proof complexity (e.g., NP vs. coNP), model checking, and knowledge representation.
Bridging Syntax and Semantics: The labelled sequent approach elegantly bridges the gap between proof theory and Kripke semantics, allowing the derivation of interpolation for logics defined purely by frame conditions.
Negative Results as Tools: The application of Universal Proof Theory turns interpolation properties into a tool for impossibility results. If a logic lacks interpolation, one can immediately conclude it cannot have a "nice" (semi-analytic) proof system, saving researchers from futile attempts to construct such calculi.
Practical Utility: The paper serves as a "manual" for researchers: to prove interpolation for a new logic, one checks if its calculus rules fit the standard "Local/Conjunctive/Disjunctive" patterns or if they require specific transformations (like the $\square$ -like rules for fresh labels).

In summary, the paper establishes that interpolation is not just a logical property but a structural constraint on proof systems. It provides the necessary tools to prove interpolation constructively for a vast array of logics using generalized sequent calculi and offers a rigorous framework to understand the limitations of proof-theoretic methods.