Introduction
In traditional Tarskian semantics, the truth of a logical formula is evaluated against a single assignment of values to variables. While this suffices for standard first-order logic, it fails to capture properties like dependence or independence between variables. To address this, researchers developed team semantics, where formulas are evaluated against sets of assignments, known as teams.
However, standard team semantics faces a significant "negation problem": it lacks natural symmetry, often forcing formulas into Negation Normal Form (NNF) or resulting in computational intractability when negation is introduced. Furthermore, integrating generalized quantifiers—such as "most," "at least $k$," or "infinitely many"—into this framework has historically been fragmented. This paper introduces double team semantics, a novel framework that achieves full symmetry for negation and provides a unified foundation for generalized quantifiers and dependence atoms.
The Double Team Framework
The core innovation of this research is the transition from a single team to a double team. Instead of evaluating a formula $\phi$ against a single team $X$, it is evaluated against a pair $(U, V)$. In this structure:
- $U$ represents the verifying team: the set of assignments that satisfy the formula.
- $V$ represents the falsifying team: the set of assignments that contradict the formula.
This shift allows for compositional negation. In double team semantics, a formula $\neg \phi$ is satisfied by the pair $(U, V)$ if and only if $\phi$ is satisfied by the swapped pair $(V, U)$. By tracking falsification as explicitly as verification, negation becomes a first-class, symmetric operator, removing the syntactic limitations that plague traditional team-based logics.
Generalized Quantifiers and Atoms
The author extends Lindström’s definition of quantifiers to create "minor quantifiers." These allow for a more granular interpretation of how an agent verifies or falsifies a quantified statement, effectively bridging the gap between "lax" and "strict" interpretations often found in existing logic literature.
Furthermore, the framework demonstrates that various atoms used in dependence logic—such as dependence, inclusion, and independence atoms—can be viewed as special cases of "generalized atoms" within the double team structure. The paper also explores epistemic variants of quantifiers. For instance, a "total" existential quantifier requires an agent to have an "epistemically complete" understanding, knowing for every element in the domain whether it satisfies the condition or not.
Game-Theoretic Foundations
To provide an action-based account of logical meaning, the paper devises a semantic game played between two participants:
- The Agent: Aims to verify the formula.
- The Interrogator: Aims to falsify the formula.
The author proves an Equivalence Theorem: a double team $(U, V)$ satisfies a formula $\phi$ if and only if the Agent has a uniform survival strategy in the corresponding semantic game. This provides a robust foundation for the logic, linking abstract semantics to strategic interaction.
The Logic $DC^2$ and Computational Complexity
To demonstrate the practical utility of the framework, the author introduces $DC^2$, a logic that fuses two-variable dependence logic ($D^2$) with counting quantifiers ($FOC^2$). A key finding is that this combination does not push the logic into undecidability.
The paper establishes that both the satisfiability and finite satisfiability problems for $DC^2$ are NEXPTIME-complete. While this indicates high computational complexity, it confirms that $DC^2$ remains within the same complexity class as its parent logics, identifying a highly expressive yet still decidable fragment of team logic.
Conclusion and Future Work
Double team semantics offers a powerful solution to the negation problem in team-based logics while unifying the treatment of generalized quantifiers. While the NEXPTIME-complete complexity of $DC^2$ may limit immediate practical applications in software verification or database querying, the theoretical groundwork is significant.
Future research directions include extending the framework to higher-type quantifiers and developing "resource-conscious" semantics. In such a system, choosing witnesses in the semantic game would incur a cost, potentially modeling reasoning under limited cognitive or computational resources. Additionally, the author calls for deeper reflection on the definition of negation for non-first-order atoms to ensure mathematical and philosophical consistency.
Summary updated