🔢 mathematics

Foundations for an Abstract Proof Theory in the Context of Horn Rules

This paper introduces a logic-independent framework based on "g-sequents" and abstract calculi to analyze inference rule interactions, enabling the transformation of any abstract calculus into a polynomially equivalent lattice of systems that encompasses known deep-inference and labeled sequent formalisms for Horn logics.

Original authors: Tim S. Lyon, Piotr Ostropolski-Nalewaja

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tim S. Lyon, Piotr Ostropolski-Nalewaja

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 build a house. You have a blueprint, but instead of just drawing lines on paper, you are using a magical construction kit where every brick, beam, and window has its own tiny, self-contained rulebook. In the world of computer science and mathematics, this "construction kit" is called logic. It's the set of rules we use to figure out if an argument is true or false, whether we are proving a math theorem or teaching a computer to reason. For decades, mathematicians have used a specific style of blueprint called a sequent. Think of a sequent as a single line on a page that says, "If these things are true, then this other thing must be true." It's a neat, tidy way to build proofs.

But as logicians started tackling more complex, weird, and wonderful types of reasoning (like time travel logic or logic about what people know), the old single-line blueprints started to crack. They were too rigid. So, scientists invented "multisequents." Imagine taking that single line and stretching it out into a whole city map, or a family tree, or a tangled web of connections. Suddenly, your proof isn't just a line; it's a landscape. The problem is, with so many different ways to draw these landscapes—some look like trees, some like graphs, some like labeled maps—it became a nightmare to compare them. How do you know if a proof in a "tree-logic" is the same strength as a proof in a "graph-logic"? It's like trying to compare a house built with LEGO bricks to one built with clay; they might look different, but are they equally strong?

This is where the paper by Tim S. Lyon and Piotr Ostropolski-NalewaJA steps in. They didn't just try to fix one specific type of logic; they built a universal translator and a master construction manual for all these different proof styles. They created a "logic-independent" framework, which is a fancy way of saying they built a system that doesn't care what specific rules you are playing by, as long as you follow the general shape of the game.

Here is the big discovery: The authors found that every single one of these complex proof systems actually sits inside a giant, invisible lattice (think of it as a multi-story elevator shaft or a diamond-shaped grid). At the very bottom of this grid are the "Explicit" calculi. These are the systems that do all their heavy lifting out in the open, using explicit rules to move information around, kind of like a construction crew that has to physically carry every brick from one spot to another. At the very top of the grid are the "Implicit" calculi. These systems are sneakier; they bake the rules directly into the shape of the blueprint itself, so the bricks just know where to go without needing a crew to move them.

The paper proves that you can take a proof from the bottom (the explicit, brick-carrying style) and transform it into a proof at the top (the implicit, shape-based style) and vice versa. They didn't just guess this; they wrote algorithms (step-by-step computer recipes) called "Implicate" and "Explicate" that can automatically do this transformation. They showed that no matter which floor of the building you are on, the proof is "polynomially equivalent." In plain English, this means that while the proofs might look different and take up different amounts of space, they are essentially the same strength, and you can convert one to the other without the computer getting stuck in an infinite loop or taking a million years to finish.

One of the most exciting things they found is that these two extremes—the "Explicit" labeled systems and the "Implicit" nested systems—aren't actually rivals. They are two sides of the same coin. The paper shows that for many famous logics, there is a "twin" system. If you have a labeled sequent system (the explicit one), there is a corresponding nested sequent system (the implicit one) that does the exact same job, just with a different internal structure. The authors demonstrated this by taking a real-world logic system for "S4" (a logic about necessity and possibility) and running their algorithm on it. The result? They successfully turned a complex labeled proof into a neat, tree-shaped nested proof, proving that the two are interchangeable.

The authors are very careful to note that this isn't a magic wand that solves every problem in the universe. They don't claim to have found the "ultimate" logic. Instead, they have provided a framework and a toolkit. They have shown how these different systems relate to each other and how to move between them. They proved that this movement is efficient (it happens in polynomial time, which is fast enough for computers) and that the size of the proofs doesn't explode out of control.

So, what does this mean for a curious teenager? It means that the messy, confusing world of different logic systems is actually much more organized than it looks. There is a hidden order, a lattice, connecting them all. Whether you are building a proof with a tangled web of connections or a neat tree, you are standing on the same foundation. The authors have handed us the map to navigate between these worlds, showing us that the "Explicit" and "Implicit" ways of thinking are just different perspectives on the same mathematical truth. They haven't solved every logic puzzle, but they have given us the keys to unlock the doors between the rooms where those puzzles live.

Technical Summary: Foundations for an Abstract Proof Theory in the Context of Horn Rules

Problem Statement

Proof calculi, particularly sequent-style systems, are fundamental to logic, serving as engines for reasoning, automated deduction, and the discovery of new logics. While Gentzen's original sequent formalism established the sub-formula property, the advent of more expressive logics (e.g., tense logic, bi-intuitionistic logic) revealed that standard sequents were too restrictive. This led to the development of various "multisequent" formalisms—such as hypersequents, nested sequents, labeled sequents, and linear nested sequents—which embed Gentzen sequents into more complex data structures (graphs, trees, lines).

Despite their utility, these formalisms often possess distinct advantages and disadvantages. For instance, nested calculi are often suitable for proof-search algorithms, while labeled calculi facilitate algorithmic construction for broad classes of logics. A significant gap exists in the literature regarding the systematic relationship between these diverse systems. Previous work has typically analyzed specific proof transformations (permutations and simulations) between concrete calculi for specific logics. There is a lack of a unifying, logic-independent framework that can:

Generalize the notion of sequents and inference rules to cover various multisequent formalisms.
Systematically analyze how different inference rule types interact.
Provide generic algorithms to transform proofs and calculi between these formalisms while preserving complexity bounds.
Explain the structural duality between labeled sequent systems and reachability nested systems.

Methodology

The authors introduce a novel, logic-independent framework based on generalized sequents (g-sequents) and abstract calculi.

1. Generalized Sequents (g-sequents)

The framework abstracts the internal structure of sequents, treating them as atomic labels. A g-sequent is defined as a tuple $G = (V, E, L)$ , where:

$V$ is a set of vertices (labels).
$E$ is a set of typed edges (relational atoms).
$L$ maps vertices to sequents (treated as atomic entities).
This abstraction allows the framework to uniformly represent labeled sequents (binary graphs), nested sequents (trees), and linear nested sequents (lines) as specific instances of graph structures.

2. Inference Rule Types and Constraints

Inference rules are generalized into types parameterized by structural constraints and sequent constraints:

Structural Constraints: Defined as finite labeled polytrees, these specify the required edge configurations (paths) within a g-sequent. They utilize E-systems (a restricted class of semi-Thue systems) to generate languages of edge strings, allowing constraints to express path-based conditions (e.g., "a path of length $n$ exists").
Sequent Constraints: Relations specifying how the sequents at designated vertices must relate to one another.

The framework defines several rule types:

Initial Rules: Axioms with no premises, subject to structural and sequent constraints.
Local Rules: Operate on a single vertex, independent of edge structure.
Expansion Rules: Introduce fresh vertices and edges (bottom-up).
Transmission Rules: Update sequents connected by a single edge.
Reachability Rules: A generalization of transmission rules where sequents are connected by paths defined by E-system languages.
Horn Rules: Encode Horn properties (universally closed first-order formulas of the form $\forall \vec{x} (\bigwedge \text{edges} \to \text{edge})$ ). These rules manipulate the edge structure directly (e.g., adding a loop for reflexivity or a shortcut for transitivity).

3. Core Operations: Absorption and Fracturing

The authors introduce two dual operations to manipulate the relationship between rules and constraints:

Absorption ( $\oplus$ ): Incorporates the functionality of a set of Horn rules into the structural constraints of an initial or reachability rule. This "internalizes" the Horn reasoning, effectively strengthening the constraint.
Fracturing ( $\ominus$ ): The inverse operation, which weakens a constraint by extracting a set of Horn rules from it, making the reasoning explicit again.

4. Permutation and Simulation

The paper establishes a theory of permutation (swapping rule applications) and simulation (one set of rules deriving everything another can). Key results show that:

Horn rules can be permuted above local and expansion rules.
Horn rules can be permuted above reachability rules if the Horn rules have been absorbed into the reachability rule's constraints.
This leads to the ability to "permute away" explicit Horn rules by absorbing them into constraints, or to "reintroduce" them by fracturing constraints.

Key Contributions and Results

1. Generic Calculus Transformation Algorithms

The authors define two algorithms, Implicate and Explicate, which compute lattices of polynomially equivalent abstract calculi:

Implicate: Takes an explicit calculus (where Horn reasoning is performed via explicit structural rules) and computes its upward space. This space is a lattice where the top element is an implicit calculus (where Horn reasoning is encoded in constraints).
Explicate: Takes an implicit calculus and computes its downward space, where the bottom element is an explicit calculus.

2. Lattice Structure and Polynomial Equivalence

The paper proves that every abstract calculus sits within a complete lattice of polynomially equivalent calculi.

Explicit Calculi: Correspond to bottom elements. They use minimal constraints and rely on explicit Horn rules. These are identified with standard labeled sequent systems.
Implicit Calculi: Correspond to top elements. They use maximal constraints (absorbing Horn rules) and contain no explicit Horn rules. These are identified with reachability nested sequent systems.
Complexity: Transformations between these calculi are computable in PTIME. Proofs in explicit (labeled) systems can be quadratically larger than those in implicit (nested) systems, but the translation overhead remains polynomial.

3. Duality of Systems

The framework reveals a duality between labeled sequent systems and reachability nested systems. They are not fundamentally distinct but occupy opposite ends of a spectrum defined by the explicitness of structural reasoning.

Labeled Systems (Bottom): Perform Horn reasoning explicitly via structural rules manipulating edges.
Nested Systems (Top): Perform Horn reasoning implicitly via constraints on paths, preserving the tree/polytree structure of proofs.

4. Instantiation and Examples

The framework is instantiated with the labeled sequent calculus G3S4 for the modal logic S4.

G3S4 is shown to be an explicit calculus.
Applying Implicate to G3S4 yields the implicit calculus NS4, which corresponds to a reachability nested sequent system for S4.
The paper demonstrates concrete proof transformations between G3S4 and NS4, showing how explicit edge manipulations in G3S4 correspond to constraint-based reasoning in NS4.

Significance and Claims

The paper claims to provide a unifying abstract framework for the study of multisequent systems that is independent of specific logics. Its significance lies in:

Generalization: It subsumes a wide variety of known proof systems (labeled, nested, linear nested) under a single formalism, allowing for the analysis of their relationships in a general setting.
Mechanism for Transformation: It provides concrete, generic algorithms (Implicate/Explicate) to transform between different proof formalisms, establishing that they are polynomially equivalent. This resolves questions about the relative sizes of proofs and sequents across formalisms.
Theoretical Insight: It explains the "structural refinement" phenomenon observed in previous literature. The paper demonstrates that the transition from labeled to nested systems is essentially a process of absorbing structural rules into constraints (and vice versa).
Preservation of Properties: The transformation algorithms preserve cut-admissibility. If a system is cut-free, its dual in the lattice is also cut-free.
Complexity Bounds: It establishes that while nested proofs are generally more compact (quadratically smaller in the worst case) than labeled proofs, the computational complexity of reasoning remains in the same class due to polynomial equivalence.

The authors position this work as a foundational step toward understanding the nature of multisequent systems, offering a toolkit for manipulating proofs and potentially extracting new proof systems for non-classical logics. They note that the framework is adaptable to other formalisms (e.g., hypersequents) and suggests future work on generalizing beyond Horn rules and exploring broader graph structures.