The Irreducibility of Iterated to Single Revision

After a number of decades of research into the dynamics of rational belief, the belief revision theory community remains split on the appropriate handling of sequences of changes in view, the issue of so-called iterated revision. It has long been suggested that the matter is at least partly settled by facts pertaining to the results of various single revisions of one’s initial state of belief. Recent work has pushed this thesis further, offering various strong principles that ultimately result in a wholesale reduction of iterated to one-shot revision. The present paper offers grounds to hold that these principles should be significantly weakened and that the reductionist thesis should ultimately be rejected. Furthermore, the considerations provided suggest a close connection between the logic of iterated belief change and the logic of evidential relevance.

1. [Ψ] is also alternatively denoted in the literature by ‘Bel(Ψ)’ (in Darwiche & Pearl [5]) or again ‘\(\ulcorner \Psi \urcorner \)’ (in Rott [12]).

2. For a presentation of the theorem, see Katsuno and Mendelzon [8], as well as the related result in Grove [6].

3. See Appendix, Observation 1. The proof is trivial, but we include it since we are not aware of its having been provided elsewhere in the literature.

4. See Appendix, Observation 2. The Appendix also includes a statement of the DP and relevant AGM postulates.

5. These constraints take the form of two principles. The first offers a condition that is sufficient to place us in case (i) of DP ^′, telling us that A ∈ [(Ψ ∗ A) ∗ B] if either A ∈ [Ψ ∗ B] or ¬B ∉ [Ψ ∗ A]. The second offers a condition that is sufficient to place us in case (iii) of DP ^′, telling us that ¬A ∈ [(Ψ ∗ A) ∗ B] if both ¬A ∈ Cn(B) and \(\neg B\notin \text {Cn}(\varnothing )\). See Appendix, Observations 3 and 4. These are the strongest constraints on the relation between (d) and (e) that we know to be derivable from the AGM and DP postulates.

