Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T22:47:36.164Z Has data issue: false hasContentIssue false

MODULAR SEQUENT CALCULI FOR INTERPRETABILITY LOGICS

Published online by Cambridge University Press:  08 August 2025

COSIMO PERINI BROGI*
Affiliation:
IMT SCHOOL FOR ADVANCED STUDIES LUCCA PIAZZA S.FRANCESCO, 19, 55100 LUCCA LU, ITALY
SARA NEGRI
Affiliation:
UNIVERSITY OF GENOA VIA BALBI, 5, 16126 GENOVA GE, ITALY E-mail: sara.negri@unige.it
NICOLA OLIVETTI
Affiliation:
AIX-MARSEILLE UNIVERSITY JARDIN DU PHARO, 58 BOULEVARD CHARLES LIVON 13007 MARSEILLE, FRANCE E-mail: nicola.olivetti@univ-amu.fr
Rights & Permissions [Opens in a new window]

Abstract

An original family of labelled sequent calculi $\mathsf {G3IL}^{\star }$ for classical interpretability logics is presented, modularly designed on the basis of Verbrugge semantics (a.k.a. generalised Veltman semantics) for those logics. We prove that each of our calculi enjoys excellent structural properties, namely, admissibility of weakening, contraction and, more relevantly, cut. A complexity measure of the cut is defined by extending the notion of range previously introduced by Negri w.r.t. a labelled sequent calculus for Gödel–Löb provability logic, and a cut-elimination algorithm is discussed in detail. To our knowledge, this is the most extensive and structurally well-behaving class of analytic proof systems for modal logics of interpretability currently available in the literature.

Information

Type
Research Article
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic
Figure 0

Figure 1Interdependencies among interpretability logics, after Vuković [56]. An arrow from $\mathsf {S}$ to $\mathsf {S}'$ is interpreted as $\mathbb {IL}+\mathsf {S}'\subsetneq \mathbb {IL}+\mathsf {S}.$

Figure 1

Figure 2This information is collected from the results in [50], [7, 8], [12], [26, 27], [37]. Here FMP abbreviates “finite model property”.

Figure 2

Figure 3Rules for $\mathsf {G3IL.}$

Figure 3

Figure 4Rules for $\mathsf {G3IL}^{\star }.$

Figure 4

Figure 5Derivation of $\mathsf {IL2}$.

Figure 5

Figure 6Derivation of $\mathsf {IL3}$.

Figure 6

Figure 7Derivation of $\mathsf {IL}\text {-}\textsf {Löb}$.

Figure 7

Figure A1Derivation of $\mathsf {M.}$

Figure 8

Figure A2Derivation of $\mathsf {P.}$

Figure 9

Figure A3Derivation of $\mathsf {M_0.}$

Figure 10

Figure A4Derivation of $\mathsf {KM1.}$