💻 computer science

Compression for Coinductive Infinitary Rewriting: A Generic Approach, with Applications to Cut-Elimination for Non-Wellfounded Proofs

This paper introduces a generic framework for coinductive rewriting of infinitary objects and characterizes "compression"—the ability to reduce transfinite rewriting sequences to length $\omega$ —applying this result to prove that cut-elimination in the non-wellfounded proof system $\mu\text{MALL}_\infty$ is compressible.

Original authors: Rémy Cerda, Alexis Saurin

Published 2026-04-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rémy Cerda, Alexis Saurin

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 watching a high-speed, infinite movie. This movie doesn't just play forever; it has layers. Some scenes happen so fast they seem instantaneous, while others unfold in slow motion, stretching out across "time" that isn't measured in minutes, but in complex mathematical steps called ordinals.

This paper is about a mathematical "editing trick" called Compression. It’s a way to take a movie that takes an incredibly long, complicated time to finish and "edit" it so that the same story is told in a much shorter, more manageable way, without losing any of the detail.

Here is the breakdown of the paper using everyday concepts.

1. The Problem: The "Infinite Movie" (Infinitary Rewriting)

In computer science and logic, we often deal with things that don't stop. Think of a program that generates an infinite stream of numbers, or a mathematical proof that is a tree with branches that never end.

Usually, we study these by watching them step-by-step. But sometimes, a process is so complex that it takes "infinite time" just to get through the first few layers. In math, we call these "ordinal-indexed sequences." It’s like a movie where, to see the second scene, you first have to watch an infinite number of tiny sub-scenes. This makes it very hard to "see" the final result or prove that the movie is actually going somewhere useful.

2. The Goal: The "Editing Trick" (Compression)

Compression is the ability to take a sequence of steps that is "infinitely long" and squash it down into a sequence that is much shorter (specifically, a length called $\omega$ , which is the simplest kind of infinity).

The Analogy: Imagine you are building a massive LEGO castle.

The Uncompressed Way: You build one brick, then wait an eternity, then build the next brick, then wait an eternity. Even though you are making progress, you can't actually see the castle shape for a very long time.
The Compressed Way: You realize you can "interleave" your work. You build a whole floor, then a whole wall, then a whole roof. Even though the total amount of LEGO work is the same, you can see the "shape" of the castle much sooner.

The paper proves that if a system has this "Compression Property," we can always find a way to "interleave" the steps so that we can see the final result in a much more "human-readable" (or computer-approximable) way.

3. The Innovation: The "Universal Blueprint" (Coinduction)

Before this paper, mathematicians had different "blueprints" for how to handle these infinite objects. One blueprint was for "infinite terms" (like infinite strings of text), and another was for "infinite proofs" (like infinite logic trees). They were like two different languages that didn't talk to each other.

The authors created a Generic Approach. They developed a single, master blueprint (using a concept called Coinduction) that works for everything. Whether you are dealing with infinite computer code, infinite math terms, or infinite logical proofs, you can use the same set of rules to analyze them.

4. The Application: Fixing the "Infinite Logic" (Cut-Elimination)

The authors put their new "Universal Blueprint" to the test on a very difficult subject: Non-wellfounded Proofs.

In standard logic, a proof is like a ladder: you start at the bottom and climb up to a conclusion. In "non-wellfounded" logic, the ladder might be a circle or a loop. This is useful for modeling things that happen "forever" (like a computer program that never stops), but it makes the math incredibly messy.

One of the most important tasks in logic is Cut-Elimination—which is essentially "cleaning up" a proof by removing unnecessary detours. In these infinite, looping proofs, cleaning up is a nightmare because the "detours" can be infinitely long.

The Result: The authors proved that for a specific, complex system (called $\mu\text{MALL}_\infty$ ), the "cleaning up" process can be compressed. This means that even though the proof is a wild, infinite loop, we can mathematically guarantee that the cleaning process won't get stuck in an infinite loop of "waiting" and will actually produce a clean, usable result.

Summary in a Nutshell

The paper provides a universal toolkit for mathematicians. This toolkit allows them to take incredibly complex, "infinite-time" processes and "edit" them into shorter, more efficient versions. This makes it possible to study "forever-running" programs and "looping" logic with the same precision we use for simple, finite math.

Technical Summary: Compression for Coinductive Infinitary Rewriting

1. Problem Statement

The paper addresses the challenge of unifying and formalizing infinitary rewriting—the study of computation on infinite objects (like infinite terms or non-wellfounded proof trees) where rewriting sequences may be indexed by arbitrary ordinals.

Traditionally, infinitary rewriting is studied through a topological lens (metric completion and Cauchy convergence). However, a more modern and powerful approach uses coinduction (coalgebraic types). While coinductive presentations exist for specific cases (like $\lambda$ -calculi), there has been a lack of a generic framework that can handle diverse objects—ranging from first-order terms and $\lambda$ -terms to complex non-wellfounded proof derivations—under a single mathematical umbrella.

A critical property in these systems is compression: the ability to take a rewriting sequence of an arbitrary ordinal length (which might be very "slow" or transfinite) and "compress" it into an equivalent sequence of length at most $\omega$ . Compression is vital because it ensures that finite approximations of a limit object can be computed in finite time, a property essential for the continuity and productivity of infinite processes.

2. Methodology

The authors employ a coinductive approach to redefine and unify infinitary rewriting. Their methodology follows these steps:

Generic Framework Construction: They define a general class of "syntactic objects" built by mixed induction and coinduction. They represent these as derivation trees generated by a family of rules $D$ , where each rule specifies which premises are inductive and which are coinductive.
Coinductive Rewriting Definition: Instead of using ordinal-indexed sequences, they define rewriting relations ( $\to^\gamma_\infty$ ) using coinductive rules. This allows them to represent transfinite rewriting steps through the depth of the derivation tree and the use of "later" modalities.
Characterization of Compression: They move away from transfinite induction (the standard topological method) and instead formulate a purely coinductive characterization of the compression property. They introduce two properties, $P_\delta$ (an induction hypothesis regarding finite prefixes) and $Q$ (a property regarding the ability to "jump" or "interleave" steps), to identify exactly when a system is compressible.
Application to Proof Theory: They apply this framework to the non-wellfounded proof system $\mu\text{MALL}_\infty$ (multiplicative-additive linear logic with fixed points), treating cut-elimination as a form of infinitary rewriting on derivation trees.

3. Key Contributions

A Unified Generic Framework: A mathematical structure that encompasses first-order rewriting, infinitary $\lambda$ -calculi, and non-wellfounded proof systems.
Coinductive Equivalence: A proof that the coinductive presentation of infinitary rewriting is equivalent to the traditional topological (metric-based) presentation.
A New Compression Lemma: A novel, purely coinductive characterization of the compression property (Theorem 14). This avoids the "detour" of transfinite induction and provides a direct procedure for compressing derivations.
Proof of Compression for $\mu\text{MALL}_\infty$ : The first application of this generic theory to show that cut-elimination in a complex, non-wellfounded logic satisfies the compression property.

4. Results

Characterization Theorem: The authors prove that a rewriting system has the compression property if and only if property $Q$ holds. This property essentially ensures that if a sequence of length $\delta+1$ exists, it can be restructured into a sequence of length $\delta$ by performing finite steps first.
Validation of Existing Systems: They successfully use their theorem to provide new, streamlined proofs of compression for:
- Left-linear first-order rewriting systems.
- Infinitary $\lambda$ -calculi (specifically the $abc$-infinitary variants).
Cut-Elimination Result: They prove that for $\mu\text{MALL}_\infty$ , all root rewriting steps (principal, commutative, and technical) are "finite patterns," which allows them to satisfy the requirements for property $Q$ , thereby proving that cut-elimination is compressible.

5. Significance

This paper is significant for both computer science and mathematical logic:

Theoretical Unification: It bridges the gap between the study of infinite terms (semantics/computation) and infinite proofs (logic/type theory), providing a single language to discuss both.
Practicality in Proof Theory: By proving compression for $\mu\text{MALL}_\infty$ , the authors provide a key lemma necessary for extending cut-elimination results to even broader classes of logics (like intuitionistic or classical logics with fixed points).
Foundations for Formalization: The coinductive nature of the results makes them highly suitable for formalization in proof assistants like Coq/Rocq, paving the way for automated or verified reasoning about infinite processes and non-terminating computations.