💻 computer science

Inference-Behaviour Semantics for All $^\ast$ Connectives in Two-Dimensional Sequent Calculi

This paper validates the new inference-behaviour semantics (I-bS) approach by systematically analyzing over 10,000 connective rule pairs in two-dimensional sequent calculi to identify 21 meaningful connectives and precisely map their semantic interrelations across various logical systems, revealing that intuitionistic connectives capture exactly half the meaning of their classical counterparts.

Original authors: Sophie Nagler

Published 2026-07-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sophie Nagler

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 what a word really means. You might think it's about the dictionary definition, but a group of philosophers and logicians argue that meaning is actually about use. It's like learning to ride a bike: you don't understand "biking" by reading a manual; you understand it by how you pedal, balance, and steer. In the world of formal logic, these "words" are symbols called connectives (like "and," "or," "not," and "if"). For decades, logicians have tried to figure out the true meaning of these symbols by looking at the rules that govern how they are used in proofs. This field is called proof-theoretic semantics. The big question is: if we change the rules of the game (the logic), do the words change their meaning? Or is there a core, unchangeable "soul" to each connective that stays the same no matter the context?

This paper dives deep into that question using a new method called Inference-Behaviour Semantics (I-bS). Think of I-bS as a high-tech scanner that doesn't just look at the rules on the page, but watches how a symbol behaves when it's forced to prove its own existence in the most stripped-down, bare-bones environment possible. The authors wanted to know: if we take every possible way we could write a rule for a logical connective, and test it in this minimal environment, which ones actually have a unique, meaningful "fingerprint"? They didn't just guess; they built a massive testing ground to see which rules survive and which ones fall apart.

The Great Connective Census

The authors set out to test a staggering number of possibilities: 10,816 different rule pairs. Imagine a giant grid where every square represents a different way to define a logical "word" using at most two starting steps and two active ingredients. They fed all 10,816 of these candidates into their "minimal derivability relation." You can think of this relation as a tiny, empty room containing only the absolute basics of reasoning: a rule that says "A is A" (Identity) and a rule that says "If you have A leading to B, and B leading to C, then you have A leading to C" (Cut). It's the logical equivalent of a survivalist's kit—no frills, no extra tools, just the essentials.

The goal was to see which of these 10,816 candidates could prove they were "definable" in this room. To be definable, a connective had to pass two strict tests:

Conservativity: It couldn't magically prove new things that weren't already possible without it. It had to play fair.
Uniqueness: It had to be the only thing that could do what it does. If another symbol could do the exact same job, it wasn't unique enough to have its own special meaning.

The Filter: From 10,816 to 21

When the dust settled, the results were surprisingly specific. Out of the 10,816 candidates, only 376 passed the first test (conservativity). But when the second test (uniqueness) was applied, the list shrank even further. In the end, the authors found exactly 21 connectives that were "minimally meaningful."

These 21 survivors are the "pure" versions of logical words. They include:

Bottom and Top: The logical equivalents of "False" and "True."
Two types of Negation: One that acts like "not" in intuitionistic logic (a cautious kind of denial) and another that acts like "not" in dual-intuitionistic logic (a more aggressive kind). The paper shows that the "classical" negation we use in everyday math is actually a mash-up of these two distinct meanings.
Conjunctions (And): There's an "additive" version (like a standard "and") and a "multiplicative" version (a stricter "and" that consumes resources).
Disjunctions (Or): Similarly, there's a standard "or" and a stricter "fission" version.
Implications (If... then): There are right-implications and left-implications, each with additive and multiplicative flavors.
Converses and Inverses: The paper also found meaningful versions of these connectives flipped around or turned inside out.

The other 10,795 candidates? They were rejected. Some were "bloatnectives"—rules that looked different on paper but acted exactly the same as the 21 winners, just with extra, useless steps attached. Others were non-conservative (they broke the rules of the room) or non-unique (they were too similar to other symbols to have a distinct identity).

The "Half-Meaning" Discovery

One of the most playful and profound findings concerns how these meanings change when we move from one type of logic to another. The paper demonstrates that classical logic (the standard logic used in most math) is like a blender that mixes distinct ingredients together.

For example, in classical logic, we usually think of "and" as just one thing. But this paper shows that classical "and" is actually a blend of two distinct meanings: the additive "and" and the multiplicative "and." When you switch to intuitionistic logic (a logic used in computer science and constructive math), you lose the multiplicative version. You are left with only the additive version.

The authors conclude that intuitionistic negation, disjunction, and implication each capture only half of the meaning of their classical counterparts. It's as if classical logic says, "I am a full sandwich," while intuitionistic logic says, "I am just the bread," and dual-intuitionistic logic says, "I am just the filling." Neither is "wrong," but they are only using half the ingredients.

Why This Matters

This isn't just a game of sorting symbols. The paper validates a new way of understanding meaning called Inference-Behaviour Semantics. By proving that this method naturally filters out the noise and leaves behind exactly the 21 connectives that logicians have been studying for decades, the authors show that their method works. It suggests that the "meaning" of a logical word isn't something we invent arbitrarily; it's something we discover by seeing how it behaves when stripped down to its bare essentials.

The paper doesn't claim to have solved every mystery in logic. It leaves open questions about how this works with more complex rules or different types of logic. But for the 21 connectives that survived the test, we now have a precise, rule-independent map of their meanings. We know that "and" isn't just "and," and "not" isn't just "not." They are complex, multi-faceted tools, and this paper has finally given us the blueprint to tell them apart.

Technical Summary: Inference-Behaviour Semantics for All∗Connectives in Two-Dimensional Sequent Calculi

1. Problem Statement

The paper addresses a central challenge in Proof-Theoretic Semantics (P-tS): how to provide meaning-invariant semantic explanations for logical connectives across different logical systems (e.g., classical, intuitionistic, linear, and dual-intuitionistic logics). Traditional approaches, such as Model-Theoretic Semantics (M-tS) and Base-Extension Semantics (B-eS), often suffer from "globalism," where changing the logic necessitates changing the meaning of connectives (e.g., classical 'and' vs. intuitionistic 'and'). This leads to a situation where logical disagreements are reduced to mere communication breakdowns due to differing definitions, rather than substantive disagreements over shared concepts.

The specific problem this paper tackles is the lack of a systematic, formal implementation of Inference-Behaviour Semantics (I-bS), a recent approach proposed by Nagler [Nag26]. While I-bS offers a promising framework for isolating the "minimal inference behaviour" of a connective to define its meaning, it had previously lacked a comprehensive technical assessment across the space of possible connective rules. The paper aims to validate I-bS by applying it to a vast, unstructured set of candidate connectives to determine which, if any, possess distinct, minimal meanings independent of specific structural rules (like weakening or contraction).

2. Methodology

The study employs a rigorous, data-driven approach to measure the "meaning" of connectives based on their inferential use in a minimal setting.

2.1 Object of Inquiry: All∗Connectives

The authors define the scope of investigation as all∗connectives: operational rule pairs formulable in two-dimensional sequent calculi subject to the following constraints:

Operational Rules: Must be separate, explicit, and symmetrical (Definition 3).
Constraints: At most two premiss sequents and at most two active formulae per rule.
Total Space: This yields exactly 10,816 syntactically unique rule pairs (combinations of premiss shapes and active formula positions).

2.2 Testing Environment: Minimal Derivability Relation

To isolate the meaning of a connective from the structural features of specific logics, the authors utilize a minimal background calculus consisting of:

Identity ( $Id_{pr}$ ): Restricted to primitive formulae only.
Cut ( $Cut_{cd}$ ): A context-differentiating Cut rule.
Structural Assumptions: The calculus assumes Exchange (multisets) but excludes Weakening and Contraction. This represents the "substructural kernel" common to many logics.

2.3 Measurement Device: Inference Behaviour

The core metric is inference behaviour, defined as the syntactic pattern a connective exhibits when its definability is proven within the minimal calculus.

Definability Criteria: Following Belnap [Bel62], a connective is definable if its addition to the calculus results in a conservative extension (no new theorems without the connective) and uniqueness (the connective is uniquely determined up to isomorphism).
Semantic Clause: The "meaning" of a connective is identified as its minimal operational rule pair that yields the minimal inference behaviour profile (the shortest list of component positions occupied by the connective and its active formulae during a definability proof).

2.4 Data Generation and Analysis

The authors systematically filter the 10,816 candidates:

Filter 1 (Formulability): All 10,816 rule pairs.
Filter 2 (Conservativity): Proving Cut-elimination for the positive cases and constructing counterexamples for non-conservative ones. This reduces the set to 376 conservative connectives.
Filter 3 (Uniqueness): Establishing horizontal and vertical interderivability. This further reduces the set to 150 uniquely definable connectives.
Minimality Analysis: Among the 150 definable connectives, the authors distinguish between "minimal" connectives and "bloatnectives" (equivalent connectives with syntactic redundancies). By applying criteria for premiss type minimality (lowest cardinality of premiss sequents), they isolate the truly minimal semantic clauses.

3. Key Contributions and Results

3.1 Identification of 21 Minimally Meaningful Connectives

The primary result is the identification of exactly 21 minimally meaningful connectives. These correspond to familiar logical constants and their converses/inverses, but with precise distinctions between additive (lattice) and multiplicative (group) versions:

Nullary: Bottom ( $\bot$ ) and Top ( $\top$ ).
Unary: Two forms of negation (Intuitionistic $\neg$ and Dual-Intuitionistic $\sim$ ), and a "trivial" converse negation.
Binary:
- Conjunction: Additive ( $\sqcap$ ) and Multiplicative ( $\otimes$ ).
- Disjunction: Additive ( $\sqcup$ ) and Multiplicative ( $\oplus$ ).
- Implication: Additive Right ( $\rightsquigarrow$ ), Multiplicative Right ( $\to$ ), Additive Left, and Multiplicative Left.
- Converses and Inverses: Each of the above has distinct semantic clauses for their converses (swapping components) and inverses.

3.2 Semantic Clauses and Frameworks

The paper provides explicit semantic clauses (minimal rule pairs) for each of the 21 connectives. Crucially, it demonstrates that these meanings are logic-independent. For instance, the semantic clause for multiplicative conjunction ( $\otimes$ ) is the same whether it appears in Linear Logic, Classical Logic, or Intuitionistic Logic. The differences in how these connectives behave in full logics (e.g., the equivalence of $\otimes$ and $\sqcap$ in Classical Logic) are attributed to structural resources (like Contraction and Weakening) rather than a change in the connective's core meaning.

3.3 Semantic Interrelations Across Logics

The study maps the semantic compatibility of these 21 connectives across various logics:

Classical Logic (LK): Conflates additive and multiplicative versions of conjunction, disjunction, and implication. It also conflates the two forms of negation.
Intuitionistic Logic (LJ): Compatible with the additive versions of conjunction and disjunction, and the "right" implication, but only captures half the meaning of classical negation (specifically $\neg_{min}$ , excluding $\sim_{min}$ ).
Dual-Intuitionistic Logic (LDJ): Captures the other half of classical negation ( $\sim_{min}$ ) and the duals of the other connectives.
Linear Logic (LL): Distinguishes all 21 connectives, treating them as semantically distinct.

3.4 Validation of I-bS

The paper claims to validate I-bS by demonstrating that when applied to a blind, exhaustive search of possible rules without bias toward any specific logic, the theory naturally converges on exactly the standard connectives found in established logical systems. The fact that the "noise" (the other 10,795 rule pairs) is filtered out as non-definable or non-minimal serves as a "sanity check" for the theory.

4. Significance and Claims

The paper positions its findings as a verification of the Inference-Behaviour Semantics framework. Its significance lies in:

Logic-Independence: It provides a method to define connective meanings that are invariant across different logics. Changing the logic (e.g., adding Weakening) does not change the meaning of the connective; it only changes the structural context in which the connective operates.
Resolution of Meaning-Change: It offers a semantic explanation for why classical and intuitionistic logics seem to disagree. They do not necessarily disagree on the meaning of "and" or "or"; rather, they differ in which minimal connectives they allow to interact and which structural rules they permit. For example, classical "and" is a conflation of two distinct minimal meanings ( $\otimes$ and $\sqcap$ ), whereas intuitionistic "and" is strictly $\sqcap$ .
Ontological Frugality: The approach requires no external models or bases, relying solely on the substructural kernel of the proof system.
Exhaustiveness: By covering the entire space of formulable rules under the given constraints, the paper claims to have provided a complete taxonomy of minimal connective meanings in two-dimensional sequent calculi.

The authors remain modest regarding the scope, noting that the results are relative to the specific constraints (two premisses, two active formulae, specific minimal calculus) and that future work could explore multi-dimensional calculi, quantification, or alternative minimal derivability relations. However, within the defined scope, the paper asserts that I-bS successfully isolates the primitive meanings of logical connectives.