Unravelling Cyclic First-Order Arithmetic
Graham E. Leigh, University of Gothenburg Dominik Wehr, University of Gothenburg · 2025
Read Unravelling Cyclic First-Order Arithmetic by Graham E. Leigh, University of Gothenburg Dominik Wehr, University of Gothenburg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20865.txt.
Introduction
Graham Leigh and Dominik Wehr untangle cyclic proofs in a 2025 logic paper. Cyclic proof systems skip induction rules by letting proofs loop as finite graphs. Showing such a system matches the classic tree based kind is often hard, with past proofs tangled in heavy coding. The pair offer a direct route that turns cyclic proofs into plain inductive ones.
They adapt a translation built for a related cyclic system with ordinal tags. Their version also recovers a known result for Peano arithmetic about how proof strength stacks. A fresh labeled sequent form for cyclic proofs supports the move. Simpler bridges like this help logicians trust cyclic methods, which are prized for automation.
Catalog record
| CREATOR | Graham E. Leigh, University of Gothenburg Dominik Wehr, University of Gothenburg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20865
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unravelling Cyclic First-Order Arithmetic Graham E. Leigh, University of Gothenburg Dominik Wehr, University of Gothenburg Abstract Cyclic proof systems for Heyting and Peano arithmetic eschew induction axioms by accepting proofs which are finite graphs rather than trees. Proving that such a cyclic proof system coincides with its more conventional variants is often difficult: Previous proofs in the literature rely on intricate arithmetisations of the metamathematics of the cyclic proof systems. In this article, we present a simple and direct embedding of cyclic proofs for Heyting and Peano arithmetic into purely inductive, i.e. ‘finitary’, proofs by adapting a translation introduced by Sprenger and Dam for a cyclic proof system of μ FOL \mu\mathrm{FOL} with explicit ordinal approximations. We extend their method to recover Das’ result of C Π n ⊆ I Π n + 1 \mathrm{C}\Pi_{n}\subseteq\mathrm{I}\Pi_{n+1} for Peano arithmetic. As part of the embedding we present a novel representation of cyclic proofs as a labelled sequent calculus. \NewDocumentCommand \mreplace mm #2 [#1] Keywords: Cyclic proof theory; Heyting arithmetic; Peano arithmetic; proof translation Funding: This work was supported by the Knut and Alice Wallenberg Foundation [2020.0199]. 1 Introduction Cyclic proof systems admit derivations whose underlying structures are finite graphs, rather than finite trees. Such proof systems are especially well-suited to logics and theories which feature fixed points or (co-)inductively defined objects. Compared to conventional ‘inductive’ proof systems, cyclic proof systems often do not require explicit induction rules, which are instead simulated by cycles. This makes cyclic proof systems particularly well-suited to proof theoretic investigations and applications in automated theorem proving, which are both often hampered by induction rules. There are two common methods for proving that a given cyclic proof system corresponds to a particular logic or theory. The usual method is via direct soundness and completeness arguments. This approach is often not well-suited to arithmetical theories. In such cases, equivalence is instead established via proof theoretic translations between the cyclic and a conventional inductive proof system. Translating inductive proofs into cyclic proofs is usually straightforward whereas the opposite direction requires considerable effort. For Peano and Heyting arithmetic, two general strategies for obtaining such translations are present in the literature. Simpson’s approach [ 16 ] , later refined by Das [ 7 ] , formalises a soundness argument for cyclic proofs in subsystems of second-order arithmetic, using reflection and conservativity results to ‘return to’ the first-order setting. Berardi and Tatsuta [ 2 , 3 ] instead rely on Ramsey-style order-theoretic principles which can be formalised in Heyting arithmetic. Both approaches involve the formalisation of complex mathematical concepts in first- and second-order arithmetic. The literature contains other translation methods, although not applied to arithmetical theories. Of significance to this article is a method first employed by Sprenger and Dam [ 18 ] for first-order logic with fixed points \mu\mathrm{FOL} . This approach unfolds a cyclic proof until inductive hypotheses can simply be ‘read off’ the proof’s structure. The inductive proof resulting from this procedure thus naturally corresponds to an unfolding of the initial cyclic proof. In this article, we adapt Sprenger and Dam’s ‘unfolding’ method to present a proof translation between the cyclic and inductive proof system for Heyting arithmetic. The strategy can be adapted to Peano arithmetic with minor adjustments. Our construction of the inductive hypothesis in the translated proof refines those employed by Sprenger and Dam, which allows recovery Das’ logical complexity result: In cyclic \mathrm{PA} , proofs with \Pi_{n} cycles correspond to \mathrm{I}\Pi_{n+1} -proofs. We obtain a similar result for \mathrm{HA} . As part of the proof, we introduce a novel syntactic representation of the cyclic proofs resulting from the unfoldings called stack-controlled cyclic proofs . These allow a clear description the process of extracting invariants from such proofs and thus lead to a simpler argument for the translation from cyclic proofs to inductive proofs. While we only present a stack-controlled system for Heyting arithmetic, the notion readily generalises to cyclic proof systems for other logics. Furthermore, we provide detailed summaries of previous approaches to translating cyclic proof systems for Peano or Heyting arithmetic to inductive proof systems. Overview Section 2 introduces the inductive and cyclic proof systems for Heyting arithmetic. Section 3 presents stack-labelled proofs of cyclic Heyting arithmetic, a proof system designed to ease the translation. In Section 4 , we present the translation of cyclic, stack-labelled proofs to plain, inductive proofs. The full translation result is obtained in Section 5 by proving that every proof in cyclic Heyting arithmetic can be unfolded into a stack-labelled proof. We conclude in Section 6 by extending the result to Peano arithmetic, analysing the translation in terms of logical and proof size complexity and discussing the wider applicability of the method presented in this article. 2 Cyclic Heyting Arithmetic The term and formula language of first-order arithmetic is given below, fixing a countable set of variables Var . Write \mathrm{FV}(\varphi) for the set of free variables which occur unbound in a formula \varphi . \displaystyle s,t\in\textsc{Term}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=~ \displaystyle x~|~0~|~Ss~|~s+t~|~s\cdot t \displaystyle x\in\textsc{Var} \displaystyle\varphi,\psi\in\textsc{Form}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=~ \displaystyle s=t~|~\bot~|~\varphi\wedge\psi~|~\varphi\vee\psi~|~\varphi\to\psi~|~\forall x.\varphi~|~\exists x.\varphi We define \neg\varphi\coloneq\varphi\to\bot and \top\coloneq\bot\to\bot . Denote by [t/x] the usual substitution operation , substituting the term t into all free occurrences of the variable x in a term or formula. This is a partial operation, \varphi[t/x] being undefined if the free variables in t are not distinct from the bound variables in \varphi . Henceforth, writing \varphi[t/x] implicitly asserts that the substitution is defined. We sometimes write \varphi(x) as a shorthand for \varphi[x/y] for an unspecified variable y\neq x if x\not\in\mathrm{FV}(\varphi) . By analogy, the notation \varphi(t) in the vicinity of \varphi(x) then denotes \varphi[t/y] . We begin by recalling the inductive proof system for Heyting arithmetic. Definition 2.1 (Heyting arithmetic). The sequents of Heyting arithmetic are expressions \Gamma\Rightarrow\delta where \Gamma is a finite set and \delta a singular formula of first-order arithmetic. Write \Gamma,\varphi for \Gamma\cup\{\varphi\} and \Gamma,\Gamma^{\prime} for \Gamma\cup\Gamma^{\prime} . The derivation rules of \mathrm{HA} comprise of the following choice of standard rules for intuitionistic first-order logic with equality, {mathpar} \inference [ Ax ]Γ, δ ⇒ δ \inference [ \to L]Γ, φ ⇒ δ Γ ⇒ ψΓ, φ → ψ ⇒ δ \inference [ \to R]Γ, φ ⇒ ψΓ ⇒ φ → ψ \inference [ \wedge L]Γ, φ, ψ ⇒ δΓ, φ ∧ ψ ⇒ δ \inference [ \wedge R]Γ ⇒ φ Γ ⇒ ψΓ ⇒ φ ∧ ψ \inference [ \vee L]Γ, φ ⇒ δ Γ, ψ ⇒ δΓ, φ ∨ ψ ⇒ δ \inference [ \vee R]Γ ⇒ φ_iΓ ⇒ φ_1 ∨ φ_2 \inference [ \forall L]Γ, φ[t / x] ⇒ δΓ, ∀ x.φ ⇒ δ \inference [ \forall R]Γ ⇒ φ x /∈FV (Γ, ∀ x. φ)Γ ⇒∀ x.φ \inference [ \exists L]Γ, φ ⇒ δ x /∈FV (Γ, ∃ x. φ, δ)Γ, ∃ x. φ ⇒ δ \inference [ \exists R]Γ ⇒ φ[t / x]Γ ⇒∃ x. φ \inference [ \bot L]Γ, ⊥⇒ δ \inference [ = L]Γ[x / y] ⇒ δ[x / y] x, y /∈FV (s, t)Γ[s / x, t / y], s = t ⇒ δ[s / x, t / y] \inference [ = R]Γ ⇒ t = t with the following two structural rules, {mathpar} \inference [ Wk ]Γ ⇒ δΓ,