TL;DR
This paper extends the classic Goldblatt-Thomason theorem to a specific fragment of modal logic with a universal modality, characterizing which classes of finite transitive frames can be defined. It also establishes hierarchies of expressive power for various team-based modal logics, providing a comprehensive map of their definability.
What Problem Does This Paper Address?
The paper tackles the problem of "definability" in modal logic, specifically focusing on frame definability. In modal logic, a formula can define a class of Kripke frames if that class is precisely the set of frames for which the formula is valid. The Goldblatt-Thomason theorem provides a fundamental characterization for basic modal logic: a class of frames is definable if and only if it's closed under certain structural operations (bounded morphic images, generated subframes, disjoint unions, and reflection of ultrafilter extensions).
This paper extends this line of research in two key directions:
- Relative Definability: It investigates definability not just in absolute terms, but relative to a specific class of frames (finite transitive frames). This is important because some properties might not be definable in general but become definable within a restricted class.
- Team Semantics Logics: It explores definability for a family of "team-based" modal logics. These logics, like dependence logic and inclusion logic, use sets of assignments (teams) instead of single assignments to evaluate formulas, leading to different expressive powers and semantic properties. The paper aims to understand how these team-based logics relate to each other and to standard modal logic in terms of what they can define.
Methods
The paper employs several key techniques:
- Goldblatt-Thomason Style Theorems: The core of the work involves adapting the well-known Goldblatt-Thomason theorem. This involves identifying structural properties of frame classes (like closure under bounded morphic images and generated subframes) that are equivalent to being definable by a set of formulas in a given logic.
- Jankov-Fine Formulas: For characterizing relative definability within finite transitive frames, the authors utilize a variant of Jankov-Fine formulas. These are specific modal formulas constructed from a given frame that capture its structure. The validity of these formulas in other frames is then used to establish equivalences.
- Team Semantics Definitions: The paper formally defines the semantics for various team-based logics (modal dependence logic, modal inclusion logic, modal team logic, etc.) using the concept of "teams" (sets of assignments).
- Hierarchy of Logics: By comparing the expressive power of different team-based logics, the authors establish strict hierarchies for both model definability and frame definability. This involves showing that certain logics can define classes of models/frames that others cannot.
- Closure Properties: The analysis of team-based logics relies heavily on understanding their closure properties, such as downward closure, union closure, and team bisimulation.
Datasets
Not discussed in the paper. The paper is theoretical and focuses on logical systems and their definability properties, rather than empirical evaluation on datasets.
Key Insights and Ideas
- Universal Modality's Role: The paper shows that a specific fragment of modal logic with a positively occurring universal modality (ML(+)) has a surprisingly strong definability power, equivalent to more complex team-based logics in certain contexts.
- Finite Transitive Frames are Key: The characterization of ML(+) definability relative to finite transitive frames is achieved by focusing on closure under generated subframes and bounded morphic images. This highlights the importance of these structural properties within this restricted class.
- Team Semantics Logics Form Hierarchies: A significant contribution is the clear mapping of expressive power for several team-based logics. The paper establishes strict inequalities (e.g., ML < MDL < EMDL) for both model and frame definability, providing a structured understanding of these logics.
- Equivalence of Logics: The research demonstrates equivalences in expressive power between seemingly different logics, such as EMINC and ML(◊), and MTL and ML(◊), simplifying the landscape of team-based logics.
Key Results
- ML(+) Definability: A class of finite transitive frames is definable in ML(+) relative to finite transitive frames if and only if it is closed under taking generated subframes and bounded morphic images.
- Model Definability Hierarchy: The paper establishes the following strict hierarchy for model definability: {ML, MINC, EMINC} <<sub>M</sub> MDL <<sub>M</sub> {EMDL, ML(◊), MTL}
- Frame Definability Hierarchy: A corresponding dichotomy is found for frame definability: {ML, MINC, EMINC} <<sub>F</sub> {MDL, EMDL, ML(◊), MTL}
- Corollaries: As a consequence, relative Goldblatt-Thomason-style theorems are obtained for various team-based logics, including modal dependence logic (MDL) and extended modal dependence logic (EMDL).
Limitations and Future Work
- Open Questions: The paper concludes with several open questions, including:
- Where modal independence logic (MIL) fits into the definability hierarchies.
- Whether a simpler fragment of ML(+) could capture the definability of MDL or MIL.
- The possibility of dropping the transitivity requirement in Theorem 3 by using "local bounded morphisms."
- Characterizing model definability of team-based logics using semantic constructions.
- Focus on Finite Frames: While the main result concerns definability within finite transitive frames, the broader context of modal logic often involves infinite frames. Future work could explore how these results extend or differ in the infinite case.
- Specific Logics: The paper focuses on a selection of team-based logics. Further research could investigate other variants or combinations of these logics.
Summary updated