🔢 mathematics

Wider systems for linear logic with fixed points: proof theory and complexity

This paper establishes that provability in infinitary wellfounded systems for linear logic with fixed points, indexed by a computable ordinal $\alpha$ , is complete for the $\omega^{\alpha^\omega}$ level of the hyperarithmetical hierarchy, a result achieved through new proof-theoretic foundations including cut elimination and focusing.

Original authors: Anupam Das, Tikhon Pshenitsyn

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anupam Das, Tikhon Pshenitsyn

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 solve a massive, infinite maze. The goal is to find a path from the entrance (your starting question) to the exit (a proven truth). In the world of computer science and logic, this "maze" is a system of rules for proving things, and the "path" is a logical argument.

This paper is about a specific, very powerful type of maze called Linear Logic with Fixed Points. To understand what the authors did, let's break it down into three simple concepts: the Maze, the Rules, and the Difficulty.

1. The Maze: Logic with "Recursion"

Most logic systems are like a standard maze: you go from point A to B, then to C. But this system includes Fixed Points. Think of a fixed point as a "loop" or a "recursive instruction."

The Analogy: Imagine a set of instructions that says, "To solve this, you need to solve this again, but with a slightly different number."
- The "Least" Fixed Point ( $\mu$ ): This is like a loop that stops when it reaches the bottom. It's like counting down: 10, 9, 8... until you hit 0. It's a finite process that eventually finishes.
- The "Greatest" Fixed Point ( $\nu$ ): This is like a loop that goes on forever, but in a controlled way. It's like a video game level that repeats infinitely, but you are looking for a specific pattern that never breaks.

The authors are studying a version of this logic where these loops can be incredibly complex, branching out into infinite directions based on a "closure ordinal" (let's call it $\alpha$ ). Think of $\alpha$ as the depth limit or the complexity rating of the loop.

2. The Rules: Cutting the Fat and Focusing the Lens

To prove something in this maze, you have to build a tree of arguments. The authors developed two main tools to make sense of this tree:

Cut-Elimination (The "Pruning Shears"):
Imagine you are building a proof, but you keep using a shortcut that says, "We know X is true because of Y, and we know Y is true because of X." This is a circular shortcut called a "Cut." The authors proved that you can always remove these shortcuts and still get the same result. It's like taking a messy, tangled ball of yarn and cutting out the knots until you have a single, straight, clean line. This proves that if a proof exists, a "clean" proof exists too.
Focussing (The "Flashlight"):
Once the knots are cut, the proof tree is still huge. The authors introduced a "focussing" discipline. Imagine you are exploring the maze in the dark.
- Negative moves (like checking if a door is locked) are automatic; you can do them anytime.
- Positive moves (like choosing which door to open) require a decision.
  The "Focussing" rule says: "Once you decide to open a specific door, you must keep going down that specific hallway until you hit a wall or a dead end before you can make another choice." This narrows down the infinite possibilities into a manageable search path.

3. The Difficulty: How Hard is the Maze?

The big question the authors answer is: How hard is it to solve these mazes?

In computer science, we classify problems by how much "computational power" (or time) they need.

Simple problems are like checking a list.
Harder problems involve loops.
The Hyperarithmetical Hierarchy is a giant ladder of difficulty. The higher you go, the more "infinite loops" you need to solve the problem.

The Main Discovery:
The authors found a precise formula for how hard these mazes are. They proved that if your loop complexity is rated by an ordinal number $\alpha$ , the difficulty of solving the maze is exactly at the level of $\omega^{\alpha \omega}$ on the difficulty ladder.

The Metaphor: Think of the difficulty ladder as a skyscraper.
- If your loop is simple ( $\alpha = \omega$ ), the problem is on the 100th floor.
- If your loop is slightly more complex, the problem shoots up to the 1,000th floor.
- The authors showed that the height of the building is determined exactly by the formula $\omega^{\alpha \omega}$ .

Why Does This Matter?

Before this paper, we knew these systems existed, but we didn't know exactly how "heavy" they were to compute.

For Computer Scientists: It tells us the absolute limit of what these logical systems can do. If a problem is harder than this level, no computer (even a theoretical one) can solve it using these specific rules.
For Mathematicians: It connects the abstract world of "infinite trees" and "loops" to the concrete world of "computability." It shows that the structure of the logic (how the loops branch) perfectly matches the structure of mathematical difficulty.

Summary in a Nutshell

The authors took a complex, infinite logic system with recursive loops, cleaned it up by removing shortcuts, organized the search process with a flashlight, and then measured exactly how high up the "difficulty skyscraper" this system sits. They found that the height is determined by a specific mathematical formula involving the complexity of the loops, proving that these systems are incredibly powerful—capable of solving problems that are far beyond the reach of standard computers, but still within a precise, calculable limit.

1. Problem Statement

The paper investigates the algorithmic complexity of theoremhood in $\mu$ MALL $_{\alpha,\alpha}$ , a system of Multiplicative Additive Linear Logic (MALL) extended with least ( $\mu$ ) and greatest ( $\nu$ ) fixed points.

Context: Previous research (e.g., [11, 13, 21]) focused on systems with $\omega$ -branching (countable branching), which are suitable for continuous models where fixed points are reached in $\le \omega$ steps.
Gap: General models (e.g., arithmetic, modal $\mu$ -calculus) often require arbitrary closure ordinals $\alpha$ to reach fixed points. The behavior and complexity of linear logic systems with transfinite branching indexed by an arbitrary computable ordinal $\alpha$ were not fully characterized.
Core Question: What is the complexity of deciding provability in $\mu$ MALL $_{\alpha,\alpha}$ for a computable ordinal $\alpha$ ? Specifically, where does it sit within the hyperarithmetical hierarchy?

2. Methodology

The authors employ a combination of structural proof theory and computability theory to establish tight complexity bounds.

A. Proof-Theoretic Foundations

To control the search space for proofs, the authors develop two fundamental properties for $\mu$ MALL $_{\alpha,\alpha}$ :

Cut-Elimination: They prove that any provable sequent has a cut-free proof. This is achieved by defining a rank function on formulas and showing that cut-reductions strictly decrease this rank.
Focussing: They introduce a focussed calculus ( $\mu$ MALL $^{cf}_{\alpha,\alpha}$ ) that organizes proof search into asynchronous (invertible) and synchronous (non-invertible) phases. This discipline significantly narrows the proof search space by enforcing a canonical order of rule applications.

B. Formula Rank and Ordinal Arithmetic

A critical innovation is the definition of a formula rank ($rk$) using natural ordinal operations (natural sum $\oplus$ and natural product $\otimes$ ) rather than standard maximum or standard arithmetic.

Motivation: Standard maximum-based ranks fail to strictly decrease for multiplicative disjunction ( $\parr$ ) in bottom-up proof search. Natural sums ensure that every inference step in the cut-free system strictly decreases the rank of the sequent.
Bounding: They prove that for a formula $A$ in $\mu$ MALL $_{\alpha,\alpha}$ , $rk(A) < \omega^{\alpha^\omega}$ . This tight bound is essential for the complexity analysis.

C. Complexity Reductions

Upper Bound: They encode the cut-free proof search as an inductive definition over the hyperarithmetical hierarchy. Using the rank bound, they show that provability corresponds to a set computable in the $\omega^{\alpha^\omega}$ -th Turing jump.
Lower Bound: They construct a reduction from the set of true computable infinitary sentences (which is complete for the hyperarithmetical hierarchy) to $\mu$ $μ$ MALL $_{\alpha,\alpha}$ $_{α, α}$ provability.
- They encode Minsky machines (to simulate computable functions) and the inductive definition of truth for infinitary formulas into the logic.
- They utilize the focussed system to ensure the encoding is adequate (i.e., the logic correctly simulates the truth conditions of the infinitary sentences).

3. Key Contributions

Generalization to Transfinite Branching: The paper extends the study of fixed-point logics from $\omega$ -branching to systems indexed by arbitrary computable ordinals $\alpha$ .
Refined Rank Function: The introduction of a rank function based on natural ordinal arithmetic allows for a precise upper bound on the height of cut-free proof trees, which was not achievable with previous rank definitions (e.g., those in [2, 12]).
Completeness Result: The main theorem establishes that provability in $\mu$ $μ$ MALL $_{\alpha,\alpha}$ $_{α, α}$ is $\Sigma^0_{\omega^{\alpha^\omega}}$ -complete under Turing reductions.
- This generalizes previous results where $\alpha = \omega$ yielded $\Sigma^0_{\omega^\omega}$ -completeness.
- It demonstrates that the complexity of the logic scales precisely with the closure ordinal $\alpha$ .
Proof-Theoretic Tools: The paper provides a robust framework (cut-elimination and focussing) for handling infinitary rules in linear logic, serving as a testbed for structural proof theory techniques.

4. Main Results

Theorem 2.8 (Main Result):
For any computable ordinal $\alpha \ge \omega$ , the set of provable sequents in $\mu$ MALL $_{\alpha,\alpha}$ is $\Sigma^0_{\omega^{\alpha^\omega}}$ -complete.

Upper Bound: Provability is in $\Sigma^0_{\omega^{\alpha^\omega}}$ . This follows from the fact that cut-free proof search terminates with a height bounded by $\omega^{\alpha^\omega}$ , and the search space can be described by an inductive definition at that level of the hierarchy.
Lower Bound: Provability is $\Sigma^0_{\omega^{\alpha^\omega}}$ -hard. This is shown by reducing the set of true computable infinitary sentences (which characterizes the $\omega^{\alpha^\omega}$ level) to the provability problem in the logic.

Corollary 8.1:
For any $\alpha$ such that $\omega \le \alpha < \omega^\omega$ , the provability problem is $\Sigma^0_{\omega^{\omega^\omega}}$ -complete. This implies that for a wide range of ordinals, the complexity class remains the same (Turing-equivalent), specifically the level $\omega^{\omega^\omega}$ .

5. Significance

Theoretical Unification: The work unifies the understanding of fixed-point logics across different branching structures, showing that the complexity is intrinsically linked to the closure ordinal of the fixed points.
Precision in Complexity Classification: By moving beyond $\omega$ -branching, the authors reveal that the "cost" of reasoning in linear logic with fixed points can be arbitrarily high within the hyperarithmetical hierarchy, depending on the closure ordinal.
Methodological Advancement: The successful application of natural ordinal arithmetic to define proof ranks offers a new tool for analyzing infinitary proof systems where standard size measures fail.
Comparison with Other Logics: The paper notes that $\mu$ $μ$ MALL $_{\omega,\omega}$ $_{ω, ω}$ is significantly more complex ( $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ ) than infinitary action logic with multiplexing ( $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ is a "whole $\omega$ $ω$ -tower lower" in some contexts, though the paper notes a specific comparison where action logic is $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ while $\mu$ $μ$ MALL is $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ —wait, the text says action logic is $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ complete, which is a whole $\omega$ $ω$ -tower lower than $\mu$ $μ$ MALL $_{\omega,\omega}$ $_{ω, ω}$ which is $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ ? Correction based on text: The text states action logic is $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ complete, which is a whole $\omega$ $ω$ -tower lower than for $\mu$ $μ$ MALL $_{\omega,\omega}$ $_{ω, ω}$ . Actually, the text says $\mu$ $μ$ MALL $_{\omega,\omega}$ $_{ω, ω}$ is $\Sigma^0_{\omega^\omega}$ $Σ_{ω^{ω}}^{0}$ complete. Let's re-read carefully.
- Re-reading Section 8: "This logic [infinitary action logic] turns out to be $\Sigma^0_{\omega^\omega}$ -complete, a whole $\omega$ -tower lower than for $\mu$ MALL $_{\omega,\omega}$ ."
- Wait, Theorem 2.8 says $\mu$ MALL $_{\alpha,\alpha}$ is $\Sigma^0_{\omega^{\alpha^\omega}}$ . If $\alpha=\omega$ , then $\omega^{\omega^\omega}$ .
- The text says action logic is $\Sigma^0_{\omega^\omega}$ (which is $\omega^\omega$ ).
- $\mu$ MALL $_{\omega,\omega}$ is $\Sigma^0_{\omega^{\omega^\omega}}$ .
- The difference is indeed a tower of height $\omega$ . This highlights the immense complexity added by the specific combination of linear logic connectives and fixed points compared to other infinitary logics.

In summary, this paper provides a definitive classification of the complexity of linear logic with fixed points indexed by transfinite ordinals, bridging the gap between structural proof theory and the hyperarithmetical hierarchy.