💻 computer science

Uniform Lyndon Interpolation via Non-wellfounded Proofs

This paper establishes the previously open property of uniform Lyndon interpolation for the provability logic GLS by applying non-wellfounded proof theory, while also providing an alternative cut elimination proof and outlining a methodology adaptable to other provability logics.

Original authors: Borja Sierra Miranda (University of Bern), Thomas Studer (University of Bern)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Borja Sierra Miranda (University of Bern), Thomas Studer (University of Bern)

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 complex mystery. You have a massive file of clues (a logical argument), and you need to find a specific piece of evidence that explains the crime without revealing any secrets you aren't supposed to know.

This paper is about a new, powerful way for detectives (logicians) to find that specific piece of evidence. The authors, Borja Sierra Miranda and Thomas Studer, are working in the field of Provability Logic, which is essentially the study of how we can prove that something is provable.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Diagonal" Trap

In traditional logic, when detectives try to break down a complex argument to find a specific piece of evidence (an "interpolant"), they often run into a tricky obstacle called the "diagonal formula."

Think of this like a magic mirror in a hallway. When you look into it, the reflection flips your image. In logic, this mirror flips the "polarity" of a variable (turning a "positive" clue into a "negative" one, or vice versa). If you are trying to find a clue that must stay positive, this mirror ruins your search. For a long time, logicians knew how to find the evidence without worrying about the mirror, but they didn't know how to find evidence that respected the mirror's rules (keeping positive things positive and negative things negative). This is called Uniform Lyndon Interpolation.

2. The New Tool: Non-Wellfounded Proofs

The authors introduce a new tool called Non-wellfounded Proofs.

The Old Way (Wellfounded): Imagine building a tower of blocks. You start at the bottom, place a block, then another on top, and keep going until you reach the top. You can never put a block on top of itself. This is a standard, finite proof.
The New Way (Non-wellfounded): Imagine a tower that is allowed to have a loop. You can build a block, go up a few levels, and then attach a rope that ties back down to a block you already placed. It's a "circular" tower.

In the world of logic, these circular towers are incredibly useful because they allow the detective to bypass the "diagonal mirror" trap. The loop lets the logic flow in a way that preserves the "polarity" (the positive/negative nature) of the clues, which the old straight towers couldn't do.

3. The Breakthrough: Solving the GLS Mystery

The specific logic they are investigating is called GLS.

What was known: People already knew you could find the evidence in GLS (Uniform Interpolation).
What was unknown: No one knew if you could find the evidence while respecting the polarity rules (Uniform Lyndon Interpolation). It was an open question: "Does GLS have a solution that keeps the clues in their proper orientation?"

The Authors' Achievement:
They used their "circular tower" method to prove that yes, GLS does have this special solution. They didn't just find the solution; they built a machine (a set of rules) to generate it automatically.

4. How They Did It: The "Equation" Machine

To make this work, they invented some new concepts:

Lyndon Fixpoints: Think of this as a "self-referential recipe." It's a formula that, when you plug it into itself, gives you the same result. It's like a recipe for a cake that, when you bake it, tells you exactly how to bake the next cake perfectly.
Lyndon Equational Systems: They set up a system of equations where the variables represent the clues. Because they used the "circular tower" method, they could solve these equations while ensuring that every "positive" variable stayed positive and every "negative" variable stayed negative.

5. The Result

By using these circular proofs, they successfully constructed a "Uniform Lyndon Interpolant" for GLS.

In plain English: They proved that for any logical argument in GLS, you can always extract a summary that explains the argument, uses only the specific vocabulary you asked for, and strictly respects the "positive" and "negative" nature of the original clues.

Summary of Contributions

The paper claims three main things:

A New Proof: They provided a fresh way to prove that "Cut Elimination" (a standard logic cleanup process) works for GLS, using these circular towers instead of the old methods.
New Concepts: They introduced the ideas of "Lyndon fixpoints" and "Lyndon equational systems" to handle the tricky polarity rules.
The Big Win: They solved the open problem of whether GLS has Uniform Lyndon Interpolation, proving that it does.

What they did NOT claim:
The paper does not claim this has immediate medical applications, uses in AI, or real-world engineering uses. It is purely a theoretical advancement in the mathematics of logic, proving that a specific type of logical puzzle can be solved in a more refined way than previously thought possible. They suggest that other logicians could use this same "circular tower" method to solve similar puzzles in other types of logic, but that is a suggestion for future work, not a current result.

Technical Summary: Uniform Lyndon Interpolation via Non-wellfounded Proofs

