Contribution
Earlier work gave two things that did not meet. Gärdenfors had postulates “of a more or less equational nature” for contraction and revision, and Alchourrón and Makinson had a construction, maxichoice contraction, which keeps one maximal subset of A that fails to imply x. Maxichoice is too large: its revision makes A + x complete, since it “will be complete whenever x is a proposition inconsistent with A” (p. 511). Full meet contraction, the intersection of all such subsets, is too small: its revision of A by an x inconsistent with A is just Cn(x), “a set which is far too small in general to represent the result of an intuitive process of revision” (p. 512). This paper takes the family in between, partial meet contraction, and shows it is exactly what Gärdenfors’s postulates describe, and that a subclass defined by a transitive relation is exactly what the postulates plus two supplementary ones describe.
Key insight
A contraction cannot be read off the theory alone. To give up x from A one has to choose among the maximal subsets of A that do not imply x, and the theory does not say which to prefer. The paper puts that choice into a selection function γ, which picks the “most important” remainders (p. 512, deferring to Gärdenfors 1984 for what importance is), and keeps what they share. Gärdenfors’s postulates turn out to say no more and no less than that some such γ exists; his two supplementary postulates say no more and no less than that γ picks the best remainders under one fixed transitive relation.
Assumptions
- Theories are logically closed. “By a theory, we mean, as is customary, a set A of propositions that is closed under Cn” (p. 511). The paper’s word is “theory”; it does not use “belief set”. Cn includes classical tautological implication, is compact, and satisfies disjunction in the premises.
- Definitions over arbitrary sets, theorems over theories. A ⊥ x, selection functions and partial meet contraction are defined for “any set of propositions” A (§2), and the abstract notes maximal subsets may be taken “of the theory (or alternatively, of one of its axiomatic bases)”. But recovery (Lemma 2.1), both representation theorems (Observation 2.5, Corollary 4.5) and all of §§3–6 are stated for theories.
- One theory, one change. A selection function is “a selection function for A”, for a fixed A. Nothing determines the selection function of the theory that results, so iterated change is outside the paper.
- The input is a proposition. Contraction removes a proposition x; revision adds one. There is no representation of evidence, sources or what a belief rests on.
- The relation in §4 is fixed for all x: “otherwise all partial meet contraction functions would be trivially relational” (p. 518).
Key results
Notation: A a theory, A ⊥ x the set of maximal subsets B ⊆ A with B ⊬ x, γ a selection function (γ(A ⊥ x) a nonempty subset of A ⊥ x when that is nonempty, and {A} when it is empty), A ∸ x = ⋂γ(A ⊥ x), A ∼ x full meet contraction ⋂(A ⊥ x).
Postulates for contraction (p. 513, attributed to Gärdenfors):
- (∸1) A ∸ x is a theory whenever A is a theory (closure).
- (∸2) A ∸ x ⊆ A (inclusion).
- (∸3) If x ∉ Cn(A), then A ∸ x = A (vacuity).
- (∸4) If x ∉ Cn(∅), then x ∉ Cn(A ∸ x) (success).
- (∸5) If Cn(x) = Cn(y), then A ∸ x = A ∸ y (preservation).
- (∸6) A ⊆ Cn((A ∸ x) ∪ {x}) whenever A is a theory (recovery).
Postulates for revision (p. 513):
- (+1) A + x is always a theory.
- (+2) x ∈ A + x.
- (+3) If ¬x ∉ Cn(A), then A + x = Cn(A ∪ {x}).
- (+4) If ¬x ∉ Cn(∅), then A + x is consistent under Cn.
- (+5) If Cn(x) = Cn(y), then A + x = A + y.
- (+6) (A + x) ∩ A = A ∸ ¬x, whenever A is a theory.
Supplementary postulates (p. 515):
- (+7) A + (x & y) ⊆ Cn((A + x) ∪ {y}) for any theory A.
- (+8) Cn((A + x) ∪ {y}) ⊆ A + (x & y) for any theory A, provided that ¬y ∉ A + x.
- (∸7) (A ∸ x) ∩ (A ∸ y) ⊆ A ∸ (x & y) for any theory A.
- (∸8) A ∸ (x & y) ⊆ A ∸ x whenever x ∉ A ∸ (x & y), for any theory A.
The Levi identity. Revision “can be reduced to that of contraction via the so-called Levi identity” (p. 511): A + x = Cn((A ∸ ¬x) ∪ {x}). Partial meet revision is defined this way (p. 512). The paper does not prove that the revision postulates follow from the contraction postulates; it cites Gärdenfors: “It is easy to show (cf. [3] and [4]) that the postulates for revision can all be derived from those for contraction via the Levi identity” (p. 513). The name “Harper identity” does not appear, though (+6) has that form.
Theorems (the paper numbers them as Lemmas, Observations and Corollaries):
- Lemma 2.1. For any theory A, A ⊆ Cn((A ∼ x) ∪ {x}): “even the very weak operation of (full) meet contraction satisfies recovery.” The proof is that for every a ∈ A, ¬x ∨ a ∈ A ∩ Cn(¬x) survives contraction. Corollary 2.2: any contraction bounded below by full meet contraction satisfies recovery over a theory.
- Observation 2.3. Every partial meet contraction satisfies (∸1)–(∸6), and its partial meet revision satisfies (+1)–(+6).
- Observation 2.5 (representation theorem). For every theory A, ∸ is a partial meet contraction over A iff ∸ satisfies (∸1)–(∸6) over A. The postulates “fully characterize the class of partial meet contraction functions” (p. 513). The γ built in the proof is γ(A ⊥ x) = {B ∈ A ⊥ x : A ∸ x ⊆ B}.
- Observation 2.7. If ∸ satisfies closure, vacuity and recovery over a theory A, it is bounded below by full meet contraction.
- Observations 3.1 and 3.2. For partial meet contraction over a theory, (∸7) iff (+7), and (∸8) iff (+8). Observation 3.3: (∸7) iff partial antitony, (A ∸ x) ∩ Cn(x) ⊆ A ∸ (x & y). Observation 3.4: (∸8) implies the covering condition, A ∸ (x & y) ⊆ A ∸ x or ⊆ A ∸ y; the converse fails.
- Observations 4.2–4.4. γ relational implies (γ7); transitively relational implies (γ8); (γ7) and (γ8) give (∸7) and (∸8); and if ∸ satisfies (∸7) and (∸8), the completion γ* of γ is transitively relational.
- Corollary 4.5 (second representation theorem). A partial meet contraction over a theory A is transitively relational iff it satisfies (∸7) and (∸8). “This result is the promised representation theorem for the collection of “basic” plus “supplementary” postulates” (p. 520), and the authors conclude “there is strong reason to focus on transitively relational partial meet contraction functions as an ideal representation of the intuitive process of contraction.”
- Observation 4.6. If A is finite modulo Cn, distinct selection functions give distinct contractions: if γ(A ⊥ x) ≠ γ′(A ⊥ x) then ⋂γ(A ⊥ x) ≠ ⋂γ′(A ⊥ x). Corollary 4.7: in the finite case, (∸7) and (∸8) make γ itself transitively relational. In the infinite case one contraction can come from two selection functions.
- Observations 4.8–4.10. Relationality alone has no known characterization by a condition on ∸. (γ7) does not imply relationality even in the finite case (Observation 4.9, an eight-element counterexample). γ is relational iff an infinitary condition (γ7:∞) holds (4.10); the “Added in proof” sharpens this to (γ7:2), and leaves open whether (γ7:2) can be expressed as a condition on the contraction.
- Observations 5.1–5.3. Adding connectivity to the relation changes nothing for transitive relationality, and in the finite case nothing for relationality: “Perhaps surprisingly, it turns out that in the infinite case it adds” very little (p. 522).
- Observations 6.1–6.2. A partial meet contraction is maxichoice iff it satisfies fullness (∸F), iff it satisfies primeness (∸Q).
- Observation 6.3. Decomposition (A ∸ (x & y) is A ∸ x or A ∸ y) iff maxichoice plus (∸7) or (∸8), iff weak decomposition, iff maxichoice plus covering.
- Observation 6.4. Intersection (A ∸ (x & y) = A ∸ x ∩ A ∸ y for x, y ∈ A) iff monotony iff full meet contraction.
- Observation 6.5. Ventilation (A ∸ (x & y) is A ∸ x, A ∸ y, or their intersection) iff (∸7) and (∸8).
- §7. A diagram of all the implications, with four finite counterexamples separating the conditions.
Bearing on the record
Belief sets and the belief-base point. The paper’s theories are logically closed sets, as the record’s entry says. The paper does not discuss why beliefs are held, justification, provenance, or the information lost by closing a set under consequence. It does not make the belief-base argument: it nowhere says that two bases with the same closure should contract differently. Its only gestures toward bases are the abstract’s parenthesis, “maximal subset of the theory (or alternatively, of one of its axiomatic bases)”, which refers to Alchourrón and Makinson 1982, and the definition of partial meet contraction over “any set of propositions” in §2. Every theorem is for theories. So the record’s sentence that AGM’s belief sets “keep no record of why a belief is held” is a fair description of the formal object, but it is the record’s and Hansson’s point (LIT-1072), not this paper’s, and should be cited to them.
On CLAIM-294: the paper agrees that current conclusions are not a sufficient state for revision, and supplies a different missing ingredient from the one the claim names.
- In AGM the theory A does not fix the contraction or the revision. A selection function γ, or under Corollary 4.5 a transitive relation over the remainders A ⊥ x, must be added. Maxichoice, full meet and every partial meet contraction between them are contractions of the same A that disagree. Two agents holding the same closed theory but different γ revise differently on the same input. That is the structural point of CLAIM-294 in a logical rather than probabilistic setting, and it is built into the framework, not argued against it.
- The extra state is not provenance or dependency. It is a preference over which maximal consistent remainders to keep, “most important” in the paper’s words, with importance left to Gärdenfors 1984. Nothing in it records what a belief rested on, and the input to revision is a sentence, not evidence about a premise. So the paper does not support the claim’s specific reading that what is missing is information “about what it depended on”. It shows that something beyond conclusions is needed, and that an ordering suffices for the postulates.
- Recovery (∸6) and Lemma 2.1 show a closed theory carries some of this structure implicitly: after giving up x, every ¬x ∨ a survives, so adding x back restores all of A. A belief set is not memoryless with respect to the proposition just removed. It is the belief-base literature, not this paper, that argues recovery is wrong and that this implicit memory is the wrong kind.
On QUESTION-105: the paper answers a one-step version of the question, and is silent on the question as posed.
- For a single contraction or revision of a fixed theory satisfying the eight postulates, what must be kept is A together with a transitive relation over its remainders (Corollary 4.5). In the finite case nothing in γ is redundant: distinct selection functions always yield distinct contractions (Observation 4.6). That is a minimality result of the kind the question asks for, for the decision family “one AGM contraction or revision by any proposition”.
- The question asks about a family of future revisions of an evolving inquiry. The paper’s γ is for one A. After a revision the new theory needs a new selection function, and the paper gives no rule for it. So it says nothing about what must be retained to support a sequence of revisions, which is where the question’s “provenance, dependencies and defeated alternatives” would matter. The iterated belief revision literature (not in the record) is where that is taken up.
- The optimal retained state in AGM is an ordering of remainders, which resembles none of the question’s three candidates. Defeated alternatives come nearest: the remainders not selected are, in a sense, alternatives kept in reserve, but they are recomputed from A, not retained.
Limitations
- Closed theories only, for every theorem; nothing on finite bases or on what is lost by closing.
- One-step change; no iterated revision, no rule for updating the selection function.
- The selection function is unexplained; “importance” is deferred to another paper.
- Recovery is assumed as a postulate and not defended here.
- Relational (as against transitively relational) partial meet contraction has no representation theorem on the contraction side; the paper leaves it open.
- No probabilities, no evidence, no sources; revision inputs are sentences accepted outright (success).