Minimal Change in Modal Logic S5

Carlos Aguilera-Ventura, Jonathan Ben-Naim, Andreas HerzigAAAI 2025 · DOI

TL;DR

This paper extends belief revision theory to modal logic S5, introducing new postulates and a distance-based semantic framework to handle modalities. The authors propose a novel revision operation, *Dsum, which satisfies these postulates and offers a more nuanced approach to belief change, particularly in handling strict implication and syntax sensitivity.

What Problem Does This Paper Address?

The standard framework for belief revision, known as the AGM (Alchourrón, Gärdenfors, and Makinson) framework, primarily deals with propositional logic. However, real-world reasoning often involves modalities, which allow us to express concepts like necessity and possibility. The existing AGM framework struggles to adequately revise belief sets containing these modal operators. For instance, it doesn't clearly distinguish between necessary truths and contingent ones, nor does it offer a principled way to handle belief changes when the input information is modally inconsistent with the current beliefs. This paper aims to bridge this gap by developing an axiomatic and semantic analysis of belief revision for modal logic S5, specifically addressing the challenge of "minimal change" in the presence of modalities.

Methods

The authors introduce three new postulates (M1-M3) that go beyond the standard AGM postulates to capture the idea of minimal change in modal logic. On the semantic side, they propose a family of distance-based revision operations. This involves lifting the concept of distance from propositional valuations to sets of valuations, which is how S5 is semantically represented. They define a family of pseudo-distances between sets of valuations and introduce axioms for these distances. A key contribution is the development of a lexicographical distance between "pointed models" (a set of valuations and an actual world) which prioritizes changes to the actual world before modifying the set of possible worlds. They then show that specific pseudo-distances, when used to induce revision operations, satisfy the proposed modal postulates. Notably, the *Dsum revision operation, derived from a specific distance measure, is shown to satisfy all three modal postulates.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Modalities Matter for Belief Revision: The paper highlights that simply extending propositional belief revision to modal logic isn't straightforward. The presence of modal operators like necessity ($\Box$) and possibility ($\Diamond$) introduces new complexities that require dedicated postulates and semantic treatments.
  • Beyond Propositional Consistency: The authors distinguish between propositional consistency (sharing a pointed model) and modal consistency (sharing a model, but not necessarily a pointed one). This distinction is crucial for understanding how to revise beliefs when information is modally but not propositionally inconsistent.
  • Lexicographical Distance for Minimal Change: The introduction of a lexicographical distance between pointed models is a novel approach. It formalizes the intuition that minimal change should first attempt to adjust the "actual world" before altering the set of "possible worlds," providing a more granular control over belief updates.
  • Strict Implication as a Solution to Syntax Sensitivity: The paper revisits the classic debate about syntax sensitivity in belief revision. They argue that by using the strict implication operator ($\Box(\phi \rightarrow \psi)$) instead of material implication ($\phi \rightarrow \psi$), the problematic cases where logically equivalent formulas lead to different revision outcomes can be resolved, providing a logical foundation for this distinction.

Key Results

  • The paper introduces three new postulates (M1-M3) for modal belief revision that capture minimal change in the presence of modalities.
  • They propose a family of distance-based revision operations for modal logic S5.
  • The *Dsum revision operation, derived from a specific distance measure, is shown to satisfy all three proposed modal postulates (M1-M3).
  • The authors demonstrate that using strict implication, rather than material implication, can resolve counterexamples against syntax-insensitive revision operations.

Limitations and Future Work

  • Logic Specificity: The current work focuses on S5. Extending the framework to other modal logics (like K, KD45, K45, S4) is a significant future direction, requiring careful adaptation of the distance measures.
  • Completeness of Postulates: The authors acknowledge that a complete set of postulates characterizing their revision operation is still an open problem.
  • Alternative Distance Measures: Exploring other distance measures beyond Hamming-based ones, such as those based on set inclusion (like Satoh's revision or Winslett's update), is suggested.
  • Broader Implications: The paper hints at connections to truthlikeness in philosophy of science and the potential for applying their framework to other conditional logics beyond strict implication.

Summary updated

BibTeX
@inproceedings{aguileraventura2025minimal,
  author = {Carlos Aguilera-Ventura and Jonathan Ben-Naim and Andreas Herzig},
  title = {{Minimal Change in Modal Logic S5}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33620},
}
Figure