AGM Belief Revision

Origin. Alchourrón, Gärdenfors, Makinson (1985). Rational belief change. Contraction and revision. Postulates. Foundation of belief dynamics.

Models. Belief sets change rationally. Three operations: expansion, contraction, revision. AGM postulates characterize. Epistemic entrenchment. Rational belief management.

Formalism.

Belief set: K = deductively closed set of sentences. Cn(K) = K. Theory of beliefs. Consistent (usually).

Three operations: K + φ: expansion (add φ, close). K - φ: contraction (remove φ, minimal change). K * φ: revision (add φ, maintain consistency).

Levi identity: K * φ = (K - ¬φ) + φ. Revision = contract negation, then expand. Reduces revision to contraction.

Harper identity: K - φ = K ∩ (K * ¬φ). Contraction from revision. Interdefinability.

AGM postulates for revision: K1: K * φ is belief set. K2: φ ∈ K * φ. K3: K * φ ⊆ K + φ. K4: If ¬φ ∉ K, then K + φ ⊆ K * φ. K5: K * φ = K_⊥ only if ⊢ ¬φ. K6: If ⊢ φ ↔ ψ, then K * φ = K * ψ. K7, K8: supplementary postulates.

Epistemic entrenchment: φ ≤ ψ: ψ at least as entrenched. More entrenched = harder to give up. Ordering determines contraction. φ ∈ K - ψ iff φ ∈ K and (ψ < φ ∨ ψ or ⊢ ψ).

Grove spheres: Possible worlds semantics. Concentric spheres around K-worlds. Revision: closest φ-worlds. Lewis-style.

Symbols.

Symbol	Unicode	Name	Meaning
K	—	Belief set	Deductively closed set of sentences
+	—	Expansion	K + φ = Cn(K ∪ {φ})
-	—	Contraction	K - φ: give up φ with minimal change
*	—	Revision	K * φ: accept φ, keep consistency
Cn	—	Consequence operator	Deductive closure
K_⊥	—	Absurd belief set	The inconsistent theory
≤	U+2264	Epistemic entrenchment	φ ≤ ψ: ψ at least as entrenched
⊆	U+2286	Inclusion	Between belief sets
∩	U+2229	Intersection	Partial meet and the Harper identity
∈	U+2208	Membership	Belonging to a belief set
⊢	U+22A2	Derivability	Classical consequence in the background logic

Metatheory. The central result is a representation theorem: a contraction function satisfies the six basic postulates iff it is a partial meet contraction — the intersection of a selection of maximal subsets of K that fail to imply φ — and it satisfies the two supplementary postulates as well iff that selection is generated by a transitive relation (Alchourrón, Gärdenfors and Makinson, 1985). Grove (1988) gave an equivalent systems-of-spheres semantics and Gärdenfors and Makinson (1988) an equivalent entrenchment ordering, so postulates, spheres and entrenchment determine one another. The Levi and Harper identities make revision and contraction interdefinable, so one representation covers both. Makinson and Gärdenfors (1991) showed that AGM revision corresponds exactly to the rational nonmonotonic consequence relations of the KLM hierarchy. Gärdenfors (1986) proved a triviality theorem: no non-trivial revision operator satisfying the AGM postulates validates the Ramsey test for conditionals. For finite propositional bases, deciding membership in the revised theory is Π₂ᵖ-complete (Eiter and Gottlob, 1992).

Applies to. Epistemology. AI. Database update. Theory change.

Limitations. AGM constrains one revision step on one agent's belief set and nothing else. The postulates say nothing about K * φ * ψ, so iterated revision is underdetermined; Darwiche and Pearl (1997) had to add postulates AGM does not entail, and the belief-set representation is too coarse to support them. Recovery — K ⊆ (K - φ) + φ — is the disputed postulate, since contracting and re-expanding need not restore everything, and withdrawal operators dropping it are coherent. Success, φ ∈ K * φ, obliges the agent to accept any consistent input whatever its source, so entrenchment governs what is surrendered but never whether the input is taken. Belief sets are deductively closed, so the agent is logically omniscient and revision operates on infinite objects; base revision trades this for syntax dependence. And by Gärdenfors' theorem the operator cannot be internalized as an object-language conditional.