A Direct Translation from Abstract Cyclic Proofs to Inductive Proofs
summary
The gist
Cyclic proof theory breaks tradition by allowing certain infinite proofs: those that can be represented by a finite graph, while satisfying a soundness condition.
In short
The work introduces a framework to translate abstract cyclic proofs into traditional finite proofs by extending cyclic proof systems with well-founded induction principles and transforming any infinite proof into a finite one while preserving its structure. The main result shows that for every $\mathcal{C}$-proof, there exists a $\mathcal{C}_{ind}$-proof of the same statement, which is crucial for applications like translating cyclic Heyting arithmetic proofs into standard Heyting arithmetic proofs.
Key concepts
- Size-change graph
- This is a bipartite graph used to model both computer science ideas and proof theory. It has nodes on one side and nodes on the other, with edges labeled either '$\ge$' (preserving) or '$>$' (progressing), helping to capture the structure of size change in proofs.
- Cyclic proof system
- This is an abstract notion of a proof where each judgment has a number of trace objects, and each rule is associated with a size-change graph. A proof is considered regular if every infinite branch in the derivation shows progressing size-change graphs, defining what constitutes a cyclic system.
- Annotation process
- This involves creating stacks ($ ext{Stack}(n)_j$), names ($ ext{Name}(n)$), and variables ($ ext{var}(n, a)$) for every node in the proof tree based on its path from the root. This detailed annotation allows researchers to extract induction hypotheses and determine their introduction order.
- $\mathcal{C}_{ind}$-proof
- This is an inductive proof derived from a cyclic proof. The core result proves that every $\mathcal{C}$-proof can be translated into a $\mathcal{C}_{ind}$-proof of the same statement, and this translation maintains the structure of the original cyclic proof, allowing for structural preservation.
Terminology used across episodes
This episode discusses
- A Direct Translation from Abstract Cyclic Proofs to Inductive Proofs · Paper Radio
- Equivalence of Intuitionistic Inductive Definitions and Intuitionistic Cyclic Proofs under Arithmetic
- A circular version of G"odel's T and its abstraction complexity
- The Size-Change Principle for Mixed Inductive and Coinductive types
- Unravelling Cyclic First-Order Arithmetic
The paper
A Direct Translation from Abstract Cyclic Proofs to Inductive Proofs · Read on arXiv
Lide Grotenhuis, Daniäl Otten
University of Amsterdam
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A Direct Translation from Abstract Cyclic Proofs to Inductive Proofs".
Paper summary: Tom: So to wrap up this paper "A Direct Translation from Abstract Cyclic Proofs to Inductive Proofs", it successfully introduces an abstract framework for cyclic proofs and demonstrates that any cyclic proof can be unravelled into a proof by induction >
Jane: The key is that the resulting inductive proof is given in an extension of the cyclic system, adding only the necessary principles to discuss well-founded induction >
Lu: It’s important because this transformation preserves structure, meaning if you forget all applications of extending rules and strip context and variables, you obtain a finite subtree of the original proof >
Meng: So for someone deploying models at scale, it means we can potentially handle these complex logical structures in our training data more robustly by mapping them to something finite >
Tom: The paper is the first of its kind formulated for a general notion of cyclic proofs rather than a specific proof system, covering things like the full modal mu-calculus >
Jane: That's really the point, it's not just about one specific system but providing a general tool for this kind of translation >
Lu: It also suggests that the finitisation problem of a cyclic system can be reduced to finding a reduction from their induced inductive system to the intended one >
Tom: So we have this abstract framework where you can take these weird infinite proofs and turn them into something finite, and it works in multi-sorted settings >
Conclusion: Tom: So, we’re wrapping up this look at "A Direct Translation from Abstract Cyclic Proofs to Inductive Proofs" by Tom and Jane >
Jane: It basically shows that these infinite cyclic proofs can be turned into finite proofs using a new set of rules >
Tom: The authors are tackling something really abstract, dealing with these size-change graphs and proof systems that have infinite branches >
Lu: The main idea is taking any of those cyclic proofs and translating it into an inductive proof, which is a more familiar structure >
Meng: So for us at the startup side, this means we can take complex logic structures that look impossible to handle and map them onto something we can actually run in production >
Tom: It seems like they're giving us a way to tame these weird infinite proofs by forcing them into a well-founded induction framework >
Jane: Right, so the big question is, what does this mean for how we think about the limits of formal systems and computation generally >
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game