💻 computer science

Unifying Sequent Systems for Gödel-Löb Provability Logic via Syntactic Transformations

This paper resolves an open problem in proof theory by introducing novel syntactic transformations, including a linearization technique and a normal form, to establish full constructive proof correspondences between six prominent sequent-based formalisms for Gödel-Löb provability logic, thereby unifying structural and cyclic systems and yielding the first cut-free linear nested sequent calculus for the logic.

Original authors: Tim S. Lyon

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tim S. Lyon

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 trying to solve a very complex puzzle. In the world of logic, this puzzle is proving that a specific statement is true within a system called Gödel-Löb logic (often just called GL). This logic is used to reason about "provability"—essentially, asking, "Is it provable that this statement is true?"

For decades, mathematicians have built different "workshops" (called sequent systems) to solve these puzzles. Each workshop has its own unique set of tools, rules, and blueprints. Some workshops use flat tables, others use 3D trees, and some even use infinite loops.

The problem? No one knew exactly how to translate a solution found in one workshop into the language of another. If you solved a puzzle in the "Tree Workshop," could you prove it in the "Loop Workshop"? Until now, that was a mystery.

This paper, by Tim S. Lyon, acts as a universal translator and a construction guide that connects all these different workshops. Here is how the paper achieves this, explained through simple analogies:

1. The Five Different Workshops

The paper focuses on five specific ways of proving things in GL:

The Flat Workshop (GLseq): The classic, traditional way. Think of this as a simple, straight line of text.
The Loop Workshop (GLcirc & GL∞): These allow proofs to loop back on themselves (like a snake eating its own tail) or go on forever in a structured way.
The Tree Workshop (CSGL∗): Here, proofs look like family trees. A main statement branches out into sub-statements, which branch out further.
The Graph Workshop (G3KGL): This is like a complex map with nodes and roads connecting them.
The New Workshop (LNGL): The paper invents this one. It's a "Linear Nested" system, which is like a stack of transparent sheets, where each sheet holds a simple line of text, but they are stacked on top of each other.

2. The Big Challenge: "Shedding" the Structure

The hardest part of the paper is moving from the Tree Workshop (CSGL∗) to the Flat Workshop (GLseq).

The Analogy: Imagine you have a sculpture made of a complex, branching tree. You want to turn it into a single, flat sheet of paper without losing any of the information.
The Problem: You can't just flatten a tree; the branches would get tangled.
The Solution (Step 1: End-Active): The author first rearranges the tree so that all the "action" (the important rules) happens only at the very tips of the branches (the leaves). It's like pruning a bonsai tree so all the growth is at the very ends.
The Solution (Step 2: Linearization): Once the tree is pruned, the author introduces a new technique called linearization. Imagine taking that pruned tree and carefully "unspooling" it. You trace a path from the root to the tip, and as you go, you lay the branches down in a straight line.
The Result: This creates the LNGL system. It's a new way of writing proofs that looks like a stack of simple lines. This is the paper's first major invention: a new tool to turn complex trees into simple lines.

3. The "Normal Form" Dance

Once the proof is in this new "stack of lines" format (LNGL), the author shows how to organize it into a specific rhythm, called Normal Form.

The Analogy: Think of a dance routine. The proof doesn't just jump around randomly. It moves in stages:
1. First, it does all the "local" moves (dealing with simple logic like "and" or "or").
2. Then, it does "propagation" moves (spreading information down the line).
3. Finally, it does the "modal" moves (dealing with the tricky "provability" boxes).
By forcing the proof to dance in this specific order, it becomes easy to translate into the old, classic "Flat Workshop" (GLseq).

4. Closing the Loop

The paper doesn't stop there. It connects the dots all the way around:

It shows how to turn the Tree proofs into the New Stack proofs.
It shows how to turn the New Stack proofs into the Classic Flat proofs.
It shows how to turn the Classic Flat proofs into the Graph proofs.
It reminds us that the Loop proofs are already connected to the Classic Flat proofs (thanks to previous work by Shamkanov).

The Final Takeaway

By building these bridges, the author has created a complete map of the Gödel-Löb logic landscape.

Before: If you had a proof in the Tree Workshop, you couldn't easily use the tools from the Loop Workshop.
Now: You can take a proof from any of these six systems, translate it into any other system, and know it's still a valid proof.

The paper essentially says: "We have built a universal adapter. No matter which language of logic you speak, you can now understand and use the proofs from any other language in this family." This allows mathematicians to pick the most convenient tool for a specific job and then translate the result to the tool they need for the final answer, without having to re-prove everything from scratch.

Technical Summary: Unifying Sequent Systems for Gödel-Löb Provability Logic

Problem Statement
The paper addresses a significant gap in the proof theory of Gödel-Löb provability logic (GL). While GL possesses a rich variety of cut-free sequent-style formalisms, the relationships between them were not fully established. Specifically, prior work had established proof-theoretic correspondences between:

Structural systems: Negri's labeled sequent system ($G3KGL$) and Poggiolesi's tree-hypersequent system ( $CSGL^*$ ), via Goré and Ramanayake.
Proof-structure generalizations: Sambin and Valentini's Gentzen system ( $GL_{seq}$ ), Shamkanov's non-wellfounded system ( $GL_\infty$ ), and Shamkanov's cyclic system ( $GL_{circ}$ ), via Shamkanov.

However, the inter-translatability of proofs between the structural systems ($G3KGL$, $CSGL^*$ ) and the proof-structure generalizations ( $GL_{seq}$ , $GL_\infty$ , $GL_{circ}$ ) remained an open problem. The inherent difficulty lies in transforming proofs that utilize complex structural sequents (graphs or trees of Gentzen sequents) into proofs using standard Gentzen sequents, a process requiring the "shedding" of this extra structural data.

Methodology
The author, Tim S. Lyon, resolves this open problem by constructing a chain of syntactic proof transformations that bridge the gap between these distinct formalisms. The methodology proceeds in three primary phases:

Restructuring to End-Active Form: The paper first demonstrates how to restructure proofs in the tree-hypersequent system $CSGL^*$ into an "end-active" form. In an end-active proof, the principal and auxiliary formulae of inference rules occur only at the (pre-)leaves of the tree-sequent structure. This is achieved by permuting non-end-active rules downward through the proof tree, leveraging the height-preserving invertibility of rules in $CSGL^*$ .
Linearization: A novel "linearization technique" is introduced to transform these end-active tree-sequent proofs into proofs using linear nested sequents. This technique involves identifying specific paths from the root to a leaf in the tree-sequent and "pruning" the sub-trees, effectively collapsing the tree structure into a linear sequence of Gentzen sequents. This process yields a new calculus, LNGL (Linear Nested Sequent Calculus for GL).
Normal Form and Translation to Gentzen: The paper shows that proofs in LNGL can be transformed into a specific normal form. In this form, proofs proceed in repetitive stages: local rules, followed by propagation rules ( $4L$ and $\Box L$ ), and finally the modal rule ( $\Box R$ ). This structured proof is then translated into Sambin and Valentini's Gentzen system ( $GL_{seq}$ ). Finally, standard transformations map $GL_{seq}$ proofs back to the labeled system $G3KGL$ and to the cyclic/non-wellfounded systems ( $GL_{circ}$ , $GL_\infty$ ).

Key Contributions

New Calculus (LNGL): The paper introduces LNGL, the first cut-free linear nested sequent calculus for Gödel-Löb logic. This system operates on lines of Gentzen sequents and retains fundamental properties like invertibility and cut-admissibility.
Novel Linearization Technique: The author presents a general method for extracting linear nested sequent systems from tree-hypersequent systems. This technique is conjectured to be applicable to other modal and related logics to generate new linear nested systems.
Complete Proof-Theoretic Correspondence: The paper establishes a full, six-way syntactic correspondence between the following systems: $G3KGL$, $CSGL^*$ , $LNGL$, $GL_{seq}$ , $GL_\infty$ , and $GL_{circ}$ .
Constructive Mappings: The work provides the first constructive proof mappings between structural systems (labeled, tree-hypersequent, linear nested) and the cyclic sequent system ( $GL_{circ}$ ).

Results
The primary result is the demonstration that proofs in any of the six major sequent systems for GL can be syntactically transformed into proofs in any other. Specifically:

Proofs in $CSGL^*$ can be transformed into end-active proofs, then linearized into LNGL.
Proofs in LNGL can be normalized and transformed into $GL_{seq}$ .
Proofs in $GL_{seq}$ can be transformed into $G3KGL$ and the cyclic systems ( $GL_{circ}$ , $GL_\infty$ ).
The paper confirms that $LNGL$ is sound and complete for GL, and that proofs in $LNGL$ can be put into a normal form where modal and local rule applications repeat in stages.

Significance
The paper claims to "complete the picture" of proof-theoretic correspondences for Gödel-Löb logic. By establishing these syntactic transformations, the work allows for the transfer of results (such as interpolation properties or complexity bounds) between systems without requiring independent proofs in each formalism. Furthermore, the introduction of LNGL provides a new tool for proof search with complexity-optimal properties, while the linearization technique offers a potential pathway for generating linear nested systems for other logics. The work also provides the first constructive mapping between structural systems and cyclic proofs, bridging a gap between different approaches to handling inductive/coinductive reasoning in modal logic.