Cut elimination for a non-wellfounded system for the master modality
Borja Sierra Miranda, Thomas Studer · 2025
Read Cut elimination for a non-wellfounded system for the master modality by Borja Sierra Miranda, Thomas Studer (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-2505-02700.txt.
Introduction
Borja Sierra Miranda and Thomas Studer extend a proof-theoretic cleanup operation, cut elimination, to a modal logic whose proofs may run forever. Non-wellfounded proofs are infinite trees justified by progress conditions along their branches. The authors' earlier method handled the simplest such condition, local progress, by splitting proofs into well-behaved fragments.
Real systems, though, use trace conditions, which track formulas along infinite branches. The new idea is to split a trace-based system into infinitely many local-progress calculi that together equal the original, so the older fragment method applies piece by piece. Only basic structural proof theory and corecursion are needed. They apply the machinery to K+, a modal logic with the master modality, obtaining purely syntactic cut elimination for it, a step toward taming infinite proofs with finite tools.
Catalog record
| CREATOR | Borja Sierra Miranda, Thomas Studer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 151 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-02700
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cut elimination for a non-wellfounded system for the master modality Borja Sierra Miranda, Thomas Studer Abstract In [ 11 ] , we provided a method for eliminating cuts in non-wellfounded proofs with a local-progress condition, these being the simplest kind of non-wellfounded proofs. The method consisted of splitting the proof into nicely behaved fragments. This paper extends our method to proofs based on simple trace conditions. The main idea is to split the system with the trace condition into infinitely many local-progress calculi that together are equivalent to the original trace-based system. This provides a cut elimination method using only basic tools of structural proof theory and corecursion, which is needed due to the non-wellfounded character of proofs. We will employ the method to obtain syntactic cut elimination for K + K^{+} , a system of modal logic with the master modality. [ style=definitionstyle, sibling=theorem ] [ style=theoremstyle, sibling=theorem ] Research supported by the Swiss National Science Foundation project 200021_214820. Introduction Cut elimination in non-wellfounded/cyclic proof theory is currently an active topic of research and has been previously addressed by other researchers with different tools. For example via finite approximations in [ 1 ] , via cyclic proofs in [ 2 ] , via multicuts in [ 3 ] , via runs in [ 4 ] , via infinitary rewriting in [ 6 ] , via ultrametric spaces in [ 7 ] , [ 8 ] and [ 10 ] , among others. First proof-theoretic results on establishing weakening admissibility in cyclic calculi for linear temporal logic can be found in [ 5 ] . The richness of methods is a witness of the hardness of the problem. We believe this hardness arises, among other things, from two fundamental facts: 1. In principle non-wellfounded proofs do not have a notion of height associated to them. This means that we cannot do recursion over them. 2. Verifying that a tree is a proof in the finitary setting just requires to check a “local” condition globally, in particular that every node is the conclusion of a rule instance. In the non-wellfounded setting a global condition on the branches is added, proving that this condition is preserved after the process of cut elimination is the principal headache. In [ 11 ] we defined a method to establish cut elimination and, more generally, to make proof translations between local progress sequent calculi. These are sequent calculi allowing non-wellfounded proofs such that any infinite branch goes through some rules infinitely many times. The method is based in splitting the proof in two parts, one of them amenable to tools of finitary proof theory such as recursion. The other part needs to be treated corecursively, but this treatment is generic and does not need to be reimplemented for each sequent calculus. The combination of these two facts brings really close the study of local progress calculi and finitary calculi, simplifying the proof theory of the first. We left open the question whether this simplication can be adapted to other non-wellfounded systems with more complex branch conditions. In this paper we answer this question positively providing a novel cut elimination method for a non-wellfounded system for the master modality ( \text{K}^{+} ). Cut elimination for \text{K}^{+} was already proved by Shamkanov in [ 10 ] by the method of continuous cut elimination via ultrametric spaces. We replace the use of ultrametric spaces by partitions, a simplification which will make it possible to study further levels of the recursive-corecursive iteration scheme occuring naturally in non-wellfounded proof theory. 0 Preliminaries Master modality We use this section to introduce some concepts that are needed for the rest of the paper. \text{K}^{+} is a modal logic, we will work with its formulation in the modal language with connectives \bot,\to and unary modalities \Box,\Box^{+} . The operator \Box^{+} is what we call the master modality. We use usual Kripke models for the semantics of this logic. If \mathbf{M}=(W,R,V) is a Kripke model, then the semantics for box and master formulas is as follows: \displaystyle\mathbf{M},w\vDash\Box\phi\text{ iff for any $v$ such that $wRv$ we have that $\mathbf{M},v\vDash\phi$}, \displaystyle\mathbf{M},w\vDash\Box^{+}\phi\text{ iff for any $v$ such that $wR^{+}v$ we have that $\mathbf{M},v\vDash\phi$}, where R^{+} is the transitive closure of R , i.e. wR^{+}v iff there is a (non-empty) sequence w_{0},\ldots,w_{n} such that w=w_{0}R\cdots Rw_{n}=v . Given a multiset of formulas \Gamma we will write \boxdot^{+}\Gamma to mean \Gamma,\Box^{+}\Gamma . 1 . We define the Hilbert system \text{HK}^{+} as the Hilbert system over the language of the master modality with axioms: 1. \phi\to(\psi\to\phi) ; 2. (\phi\to(\psi\to\chi))\to((\phi\to\psi)\to(\phi\to\chi)) ; 3. ((\phi\to\bot)\to\bot)\to\phi ; 4. \Box(\phi\to\psi)\to(\Box\phi\to\Box\psi) ; 5. \Box^{+}(\phi\to\psi)\to(\Box^{+}\phi\to\Box^{+}\psi) ; 6. \Box^{+}\phi\to\Box\phi ; 7. \Box^{+}\phi\to\Box\Box^{+}\phi ; 8. \Box\phi\to(\Box^{+}(\phi\to\Box\phi)\to\Box^{+}\phi) . And the rules of modus ponens: and necessitation for \Box^{+} : \phi \phi\to\psi MP \psi \phi Nec \Box^{+}\phi As mentioned in [ 9 ] , \text{HK}^{+} is sound and weakly complete with respect to the \text{K}^{+} semantics. Shamkanov’s non-wellfounded sequent calculus for \text{K}^{+} In [ 9 ] Shamkanov provided a non-wellfounded Gentzen calculus for \text{K}^{+} , let us denote it as \text{G}^{\infty}\text{K}^{+} and its version with cut as \text{G}^{\infty}\text{K}^{+}+\textsf{Cut} . In \text{G}^{\infty}\text{K}^{+} sequents are ordered pairs (\Gamma,\Delta) where \Gamma,\Delta are finite multisets of formulas. These are usually denoted as \Gamma\Rightarrow\Delta . Proofs are non-wellfounded trees, i.e. trees that are allowed to have infinite length paths from the root (infinite branches). It is easy to show that \text{G}^{\infty}\text{K}^{+} is sound and that if \text{HK}^{+}\vdash\phi then \text{G}^{\infty}\text{K}^{+}+\text{Cut}\vdash{\Rightarrow\phi} (by induction on the size of the Hilbert proof and some inversion principles of \text{G}^{\infty}\text{K}^{+}+\text{Cut} ), so \text{G}^{\infty}\text{K}^{+}+\text{Cut} is also weakly complete. Then soundness of \text{G}^{\infty}\text{K}^{+} is clear, (weak) completness will be a consequence of the cut elimination procedure we are going to describe in the paper. 1 1 1 Note that in [ 9 ] the weak completeness of \text{G}^{\infty}\text{K}^{+} (completeness in the set of theorems but not necessarily in the consequence relation given by the logic) is already proven via refutation trees. Then one could eliminate cuts via a semantical argument, since (weak) completeness was shown for the cut-free version of the calculus. As usual with non-wellfounded proofs a condition limiting the possible shape of the infinite branches needs to be added, for the sake of soundness. This condition is simplified by turning to another non-wellfounded Gentzen calculus, which we will denote as \text{G}^{\infty}_{\ell}\text{K}^{+} , whose sequents are annotated . Let us define it precisely. An annotation is just a formula or the symbol \circ , meaning that no formula is annotated. Sequents in \text{G}^{\infty}_{\ell}\text{K}^{+} are triples (\Gamma,s,\Delta) , where \Gamma,\Delta are finite multisets of formulas and s is an annotation. An additional condition is imposed on sequents, if the annotation of the sequent is a formula \phi then \Box^{+}\phi must occur in \Delta . A sequent (\Gamma,s,\Delta) is denoted by \Gamma\Rightarrow_{s}\Delta . In the case the annotation is a formula \phi , we say that the formula is in focus and if it is \circ , we say that the sequent is unfocused . Then the rules of \text{G}^{\infty}_{\ell}\text{K}^{+} are Ax \Gamma,p\Rightarrow_{s}p,\Delta Ax- \bot \Gamma,\bot\Rightarrow_{s}\Delta \Gamma\Rightarrow_{s}\Delta,\phi \Gamma,\psi\Rightarrow_{s}\Delta \to L \Gamma,\phi\to\psi\Rightarrow_{s}\Delta \Gamma,\phi\Rightarrow_{s}\psi,\Delta \to R \Gamma\Rightarrow_{s}\phi\to\psi,\Delta \Gamma,\boxdot^{+}\Pi\Rightarrow_{\circ}\phi \Box \Sigma,\Box\Gamma,\Box^{+}\Pi\Rightarrow_{s}\Box\phi,\Delta \Gamma,\boxdot^{+}\Pi\Rightarrow_{\circ}\phi \Gamma,\boxdot^{+}\Pi\Rightarrow_{\phi}\Box^{+}\phi \Box^{+} \Sigma,\Box\Gamma,\Box^{+}\Pi\Rightarrow_{s}\Box^{+}\phi,\Delta The condition on infinite branches is then that any branch has a suffix that