🔢 mathematics

Nested Sequents for Horn-Characterizable Quantified Modal Logics with Equality via Reachability Rules

This paper introduces the first sound and complete, cut-free nested sequent systems for a broad class of quantified modal logics with equality and varying domain conditions, utilizing signature-based rules and grammar-parameterized reachability rules to handle complex frame properties while proving key proof-theoretic properties like invertibility and syntactic cut-elimination.

Original authors: Tim S. Lyon, Eugenio Orlandelli

Published 2026-04-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tim S. Lyon, Eugenio Orlandelli

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 build a universal translator for a very complex, multi-layered language. This language isn't just about words; it's about logic, possibility, and existence. Specifically, it's a language used by philosophers and computer scientists to talk about things like: "Is it possible that everyone in the next room is happy?" or "Does the set of people in this room change as we move to the next room?"

This paper, written by Tim Lyon and Eugenio Orlandelli, introduces a new, elegant way to prove statements in this complex language. They call their method "Nested Sequents."

Here is the breakdown of their breakthrough using simple analogies.

1. The Problem: The "Box" is Too Rigid

Imagine you are playing a game of "Truth or Dare" inside a series of nested Russian dolls.

The Outer Doll: Represents the current world.
The Inner Dolls: Represent possible future worlds (what could happen).

In standard logic games, there's a rule: "If a character exists in the outer doll, they must exist in all inner dolls." This is called a Constant Domain. It's like saying, "If I have a red ball here, I must have that same red ball in every possible future version of this room."

But in real life (and in many advanced logic systems), the rules are messier.

Increasing Domain: New people might be born as we move to the next world (the inner doll gets bigger).
Decreasing Domain: People might leave (the inner doll gets smaller).
Empty Domain: Sometimes, a world might have no people at all.

Previous attempts to build a "proof machine" for these messy rules were clunky. They either forced the "constant domain" rule (ignoring reality) or required a different, messy machine for every single variation of the rules.

2. The Solution: The "Signature" Backpack

The authors' first trick is to give every world a backpack (called a Signature).

In old systems, the backpack was empty or fixed.
In this new system, the backpack contains a list of names (terms) that exist in that specific world.
If you are in World A, your backpack might have names {Alice, Bob}. If you move to World B (a future possibility), your backpack might have {Alice, Bob, Charlie} (Increasing) or just {Alice} (Decreasing).

This allows the proof system to be flexible. It knows exactly who exists where, without forcing everyone to be everywhere.

3. The Magic Tool: "Reachability Rules" (The GPS)

The second, and most unique, part of their invention is the Reachability Rule.

Imagine the nested dolls are connected by a network of tunnels. Sometimes, the rules of the game say: "You can only move from World A to World B if there is a direct tunnel." Other times, it says: "You can move if there is a path of any length."

The authors use a GPS system (formally called a grammar) to navigate these tunnels.

The GPS: It's a set of instructions that tells the proof machine: "To get from here to there, follow a path of 3 steps," or "Follow a path that goes forward, then backward, then forward."
The Action: Instead of hard-coding a rule for "Transitivity" or "Symmetry," the machine just asks the GPS: "Is there a valid path between these two worlds according to the current map?"
The Result: If the GPS says "Yes," the machine can move a piece of information (a formula) from one world to another. If the GPS says "No," it stops.

This is like having a single robot that can navigate a maze, a city, or a forest just by changing the map it holds, rather than building a new robot for each terrain.

4. The "Cut" Trick (Cleaning the Mess)

In logic proofs, there is often a step called a "Cut." Imagine you are solving a puzzle. You might say, "I know piece A fits here, and I know piece B fits there, so I'll just glue them together and pretend I didn't need to check the middle."

While this makes the proof shorter, it's dangerous because you might be hiding a mistake. A "Cut-Elimination" theorem proves that you can always solve the puzzle without gluing pieces together; you can find the direct path.

The authors prove that their new system is Cut-Free.

Why it matters: It means their system is "honest." It doesn't rely on shortcuts. It builds the proof step-by-step from the ground up.
The Secret Weapon: They use a special "Shift Rule." Imagine you have a stack of boxes. The Shift Rule lets you slide a box from the top of one stack to the bottom of another without breaking the stack, as long as the "GPS" says the path is valid. This single rule handles all the complex "maze" variations at once.

5. The Big Surprise: The "Universal" Trap

The paper also points out a funny quirk in their system.
They found that their standard rule for "For All" (Universal Quantifier) is so powerful that it accidentally forces the "Outer Domain" (the set of all possible objects in the universe) to be constant.

Think of it like a magic spell: "If you use this specific wand to cast a 'For All' spell, the universe automatically freezes the population count."

This is actually a good thing for their specific goal because it simplifies the math.
But it means their system is best suited for worlds where the total pool of possible things doesn't change, even if the local population (who is currently in the room) does.

Summary: Why Should You Care?

This paper is a major upgrade for the "operating system" of logic.

It's Modular: You can swap out the "GPS map" (the grammar) to handle different types of worlds (increasing, decreasing, empty) without rewriting the whole engine.
It's Efficient: It avoids messy shortcuts (Cuts), ensuring the proofs are clean and reliable.
It's Flexible: It handles the tricky business of "who exists where" using the "backpack" (signature) method.

In short, Lyon and Orlandelli have built a universal logic engine that can navigate the complex, shifting landscapes of "what could be" and "who exists," all while keeping the rules of the game strict, fair, and mathematically sound.

1. Problem Statement

The paper addresses the challenge of constructing analytic proof systems (specifically, cut-free nested sequent calculi) for a broad class of Quantified Modal Logics (QMLs) that include equality.

The Difficulty: Standard proof-theoretic frameworks for QMLs often struggle to capture the nuances of non-classical quantifiers. Specifically, adding standard universal quantifier rules to nested sequent systems for modal logic often forces the logic to have constant domains (where the set of existing objects is the same across all possible worlds). This prevents the system from capturing logics with varying domains (increasing, decreasing, or empty domains).
The Gap: While labeled sequent calculi exist for these logics, they often suffer from redundant syntactic structures, lack of formula interpretation, and inflated proof sizes. Existing nested sequent systems for QMLs have been limited in scope, often failing to handle general path conditions or the specific interplay between inner and outer domains defined in models with equality.
Goal: To provide a uniform, sound, and complete cut-free nested sequent system for QMLs characterized by relational models with both inner domains (existing objects) and outer domains (possible objects), supporting various frame conditions (seriality, path conditions) and domain constraints (increasing, decreasing, constant, non-empty).

2. Methodology

The authors extend the nested sequent formalism (tree-like structures of Gentzen sequents) by integrating two key mechanisms: signatures and reachability rules.

A. Semantic Framework

The logics are defined over normal models (following Corsi) which consist of:

A set of worlds $W$ and an accessibility relation $R$ .
An outer domain $U$ (constant across all worlds in this specific formulation).
An inner domain $D_w \subseteq U$ for each world $w$ , representing objects that exist at $w$ .
The logic supports equality and allows for conditions such as increasing/decreasing domains, classical domains, and non-empty domains.

B. Syntax: Nested Sequents with Signatures

A nested sequent is a tree of flat sequents. A flat sequent is defined as a multiset of formulae $\vec{\phi}$ and a signature $\vec{t}$ (a multiset of terms).

Signatures: The inclusion of terms in the sequent structure allows the system to track "local existence." This implicitly encodes an existence predicate $E$ (where $Et \equiv \exists x (x=t)$ ), enabling the system to distinguish between objects that exist in a specific world versus those that merely exist in the outer domain.

C. Core Innovation: Reachability Rules

The paper introduces reachability rules, which are inference rules parameterized by formal grammars (specifically, semi-Thue systems or $\Sigma$ -systems).

Mechanism: These rules operate by propagating or consuming formulae/terms along paths within the nested sequent tree.
Encoding: Paths are encoded as strings generated by a grammar. For example, a string $R$ represents a forward step in the accessibility relation, while $\bar{R}$ represents a backward step.
Functionality:
1. Propagation: Moving terms or formulae from one world (node) to another based on path conditions (e.g., if a term exists in world $w$ and the domain is increasing, it must exist in world $u$ if $wRu$).
2. Search: Checking for the existence of data along a path to satisfy modal operators (e.g., $\Diamond$ ).
Modularity: By changing the underlying $\Sigma$ -system (the grammar), the same proof system can capture different frame conditions (e.g., transitivity, symmetry, Euclideanity, or generalized path conditions $G(n,k)$ ) without altering the core inference rules.

D. The Shift Rule

A novel structural rule called the shift rule ($sft(C)$) is introduced. It allows for the movement of nested components along paths defined by the grammar. This rule is crucial for proving cut-elimination uniformly across all logics in the class, avoiding the need for ad-hoc structural rules for each specific frame condition.

3. Key Contributions

Unified Framework: The first sound and complete nested sequent systems for a broad class of QMLs with equality, covering varying domains (increasing, decreasing, constant, empty) and general path conditions.
Reachability Rules: The introduction of grammar-parameterized reachability rules that allow for a modular treatment of frame conditions. This replaces the need for multiple specific rules with a single mechanism that adapts to the logic's constraints.
Signatures in Nested Sequents: The effective use of signatures (multisets of terms) to handle domain conditions and the existence predicate naturally within the nested structure.
The Shift Rule: The definition of a generic structural rule that captures all generalized path conditions simultaneously, facilitating a uniform proof of cut-elimination.
Observation on the Extended Barcan Rule (EBR): The authors demonstrate that the standard universal quantifier rule in their nested system inherently subsumes the Extended Barcan Rule. Consequently, these systems naturally capture QMLs with constant outer domains. This implies that to capture logics with non-constant outer domains, a different quantifier rule would be required.

4. Results

The paper establishes several critical proof-theoretic properties for the defined systems ( $NQ^{\circ}_{=.K}(C)$ ):

Soundness and Completeness: The systems are proven sound and complete relative to the semantic models defined by Corsi. Completeness is established via a counter-model extraction method from failed proof searches (Kripke-style).
Invertibility: All inference rules are shown to be height-preserving invertible. This means that if a conclusion is provable, the premises are provable with the same or lower proof height. This is essential for proof search and cut-elimination.
Admissibility of Structural Rules: The paper proves the height-preserving admissibility of standard structural rules (weakening, contraction, substitution) and the novel shift rule.
Syntactic Cut-Elimination: A non-trivial cut-elimination theorem is proven. The proof is uniform across the class of logics, relying on the admissibility of the shift rule to handle the interaction between modal operators and path conditions without needing logic-specific ad-hoc strategies.
Properties of Equality: The admissibility of symmetry, transitivity, and general replacement rules for equality is established, confirming the system's robustness for reasoning with equality.

5. Significance

Proof-Theoretic Advancement: This work bridges a significant gap in the literature by providing analytic proof systems for QMLs that were previously only accessible via labeled calculi or lacked cut-free formulations.
Efficiency and Modularity: By using reachability rules and signatures, the system avoids the syntactic redundancy of labeled calculi. The modular nature of the grammar parameterization allows researchers to easily define and analyze new QMLs by simply adjusting the underlying path conditions.
Insight into Domain Constraints: The finding that standard nested sequent rules enforce constant outer domains provides a clear theoretical boundary for the current framework. It highlights a specific limitation and suggests a direction for future research (developing alternative quantifier rules for non-constant outer domains).
Foundations for Automation: The properties of invertibility and cut-elimination are prerequisites for automated theorem proving and decision procedures. This work lays the groundwork for developing efficient decision procedures for these complex logics.

In summary, the paper presents a sophisticated and modular proof-theoretic framework that successfully handles the complexities of quantified modal logic with equality, offering a unified approach to a wide variety of semantic conditions through the innovative use of reachability rules and signatures.