💻 computer science

From Herbrand schemes to functional interpretation

This paper reformulates the core concepts of Herbrand schemes as a functional interpretation of classical sequent calculus, offering a natural computational perspective that aligns with game-theoretic approaches to analyzing Herbrand's theorem.

Original authors: Sebastian Enqvist-Pyk

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sebastian Enqvist-Pyk

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

The Big Picture: Turning a Proof into a Recipe

Imagine you have a mathematical proof. In the world of logic, a proof isn't just a "yes, this is true" stamp; it's a story of how we know it's true. Usually, to find the specific numbers or objects that make a statement true (like finding a specific key that opens a lock), mathematicians have to perform a massive, messy cleanup operation on the proof first. This is like trying to find a specific ingredient in a recipe by first rewriting the entire cookbook to remove all the chef's notes and shortcuts.

This paper proposes a new, cleaner way. The author, Sebastian Enqvist-Pyk, shows that we can look at a mathematical proof as if it were a computer program or a set of instructions right from the start. We don't need to clean it up first. By treating the proof as a program, we can directly extract the "witnesses" (the specific answers) we are looking for.

The Core Idea: The Game of "Evidence" vs. "Counter-Evidence"

To understand how this works, imagine a debate between two players:

The Prover (Verifier): Wants to prove a statement is true.
The Refuter (Falsifier): Wants to prove the statement is false.

In this paper's framework, every mathematical statement has two sides:

Evidence Type: A "ticket" the Prover holds to prove the statement.
Counter-Evidence Type: A "ticket" the Refuter holds to challenge the statement.

The paper creates a system where the Prover's strategy is a program that takes the Refuter's challenges (counter-evidence) and turns them into a winning move (evidence).

The Analogy:
Think of the Prover as a chef and the Refuter as a picky food critic.

The critic says, "This soup is bad because it lacks salt." (Counter-evidence).
The chef's program (the proof) takes that complaint and immediately says, "Ah, I see. If you say there's no salt, I will add salt and serve you this specific bowl." (Evidence).
The paper shows that for any valid mathematical proof, we can write down the exact recipe (the program) the chef uses to turn any criticism into a perfect dish.

The "Herbrand Scheme" Connection

Before this paper, there was a method called "Herbrand schemes" that did something similar, but it treated proofs like grammar rules (like a language textbook). It was a bit abstract.

This paper says: "Let's stop treating proofs like grammar and start treating them like functional programs."

Old Way: "If the proof ends with Rule X, write down Rewrite Rule Y." (Like a grammar book).
New Way: "If the proof ends with Rule X, run this specific function." (Like a computer program).

The author shows that these two ways are actually the same thing, just viewed through a different lens. By viewing it as a program, the "rules" for extracting the answer become automatic. You don't have to manually invent new rules for every step; the logic of the programming language does the work for you.

The "Drinker Paradox" and Parallel Universes

The paper uses a famous logic puzzle called the "Drinker Paradox" to explain a cool feature: Concurrency (doing things at the same time).

The Paradox: "In every pub, there is a person such that if they drink, everyone drinks."
The Strategy:
Imagine the Prover is playing a game in two parallel universes at once.

Universe A: The Prover picks a specific person (let's call him Bob) and says, "If Bob drinks, everyone drinks."
Universe B: The Refuter says, "No, Bob doesn't drink; I have a counter-example."
The Twist: Because the game is happening in parallel, the Prover can use the Refuter's answer from Universe B to win in Universe A. The Prover says, "Okay, since you said Bob doesn't drink, I will switch my strategy and pick you as the person who makes everyone drink."

The paper explains that the mathematical proof naturally contains these "parallel threads." The extracted program (the recipe) knows how to listen to the Refuter in one thread and use that information to win in the other. It's like a chess player who can see two different games happening at once and use a move from one to checkmate in the other.

What Did They Actually Achieve?

Direct Extraction: They showed how to go straight from a standard mathematical proof to a computer program that finds the answer, without needing the messy "cleanup" steps usually required.
Unified View: They proved that the "grammar" method (Herbrand schemes) and the "program" method (Functional Interpretation) are two sides of the same coin.
Game Theory: They connected this to a "game" where the Prover and Refuter play simultaneously, showing that the proof itself is a strategy for winning that game.

What They Did Not Do (Based on the Text)

They did not apply this to medical diagnoses, clinical trials, or real-world engineering problems.
They did not claim this will immediately make computers faster at solving problems (though it offers a new way to think about them).
They did not solve the Drinker Paradox itself (it was already solved); they just used it to explain their new method.

Summary in One Sentence

This paper shows that we can treat mathematical proofs like computer programs that play a game against a critic, allowing us to instantly extract the specific answers hidden inside the proof without needing to rewrite the proof first.

Technical Summary: From Herbrand schemes to functional interpretation

Problem Statement
The paper addresses the challenge of extracting Herbrand disjunctions directly from classical sequent calculus proofs without relying on cut elimination. While Herbrand's theorem is traditionally proven via cut elimination (yielding a "mid-sequent"), recent work by Afshari, Hetzl, and Leigh demonstrated that Herbrand disjunctions can be extracted directly using "Herbrand schemes"—a method treating proofs as higher-order recursion schemes. However, this approach relies on specific grammar-based rewrite rules. Conversely, functional interpretations (such as those by Gerhardy and Kohlenbach) typically operate on Hilbert-style axiomatic systems. The paper seeks to bridge these two domains: can the core mechanism of Herbrand schemes be reformulated as a functional interpretation of classical sequent calculus, thereby providing a natural computational interpretation of sequent proofs similar to game-theoretic approaches?

Methodology
The authors develop a functional interpretation for classical sequent calculus based on a typed lambda-calculus extended with a case-distinction operator. The methodology proceeds as follows:

Type Structure: The system utilizes a type theory with two atomic types: $\iota$ (individuals) and $\square$ (null type). Complex types are formed via products and function spaces. Crucially, every formula $A$ is associated with two distinct types:
- An evidence type $[A]$ (representing a witness or strategy for the "Prover").
- A counter-evidence type $\langle A \rangle$ (representing a counter-witness or strategy for the "Refuter").
  These types are defined recursively based on the logical structure of $A$ (e.g., $[\exists x A] = \iota \times \langle \neg A \rangle$ , $[\neg A] = (\langle A \rangle \to [A]) \to \langle A \rangle$ ).
Term Extraction (Term Transformers): The authors define a "term transformer" for each formula occurrence in a sequent. Given a proof $p$ of a sequent $A_1, \dots, A_n$ , the extraction associates each index $i$ with a term transformer $F^p_i$ . This transformer takes terms of counter-evidence types $\langle A_1 \rangle, \dots, \langle A_n \rangle$ as input and produces a term of evidence type $[A_i]$ .
- The extraction is defined by structural recursion on the proof $p$ , corresponding to the last inference rule used (e.g., $\exists$ , $\neg\exists$ , $\vee$ , $\neg\vee$ , cut, contraction).
- Unlike Herbrand schemes, which require ad-hoc rewrite rules for non-terminal symbols, the behavior of these extracted terms is governed entirely by the standard rewrite rules of the underlying type theory (beta-reduction, projection, and case distinction).
Logical Framework: The extraction operates within a quantifier-free system $QF$ augmented with axioms for the case-distinction operator $[u \text{ if } A \text{ else } v]$ . The main result establishes that for any proof $p$ of $A_1, \dots, A_n$ , and for any closed counter-evidence terms $u_1, \dots, u_n$ , the disjunction of the interpreted formulas holds:
$\vdash_{QF} A_1 \frac{F^p_1 \vec{u}}{u_1} \vee \dots \vee A_n \frac{F^p_n \vec{u}}{u_n}$
Here, the notation $A \frac{t}{u}$ represents the formula $A$ where evidence $t$ is pitted against counter-evidence $u$ .

Key Contributions

Reformulation of Herbrand Schemes: The paper demonstrates that Herbrand schemes can be recast as a functional interpretation of sequent calculus. The "non-terminal symbols" of a Herbrand scheme correspond to the term transformers extracted here, and the "rewrite rules" of the scheme are replaced by the intrinsic reduction rules of the lambda-calculus.
Direct Extraction without Cut Elimination: The method provides a direct algorithm to extract realizing terms (and subsequently Herbrand disjunctions) from sequent calculus proofs without performing cut elimination.
Modular Construction: The extraction process is modular; the term transformer for a proof is constructed uniformly from the transformers of its immediate sub-proofs based on the inference rule applied.
Handling Contraction: The authors utilize the case-distinction operator (from Gerhardy and Kohlenbach) to handle the branching structure introduced by contraction rules in the sequent calculus, avoiding the need for more complex "Herbrandized" type structures involving finite sets.

Results

Theorem 1 (Soundness): For any proof $p$ of a sequent $A_1, \dots, A_n$ , the extracted term transformers satisfy the functional interpretation property: the disjunction of the interpreted formulas is provable in $QF$ for any closed counter-evidence inputs.
Theorem 2 (Herbrand's Theorem): As a corollary, if an existential formula $\exists x A$ (with $A$ quantifier-free) is provable, the extraction yields a finite set of closed terms $t_1, \dots, t_n$ such that the Herbrand disjunction $A[t_1/x] \vee \dots \vee A[t_n/x]$ is provable. This is achieved by reducing the extracted term to normal form and analyzing its structure.
Strong Normalization: The underlying term system is shown to be strongly normalizing, ensuring that the extracted terms always reduce to a canonical form.

Significance and Claims
The paper claims that this work provides a "natural computational interpretation of classical sequent calculus." By reformulating Herbrand schemes as a functional interpretation, the authors argue that the connection between Herbrand's theorem and functional interpretation is more fundamental than previously realized.

Specifically, the paper highlights a conceptual link to game-theoretic approaches (such as those by Alcolei et al.). In this view:

The extracted terms represent strategies for a "Prover" in a concurrent game.
The inputs (counter-evidence terms) represent strategies for a "Refuter."
The structure of the proof corresponds to concurrent processes where the Prover can observe the Refuter's moves in one "thread" (parallel copy of the game) and use that information to determine moves in another thread.

The authors position this work as completing an emerging picture where Herbrand schemes, functional interpretations, and game semantics converge to explain the computational content of classical logic. They explicitly state that the results are self-contained and do not require prior knowledge of Herbrand schemes, though the extraction procedure was derived by closely examining the type structure of existing Herbrand scheme literature.