TL;DR
This paper extends the classic Goldblatt-Thomason theorem to the realm of team semantics, a logic framework where formulas are evaluated over sets of assignments. The authors provide a precise characterization of what classes of finite transitive frames can be defined by a specific modal logic fragment (ML(U^+)) within this team-based setting. This work also establishes hierarchies of expressive power for various team-based modal logics, offering a clearer understanding of their definability capabilities.
What Problem Does This Paper Address?
The field of modal logic, which deals with reasoning about necessity and possibility, has a well-established theory of definability. The Goldblatt-Thomason theorem, for instance, precisely characterizes which classes of Kripke frames can be defined by formulas of basic modal logic. However, recent research has explored "team semantics," a generalization of Kripke semantics where formulas are evaluated over sets of assignments (teams) rather than single assignments. This shift introduces new logics with different expressive powers. This paper addresses the question of whether the powerful definability results from classical modal logic can be translated to these team-based logics, specifically focusing on a fragment of modal logic with a positive universal modality (ML(U^+)) and its definability relative to finite transitive frames. It also aims to map out the expressive power and definability landscape of several other prominent team-based modal logics.
Methods
The core of the paper involves adapting and extending classical modal logic techniques to the team semantics framework. Key methods include:
- Generalizing Goldblatt-Thomason Theorems: The authors extend the spirit of the Goldblatt-Thomason theorem to team semantics. This involves characterizing frame definability not just by classes of frames but also by specific logical fragments within the team semantics context.
- Jankov-Fine Formulas: A crucial technical tool is the use of Jankov-Fine formulas. These are constructed to precisely capture the structure of finite transitive frames. The paper adapts these formulas for the team semantics setting to prove its main definability results.
- Frame Constructions: Standard frame constructions like generated subframes, bounded morphic images, and ultrafilter extensions are employed. These are essential for defining and proving properties of definable classes of frames.
- Team Semantics Definitions: The paper meticulously defines the semantics for various team-based modal logics, including modal logic with universal modality, modal dependence logic, modal inclusion logic, and modal team logic.
- Hierarchy of Logics: The authors establish strict hierarchies of expressive power and definability for these logics, both in terms of global model definability and frame definability.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Team Semantics Definability Mirrors Classical Logic (with caveats): The paper shows that for ML(U^+), the characterization of definable frame classes in team semantics is remarkably similar to the classical Goldblatt-Thomason theorem: closure under generated subframes and bounded morphic images. This suggests a strong structural correspondence between classical and team-based definability for certain logics.
- A Richer Landscape of Logics: The study reveals a complex hierarchy of expressive power among team-based modal logics like modal dependence logic, inclusion logic, and team logic. This clarifies their relative strengths and weaknesses.
- Trichotomy and Dichotomy: The paper establishes a trichotomy for global model definability and a dichotomy for frame definability across the studied team-based logics, providing a clear organizational structure for their expressive capabilities.
- Jankov-Fine Formulas as Powerful Tools: The successful adaptation and use of Jankov-Fine formulas highlight their utility in bridging the gap between frame properties and logical definability in the team semantics context.
Key Results
- ML(U^+) Definability: A class of finite transitive frames is definable in ML(U^+) relative to finite transitive frames if and only if it is closed under taking generated subframes and bounded morphic images.
- Logic Hierarchies:
- Model Definability: {ML, MINC, EMINC} <_M MDL <_M {EMDL, ML(U), MTL}
- Frame Definability: {ML, MINC, EMINC} <_F {MDL, EMDL, ML(U), MTL}
- Equivalences: The paper proves equivalences such as EMINC =_M ML(U) and EMINC =_F ML(U), and MTL =_M ML(U) and MTL =_F ML(U).
- Corollaries: As a consequence, relative Goldblatt-Thomason-style theorems are obtained for several team-based logics.
Limitations and Future Work
- Transitivity Requirement: Theorem 3, which characterizes ML(U^+) definability, is stated for finite transitive frames. The authors pose a question about whether the requirement of transitivity can be dropped by using the notion of local bounded morphisms.
- MIL/EMIL Definability: The paper concludes with open questions regarding the definability of modal independence logic (MIL) and extended modal independence logic (EMIL) with respect to modal definability.
- Semantic Constructions for Model Definability: A general question is raised about characterizing model definability of team-based logics in terms of semantic constructions.
- Natural Fragments of ML(U^+): The paper asks if there are natural fragments of ML(U^+) that coincide with MDL or MIL in terms of model definability.
Summary updated