💻 computer science

Coalgebraic Non-Wellfounded Proofs: Recursiveness and GTC

This paper establishes a coalgebraic framework for non-wellfounded proof systems that characterizes the global trace condition (GTC) via recursive coalgebras, thereby providing a categorical formulation of soundness as the existence of unique coalgebra-to-algebra morphisms.

Original authors: Mayuko Kori

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mayuko Kori

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: Proofs That Never End

Imagine you are trying to prove a mathematical statement. Usually, you build a "proof tree" that starts with your conclusion at the top and branches down into smaller steps until you hit the ground (basic facts you know are true). Because the tree is finite, you can check it from the bottom up to make sure it's correct.

But what if your proof tree is infinite? It keeps branching forever, never hitting the ground. This happens in advanced logic systems involving loops or "fixed points" (like a definition that refers to itself).

The problem is: How do you know an infinite tree isn't just a giant, endless loop of nonsense? In the past, mathematicians had to check the whole infinite tree at once to ensure it was "sound" (logically valid). This paper introduces a new, cleaner way to check these infinite trees using a branch of math called Category Theory (think of it as the study of shapes and connections).

The Core Problem: The "Global Trace Condition" (GTC)

To stop an infinite proof from being nonsense, logicians use a rule called the Global Trace Condition (GTC).

The Analogy: The Infinite Maze
Imagine an infinite maze. You are walking through it.

The Trap: If you just walk in circles forever without ever reaching a "winning" spot, you haven't actually solved the maze.
The Rule (GTC): To win, you must visit a specific "checkpoint" (like a red flag) infinitely many times as you walk through the maze. If you keep walking forever but never hit a red flag, the path is invalid.

In logic, these "checkpoints" are usually the moments where a complex definition is "unfolded" or simplified. The GTC says: "If your proof goes on forever, it must keep simplifying itself infinitely often."

The Paper's Innovation: Turning Logic into Graphs

The author, Mayuko Kori, argues that checking this rule is hard because it requires looking at the entire infinite path at once. She proposes a new way to look at these proofs using Coalgebras.

The Analogy: The Map vs. The Traveler

Old Way: You try to check the validity of the proof by looking at the whole infinite map at once.
Kori's Way: She treats the proof not as a static map, but as a traveler moving through a graph. She uses a mathematical tool called a Coalgebra to describe the traveler's movement.

She then uses a clever trick involving Adjunctions (a type of mathematical bridge between two different worlds).

The Analogy: The "Ordinal Ladder"
Imagine the infinite maze is too confusing to navigate. Kori suggests adding a ladder (an ordinal number) to every step of the maze.

Every time the traveler hits a "checkpoint" (the red flag), they must climb down one rung of the ladder.
If the traveler goes on forever, they must climb down the ladder infinitely many times.
The Catch: You can't climb down a ladder forever! Eventually, you hit the bottom.

If the traveler can go on forever, it means they are stuck in a loop where they aren't climbing down. But if the rule (GTC) is satisfied, the traveler must be climbing down. Since you can't climb down an infinite ladder, the only way the traveler can exist is if the path is actually "well-founded" (it eventually stops or makes sense).

By adding this ladder, Kori transforms a messy, infinite, non-well-founded problem into a clean, finite, well-founded one that is easy to check.

The Main Results in Simple Terms

The "Soundness" Guarantee:
The paper proves that if an infinite proof satisfies the GTC (the rule about hitting checkpoints), it is guaranteed to be valid. It does this by showing that the proof can be translated into a "recursive" structure (a structure that is guaranteed to have a unique solution) by using the "ladder" trick.
The Two-Way Street:
The paper shows a perfect match between two concepts:
- GTC: The logical rule about infinite paths hitting checkpoints.
- Recursiveness: The mathematical property of a structure having a unique solution.
- Translation: "A proof is valid (GTC) if and only if it behaves like a well-structured, solvable puzzle (Recursive)."
Real-World Examples:
The author tests this framework on three complex logic systems:
- Modal $\mu$ -calculus: A logic used to verify computer systems (like checking if a traffic light system will ever get stuck).
- Higher-Order Fixed-Point Logics: More complex logic used in advanced programming languages.
- Circular Proofs: A specific type of proof system used in category theory.

In all three cases, the new framework successfully proved that the infinite proofs were valid, just like the old methods, but with a more unified and elegant mathematical explanation.

Summary

This paper is like inventing a new pair of glasses for mathematicians. Before, looking at infinite proofs was blurry and required checking the whole thing at once. Now, with Kori's "Coalgebraic Glasses," we can see these infinite proofs as travelers on a graph. If they follow the rules (hitting checkpoints), we can mathematically prove they are valid by showing they are climbing down an infinite ladder—a task that is impossible to do incorrectly.

This doesn't just solve a puzzle; it provides a universal language to talk about why these infinite proofs work, making it easier to build new logic systems in the future.

Technical Summary: Coalgebraic Non-Wellfounded Proofs: Recursiveness and GTC

Problem Statement

Non-wellfounded proof systems, including cyclic proofs, are essential for logics involving (co)induction, such as the modal $\mu$ -calculus and higher-order fixed-point logics. Unlike finitary proofs with finite derivation trees, these systems permit infinite derivation trees. Consequently, soundness cannot be established via standard structural induction on tree depth. Instead, these systems impose a Global Trace Condition (GTC), a constraint on infinite paths within derivation trees, to ensure soundness.

Despite various categorical approaches to cyclic proofs (e.g., $\mu$ -bicomplete categories, trace categories), providing a categorical characterisation of the GTC that guarantees soundness remains a significant challenge. The primary difficulties are:

Global vs. Local: The GTC imposes constraints on entire derivation trees, which conflicts with the local and compositional nature of standard categorical reasoning.
Infinitary Structure: Non-wellfounded proofs may be infinite, preventing the use of standard structural induction to construct semantic morphisms.
Gap in Recursive Coalgebra Theory: While recursive and well-founded coalgebras guarantee unique solutions (semantic interpretations), derivation trees of non-wellfounded proofs often yield non-wellfounded coalgebras. Existing theories do not straightforwardly explain why unique solutions exist in specific non-wellfounded cases (e.g., the "descending sequence" example from Capretta and Jeannin et al.).

Methodology

The paper develops a coalgebraic framework for non-wellfounded proof systems, modelling derivation trees as coalgebras and formulating the GTC as a condition on the graphs of these coalgebras.

1. Coalgebras of Familial Functors on Presheaves

The authors model derivation trees as coalgebras $c: C \to FC$ where $F$ is a familial functor on a presheaf category $\widehat{\mathcal{J}}$ .

Familial Functors: These are generalisations of polynomial functors defined via polynomials (diagrams of categories with specific fibration properties). They allow nodes to be labelled by judgements and branching structures to be determined by inference rules, accommodating parameters and contexts naturally.
Graphs of Coalgebras: Building on the notion of graphs of coalgebras, the paper extends the equivalence between well-foundedness of coalgebras and the absence of infinite paths in their associated graphs to endofunctors on presheaves (Theorem 1.9).

2. Adjunctions and Recursive Images

To address the non-wellfounded nature of proofs, the framework exploits the correspondence of coalgebra-to-algebra morphisms along adjunctions.

Strategy: Instead of requiring the original coalgebra $c$ to be recursive, the paper investigates whether its image under a suitable left adjoint $L$ (specifically, a base-change functor induced by an ordinal annotation) is recursive.
Mechanism: If $Coalg(L)(c)$ is recursive, and the target semantic algebra $a$ lies in the image of the right adjoint $R$ (i.e., $a \cong Alg(R)(a')$ ), then a unique coalgebra-to-algebra morphism exists for $c$ (Proposition 2.4).
Intuition: This corresponds to enriching the derivation graph with an additional dimension (ordinal annotations) obtained by pulling back along an adjunction. This expansion can render the graph well-founded even if the original is not.

3. Trace Structures and GTC

The GTC is formalised using trace structures $(pfml, prog)$:

Trace Structure: A morphism in the category of polynomials ($VPoly$) that tracks formulas (or marked formulas) along edges, combined with a subset of "progressing" edges (typically corresponding to fixed-point unfoldings).
GTC Definition: A pre-proof satisfies the GTC if every infinite path in its labelled graph admits an infinitely progressing trace along a suffix.
Ordinal Annotations: The framework constructs an abstract proof system $P^\gamma$ with judgements annotated by ordinals. The forgetful functor $u_\gamma: \mathcal{J}dg^\gamma \to \mathcal{J}dg$ induces the necessary adjunction.

Key Contributions and Results

1. Extension of Graph Theory to Presheaves

The paper extends the equivalence between well-foundedness of graphs and recursiveness of coalgebras from endofunctors on $\mathbf{Set}$ to endofunctors on presheaf categories (Theorem 1.9). This is achieved by defining graphs of coalgebras for familial functors and proving that the functor preserves intersections and inverse images.

2. Soundness via Recursive Images

The paper establishes a Soundness Theorem (Theorem 4.13): If a pre-proof $c$ satisfies the GTC, then there exists a unique coalgebra-to-algebra morphism from $c$ to any semantic algebra $a$ (provided $a$ is in the image of the lifted algebra via ordinal annotations).

This provides a coalgebraic explanation for non-wellfounded examples (like the descending sequence) that admit unique solutions but are not recursive in the standard sense.
It demonstrates that the GTC ensures the "expanded" coalgebra (with ordinal annotations) becomes recursive.

3. Characterisation of GTC and Recursiveness

The paper establishes a bidirectional characterisation between the GTC and recursiveness:

GTC $\implies$ Recursiveness: A pre-proof satisfies the GTC if and only if its image under the ordinal-annotation functor is recursive (Theorem 4.17).
Recursiveness $\implies$ GTC: A pre-proof is recursive if and only if it satisfies the GTC for all trace structures (Proposition 4.14).
This clarifies that the GTC is essentially the condition ensuring that, after transport along a suitable adjunction, the relevant coalgebra becomes recursive.

4. Concrete Instantiations

The framework is demonstrated through three proof systems:

Modal $\mu$ -calculus: A non-wellfounded proof system where the GTC corresponds to the existence of a $\nu$ -thread (infinitely unfolding a greatest fixed point). The ordinal annotations correspond to the standard approximants for greatest fixed points.
Higher-Order Fixed-Point Logics (HFLN): A system requiring tracking of both $\mu$ and $\nu$ traces, demonstrating the framework's ability to handle complex trace structures.
$\mu$ -bicomplete Categories: A non-wellfounded variant of Santocanale's circular proof system, illustrating the framework's capacity to handle non-discrete categories of judgements (where judgements vary functorially with variable assignments).

Significance and Claims

The paper claims that its primary contribution is a categorical abstraction of non-wellfounded proofs that successfully guarantees soundness.

Conceptual Insight: The GTC is not merely an operational check but a structural property ensuring that the coalgebra becomes recursive when viewed through the lens of a suitable adjunction (specifically, one guided by ordinal semantics).
Unification: The framework unifies the treatment of soundness for various non-wellfounded proof systems under a single coalgebraic mechanism involving familial functors and adjunctions.
Theoretical Gap Filling: It addresses the gap in existing recursive coalgebra theories by explaining how unique solutions can exist for non-wellfounded coalgebras via the "lifting" of semantics along adjunctions.

The authors note that while the framework establishes soundness, future work is needed to address completeness, cut-elimination, and other soundness conditions like reset conditions or bouncing threads within this coalgebraic setting.