💻 computer science

A Proof-theoretic Semantics for Intuitionistic Linear Logic

This paper extends the base-extension semantics framework, previously applied to the multiplicative fragment of Intuitionistic Linear Logic, to the full logic by providing a proof-theoretic semantics that specifically addresses the inferentialist challenges posed by the modal "bang" connective.

Original authors: Yll Buzoku

Published 2026-06-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yll Buzoku

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 trying to explain how a computer program works, but instead of looking at the code's output (what it does), you want to understand the code's meaning by looking strictly at the rules that allow you to write it. This is the core idea of Proof-theoretic Semantics: meaning comes from how we use things (the rules of inference), not from some abstract "truth" they represent.

This paper, by Yll Buzoku, tackles a specific and tricky version of logic called Intuitionistic Linear Logic (ILL). To understand what the author did, let's break it down using some everyday analogies.

1. The Problem: The "Resource" Logic

Most logic we use in daily life is like a library book. If I say, "If I have a book, I can read it," and I have a book, I can read it. If I have two books, I can still read one. The rules of standard logic allow you to copy things (weakening) or throw them away (contraction) without changing the meaning.

Linear Logic is different. It treats information like ingredients in a recipe.

If a recipe says "If you have an egg, you can make an omelet," and you have two eggs, you can make two omelets. You cannot make one omelet and pretend you still have the egg left over.
In this world, every piece of information is a resource that gets "consumed" when used.

The author's goal was to create a new dictionary (a semantics) for this "recipe logic" that explains what the words mean based only on the rules of how they are used, without relying on abstract "truths."

2. The Tool: The "Base" and the "Support"

To explain meaning, the author uses a concept called Base-Extension Semantics.

The Base: Imagine a toolbox. This toolbox contains a set of basic rules (atomic rules) that tell you how to build simple things.
The Support: A sentence is "supported" (meaningful) if you can build it using the tools in your current toolbox, or by expanding your toolbox with more tools.

The tricky part of Linear Logic is that it has two types of rules:

Multiplicative: Things that must be used exactly once (like the egg in the omelet).
Additive: Things where you can choose one path or another, but you share the same context (like choosing between a fork or a spoon, but you only have one table to set).

Previous researchers had figured out how to handle the "Multiplicative" (resource) part. But they hadn't fully solved how to handle the "Additive" part (sharing resources) or the "Modal" part (special rules for things that can be copied).

3. The Innovation: "Boxes" for Rules

The author's main breakthrough was inventing a new way to draw the rules of logic, using Boxes.

The Additive Box (The Shared Table): Imagine a group of people sitting around a single table. If they are all working on a problem together, they share the same resources. The author uses a curly bracket { } to draw a box around these shared resources. This ensures that when you make a choice (like "A or B"), you are making that choice with the same set of ingredients, not different sets.
The Modal Box (The "Magic" Box): Linear Logic has a special symbol ! (bang). This means "This item is special; you can copy it or throw it away as much as you want." It's like a magic ingredient that never runs out.
- The author created a special "Modal Box" (using square brackets J K) to handle this. This box acts like a strict rule: "To use this magic ingredient, you must prove that the item inside is valid before you even put it in the box." This prevents the logic from getting messy and ensures the "magic" works correctly.

4. The Result: A Complete Dictionary

By using these "Boxes," the author was able to:

Define the rules clearly: They created a system where every logical step (inference) is drawn out with these boxes, making it clear when resources are shared and when they are consumed.
Prove it works (Soundness): They showed that if you follow these rules, you never end up with a "nonsense" result. The logic holds up.
Prove it's complete: They showed that if a statement is true in this logic, you can always find a way to build it using their rules. There are no "true" statements that their dictionary can't explain.

5. The "Bang" (The Modal Connective)

The paper spends a lot of time on the ! (bang) symbol. In everyday terms, this is the difference between a one-time use coupon and a membership card.

A coupon (A) can be used once.
A membership card (!A) allows you to use the benefit as many times as you want.

The author explains that the meaning of the "membership card" isn't just about having the card; it's about the potential to use it. Their new definition says: "You have a membership card for A if, in any possible future scenario where A is proven true, you can derive whatever you need." It captures the idea that the card is valid forever, not just right now.

Summary

Yll Buzoku took a complex system of logic that treats information like finite resources (Linear Logic) and built a new, rigorous way to explain what it means.

The Problem: Previous explanations couldn't handle the mix of "shared resources" and "infinite resources" (the ! symbol) well.
The Solution: The author introduced Additive Boxes (for shared contexts) and Modal Boxes (for infinite resources) to organize the rules.
The Outcome: They proved that this new system is mathematically perfect: it explains every valid statement in this logic and nothing else.

Essentially, the author built a better instruction manual for a very specific, high-stakes game of logic, ensuring that every move is accounted for, every resource is tracked, and the "magic" rules are strictly defined.

Problem
Proof-theoretic semantics (P-tS) aims to confer meaning to logical expressions through the notion of proof rather than truth. While Sandqvist successfully established a base-extension semantics (B-eS) for Intuitionistic Propositional Logic (IPL), and Gheorghiu, Gu, and Pym extended this to the multiplicative fragment of Intuitionistic Linear Logic (IMLL), a complete P-tS for the full Intuitionistic Linear Logic (ILL) remained elusive. The primary challenge lies in ILL's substructural nature, which forbids general weakening and contraction, and its inclusion of additive connectives and the exponential modality (!). Existing approaches struggle to handle the interaction between these features within a base-extension framework. Specifically, defining a support relation that respects the resource-sensitive nature of ILL while correctly capturing the inferentialist content of the "bang" (!) connective—a modal operator requiring strict derivations—presents significant difficulties. Furthermore, standard natural deduction systems for ILL often rely on ad-hoc side conditions regarding context sharing (additivity) and variable numbers of premises, which are difficult to formalize within the rigid, non-schematic structure required for atomic rules in B-eS.

