Abstract
Sahlqvist's Theorem is a fundamental result in modal logic, identifying a syntactic class of formulas that are canonical and thus complete with respect to their corresponding frame classes. This paper extends these results to the broader framework of coalgebraic logic. By leveraging functor presentations, the authors demonstrate that complex transition systems can be treated as quotients of simpler polynomial functors. This allows for the "transportation" of completeness results from Boolean Algebras with Operators (BAOs) to a wide variety of dynamical systems, including those described by Graded Modal Logic.
Introduction
In the study of modal logic, the Sahlqvist theorem provides a powerful tool for establishing the completeness of axiomatic systems. A formula is Sahlqvist if it belongs to a specific syntactic class that guarantees its canonicity. However, as computer science moves toward more diverse transition systems—such as probabilistic, non-deterministic, or weighted automata—the classical Kripke-frame-based Sahlqvist results become insufficient.
Coalgebraic logic offers a unified mathematical framework for these systems. Yet, until recently, completeness results for specific axioms (like transitivity or symmetry) had to be proven manually for each new functor type. This research addresses this gap by providing a general, unified Sahlqvist theorem for the coalgebraic setting.
The Coalgebraic Framework and Methodology
The authors' strategy for proving completeness relies on a "transportation" method that connects complex coalgebraic logics to well-understood algebraic structures. The methodology is built upon three main pillars:
- Functor Presentations: Every accessible functor $T$ (representing a transition type) can be seen as a quotient of a simpler polynomial functor $S$.
- BAO Connection: Polynomial functors correspond naturally to Boolean Algebras with Operators (BAOs). Since Sahlqvist results are well-established for BAOs, the authors first prove completeness for logics associated with these polynomial functors.
- The Translation Theorem: The core contribution is a mechanism to translate formulas and proofs from the simpler polynomial logic ($S$) to the target coalgebraic logic ($T$).
The logic employed is the $\nabla$-style (or Moss) logic, which utilizes a "cover" modality. This modality is more structurally flexible for categorical proofs than the standard box ($\Box$) and diamond ($\Diamond$) operators.
The figure above details the inference rules for this system, including the specific rules for the $\nabla$ operator ($\nabla 1, \nabla 2, \nabla 3$) and the distributivity axiom that bridges conjunctions and disjunctions within the coalgebraic structure.
Key Insights
A central insight of the paper is that the classical path to completeness—embedding an algebra into a "canonical extension"—remains viable in the abstract coalgebraic setting. By viewing complex logics as filtered versions of simpler ones, researchers can solve difficult completeness problems by analyzing the "pre-images" of formulas in the simpler polynomial logic.
Furthermore, the authors address the challenge of "deadlocks" in systems with infinite signatures. By introducing "acceptable sets" of frame conditions, they ensure that the mathematical structures remain well-behaved even when an infinite number of moves or operators are possible.
Main Results
The paper culminates in several significant theorems that bridge the gap between abstract category theory and modal logic:
- Theorem 4: Establishes Sahlqvist completeness for polynomial functors, providing the necessary link between BAOs and coalgebraic logic.
- Theorem 14 (Translation Theorem): Proves the soundness of the translation process, ensuring that provability in the presentation logic implies provability in the target logic.
- Theorem 16: The main result, providing a general Sahlqvist Completeness Theorem for any Set-functor that preserves weak pullbacks. This provides a syntactic criterion to guarantee completeness for a vast range of modal logics.
- Application to Graded Modal Logic (GML): The authors apply their framework to GML, successfully defining a "graded" version of transitivity and proving its completeness for transitive, finitely-branching multiset frames.
Conclusion and Future Directions
While this work provides a robust foundation for Sahlqvist completeness in coalgebraic logic, some limitations remain. The results currently apply to functors preserving weak pullbacks on the category of Sets. Future research may extend these findings to fixed-point logics (like the $\mu$-calculus) or hybrid logics. Additionally, the treatment of infinite signatures via "acceptable sets" offers a path toward a more comprehensive theory of strong completeness for infinite axiom sets.
Summary updated