betaFeedback

WorksComputer Science

A generalised and modular proof-theoretic semantics for sequent systems

Abstract

Base-extension semantics explains logical consequence via derivability in atomic systems. Extending this approach across logics requires careful control of structural principles and contexts. We present a modular sequent-based framework in which support is indexed by multisets of atomic resources and the semantic clauses for connectives are guided by their left introduction rules. The framework separates additive from multiplicative behaviour and makes explicit the contributions of structural rules and restrictions on sequents. We establish soundness and completeness for classical and intuitionistic propositional logic and for multiplicative-additive fragments of classical and intuitionistic linear logic. We then investigate axiomatic extensions of intuitionistic logic through Jankov logic. Two classes of atomic bases yield sound and complete semantics. Completeness is proven using two novel and modular methods using simulation bases, one of which is constructive. These results provide a common semantic treatment of several logical systems while identifying the additional conditions needed to extend the framework beyond structural variations.

Introduction

In model-theoretic semantics, mathematical structures help in supporting the notion of validity, which is based on a notion of truth. In the case of intuitionistic logic, for example, one could use Kripke structures, where the validation of atomic propositions using the classical notion of truth (e.g., via truth tables) is enough for describing the meaning of a logical connective.

Proof-theoretic semantics [22, 25, 26, 27] (PtS), on the other hand, takes inference as its starting point: logical connectives acquire their meaning through rules governing how statements containing them are established and used. The significance of PtS lies in this connection between meaning and justification: it seeks to explain why the inferences we make are warranted by the meaning of the expressions involved. This perspective is particularly well-suited for natural deduction and intuitionistic logic, where proofs express the constructive content of propositions.

However, PtS does not readily extend in a modular way to other proof systems or logical traditions. In fact, although several extensions and adaptations have been proposed for other logical systems, there is still no modular methodology capable of systematically assigning proof-theoretic semantics to a broad family of logics. Each adaptation typically requires ad hoc constructions reflecting the specific proof theory of the logic under consideration [24, 23, 14, 28, 11, 1].

Shift to sequent systems. A first step towards such a unification was taken in [4], where a proof-theoretic semantics for classical logic was proposed based on sequent systems rather than natural deduction. The resulting framework fits classical reasoning remarkably well. Indeed, one may argue that sequent calculi play, for classical logic, the same foundational role that natural deduction plays for intuitionistic logic [27]. Rather than viewing sequents merely as technical devices for proving meta-theoretical properties such as cut elimination, this approach treats them as the primary carriers of meaning, allowing logical constants to be interpreted directly through their sequent rules.

The present paper develops this idea substantially. We argue that the sequent-based perspective provides a uniform and modular framework for proof-theoretic semantics that extends naturally beyond classical logic. Our framework encompasses not only classical and intuitionistic logic, but also substructural logics and, more interestingly, intermediate logics, showing that the same semantic machinery can be instantiated over different structural bases. In this sense, the framework isolates the contribution of the logical rules from that of the structural rules, making explicit how different notions of logical consequence arise from different choices of base systems.

Base-extension semantics. To achieve this, we make use of a strand of PtS called base-extension semantics [24] (BeS), where proof-theoretic validity is defined relative to a given collection of inference rules regarding basic formulas of the language. More specifically, in BeS the characterisation of consequence is given by an inductively defined semantic judgment whose base case is given by provability in an atomic system (or a base), which is a collection of rules involving only atomic formulas.

As a simple example, fix an integer nn and, for k∈{2,3,6}k \in\{2,3,6\}, let pkp_k represent the atomic sentence “nn is divisible by kk”. Consider, informally, the rules

p6p2p6p3p2p3p6\frac{p_6}{p_2} \qquad \frac{p_6}{p_3} \qquad \frac{p_2\quad p_3}{p_6}

These rules specify both consequences of asserting p6p_6 and sufficient grounds for asserting it: p6p_6 licenses each of p2p_2 and p3p_3, while p2p_2 and p3p_3 jointly license p6p_6. The internal arithmetic structure of the sentences is not represented in the formal language: only the inferential relationships among the atoms are specified.

After defining validity for atoms, one can define validity for logical connectives via semantic clauses that express proof conditions, which results in a framework that evaluates propositions exclusively in terms of proofs of its constituents.

Generalising sequent BeS. Starting from the classical sequent-based semantics developed in [4], we transition to substructural logics by presenting separate additive and multiplicative semantic clauses and controlling the use and multiplicity of assumptions through the atomic rules. Substructurality is thus reflected directly in the conditions imposed on bases and their admissible extensions.

The same framework also accommodates intuitionistic logic through the familiar restriction that right-hand contexts contain at most one formula. At the atomic level, this requires every premise and conclusion of every rule to have at most one atom in its succedent, with extensions preserving this condition. Retaining the appropriate weakening and contraction principles, and choosing the additive interpretation of disjunction and falsity, yields intuitionistic semantics. Combining restrictions on sequents with restrictions on structural rules similarly leads to substructural semantics. In particular, taking structural rules out of classical bases yields a semantics for the multiplicative-additive fragment of linear logic [15] (MALL), and taking them out of intuitionistic bases yields one for intuitionistic MALL (iMALL). The same ideas also work, to some extent, for intermediate logics. These variations arise within a common semantic framework, making explicit the respective contributions of the logical clauses, the structural rules, and the shape of contexts.

Modularity. A remarkable property of our proof strategies is that they do not need to be changed in order to work for different logics. Validity of weakening is tied to closure under atomic weakening, the same holding for contraction, and by taking structural rules from bases the classical and intuitionistic proofs immediately become proofs for MALL and iMALL. Moreover, the two proofs of completeness presented for the intermediate Jankov logic [30, 8, 17] can be adapted to any intermediate logic, obtained by adding axioms to IPL, although soundness is still ad hoc.

Another interesting consequence is that intuitionistic logic may be obtained by restricting the semantics of classical logic, but restricting the intuitionistic semantics also yields a different classical semantics. The same holds for MALL and iMALL. This provides insights on the reason why intuitionistic logic may be visualised either as an extension or as a restriction of classical logic [18].

The relevance. While it may be tempting to expect that the familiar syntactic restrictions ensuring nice proof-theoretic properties such as cut elimination immediately yield soundness and completeness with respect to the corresponding semantics, this turns out not to be the case. The interaction between bases and their extensions introduce subtleties that do not arise in the purely classical setting. For instance, despite being sequent-based, the semantics in [4] does not produce intuitionistic logic when restricted to single succedents. As showcased by our proofs for Jankov logic, other subtle features, such as whether rules can be used with arbitrary contexts or not, also have important semantic bearing.

Beyond providing a correct and uniform semantic account, our framework also sheds new light on several foundational questions in proof theory. In particular, it offers a new perspective on the distinction between intuitionistic and classical reasoning [2]. Since both emerge as different instantiations of the same semantic construction, the framework separates the role of structural principles from the behaviour of the logical connectives themselves. This perspective resonates with recent discussions on the proof-theoretic characterisation of intuitionistic consequence, including the claim that multiple-conclusion formulations of intuitionistic logic may obscure its genuine proof-theoretic nature [29].

Base-extension semantics

BeS is founded on an inductively defined judgment called support, which mirrors the syntactic structure of formulas. The inductive definition begins with a base case: the support of atomic propositions is determined by derivability in a given base – a specified collection of inference rules that govern atomic propositions. Sandqvist [24] introduced a sound and complete formulation of BeS for intuitionistic propositional logic (IPL). In this work, we adopt Sandqvist’s [24] terminology, adapting it to the sequent setting as presented in [4].

Atomic Derivability

Let At denote the set of atoms, and let ΓAt,ΔAt,ΘAt,ΣAt,…\Gamma_{\mathrm{At}}, \Delta_{\mathrm{At}}, \Theta_{\mathrm{At}}, \Sigma_{\mathrm{At}}, \ldots range over finite multisets of atoms. Commas denote multiset union, with multiplicities added. In particular, ΓAt,p\Gamma_{\mathrm{At}},p denotes ΓAt⊎p\Gamma_{\mathrm{At}} \uplus p. An atomic sequent is an expression ΓAt⇒ΔAt\Gamma_{\mathrm{At}} \Rightarrow\Delta_{\mathrm{At}}, where either multiset may be empty.

Definition 1 (Base). An atomic system (a.k.a. a base) B\mathcal{B} is a set of atomic rules of the form

ΓAt1⇒ΔAt1⋯ΓAtn⇒ΔAtnΘAt⇒ΣAt\frac{\Gamma_{\mathrm{At}}^{1} \Rightarrow\Delta_{\mathrm{At}}^{1} \quad\cdots\quad\Gamma_{\mathrm{At}}^{n} \Rightarrow\Delta_{\mathrm{At}}^{n}}{\Theta_{\mathrm{At}} \Rightarrow\Sigma_{\mathrm{At}}}

The sequence of sequents ΓAtm⇒ΔAtm\Gamma_{\mathrm{At}}^{m} \Rightarrow\Delta_{\mathrm{At}}^{m} might be empty, in which case we call the rule a zero-level rule.

Notice that the multisets of atoms occurring in the sequents of the rule might not be related to each other. We can have rules in which some of them are the same (e.g., a rule with ΓAt=ΘAt\Gamma_{\mathrm{At}} = \Theta_{\mathrm{At}}), but no identity between the multisets is built into the definition. This definition is quite general and quite useful in handling, for instance, additive contexts, see e.g. [4].

When defining bases, we distinguish between individual rules and rule schemata. In standard presentations of sequent calculi, rules are given by schemata whose metavariables range over formulas and contexts, with instantiation governed by the stated side conditions. In our setting, each individual rule in a base has fixed atomic sequents as its premises and conclusion. A displayed structural rule schema describes a family of such rules, obtained by varying the atoms and atomic contexts subject to the specified restrictions.

Applying an individual rule requires derivations of its specified premise sequents, with contexts matching exactly, including the multiplicities of atoms. The metavariables in a schema therefore describe different members of a family of rules. They do not permit the premises or conclusion of a rule already fixed in a base to vary during its application.

Definition 2 (Deducibility). For every base B\mathcal{B}, the relation ⊢B\vdash_{\mathcal{B}} is defined as the least relation generated by the following clauses:

  1. If ΓAt⇒ΔAt\Gamma_{\mathrm{At}} \Rightarrow\Delta_{\mathrm{At}} is the conclusion of a zero-level rule in B\mathcal{B}, then ⊢BΓAt⇒ΔAt\vdash_{\mathcal{B}} \Gamma_{\mathrm{At}} \Rightarrow\Delta_{\mathrm{At}} holds;

  1. Assume B\mathcal{B} contains a rule with the following shape

ΓAt1⇒ΔAt1⋯ΓAtn⇒ΔAtnΘAt⇒ΣAt\frac{\Gamma_{\mathrm{At}}^{1} \Rightarrow\Delta_{\mathrm{At}}^{1} \quad\cdots\quad\Gamma_{\mathrm{At}}^{n} \Rightarrow\Delta_{\mathrm{At}}^{n}}{\Theta_{\mathrm{At}} \Rightarrow\Sigma_{\mathrm{At}}}

Then, if ⊢BΓAtm⇒ΔAtm\vdash_{\mathcal{B}} \Gamma_{\mathrm{At}}^{m} \Rightarrow\Delta_{\mathrm{At}}^{m} holds for all 1≤m≤n1 \leq m \leq n, so does ⊢BΘAt⇒ΣAt\vdash_{\mathcal{B}} \Theta_{\mathrm{At}} \Rightarrow\Sigma_{\mathrm{At}}.

Derivations are hence finite trees built by applying rules of the base, as illustrated next.

Example 1. Consider a base B\mathcal{B} consisting exactly of the following rules

p⇒q R1p⇒qr⇒sr⇒s R2p,j⇒qr⇒s R3r⇒sj⇒k R4\frac{}{p \Rightarrow q}\ R1 \qquad \frac{p \Rightarrow q \qquad r \Rightarrow s}{r \Rightarrow s}\ R2 \qquad \frac{p,j \Rightarrow q}{r \Rightarrow s}\ R3 \qquad \frac{r \Rightarrow s}{j \Rightarrow k}\ R4

The following is a deduction in B\mathcal{B} that establishes ⊢Bj⇒k\vdash_{\mathcal{B}} j \Rightarrow k

p⇒q R1r⇒s R2r⇒sj⇒k R4\frac{\frac{}{p \Rightarrow q}\ R1 \qquad r \Rightarrow s\ R2}{\frac{r \Rightarrow s}{j \Rightarrow k}\ R4}

Observe that the application of the rule R2R2 cannot be replaced by R3R3 since ⊬Bp,j⇒q\nvdash_{\mathcal{B}} p,j \Rightarrow q.

Unlike in traditional sequent calculi, contexts are not arbitrary (or cumulative). The definition of derivability does not implicitly allow contexts to be enlarged or repeated occurrences of atoms to be identified. This makes it possible to control weakening and contraction through the choice of atomic rules.

Definition 3 (Classical, intuitionistic and linear bases). We say that a base is closed under a set of rules if it contains every instance of the corresponding rule schemata.

Consider the following set of atomic rules

p⇒p InitΓAt⇒ΔAtΓAt,p⇒ΔAt LWΓAt⇒ΔAtΓAt⇒p,ΔAt RW\frac{}{p \Rightarrow p}\ \mathit{Init} \qquad \frac{\Gamma_{\mathrm{At}} \Rightarrow\Delta_{\mathrm{At}}}{\Gamma_{\mathrm{At}},p \Rightarrow\Delta_{\mathrm{At}}}\ \mathit{LW} \qquad \frac{\Gamma_{\mathrm{At}} \Rightarrow\Delta_{\mathrm{At}}}{\Gamma_{\mathrm{At}} \Rightarrow p,\Delta_{\mathrm{At}}}\ \mathit{RW}
ΓAt,p,p⇒ΔAtΓAt,p⇒ΔAt LCΓAt⇒p,p,ΔAtΓAt⇒p,ΔAt RC\frac{\Gamma_{\mathrm{At}},p,p \Rightarrow\Delta_{\mathrm{At}}}{\Gamma_{\mathrm{At}},p \Rightarrow\Delta_{\mathrm{At}}}\ \mathit{LC} \qquad \frac{\Gamma_{\mathrm{At}} \Rightarrow p,p,\Delta_{\mathrm{At}}}{\Gamma_{\mathrm{At}} \Rightarrow p,\Delta_{\mathrm{At}}}\ \mathit{RC}
ΓAt⇒ΣAt,pΘAt,p⇒ΔAtΓAt,ΘAt⇒ΣAt,ΔAt CutcΓAt⇒pΘAt,p⇒ΔAtΓAt,ΘAt⇒ΔAt Cuti\frac{\Gamma_{\mathrm{At}} \Rightarrow\Sigma_{\mathrm{At}},p \qquad\Theta_{\mathrm{At}},p \Rightarrow\Delta_{\mathrm{At}}}{\Gamma_{\mathrm{At}},\Theta_{\mathrm{At}} \Rightarrow\Sigma_{\mathrm{At}},\Delta_{\mathrm{At}}}\ \mathit{Cut}_{c} \qquad \frac{\Gamma_{\mathrm{At}} \Rightarrow p \qquad\Theta_{\mathrm{At}},p \Rightarrow\Delta_{\mathrm{At}}}{\Gamma_{\mathrm{At}},\Theta_{\mathrm{At}} \Rightarrow\Delta_{\mathrm{At}}}\ \mathit{Cut}_{i}

A base is said to be

  • Classical if it is closed under rules Init, LW, RW, LC, RC and CutcCut_c.

  • Intuitionistic if it is closed under rules Init, LW, RW, LC, CutiCut_i. Moreover, every premise and conclusion of every rule in the base has at most one atom in its succedent;

  • Linear if it is closed under rules InitInit, CutcCut_c;

  • Intuitionistic linear if it is closed under rules InitInit, CutiCut_i, and all sequents appearing in rules contain at most one atom in their succedents.

Definition 4 (Extensions). An atomic system C\mathcal{C} is an extension of an atomic system B\mathcal{B} (written C⊇B\mathcal{C} \supseteq\mathcal{B}), if C\mathcal{C} results from adding a (possibly empty) set of atomic rules to B\mathcal{B}, satisfying the conditions defining the chosen class of bases.

Support

We now extend atomic derivability to an inductively defined notion of semantic support (⊩\Vdash). Following the perspective of Gentzen [13] and Prawitz [22], according to which introduction rules define the meaning of logical constants and elimination rules are justified by these definitions, the semantics in [4] formulated the clauses for the connectives in terms of their right introduction rules in the sequent calculus. For example, the support in a base B\mathcal{B} for the conjunction is defined in [4] as

⊩BΔ,A∧Biff⊩BΔ,Aand⊩BΔ,B.\Vdash_{\mathcal{B}} \Delta, A \wedge B \quad\text{iff}\quad\Vdash_{\mathcal{B}} \Delta, A \quad\text{and}\quad\Vdash_{\mathcal{B}} \Delta, B.

However, directly translating introduction rules into semantic clauses does not provide a uniform approach across logics. Indeed, for intuitionistic logic, the following definition yields an incomplete base-extension semantics, as shown in [21].

⊩BA∨Biff⊩BAor⊩BB\Vdash_{\mathcal{B}} A \vee B \quad\text{iff}\quad\Vdash_{\mathcal{B}} A \quad\text{or}\quad\Vdash_{\mathcal{B}} B

A related issue arises on the proof-theoretic definition for substructural logics. For example, one could attempt to define support for the multiplicative conjunction ⊗\otimes as

References

  1. [1]Ayhan, S.: Contradictions without negation and a proof-theoretic, bilateralist account of connexive logics. Rev. Symb. Log. 19(2), 375–402 (2026), https://doi.org/10.1017/S1755020326101063
  2. [2]Barroso-Nascimento, V., Pereira, L.C., Pimentel, E.: An ecumenical view of proof-theoretic semantics. Synthese 206(4), 197 (2025), https://doi.org/10.1007/s11229-025-05269-z
  3. [3]Barroso-Nascimento, V., Piotrovskaya, E., Pimentel, E.: A proof-theoretic approach to the semantics of classical linear logic. In: Kupke, C., Milius, S. (eds.) Proceedings of the 41st Conference on the Mathematical Foundations of Programming Semantics, MFPS XLI, University of Strathclyde, Glasgow, UK, June 16-21, 2025. Electronic Notes in Theoretical Informatics and Computer Science, vol. 5. EpiSciences (Apr 2025), https://doi.org/10.46298/entics.16888
  4. [4]Barroso-Nascimento, V., Piotrovskaya, E., Pimentel, E.: A sequent calculus perspective on base-extension semantics. In: Pozzato, G.L., Uustalu, T. (eds.) Automated Reasoning with Analytic Tableaux and Related Methods - 34th International Conference, TABLEAUX 2025, Reykjavik, Iceland, September 27-29, 2025, Proceedings. Lecture Notes in Computer Science, vol. 15980, pp. 3–21. Springer (2025), https://doi.org/10.1007/978-3-032-06085-3_1
  5. [5]Brünnler, K.: Locality for classical logic. Notre Dame J. Formal Log. 47(4), 557–580 (2006), https://doi.org/10.1305/ndjfl/1168352668
  6. [6]Buzoku, Y.: A proof-theoretic semantics for intuitionistic linear logic (2026), https://arxiv.org/abs/2402.01982
  7. [7]Ciabattoni, A., Maffezioli, P., Spendier, L.: Hypersequent and labelled calculi for intermediate logics. In: Galmiche, D., Larchery-Wendling, D. (eds.) Automated Reasoning with Analytic Tableaux and Related Systems (TABLEAUX 2013). Lecture Notes in Computer Science, vol. 8123, pp. 81–96. Springer (2013)
  8. [8]Citkin, A., Vandoulakis, J.M. (eds.): V. A. Yankov on Non-Classical Logics, History and Philosophy of Mathematics, Outstanding Contributions to Logic, vol. 24. Springer Nature Switzerland (2022)
  9. [9]Corsi, G.: The Logic of the Weak Excluded Middle: A Case Study of Proof-Search, pp. 95–116. Springer Milan, Milano (2008), https://doi.org/10.1007/978-88-470-0784-0_6
  10. [10]van Dalen, D.: Logic and Structure. Universitext, Springer, 5th edn. (2013)
  11. [11]d’Aragona, A.P., Prawitz, D.: Some variants of proof-theoretic semantics and their relations with intuitionistic logic. Topoi 45, 663–674 (2026)
  12. [12]Dyckhoff, R., Negri, S.: Proof analysis in intermediate logics. Arch. Math. Log. 51(1-2), 71–92 (2012), http://dx.doi.org/10.1007/s00153-011-0254-7
  13. [13]Gentzen, G.: Introduction into Logical Deduction. In: Szabo, M.E. (ed.) The Collected Papers of Gerhard Gentzen. North-Holland Publishing Company (1969)
  14. [14]Gheorghiu, A.V., Gu, T., Pym, D.J.: Proof-theoretic semantics for intuitionistic multiplicative linear logic. Studia Logica 114(2), 451–511 (2026), https://doi.org/10.1007/s11225-024-10158-6
  15. [15]Girard, J.Y.: Linear logic. Theoretical Computer Science 50, 1–102 (1987)DOI
  16. [16]Hosoi, T.: Pseudo two-valued evaluation method for intermediate logics. Studia Logica 45(1), 3–8 (1986), https://link.springer.com/article/10.1007/BF0181544DOI
  17. [17]Indrzejczak, A.: Dialogues and Proofs; Yankov’s Contribution to Proof Theory, pp. 53–70. Springer International Publishing, Cham (2022), https://doi.org/10.1007/978-3-031-06843-0_3
  18. [18]Legris, J., Molina, J.A.: Intuitionistic logic considered as an extension of classical logic: Some critical remarks. Philosophia Scientiae 5(2), 27–50 (2001)
  19. [19]Lukasiewicz, J.: On the intuitionistic theory of deduction. Indagationes Mathematicae 14, 202–212 (1952)DOI
  20. [20]Moschovakis, J.: Intuitionistic Logic. In: Zalta, E.N., Nodelman, U. (eds.) The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2024 edn. (2024)
  21. [21]Piecha, T., de Campos Sanz, W., Schroeder-Heister, P.: Failure of completeness in proof-theoretic semantics. Journal of Philosophical Logic 44(3), 321–335 (2015)DOI
  22. [22]Prawitz, D.: Meaning approached via proofs. Synthese 148, 507–524 (2006)
  23. [23]Sandqvist, T.: Classical logic without bivalence. Analysis 69(2), 211–218 (04 2009), https://doi.org/10.1093/analys/anp003
  24. [24]Sandqvist, T.: Base-extension semantics for intuitionistic sentential logic. Logic J. of the IGPL 23(5), 719–731 (2015)DOI
  25. [25]Schroeder-Heister, P.: Uniform proof-theoretic semantics for logical constants (abstract). Journal of Symbolic Logic 56, 1142 (1991)
  26. [26]Schroeder-Heister, P.: Validity concepts in proof-theoretic semantics. Synth. 148(3), 525–571 (2006), https://doi.org/10.1007/s11229-004-6296-1
  27. [27]Schroeder-Heister, P.: Proof-Theoretic Semantics. In: Zalta, E.N., Nodelman, U. (eds.) The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Palo Alto, Summer 2024 edn. (2024)
  28. [28]Stafford, W., Piecha, T., Schroeder-Heister, P.: Logics of proof-theoretic validity. Topoi 45(2), 643–661 (2025)DOI
  29. [29]Steinberger, F.: Why conclusions should remain single. Journal of Philosophical Logic 40(3), 333–355 (2011)DOI
  30. [30]Yankov, V.A.: The calculus of the weak “law of excluded middle”. Mathematics of the USSR-Izvestiya 2(5), 997–1004 (1968)

Paper details

vlnc:W_tecmmq8r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents