Belief Revision

Origin. Alchourrón, Gärdenfors, and Makinson introduced AGM theory (1985). Formalizes rational belief change. Three operations: expansion (adding belief), contraction (removing belief), revision (adding belief while maintaining consistency). Foundational for AI knowledge base maintenance and epistemology.

Models. Rational belief change. Agents have belief sets (logically closed). New information may conflict with existing beliefs. Revision prioritizes new information while minimizing change. Contraction removes beliefs while preserving as much as possible. Epistemic entrenchment orders beliefs by how firmly held.

Formalism.

Belief set: K = Cn(K) (closed under logical consequence) K ⊆ L (set of sentences)

Three operations:

Expansion K + φ = Cn(K ∪ {φ})
Contraction K - φ (remove φ, close)
Revision K * φ = (K - ¬φ) + φ (Levi identity)

AGM postulates for revision:

Closure: K * φ = Cn(K * φ)
Success: φ ∈ K * φ
Inclusion: K * φ ⊆ K + φ
Vacuity: if ¬φ ∉ K, then K * φ = K + φ
Consistency: K * φ is consistent if φ is consistent
Extensionality: if φ ↔ ψ, then K * φ = K * ψ 7-8. Superexpansion and subexpansion (for conjunctions)

Epistemic entrenchment: φ ≤ ψ means ψ is at least as entrenched as φ. Less entrenched beliefs are contracted first.

Iterated revision: Darwiche-Pearl postulates extend AGM to sequences of revisions.

Symbols.

Symbol	Unicode	Name	Meaning
+	U+002B	Plus sign / Expansion	Add a sentence and close under consequence
-	U+002D	Hyphen-minus / Contraction	Remove a sentence and close
*	U+002A	Asterisk / Revision	K * φ : add a sentence while restoring consistency
∗	U+2217	Asterisk operator / Revision	The same operator, written so as not to trigger emphasis
⊆	U+2286	Subset	Belief set inside the language; the inclusion postulate
∪	U+222A	Union	Sentences joined before closure in an expansion
∈	U+2208	Membership	Sentence belongs to a belief set
∉	U+2209	Non-membership	Sentence absent from the belief set, as in vacuity
¬	U+00AC	Negation	Sentence contracted first under the Levi identity
↔	U+2194	Biconditional	Logical equivalence, as used in extensionality
≤	U+2264	Less-than or equal to / Entrenchment	ψ is held at least as firmly as φ
⊨	U+22A8	Double turnstile / Entailment	Consequence drawn from a revised base
φ	U+03C6	Greek small letter phi	Sentence being added or removed
ψ	U+03C8	Greek small letter psi	Second sentence, compared or queried
K	—	Belief set	Sentences accepted, closed under consequence
L	—	Language	Sentences available to the agent
Cn	—	Consequence closure	Cn(K) : everything K entails

Metatheory. Alchourrón, Gärdenfors and Makinson proved the theorem that gives the postulates their standing: an operation is a partial meet contraction — an intersection of some selection among the maximal subsets of K that fail to imply φ — if and only if it satisfies the six basic contraction postulates, and it is transitively relational partial meet if and only if it satisfies the two supplementary postulates as well. Equivalent characterizations followed, so that the syntactic, ordinal and semantic presentations carry the same content: Gärdenfors and Makinson (1988) matched contraction to epistemic entrenchment orderings, Grove (1988) to systems of spheres over maximal consistent sets, and Katsuno and Mendelzon (1991) to total preorders on interpretations. Complexity depends on base logic: for propositional knowledge bases, deciding K ∗ φ ⊨ ψ is Π₂ᵖ-complete under most of the standard operators (Eiter and Gottlob 1992), not coNP-complete — coNP is the cost of deduction from the unrevised base, and revision adds an alternation by quantifying over the maximal consistent remnants. Dalal's operator is the outlier at Θ₂ᵖ = P^NP[log n], since its cardinality-minimality can be resolved by binary search over an NP oracle.

Applies to. Database update and maintenance. AI reasoning under changing information. Philosophy of science (theory change). Legal reasoning (precedent and amendment). Preference change modeling. Multi-agent belief dynamics.

Limitations. Belief sets are closed under consequence, so the agent believes everything its beliefs entail, and the theory has nothing to say about revising a finite base: distinct bases with the same closure are indistinguishable to it, yet revise differently in practice. Recovery, the postulate that contracting φ and adding it back restores K, is the least defended of the eight, and withdrawal operations that abandon it satisfy all the rest. Success forces the input into the revised set unconditionally, so information cannot be rejected as less credible than what it contradicts. Gärdenfors (1986) proved the postulates incompatible with the Ramsey test for conditionals over any non-trivial belief set, so conditionals cannot be carried as ordinary beliefs. Iteration lies outside the theory as stated: Darwiche and Pearl (1997) showed that the postulates, formulated over belief sets, conflict with plausible principles for successive revisions, and the repair requires operators on epistemic states carrying more than the belief set.