💻 computer science

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

This paper extends the proof-theoretic framework of base-extension semantics to the multiplicative-additive fragment of classical linear logic (MALL), offering a novel approach to characterizing proofs through base support.

Original authors: Victor Barroso-Nascimento, Ekaterina Piotrovskaya, Elaine Pimentel

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Victor Barroso-Nascimento, Ekaterina Piotrovskaya, Elaine Pimentel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a high-stakes restaurant kitchen. In this kitchen, Linear Logic is the rulebook.

In a normal kitchen (Classical Logic), if you have a recipe for a cake, you can photocopy the recipe as many times as you want, or throw it away if you don't need it. In this paper's "Linear" kitchen, ingredients are precious. If a recipe calls for "one egg," you must use exactly one egg. You can't photocopy the egg, and you can't throw it away without using it. Every resource must be accounted for.

Now, usually, when we want to understand if a recipe (a logical statement) is "true," we look at a Menu of Possibilities (Model-Theoretic Semantics). We ask: "Is there a world where this cake exists?"

The Problem:
The authors of this paper are saying, "Wait a minute. In logic, we shouldn't just ask if a cake could exist in some imaginary world. We should look at the act of cooking itself (Proof-Theoretic Semantics). Does the recipe actually work step-by-step?"

They are trying to build a new way to check if a recipe works, specifically for a very strict, classical version of this kitchen (Classical Linear Logic).

The Core Idea: "Base-Extension Semantics" (BeS)

Think of a Base as a Chef's Handbook.

It contains the basic rules for the simplest ingredients (atoms).
For example, the handbook might say: "If you have flour and water, you can make dough."

In this new system, to prove a complex dish (a complex logical formula) is valid, you don't just check if it's true. You check if you can derive it using the rules in the handbook, potentially by adding more rules to the handbook later (extensions).

The Big Challenge: The "Classical" Twist

Here is where it gets tricky.

Intuitionistic Logic (Constructive) is like a chef who says: "I will only serve a dish if I have actually cooked it from scratch right now."
Classical Logic allows a chef to say: "I know I can cook this dish, even if I haven't started yet, because if I couldn't cook it, it would lead to a disaster (a contradiction)."

The authors faced a huge problem: How do you explain this "Classical" style of cooking (using contradictions) inside a system that is supposed to be about strict resource management?

Their Creative Solution: The "Disaster" Button
In most logic systems, "False" (or $\bot$ ) is just a concept meaning "This is impossible."
The authors decided to treat "False" ( $\bot$ ) as a special, fixed ingredient in the kitchen, like a "Disaster Button."

Instead of asking, "Can we prove $P$ ?", they ask:

"If we assume $P$ leads to a Disaster (pushing the $\bot$ button), does that mean we have a valid proof?"

They realized that for Classical Linear Logic, you can take the rules for the "Constructive" chef and apply a tiny, uniform restriction:

Old Rule: "If you can prove $P$ , you are good."
New Classical Rule: "If you can prove that $P$ leads to a Disaster ( $\bot$ ), then you are good."

It's like saying: "In this kitchen, the only way to prove you are a master chef is to show that if you didn't follow the rules, the whole kitchen would explode."

The "Aha!" Moment

The paper shows that this simple switch (focusing on the "Disaster" button instead of just "Truth") works perfectly for the complex rules of Linear Logic.

It's Elegant: You don't need a completely new kitchen. You just change the goalpost from "Make a cake" to "Show that not making the cake causes an explosion."
It's Robust: They proved that if a recipe is valid in their new system, it can actually be cooked (Soundness). And if a recipe can be cooked, it is valid in their system (Completeness).
It Unifies Things: They discovered that Classical Logic isn't a totally different language from Intuitionistic Logic. It's just Intuitionistic Logic with a slightly stricter definition of what counts as a "proof." It's like the difference between a chef who must bake the cake, and a chef who must prove that failing to bake it would be a catastrophe.

Why Does This Matter?

This paper is like finding a universal translator between two different dialects of logic.

It helps computer scientists understand how to write programs that manage resources (like memory or energy) more efficiently.
It suggests that "Classical" thinking (which often feels abstract and non-constructive) actually has a hidden "constructive" core, provided you look at it through the lens of "what happens if we fail?"

In a nutshell:
The authors built a new set of glasses to look at logical proofs. Instead of looking for "Truth" in a distant world, they look at the consequences of failure within the proof itself. By treating "False" as a special ingredient that triggers a chain reaction, they successfully explained how the strict rules of resource management (Linear Logic) can coexist with the powerful, sometimes paradoxical rules of Classical Logic.

1. Problem Statement

The paper addresses the challenge of defining Base-Extension Semantics (BeS) for Classical Linear Logic (CLL), specifically its multiplicative-additive fragment (MALL).

Context: Traditional model-theoretic semantics (e.g., phase semantics, coherence spaces) assign meaning to formulas based on truth conditions in mathematical structures. Proof-theoretic semantics (PtS), conversely, defines meaning based on the notion of proof. BeS is a strand of PtS where validity is defined relative to a "base" (a collection of inference rules for atomic formulas).
The Gap: While BeS has been successfully applied to Intuitionistic Propositional Logic (IPL) and Intuitionistic Linear Logic (ILL), extending it to classical systems is difficult.
- The Falsity Problem: In classical logic, falsity ( $\bot$ ) is often defined semantically as "never valid." However, in PtS, this creates a philosophical and technical gap regarding the syntactic counterpart to semantic refutability.
- The Classical/Constructive Gap: Classical logic relies on non-constructive principles (like Reductio Ad Absurdum), whereas standard BeS is inherently constructive. Previous attempts to define classical BeS often resulted in non-harmonic systems or relied heavily on the duality of connectives, which is unsatisfactory from an inferentialist perspective.
- Substructurality: Linear logic introduces resource sensitivity (formulas cannot be freely copied or erased), requiring a semantics that handles multisets rather than sets, complicating the extension of classical BeS frameworks.

