In classical logic, truth is evaluated against a single state of affairs. In propositional logic, this is a single truth assignment to variables; in first-order logic, it is a single assignment of domain elements; in modal logic, it is a single possible world. We write $\mathcal{M}, s \models \phi$ to say that the formula $\phi$ is true under the individual assignment $s$.
However, this classical paradigm faces a fundamental limitation: it cannot natively express relationships between different states or variables.
Consider the statement: "The variable $y$ depends entirely on the variable $x$." If you look at a single isolated assignment where $x = 5$ and $y = 10$, you cannot determine if this dependency holds. You have no way of knowing whether changing $x$ would force a change in $y$, or if $y$ is simply a constant. To observe a dependency, you must look at a collection of assignments simultaneously and check if they vary together consistently.
As noted by Durand et al. in the Special issue on logic and complexity, evaluating formulas against single assignments is fundamentally insufficient for specifying these collective, relational properties. This realization drove the creation of team semantics, a framework that lifts the evaluation of logic from individual assignments to sets of assignments, unlocking the ability to reason about dependence, independence, and information flow.
The Mechanism of a Team
To transition from classical semantics to team semantics, we replace the single assignment $s$ with a team $X$, which is simply a set of assignments.
An intuitive way to visualize a team is as a relational database table. Each row in the table represents an assignment (a state or a data point), and each column represents a variable.
| Assignment (Row) | Variable $x$ | Variable $y$ | Variable $z$ |
|---|---|---|---|
| $s_1$ | 1 | 2 | 5 |
| $s_2$ | 1 | 2 | 9 |
| $s_3$ | 3 | 4 | 5 |
| $s_4$ | 3 | 4 | 2 |
By evaluating formulas against the entire table $X$ rather than individual rows, we can introduce specialized atomic formulas that inspect the global structure of the data. The most foundational of these is the dependence atom, typically written as $\text{dep}(x, y)$.
We say that a team $X$ satisfies $\text{dep}(x, y)$ if and only if any two rows that agree on their value for $x$ also agree on their value for $y$. Looking at the table above:
- $s_1$ and $s_2$ both have $x=1$, and both have $y=2$.
- $s_3$ and $s_4$ both have $x=3$, and both have $y=4$.
Because the value of $x$ uniquely determines the value of $y$ across all rows, the team satisfies $\text{dep}(x, y)$. Conversely, the team does not satisfy $\text{dep}(x, z)$, because $s_1$ and $s_2$ agree on $x$ ($x=1$) but disagree on $z$ ($5 \neq 9$).
As explored by Abramsky et al. in Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071), this simple semantic shift allows logic to natively incorporate functional dependencies, transforming it into a powerful language for modeling complex interactions in databases, software verification, and multi-agent systems.
Beyond Dependence: Independence and Inclusion
Once the conceptual leap to set-based evaluation is made, logicians can define atoms for other relational properties that are invisible to classical logic:
- Independence Atoms ($x \perp y$): Assert that knowing the value of $x$ provides no information about the value of $y$ within the team.
- Inclusion Atoms ($x \subseteq y$): Assert that the collection of values taken by $x$ across the team is a subset of the values taken by $y$.
Hannula et al. demonstrate in Complexity of Propositional Independence and Inclusion Logic that these variations drastically alter the mathematical landscape, allowing us to reason about data constraints that emerge only when looking at datasets as a whole. Mahmood et al. further map this out in Parameterized Complexity of Propositional Inclusion and Independence Logic, showing how these atoms behave under various computational constraints.
Translating Teams to Modal and Temporal Domains
The intuition of team semantics is not restricted to first-order or propositional logic; it naturally extends to modal and temporal frameworks.
In standard modal logic, a formula is evaluated at a single "possible world." Under modal team semantics, it is evaluated over a set of worlds. This allows the logic to track information flow and dependencies across different states or execution paths. Müller et al. leveraged this in Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice to classify the exact computational difficulty of verifying these multi-state dependencies.
This capability is incredibly useful for verifying hyperproperties—system security requirements (like anonymity, privacy, or non-interference) that cannot be checked on a single execution trace but require comparing multiple traces. For example, to prove a system is secure against information leaks, you must show that an observer seeing the public outputs cannot deduce the secret inputs. This is fundamentally a statement about the dependence of one variable on another across all possible execution paths.
Krebs et al. demonstrate in Team Semantics for the Specification and Verification of Hyperproperties that applying team semantics to Linear Temporal Logic (LTL) creates a powerful, computationally manageable framework for system verification, bypassing the non-elementary complexity traps of alternative approaches. Similarly, Krebs et al. extended this to branching time in A Team Based Variant of CTL to reason about parallel processes and collective behavior.
The Price of Power: Complexity and Expressivity
What happens to a logic when you lift its evaluation from individuals to sets? Its expressive power skyrockets—but so does its computational complexity.
When first-order logic is augmented with dependence atoms under team semantics, it gains the ability to define properties equivalent to existential second-order logic, as noted by Grädel et al. in Logics for Dependence and Independence (Dagstuhl Seminar 15261). However, this power comes at a cost. Kuusisto et al. proved in Decidability of Predicate Logics with Team Semantics that even the two-variable fragment of dependence logic becomes completely undecidable, settling a long-standing open question in the field.
Furthermore, adding non-standard operators can break classical logical assumptions. For instance, Durand et al. show in Dependence logic with a majority quantifier that introducing a majority quantifier causes a violation of the free variable property. In classical logic, the truth of a formula depends only on the variables that appear free within it. In team semantics with counting quantifiers, the truth value of a formula can suddenly be influenced by variables not contained within it, because the majority threshold is calculated relative to the total number of possible assignment extensions across the entire team's domain.
Modern Frontiers: Probability and Multi-Table Frameworks
The frontier of this research direction involves pushing team semantics into statistical and relational database domains.
Instead of just looking at sets of assignments, what if we look at probability distributions over assignments? This leads to probabilistic team semantics, introduced by Durand et al. in Probabilistic Team Semantics. This framework bridges formal logic with statistics, allowing for direct reasoning about conditional independence. As Hirvonen et al. show in Facets of Distribution Identities in Probabilistic Team Semantics, this allows logicians to tackle complex relational dependencies that are completely invisible to classical single-assignment frameworks.
Finally, real-world data rarely sits in a single table. To handle dependencies that cross multiple tables, Virtema et al. introduced Polyteam Semantics. By evaluating formulas over a family of distinct assignment sets simultaneously, this multi-table framework allows logic to natively express cross-table constraints like foreign keys, fully uniting the foundational power of logic with the practical realities of database theory.
Key Foundational Work
Complexity of two-variable Dependence Logic and IF-Logic (2011) — contributed 1 concept elements to this direction.
Defining a Double Team Semantics for Generalized Quantifiers (2012) — contributed 2 concept elements to this direction.
Dependence logic with a majority quantifier (2011) — contributed 2 concept elements to this direction.