Belief Contraction without the Recovery Postulate

26 concepts13 papers1 proposal

In classical logic, changing your mind follows a elegant mathematical symmetry. If you remove a belief $\phi$ from your knowledge base (a process called contraction) and then immediately add it back (revision), you should return exactly to your original state of knowledge. This principle is known as the Recovery Postulate, and it serves as a cornerstone of the foundational AGM framework for belief change. It ensures that the contraction process is clean and does not cause collateral damage to unrelated beliefs.

However, when we move from theoretical propositional logic to the practical, lightweight languages that power the Semantic Web and modern ontologies—such as Description Logics (DLs) and Horn fragments—this symmetry completely breaks down.

The Expressive Wall of Lightweight Logics

To understand why recovery fails, we must first look at why these practical logic fragments exist. Classical first-order logic is highly expressive, but that expressivity makes automated reasoning computationally expensive or even undecidable. To build scalable knowledge bases, computer scientists intentionally strip away certain logical operators.

As noted by Guilin Qi et al. in A Survey of Revision Approaches in Description Logics, lightweight description logics typically lack a universal negation operator ($\neg$). Furthermore, as Zhe Wang et al. point out in Extending AGM Contraction to Arbitrary Logics, these fragments also frequently omit the disjunction operator ($\lor$, or "OR") to maintain fast query performance.

The absence of these operators creates a severe challenge for maintaining consistency. Without negation, standard contradiction-resolution techniques cannot be applied directly because there is no syntactic way to isolate or negate a specific problematic axiom (Marc Aiguier et al.). More fundamentally, the lack of disjunction destroys the mechanism that makes the recovery postulate work.

Why Recovery Fails: The Inevitable Logical Gap

To build intuition for why recovery requires disjunction, imagine a simple knowledge base that contains two facts:

  1. Employee(Alice) (Alice is an employee)
  2. Manager(Alice) -> Employee(Alice) (All managers are employees)

Suppose we want to contract the belief Employee(Alice). In classical logic, we want to drop the definitive statement that Alice is an employee, but we want to retain as much residual information as possible. Classical AGM contraction achieves this by keeping a weakened disjunctive statement: Employee(Alice) v Manager(Alice). If we later learn and re-add Employee(Alice), this disjunction allows us to perfectly reconstruct our original knowledge base.

But what happens if our logic language does not allow the $\lor$ operator?

As Zhe Wang et al. demonstrate in Rational Elimination of DL-Lite TBox Axioms, without disjunction, we cannot form these intermediate, weakened safety nets. We are faced with a brutal binary choice: we must either keep an axiom fully or delete it entirely. To guarantee that Employee(Alice) is truly removed, we are forced to over-erase surrounding axioms that might implicitly re-entail it.

This creates an unbridgeable "logical gap." In Concept Contraction in the Description Logic EL, Tjitze Rienstra et al. explain that lightweight description logics simply lack the expressive power to represent the exact logical difference between a concept and its generalization. Because the logic cannot capture this boundary, the contraction process becomes inherently lossy.

Consequently, as Giorgos Flouris et al. proved in Inconsistencies, Negations and Changes in Ontologies, the recovery postulate is fundamentally incompatible with any logic lacking a universal negation or disjunction operator. If you drop a belief and add it back, the collateral data you were forced to over-erase is gone forever.

Shifting the Paradigm: Relevance and Belief Withdrawal

If recovery is mathematically impossible in these fragments, how do we define a "rational" way to remove information? The consensus across recent research is that we must abandon the recovery postulate entirely and replace it with alternative constraints.

In Entrenchment-Based Horn Contraction, Zhiqiang Zhuang argues that belief change in computationally efficient fragments is better modeled as a belief withdrawal operation. In a withdrawal framework, we accept from the outset that a cycle of removal and re-addition will not preserve the original state.

To ensure that this withdrawal still respects the principle of "minimal change," researchers substitute recovery with the relevance and fullness postulates.

Classical AGM Contraction:
[Original Knowledge] -> (Contract φ) -> [Over-erased State + Disjunctive Safety Nets] -> (Re-add φ) -> [Original Knowledge]

Relevance-Based Withdrawal:
[Original Knowledge] -> (Contract φ via Relevance) -> [Cleanly Severed State] -> (Re-add φ) -> [Altered Knowledge State]

As detailed by Márcio Moretto Ribeiro et al. in Contraction on the Semantic Web: On the Role of Relevance and Recovery, a relevance-based contraction operator dictates that an axiom can only be deleted if it directly contributed to entailing the belief being removed. If an axiom does not structurally support the targeted belief, it is completely safe from erasure. The authors proved that for any monotonic and compact logic, this relevance-based approach is mathematically equivalent to the classical "partial meet contraction" method, providing a rock-solid foundation for information removal without recovery.

This pivot to relevance has allowed researchers to build highly effective, tailored update operators across various restricted languages:

By shifting the goal from perfect restoration (recovery) to targeted deletion (relevance), this body of work provides the theoretical tools necessary to safely evolve knowledge bases on the Semantic Web, proving that a belief change framework can be entirely rational even when it is inherently forgetful.

Key Foundational Work

Inconsistencies, Negations and Changes in Ontologies (2006) — contributed 2 concept elements to this direction.
A Survey of Revision Approaches in Description Logics (2008) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 13 papers
  2. Version 1 · 2026-10-04 · 26 papers
Cite this direction

Latest version (a living page):

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

This exact version (version 2, frozen text):

@misc{lacuna_recovery_postulate_incompatibility_19738f5d_v2,
  title = {recovery postulate incompatibility},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recovery-postulate-incompatibility/rdr_19738f5dab2843989290bfe1f825b75d/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake