A Proof-Theoretic Approach to the Semantics of Classical Linear Logic

Victor Barroso-Nascimento a 1email, Ekaterina Piotrovskaya a 2email, Elaine Pimentel a 3email · 2025

Read A Proof-Theoretic Approach to the Semantics of Classical Linear Logic by Victor Barroso-Nascimento a 1email, Ekaterina Piotrovskaya a 2email, Elaine Pimentel a 3email (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-2504-08349.txt.

Introduction

Victor Barroso-Nascimento, Ekaterina Piotrovskaya, and Elaine Pimentel work on the meaning of proofs in a logic of resources. Their paper is from two thousand twenty-five. Linear logic is careful about how often each fact may be used, unlike standard logic. That care makes it useful for describing programs and processes.

Meaning in this logic is often given by sets of contexts or by spaces built from proofs. The authors take a third route based on proof theory itself. They extend a method that defines meaning through what can be proved from a base of facts. Past work had done this for a one-sided form of the logic. This paper carries it to the classical, two-sided form, for a large fragment of it.

Catalog record

CREATORVictor Barroso-Nascimento a 1email, Ekaterina Piotrovskaya a 2email, Elaine Pimentel a 3email
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE168 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08349

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic Victor Barroso-Nascimento a 1email, Ekaterina Piotrovskaya a 2email, Elaine Pimentel a 3email Abstract Linear logic ( 𝖫𝖫 \sf{LL} ) is a resource-aware, abstract logic programming language that refines both classical and intuitionistic logic. Linear logic semantics is typically presented in one of two ways: by associating each formula with the set of all contexts that can be used to prove it ( e.g. phase semantics) or by assigning meaning directly to proofs ( e.g. coherence spaces). This work proposes a different perspective on assigning meaning to proofs by adopting a proof-theoretic perspective. More specifically, we employ base-extension semantics ( 𝖡𝖾𝖲 \sf{BeS} ) to characterise proofs through the notion of base support. Recent developments have shown that 𝖡𝖾𝖲 \sf{BeS} is powerful enough to capture proof-theoretic notions in structurally rich logics such as intuitionistic linear logic. In this paper, we extend this framework to the classical case, presenting a proof-theoretic approach to the semantics of the multiplicative-additive fragment of linear logic ( 𝖬𝖠𝖫𝖫 \sf{MALL} ). Journal: Electronic Notes in Theoretical Informatics and Computer Science Volume: 5 Piotrovskaya is supported by the Engineering and Physical Sciences Research Council grants EP/T517793/1 and EP/W524335/1. Barroso-Nascimento and Pimentel are supported by the Leverhulme grant RPG-2024-196. Pimentel has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement Number 101007627. Email: [email protected] Email: [email protected] Email: [email protected] keywords Linear logic, Semantics, Proof Theory, Proof-theoretic Semantics, Base-extension Semantics. 1 Introduction In model-theoretic semantics [ 32 ] , when giving meaning to a sentence p , one generally assigns an interpretation to determine whether it is true or false. This process may involve adding missing information as, e.g. , in Kripke systems for modal logics: Since modalities “qualify” the notion of truth, mathematical structures support the validity of \Box A by checking the validity of A in such structures instead. If a particular interpretation \mathcal{M} results in p expressing a true statement, we say that \mathcal{M} is a model of p , or equivalently, that \mathcal{M} satisfies p , which can be symbolically denoted as \Vdash_{\mathcal{M}}p . However, it is important to note that asserting “ p is true in \mathcal{M} ” is simply a reformulation of the claim that p , when understood according to \mathcal{M} , is true. In this sense, model-theoretic truth relies on ordinary truth and can always be restated in terms of it. Proof-theoretic semantics [ 54 , 56 ] ( \sf{PtS} ), on the other hand, provides an alternative perspective for the meaning of logical operators compared to the viewpoint offered by model-theoretic semantics. In \sf{PtS} , the concept of truth is substituted with that of proof , emphasizing the fundamental nature of proofs as a means through which we gain demonstrative knowledge, particularly in mathematical contexts. This makes \sf{PtS} a more adequate approach for comprehending reasoning since it ensures that the meaning of logical operators, such as connectives in logics, is defined based on their usage in inferences. Base-extension semantics [ 52 , 55 ] ( \sf{BeS} ) is a strand of \sf{PtS} where proof-theoretic validity is defined relative to a given collection of inference rules regarding basic formulas of the language. More specifically, in \sf{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 ). A base is a collection of rules involving only atomic formulas. The nature of such collection/formulas change depending on the logic considered. For example, in [ 52 ] , atoms are intuitionistic atomic propositions and rules have natural deduction style, e.g. l r r p [l] . . . p u One could view these as rules that assign interpretations to atomic sentences, much like how models operate in model-theoretic semantics. For example, if l,r,p,u represent the sentences “ We are in London ”, “ It rains all the time ”, “ We must be prudent ” and “ We carry an umbrella ” respectively, and \mathcal{B} is a base containing the rules above, one can infer that “ We carry an umbrella ” is supported by \mathcal{B} , denoted by \Vdash_{\mathcal{B}}u . As usual in semantics, starting from validity-as-deduction in the atomic case, the interpretation of more complex sentences is built compositionally from the meanings of its components, with logical connectives guiding the construction. As expected, different logics permit various approaches, each imposing its own requirements. For instance, substructural logics – often described as non-classical systems that omit one or more structural rules of classical logic – typically require the use of multisets rather than sets of formulas [ 9 , 23 ] . In contrast, classical systems often require a more refined definition of bases [ 35 , 51 ] . In this paper, we explore how \sf{BeS} applies to both substructural and classical settings. In the following, we outline the main challenges in developing proof-theoretic semantics for classical linear logic. The question of falsity. In model-theoretic semantics, falsity ( \bot ) is often defined as “never valid”. For example, in Kripke semantics, this is expressed as \not\Vdash_{\mathcal{M}}\bot\vskip-5.0pt This, however, raises the philosophical question of what constitutes the syntactic counterpart to semantic refutability [ 28 ] . Dummet avoids this problem by treating falsity as the conjunction of all basic sentences [ 17 ] , which is stated in [ 52 ] as \Vdash_{\mathcal{B}}\bot\mbox{ iff }\Vdash_{\mathcal{B}}p\mbox{ for all $p$ atomic.}\vskip-5.0pt Alternatively, in [ 42 ] the semantic of the logical constant \bot was not defined, but instead \bot was allowed to be manipulated by the atomic rules of the base – hence being considered as a “fixed atomic formula”. In this work, we adopt the same approach, which not only circumvents the aforementioned discussion but also enables an elegant presentation of \sf{BeS} for the classical substructural case, as discussed next. Dealing with classical notions of validity. The proof-theoretic essence of \sf{BeS} , where validity is built on the concept of proofs, presents a challenge: How can classical systems be described within this framework? This question is particularly relevant in the context of natural deduction systems, where inference rules inherently exhibit a constructive nature. In fact, the most common approaches to handling classical proofs often lead to non-harmonic systems [ 47 ] , whereas harmonic conservative extensions of intuitionistic natural deduction systems tend to simulate the multiple-conclusion behavior of classical sequent systems [ 22 , 44 , 50 ] . In [ 51 ] , Sandqvist proposed an inferential semantic justification for first-order classical logic, thus avoiding reliance on a notion of bivalent truth. However, as pointed out in [ 45 ] and further discussed in [ 35 ] , Sandqvist’s system lacks robustness in its choice of primitive connectives. Moreover, the proposed solution remains somewhat unsatisfactory from an inferentialist perspective, as it heavily depends on the duality of connectives to describe the entire logical system. In [ 42 ] , we tackle this problem with a different approach: Classical proofs are defined by taking into account an idea advanced by David Hilbert to justify non-constructive proof methods, where the concept of consistency is conceptually prior to that of truth, and

Read the complete text