Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics
Listen
Radio episode about this paper
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: "Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics".
Jane: Here's the gist of the paper. A labelled and non-wellfounded calculus for the bimodal provability logic CS is presented by modeling its Kripke-like semantics and proving its soundness and completeness with respect to a primitive decision procedure.
Tom: Logic Definition and Semantics The paper introduces the basic bimodal provability logic CS, defined as the smallest subset of L□△ containing classical tautologies and specific axiom schemas like (K□) □(A → B) → (□A → □B).
Jane: The logic is formulated in a two-sorted modal propositional language L□△ with modalities □ and △.
Tom: A Carlson model M is defined as a tuple ⟨W, ≺, M0, M1, V⟩ where the evaluation of formulas depends on the subsets M0 and M1 corresponding to the two modalities.
Title and authors: Tom: So, focusing on the title and authors of "Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics", what’s the main idea behind that name?
Jane: Well, it points to two big things: non-wellfounded proofs, which means they allow for infinite loops or cycles in the reasoning process, and labelled sequents.
Lu: The labels are a way to track things inside the calculus so we can keep everything organized and ensure we’re dealing with well-behaved structures.
Meng: But what does that actually change about how you prove things in this logic compared to standard systems?
Tom: It suggests they are using techniques from cyclic proof theory, which is a specific way of handling these kinds of non-wellfounded structures to enforce the second-order property of converse wellfoundedness.
Jane: That means they’re not just writing down rules; they’re making sure the proof structure itself respects the underlying logic's requirements for being sound.
Lu: And this leads directly into how they construct their system, which is a labelled and non-wellfounded calculus for CS that models the Kripke-like semantics of this logic.
The paper's summary: Tom: Let’s look at what the abstract says about the paper "Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics".
Jane: It summarizes that they present a labelled and non-wellfounded calculus for the basic bimodal provability logic CS. They model the Kripke-like semantics of this logic, which is how we define what formulas mean in terms of truth conditions.
Lu: The key part is that they prove soundness and completeness with respect to the semantics and provide a primitive decision procedure together with a way to extract countermodels.
Meng: A decision procedure sounds great for automation, but extracting countermodels from failed proofs means if something isn't provable, we can actually see why it’s not provable by finding a model that fails.
Tom: Right. So instead of just saying "this is unprovable," we get a concrete example of where the system breaks down, which is super useful for debugging AI models.
Jane: It’s about bridging the gap between theoretical logic and practical reasoning, giving us both a formal system and a way to test it against actual failure cases.
The paper's improvements: Lu: The paper points out that they combine non-wellfounded proofs with labelled sequents similarly to what was done for GL, iGL, and Grz variants.
Tom: So the improvement here is specifically tailoring these existing proof system techniques to the bimodal provability logic CS, which is a new addition in this area.
Meng: What about the actual mechanics of their proof search strategy? Is it just some standard search algorithm they adapted?
Lu: No, they show that their proof search strategy alternates between saturation phases and label phases, and crucially, both of these phases terminate.
Jane: That termination is important because it’s what allows them to build a primitive decision procedure for CS by applying this alternating strategy to a given sequent.
Tom: So the improvement isn't just the system itself, but that the entire process—from checking if something is provable to finding a countermodel—is guaranteed to finish.
Conclusion: Jane: So we’ve seen that this paper gives us a complete system for bimodal provability logic CS, modeled by its Kripke-like semantics, and it comes with a decision procedure.
Tom: It means AI systems can now verify formulas in CS by checking if a sequent is derivable or by constructing a countermodel M where the sequent S doesn't hold.
Lu: And the extraction of those countermodels from saturated sequents is a powerful tool for understanding where the logic fails.
Meng: For deployment, this means we have a rigorous way to check if our complex inference engines are sound under these specific provability rules, rather than just hoping they work in practice.
Lalam: I’m confident in this direction because the logic is being grounded in theories T and U extending Elementary Arithmetic with very specific interaction axioms.
Jane: It sounds like a solid foundation for future work, especially if they can extend this to other logics or even Kripke-incomplete logics later on.
Tom: Yeah, so the paper "Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics" gives us a formal way to handle these complex provability structures, and it sets up a path for building more robust reasoning systems.
Justus Becker
University of Birmingham
cs.LO, math.LO
Submitted: 2025-06-17
Updated: 2026-11-16
Comments: 40 pages
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 79/100
The gist: A labelled and non-wellfounded calculus for the bimodal provability logic CS is presented by modeling its Kripke-like semantics and proving its soundness and completeness with respect to a primitive…
Key concepts
- Bimodal Provability Logic CS
- CS is a specific logical system defined by classical tautologies and axioms like (K□) □(A → B) → (□A → □B). It uses two modalities, □ and △, to express provability concepts. The logic is studied through its Kripke-like semantics.
- LabCS∞ Calculus
- This is a bi-labelled non-wellfounded calculus for CS. It uses labels (x, y, z...) and relational atoms (xRy or xSy) to structure proofs. Crucially, it allows for non-wellfounded proofs using coinductive trees with a progress condition.
- Decision Procedure Extraction
- The paper develops a method to turn the proof search strategy into a primitive decision procedure. This is achieved by ensuring that each phase of the alternating search (saturation and label) terminates, leading to an algorithm that either finds a valid proof or extracts a countermodel.
Terminology
Summary
A labelled and non-wellfounded calculus for the bimodal provability logic CS is presented by modeling its Kripke-like semantics and proving its soundness and completeness with respect to a primitive decision procedure. p. 0 We will prove soundness and completeness of this system
with respect to the semantics and provide a primitive decision procedure
together with a way to extract countermodels. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs.Where the paper says it
Logic Definition and Semantics
The paper introduces the basic bimodal provability logic CS, defined as the smallest subset of L□△ containing classical tautologies and specific axiom schemas like (K□) □(A → B) → (□A → □B). The logic is formulated in a two-sorted modal propositional language L□△ with modalities □ and △. p. 1 The
latter is obtained by a countermodel construction, which we get by a primitive
proof search strategy, giving us a decision procedure for CS. 2 Bimodal Provability Logic
We work in a two-sorted modal propositional language with modalities, □ and △. Definition 2 ([7]). A Carlson model M is a tuple ⟨W, ≺, M0, M1, V ⟩ such that
⟨W, ≺, V ⟩ is a GL-model with two subsets M0, M1 ⊆ W. Theorem 3 ([28]). For any formula A ∈ L□△: CS ⊢ A iff for all Carlson
models M: M ⊩ A.Where the paper says it
Where the paper says it
Where the paper says it
Calculus Construction
The authors present the labCS∞ calculus, a bi-labelled non-wellfounded calculus for CS. This system uses labels Lab = In the following section, we introduce the syntax and Kripke-like semantics
for CS. In section 3, we introduce the rules of a non-wellfounded and labelled
proof system for this logic, and prove semantic soundness and completeness. While wellfounded
proofs are often seen as top-down inductively definable trees, non-wellfounded
proofs are defined as coinductive trees, allowing for infinitary branches. Our
system is inspired by the labelled, non-wellfounded systems for GL and IGL (an
intuitionistic version of GL with explicit ♢) from [8].x, y, z, … and relational atoms of the form xRy or xSy. The rules include structural rules like →R and →L. p. 1Where the paper says it
Where the paper says it
Soundness and Completeness Proof Strategy
Soundness is established via Lemma 8 (Local Soundness), which shows that truth is preserved in rule applications across all Carlson models. Theorem 10 proves soundness by contradiction, showing that if CS ⊮ S, an infinite non-progressing branch must exist, contradicting the validity of T. p. 7 As labCS∞ ⊢ S, it must be witnessed by some proof T , where
every branch of T is either finite or progressing. We now extract an infinite
branch (Si)i<ω from T which will not be progressing, contradicting the fact
that T is a proof. As we have a fully invertible calculus, we are able
to consider a technique which is relatively simple and has been inspired by an
unpublished (personally communicated) completeness proof for the labelled and
non-wellfounded system for classical GL from [8]. Let us define a proof search procedure which we define in two phases. Note that
any open leaves which our proof search strategy creates must be fully saturated. Let us show in the following lemma how to extract a countermodel from such a
sequent.Where the paper says it
Where the paper says it
Where the paper says it
Decision Procedure Extraction
The proof search strategy is designed to be well-defined by ensuring that each phase terminates, as shown in Lemma 12 (Saturation) and Lemma 13 (Label Phase). This leads to a primitive decision procedure for CS by applying the strategy to a given sequent ⇒ x: A and obtaining either a valid proof or extracting a countermodel. p. 1 In section 3, we introduce the rules of a non-wellfounded and labelled
proof system for this logic, and prove semantic soundness and completeness. The
latter is obtained by a countermodel construction, which we get by a primitive
proof search strategy, giving us a decision procedure for CS. Corollary 9. Given an instance of a rule of labCS∞, with conclusion S and
premisses S1, .Where the paper says it
Where the paper says it
Future Directions
Future work involves investigating modal extensions of this calculus, particularly for Kripke-incomplete logics like ER by introducing a different progress condition. There is also an interest in reducing these labelled proof systems to simple sequent calculi without labels while retaining the non-wellfounded aspect. p. 3 While wellfounded
proofs are often seen as top-down inductively definable trees, non-wellfounded
proofs are defined as coinductive trees, allowing for infinitary branches. Our
system is inspired by the labelled, non-wellfounded systems for GL and IGL (an
intuitionistic version of GL with explicit ♢) from [8]. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. Since then,
the concept of provability logic has been extended towards more and more complex logics: for instance, Japaridze’s polymodal provability logic GLP [16] or logics of non-standard provability [10,13,24,31].Where the paper says it
Where the paper says it
References
1 Afshari, B., Leigh, G.E., Menéndez Turata, G.: Uniform interpolation from cyclic proofs: The case of modal mu-calculus. p. 0 As
the labelled structure internalises part of the semantics, we can sometimes read
out countermodels from the leaves of failed proof search, which is a common
feature of labelled calculi. Cyclic and more generally non-wellfounded proofs were originally developed
for the modal µ-calculus [20] and later also adapted for first-order logic handling
induction [5,6]. As
the labelled structure internalises part of the semantics, we can sometimes read
out countermodels from the leaves of failed proof search, which is a common
feature of labelled calculi. Cyclic and more generally non-wellfounded proofs were originally developed
for the modal µ-calculus [20] and later also adapted for first-order logic handling
induction [5,6].Where the paper says it
Where the paper says it
2 Ardeshir, M., Mojtahedi, M.: The σ1-provability logic of ha. p. 2 ii]
that there are theories T, U extending Elementary Arithmetic such that their
joint provability logic coincides with CS. Notice, however, that these theories
will not be natural, as the two modalities know essentially as little as possible about each other: the only interaction axioms are 4△□ and 4□△, which are
purely consequences of the provable Σ1-completeness of T and U. ii]
that there are theories T, U extending Elementary Arithmetic such that their
joint provability logic coincides with CS. Notice, however, that these theories
will not be natural, as the two modalities know essentially as little as possible about each other: the only interaction axioms are 4△□ and 4□△, which are
purely consequences of the provable Σ1-completeness of T and U. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5. However, only much later have labelled systems been applied widely to nonclassical logics [11,19,26,30]. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5. However, only much later have labelled systems been applied widely to nonclassical logics [11,19,26,30].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
3 Artemov, S.N., Beklemishev, L.D.: Provability logic. p. 0 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
4 Beklemishev, L.D.: On bimodal logics of provability. p. 0 Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5. However, only much later have labelled systems been applied widely to nonclassical logics [11,19,26,30]. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5. However, only much later have labelled systems been applied widely to nonclassical logics [11,19,26,30].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
5 Brotherston, J.: Cyclic proofs for first-order logic with inductive definitions. p. 3 The second proof theoretic tool we use are non-wellfounded proofs. Those
are a generalisation of cyclic proofs which have been introduced for the modal
µ-calculus [20] and later also adapted for other logics, such as propositional
dynamic logic [9] or logics with inductive definitions [5,27]. The second proof theoretic tool we use are non-wellfounded proofs. Those
are a generalisation of cyclic proofs which have been introduced for the modal
µ-calculus [20] and later also adapted for other logics, such as propositional
dynamic logic [9] or logics with inductive definitions [5,27].Where the paper says it
Where the paper says it
6 Brotherston, J., Simpson, A.: Sequent calculi for induction and infinite descent. p. 0 As
the labelled structure internalises part of the semantics, we can sometimes read
out countermodels from the leaves of failed proof search, which is a common
feature of labelled calculi. Cyclic and more generally non-wellfounded proofs were originally developed
for the modal µ-calculus [20] and later also adapted for first-order logic handling
induction [5,6]. As
the labelled structure internalises part of the semantics, we can sometimes read
out countermodels from the leaves of failed proof search, which is a common
feature of labelled calculi. Cyclic and more generally non-wellfounded proofs were originally developed
for the modal µ-calculus [20] and later also adapted for first-order logic handling
induction [5,6]. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
7 Carlson, T.J.: Modal logics with several operators and provability interpretations. p. 0 Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory.Where the paper says it
Where the paper says it
8 Das, A., van der Giessen, I., Marin, S.: Intuitionistic Gödel-Löb Logic, à la Simpson: Labelled Systems and Birelational Semantics. p. 3 While wellfounded
proofs are often seen as top-down inductively definable trees, non-wellfounded
proofs are defined as coinductive trees, allowing for infinitary branches. Our
system is inspired by the labelled, non-wellfounded systems for GL and IGL (an
intuitionistic version of GL with explicit ♢) from [8]. While wellfounded
proofs are often seen as top-down inductively definable trees, non-wellfounded
proofs are defined as coinductive trees, allowing for infinitary branches. Our
system is inspired by the labelled, non-wellfounded systems for GL and IGL (an
intuitionistic version of GL with explicit ♢) from [8].Where the paper says it
Where the paper says it
9 Docherty, S., Rowe, R.N.S.: A non-wellfounded, labelled proof system for propositional dynamic logic. p. 0 Cyclic and more generally non-wellfounded proofs were originally developed
for the modal µ-calculus [20] and later also adapted for first-order logic handling
induction [5,6]. In the recent decade non-wellfounded proof theory has been also
adapted for Arithmetic [27] and other logics, such as propositional dynamic logic
[9]. Cyclic and more generally non-wellfounded proofs were originally developed
for the modal µ-calculus [20] and later also adapted for first-order logic handling
induction [5,6]. In the recent decade non-wellfounded proof theory has been also
adapted for Arithmetic [27] and other logics, such as propositional dynamic logic
[9].Where the paper says it
Where the paper says it
10 Feferman, S.: Arithmetization of metamathematics in a general setting. p. 1 2 Bimodal Provability Logic
We work in a two-sorted modal propositional language with modalities, □ and △. As we are in a classical setting, it is enough to consider → and ⊥ as the only
logical connectives (where ⊥ is a connective of arity zero), besides a countable
set of propositional atoms Prop = {p, q, r, . 2 Bimodal Provability Logic
We work in a two-sorted modal propositional language with modalities, □ and △. As we are in a classical setting, it is enough to consider → and ⊥ as the only
logical connectives (where ⊥ is a connective of arity zero), besides a countable
set of propositional atoms Prop = {p, q, r, . 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
11 Gabbay, D.M.: Labelled deductive systems. p. 3 1 The Calculus labCS∞
The calculus we present is based on the relational semantics introduced in the
previous section, using labels. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5. 1 The Calculus labCS∞
The calculus we present is based on the relational semantics introduced in the
previous section, using labels. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5.Where the paper says it
Where the paper says it
12 Garg, D., Genovese, V., Negri, S.: Countermodels from sequent calculi in multimodal logics. p. 0 Here, we use a two-sorted
approach to labels by using two kinds of relational atoms (see [12] for a multilabelled system), which allows us to capture two modalities simultaneously. As
the labelled structure internalises part of the semantics, we can sometimes read
out countermodels from the leaves of failed proof search, which is a common
feature of labelled calculi. Here, we use a two-sorted
approach to labels by using two kinds of relational atoms (see [12] for a multilabelled system), which allows us to capture two modalities simultaneously. As
the labelled structure internalises part of the semantics, we can sometimes read
out countermodels from the leaves of failed proof search, which is a common
feature of labelled calculi.Where the paper says it
Where the paper says it
13 Henk, P., Pakhomov, F.: Slow and ordinary provability for peano arithmetic. p. 0 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. arXiv:2506. 14307v1 [cs. arXiv:2506. 14307v1 [cs. arXiv:2506. 14307v1 [cs. arXiv:2506. 14307v1 [cs.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
14 Iemhoff, R.: Reasoning in circles. In: van Eijck, J., Joosten, J., Iemhoff, R. (eds.) Liber Amicorum Alberti. A Tribute to Albert Visser., pp. 165–178. College Publications, United Kingdom (2016)
15 Japaridze, G.K.: The polymodal logic of provability. p. 0 In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. Since then,
the concept of provability logic has been extended towards more and more complex logics: for instance, Japaridze’s polymodal provability logic GLP [16] or logics of non-standard provability [10,13,24,31]. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. Since then,
the concept of provability logic has been extended towards more and more complex logics: for instance, Japaridze’s polymodal provability logic GLP [16] or logics of non-standard provability [10,13,24,31]. Similarly, we can describe
bimodal provability logics in terms of the provability of two recursively enumerable (r. ) theories T, U, where □ is interpreted as a provability predicate for T
and △ as the provability predicate for U. Similarly, we can describe
bimodal provability logics in terms of the provability of two recursively enumerable (r. ) theories T, U, where □ is interpreted as a provability predicate for T
and △ as the provability predicate for U.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
16 Japaridze, G.K.: The modal logical means of investigation of provability. p. 2 Rules of the Hilbert Axiomatisation for CS
Recall that the logic GL is sound and complete with respect to the provability of PA [29]. More formally, this means that we interpret modal formulas as
arithmetic sentences such that the logical connectives are preserved and □ is
interpreted as a provability predicate; then for any modal formula A and any
such interpretation (·)
∗ we have GL ⊢ A iff PA ⊢ A∗
. Rules of the Hilbert Axiomatisation for CS
Recall that the logic GL is sound and complete with respect to the provability of PA [29]. More formally, this means that we interpret modal formulas as
arithmetic sentences such that the logical connectives are preserved and □ is
interpreted as a provability predicate; then for any modal formula A and any
such interpretation (·)
∗ we have GL ⊢ A iff PA ⊢ A∗
.Where the paper says it
Where the paper says it
17 Kanger, S.: Provability in Logic. p. 0 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
18 Lyon, T.S.: Unifying sequent systems for gödel-löb provability logic via syntactic transformations. p. 1 Since then, a lot of variants of cyclic systems for similar logics, such as iGL [14,25] and Grz [22], have been developed. For bimodal
provability logic, however, no sequent system has been introduced thus far. Since then, a lot of variants of cyclic systems for similar logics, such as iGL [14,25] and Grz [22], have been developed. For bimodal
provability logic, however, no sequent system has been introduced thus far. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
19 Negri, S.: Proof analysis in modal logic. p. 0 Bimodal provability logics extend
unimodal logics, such as GL, by also incorporating the provability of a second
theory. A useful technique in the proof theory of modal logic is the usage of labelled sequents, which are syntactically enriched sequents utilising the Kripke
frame correspondence of modal logics (see [19,26,30]). Bimodal provability logics extend
unimodal logics, such as GL, by also incorporating the provability of a second
theory. A useful technique in the proof theory of modal logic is the usage of labelled sequents, which are syntactically enriched sequents utilising the Kripke
frame correspondence of modal logics (see [19,26,30]). 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
26 Simpson, A.: The Proof Theory and Semantics of Intuitionistic Modal Logic. p. 0 The system is obtained by modelling the
Kripke-like semantics of this logic. As in [8], we enforce the second-order
property of converse wellfoundedness by using techniques from cyclic
proof theory. The system is obtained by modelling the
Kripke-like semantics of this logic. As in [8], we enforce the second-order
property of converse wellfoundedness by using techniques from cyclic
proof theory. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
27 Simpson, A.: Cyclic arithmetic is equivalent to peano arithmetic. p. 0 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA.Where the paper says it
Where the paper says it
28 Smoryński, C.: Self-Reference and Modal Logic. p. 0 We will prove soundness and completeness of this system
with respect to the semantics and provide a primitive decision procedure
together with a way to extract countermodels. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs. We will prove soundness and completeness of this system
with respect to the semantics and provide a primitive decision procedure
together with a way to extract countermodels. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs.Where the paper says it
Where the paper says it
29 Solovay, R.M.: Provability interpretations of modal logic. p. 0 We will prove soundness and completeness of this system
with respect to the semantics and provide a primitive decision procedure
together with a way to extract countermodels. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs. We will prove soundness and completeness of this system
with respect to the semantics and provide a primitive decision procedure
together with a way to extract countermodels. Keywords: Provability logic · Modal Logic · Bimodal logic · Labelled
sequents · Non-wellfounded proofs.Where the paper says it
Where the paper says it
30 Vigano, L.: Labelled Non-Classical Logics. p. 8 We will do the latter here. As we have a fully invertible calculus, we are able
to consider a technique which is relatively simple and has been inspired by an
unpublished (personally communicated) completeness proof for the labelled and
non-wellfounded system for classical GL from [8]. We will do the latter here. As we have a fully invertible calculus, we are able
to consider a technique which is relatively simple and has been inspired by an
unpublished (personally communicated) completeness proof for the labelled and
non-wellfounded system for classical GL from [8].Where the paper says it
Where the paper says it
31 Visser, A.: Peano’s smart children: A provability logical study of systems with built-in consistency. p. 0 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA. 1 Introduction
Modal provability logics originate from interpreting the □-modality as “it is provable that” in a sufficiently strong (usually arithmetic) theory. In [29], Robert
Solovay proved completeness of the modal logic GL with respect to the provability of Peano Arithmetic (PA) as well as the completeness of the modal logic S
(also referred to as GLS) with respect to the true provability of PA.Where the paper says it
Where the paper says it
32 Visser, A.: A course on bimodal provability logic. p. 0 14307v1 [cs. LO] 17 Jun 2025
A Non-Wellfounded and Labelled Sequent
Calculus for Bimodal Provability Logic
Justus Becker
University of Birmingham, Birmingham, UK
jvb443@student. Labelled systems can be traced back to Kanger
[17], who used them to introduce the first cut-free system for the modal logic
S5. However, only much later have labelled systems been applied widely to nonclassical logics [11,19,26,30].Where the paper says it
Where the paper says it
E0079-4, a Tribute to Dirk van Dalen
Conclusion
The paper introduces a non-wellfounded calculus for the bimodal provability logic CS by modeling its Kripke-like semantics and proving its soundness and completeness with respect to a primitive decision procedure. The system is obtained by modelling the Kripke-like semantics of this logic. p. 0 We present a labelled and non-wellfounded calculus for the
bimodal provability logic CS. The system is obtained by modelling the
Kripke-like semantics of this logic. We present a labelled and non-wellfounded calculus for the
bimodal provability logic CS. The system is obtained by modelling the
Kripke-like semantics of this logic. We present a labelled and non-wellfounded calculus for the
bimodal provability logic CS. The system is obtained by modelling the
Kripke-like semantics of this logic. We present a labelled and non-wellfounded calculus for the
bimodal provability logic CS. The system is obtained by modelling the
Kripke-like semantics of this logic.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
1 Afshari, B., Leigh, G.E., Menéndez Turata, G.: Uniform interpolation from cyclic proofs: The case of modal mu-calculus. In: Das, A., Negri, S. (eds.) Automated Reasoning with Analytic Tableaux and Related Methods. pp. 335–353. Springer International Publishing, Cham (2021)
2 Ardeshir, M., Mojtahedi, M.: The σ1-provability logic of ha. Annals of Pure and Applied Logic 169(10), 997–1043 (2018). https://doi.org/10.1016/j.apal.2018.05
3 Artemov, S.N., Beklemishev, L.D.: Provability logic. In: Gabbay, D., Guenthner, F., (eds.) Handbook of Philosophical Logic, 2nd Edition, pp. 189–360. Springer Netherlands, Dordrecht (2005). https://doi.org/10.1007/1-4020-3521-7 3
4 Beklemishev, L.D.: On bimodal logics of provability. Annals of Pure and Applied Logic 68(2), 115–159 (1994). https://doi.org/https://doi.org/10.1016/0168-0072(94)90071-X
5 Brotherston, J.: Cyclic proofs for first-order logic with inductive definitions. In: Proceedings of the 14th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods. p. 78–92. TABLEAUX’05, SpringerVerlag, Berlin, Heidelberg (2005). https://doi.org/10.1007/11554554 8
6 Brotherston, J., Simpson, A.: Sequent calculi for induction and infinite descent. Journal of Logic and Computation 21(6), 1177–1216 (20 2010). https://doi.org/10.93/logcom/exq052
7 Carlson, T.J.: Modal logics with several operators and provability interpretations. Israel Journal of Mathematics 54, 14–24 (1986)
8 Das, A., van der Giessen, I., Marin, S.: Intuitionistic Gödel-Löb Logic, à la Simpson: Labelled Systems and Birelational Semantics. In: Murano, A., Silva, A. (eds.) 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 288, pp. 22:1–22:18
9 Docherty, S., Rowe, R.N.S.: A non-wellfounded, labelled proof system for propositional dynamic logic. In: Cerrito, Serenellaand Popescu, A. (ed.) Automated Reasoning with Analytic Tableaux and Related Methods. pp. 335–352. Springer International Publishing, Cham (2019)
10 Feferman, S.: Arithmetization of metamathematics in a general setting. Journal of Symbolic Logic 31(2), 269–270 (1960). https://doi.org/10.2307/2269834
11 Gabbay, D.M.: Labelled deductive systems. Oxford logic guides, Clarendon press, Oxford (1996)
12 Garg, D., Genovese, V., Negri, S.: Countermodels from sequent calculi in multimodal logics. In: Proceedings of the Twenty-Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 2012). pp. 315–324. IEEE Computer Society Press (June 2012)
13 Henk, P., Pakhomov, F.: Slow and ordinary provability for peano arithmetic. arXiv: Logic (2016). https://doi.org/10.48550/arXiv.1602.01822
14 Iemhoff, R.: Reasoning in circles. In: van Eijck, J., Joosten, J., Iemhoff, R. (eds.) Liber Amicorum Alberti. A Tribute to Albert Visser., pp. 165–178. College Publications, United Kingdom (2016)
15 Japaridze, G.K.: The polymodal logic of provability. In: Intensional Logics and Logical Structure of Theories: Material from the fourth Soviet–Finnish Symposium on Logic, Telavi. pp. 16–48 (1985), in Russian
16 Japaridze, G.K.: The modal logical means of investigation of provability. Ph.D. thesis, Moscow (1986), in Russian
17 Kanger, S.: Provability in Logic. Almqvist & Wiksell, Stockholm, (1957)
18 Lyon, T.S.: Unifying sequent systems for gödel-löb provability logic via syntactic transformations. LIPIcs, Volume 326, CSL 2025 326, 42:1–42:23 (2025). https://doi.org/10.4
19 Negri, S.: Proof analysis in modal logic. Journal of Philosophical Logic 34, 507–544 (2005). https://doi.org/10.10
26 Simpson, A.: The Proof Theory and Semantics of Intuitionistic Modal Logic. Ph.D. thesis, University of Edinburgh (1994) https://doi.org/10.13
27 Simpson, A.: Cyclic arithmetic is equivalent to peano arithmetic. In: Esparza, Javierand Murawski, A.S. (ed.) Foundations of Software Science and Computation Structures. pp. 283–300. Springer Berlin Heidelberg, Berlin, Heidelberg (2017). https://doi.org/10
28 Smoryński, C.: Self-Reference and Modal Logic. Springer Verlag (1985)
29 Solovay, R.M.: Provability interpretations of modal logic. Israel Journal of Mathematics 25(3–4), 287–304 (Sep 1976). https://doi.org/10.10
30 Vigano, L.: Labelled Non-Classical Logics. Kluwer Academic Publishers, Boston (2000)
31 Visser, A.: Peano’s smart children: A provability logical study of systems with built-in consistency. Notre Dame Journal of Formal Logic 30(2), 161–196 (1989). https://doi.org/https://doi.org/10.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Implementation of a primitive decision procedure for CS allows AI systems to determine if a given sequent is provable in Carlson provability logic by applying an alternating proof search strategy of saturation and label phases.
-
The ability to extract countermodels from failed proofs provides AI systems with a mechanism to generate explicit counterexamples for unprovable sequents, aiding in model extraction from logical failures.
-
AI systems can utilize the labelled sequent calculus labCS infinity to verify formulas in CS by checking if a sequent is derivable or by constructing a countermodel M where M does not satisfy the sequent S.
Abstract
Bimodal provability logics are modal logics where the two modalities are interpreted as two formal provability predicates of arithmetic theories. We present modular labelled calculi for four different bimodal provability logics, whose rules arise from the relational semantics of these logics, while the second-order property of Noetherianity of models is enforced using techniques from cyclic proof theory. Completeness with respect to the semantics is established via proof search and countermodel construction. We further present regular and finite variants of the calculi via proof transformations.
Sources
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring