Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics

arXiv:2506.14307 · cs.LO, math.LO · Submitted 2025-06-17 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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 △.

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. p. 2
Where the paper says it

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.

The completeness theorem states that CS ⊢ A iff for all Carlson models M: M ⊩ A. p. 2
Where the paper says it

Theorem 3 ([28]). For any formula A ∈ L□△: CS ⊢ A iff for all Carlson models M: M ⊩ A.

Calculus Construction

The authors present the labCS∞ calculus, a bi-labelled non-wellfounded calculus for CS. This system uses labels Lab = x, y, z, … and relational atoms of the form xRy or xSy. The rules include structural rules like →R and →L. p. 1

Where the paper says it

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.

Crucially, the system incorporates non-wellfounded proofs, defined as coinductive trees allowing for infinitary branches constrained by a progress condition. p. 3
Where the paper says it

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].

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

Where the paper says it

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.

Completeness is shown by demonstrating a proof search procedure that alternates between saturation phases and label phases. p. 8
Where the paper says it

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.

Lemma 14 provides a method to extract a countermodel M ⊮ S from any fully saturated sequent S. p. 9
Where the paper says it

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.

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

Where the paper says it

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 16 confirms that CS ⊢ A iff labCS∞ ⊢ A. p. 7
Where the paper says it

Corollary 9. Given an instance of a rule of labCS∞, with conclusion S and premisses S1, .

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

Where the paper says it

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].

Furthermore, developing calculi for other provability logics such as Feferman provability or GLP is another potential research avenue. p. 0
Where the paper says it

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].

References

1 Afshari, B., Leigh, G.E., Menéndez Turata, G.: Uniform interpolation from cyclic proofs: The case of modal mu-calculus. p. 0

Where the paper says it

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].

p. 0
Where the paper says it

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].

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. p. 2

Where the paper says it

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.

p. 2
Where the paper says it

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.

Annals of Pure and Applied Logic 169(10), 997–1043 (2018). p. 3
Where the paper says it

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].

p. 3
Where the paper says it

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].

https://doi.org/10.1016/j.apal.2018.05

3 Artemov, S.N., Beklemishev, L.D.: Provability logic. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

In: Gabbay, D., Guenthner, F. (eds.) Handbook of Philosophical Logic, 2nd Edition, pp. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Annals of Pure and Applied Logic 68(2), 115–159 (1994). p. 3
Where the paper says it

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].

p. 3
Where the paper says it

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].

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. p. 3

Where the paper says it

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].

p. 3
Where the paper says it

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].

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. p. 0

Where the paper says it

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].

p. 0
Where the paper says it

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].

Journal of Logic and Computation 21(6), 1177–1216 (20 2010). p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

https://doi.org/10.93/logcom/exq052

7 Carlson, T.J.: Modal logics with several operators and provability interpretations. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 3

Where the paper says it

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].

p. 3
Where the paper says it

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: 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. p. 0

Where the paper says it

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].

p. 0
Where the paper says it

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].

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. p. 1

Where the paper says it

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, .

p. 1
Where the paper says it

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, .

Journal of Symbolic Logic 31(2), 269–270 (1960). p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

https://doi.org/10.2307/2269834

11 Gabbay, D.M.: Labelled deductive systems. p. 3

Where the paper says it

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.

p. 3
Where the paper says it

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.

Oxford logic guides, Clarendon press, Oxford (1996)

12 Garg, D., Genovese, V., Negri, S.: Countermodels from sequent calculi in multimodal logics. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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: Logic (2016). p. 0
Where the paper says it

arXiv:2506. 14307v1 [cs.

p. 0
Where the paper says it

arXiv:2506. 14307v1 [cs.

https://doi.org/10.48550/arXiv. p. 0
Where the paper says it

arXiv:2506. 14307v1 [cs.

p. 0
Where the paper says it

arXiv:2506. 14307v1 [cs.

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. p. 0

Where the paper says it

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].

p. 0
Where the paper says it

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: Intensional Logics and Logical Structure of Theories: Material from the fourth Soviet–Finnish Symposium on Logic, Telavi. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

pp. 16–48 (1985), in Russian

16 Japaridze, G.K.: The modal logical means of investigation of provability. p. 2

Where the paper says it

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∗ .

p. 2
Where the paper says it

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∗ .

Ph.D. thesis, Moscow (1986), in Russian

17 Kanger, S.: Provability in Logic. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Almqvist & Wiksell, Stockholm, (1957)

18 Lyon, T.S.: Unifying sequent systems for gödel-löb provability logic via syntactic transformations. p. 1

Where the paper says it

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.

p. 1
Where the paper says it

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.

LIPIcs, Volume 326, CSL 2025 326, 42:1–42:23 (2025). p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

https://doi.org/10.4230/LIPICS.CSL.20

19 Negri, S.: Proof analysis in modal logic. p. 0

Where the paper says it

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]).

p. 0
Where the paper says it

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]).

Journal of Philosophical Logic 34, 507–544 (2005). p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

https://doi.org/10.1007/s10992-005-2267-3

26 Simpson, A.: The Proof Theory and Semantics of Intuitionistic Modal Logic. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Ph.D. thesis, University of Edinburgh (1994) https://doi. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

org/10.1305/ndjfl/1094061859

27 Simpson, A.: Cyclic arithmetic is equivalent to peano arithmetic. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

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.1305/ndjfl/109466

28 Smoryński, C.: Self-Reference and Modal Logic. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Springer Verlag (1985)

29 Solovay, R.M.: Provability interpretations of modal logic. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Israel Journal of Mathematics 25(3–4), 287–304 (Sep 1976). https://doi.org/10.1007/BF02757006

30 Vigano, L.: Labelled Non-Classical Logics. p. 8

Where the paper says it

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].

p. 8
Where the paper says it

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].

Kluwer Academic Publishers, Boston (2000)

31 Visser, A.: Peano’s smart children: A provability logical study of systems with built-in consistency. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Notre Dame Journal of Formal Logic 30(2), 161–196 (1989). https://doi.org/https://doi.org/10.1305/ndjfl/1093635077

32 Visser, A.: A course on bimodal provability logic. p. 0

Where the paper says it

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.

Annals of Pure and Applied Logic 73(1), 109–142 (1995). p. 3
Where the paper says it

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].

https://doi.org/https://doi.org/10.1016/0168-0072(93)

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

Where the paper says it

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.

p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

The system is obtained by modelling the Kripke-like semantics of this logic. The system is obtained by modelling the Kripke-like semantics of this logic. The system is obtained by modelling the Kripke-like semantics of this logic.

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

  1. 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.

  2. 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.

  3. 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