💻 computer science

From Phase Semantics to Base-extension Semantics (and back)

This paper establishes an equivalence between phase semantics and base-extension semantics for linear logic by constructing bidirectional maps and an isomorphism between phase spaces and bases, while also defining base-extension semantics clauses for the logic's exponentials.

Original authors: Ekaterina Piotrovskaya

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ekaterina Piotrovskaya

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 understand how a very strict, resource-conscious accountant (let's call him "Linear Logic") keeps track of his books. In this world, you can't just copy a receipt or throw one away; every item has to be used exactly once unless you have a special "magic stamp" that allows you to duplicate or discard it.

This paper is about proving that two completely different ways of explaining how this accountant works are actually saying the exact same thing.

The Two Ways of Explaining the System

1. The "Phase Space" Method (The Algebraic Map)
Think of this as a giant, abstract map.

The Terrain: Imagine a landscape made of "phases" (like different types of energy or resources).
The Rules: There is a fixed "danger zone" (a specific subset of the map). If you combine two phases and land in the danger zone, that combination is invalid.
How it works: To see if a statement is true, you check if it lands in a "safe zone" on this map. It's like checking if a specific route on a map avoids all the potholes. This method is very mathematical and relies on shapes and sets.

2. The "Base-Extension" Method (The Rulebook)
Think of this as a game played with a specific deck of cards and a set of rules.

The Base: You start with a small list of basic facts (atoms) and a few rules for how they interact. This is your "Base."
The Extension: To understand complex statements, you don't look at a map; you ask, "If I add this new rule to my current list of rules, can I still prove my statement?"
How it works: It's like a lawyer building a case. You start with a few undeniable facts and see if you can logically extend your argument to cover new, complex situations. This method is about proofs and inference rather than maps.

The Big Problem

For a long time, these two methods lived in separate houses. One was built by mathematicians who loved algebra (Phase Semantics), and the other by logicians who loved proof theory (Base-Extension Semantics). They both claimed to explain the same logic, but they spoke different languages. No one had built a bridge between them.

What This Paper Does: Building the Bridge

The author, Ekaterina Piotrovskaya, builds a two-way bridge between these two houses.

Step 1: Translating the Map into a Rulebook
She shows that if you have a "Phase Map," you can automatically generate a "Rulebook" (a Base) that mimics the map's behavior.

Analogy: Imagine you have a topographical map of a mountain. You can translate every peak and valley on that map into a set of hiking rules (e.g., "If you are at the North Peak, you cannot go East"). The paper proves you can do this translation perfectly.

Step 2: Translating the Rulebook into a Map
She does the reverse. If you have a "Rulebook," she shows how to construct a "Phase Map" that behaves exactly like those rules.

Analogy: If you have a list of hiking rules, you can draw a map where the "danger zones" are exactly the places where those rules would break.

Step 3: Proving They Are Twins
The paper proves that if you translate a Map to a Rulebook, and then translate that Rulebook back to a Map, you end up with the exact same Map you started with (or one that is indistinguishable from it). The same goes for the Rulebook.

The Result: They are not just similar; they are isomorphic. They are two different languages describing the exact same underlying reality.

The New Ingredient: The "Exponentials"

Linear Logic has special "magic stamps" (called exponentials, written as ! and ?). These stamps allow you to copy or delete resources, which breaks the usual "use it once" rule.

Previous versions of the "Rulebook" method didn't know how to handle these magic stamps properly.
This paper writes the specific rules for how to handle these stamps in the Rulebook method. It defines exactly how these stamps behave when you are extending your list of rules.

Why This Matters (According to the Paper)

Verification: It proves that both methods are correct. If a statement is valid in the "Map" world, it is definitely valid in the "Rulebook" world, and vice versa.
Tool Sharing: Now, if a mathematician finds a cool trick for solving problems using Maps, they can translate that trick into the Rulebook language and use it there. It allows researchers to swap tools between the two fields.
Unification: It places the newer "Rulebook" method firmly into the established family of Linear Logic theories, showing it belongs right next to the older, famous "Map" method.

Summary

The paper is a translation manual. It proves that the "Algebraic Map" way of understanding Linear Logic and the "Proof-Based Rulebook" way are actually the same thing, just dressed in different clothes. It also adds the missing instructions for handling the "magic stamps" (exponentials) in the Rulebook system, ensuring the translation is complete.

Problem
Linear logic (LL) possesses a resource-sensitive notion of consequence that necessitates diverse semantic frameworks, ranging from algebraic models like phase semantics to proof-theoretic approaches like base-extension semantics (B-eS). While phase semantics interprets formulas over phase spaces (commutative monoids with orthogonality relations) and B-eS defines validity via inductive support relations over inference rules (bases), the relationship between these two distinct frameworks has not been formally established. Specifically, it was unclear whether these semantics, despite their different formulations (algebraic vs. inferential), capture the same underlying proof-theoretic behavior of linear consequence, particularly regarding the exponential modalities (! and ?).

Methodology
The paper establishes an equivalence between phase semantics and B-eS for classical linear logic through a systematic construction of bidirectional maps between the two domains:

Phase to Base: Given a phase space $P$ , the authors construct a base $P_B$ where the set of atoms corresponds to the set of facts in $P$ . The inference rules in $P_B$ are defined to mirror the orthogonality and closure properties of the phase space, including specific rules for reductio ad absurdum and structural behavior.
Base to Phase: Given a base $B$ , the authors construct a phase space $B_P$ where the monoid consists of multisets of formulas over the base's atoms. The fixed subset $\bot$ is defined as the set of multisets that support a contradiction ( $\Gamma \Vdash_B \bot$ ).
Morphisms and Isomorphism: The authors define structure-preserving maps (morphisms) between bases and phase spaces. They demonstrate that the composition of the bidirectional maps yields an identity map (or an identity up to "intersupport" in the base setting), thereby proving that the two structures are isomorphic.
Extension to Exponentials: A significant methodological step involves defining the semantic clauses for the exponential modalities (! and ?) within the B-eS framework, which had not been previously formalized for classical linear logic in this context. These clauses utilize "structural atoms" in the base to mimic the weakening and contraction properties of exponentials.

Key Contributions

Equivalence Proof: The primary contribution is the rigorous proof that phase semantics and base-extension semantics are equivalent for classical linear logic. This is achieved by showing that a phase space can be converted into a base and vice versa such that the resulting structures are isomorphic.
New Semantic Clauses: The paper introduces the first formal B-eS clauses for the exponential modalities (! and ?) in classical linear logic. These clauses rely on the concept of structural atoms to handle the resource-management aspects (weakening and contraction) inherent to exponentials.
Formalization of Correspondence: The work formalizes the relationship between the algebraic structure of phase spaces and the inferential structure of bases, defining specific morphisms that preserve validity and support relations.

Results

Theorem 25 & 29: The paper proves that the composition of the maps from Phase to Base and back to Phase results in an identity map on phase spaces. Similarly, the composition from Base to Phase and back to Base results in an identity up to intersupport (logical equivalence within the base).
Soundness and Completeness: The paper asserts that linear logic is sound and complete with respect to the newly defined B-eS clauses for exponentials. Proofs for these properties are provided in Appendix A, relying on the interaction between structural atoms and the support relation.
Lemma 16: It is demonstrated that in a base derived from a phase space, an atom is structural if and only if it corresponds to the interpretation of an exponential formula ( $! \alpha$ ). This bridges the gap between the algebraic definition of exponentials in phase semantics and the inferential definition of structural atoms in B-eS.

Significance
The paper claims that establishing this equivalence serves several purposes:

Correctness Check: It validates both frameworks by showing that a semantics formulated via induction over proofs (B-eS) and one formulated over phase spaces express exactly the same inferences.
Transfer of Results: It allows results obtained in one setting (e.g., decidability or cut-admissibility proofs in phase semantics) to be reformulated and transferred to the other (B-eS), and vice versa.
Integration: It places the relatively recent base-extension semantics within the established semantic theory of linear logic, enabling systematic comparison with other standard frameworks.
Categorical Potential: The authors note that the morphisms defined suggest that bases and phase spaces can be viewed as categories, opening the door to a more abstract, category-theoretic interpretation of the equivalence, potentially linking to existing categorical proof-theoretic semantics.

The paper concludes by modestly noting that while the equivalence is established, subtle differences remain between the proposed classical B-eS clauses for exponentials and existing intuitionistic versions, warranting further investigation. It also suggests that a similar equivalence result likely holds for intuitionistic linear logic, given the structural similarities between the classical and intuitionistic versions of both semantics.