6. To put things a little more precisely, let us say that (i) Ψ and Ψ^′ are k -equivalent iff for any k-tuple 〈A ₁,…,A _k 〉, [(((Ψ∗A ₁)∗…)∗A _k ] = [(((Ψ^′ ∗ A ₁)∗…)∗A _k ] and that (ii) they are equivalent simpliciter iff there are k-equivalent for all k. RED3 is then the claim that, if two doxastic states are 1-equivalent (in other words: if they are such that their single-shot revision dispositions are representable by the same preference ordering), then they are 2-equivalent. What we are effectively noting is that this claim amounts to the following: if two doxastic states are 1-equivalent, then they are equivalent. We provide a quick proof of this in the Appendix–see Observation 5.

7. To the best of our knowledge, the present paper offers the first explicit formulation and critical discussion of these claims.

8. These are all clear strengthenings of the principles mentioned in footnote 5 above. It is easy to verify that they are equivalent, in the presence of the DP and AGM postulates, to the corresponding characteristic principles listed in Rott [11, pp. 278–280]. We provide a straightforward proof of this equivalence in the Appendix–see Observation 6.

9. Could one not, in response to this, insist that a restricted version of RED3 nevertheless holds for agents with more extensive conceptual resources? In principle, sure. But the resulting picture would strike us as being unappealingly disunified, with doxastic states being representable by preference orderings in some cases but only by richer structures in others.

10. Robert Stalnaker has also recently voiced suspicions regarding RED3. However, the grounds that he offers for doubting the principle are insufficiently strong. Finding fault with the first two Darwiche-Pearl postulates, he ipso facto rejects any reductionist proposal that satisfies them, including the three proposals that we consider here. But RED3 does not logically require either of of the postulates that he criticises and the aforementioned proposals do not exhaust the space of reductiivist options. See Stalnaker [13].

11. We should perhaps mention in passing another potential line of argument from the failure of RED2 to the failure of RED3: Recall that RED2 asserts that the belief sets resulting from revising a doxastic state by the different truth-functional combinations of A and B jointly determine the belief sets resulting from sequentially revising that state by A and then by B. But this strong ‘determination’ thesis entails an altogether far weaker ‘consistency’, or again ‘irrelevance’, principle, namely:

    1. (IR)

       If [Ψ ∗ C] = [Ψ^′ ∗ C], for any truth functional combination C of A and B,then there exists a Ψ^″, such that [Ψ^′ ∗ C] = [Ψ^″ ∗ C], for any C, and [(Ψ ∗ A) ∗ B] = [(Ψ^″ ∗ A) ∗ B]

    The entailment is obvious: let Ψ^″ = Ψ^′. IR, in effect, tells us that, holding fixed one’s single-shot revision dispositions with respect to sentences that are truth functional combinations of A and B, one’s single-shot revision dispositions with respect to sentences that are not truth functional combinations of A and B are irrelevant to the composition of the belief set resulting from a sequential revision of one’s doxastic state by A and then by B. It does not strike us as being a unreasonable requirement to impose. It is also one that is perfectly consistent with the examples that we consider. However, given the latter, it is easy to see that IR entails that RED3 must fail too. See Appendix, Observation 7.

We would like to thank the audience of the MCMP Colloquium in Logic, Philosophy of Science and Philosophy, at LMU Munich, and in particular Hannes Leitgeb and Hans Rott, for helpful feedback on an early presentation of this material. We are also thankful to an anonymous reviewer for this journal for his or her extensive and detailed feedback throughout the refereeing process. J. Chandler gratefully acknowledges support from the Alexander von Humboldt Foundation during the earlier stages of the research underpinning this article.

Authors and Affiliations

1. School of Computer Science and Informatics, Cardiff University, Cardiff, CF24 3AA, UK

   Richard Booth

2. Department of Politics and Philosophy, La Trobe University, Melbourne, VIC 3086, Australia

   Jake Chandler

Corresponding author

Correspondence to Jake Chandler.

Appendix:

In the proofs that follow, we shall be appealing to the following principles, which are not defined in the main body of the paper. They are to be read as holding for all doxastic states Ψ and all sentences A, B, C:

1. (AGM2)

   A ∈ [Ψ ∗ A]

2. (AGM3)

   If B ∈ [Ψ ∗ A], then B ∈ Cn ([Ψ]∪{A})

3. (AGM4)

   If ¬A ∉ [Ψ] and B ∈ Cn([Ψ] ∪ {A}), then B ∈ [Ψ ∗ A]

4. (AGM5)

   If A is consistent , then [Ψ ∗ A] is also consistent

5. (AGM7)

   [Ψ ∗ A ∧ B]⊆ Cn ([Ψ ∗ A] ∪ {B})

6. (AGM8)

   If ¬B ∉ [Ψ ∗ A], then Cn([Ψ ∗ A] ∪ {B}) ⊆ [Ψ ∗ A ∧ B]

7. (DP1)

   If C ∈ Cn (A), then B ∈ [Ψ ∗ A] iff B ∈ [(Ψ ∗ C) ∗ A]

8. (DP2)

   If ¬C ∈ Cn (A), then B ∈ [Ψ ∗ A] iff B ∈ [(Ψ ∗ C) ∗ A]

9. (DP3)

   If B ∈ [Ψ ∗ A], then B ∈ [(Ψ ∗ B) ∗ A]

10. (DP4)

    If¬B ∉ [Ψ ∗ A],then¬B ∉ [(Ψ ∗ B) ∗ A]

Observation 1

An agent’s single-shot revision dispositions with respect to any truth-functional combination C of sentences A and B are fully determined by the restriction of the preference relation to the members of the sets of maximal A ∧ B-, A ∧ ¬B-, ¬A ∧ B- and ¬A ∧ ¬B-worlds.

Proof

Let ≽ be a complete weak ordering of the set W of possible worlds and ≻ its strict part. Let [[ψ]] denote {w ∈ W:w⊧ψ} and, where S ⊆ W, max(S) denote {x ∈ S: For all y ∈ S, x≽y}. Since C is a truth-functional combination of A and B, the set [[C]] will be equal to the union of one or more of the cells of the partition \(\mathcal {P}=\{[{\kern -2.3pt}[ A\wedge B]{\kern -2.3pt}], [{\kern -2.3pt}[ A\wedge \neg B]{\kern -2.3pt}], [{\kern -2.3pt}[ \neg A\wedge B]{\kern -2.3pt}], [{\kern -2.3pt}[ \neg A\wedge \neg B]{\kern -2.3pt}]\}\) of W. We now show that x ∈ max([[C]]) iff \(x\in \max (\bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\})\), the nature of this last set being determined, as required, by the restriction of the preference relation to the members of the sets of maximal A ∧ B-, A ∧ ¬B-, ¬A ∧ B- and ¬A ∧ ¬B-worlds.

Regarding the left-to-right direction: Assume that x ∈ max([[C]]). Now assume for reductio that \(x\notin \max (\bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\})\). Now either (i) \(x\in \bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\}\) or (ii) \(x\notin \bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\}\). Assume (i). Then there exists a y in \(\max (\bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\})\), such that y ≻ x. Since \(\max (\bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\})\subseteq [{\kern -2.3pt}[ C ]{\kern -2.3pt}]\), we also have y ∈ [[C]], contradicting our initial assumption. So assume (ii). Since \(\mathcal {P}\) partitions [[C]], there exists an \(S\in \mathcal {P}\) such that x ∈ S. Given (ii), we know that x∉ max(S). So there exists a y ∈ max(S) such that y ≻ x. Since S ⊆ [[C]], we also have y ∈ [[C]], again contradicting our initial assumption.

Regarding the right-to-left direction: Assume that \(x\in \max (\bigcup \{\max (S):S\in \mathcal {P}\) and S ⊆ [[C]]}). Assume for reductio that x∉ max([[C]]) and hence that there exists a y ∈ [[C]] such that y ≻ x. Since \(\mathcal {P}\) partitions [[C]], there exists an \(S\in \mathcal {P}\) such that y ∈ S and a z ∈ max(S) such that z≽y. But since \(x\in \max (\bigcup \{\max (S):S\in \mathcal {P} \text { and } S\subseteq [{\kern -2.3pt}[ C]{\kern -2.3pt}]\})\), we have x≽z and hence, by transitivity of ≽, x≽y. Contradiction. □

Observation 2

In the presence of the AGM postulates, the DP postulates are jointly equivalent to DP ^′.

Proof

Regarding the left-to-right direction: We consider three cases:

• (1) Suppose A ∈ [(Ψ ∗ A) ∗ B]. Then, by AGM7 and AGM8, it follows that [(Ψ ∗ A) ∗ B] = [(Ψ ∗ A) ∗ A ∧ B]. But from DP1, we know that [(Ψ ∗ A) ∗ A ∧ B] = [Ψ ∗ A ∧ B]. Hence [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B], as required.

• (2) Suppose A, ¬A ∉ [(Ψ ∗ A) ∗ B]. By AGM8, this gives [(Ψ ∗ A) ∗ B]⊆[(Ψ ∗ A)∗¬A ∧ B]∩[(Ψ ∗ A) ∗ A ∧ B] while the converse inclusion to this also holds by AGM7. Hence [(Ψ ∗ A) ∗ B] = [(Ψ ∗ A)∗¬A ∧ B]∩[(Ψ ∗ A) ∗ A ∧ B]. Applying DP1 and DP2 to the right-hand side yields [(Ψ ∗ A) ∗ B] = [Ψ∗¬A ∧ B]∩[Ψ ∗ A ∧ B]. We now split into two cases: (i) ¬A ∈ [Ψ ∗ B] and (ii) ¬A ∉ [Ψ ∗ B]. Assume (i). It follows that [Ψ∗¬A ∧ B] = [Ψ ∗ B] and we recover the desired conclusion. Assume (ii). then we also have A ∉ [Ψ ∗ B] from DP3 and the fact that A ∉ [(Ψ ∗ A) ∗ B]. Hence, by AGM8 and AGM7, we have [Ψ ∗ B] = [Ψ∗¬A ∧ B]∩[Ψ ∗ A ∧ B]. Hence [(Ψ ∗ A) ∗ B] = [Ψ ∗ B]. But since [Ψ ∗ B]⊆[Ψ ∗ A ∧ B], we have [(Ψ ∗ A) ∗ B] = [Ψ ∗ B]∩[Ψ ∗ A ∧ B], as required.