Methodology
The paper proposes a novel base-extension semantics for ILL by addressing two main technical hurdles: the formalization of natural deduction rules without schematic context metavariables, and the definition of a support relation that handles additivity and modality.

Reformulation of Natural Deduction: The author introduces a new syntax for the natural deduction system NILL using "additive boxes" (denoted by curly braces {...}) and "modal boxes" (denoted by semantic brackets J...K).
- Additive Boxes: These demarcate shared contexts, allowing the system to represent additive connectives (like & and ⊕) and rules with variable premises (like ⊤I and 0E) without relying on arbitrary context metavariables. This allows for a systematic treatment of additivity where derivations within a box share the same multiset of open assumptions.
- Modal Boxes: These are used to characterize the Promotion rule (Prom). The rule is redefined to require that the conclusion follows from a context where all assumptions are conclusions of rules containing only modal boxes above them. This captures the strict derivation requirement of the exponential modality without explicitly referencing the ! connective in the rule's structural definition.
- The author proves that this new system is equivalent to the standard sequent-style NILL (Theorem 2.7).
Atomic Derivability and Support Relation:
- Atomic Rules: The semantics defines atomic rules as triples consisting of a multiset of additive boxes, a single additive box (the conclusion), and an atom. This mirrors the structure of the reformulated natural deduction rules.
- Base Extension: A base $B$ is a set of such atomic rules. The derivability relation $\vdash_B$ is defined inductively, handling the multiplicative splitting of contexts and the additive sharing via the box structure.
- Support Relation ( $\Vdash_B^L$ ): The core semantic definition extends the support relation to ILL. Crucially, the clause for the exponential modality !ϕ is defined not merely as a structural rule but as a condition on the validity of $\phi$ across base extensions. Specifically, $\Vdash_B^L !\phi$ holds if, for any extension $C$ of $B$ , if $\phi$ is a "theorem" of $C$ (i.e., $\Vdash_D^\emptyset \phi$ for all $D \supseteq C$ ), then the resource can be used.
- Handling Modality: The paper introduces the concept of "persistent atoms" in the base, which correspond to formulae of the form !ϕ. These atoms play a role analogous to the ! connective in the derivability relation, allowing the semantics to distinguish between standard assumptions and those that can be weakened or contracted.

Key Contributions

A Complete B-eS for ILL: The paper presents the first base-extension semantics that covers the full Intuitionistic Linear Logic, including additive connectives and the exponential modality.
Systematic Treatment of Additivity: By introducing additive boxes, the author provides a method to handle context-sharing and variable-premise rules in natural deduction without ad-hoc side conditions or explicit context metavariables. This offers a cleaner, more uniform representation of inference figures.
Modal Box Characterization: The redefinition of the Promotion rule using modal boxes provides a structural characterization of the exponential modality that is independent of the specific connective syntax, facilitating its integration into the base-extension framework.
Inferentialist Account of !: The paper offers a detailed discussion on the inferentialist content of the ! connective. It argues that the semantics captures the modal nature of ! by treating it as a condition on the validity of the underlying formula across base extensions, effectively internalizing the "necessitation" aspect of the modality.
Soundness and Completeness: The paper proves that the proposed semantics is both sound and complete with respect to the natural deduction system NILL. The completeness proof involves constructing a "simulation base" $N$ where atomic rules mimic the inference rules of NILL, and a flattening map translates ILL formulae into atoms.

Results

Theorem 2.7: Establishes the equivalence between the standard sequent-style derivability ( $\vdash$ ) and the new box-based derivability ( $\vdash^*$ ).
Theorem 5.1 (Soundness): Proves that if a sequent is provable in NILL, it is valid in the proposed semantics ( $\Gamma \vdash \phi \implies \Gamma \Vdash \phi$ ).
Theorem 6.1 (Completeness): Proves that if a sequent is valid in the semantics, it is provable in NILL ( $\Gamma \Vdash \phi \implies \Gamma \vdash \phi$ ).
Theorem 4.15: Demonstrates that the specific (Inf) clause used for handling hypotheses with ! is equivalent to a more general (Gen-Inf) clause, validating the specific treatment of modal hypotheses.
Corollary 4.11 & 4.12: Establish structural properties regarding the interaction of ! with the support relation, showing that if $\phi$ is valid, then !ϕ is valid, and that !Γ supports !ϕ if it supports ϕ.

Significance
The paper claims to fill a significant gap in proof-theoretic semantics by extending the base-extension approach from IPL and IMLL to the full ILL. The author notes that while Gheorghiu, Gu, and Pym successfully handled the multiplicative fragment, the addition of additives and the exponential modality required substantial new machinery. The work is significant for its intrinsic proof-theoretic approach to modality, offering a way to understand the "bang" connective not just as a structural rule but as a condition on the validity of formulae within the base-extension framework. The author modestly acknowledges that the solution for handling the promotion rule and additivity is "somewhat convoluted" but necessary to achieve a clean, systematic representation of inference figures. Furthermore, the paper highlights the difficulty of embedding Sandqvist's IPL semantics directly into this ILL framework, leaving the generalization of the mapping between the two as an open problem for future study. The work suggests that the current approach to modalities in P-tS may require deep metaphysical or structural insights that are only beginning to be addressed.