Base-extension Semantics for Intuitionistic Modal Logics
Yll Buzoku, David J. Pym · 2025
Read Base-extension Semantics for Intuitionistic Modal Logics by Yll Buzoku, David J. Pym (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06834.txt.
Introduction
Yll Buzoku and David Pym develop a proof-based semantics for intuitionistic modal logics in a 2025 paper. Simpson had earlier studied these logics with labelled deduction systems and Kripke models. The new work asks what the same logics look like when meaning comes from proof rules instead of models.
Base-extension semantics builds validity from bases of atomic rules that mention only simple propositions. The authors set up this semantics for Simpson's logics in a systematic way. They then prove soundness and completeness against his natural deduction systems. The result gives logicians a second, proof-centered route to the same systems.
Catalog record
| CREATOR | Yll Buzoku, David J. Pym |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06834
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Base-extension Semantics for Intuitionistic Modal Logics Yll Buzoku, David J. Pym Abstract The proof theory and semantics of intuitionistic modal logics have been studied by Simpson in terms of Prawitz-style labelled natural deduction systems and Kripke models. An alternative to model-theoretic semantics is provided by proof-theoretic semantics, which is a logical realization of inferentialism, in which the meaning of constructs is understood through their use. The key idea in proof-theoretic semantics is that of a base of atomic rules, all of which refer only to propositional atoms and involve no logical connectives. A specific form of proof-theoretic semantics, known as base-extension semantics (B-eS), is concerned with the validity of formulae and provides a direct counterpart to Kripke models that is grounded in the provability of atomic formulae in a base. We establish, systematically, B-eS for Simpson’s intuitionistic modal logics and, also systematically, obtain soundness and completeness theorems with respect to Simpson’s natural deduction systems. 1 Introduction Simpson [ 25 ] introduces a family of natural deduction systems for a range of intuitionistic modal logics (iMLs). These natural deduction systems are shown to be both sound and complete with respect to meta-logical derivations in the intuitionistic first-order meta-theory that is assumed. This result is shown by defining a bidirectional translation of modal formulae to intuitionistic first-order formulae and showing that theorems of the natural deduction systems, under the translation, correspond to a particular type of (intuitionistic) first-order derivation. Simpson also defines a Kripke semantics for his intuitionistic modal logics based on the interpretation of first-order expressions in the Kripke semantics of first-order intuitionistic logic. The resulting modal models are then used to establish the soundness and completeness of his natural deduction systems. Proof-theoretic semantics is an alternative conception of a semantic theory that is grounded in the philosophical position known as inferentialism, in which the meanings of language constructs are considered to be determined by their use. In proof-theoretic semantics, which may be seen as a logical realization of the inferentialist position, meaning is given to a logical language through proof, rather than truth. This idea has deep roots in the works of Wittgenstein, with his principle that the meaning of a word should be reflected in its use [ 26 ] , but also more recently in works such as those of Dummett [ 6 ] and Brandom [ 1 , 2 , 15 ] . Proof-theoretic semantics can usefully be seen as having two main branches. One, proof-theoretic validity (P-tV) is concerned — in a sense articulated by Prawitz [ 20 ] , Dummett [ 6 ] , and Schroeder-Heister [ 23 , 24 , 18 , 17 ] — with what constitutes a valid proof. The other, base-extension semantics (B-eS) is concerned with what constitutes a valid formula and is the focus of this paper: we provide a uniform B-eS for the iMLs studied by Simpson [ 25 ] . Sandqvist [ 22 ] obtains a sound and complete B-eS for intuitionistic propositional logic (IPL). This is achieved by defining the concept of an atomic rule as an inference figure such as \mathcal{R} in Figure 1 (which we may write linearly as ((P_{1}\Rightarrow q_{1}),\ldots,(P_{n}\Rightarrow q_{n}))\Rightarrow r) ), and then defining a relation of atomic derivability \vdash_{\mathscr{B}} over sets of atomic rules \mathscr{B} , between sets of atoms and atoms. Crucially, the rules make mention only of atoms and the relation of atomic derivability, as the name suggests, is thus capable only of observing judgements between sets of atoms and individual atoms. One can imagine the \mathscr{B} as being a natural deduction like construct whose elements are not schemas, but, in fact, instances of rules. Thus, in the same way that \rm NJ can be viewed as generating the consequence relation \vdash_{\rm NJ} , the relation \vdash_{\mathscr{B}} can be understood as the consequence relation generated by \mathscr{B} . Sandqvist then conservatively extends this relation to a relation of support \Vdash_{\!\!\mathscr{B}}^{\!\!} over a base \mathscr{B} which relates sets of IPL formulae to an IPL formula. \frac{\begin{array}[]{ccc}[P_{1}]&&[P_{n}]\\ q_{1}&\ldots&q_{n}\end{array}}{r}\,\mathcal{R}\qquad{\small\begin{array}[]{rl}\mbox{(Ref)}&\mbox{$P,p\vdash_{\mathscr{B}}p$}\\ (\mbox{App}_{\mathcal{R}})&\mbox{if $((P_{1}\Rightarrow q_{1}),\ldots,(P_{n}\Rightarrow q_{n}))\Rightarrow r)$ and,}\\ &\mbox{for all $i\in[1,n]$, $P,P_{i}\vdash_{\mathscr{B}}q_{i}$, then $P\vdash_{\mathscr{B}}r$}\end{array}} {\small\begin{array}[]{rl@{\quad}rl}\mbox{(At)}&\mbox{for atomic $p$, $\Vdash_{\mathscr{B}}p$ iff $\vdash_{\mathscr{B}}p$}\hfil\hskip 9.24994pt&(\vee)&\mbox{$\Vdash_{\mathscr{B}}\phi\!\vee\!\psi$ iff, for every atomic $p$ and every }\\ &\hfil\hskip 9.24994pt&&\mbox{$\mathscr{C}\!\supseteq\!\mathscr{B}$, if $\phi\Vdash_{\mathscr{C}}p$ and $\psi\Vdash_{\mathscr{C}}p$, then $\Vdash_{\mathscr{C}}p$}\\ (\supset)&\mbox{$\Vdash_{\mathscr{B}}\phi\supset\psi$ iff $\phi\Vdash_{\mathscr{B}}\psi$}\hfil\hskip 9.24994pt&(\bot)&\mbox{$\Vdash_{\mathscr{B}}\bot$ iff, for all atomic $p$, $\Vdash_{\mathscr{B}}p$}\\ (\wedge)&\mbox{$\Vdash_{\mathscr{B}}\phi\wedge\psi$ iff $\Vdash_{\mathscr{B}}\phi$ and $\Vdash_{\mathscr{B}}\psi$}\hfil\hskip 9.24994pt&\mbox{(Inf)}&\mbox{for $\Theta\neq\emptyset$, $\Theta\Vdash_{\mathscr{B}}\phi$ iff, for every $\mathscr{C}\supseteq\mathscr{B}$,}\\ &\hfil\hskip 9.24994pt&&\mbox{if $\Vdash_{\mathscr{C}}\theta$, for every $\theta\in\Theta$, then $\Vdash_{\mathscr{C}}\phi$}\end{array}} Figure 1: Sandqvist’s B-eS for Intuitionistic Propositional Logic The need to consider base extensions, of the form \mathscr{C}\supseteq\mathscr{B} , in entailments defined by \Vdash_{\mathscr{B}} is analogous to the need to consider accessible worlds in Kripke models of intuitionistic implication. As Prawitz [ 20 ] explains, we wish the semantics to yield a construction of an implication \phi\supset\psi , say, as a construction of \psi from \phi that, together with a construction of \phi , yields a construction of \psi . For a fixed base \mathscr{B} , the condition as formulated above would be vacuously satisfied in the absence of a construction of \phi relative to \mathscr{B} . This would be a rather weak condition and, unsurprisingly, the semantics requires that all base-extensions \mathscr{C}\supseteq\mathscr{B} be used. See also [ 10 ] to explore further some related issues. It is a support relation of this form that provides our main semantic tool in giving a uniform B-eS for iMLs. The semantics as defined in Figure 1 is sound and complete for IPL. In this framework, an IPL sequent (\Gamma:\phi) is deemed valid iff for all bases \mathscr{B} , we have that \Gamma\Vdash_{\!\!\mathscr{B}}^{\!\!}\phi (where \Gamma is a set of IPL formulae and \phi is an IPL formula). This is somewhat analogous to what one might expect in a Kripke-like semantics, where one would say something like \phi is valid iff for all models \mathcal{M} we have that \mathcal{M}\vDash\phi . It is crucial, though, that bases are not the same as models and that this difference is easily observed in the fact that the meanings of the connectives — that is, the semantic clauses — are very different in some cases from the familiar Kripke semantics for IPL. For example, the form of the clause for disjunction in Figure 1 can be understood either as following the second-order definition of \vee or, perhaps more proof-theoretically, as following the form of the \vee -elimination rule in NJ (see, e.g., [ 19 , 21 , 10 ] ) — cf. also Beth’s semantics; for example, [ 16 ] provides an illuminating discussion. That said, the treatment of \bot follows, for example, Dummett [ 6 ] . Sandqvist proves, in [ 22 ] , soundness and completeness of the B-eS relative to NJ [ 19 ] . We sketch the arguments below. Theorem 1.1 (IPL Soundness) If \Gamma\vdash_{\rm NJ}\phi , then \Gamma\Vdash\phi . \Box In this case, by the inductive definition of \vdash_{\rm NJ} , it is sufficient to consider simply every rule of \rm NJ as a series of meta-logical expressions with us assuming the hypothesis of every rule is valid and showing that the conclusion of every rule is also valid. For example, for \mathsf{\supset}_{\mathsf{I}} , we show that if \Gamma,\phi\Vdash_{\emptyset}\psi , then \Gamma\Vdash_{\emptyset}\phi\supset\psi (note, using the base \emptyset is equivalent to the