• (3) Suppose ¬A ∈ [(Ψ ∗ A) ∗ B]. Then, by AGM7 and AGM8, [(Ψ ∗ A) ∗ B] = [(Ψ ∗ A)∗¬A ∧ B]. By DP2, we have [(Ψ ∗ A)∗¬A ∧ B] = [Ψ∗¬A ∧ B] and so [(Ψ ∗ A) ∗ B] = [Ψ∗¬A ∧ B]. From ¬A ∈ [(Ψ ∗ A) ∗ B] and DP4 we know that ¬A ∈ [Ψ ∗ B]. Hence, by AGM7 and AGM8, we have [Ψ ∗ B] = [Ψ∗¬A ∧ B] and so [(Ψ ∗ A) ∗ B] = [Ψ ∗ B], as required.

Regarding the right-to-left direction:

• (1) Regarding DP1: If A ∈ Cn(B), then we must be in Case (i) of DP ^′ and so [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B]. Since A ∧ B and B are logically equivalent, we know that [Ψ ∗ A ∧ B] = [Ψ ∗ B] and so [(Ψ ∗ A) ∗ B] = [Ψ ∗ B].

• (2) Regarding DP2: If ¬A ∈ Cn(B), then we must be in Case (iii) of DP ^′, which immediately gives us [(Ψ ∗ A) ∗ B] = [Ψ ∗ B].

• (3) Regarding DP3: We prove the contrapositive. Assume A ∉ [(Ψ ∗ A) ∗ B]. If ¬A ∈ [(Ψ ∗ A) ∗ B], then [(Ψ ∗ A) ∗ B] = [Ψ ∗ B] from Clause (iii) of DP ^′ and so A ∉ [Ψ ∗ B], as required. If ¬A ∉ [(Ψ ∗ A) ∗ B], then [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B]∩[Ψ ∗ B] by Clause (ii) of DP ^′. We know that A ∈ [Ψ ∗ A ∧ B], so if A ∉ [(Ψ ∗ A) ∗ B], then we must have A ∉ [Ψ ∗ B], again as required.

• (4) Regarding DP4: If ¬A ∈ [(Ψ ∗ A) ∗ B], then we must be in Case (iii) of DP ^′, so [(Ψ ∗ A) ∗ B] = [Ψ ∗ B] and hence ¬A ∈ [Ψ ∗ B].

□

Observation 3

AGM2, AGM4 and DP3 jointly entail that A ∈ [(Ψ ∗ A) ∗ B] if A ∈ [Ψ ∗ B] or ¬B ∉ [Ψ ∗ A].

Proof

Assume that ¬B ∉ [Ψ ∗ A]. By AGM2, A ∈ [Ψ ∗ A]. It then follows by AGM4 that A ∈ [(Ψ ∗ A) ∗ B]. Assume that A ∈ [Ψ ∗ B]. It then follows by DP3 that A ∈ [(Ψ ∗ A) ∗ B]. □

Observation 4

AGM2 entails that ¬A ∈ [(Ψ ∗ A) ∗ B] if ¬A ∈ Cn(B) and \(\neg B\notin \text {Cn}(\varnothing )\).

Proof

Trivial: Assume that ¬A ∈ Cn(B) and that \(\neg B\notin \text {Cn}(\varnothing )\). From the latter, by AGM2, we have B ∈ [(Ψ ∗ A) ∗ B]. By deductive closure of belief sets, and the fact that ¬A ∈ Cn(B), it then follows from this that ¬A ∈ [(Ψ ∗ A) ∗ B]. □

Observation 5

The following two statements are equivalent:

• (1) If two doxastic states are 1-equivalent, then they are 2-equivalent

• (2) If two doxastic states are 1-equivalent, then they are equivalent

Proof

Clearly (2) entails (1), from the definitions of equivalence and k-equivalence. It remains to show that (1) entails (2). So suppose that (a) holds and that Ψ and Ψ^′ are 1-equivalent. We will show by induction on k that Ψ and Ψ^′ are k-equivalent for all k. The base case, k = 1, holds by assumption. Regarding the inductive step, assume that Ψ and Ψ^′ are k-equivalent. We need to show that they are are (k+1)-equivalent, i.e. that for any (k+1)-tuple 〈A ₁, A ₂,…,A _k , A _k+1〉, [((((Ψ∗A ₁)∗A ₂)∗…)∗A _k )∗A _k+1] = [((((Ψ^′ ∗ A ₁)∗A ₂)∗…)∗A _k )∗A _k+1]. Since Ψ and Ψ^′ are k-equivalent, we know that [(((Ψ∗A ₁)∗A ₂)∗…)∗A _k−1] and [(((Ψ^′ ∗ A ₁)∗A ₂)∗…)∗A _k−1] are 1-equivalent. Hence, by (1), they are also 2-equivalent and so [((((Ψ∗A ₁)∗A ₂)∗…)∗A _k )∗A _k+1] = [((((Ψ^′ ∗ A ₁)∗A ₂)∗…)∗A _k )∗A _k+1], as required. □

Observation 6

In the presence of the AGM and DP postulates, NR, RR and LR are respectively equivalent to

Proof

Regarding the equivalence between NR and NR ^′:

• From NR to NR ^′: Assume ¬B ∉ [Ψ ∗ A]. It follows by NR that A ∈ [(Ψ ∗ A) ∗ B]. By DP ^′, we then recover [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B], as required. Assume ¬B ∈ [Ψ ∗ A]. Now either (i) ¬A ∉ [Ψ ∗ B], or (ii) ¬A ∈ [Ψ ∗ B]. Assume (i). Then, by NR, ¬A ∈ [(Ψ ∗ A) ∗ B] and hence, by DP ^′, [(Ψ ∗ A) ∗ B] = [Ψ ∗ B], as required. Assume (ii). On the one hand, it follows by AGM8 that Cn([Ψ ∗ B] ∪ {A}) ⊆ [Ψ ∗ A ∧ B] and hence that (iii) [Ψ ∗ B]⊆[Ψ ∗ A ∧ B]. On the other hand, it it follows by NR that A, ¬A ∉ [(Ψ ∗ A) ∗ B] and hence, by DP ^′, that (iv) [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B]∩[Ψ ∗ B]. By (iii) and (iv), we have [(Ψ ∗ A) ∗ B] = [Ψ ∗ B], as required.

• From NR ^′ to NR: Assume that A ∈ [Ψ ∗ B] or ¬B ∉ [Ψ ∗ A]. From the latter, by NR ^′, we recover [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B] and hence, by AGM2 and closure of belief sets, A ∈ [(Ψ ∗ A) ∗ B], as required. Assume that ¬B ∈ [Ψ ∗ A]. From this, by NR ^′, we recover [(Ψ ∗ A) ∗ B] = [Ψ ∗ B]. Assume further that A, ¬A ∉ [Ψ ∗ B]. It follows that A, ¬A ∉ [(Ψ ∗ A) ∗ B], as required. Finally, alternatively, assume that ¬A ∉ [Ψ ∗ B]. It follows that ¬A ∈ [(Ψ ∗ A) ∗ B], again as required.

Regarding the equivalence between RR and RR ^′:

• From RR to RR ^′: Assume that either ¬A ∉ [Ψ ∗ B] or ¬B ∉ [Ψ ∗ A]. By RR, we have A ∈ [(Ψ ∗ A) ∗ B] and hence, by DP ^′, [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B], as required. Assume instead that ¬A ∈ [Ψ ∗ B] and ¬B ∈ [Ψ ∗ A]. By RR, we have ¬A ∈ [(Ψ ∗ A) ∗ B] and hence, by DP ^′, [(Ψ ∗ A) ∗ B] = [Ψ ∗ B], as required.

• From RR ^′ to RR: Assume that either ¬A ∉ [Ψ ∗ B] or ¬B ∉ [Ψ ∗ A]. By RR ^′ it follows that [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B] and hence, by AGM2 and closure of belief sets, that A ∈ [(Ψ ∗ A) ∗ B], as required. So assume instead that ¬A ∈ [Ψ ∗ B] and ¬B ∈ [Ψ ∗ A]. It follows by RR ^′ that [(Ψ ∗ A) ∗ B] = [Ψ ∗ B] and hence, since ¬A ∈ [Ψ ∗ B], that ¬A ∈ [(Ψ ∗ A) ∗ B], as required.

Regarding the equivalence between LR and LR ^′:

• From LR to LR ^′: Assume that [Ψ ∗ A ∧ B] is consistent. By AGM2, it follows that ¬B∉Cn(A) and hence, by LR, that A ∈ [(Ψ ∗ A) ∗ B]. By DP ^′, we then recover the required result that [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B]. Assume instead that [Ψ ∗ A ∧ B] is inconsistent. By AGM5, it follows that ¬B ∈ Cn(A). By LR, we therefore have ¬A ∈ [(Ψ ∗ A) ∗ B] and hence, by DP ^′, [(Ψ ∗ A) ∗ B] = [Ψ ∗ B], as required.

• From LR ^′ to LR: Assume that ¬B∉Cn(A). It follows, by AGM5, that [Ψ ∗ A ∧ B] is consistent. and hence, by LR ^′, that [(Ψ ∗ A) ∗ B] = [Ψ ∗ A ∧ B]. By AGM2 and closure of belief sets, we then recover A ∈ [(Ψ ∗ A) ∗ B], as required. Assume instead that ¬B ∈ Cn(A). Since, by AGM2, we have B ∈ [(Ψ ∗ A) ∗ B], it then follows by closure of belief sets that ¬A ∈ [(Ψ ∗ A) ∗ B], as required.

□

Observation 7

RED3, IR and the negation of RED2 are jointly inconsistent.

Proof

Assume the negation of RED2, i.e. that there exist sentences A and B and doxastic states Ψ and Ψ^′, such that [Ψ ∗ C] = [Ψ^′ ∗ C], for any truth-functional combination C of A and B, but [(Ψ ∗ A) ∗ B]≠[(Ψ^′ ∗ A) ∗ B]. By IR, there then exists a Ψ^″ such that [Ψ^″ ∗ C] = [Ψ^′ ∗ C], for any C, and [(Ψ^″ ∗ A) ∗ B] = [(Ψ ∗ A) ∗ B]. Since, by assumption, [(Ψ ∗ A) ∗ B]≠[(Ψ^′ ∗ A) ∗ B], we therefore have [(Ψ^″ ∗ A) ∗ B]≠[(Ψ^′ ∗ A) ∗ B]. But this contradicts RED3, which would require, since [Ψ^″ ∗ C] = [Ψ^′ ∗ C], for any C, that [(Ψ^″ ∗ A) ∗ B] = [(Ψ^′ ∗ A) ∗ B]. □

Reprints and permissions