💻 computer science

Labelled Sequent Calculi for Propositional Team Logics

This paper presents sound and complete labelled sequent calculi with admissible structural rules and terminating proof search procedures for four propositional team logics, including basic inquisitive logic and propositional intuitionistic dependence logic, along with their tensor disjunction extensions.

Original authors: Fausto Barbero, Marianna Girlando, Valentin Müller, Fan Yang

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fausto Barbero, Marianna Girlando, Valentin Müller, Fan Yang

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 solve a logic puzzle. In the traditional way of doing this (called "Tarskian semantics"), you look at the puzzle from just one specific angle. You ask, "Is this statement true right here, in this single spot?"

But the authors of this paper are working with a different kind of logic called Team Semantics. Instead of looking at a single spot, imagine you are looking at a whole team of people standing together. You aren't asking if a statement is true for just one person; you are asking if it's true for the entire group acting together.

This "team" approach is used in real-world scenarios like figuring out how variables depend on each other in a database (e.g., "Does the price depend on the color?") or understanding the meaning of questions in language (e.g., "Is it true that it's raining OR is it true that it's snowing?").

The Problem: How to Prove Things About Teams

The authors wanted to create a set of rules (a "calculator") to prove whether statements about these teams are true or false. They call these Labelled Sequent Calculi.

Think of a "sequent" as a balance scale. On one side, you have a list of facts you know (the team's current state). On the other side, you have a conclusion you want to prove. The goal is to show that if the facts on the left are true, the conclusion on the right must also be true.

The paper introduces four specific "calculators" (proof systems) for four different types of team logic:

Basic Inquisitive Logic: The standard team logic for questions.
Propositional Intuitionistic Dependence Logic: Team logic that handles "dependence" (like "A depends on B").
Two Extended Versions: These add a special "Tensor Disjunction" (a fancy way of saying "splitting the team into two separate groups to check different things").

The Tools: Labels as Team Members

To make these calculi work, the authors use labels.

Imagine every member of your team has a name tag.
Some name tags are for individuals (single people).
Some name tags are for groups (the whole team).
The rules allow you to say things like "The group x is the same as the group y" or "Group x is a subset of group y."

The paper presents two main types of these calculi:

1. The "Detailed" Calculator (G(L))

This version is very precise. It uses complex labels that can represent teams, their unions (merging two teams), and their intersections (finding the overlap between two teams).

Analogy: This is like a high-end GPS that tracks every single car in a traffic jam, their exact positions, and how they merge or split lanes. It's mathematically rigorous and mirrors exactly how teams behave in the real world.
The Catch: Because it tracks so much detail, it's hard to tell if the GPS will ever stop calculating (it might run forever).

2. The "Terminating" Calculator (G*(L))

To fix the "running forever" problem, the authors created a simplified version.

Analogy: Instead of tracking every car's exact movement, this GPS just says, "We have a list of 5 cars. Let's check every possible combination of these 5 cars."
The Trick: They assume there is a finite number of possible "states" (like a finite number of possible weather conditions). Because the number of possibilities is limited, the calculator is guaranteed to stop after a while. It will either find a proof (Success!) or hit a wall where no more rules apply (Failure/Counter-example).
Why it matters: This guarantees that you can always write a computer program to decide if a statement is true or false in these logics.

The Key Rules of the Game

The paper proves that their calculi are Sound and Complete:

Sound: If the calculator says "True," it is actually True. (The calculator doesn't lie).
Complete: If something is actually True, the calculator can eventually find a proof for it. (The calculator doesn't miss anything).

They also proved that the calculi have admissible rules.

Weakening: You can add extra, useless facts to your list without breaking the logic.
Contraction: If you list the same fact twice, you can treat it as if it's only listed once.
Cut: If you prove A leads to B, and B leads to C, you can jump straight to "A leads to C" without showing the middle step.

The "Tensor" Challenge

One of the hardest parts of this paper was dealing with the Tensor Disjunction (the "splitting" rule).

The Analogy: Imagine you have a team of detectives.
- Standard logic says: "The whole team solves the case if they all agree on the answer."
- Tensor logic says: "The team solves the case if we can split them into two groups, where Group A solves part of the case and Group B solves the rest."
The authors had to invent a special rule (called the fin rule) to handle this. Because they assumed the number of possible "worlds" (valuations) is finite, they could say, "Every team is just a combination of these specific, limited worlds." This allowed them to simulate the splitting behavior mathematically.

Summary

In short, the authors built two sets of rulebooks for solving logic puzzles involving groups of people (teams):

A detailed, mathematically perfect rulebook that handles complex group interactions but is hard to automate.
A simplified, guaranteed-to-finish rulebook that assumes a limited number of possibilities, allowing computers to automatically check if a statement is true or false.

They proved that both rulebooks are reliable (sound) and cover all possible truths (complete) for the specific logics they studied.

Technical Summary: Labelled Sequent Calculi for Propositional Team Logics

Problem Statement
The paper addresses the proof-theoretic challenges associated with propositional logics based on team semantics. While the semantic properties of downward-closed team logics—specifically basic inquisitive logic (InqB), propositional intuitionistic dependence logic (PID), and their extensions with tensor disjunction (InqB∨ and PID∨)—are well-understood, their proof theory remains underdeveloped. Existing analytic proof systems for these logics, such as multi-type display calculi or deep-inference sequent calculi, often involve complex structural enrichments of Gentzen-style sequents. The authors identify a need for modular, labelled sequent calculi that can handle the specific satisfaction conditions of team semantics, particularly the behavior of tensor disjunction (∨) and dependence atoms, while ensuring properties like cut-admissibility and terminating proof search.

Methodology
The authors develop two families of labelled sequent calculi for the four target logics:

General Labelled Calculi ( $G(L)$ ): These systems utilize labels constructed from infinite sets of team variables ( $S$ for singleton teams, $A$ for arbitrary teams) combined with set-theoretic operations (union $\cup$ and intersection $\cap$ ). The labels represent arbitrary teams, singleton teams, and their combinations. The calculi include:
- Initial Sequents and Logical Rules: Mirroring the satisfaction conditions defined in team semantics (e.g., rules for $\land$ , $\lor$ , $\to$ , and the tensor $\lor$ ).
- Order Rules: A suite of rules formalizing set-theoretic properties of teams (e.g., transitivity, union, intersection, and the empty team property).
- Special Rules: A rule named fin is introduced to handle the assumption that the set of propositional variables $P$ is finite. This rule allows the system to describe any team as a union of $2^{|P|}$ valuations, which is crucial for simulating the tensor disjunction over classical formulas.
- Modularity: The systems are designed such that calculi for PID and PID∨ are obtained by adding specific rules for dependence atoms to the calculi for InqB and InqB∨.
Terminating Calculi ( $G^\star(L)$ ): To facilitate automated proof search, the authors introduce a simplified variant where labels are defined as finite sets of variables rather than complex terms involving unions and intersections. This approach eliminates the need for relational atoms and order rules, replacing them with rules that operate directly on the set of variables in a label.

Key Contributions and Results

Soundness and Completeness: The authors prove that the general calculi $G(L)$ are sound and complete with respect to the corresponding team semantics and Hilbert-style axiomatizations. This is achieved by demonstrating the admissibility of structural rules (weakening, contraction, cut) and establishing the admissibility of derived rules (such as mp for modus ponens and flat for the flatness of classical formulas).
Cut-Admissibility: A central technical result is the proof of cut-admissibility for all four calculi. The proof proceeds by induction on the rank of the cut formula and the height of the derivation, utilizing a lexicographic ordering that accounts for both the complexity of the formula and the label.
Terminating Proof Search: The paper presents explicit, terminating proof search algorithms for the simplified calculi $G^\star(L)$ . The algorithm constructs a proof search tree root-first. It is proven to terminate because the number of possible labelled formulas is finite (given a finite set of propositional variables and a finite set of subformulas).
Decision Procedures: The terminating nature of the $G^\star(L)$ calculi implies that the satisfiability and validity problems for InqB, PID, InqB∨, and PID∨ are decidable. The authors provide a counter-model construction from any saturated (open) branch of the proof search tree, ensuring completeness of the search procedure.

Significance and Claims
The paper claims that its primary contribution lies in providing the first sound and complete labelled sequent calculi for the full range of propositional team logics including tensor disjunction and dependence atoms. The authors highlight two distinct advantages of their approach:

Modularity: The proof systems can be adapted to different sets of connectives or atoms by simply adding or removing rules, a feature not present in the more rigid structured calculi found in previous literature.
Termination and Decision: By simplifying the label structure in $G^\star(L)$ , the authors provide a concrete decision procedure for these logics, a significant step for automated reasoning in team semantics.

The authors note that while the general calculi $G(L)$ may yield shorter proofs due to fixed-premise rules and the ability to reason about arbitrary subsets via variables, the simplified calculi $G^\star(L)$ are essential for establishing termination. The work is restricted to languages with finitely many propositional atoms, a necessary condition for the fin rule and the termination of the proof search in the presence of tensor disjunction. The paper concludes by identifying future work, including extending these systems to languages with infinitely many atoms and developing proof systems for other classes of team logics, such as those without intuitionistic implication or those possessing the union closure property.