Problem Statement
Non-wellfounded proof theory has been successfully employed to establish Craig interpolation, Lyndon interpolation, and uniform interpolation for various logics, including provability logics. However, the combination of these properties—specifically the Uniform Lyndon Interpolation Property (ULIP)—had not been addressed using non-wellfounded methods prior to this work. The paper focuses on the provability logic GLS (also known as S), which corresponds to the provability predicate of Peano Arithmetic under true arithmetic. While GLS was known to possess uniform interpolation and Craig interpolation, it remained an open question whether GLS admits uniform Lyndon interpolation (or even non-uniform Lyndon interpolation). A primary obstacle in wellfounded proof systems for such logics is the "diagonal formula" in modal rules, which fails to preserve variable polarity, a requirement for Lyndon interpolation.

Methodology
The authors utilize non-wellfounded sequent calculi and local progress proof theory to overcome the limitations of wellfounded proofs. The methodology relies on three core technical components:

Local Progress Sequent Calculi: The authors employ a calculus, $G_{\infty}^{GLS}$ , which is a local progress system. Unlike standard wellfounded calculi, proofs in this system are trees that may contain infinite branches, provided that every infinite branch contains infinitely many "progressing nodes" (specifically, applications of the modal rule $\square K4_{sat}$ ). This system avoids the diagonal formula found in the wellfounded calculus $G_{GLS}$ , thereby preserving the polarity of variables throughout the proof search.
Interpolation Templates: To construct interpolants, the authors define "interpolation templates," which are cyclic preproofs (proofs with back-edges) generated by a specific set of saturation rules. These templates are built by applying rules that decompose formulas until they reach a saturated state. The templates are annotated with "preinterpolants," which are pseudoformulas involving bound variables corresponding to the repeat nodes in the cyclic proof.
Lyndon Equational Systems: To resolve the preinterpolants into valid formulas, the authors introduce the concepts of Lyndon fixpoints and Lyndon equational systems. An equational system consists of equations linking unknown variables to formulas, constrained by positive and negative vocabularies (sets of variables appearing with specific polarities). The authors prove that "simple" and "positive modalized" Lyndon equational systems are solvable in GLS. This solvability allows the substitution of bound variables in the preinterpolants with actual formulas that respect the required polarities.

Key Contributions
The paper makes three distinct contributions:

Alternative Cut Elimination: It provides a new proof of cut elimination for $G_{GLS}$ by translating proofs from the wellfounded calculus to the non-wellfounded calculus $G_{\infty}^{GLS}$ and establishing the local admissibility of the cut rule in the latter.
New Theoretical Concepts: It introduces Lyndon fixpoints and Lyndon equational systems. These concepts are essential for demonstrating that the uniform interpolants constructed via non-wellfounded proofs respect the polarity constraints required by Lyndon interpolation.
Proof of ULIP for GLS: It presents the first proof that GLS possesses the Uniform Lyndon Interpolation Property.

Results
The central result is Theorem 4.16, which states that GLS has the Uniform Lyndon Interpolation Property. The proof proceeds by:

Constructing an interpolation template for a given sequent.
Associating a positive modalized Lyndon equational system to the template's repeat nodes.
Solving this system in GLS (guaranteed by Theorem 4.7) to obtain a solution sequence.
Substituting this solution into the preinterpolant of the root node to generate the uniform Lyndon interpolant $\iota_T$ .
Verifying via Lemmas 4.14 and 4.15 that $\iota_T$ satisfies the conditions of ULIP: it contains only the specified positive and negative vocabularies, and it acts as an interpolant for any formula $\psi$ with compatible vocabularies.

Additionally, the paper establishes that the cut rule is eliminable in $G_{GLS}$ via the translation to $G_{\infty}^{GLS}$ , and that the cut rule is locally admissible in $G_{\infty}^{GLS}$ .

Significance and Scope
The paper claims to close the gap in the literature regarding uniform Lyndon interpolation for provability logics using non-wellfounded methods. The authors note that their methodology is adaptable to other provability logics, provided a non-wellfounded sequent calculus is available for them. They explicitly identify future directions, including applying the method to unary interpretability logics, bimodal provability logics, and intuitionistic provability logics. They also suggest investigating logics where simple Lyndon fixpoints do not exist (such as interpretability logic IL) and whether positive modalized Lyndon equational systems can still be solved in those contexts. The work does not claim to resolve ULIP for all modal logics, but rather demonstrates the viability of the non-wellfounded approach for GLS and outlines a framework for extension.