💻 computer science

Labelled Sequents for Inquisitive First-Order Modal Logic

This paper introduces a complete labelled sequent calculus for inquisitive first-order modal logic, extending previous work to handle global supervenience and proving its strong completeness along with key structural properties like rule invertibility and cut admissibility.

Original authors: Ivano Ciardelli (University of Padua), Simone Conti (University of Padua)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ivano Ciardelli (University of Padua), Simone Conti (University of Padua)

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 organize a massive, chaotic library of "what ifs." In this library, books aren't just statements of fact (like "The sky is blue"); they are also questions (like "Is the sky blue, or is it green?"). This is the world of Inquisitive Logic.

Now, imagine you want to add a new layer to this library: Modality. This means you want to ask questions not just about the current state of the world, but about how things could be in other possible worlds. For example: "Is it necessary that, no matter which alternate reality we look at, the sky is blue?"

The paper you provided, "Labelled Sequents for Inquisitive First-Order Modal Logic," by Ciardelli and Conti, is essentially a rulebook for a new game designed to solve puzzles in this complex library. Here is the breakdown in simple terms:

1. The Problem: A Library Without a Librarian

For a long time, logicians had a great way to handle questions (Inquisitive Logic) and a great way to handle "what ifs" (Modal Logic). But when they tried to combine them—specifically to handle complex dependencies where one set of facts determines another across different possible worlds—they hit a wall.

They had a logic system (called InqQML−₂) that could describe these complex relationships perfectly, but they had no proof system. It was like having a perfect map of a treasure island but no compass or rules to navigate it. They knew the treasure existed (the logic was valid), but they couldn't prove why a specific path led to the treasure without getting lost.

2. The Solution: A New Compass (The Labelled Sequent Calculus)

The authors built a new navigation tool called a Labelled Sequent Calculus (named IWMC).

The "Labels" (The Post-it Notes): In this system, instead of just writing down a sentence, you attach a "label" to it. Think of these labels as Post-it notes representing specific groups of possible worlds. If you write "World A is blue," you stick a note on it. If you want to check a group of worlds, you stick a note on the whole group.
The "Sequents" (The Checklists): A "sequent" is just a checklist. It says: "If all the items on the left side of this checklist are true, then at least one item on the right side must be true."
The Rules (The Game Mechanics): The paper provides a set of strict rules for how you can move Post-it notes around, combine them, or split them to prove that a statement is valid.

3. The Secret Ingredient: "Finite Coherence"

The magic trick that makes this system work is a property called Finite Coherence.

Imagine you are trying to verify if a huge crowd of people (a "state") agrees on a question. Usually, you might think you need to ask everyone. But the authors discovered that for this specific type of logic, you don't need to ask the whole crowd. You only need to ask a small, specific number of people (say, 3 or 5) to know if the whole group agrees.

The Analogy: If you want to know if a team is "cohesive," you don't need to interview every single member. If you check a small, representative sample and they all agree, the whole team is cohesive.
Why it matters: This allows the authors to create a rule that says, "To prove something about a huge group of worlds, just check a small, manageable number of them." This keeps the game from becoming infinitely complicated.

4. What They Proved

The authors didn't just invent the rules; they proved that the rules actually work:

Soundness: If you follow the rules and reach a conclusion, that conclusion is guaranteed to be true. You can't cheat the system.
Completeness: If a conclusion is true in the logic, you can always find a way to prove it using their rules. There are no "true but unprovable" statements left behind.
Structural Perfection: They showed that the rules are flexible. You can rearrange steps, remove duplicates, or cut out unnecessary middle steps without breaking the proof. This makes the system robust and reliable.

5. The Big Picture

Before this paper, the logic of "global supervenience" (a fancy way of saying "how one set of facts determines another across all possible worlds") was a black box. You could describe it, but you couldn't formally analyze it step-by-step.

This paper opens the door. It provides the first-ever formal toolkit for reasoning about these complex, question-based, multi-world scenarios. It turns a philosophical mystery into a solvable puzzle with a clear set of instructions.

In short: The authors took a confusing, high-level logic system that deals with questions and possibilities, and they built a step-by-step instruction manual (a proof system) that guarantees you can solve any puzzle within that system, using a clever trick that lets you check small groups instead of infinite ones.

Problem
The paper addresses a gap in the proof-theoretic development of Inquisitive First-Order Modal Logic, specifically the system $\text{InqQML}^{-}_{\Box}$ proposed by Ciardelli [5]. This logic extends Inquisitive Weak First-Order Logic ( $\text{InqWQ}$ ) with a Kripke-style modality $\Box$ to reason about modal dependence relations, most notably global supervenience. While $\text{InqQML}^{-}_{\Box}$ was shown to be recursively enumerable via translation to two-sorted first-order logic, no dedicated proof system existed for it. Existing proof systems for the propositional or non-modal fragments (e.g., natural deduction by Conti [10] or labelled sequents by Litak and Sano [22]) rely on the property of finite coherence, but the extension to the modal case required new structural rules to handle the interaction between the modality and inquisitive disjunction.

Methodology
The authors develop a labelled sequent calculus named IWMC (Inquisitive Weak Modal Calculus). The methodology builds upon the labelled sequent framework of Litak and Sano [22] for $\text{InqWQ}$ , adapting it to the modal setting.

Labels and Semantics: Labels are finite non-empty sets of natural numbers (indices), representing finite information states. A labelled formula $s : \phi$ intuitively asserts that the state represented by $s$ supports $\phi$ . Relational atoms $wRv$ encode the accessibility relation.
Finite Coherence: A central technical tool is the finite coherence property of $\text{InqQML}^{-}_{\Box}$ . Every formula $\phi$ is $n_\phi$ -coherent, meaning its support in a state depends only on substates of cardinality at most $n_\phi$ . This number is computable from the formula.
Modal Rules: The calculus introduces specific rules for the $\Box$ $□$ modality:
- $(\Rightarrow \Box)$ : To prove $s : \Box \phi$ , the rule introduces $n_\phi$ fresh indices $t$ (representing a set of successors) and requires proving $t : \phi$ for all $w \in s$ such that $wRt$. This rule leverages finite coherence to reduce the semantic condition (support by all successors) to support by finite sets of successors of bounded size.
- $(\Box \Rightarrow)$ : To use $s : \Box \phi$ in the antecedent, the rule allows deriving consequences from $t : \phi$ for any finite set of successors $t$ of a world $w \in s$ that are already present in the derivation.
Handling Identity: The authors extend the calculus to IWMC= to handle signatures with the identity predicate, adding rules for reflexivity, symmetry, transitivity, and replacement, treating identity as a binary predicate with world-dependent extensions subject to congruence constraints.

Key Contributions and Results

Soundness and Completeness: The authors prove that IWMC is sound and strongly complete for $\text{InqQML}^{-}_{\Box}$ $InqQML_{□}^{-}$ .
- Soundness is established by induction on derivations, showing that derivable sequents are valid under the standard inquisitive semantics.
- Completeness is proven via a canonical model construction. The authors define "saturated" generalized sequents (potentially infinite) and show that any non-derivable sequent can be extended to a saturated one. A canonical model is then constructed from this saturated sequent, which serves as a countermodel, thereby proving that if a sequent is valid, it must be derivable.
Structural Properties: The calculus enjoys desirable proof-theoretic properties:
- Invertibility: All inference rules are invertible (height-preserving).
- Admissibility: The rules of weakening, contraction, and cut are admissible.
- Analyticity: The system satisfies the subformula property (extended to include substitutions), ensuring that proofs only contain subformulas of the conclusion.
Extension to Identity: The paper demonstrates how to generalize the approach to include the identity predicate, maintaining the structural properties and completeness of the system.

Significance
The paper claims that IWMC represents the first proof system for a first-order inquisitive modal logic. Its significance is twofold:

Practical Utility: It provides a formal tool to establish the validity of inferences concerning modal dependencies and global supervenience, allowing for the rigorous analysis of philosophical theses like Humean supervenience within this logical framework.
Theoretical Model: The authors suggest that their approach, particularly the integration of finite coherence into labelled sequent rules for modalities, may serve as a model for constructing proof systems for other first-order inquisitive modal logics.

The paper concludes by noting that while the system is complete, further work is needed to explore extensions to signatures with function symbols, investigate metatheoretical results like interpolation, and adapt the calculus to neighborhood-based modalities.

1. The Problem: A Library Without a Librarian

2. The Solution: A New Compass (The Labelled Sequent Calculus)

3. The Secret Ingredient: "Finite Coherence"

4. What They Proved

5. The Big Picture

More like this