Inaccessible Worlds and Irrelevance: Preliminary Report

Craig Boutilier

Abstract

Recent research has established that several frameworks for default reasoning—including $\epsilon$-semantics, preferential models, and specific modal conditional logics—are fundamentally equivalent. While these systems provide a robust core for default inference, they are generally too weak to handle the problem of irrelevance. This paper proposes an extension of modal conditional logics that allows for the expression of truth at inaccessible possible worlds. We demonstrate how this logic, denoted as CO, can axiomatize a preference relation on modal structures that is mathematically equivalent to Pearl’s 1-entailment and Lehmann’s rational closure. This approach suggests that many meta-logical systems of default inference can be internalized within the object logic itself.

Introduction: The Irrelevance Problem

In the field of Artificial Intelligence and Knowledge Representation, default reasoning allows systems to make common-sense assumptions, such as "Normally, birds fly." While standard conditional logics successfully capture the hierarchy of normality (e.g., recognizing that penguins are exceptional birds and do not fly), they suffer from a significant limitation: the irrelevance problem.

If a system knows that "Birds fly," it should logically conclude that "Green birds fly," assuming greenness is irrelevant to flight. However, in standard preferential logics, the system cannot make this leap. Logically, a green bird could be an exception just as a penguin is. To resolve this, researchers have traditionally relied on "meta-logical" machinery—algorithms like Pearl’s System Z or Lehmann’s rational closure—to force the system to assume worlds are as normal as possible. This paper investigates whether this capability can be brought entirely inside the logic itself.

The Logic of Inaccessible Worlds (CO)

The author’s methodological innovation lies in the development of a Kripke-style possible worlds semantics where the accessibility relation represents a normality ordering. In this framework, a world $v$ is accessible to world $w$ if $v$ is at least as normal as $w$.

To internalize the assumption of normality, the paper introduces the modal logic CO. Unlike standard modal logics that only reason about accessible worlds using the $\Box$ operator, CO introduces a dual operator, $\overline{\Box}$:

  • $\Box A$: $A$ is true in all accessible (more normal) worlds.
  • $\overline{\Box} A$: $A$ is true in all inaccessible (less normal) worlds.

By utilizing both operators, the logic can express constraints on the entire universe of possible worlds. This allows for a logical version of "only knowing," where the system can specify that no worlds exist beyond those explicitly required by the knowledge base.

Key Results and Equivalence

The paper provides a formal axiomatization for CO and its extension CO*, proving that they accurately characterize their respective classes of models (Theorems 1 and 2). The most significant contribution, however, is the proof of equivalence between this logical framework and established meta-logical systems:

  1. Internalizing Meta-Logic: The author defines a preference relation over modal structures that prefers models where worlds are "pushed" to be as normal as possible. This effectively internalizes the ranking algorithms used in System Z.
  2. Equivalence to 1-Entailment: Theorems 3 and 4 prove that the minimal Z-ranking of worlds corresponds exactly to the theory-dependent preference ranking of CO*-models.
  3. Solving Irrelevance: The logic successfully sanctions inferences involving irrelevant properties. Given the rule $Bird \Rightarrow Fly$, the closure of the theory $Cl(T)$ entails $(Bird \land Green) \Rightarrow Fly$, while correctly maintaining that $(Bird \land Penguin) \Rightarrow \neg Fly$.

Discussion and Limitations

By moving the machinery of default reasoning from an external algorithm into the object language, the author provides a more unified theoretical foundation for non-monotonic reasoning. This is conceptually similar to how second-order circumscription internalizes the concept of minimal models in predicate logic.

However, the paper acknowledges certain limitations. The notion of irrelevance captured here mirrors the behavior of rational closure, which is known to be somewhat "coarse." Specifically, it faces the property inheritance problem: if a subclass is exceptional in one regard (e.g., penguins cannot fly), the system may struggle to infer that the subclass still inherits other irrelevant properties from the superclass (e.g., penguins have wings).

Conclusion and Future Work

This preliminary report demonstrates that the notion of inaccessible worlds is a powerful tool for axiomatizing default inference. Future work will focus on applying this framework to belief revision and exploring whether the underlying logic can be weakened (e.g., from S4.3 to S4) while still providing the same inferential benefits. Additionally, the author suggests that this logic could be used to capture even more sophisticated systems, such as the maximum entropy formalism.

Summary updated

Abstract

Recently, the relationship between several forms of default reasoning based on conditional defaults has been investigated, In particular, the systems based on e-semantics, preferential models and (fragments of) modally-defined conditional logics have been shown to be equivalent. These systems form a plausible core for default inference, but are too weak in general, failing to deal adequately with irrelevance. We propose an extension of the (modal) conditional logics in which one can express the truth of sentences at inaccessible possible worlds and show how this logic can be used to axiomatize a simple preference relation on the modal structures of this logic. This preferential semantics is shown to be equivalent to 1-entailment and rational closure. We suggest that many metalogical systems of default inference can be axiomatized within this logic, using the notion of inaccessible worlds.
BibTeX
@inproceedings{boutilier1991inaccessible,
  author = {Craig Boutilier},
  title = {{Inaccessible Worlds and Irrelevance: Preliminary Report}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure