Self-Reference, Knowledge, Belief, and Modality

Donald PerlisAAAI 1986

Abstract

For decades, the field of Artificial Intelligence has grappled with the perceived "danger" of first-order logic (FOL) when applied to self-referential mental states. Richard Montague’s 1963 result suggested that treating modal operators like "Knowledge" or "Belief" as predicates within FOL leads to logical inconsistency. Donald Perlis challenges this paradigm, arguing that FOL's expressive power is essential for AI and demonstrating how to achieve consistency through "qualifiedly substitutive" frameworks.

Introduction: The Problem of Inconsistency

In the 1960s, logician Richard Montague published a famous "negative result" showing that if you treat modal operators as predicates in first-order logic—essentially treating sentences as objects that can be named and referred to—you quickly run into inconsistencies. This is because first-order logic allows for self-reference, which, when combined with certain intuitive axioms about truth and knowledge, leads to versions of the "Liar Paradox" (e.g., "This sentence is false").

Because of Montague’s work, most researchers shifted toward modal logics. While these are "safer," they are often significantly weaker. They struggle to represent common-sense notions like "I have a false belief" because they lack the expressive power to treat beliefs as variables. Perlis argues that for Artificial Intelligence to be truly effective, an agent must be able to refer to its own beliefs—a property he calls "referenceability."

Methodology: Qualified Substitution

The paper uses formal mathematical logic to construct and analyze different theories of modality. The key methodological innovation is the distinction between unqualifiedly substitutive and qualifiedly substitutive theories.

  • Unqualifiedly substitutive: These allow an operator to assert the result of any substitution. Perlis proves these are always inconsistent (Theorem 1).
  • Qualifiedly substitutive: These use a specific logical mechanism to avoid paradox. Instead of allowing a direct assertion of a negated self-referential statement, the theory uses a "qualified" schema that prevents the logic from creating a contradiction.

Perlis applies these qualified mechanisms to create three specific consistent theories:

  1. Int (Internal): A theory for belief that allows for introspection (if I believe $\alpha$, I believe that I believe $\alpha$).
  2. Ext (External): A theory for knowledge that enforces truth (if I know $\alpha$, then $\alpha$ is true).
  3. Omni: A combined theory that allows an agent to reason about both its beliefs and its knowledge simultaneously.

Key Insights and Ideas

The Modal Safety Illusion

One of the most striking insights is that modal logics (like S5) aren't actually "safer" than first-order logic. Perlis shows that if you add self-reference and substitution capabilities to modal logic, it becomes just as inconsistent as the first-order versions it was meant to replace.

Internal vs. External Views

Perlis suggests that paradoxes arise from mixing two different perspectives. An agent's internal view (Belief) is about what it affirms to be true. Its external view (Knowledge) is a comparison of those beliefs against an "unauthenticated outer world."

The "False Belief" Requirement

A rational agent must be able to believe that some of its other beliefs might be wrong. Traditional modal logics cannot easily say "There exists an $x$ such that I believe $x$ and $x$ is false." First-order logic can, and Perlis shows how to make that consistent.

Results

Perlis provides several key proofs that re-open the door for syntactic (first-order) approaches to AI reasoning:

  • Theorems 1 & 5: Proves that any "unqualifiedly substitutive" theory (first-order or modal) is inherently inconsistent.
  • Theorem 2: Proves that "qualifiedly substitutive" first-order theories can maintain consistency.
  • Theorems 6, 7, & 8: These serve as existence proofs for the proposed frameworks. Perlis demonstrates that it is mathematically possible to have consistent first-order theories (Int, Ext, and Omni) that handle self-referential belief and knowledge.

Limitations and Future Work

While these theories are consistent, they currently assume "logical omniscience," meaning the agent instantly knows all logical consequences of its beliefs. In practice, AI agents have limited time and memory. Perlis acknowledges that these theories need to be adapted for "limited reasoning," pointing toward "step-logics" as a potential solution for agents that must reason in real-time. Additionally, while the paper proves consistency, it does not provide an algorithm for efficiently querying these self-referential beliefs in large-scale knowledge bases.

Summary updated

BibTeX
@inproceedings{perlis1986self,
  author = {Donald Perlis},
  title = {{Self-Reference, Knowledge, Belief, and Modality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure