Expressive Equivalence and Definability in Extended Modal Logics

19 concepts9 papers1 proposal

Modal logic is celebrated for its "locality." By evaluating truth from the perspective of a single world and traversing only accessible paths, it remains computationally well-behaved and decidable. However, this locality can also be a prison: standard modal logic cannot express global properties (such as "every world satisfies $P$") or complex dependencies between variables.

To break out of these constraints, logicians introduce extensions: universal modalities, propositional quantifiers, and team semantics. Intuitively, these extensions should create a wild west of increasingly complex, incomparable logics. Yet, a remarkable body of research reveals the opposite: a phenomenon of expressive equivalence and definability collapse. Seemingly disparate extensions often possess identical expressive power or collapse into simpler, well-understood modal fragments.

Bridging the Local-Global Divide via Universal Modalities

The simplest way to break modal locality is to introduce a universal modality—an operator that allows quantification over all possible worlds, not just accessible ones. When combined with other structural tools, this simple addition acts as a bridge to powerful global logics.

For instance, in A modal perspective on monadic second-order alternation hierarchies, Antti Kuusisto demonstrated that Second-Order Propositional Modal Logic (SOPML) equipped with a universal modality is expressively equivalent to Monadic Second-Order Logic (MSO). By quantifying over propositions (which act as sets of worlds) and using the universal modality to span the entire model, the logic can mirror the full alternation hierarchy of MSO over finite graphs.

Tadeusz Litak explored this boundary in One Modal Logic to Rule Them All?, showing that bundling a global modality with a propositional quantifier yields the exact same expressive power as standard SOPML over complete algebraic structures. This reveals that the global reach of the universal modality removes the need for more complex, unconstrained syntactic machinery.

Team Semantics and the Definability Collapse

Another major paradigm shift comes from team semantics. Instead of evaluating a formula at a single world, formulas are evaluated against a team—a set of worlds or variable assignments. This framework allows the logic to express dependencies and majorities across states. For example, Arnaud Durand et al. in Dependence Logic with a Majority Quantifier showed that adding a majority quantifier to dependence logic under team semantics allows it to scale up to match the expressive power of second-order logic with majority quantifiers ($SO(\text{Most})$).

However, when these team-based extensions are applied to modal frameworks, they often exhibit a surprising structural simplification. In The Expressive Power of Modal Dependence Logic, Lauri Hella et al. proved that Extended Modal Dependence Logic ($EMDL$) and Modal Logic with intuitionistic disjunction ($ML(\otimes)$) are expressively equivalent, despite their radically different syntactic starting points.

More strikingly, when evaluating what kinds of frame structures these logics can define, the expected explosion in expressive power often completely deflates. Katsuhiko Sano et al. investigated this in Characterising modal definability of team-based logics via the universal modality. They discovered a "definability collapse": several complex team-based modal logics turn out to be no more powerful than standard modal logic ($ML$) or modal logic with a universal modality ($ML(\Box^+)$) when characterizing frame and model classes.

Why It Works: Bisimulation and Structural Closure

Why do these complex, team-based, and quantified logics collapse into simpler modal variants? The answer lies in the deep model-theoretic properties that govern modal logic: bisimulation and structural closure.

In classical modal logic, the Goldblatt-Thomason theorem dictates that a class of frames is definable if and only if it is closed under structural operations like generated subframes and bounded morphic images. In Characterizing Relative Frame Definability in Team Semantics via the Universal Modality, Katsuhiko Sano et al. extended this characterization to fragments containing a universal modality over finite transitive frames. They showed that even with the added power of the universal modality or team semantics, the logic remains bound by these fundamental structural closure properties.

Furthermore, the expressive boundaries of these extended logics are precisely mapped using generalized notions of bisimulation. Just as standard bisimulation characterizes the limits of basic modal logic, specialized bisimulations capture the limits of extended formalisms:

  • Helle Hvid Hansen et al. in Bisimulation for Neighbourhood Structures demonstrated a Van Benthem-style characterization theorem where behavioral equivalence precisely captures the modal fragment of first-order logic over neighborhood models.
  • Luc Segoufin et al. in Unary negation introduced "UN-bisimulations" to show how restricting negation to formulas with at most one free variable creates a highly expressive yet robustly decidable fragment of first-order logic.

Because these logics must preserve these generalized bisimulations, they cannot distinguish between models that share the same structural backbone. This explains why adding complex syntax—like definite descriptions, as explored by Przemyslaw Andrzej Walega et al. in Hybrid Modal Operators for Definite Descriptions—often lands them in an expressive middle ground rather than granting them unconstrained power. They can uniquely identify a single world satisfying a property, but they still cannot count or distinguish models beyond the limits imposed by their structural equivalences.

Summary

The landscape of extended modal logics is not an infinite hierarchy of increasingly unmanageable systems. Instead, through the lens of universal modalities and team semantics, we see a highly unified ecosystem. The apparent complexity of tracking sets of worlds or global states is tightly constrained by structural bisimulations, leading to a beautiful simplification where powerful global properties can be captured without losing the elegant, structural essence of modal logic.

Key Foundational Work

A modal perspective on monadic second-order alternation hierarchies (2008) — contributed 1 concept elements to this direction.
Bisimulation for Neighbourhood Structures (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_expressive_equivalence_d9a9dd42,
  title = {expressive equivalence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressive-equivalence/rdr_d9a9dd4226ec4f15b80bf3a10923ac6b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_expressive_equivalence_d9a9dd42_v1,
  title = {expressive equivalence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressive-equivalence/rdr_d9a9dd4226ec4f15b80bf3a10923ac6b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake