💻 computer science

Making progress: Reducibility Candidates and Cut Elimination in the Ill-founded Realm

This paper presents two cut elimination arguments for ill-founded $\mu\mathsf{MALL}$ using Tait-Girard reducibility candidates, demonstrating that the preservation of progressivity—a key soundness criterion—follows directly from the properties of these candidates, with the second argument leveraging the topological concept of internally closed sets.

Original authors: Gianluca Curzi, Graham E. Leigh

Published 2026-02-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gianluca Curzi, Graham E. Leigh

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: Fixing Infinite Mazes

Imagine you are trying to solve a giant, infinite maze. In normal math proofs, the maze has a clear start and a clear end; you walk a path, and eventually, you hit a wall (the conclusion). This is called a well-founded proof.

But in this paper, the authors are dealing with ill-founded proofs. These are mazes that go on forever. They don't have a clear "bottom." You could walk down a corridor forever, and the path never ends.

The problem is: How do you know you aren't just walking in circles forever? How do you know the maze makes sense?

In these infinite mazes, mathematicians use a rule called "Progressivity." Think of it like a hiker's compass. Even if the path is infinite, the compass must point in a specific direction (like "North") infinitely often. If the path keeps spinning in circles without ever pointing North, the hiker is lost, and the proof is invalid.

The Main Challenge: Cutting the Knots

In logic, proofs often have "knots" called Cuts. A Cut is like a shortcut where you prove a statement $A$ , then use $A$ to prove $B$ . It's efficient, but it makes the proof messy.

The goal of Cut Elimination is to untangle these knots. You want to remove the shortcuts and show that you can get from the start to the finish using only the basic, raw steps.

The Problem: When your maze is infinite, you can't just untie the knots one by one. If you try to untie them from the bottom up, you might get stuck in an infinite loop. You need a way to untie them that guarantees you will eventually reach a clean, knot-free proof, and that you haven't broken the "North-pointing" rule (Progressivity) while doing it.

The Solution: Two New Tools

The authors, Curzi and Leigh, introduce two new "tools" (techniques) to solve this. They call them Reducibility Candidates. Think of these as special "quality control" checklists for proofs.

Tool 1: The "N-Check" (The Existence Proof)

The first tool is like a black box.

How it works: The authors define a special club of "good" proofs. They show that if you start with a proof that has a compass (Progressive), it belongs to this club.
The Magic: They prove that if a proof is in this club, it must be possible to untie all the knots eventually.
The Catch: This tool tells you that you can fix the maze, but it doesn't show you how to walk the path step-by-step. It's like a mechanic saying, "Your car will definitely start if you fix the engine," but not handing you the wrench.

Tool 2: The "E-Check" (The Topological Map)

The second tool is much more visual and clever. It uses a concept from topology (the study of shapes and spaces) called Internally Closed Sets.

The Analogy: Imagine the infinite maze is a giant, foggy forest. You can't see the whole thing at once.
The Concept: The authors define a "safe zone" (an Internally Closed Set). This is a group of paths in the forest that are "coherent." If you are walking on one path in this group, and you hit a knot, there is a matching path right next to you that helps you untie it.
The Innovation: They introduce a new rule called External Progressivity. This checks if the "safe zone" has a compass that points North.
The Result: They prove that if your maze has a compass (is Progressive), it automatically fits into this "safe zone" (is Externally Progressive). Because it's in the safe zone, they can now explicitly show a step-by-step method to untie the knots without losing the compass direction.

Why This Matters

Before this paper, fixing infinite mazes was like trying to untangle a ball of yarn while blindfolded. You might get it done, but you had to invent a new, complicated trick for every single type of yarn.

This paper provides a universal toolkit.

It proves that if a proof is "sane" (has a compass), it can be cleaned up.
It gives a concrete, step-by-step recipe (using the "External Progressivity" map) to do the cleaning.

The "Aha!" Moment

The most beautiful part of their work is the connection between the two tools.

They show that Tool 1 (the existence proof) and Tool 2 (the step-by-step map) actually agree with each other.
They prove that any proof that passes the "North-pointing" test is automatically safe enough to be untangled.

Summary in a Nutshell

Imagine you have a broken, infinite robot that keeps spinning in circles.

The Problem: You need to fix the robot so it walks in a straight line, but you can't just stop it because it never stops.
The Old Way: People tried to fix specific robots with specific hacks.
The New Way (This Paper): The authors built a "Universal Repair Kit."
- First, they proved that if the robot has a "North Sensor" (Progressivity), it can be fixed.
- Second, they built a "GPS Map" (External Progressivity) that shows exactly how to rewire the robot's circuits to remove the loops, ensuring the North Sensor still works perfectly at the end.

This is a huge step forward because it gives mathematicians a reliable, standard way to handle infinite logic problems, making the "ill-founded" realm much less scary and much more manageable.

1. Problem Statement

The paper addresses a central challenge in ill-founded (non-wellfounded) proof theory: ensuring that infinitary cut elimination preserves global correctness criteria.

Context: Ill-founded proof systems (e.g., for inductive and coinductive reasoning) allow proofs to be infinite in depth. Unlike well-founded systems where soundness is local, these systems rely on global conditions like the progressivity (or trace) condition. A derivation is "progressing" if every infinite branch contains a "good" thread (an infinite sequence of formulas where a greatest fixed-point $\nu$ unfolds infinitely often).
The Challenge: When applying cut elimination to infinite proofs, the process is an infinite rewriting sequence. It is technically difficult to prove that:
1. The rewriting process converges to a limit proof (productivity).
2. The limit proof remains progressing (preserves soundness).
Limitations of Existing Work: Previous methods (e.g., by Baelde et al., Santocanale) often rely on bespoke, system-specific arguments (like truth semantics) or specific rewriting strategies that lack generality and robustness across different fixed-point logics.