2. Methodology

The authors propose a novel framework that adapts BeS to the classical substructural setting by treating $\bot$ (falsity) as a fixed atomic formula within the base.

Atomic Derivability: The authors define a base $\mathcal{B}$ as a set of atomic rules. Unlike previous approaches where $\bot$ was excluded from bases, here $\bot$ is treated as an atom. The support relation ( $\Vdash$ ) is defined inductively.
The Key Restriction (Classical vs. Intuitionistic):
- In Intuitionistic BeS, an atomic proposition $p$ is supported if it is derivable from the base.
- In this Classical BeS, the authors introduce a uniform restriction: A formula is supported if, whenever the components of the formula lead to $\bot$ (falsity) in an extended base, the whole formula leads to $\bot$ .
- Specifically, the clause for atomic support (At) is redefined: $\Vdash_{\mathcal{B}}^{\Gamma_{At}} p$ iff for all extensions $\mathcal{C} \supseteq \mathcal{B}$ , if $p, \Delta_{At} \vdash_{\mathcal{C}} \bot$ , then $\Gamma_{At}, \Delta_{At} \vdash_{\mathcal{C}} \bot$ .
- This effectively shifts the focus from "deriving truth" to "preserving consistency" (avoiding $\bot$ ), aligning with Hilbert's view that consistency is prior to truth.
Handling Connectives: The semantic clauses for MALL connectives ( $\otimes, \parr, \multimap, \&, \oplus, 1, 0, \top, \bot$ ) are defined recursively using this restriction. For example, the multiplicative conjunction $\otimes$ is supported if, for any extension, the support of the components implies the support of the conclusion relative to $\bot$ .

3. Key Contributions

First BeS for Classical Substructural Logics: This is the first work to successfully define a Base-Extension Semantics for the multiplicative-additive fragment of Classical Linear Logic (MALL).
Uniform Restriction Mechanism: The paper demonstrates that classical proof conditions can be obtained from intuitionistic ones through a simple, uniform restriction: replacing the target of derivation with $\bot$ (treated as a fixed atom). This provides a unified view of classical and constructive proofs.
Soundness and Completeness: The authors prove that the proposed semantics is both sound and complete with respect to a standard natural deduction system for MALL.
- Soundness: If a formula is provable in MALL, it is valid in the BeS.
- Completeness: If a formula is valid in the BeS, it is provable in MALL. The proof utilizes a Simulation Base construction, mapping every subformula to a unique atomic proposition.
Semantic Proof of Syntactic Properties: The completeness proof yields a purely semantic proof of a specific proof-theoretic property: any MALL derivation can be transformed into one where the elimination rules for $\otimes, \oplus, 0, \parr$ have minor premises of the shape $\bot$ .

4. Results

Theoretical Validation: The paper establishes that the proposed BeS correctly characterizes MALL. The natural deduction system for MALL is shown to be sound and complete with respect to the defined support relation.
Conceptual Insight: The results suggest that the difference between classical and constructive proofs is quantitative (amount of information required) rather than qualitative. Classical proofs are seen as a "restriction" of constructive proofs, requiring less information to establish validity because they rely on consistency ( $\bot$ ) rather than direct construction.
Connective Analysis:
- The semantics for $\parr$ (par) and $\&$ (with) are shown to be essentially classical in their standard rules, requiring no modification to the intuitionistic clauses to fit the classical framework.
- The paper discusses the difficulty of defining an intuitionistic version of $\parr$ that satisfies cut elimination, reinforcing the view that $\parr$ is inherently classical.
Future Directions: The authors propose semantic clauses for the exponential modalities ( $!$ and $?$ ) in full Linear Logic, conjecturing that the restriction to $\bot$ applies there as well, though this remains a subject for future work.

5. Significance

Bridging Paradigms: The work successfully bridges the gap between model-theoretic and proof-theoretic semantics for classical logic, offering a perspective where classical truth is derived from proof-theoretic consistency.
Inferentialist Justification: It provides a robust inferentialist justification for classical linear logic without relying on bivalent truth values or non-harmonic rule sets.
Resource Sensitivity: By applying BeS to linear logic, the paper highlights how resource management (substructurality) interacts with classical reasoning. It suggests that the absence of structural rules (contraction/weakening) in linear logic increases the informational content required for proofs, making even classical linear logic "constructive enough" to support algorithmic extraction.
Foundational Impact: The approach supports the "logical ecumenism" view that different logics may share proof conditions for certain connectives (like $\&$ ), and offers a new tool for analyzing the spectrum of constructivity in logic.

In summary, this paper provides a rigorous, proof-theoretic foundation for Classical Linear Logic, demonstrating that classical validity can be captured by a simple, uniform restriction on intuitionistic proof conditions, thereby unifying the semantic treatment of classical and constructive logics within the resource-sensitive framework of linear logic.