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

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

← Home