2. Methodology

The authors adapt the reducibility candidates technique, originally developed by Tait and Girard for normalization in System F and Gödel's System T, to the setting of ill-founded proofs. They introduce two distinct notions of reducibility candidates to tackle the problem:

A. The Framework: Ill-founded $\mu$ MALL

The work focuses on $\mu$ MALL (Multiplicative Additive Linear Logic with least and greatest fixed points). The system uses a one-sided sequent calculus with infinitary derivations (infinite trees).

Key Concepts:
- Threads/Traces: Sequences of formulas along a branch.
- Good Threads: Threads where a $\nu$ -formula unfolds infinitely often.
- Progressing Derivations: Derivations where every branch bears a good thread.
- $\omega$ -Normalisation: A derivation is $\omega$ -normalisable if there exists a depth-increasing sequence of cut reductions converging to a cut-free, progressing derivation.

B. The Two Reducibility Arguments

The paper presents two distinct cut elimination arguments based on reducibility candidates:

1. N-Reducibility Candidates (Based on Cut Elimination)

Definition: A set of derivations is an N-reducibility candidate if it is closed under orthogonality with respect to a specific set $N$ (the set of $\omega$ -normalisable derivations).
Approach: This argument follows a standard "computational totality" proof structure.
- It defines an interpretation of formulas as sets of derivations (reducibility candidates).
- It proves Local Soundness: If the premises of a rule are reducible, the conclusion is reducible.
- It uses a contradiction argument: Assuming a progressing derivation is not reducible, one can construct an infinite branch where ordinal approximations of the fixed points decrease infinitely often, contradicting the well-foundedness of ordinals.
Outcome: This proves that all progressing derivations are $\omega$ -normalisable. However, it is non-constructive regarding the specific rewriting strategy and does not explicitly track the preservation of progressivity during the reduction steps.

2. E-Reducibility Candidates (Based on External Progressivity)

Motivation: To provide a more explicit and insightful argument that directly tracks the preservation of the progressivity condition.
Key Innovation: External Progressivity & Internally Closed (IC) Sets.
- The authors introduce External Progressivity: A derivation is externally progressing if every Internally Closed (IC) set of branches bears a good external thread.
- IC Sets: A set of branches is IC if it is closed and "coherent." Coherence means that if two branches meet at a cut, the set contains both branches, and the cut formulas form a dual pair. IC sets represent the specific subtrees visited by a cut elimination procedure.
- External vs. Internal: Threads starting from the root are "external"; those starting from cut formulas are "internal." Cut elimination annihilates internal threads but must preserve external ones.
Approach:
- The authors define E-reducibility candidates based on the set $E$ of externally progressing derivations.
- They utilize Multicut $\omega$ -reduction sequences. Instead of single cuts, they manipulate "multicuts" (macro-rules representing trees of consecutive cuts) to handle permutations and ensure fairness.
- They prove that if a derivation is externally progressing, any fair multicut reduction path generates a limit derivation that is cut-free and progressing.
Outcome: This argument explicitly certifies that the limit of the rewriting process preserves the progressivity condition.

3. Key Contributions

Generalization of Reducibility Candidates: The paper successfully adapts the Tait-Girard reducibility method to the ill-founded realm, moving away from system-specific semantic arguments to a more modular, proof-theoretic approach.
Two Distinct Proofs:
- A non-constructive existence proof (via N-reducibility) confirming that progressing proofs are normalisable.
- A constructive, explicit proof (via E-reducibility) that demonstrates how progressivity is preserved during the reduction process using IC sets and external threads.
Concept of External Progressivity: The introduction of "external progressivity" and "internally closed sets" provides a new, robust tool for analyzing the interaction between cut elimination and global correctness. It clarifies the relationship between the structure of the proof tree and the rewriting strategy.
Logic Independence: The methodology is designed to be robust and generalizable. While presented for $\mu$ MALL, the authors argue it extends to intuitionistic logic ( $\mu$ LJ) and higher-order fixed-point logics via standard embeddings.

4. Main Results

Theorem 60 (Soundness): Every progressing derivation in ill-founded $\mu$ MALL belongs to the reducibility candidate $J\Gamma K_N$ . Consequently, every progressing derivation is $\omega$ -normalisable.
Theorem 73: Every externally progressing derivation is $\omega$ -normalisable.
Corollary 61 (Cut Elimination): If a derivation $d$ $d$ is progressing ( $d \in P$ $d \in P$ ), then it is $\omega$ $ω$ -normalisable ( $d \in N$ $d \in N$ ).
- Significance: This confirms that the global correctness condition (progressivity) is preserved under infinitary cut elimination.
Equivalence in Cut-Free Setting: The paper proves that for cut-free derivations, "progressing" and "externally progressing" are equivalent conditions.

5. Significance

This work represents a significant step toward a uniform proof-theoretic framework for ill-founded systems.

Robustness: By relying on reducibility candidates rather than bespoke semantic arguments, the results are more likely to generalize to other logics (e.g., higher-order arithmetic, modal $\mu$ -calculi).
Clarification of Mechanism: The second argument (E-reducibility) demystifies why cut elimination preserves progressivity. It shows that the "external" nature of the correctness condition (invariant under the specific "internal" cuts being removed) is the key to the proof.
Future Directions: The authors propose extending this framework to other global correctness criteria (e.g., semantic runs, automata-based conditions, bouncing threads) and other logics, suggesting a path toward a comprehensive theory of infinitary proof systems.

In summary, Curzi and Leigh provide a rigorous, modular solution to the cut elimination problem in ill-founded logic, bridging the gap between infinitary rewriting and global soundness criteria through the innovative application of reducibility candidates.