🔢 mathematics

Schemata, Cyclic Proofs and Herbrand Systems

This paper introduces a new type of proof schema based on point transition systems that enables the computation of Herbrand systems for inductive proofs, establishes a transformation from cyclic proofs to these schemata, and demonstrates their superior expressive power by proving the 2-Hydra statement, which is unprovable in standard LKID.

Original authors: Alexander Leitsch, Anela Lolic, Stella Mahler

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander Leitsch, Anela Lolic, Stella Mahler

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 prove a mathematical statement that involves a never-ending process, like counting up to infinity or solving a puzzle where the rules change slightly every time you make a move. In traditional mathematics, proving these things usually requires a special "Induction Rule"—a magic wand that says, "If it works for step 1, and if it works for step $n$ implies it works for step $n+1$ , then it works for all steps."

However, the authors of this paper are interested in a different way of looking at these proofs. They want to strip away the magic wand and instead describe the proof as a recipe or a blueprint that generates an infinite sequence of specific, finite proofs. They call these Proof Schemata.

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Infinite Library"

Imagine a library where every book is a proof of a specific math problem. If you have a problem that requires induction, you might need an infinite library: one book for $n=1$ , one for $n=2$ , one for $n=3$ , and so on, forever.

Traditional Proofs: Use a rule to say, "We don't need to write down every book; we just need a rule that generates them."
The Authors' Approach: They create a Master Blueprint (a Proof Schema). This blueprint isn't a single proof; it's a set of instructions that tells you how to build the specific proof for any number $n$ . It's like a computer program that prints out the proof for $n=100$ or $n=1,000,000$ on demand.

2. The New Tool: "Point Transition Systems"

To make these blueprints more powerful, the authors introduce a new way of organizing the instructions called Point Transition Systems.

The Analogy: Think of a board game. You are at a specific square (a "point"). Depending on the roll of the dice (a "condition"), you move to a new square.
In the Paper: Instead of dice, the "conditions" are mathematical rules (like "if $x$ is greater than 0"). The "squares" are different parts of the proof. The system maps out all the possible moves. If the game is designed well, you are guaranteed to eventually reach the "End" square (a finished proof) no matter where you start. This ensures the blueprint actually works and doesn't get stuck in an infinite loop.

3. The Treasure Hunt: "Herbrand Systems"

One of the main goals of this research is Proof Mining. This is the idea that a proof contains hidden information, like a treasure map.

The Treasure: In logic, this treasure is a list of specific examples (called Herbrand instances) that prove the statement is true. For example, if you prove "All numbers have a property," the treasure is the list of specific numbers that actually demonstrate this.
The Challenge: Usually, if a proof uses induction, finding this list of examples is impossible because the proof is too abstract.
The Breakthrough: The authors show that for their new "Blueprints" (Proof Schemata), they can automatically extract this treasure map. They call the resulting map a Herbrand System. It's a schematic list of examples that works for any number $n$ , generated directly from the blueprint.

4. The Connection: "Cyclic Proofs" vs. "Blueprints"

There is another way mathematicians handle infinite processes called Cyclic Proofs.

The Analogy: Imagine a proof that draws a circle. It says, "To prove this, I need to prove that part, which leads back to the start, but with a smaller number." It's a loop.
The Paper's Achievement: The authors built a translator. They showed that a large class of these "looping" proofs (Cyclic Proofs) can be converted into their "Blueprints" (Proof Schemata).
Why it matters: Once converted, the "Blueprint" can be used to extract the treasure map (Herbrand System) that was previously hard to find in the "looping" proof.

5. The Big Test: The "Two-Hydra" Monster

To prove their method is powerful, they tested it on a famous, difficult problem called the Two-Hydra Statement.

The Story: Imagine a hydra (a monster) with two heads. Every time you cut off a head, it grows back, but in a specific, complex way. The question is: "Can you eventually kill this hydra?"
The Result:
- A standard logic system (called LKID) cannot prove this hydra can be killed. It's too weak.
- A system using "loops" (called CLKID) can prove it.
- The Authors' Win: They took the "looping" proof of the Hydra and turned it into their "Blueprint." They proved that their Blueprint works (it terminates) and successfully extracted the "treasure map" (the Herbrand System) showing exactly how the Hydra is defeated.
- The Conclusion: Their method is stronger than the standard logic system because it can solve problems (like the Hydra) that the standard system cannot, while still providing the detailed "treasure map" of examples.

Summary

The paper introduces a new, more powerful way to write down mathematical proofs for infinite processes. They created a "translator" that turns "looping" proofs into "blueprints." These blueprints are so well-structured that they allow mathematicians to automatically extract a list of concrete examples (the "treasure") that prove the statement, even for problems that were previously considered too difficult to analyze in this way. They demonstrated this power by solving a famous "Hydra" puzzle that standard logic couldn't handle.

Technical Summary: Schemata, Cyclic Proofs and Herbrand Systems

Problem Statement
The paper addresses the challenge of analyzing inductive proofs within formal logic, specifically focusing on the extraction of computational content (Herbrand information) from proofs that utilize mathematical induction. While Herbrand's theorem provides a mechanism to separate propositional and quantifier inferences in cut-free proofs, it fails in the presence of the induction principle. Consequently, extracting "Herbrand information" from standard inductive proofs has been considered impossible.

Existing approaches to inductive reasoning include proof schemata (recursive definitions of proof sequences) and cyclic proof systems (global proof structures with cycles justified by trace conditions). While Herbrand systems have been successfully computed for proof schemata based on primitive recursion, and recent work has shown Herbrand structures can be extracted from cyclic proofs via higher-order recursion schemes, a direct connection between cyclic proofs and the extraction of Herbrand systems via proof schemata remained open. Furthermore, the expressive power of proof schemata was limited compared to cyclic proof systems like $CLKID_\omega$ , which can prove statements (e.g., the 2-Hydra statement) that are unprovable in the standard inductive calculus $LKID$.

Methodology
The authors develop a new formalism for proof schemata based on point transition systems and establish a translation from a specific subclass of cyclic proofs to this formalism.

Point Transition Systems (PTS): The authors define a framework for describing recursive calls independent of the objects being defined. A PTS consists of labeled points (pairs of a label and a tuple of parameters) and transitions governed by conditions. Crucially, they define canonic PTSs, which admit a well-founded ordering ensuring termination for all parameter assignments. This allows the definition of proof schemata that represent infinite sequences of proofs via recursive calls between schematic proof components.
Schematic Logic ($LKN$): The authors introduce a sequent calculus $LKN$ over natural numbers, allowing weak quantification over parameters but restricting strong quantification to avoid semantic issues when applying parameter assignments to proofs.
Herbrand Systems for Schemata: For proof schemata containing at most quantifier-free cuts, the paper defines a method to compute Herbrand systems. These are schemata of Herbrand instances of quantified formulas. The method involves tracing formula occurrences through the proof schema (including recursive calls) to collect substitutions, effectively realizing Herbrand's theorem for inductive proofs without explicit induction rules.
Translation from Cyclic Proofs: The paper presents an algorithm, transformIntoSchema, to translate a subclass of cyclic proofs ( $CLKID_\omega$ $C L K I D_{ω}$ ) into proof schemata. The translation is restricted to cyclic proofs where:
- Inductive definitions are of a specific "definition type" (premises do not introduce fresh variables, and productions are pairwise non-overlapping).
- Variables governing inductive behavior are not strongly quantified elsewhere.
  The algorithm proceeds in five steps:
- Initialization: Encoding inductive definitions as first-order axioms ( $p_{def}$ ).
- Cycle Decomposition: Identifying companion nodes (targets of back-links) and partitioning the cyclic proof into finite sub-derivations.
- Case Partitioning: Splitting derivations based on case-split rules to handle branching.
- Subderivation Transformation: Converting sub-derivations into $s$ -proofs (schematic proofs) by normalizing guards, eliminating auxiliary variables via predecessor functions, and replacing companion/bud nodes with proof terms.
- Schema Assembly: Aggregating components into a final proof schema.

Key Contributions and Results

New Proof Schema Formalism: The paper introduces proof schemata based on point transition systems. Unlike previous schemata based on primitive recursion, this formalism supports more complex recursive structures, increasing the strength of the method.
Herbrand Systems for Inductive Proofs: The authors prove that for proof schemata (based on PTS) with at most quantifier-free cuts, Herbrand systems and schematic Herbrand sequents can be effectively computed. This extends previous results limited to primitive recursion.
Translation Algorithm: A constructive algorithm is provided to translate a significant subclass of $CLKID_\omega$ proofs into proof schemata. This establishes a direct link between cyclic proofs and the schematic CERES method, enabling the extraction of Herbrand systems from cyclic proofs.
The 2-Hydra Example: The paper applies the translation to the 2-Hydra statement, a well-known example introduced by Berardi and Tatsuta.
- The 2-Hydra statement is provable in $CLKID_\omega$ but not in $LKID$.
- The authors successfully translate the cyclic proof of the 2-Hydra statement into a proof schema based on a point transition system.
- They demonstrate that the associated point transition system is terminating (canonic).
- They extract the corresponding Herbrand system for this schema.

Significance and Claims
The primary significance of this work, as claimed by the authors, is twofold:

Expressive Power: The paper demonstrates that proof schemata based on point transition systems are capable of proving inductive statements that are not provable in $LKID$. Specifically, by translating the 2-Hydra cyclic proof, the authors show that their formalism captures inductive arguments beyond the reach of standard inductive calculi.
Unification of Frameworks: The work bridges the gap between cyclic proofs and proof schemata. By providing an algorithmic translation, the authors show that cyclic proofs can be viewed as a source for proof schemata, thereby allowing the application of schematic CERES and the direct extraction of Herbrand systems from a class of cyclic proofs.

The authors note that while the translation is restricted to a specific subclass of cyclic proofs (those with non-overlapping, non-fresh-variable inductive definitions), this subclass includes the 2-Hydra example and numerous other cases from Brotherston's thesis. The paper concludes by identifying future directions, such as extending the translation to more general cyclic proofs and comparing the resulting Herbrand systems with those extracted via higher-order recursion schemes.