Elementary Belief Revision Operators

Discussions of the issue of iterated belief revision are commonly accompanied by the presentation of three “concrete” operators: natural, restrained and lexicographic. This raises a natural question: What is so distinctive about these three particular methods? Indeed, the common axiomatic ground for work on iterated revision, the AGM and Darwiche-Pearl postulates, leaves open a whole range of alternative proposals. In this paper, we show that it is satisfaction of an additional principle of “Independence of Irrelevant Alternatives”, inspired by the literature on Social Choice, that unites and sets apart our three “elementary” revision operators. A parallel treatment of iterated belief contraction is also given, yielding a family of elementary contraction operators that includes, besides the well-known “conservative” and “moderate” operators, a new contraction operator that is related to restrained revision.

1. This principle is given as follows:

   • \((\mathrm {P}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) If ρ_A(x,y) = 1 and ρ_Ψ(x,y) ≥ 0, then ρ_Ψ∗A(x,y) = 1

   It was noted, in [3], that, in its unqualified form (there called “\((\mathrm {P}^{\scriptscriptstyle \div }_{\scriptscriptstyle \preccurlyeq })\)”), without the requirement that \(y\notin \min \limits (\preccurlyeq _{\Psi }, W)\), this principle would lead to trouble.

Open Access funding enabled and organized by CAUL and its Member Institutions.

Authors and Affiliations

1. La Trobe University, Melbourne, Australia

   Jake Chandler

2. Cardiff University, Cardiff, UK

   Richard Booth

Corresponding author

Correspondence to Jake Chandler.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This research was partially supported by the Australian Government through an ARC Future Fellowship (project number FT160100092) awarded to Jake Chandler.

Appendix A: Proofs

Proposition 1

Given \((KM^{\div }_{\preccurlyeq })\), \((\text {IIA}^{\ast }_{\preccurlyeq })\) does not imply any of \((\mathrm {C}{1},{2}^{\ast }_{\preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\preccurlyeq })\)

Proof

Let ∗ be defined in such a way that, for all states Ψ, x,y ∈ W and A ∈ L:

• \(\min \limits (\preccurlyeq _{\Psi \ast A}, W) = \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\)

• If \(x, y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), then

  • If ρ_Ψ(x,y) = 1, then ρ_Ψ∗A(x,y) = − 1

  • If ρ_Ψ(x,y) = 0, then ρ_Ψ∗A(x,y) = 0

Essentially, this operator will set the \(\preccurlyeq _{\Psi }\)-minimal A-worlds as \(\preccurlyeq _{\Psi \ast A}\)-minimal (thus satisfying AGM) and simply “flip” the remainder of the ordering.

It is easy to see that ∗ satisfies \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\): Assume that \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), that ρ_Ψ(x,y) = ρ_Θ(x,y) and that ρ_A(x,y) = ρ_B(x,y). We need to show that ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y). For this, we consider two cases:

• (a) Assume ρ_Ψ(x,y) = ρ_Θ(x,y) = 1. Then ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y) = − 1.

• (b) Assume ρ_Ψ(x,y) = ρ_Θ(x,y) = 0. Then ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y) = 0.

In either case, ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y), as required.

Clearly, however, each of \((\mathrm {C}{1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) to \((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) will be violated. A counterexample is provided in Fig. 5. There, \((\mathrm {C}{1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) fails because, for instance, y ≺_Ψx but x ≺_Ψ∗Ay. Regarding \((\mathrm {C}{2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), we have t ≺_Ψs but s ≺_Ψ∗At. Regarding \((\mathrm {C}{3}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), we have z ≺_Ψs but s ≺_Ψ∗Az. □

Model demonstrating the fact that the conjunction of \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) does not imply any of \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) to \((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)

Full size image

Proposition 2

Given \((KM^{\ast }_{\preccurlyeq })\), \((\mathrm {C}{1},{2}^{\ast }_{\preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\preccurlyeq })\) do not jointly imply \((\text {IIA}^{\ast }_{\preccurlyeq })\)

Proof

Consider the operator ∗ defined as follows: for all states Ψ and A ∈ L, Ψ ∗ A = Ψ ∗_LA if \(\preccurlyeq _{\Psi }\) is a chain (i.e. an antisymmetric TPO, such that, for all x,y ∈ W, if \(x\sim _{\Psi }y\), then x≠y), and Ψ ∗ A = Ψ ∗_RA otherwise.

It is easily verified that ∗ satisfies \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). But ∗ does not satisfy \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), as can be seen from the following countermodel: Let W = {x,y,z,w}, [ [A] ] = {z,x}, z ≺_Ψw ≺_Ψx ≺_Ψy and {z,w}≺_Θx ≺_Θy, so that, notably, Ψ ∗ A = Ψ ∗_LA but Θ ∗ A = Θ ∗_RA. Then \(w, x \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\), ρ_Ψ(w,x) = ρ_Θ(w,x) = 1, but ρ_Ψ∗A(w,x) = − 1 and ρ_Θ∗A(w,x) = 1. □

Proposition 3

Given \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\), \((\text {IIA}^{\ast }_{\preccurlyeq })\) is equivalent to the conjunction of the following principles of “Independence of Irrelevant Alternatives” with respect to the “Prior” and the “Input”, respectively:

• \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) If \(x,y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\) then, if ρ_Ψ(x,y) = ρ_Θ(x,y) then ρ_Ψ∗A(x,y) = ρ_Θ∗A(x,y)

• \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) If \(x,y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{\Psi }, [\![{B}]\!])\) then, if ρ_A(x,y) = ρ_B(x,y) then ρ_Ψ∗A(x,y) = ρ_Ψ∗B(x,y)

Proof

From \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) to \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\): simply set Ψ = Θ in the former case and A = B in the latter.

From \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) to \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\): Suppose \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), ρ_Ψ(x,y) = ρ_Θ(x,y) and ρ_A(x,y) = ρ_B(x,y). We need to show ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y). Consider a state Φ such that, for all z∉{x,y},z ≺_Φx,z ≺_Φy and ρ_Φ(x,y) = ρ_Ψ(x,y) = ρ_Θ(x,y). Such a state exists by \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\). Since \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), by the construction of \(\preccurlyeq _{\Phi }\), we must have \(x, y \notin \min \limits (\preccurlyeq _{\Phi }, [\![{A}]\!])\). Hence, by \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we have (1) ρ_Ψ∗A(x,y) = ρ_Ψ∗A(x,y). Similarly, since \(x, y \notin \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), we have \(x, y \notin \min \limits (\preccurlyeq _{\Phi }, [\![{B}]\!])\) and so, by \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we have: (2) ρ_Θ∗B(x,y) = ρ_Θ∗B(x,y). Finally, from the fact that \(x, y \notin \min \limits (\preccurlyeq _{\Phi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{\Phi }, [\![{B}]\!])\) and ρ_A(x,y) = ρ_B(x,y), by \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we have: (3) ρ_Φ∗A(x,y) = ρ_Φ∗B(x,y). The required result then follows from (1), (2) and (3). □

Proposition 4

\((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) does not imply \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) or vice versa, even in the presence of \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\).

Proof

For an operator satisfying \((\text {KM}^{\ast }_{\preccurlyeq })\), \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), and \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) but not \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we can consider the operator ∗ introduced in the proof of Proposition 2 above. It was defined as follows: for all states Ψ and A ∈ L, Ψ ∗ A = Ψ ∗_LA if \(\preccurlyeq _{\Psi }\) is a chain (i.e. an antisymmetric TPO, such that, for all x,y ∈ W, if \(x\sim _{\Psi }y\), then x≠y), and Ψ ∗ A = Ψ ∗_RA otherwise.

We’ve already noted above that it satisfies \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is also satisfied, since, for any given state, the same method (i.e. ∗_L or ∗_R) is used for all sentences and this method satisfies \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\). But ∗ does not satisfy \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), as can be seen from the countermodel given in the proof of Proposition 2 above. For convenience, we repeat it here. Let W = {x,y,z,w}, [ [A] ] = {z,x}, z ≺_Ψw ≺_Ψx ≺_Ψy and {z,w}≺_Θx ≺_Θy, so that, notably, Ψ ∗ A = Ψ ∗_LA but Θ ∗ A = Θ ∗_RA. Then \(w, x \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\), ρ_Ψ(w,x) = ρ_Θ(w,x) = 1, ρ_A(w,x) − 1, but ρ_Ψ∗A(w,x) = − 1 and ρ_Θ∗A(w,x) = 1.

For an operator that satisfies \((\text {KM}^{\ast }_{\preccurlyeq })\), \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), and \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) but not \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), consider the operator ∗ defined as follows: For all states Ψ and A ∈ L, Ψ ∗ A = Ψ ∗_LA if \(\lvert [\![{\neg A}]\!]\rvert =1\), and Ψ ∗ A = Ψ ∗_RA otherwise.

Again, as for the previous operator, it is easily verified that ∗ satisfies \((\text {KM}^{\ast }_{\preccurlyeq })\), and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is also satisfied, since, , for any given sentence, the same method (i.e. ∗_L or ∗_R) is used for all states and this method satisfies \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\). But ∗ does not satisfy \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), as can be seen from the following countermodel: Let W = {x,y,z,w}, [ [A] ] = {x,z,w}, [ [B] ] = {x,w} and w ≺_Ψy ≺_Ψx ≺_Ψz. Then \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{\Psi }, [\![{B}]\!])\) and ρ_A(x,y) = 1 = ρ_B(x,y), but ρ_Ψ∗A(x,y) = 1, whereas ρ_Ψ∗B(x,y) = − 1. □

Proposition 5

Given (KM\(^{\div }_{\preccurlyeq })\), \((\text {IIAP}^{\ast }_{\preccurlyeq })\) entails \((\text {TPOR}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\)

Proof

Assume that \(\preccurlyeq _{\Psi }=\preccurlyeq _{{\varTheta }}\). Consider arbitrary x,y ∈ W. If either x or y is in \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\), then \(\rho _{\preccurlyeq _{\Psi \ast A}}({x},{y})= \rho _{\preccurlyeq _{{\varTheta }\ast A}}({x},{y})\) by virtue of \((\text {KM}^{\ast }_{\preccurlyeq })\). If \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\), then \(\rho _{\preccurlyeq _{\Psi \ast A}}({x},{y})= \rho _{\preccurlyeq _{{\varTheta }\ast A}}({x},{y})\) by virtue of \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\). Hence \(\preccurlyeq _{\Psi \ast A}=\preccurlyeq _{{\varTheta }\ast A}\), as required. □

Proposition 6

Given \((KM^{\ast }_{\preccurlyeq })\), \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), \((\text {IIAI}^{\ast }_{\preccurlyeq })\) is equivalent to the conjunction of:

• (\(\beta 1^{\ast }_{\scriptscriptstyle \preccurlyeq }\)) If \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![C]\!]), \rho _{A}(x,y)= 1\) and ρ_Ψ∗A(x,y) ≤ 0, then ρ_Ψ∗C(x,y) ≤ 0

• (\(\beta 2^{\ast }_{\scriptscriptstyle \preccurlyeq }\)) If \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![C]\!]), \rho _{A}(x,y)= 1\) and ρ_Ψ∗A(x,y) = − 1, then ρ_Ψ∗C(x,y) = − 1

Proof

The proof of this claim closely resembles the proof of Proposition 3 of [8]. For ease of comparison, we use the \(\preccurlyeq \)-notation, rather than the ρ-notation, so that \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) are presented as follows:

• \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) If \(x \not \in \min \limits (\preccurlyeq _{\Psi }, [\![C]\!])\), x ≺_Ay, and \(y \preccurlyeq _{\Psi \ast A} x\), then \(y \preccurlyeq _{\Psi \ast C} x\)

• \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) If \(x \not \in \min \limits (\preccurlyeq _{\Psi }, [\![C]\!])\), x ≺_Ay, and y ≺_Ψ∗Ax, then y ≺_Ψ∗Cx

□

We first establish the following lemma:

Lemma 4

Given \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)–\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\),

• (a) If x ≺_Ay and ρ_A(x,y)≠ρ_C(x,y), then, if \(y \preccurlyeq _{\Psi \ast A} x\), then \(y \preccurlyeq _{\Psi \ast C} x\).

• (b) If x ≺_Ay and ρ_A(x,y)≠ρ_C(x,y), then, if y ≺_Ψ∗Ax, then y ≺_Ψ∗Cx.

We simply derive (a), since the proof of (b) is analogous. Assume that x ≺_Ay and ρ_A(x,y)≠ρ_C(x,y). In other words: x ∈ [ [A] ],y ∈ [ [¬A] ], and either (i) x ∈ [ [C] ],y ∈ [ [C] ], (ii) x ∈ [ [¬C] ],y ∈ [ [¬C] ] or (iii) x ∈ [ [¬C] ],y ∈ [ [C] ]. Assume that \(y \preccurlyeq _{\Psi \ast A} x\). From this and x ∈ [ [A] ],y ∈ [ [¬A] ], it follows, by \((\mathrm {C}{3}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), that \(y \preccurlyeq _{\Psi } x\). From this, if either (i), (ii) or (iii) hold, then, by \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), \((\mathrm {C}{2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), and \((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), respectively, we have \(y \preccurlyeq _{\Psi \ast C} x\), as required. This completes the proof of Lemma 4.

With this in hand, we can derive each direction of the equivalence:

• (a) From \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) to \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\): Regarding \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), assume \(x \not \in \min \limits (\preccurlyeq _{\Psi }, [\![{C}]\!])\), x ≺_Ay, and \(y \preccurlyeq _{\Psi \ast A} x\). We need to show that \(y \preccurlyeq _{\Psi \ast C} x\). If ρ_A(x,y)≠ρ_C(x,y), then the required result follows by principle (a) of Lemma 4. So assume ρ_A(x,y) = ρ_C(x,y), and hence that x ≺_Cy. We now establish that \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{\Psi }, [\![{C}]\!])\). We already have \(x \not \in \min \limits (\preccurlyeq _{\Psi }, [\![{C}]\!])\). Since, by x ≺_Cy, it follows that y ∈ [ [¬C] ], we therefore have \(y \not \in \min \limits (\preccurlyeq _{\Psi }, [\![{C}]\!])\). Furthermore, by x ≺_Ay, it follows that y ∈ [ [¬A] ] and so \(y \not \in \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\). Finally, assume for contradiction that \(x\in \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\). Then \(x\in \min \limits (\preccurlyeq _{\Psi \ast A}, W)\), by \((\text {KM}^{\ast }_{\preccurlyeq })\). Since y ∈ [ [¬A] ], by \((\text {KM}^{\ast }_{\preccurlyeq })\), \(y\notin \min \limits (\preccurlyeq _{\Psi \ast A}, W)\). Hence x ≺_Ψ∗Ay, contradicting \(y \preccurlyeq _{\Psi \ast A} x\). So we can infer that \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\). With this in hand, we can apply \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) to derive \(y \preccurlyeq _{\Psi \ast C} x\), as required. The derivation of \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) is analogous, but using principle (b) of Lemma 4.

• (b) From \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) to \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\): Assume that \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{\Psi }, [\![{C}]\!])\) and that ρ_A(x,y) = ρ_C(x,y). We want to show that \(x\preccurlyeq _{\Psi \ast A} y\) iff \(x\preccurlyeq _{\Psi \ast C} y\). By symmetry, it suffices for this to show that \(x\preccurlyeq _{\Psi \ast A} y\) implies \(x\preccurlyeq _{\Psi \ast C} y\). So assume \(x\preccurlyeq _{\Psi \ast A} y\). Since ρ_A(x,y) = ρ_C(x,y), we have three cases to consider:

  • (i) \(\rho _{A}({x},{y}){\kern -.5pt}={\kern -.5pt}\rho _{C}({x},{y}){\kern -.5pt}={\kern -.5pt}1\): Assume for contradiction that y ≺_Ψ∗Cx. From this, \(x \not \in \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) and x ≺_Cy, it follows by \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) that y ≺_Ψ∗Ax, contradicting \(x\preccurlyeq _{\Psi \ast A} y\). Hence \(x\preccurlyeq _{\Psi \ast C} y\), as required.

  • (ii) ρ_A(x,y) = ρ_C(x,y) = 0: It follows from this, via \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), that \(x\preccurlyeq _{\Psi \ast A} y\) iff \(x\preccurlyeq _{\Psi } y\) iff \(x\preccurlyeq _{\Psi \ast C} y\). Hence \(x\preccurlyeq _{\Psi \ast C} y\), as required.

  • (iii) ρ_A(x,y) = ρ_C(x,y) = − 1: By \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), it follows, from \(x \not \in \min \limits \) \((\preccurlyeq _{\Psi }, [\![{A}]\!])\), y ≺_Ax, and \(x\preccurlyeq _{\Psi \ast A} y\), that \(x\preccurlyeq _{\Psi \ast C} y\), as required.

Lemma 2

The conjunction of \((\text {KM}^{\ast }_{\preccurlyeq })\) transitivity of \({\preccurlyeq }_{\Psi \ast A}, (\text {PI}^{\ast }_{\preccurlyeq })\) and \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) implies the following principle of “Zero Symmetry”:

• \((\text {ZS}^{\ast }_{\preccurlyeq })\) If \(x,y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!]), \rho _{\Psi }(x,y)= -\rho _{{\varTheta }}(x,y)\) and ρ_A(x,y) = −ρ_B(x,y) then, ρ_Ψ∗A(x,y) = −ρ_Ψ∗B(x,y)

Proof

\((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) jointly tell us that that, for a pair of worlds {x,y}, the posterior relative rank ρ_Ψ∗A(x,y) is determined by the prior relative rank ρ_Ψ(x,y) and input sentence relative rank ρ_A(x,y) (although this mapping may be different for different pairs of worlds). With the case in which x or \(y\in \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) being taken care of by \((\text {KM}^{\ast }_{\preccurlyeq })\), the behaviour of ∗ with respect to {x,y} can therefore be represented in the form of a matrix giving us, for \(x, y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), the values of ρ_Ψ∗A(x,y) as a function of those of ρ_Ψ(x,y) and ρ_A(x,y).

Since we assume A to be consistent and hence that \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) is non-empty, we must have strictly more than two, and therefore (since \(\lvert W\rvert =2^{n}\)) at least four, worlds. Let these worlds be x, y, z and w. We will consider the matrices for the pairs 〈x,y〉, 〈y,z〉 and 〈z,x〉 in Table 7.

\((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) tells us that the value of the central cell in each matrix is 0. To establish \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we then just need to show that a_i = −b_i, for 1 ≤ i ≤ 4. We shall simply show that a₁ = −b₁, since the proof strategy is identical for other values of i.

Let Ψ be such that ρ_Ψ(x,z) = ρ_Ψ(x,y) = ρ_Ψ(y,z) = 0. Let A be such that x,z ∈ [ [A] ] but y∉[ [A] ] (with \(x, z\notin \min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\); this can be ensured by designating the fourth world w to be the sole member of that set) and so ρ_A(x,z) = 0. Since ρ_Ψ(x,z) = 0, we therefore have ρ_Ψ∗A(x,z) = 0. We also have ρ_A(x,y) = 1 and ρ_A(y,z) = − 1. Therefore ρ_Ψ∗A(x,y) = a₁ and ρ_Ψ∗A(y,z) = d₁. Assume a₁≠ − d₁ for reductio (so that 〈a₁,d₁〉 is equal to either 〈1, 0〉, 〈0, 1〉, 〈− 1, 0〉, 〈0,− 1〉, 〈1, 1〉, or 〈− 1,− 1〉). It then follows, by transitivity of \(\preccurlyeq _{\Psi \ast A}\), that ρ_Ψ∗A(x,z) = 1 or − 1. But this contradicts our earlier finding that ρ_Ψ∗A(x,z) = 0. Hence a₁ = −d₁. By similar reasoning, we can establish that e₁ = −d₁ (let A be such that y,x ∈ [ [A] ] but z∉[ [A] ], with \(y, x\notin \min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\) and hence ρ_A(y,x) = 0) and e₁ = −b₁ (let A be such that z,y ∈ [ [A] ] but x∉[ [A] ], with \(z, y\notin \min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\), and hence ρ_A(z,y) = 0) and hence that a₁ = −b₁, as required. □

Lemma 3

The conjunction of \((\text {KM}^{\ast }_{\preccurlyeq })\), transitivity of \({\preccurlyeq }_{\Psi \ast A}\), \((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\text {IIA}^{\ast }_{\preccurlyeq })\) implies the following “Representation Invariance” principle:

• \((\text {RI}^{\ast }_{\preccurlyeq })\) ρ_Ψ∗A(x,y) = ρ_Θ∗π(A)(π(x),π(y)), for any order isomorphism π from \({\preccurlyeq }_{\Psi }\) to \({{\preccurlyeq }_{{\varTheta }}}\)

Proof

We consider 3 cases, depending on x and y’s membership of \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\): (a) one of x or y is in the set, (b) both x and y are in the set and (c) neither x nor y are in the set.

For each case, we shall prove the identity of the matrices relating to the pair 〈x,y〉 and revision by A on the one hand, and the pair 〈π(x),π(y)〉 and revision by π(A), on the other. Since, if π is an order isomorphism from \(\preccurlyeq _{\Psi }\) to \(\preccurlyeq _{{\varTheta }}\), then ρ_Ψ(x,y) = ρ_Θ(π(x),π(y)) and ρ_A(x,y) = ρ_π(A)(π(x),π(y)), it then follows that ρ_Ψ∗A(x,y) = ρ_Θ∗π(A)(π(x),π(y)), as required.

Assume (a), so that, for example, \(x \in \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), \(y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) (the other case in analogous). Since we then have ρ_A(x,y) ≥ 0, it must be the case that either (i) ρ_A(x,y) = 1, or (ii) ρ_A(x,y) = 0. Furthermore, if (ii) is the case, it must be the case that ρ_Ψ(x,y) = 1. The relevant matrix is then given in Table 8a, with impossible combinations of values indicated by “×”. Since, for all x ∈ W, A ∈ L and order isomorphisms π from \(\preccurlyeq _{\Psi }\) to \(\preccurlyeq _{{\varTheta }}\), we have \(x\in \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) iff \(\pi (x)\in \min \limits (\preccurlyeq _{\Psi }, [\![{\pi (A)}]\!])\), the same matrix characterises the pair 〈π(x),π(y)〉 under revision by π(A). Assume (b). The reasoning is analogous to the one provided in relation to (a) above, this time with reference to the matrix given in Table 8b. Assume (c). Again, as we have noted above, since we assume A to be consistent and hence that \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) is non-empty, we must have at least 4 worlds. Here we make use of the transitivity of \(\preccurlyeq _{\Psi \ast A}\), much as we did in the proof of Lemma 2, and consider, in addition to 〈x,y〉, the pairs 〈y,z〉 and 〈z,x〉. The matrices for these pairs are given in Table 7 above.

Using the strategy applied in relation to the same case in the proof of Lemma 2, we can show that, for 1 ≤ i ≤ 4, not only a_i = −b_i and c_i = −d_i, but also a_i = −d_i and so a_i = c_i. So the matrix for all sentences is the same for all pairs of worlds. In particular, the matrix relating to the pair 〈x,y〉 and revision by A on the one hand, is identical to that relating the pair 〈π(x),π(y)〉 and revision by π(A), on the other.

Proposition 7

In the presence of \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\), \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) implies \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\).

Proof

Assume \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), ρ_Ψ(x,y) = ρ_Θ(x,y) and ρ_A(x,y) = ρ_B(x,y). We need to show that ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y). By \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\), there will exist a state Ξ and sentence C such that \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{\Xi }, [\![{C}]\!])\), ρ_Ψ(x,y) = −ρ_Ξ(x,y) and ρ_A(x,y) = −ρ_C(x,y). By \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we then have ρ_Ψ∗A(x,y) = −ρ_Ξ∗C(x,y). But since ρ_Ψ(x,y) = ρ_Θ(x,y) and ρ_A(x,y) = ρ_B(x,y), we also have ρ_Θ(x,y) = −ρ_Ξ(x,y) and ρ_B(x,y) = −ρ_C(x,y). Since \(x, y \notin \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\cup \min \limits (\preccurlyeq _{\Xi }, [\![{C}]\!])\), we can reapply \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), to obtain ρ_Θ∗B(x,y) = −ρ_Ξ∗C(x,y). Hence ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y), as required. □

Proposition 8

\((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) does not imply either \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) or \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) even in the presence \((\text {KM}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\mathrm {C}{1}, {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)

Proof

We simply need to show that both the operators introduced in the proof of Proposition 4 satisfy \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\). Indeed, both satisfy \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), but the first does not satisfy \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and the second does not satisfy \((\text {IIAI}^{\ast }_{\scriptscriptstyle \preccurlyeq })\).

Regarding the first operator: If π is an order isomorphism between \(\preccurlyeq _{\Psi }\) and \(\preccurlyeq _{{\varTheta }}\), then \(\preccurlyeq _{\Psi }\) is a chain if and only if \(\preccurlyeq _{{\varTheta }}\) is. So we have \(\rho _{\Psi \ast A}({x},{y}) = \rho _{\Psi \ast _{\mathrm {L}} A}(x,y)\) if and only if we have \(\rho _{{\varTheta }\ast \pi (A)}({\pi (x)},{\pi (y)}) = \rho _{{\varTheta }\ast _{\mathrm {L}} \pi (A)}({\pi (x)},{\pi (y)})\) and similarly regarding ∗_R. But we have also noted that ∗_L and ∗_R both satisfy \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). Furthermore, since they also satisfy \((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) (because they satisfy \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\); see Lemma 1) and \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), we know from Lemma 3 that they also satisfy \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\).

Regarding the second operator: If π is an order isomorphism between \(\preccurlyeq _{\Psi }\) and \(\preccurlyeq _{{\varTheta }}\), then \(\lvert [\![{\neg A}]\!]\rvert =1\) iff \(\lvert [\![{\pi (\neg A)}]\!]\rvert =1\). So we have \(\rho _{\Psi \ast A}({x},{y}) = \rho _{\Psi \ast _{\mathrm {L}} A}({x},{y})\) iff \(\rho _{\Psi \ast \pi (A)}({\pi (x)},{\pi (y)}) = \rho _{\Psi \ast _{\mathrm {L}} \pi (A)}({\pi (x)},{\pi (y)})\) and similarly regarding ∗_R. The reasoning to establish \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) then proceeds as above. □

Proposition 9

\((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) entails \((\text {TPOR}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\).

Proof

Let \(\preccurlyeq _{\Psi }=\preccurlyeq _{{\varTheta }}\) and the order isomorphism π be such that π(x) = x. It follows by \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) that ρ_Ψ∗A(x,y) = ρ_Θ∗π(A)(π(x),π(y)) = ρ_Θ∗A(x,y). □

Proposition 10

Given AGM, \((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is equivalent to:

• (PI^∗ ) If [Ψ∗B] = Cn(B), then [(Ψ∗A) ∗ A ∧ B] = [Ψ∗A ∧ B] and [(Ψ∗A) ∗¬A ∧ B] = [Ψ ∗¬A ∧ B]

Proof

From \((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) to (PI^∗): Assume that [Ψ∗B] = Cn(B) but, for reductio, [(Ψ ∗ A) ∗ A ∧ B]≠[Ψ∗A ∧ B] (the case of [(Ψ ∗ A) ∗¬A ∧ B] = [Ψ∗¬A ∧ B] is analogous). We consider two cases:

• (i) \([{\Psi \ast A\wedge B}] \nsubseteq [{({\Psi }\ast A)\ast A\wedge B}]\), so \( [\![[{({\Psi }\ast A)\ast A\wedge B}]]\!] \nsubseteq [\![[{({\Psi }\ast A)\ast A\wedge B}]]\!]\): Then, since we assume A ∧ B to be consistent, \(\exists x\in \min \limits (\preccurlyeq _{\Psi \ast A}, [\![{A\wedge B}]\!])\setminus \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge B}]\!])\). Let \(y\in \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge B}]\!])\). On the one hand, since x,y ∈ [ [B] ] and [Ψ∗B] = Cn(B), we have \(x, y\in \min \limits (\preccurlyeq _{\Psi }, [\![{B}]\!])\), by \((\text {KM}^{\ast }_{\preccurlyeq })\), and so \(x\sim _{\Psi } y\). On the other hand, since \(y\in \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge B}]\!])\), and x ∈ [ [A ∧ B] ] but \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge B}]\!])\), we have y ≺_Ψx. Contradiction.

• (ii) \([{({\Psi }\ast A)\ast A\wedge B}]\nsubseteq [{\Psi \ast A\wedge B}]\) and so \([\![[{\Psi \ast A\wedge B}]]\!]\nsubseteq [\![[({\Psi }\ast A)\ast A\wedge B]]\!]\): Then, since we assume A ∧ B to be consistent, \(\exists x\in \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge B}]\!]) \setminus \min \limits (\preccurlyeq _{\Psi \ast A}, [\![{A\wedge B}]\!])\). Let \(y\in \min \limits (\preccurlyeq _{\Psi \ast A}, [\![{A\wedge B}]\!])\). As above, since x,y ∈ [ [B] ] and [Ψ∗B] = Cn(B), we have \(x\sim _{\Psi } y\). Since x,y ∈ [ [A] ], it follows from this, by \((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), that \(x\sim _{\Psi \ast A} y\). But since \(y\in \min \limits (\preccurlyeq _{\Psi \ast A}, [\![{A\wedge B}]\!])\), and x ∈ [ [A ∧ B] ] but \(x\notin \min \limits (\preccurlyeq _{\Psi \ast A}, [\![{A\wedge B}]\!])\), we also have y ≺_Ψ∗Ax. Contradiction.

From (PI^∗) to \((\text {PI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\): Assume \(x\sim _{\Psi } y\). Then \(\min \limits (\preccurlyeq _{\Psi }, [\![{x\vee y}]\!])=[\![{x\vee y}]\!]\) and so [Ψ∗x ∨ y] = Cn(x ∨ y). By (PI^∗), letting B = x ∨ y, we then have:

• (a) [(Ψ ∗ A) ∗ A ∧ (x ∨ y)] = [Ψ∗A ∧ (x ∨ y)]

• (b) [(Ψ ∗ A) ∗¬A ∧ (x ∨ y)] = [Ψ∗¬A ∧ (x ∨ y)]

We consider two cases:

• (i) Assume x,y ∈ [ [A] ]. Then A ∧ (x ∨ y) ≡ x ∨ y. So by (a), [(Ψ ∗ A) ∗ x ∨ y] = [Ψ∗x ∨ y] = Cn(x ∨ y). Since \(x\sim _{\Psi \ast A} y\) iff [(Ψ ∗ A) ∗ x ∨ y] = Cn(x ∨ y), it then follows that \(x\sim _{\Psi \ast A} y\), as required.

• (ii) Assume x,y ∈ [ [¬A] ]. Then we obtain \(x\sim _{\Psi \ast A} y\) by the same reasoning as above, this time using (b).

□

Proposition 11

Given AGM and \((\mathrm {C}{1,2}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\),\((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) are respectively equivalent to:

• \((\text {IIA}_{\preccurlyeq })\) If ¬C ∈ [Ψ ∗ A] ∩ [Θ ∗ B],A ≡_CB and Ψ and Θ agree modulo C, then so do Ψ ∗ A and Θ ∗ B

• \((\text {IIAP}_{\preccurlyeq })\) If ¬C ∈ [Ψ ∗ A] ∩ [Θ ∗ A], then, if Ψ and Θ agree modulo C , so do Ψ ∗ A and Θ ∗ A

• \((\text {IIAI}_{\preccurlyeq })\) If ¬C ∈ [Ψ ∗ A] ∩ [Ψ ∗ B] and A ≡_CB, then Ψ ∗ A and Ψ ∗ B agree modulo C

Proof

We simply prove the equivalence of (IIA^∗) and \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), since the remaining equivalences are established in an analogous manner. We first note that \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) gives us the result that, if ρ_Ψ(x,y) = ρ_Θ(x,y) and x,y ∈ [ [A ∧¬B] ] or x,y ∈ [ [¬A ∧ B] ], then ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y). “Removing” these two cases from the condition ρ_A(x,y) = ρ_B(x,y) leaves us with four cases: (i) x ∈ [ [A ∧ B] ] and y ∈ [ [¬A ∧¬B] ], (ii) y ∈ [ [A ∧ B] ] and x ∈ [ [¬A ∧¬B] ], (iii) x,y ∈ [ [A ∧ B] ], or (iv) x,y ∈ [ [¬A ∧¬B] ]. In view of this, \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is equivalent to the following weaker principle in the presence of \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\):

• If \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), then, if ρ_Ψ(x,y) = ρ_Θ(x,y) and (i) x ∈ [ [A ∧ B] ] and y ∈ [ [¬A ∧¬B] ], (ii) y ∈ [ [A ∧ B] ] and x ∈ [ [¬A ∧¬B] ], (iii) x,y ∈ [ [A ∧ B] ], or (iv) x,y ∈ [ [¬A ∧¬B] ], then ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y)

We first show that this weaker principle can alternatively be presented as follows:

• If \([\![{C}]\!]\cap (\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!]) )= \varnothing \) and, for all x,y ∈ [ [C] ], ρ_Ψ(x,y) = ρ_Θ(x,y) and either (i) x ∈ [ [A ∧ B] ] and y ∈ [ [¬A ∧¬B] ], (ii) y ∈ [ [A ∧ B] ] and x ∈ [ [¬A ∧¬B] ], (iii) x,y ∈ [ [A ∧ B] ], or (iv) x,y ∈ [ [¬A ∧¬B] ], then, for all x,y ∈ [ [C] ], ρ_Ψ∗A(x,y) = ρ_Θ∗A(x,y)

Going from the second principle to the first, the entailment is obvious, since the latter is just the special case in which [ [C] ] = {x,y}. Going the other way, assume that \([\![{C}]\!]\cap (\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])) = \varnothing \) and, for all x,y ∈ [ [C] ], ρ_Ψ(x,y) = ρ_Θ(x,y) and (i) x ∈ [ [A ∧ B] ] and y ∈ [ [¬A ∧¬B] ], (ii) y ∈ [ [A ∧ B] ] and x ∈ [ [¬A ∧¬B] ], (iii) x,y ∈ [ [A ∧ B] ], or (iv) x,y ∈ [ [¬A ∧¬B] ]. Assume further that x,y ∈ [ [C] ], for arbitrary x,y ∈ W. From these assumptions, we have \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), ρ_Ψ(x,y) = ρ_Θ(x,y) and (i) x ∈ [ [A ∧ B] ] and y ∈ [ [¬A ∧¬B] ], (ii) y ∈ [ [A ∧ B] ] and x ∈ [ [¬A ∧¬B] ], (iii) x,y ∈ [ [A ∧ B] ], or (iv) x,y ∈ [ [¬A ∧¬B] ]. Given this, by \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), it follows that ρ_Ψ∗A(x,y) = ρ_Θ∗B(x,y), as required.

Next we establish syntactic equivalents for the various semantic properties figuring in this principle.

Clearly \([\![{C}]\!]\cap (\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!]) )= \varnothing \) iff ¬C ∈ [Ψ∗A] ∩ [Θ ∗ B]. Furthermore, it is easy to see that conditions (i) to (iv) hold for all x,y ∈ [ [C] ] iff A ≡_CB.

Finally, we can show that ρ_Ψ(x,y) = ρ_Θ(x,y) for all x,y ∈ [ [C] ] iff Ψ and Θ agree modulo C (and obviously similarly regarding Ψ ∗ A and Θ ∗ B).

Indeed, assume that (1) ∀B ∈ L, [Ψ∗B ∧ C] = [Θ ∗ B ∧ C], but, for reductio, that (2) ∃x,y ∈ [ [C] ], such that ρ_Ψ(x,y)≠ρ_Θ(x,y). Where B ∈ L is such that [ [B ∧ C] ] = {x,y}, it follows from (2) that \(\min \limits (\preccurlyeq _{\Psi }, [\![{B\wedge C}]\!])\neq \min \limits (\preccurlyeq _{{\varTheta } ,} [\![{B\wedge C}]\!])\). But from (1), we have \(\min \limits (\preccurlyeq _{\Psi }, [\![{B\wedge C}]\!])=\min \limits (\preccurlyeq _{{\varTheta }}, [\![{B\wedge C}]\!])\). Contradiction.

Going the other way, assume that (1) ∀x,y ∈ [ [C] ], ρ_Ψ(x,y) = ρ_Θ(x,y), but, for reductio, that (2) ∃B ∈ L such that [Ψ∗B ∧ C]≠[Θ ∗ B ∧ C]. From (2), \(\min \limits (\preccurlyeq _{\Psi }, [\![{B\wedge C}]\!])\neq \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B\wedge C}]\!])\). From this, either there exists x ∈ W such that \(x\in \min \limits (\preccurlyeq _{\Psi }, [\![{B\wedge C}]\!])\) but \(x\notin \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B\wedge C}]\!])\), or exists x ∈ W such that \(x\in \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B\wedge C}]\!])\) but \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![{B\wedge C}]\!])\). Assume the former (the other case is analogous). Let \(y\in \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B\wedge C}]\!])\). From this, we have y ≺_Θx but \(x\preccurlyeq _{\Psi } y\) and hence ρ_Ψ(x,y)≠ρ_Θ(x,y). However, since x,y ∈ [ [C] ], this contradicts (1). □

Proposition 12

Given AGM and \((\mathrm {C}{1, 2}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is equivalent to:

• (ZS^∗ ) If ¬C ∈ [Ψ ∗ A] ∩ [Θ ∗ B],A ≡_C¬B and Ψ and Θ are in opposition modulo C, then so are Ψ∗A and Θ ∗ B

Proof

The proof is somewhat similar to the one given in relation to Proposition 11. We first note that \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) gives us the result that, if ρ_Ψ(x,y) = −ρ_Θ(x,y) and x,y ∈ [ [A ∧ B] ] or x,y ∈ [ [¬A ∧¬B] ], then ρ_Ψ∗A(x,y) = −ρ_Θ∗B(x,y). Note that in these two cases, we have ρ_A(x,y) = −ρ_B(x,y) = 0. “Removing” the cases from the condition ρ_A(x,y) = −ρ_B(x,y) leaves us with two cases: (i) x ∈ [ [A ∧¬B] ] and y ∈ [ [¬A ∧ B] ] and (ii) y ∈ [ [A ∧¬B] ] and x ∈ [ [¬A ∧ B] ].

In view of this, \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is equivalent to the following weaker principle in the presence of \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\):

• If \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), ρ_Ψ(x,y) = −ρ_Θ(x,y) and (i) x ∈ [ [A ∧¬B] ] and y ∈ [ [¬A ∧ B] ] or (ii) y ∈ [ [A ∧¬B] ] and x ∈ [ [¬A ∧ B] ], then ρ_Ψ∗A(x,y) = −ρ_Θ∗B(x,y)

We first show that this weaker principle can alternatively be presented as follows:

• If \([\![{C}]\!]\cap (\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])) = \varnothing \) and, for all x,y ∈ [ [C] ], ρ_Ψ(x,y) = −ρ_Θ(x,y) and (i) x ∈ [ [A ∧¬B] ] and y ∈ [ [¬A ∧ B] ] or (ii) y ∈ [ [A ∧¬B] ] and x ∈ [ [¬A ∧ B] ], then, for all x,y ∈ [ [C] ], ρ_Ψ∗A(x,y) = −ρ_Θ∗B(x,y)

Going from the second principle to the first, the entailment is obvious, since the latter is just the special case in which [ [C] ] = {x,y}. Going the other way, assume that \([\![{C}]\!]\cap (\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!]) = \varnothing \) and, for all x,y ∈ [ [C] ], (i) x ∈ [ [A ∧¬B] ] and y ∈ [ [¬A ∧ B] ] or (ii) y ∈ [ [A ∧¬B] ] and x ∈ [ [¬A ∧ B] ], and ρ_Ψ(x,y) = −ρ_Θ(x,y). From these assumptions, we have \(x, y \notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!])\), ρ_Ψ(x,y)= −ρ_Θ(x,y) and ρ_A(x,y) = −ρ_B(x,y). Given this, by \((\text {ZS}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), it follows that ρ_Ψ∗A(x,y) = −ρ_Θ∗B(x,y), as required.

Next we establish syntactic equivalents for the various semantic properties figuring in this principle.

As we have noted above, in the proof of Proposition 11, \([\![{C}]\!]\cap (\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\cup \min \limits (\preccurlyeq _{{\varTheta }}, [\![{B}]\!]) )= \varnothing \) iff ¬C ∈ [Ψ∗A] ∩ [Θ ∗ B]. Furthermore, (i) and (ii) hold for all x,y ∈ [ [C] ] iff A ≡_C¬B.

Finally, we can show that ρ_Ψ(x,y) = −ρ_Θ(x,y) for all x,y ∈ [ [C] ] iff Ψ and Θ are in opposition modulo C (and obviously similarly regarding Ψ ∗ A and Θ ∗ B).

From left to right: Assume that (1) ∀x,y ∈ [ [C] ], ρ_Ψ(x,y) = −ρ_Θ(x,y) but, for reductio, that ∃B,D ∈ L such that B is quasi-complete, \(B\wedge C\nvdash D\), D ∈ [Ψ∗B ∧ C] but ¬D∉[Θ ∗ B ∧ C]. Since \(B\wedge C\nvdash D\), there exists x ∈ [ [B ∧ C ∧¬D] ]. Let \(y\in \min \limits (\preccurlyeq _{\Psi }, [\![{B\wedge C}]\!])\) (we can assume that such a y exists, since \(B\wedge C\nvdash D\) and hence \([\![{B\wedge C}]\!]\neq \varnothing \)). Since D ∈ [Ψ∗B ∧ C] and x ∈ [ [B ∧ C ∧¬D] ], we have y ≺_Ψ∗B∧Cx. Therefore, since x,y ∈ [ [B ∧ C] ], by \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), it follows that y ≺_Ψx, so that ρ_Ψ(x,y) = − 1. Given our assumption that ρ_Ψ(x,y) = −ρ_Θ(x,y), we then recover ρ_Θ(x,y) = 1. From this, given that x,y ∈ [ [B ∧ C] ], we have ρ_Θ∗B∧C(x,y) = 1, by \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). Since B is quasi-complete and x,y ∈ [ [B ∧ C] ], we also have [ [B ∧ C] ] = {x,y}. It then follows that ¬D ∈ [Θ ∗ B ∧ C]. Contradiction.

From right to left: Assume that (1) for all B,D ∈ L such that B is quasi-complete and \(B\wedge C\nvdash D\), if D ∈ [Ψ∗B ∧ C], then ¬D ∈ [Θ ∗ B ∧ C], but, for reductio, that (2) ∃x,y ∈ [ [C] ], such that ρ_Ψ(x,y)≠ − ρ_Θ(x,y). Where B ∈ L is such that [ [B] ] = {x,y}, and D ∈ L is such that x ∈ [ [D] ] but y∉[ [D] ], it follows from (1) that x ≺_Ψ∗B∧Cy and y ≺_Θ∗B∧Cx. By \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), since x,y ∈ [ [B ∧ C] ], we then have x ≺_Ψy and y ≺_Θx and hence ρ_Ψ(x,y) = −ρ_Θ(x,y). Contradiction. □

Proposition 13

Given AGM \((\text {RI}^{\ast }_{\preccurlyeq })\) is equivalent to

• \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle })\) \(B {\kern -.5pt}\in {\kern -.5pt} [({\Psi \ast A}) \ast C]\ \mathit {iff}\ \iota (B){\kern -.5pt} \in {\kern -.5pt} [({{\varTheta }\ast \iota (A)})\ast \iota (C)]\), for any c-belief isomorphism ι from Ψ to Θ

Proof For convenience, we first recall the definition of \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\):

• \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) ρ_Ψ∗A(x,y) = ρ_Θ∗π(A)(π(x),π(y)), for any order isomorphism π from \( \preccurlyeq _{\Psi }\) to \(\preccurlyeq _{{\varTheta }}\)

Let I be the set of all c-belief isomorphisms between Ψ and Θ and π the set of all order isomorphisms between the corresponding TPOs. We will show that there exists a bijection f between π and I such that if ι = f(π), then the biconditional of (RI^∗) holds for ι iff the equality of \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) holds for π. It then follows from this that the biconditional holds for all ι in I iff the equality holds for all π in π.

We divide the proof into two lemmas. The first establishes that a particular relation f is a bijection. The second shows that f has the required property stated above. The first lemma, then, is:

Lemma 5

The relation \(f\subseteq {\Pi }\times I\), such that, ∀A ∈ L, ∀π ∈π, ∀ι ∈ I, f(π,ι) iff [ [ι(A)] ] = {x ∈ W∣∃y ∈ [ [A] ], such that x = π(y)}, is a bijection from π to I.

In other words f maps π onto the unique ι (modulo logical equivalence) such that the set of models of the image, under ι, of a sentence A is the set of images, under π, of the models of A. Since f is a bijection, we write f(π) for the unique ι (modulo logical equivalence) such that f(π,ι).

To establish Lemma 5, we first note that [18, Proposition 6.2] already prove the following first of two sublemmas, where \({\Sigma }\supseteq I\) is the set of all belief amount preserving symbol translations (i.e. permutations of L satisfying properties (i)–(iii) of Definition 9) σ on L and \({\varGamma }\supseteq {\Pi }\) is the set of all permutations γ of W:

Sublemma 1

The relation \(g\subseteq {\Pi }\times {\varSigma }\), such that, ∀A ∈ L, ∀γ ∈Γ, ∀σ ∈Σ, f(γ,σ) iff [ [σ(A)] ] = {x ∈ W∣∃y ∈ [ [A] ], such that x = γ(y)}, is a bijection from Γ to Σ.

In view of this, it therefore simply remains to be shown that ι is in I iff its pre-image under g is in π, since it then follows from this, and the fact that g is a bijection between Γ and Σ, that f is a bijection between π and I:

Sublemma 2

Where ι = g(π), the following are equivalent

• (1) For all x,y ∈ W, ρ_Ψ(x,y) = ρ_Θ(π(x),π(y))

• (2) For all A,B ∈ L, B ∈ [Ψ∗A] iff ι(B) ∈ [Θ ∗ ι(A)]

From (1) to (2): Assume ι = g(π) and (1). We need to establish (2), which, given \((\text {KM}^{\ast }_{\preccurlyeq })\), we can reformulate in terms of minimal sets as: \(\min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\subseteq [\![{B}]\!]\) iff \(\min \limits (\preccurlyeq _{{\varTheta }},[\![{\iota (A)}]\!])\subseteq [\![{\iota (B)}]\!]\). We simply derive the left to right direction of (2), since the other direction is established in an analogous manner. Assume that \(\min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\subseteq [\![{B}]\!]\) but, for reductio, that \(\min \limits (\preccurlyeq _{{\varTheta }},[\![{\iota (A)}]\!])\nsubseteq [\![{\iota (B)}]\!]\), so that \(\exists x\in \min \limits (\preccurlyeq _{{\varTheta }},[\![{\iota (A)}]\!])\cap [\![{\neg \iota (B)}]\!]\). By the definitions of ι and g, it follows that π^− 1(x) ∈ [ [A] ] ∩ [ [¬B] ]. Let \(y\in \min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\). Since \(\min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\subseteq [\![{B}]\!]\), we then have y ≺_Ψπ^− 1(x). By (1), we then have π(y) ≺_Θx. Since y ∈ [ [A] ], it follows by the definition of g that π(y) ∈ [ [ι(A)] ] and so, given π(y) ≺_Θx, that \(x\notin \min \limits (\preccurlyeq _{{\varTheta }},[\![{\iota (A)}]\!])\) after all: contradiction.

From (2) to (1): Assume that ι = g(π) and that (2) holds. Given \((\text {KM}^{\ast }_{\preccurlyeq })\), we can again reformulate (2) in terms of minimal sets as: \(\min \limits (\preccurlyeq _{\Psi },[\![{A}]\!])\subseteq [\![{B}]\!]\) iff \(\min \limits (\preccurlyeq _{{\varTheta }},[\![{\iota (A)}]\!])\subseteq [\![{\iota (B)}]\!]\). Where [ [A] ] = {x,y}, this gives us, in view of the definition of g:

• \(\min \limits (\preccurlyeq _{\Psi }, \{x, y\})\subseteq [\![{B}]\!]\) iff \(\min \limits (\preccurlyeq _{{\varTheta }}, \{\pi (x), \pi (y)\})\subseteq [\![{\iota (B)}]\!]\)

By the definition of g, for all x ∈ W, x ∈ [ [B] ] iff π(x) ∈ [ [ι(B)] ]. Hence ρ_Ψ(x,y) = ρ_Θ(π(x),π(y)), i.e. (1). This completes the proof of Sublemma 2 and hence of Lemma 5.

We finally derive our second lemma towards the proof of our main result, which tells us that f has the required property, namely that, if ι = f(π), then the biconditional in (RI^∗) holds for ι, iff the equality in \((\text {RI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) holds for π:

Lemma 6

Where ι = f(π), the following are equivalent

• (1) For all x,y ∈ W and A ∈ L, ρ_Ψ∗A(x,y) = ρ_Θ∗π(A)(π(x),π(y))

• (2) For all A,B,C ∈ L, B ∈ [(Ψ ∗ A) ∗ C] iff ι(B) ∈ [(Θ ∗ ι(A)) ∗ ι(C)]

The proof of this is identical to that of Sublemma 2, save for the fact that we need to note that, as we defined the extension of π to L, Θ ∗ π(A) = Θ ∗ ι(A).

The conjunction of Lemmas 5 and 6 then establishes the required result. □

Proposition 15

Lexicographic revision is the only elementary revision operator that satisfies \((\text {IIAP}+^{\ast }_{\preccurlyeq })\)

Proof

We show that, given \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\), \((\mathrm {IIAP+}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) entails Recalcitrance (i.e. if ρ_A(x,y) = 1, then ρ_Ψ∗A(x,y) = 1), which characterises lexicographic revision in the presence of \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). This was already established as Fact 2.2 (a) in [15]. Let ρ_A(x,y) = 1, so that x ∈ [ [A] ] and y ∈ [ [¬A] ]. Then, by \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\), for any state Ψ, there will exist a state Θ such that ρ_Θ(x,y) = ρ_Ψ(x,y) and \(x\in \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\) (and, since y ∈ [ [¬A] ], \(y\notin \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\)). But by \((\text {KM}^{\ast }_{\preccurlyeq })\), if \(x\in \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\) but \(y\notin \min \limits (\preccurlyeq _{{\varTheta }}, [\![{A}]\!])\), then x ≺_Θ∗Ay. So, by \((\mathrm {IIAP+}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), x ≺_Ψ∗Ay, as required. □

Proposition 16

Lexicographic revision is the only elementary revision operator that satisfies \((\text {IIAI}+^{\ast }_{\preccurlyeq })\)

Proof

\((\mathrm {IIAI+}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\), in conjunction with \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)–\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), can be shown to entail a principle that we have called “\((\beta {1 +}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)” in previous work [6]. Indeed, in the proof of Proposition 6 above, we established the equivalence between \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and the conjunction of \((\beta {1}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\beta {2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) using only \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)–\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). This proof can be adapted to establish a strengthening of Proposition 3 in [8], in which, unlike in the original, the principle of “Independence” \((\mathrm {P}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) is not appealed to. This yields the following: In the presence of \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)–\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), Booth & Meyer’s strengthening of \((\text {IIAI}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is equivalent to the conjunction of what [6] call “\((\beta {1 +}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)” and “\((\beta {2 +}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)”.

Furthermore, we also showed in [6] (see Corollary 1 there) that \((\beta {1 +}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) characterises lexicographic revision, given \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)-\((\mathrm {C}{2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). □

Proposition 17

Lexicographic revision is the only elementary revision operator that satisfies \((\text {ZS}{+}^{\ast }_{\preccurlyeq })\)

Proof

We show that, given \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\mathrm {C}{3}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), \((\mathrm {ZS+}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) entails Recalcitrance (i.e. if ρ_A(x,y) = 1, then ρ_Ψ∗A(x,y) = 1), which characterises lexicographic revision in the presence of \((\mathrm {C}{1, 2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\). Assume for reductio that Recalcitrance fails, so that there exists Ψ, x,y ∈ W, A ∈ L such that

• (1) ρ_A(x,y) = 1

• (2) ρ_Ψ∗A(x,y)≠ 1

From (1) and (2), by \((\mathrm {C}{3}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), we must have:

• (3) ρ_Ψ(x,y)≠ 1

From (1), we have:

• (4) ρ_¬A(x,y) = − 1

From (1), it follows that y ∈ [ [¬A] ] and x≠y, and so by \((\text {UD}_{\scriptscriptstyle \preccurlyeq })\) there exists a state Θ such that:

• (5) \(y\in \min \limits (\preccurlyeq _{{\varTheta }}, [\![{\neg A}]\!])\)

• (6) ρ_Θ(x,y) = −ρ_Ψ(x,y)

From (1), (4), (3) and (6), by \((\mathrm {ZS+}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\):

• (7) ρ_Θ∗¬A(x,y)≠ − 1

However, by AGM, given (4) and (5), we have ρ_Θ∗¬A(x,y) = − 1, directly contradicting (7). □

Proposition 18

Given AGM ÷_R is characterised by the following property:

Proof

We first recall the definition of ÷_R:

• If x ∈ or \(y \in \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A}]\!])\), then:

  $$ \rho_{\Psi\div_{\mathrm{R}} A}({x},{y})=\begin{cases} 1 \text{, if } x \in \text{ and } y\notin \min(\preccurlyeq_{\Psi}, W)\cup \min(\preccurlyeq_{\Psi}, [\![{\neg A}]\!]) \\ 0\text{, if } x\in \text{ and } y \in \min(\preccurlyeq_{\Psi}, W)\cup \min(\preccurlyeq_{\Psi}, [\![{\neg A}]\!]) \\ -1\text{, if } x\notin \text{ and } y \in \min(\preccurlyeq_{\Psi}, W)\cup \min(\preccurlyeq_{\Psi}, [\![{\neg A}]\!]) \end{cases} $$

• If x∉ and \(y \notin \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A}]\!])\), then:

  $$ \rho_{\Psi\div_{\mathrm{R}} A}({x},{y})=\begin{cases} \rho_{\Psi}({x},{y})\text{, if }\rho_{\Psi}({x},{y})\neq 0\\ \rho_{\neg A}({x},{y})\text{, if }\rho_{\Psi}({x},{y})= 0\end{cases} $$

Next, with the help of (KM\(^{\div }_{\preccurlyeq }\)), we translate the two conditionals on the right hand side of the equality of the characteristic syntactic property into the following statements about minimal sets:

• (1) If \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\subseteq [\![{A\vee B}]\!]\), then \(\min \limits (\preccurlyeq _{({\Psi }\div A)\div B}, W)=\min \limits (\preccurlyeq _{\Psi \div A}, W)\cup \min \limits (\preccurlyeq _{\Psi \div A}, [\![{A\wedge \neg B}]\!])\)

• (2) If \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\nsubseteq [\![{A\vee B}]\!]\), then \(\min \limits (\preccurlyeq _{({\Psi }\div A)\div B}, W)=\min \limits (\preccurlyeq _{\Psi \div A}, W)\cup \min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg A\wedge \neg B}]\!])\)

From the semantic characterisation to the syntactic one: We first note that, given (KM\(^{\div }_{\preccurlyeq }\)), the consequent of (1) is equivalent to \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) - \min \limits (\preccurlyeq _{\Psi \div A}, W) = \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge \neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)\), while the consequent of (2) is equivalent to \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) - \min \limits (\preccurlyeq _{\Psi \div A}, W) = \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge \neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)\). We then split the proof into two obvious parts:

• (A) If ÷ = ÷_R, then (1): Assume \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\subseteq [\![{A\vee B}]\!]\), so that there does not exist \(x\in \min \limits (\preccurlyeq _{\Psi },[\![{\neg B}]\!])\cap [\![{\neg A}]\!]\). Assume for reductio that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)\nsubseteq [\![{A}]\!]\), so that there exists \(x\in \min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!])\cap [\![{\neg A}]\!]\) and \(x\notin \min \limits (\preccurlyeq _{\Psi \div A}, W)\). As we have noted, from our initial assumption, it must be the case that \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\cap [\![{\neg A}]\!]\) and hence, since x ∈ [ [A] ], \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\). So, since x ∈ [ [¬B] ], there exists y ∈ [ [¬B] ] such that ρ_Ψ(y,x) = 1. Given the semantic definition of ÷_R, the fact that \(x\notin \min \limits (\preccurlyeq _{\Psi \div A}, W)\) then suffices to ensure that ρ_Ψ÷A(y,x) = 1 (indeed, if \(y\in \min \limits (\preccurlyeq _{\Psi \div A}, W)\), then this follows from the first conditional of the definition, and if \(y\notin \min \limits (\preccurlyeq _{\Psi \div A}, W)\), then, since ρ_Ψ(y,x)≠ 0, the second conditional tells us that ρ_Ψ÷A(y,x) = ρ_Ψ(y,x) = 1), and hence, since y ∈ [ [¬B] ], \(x\notin \min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!])\cap [\![{\neg A}]\!]\). Contradiction. We can therefore conclude that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\subseteq [\![{A}]\!]\). From this, it follows that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)= \min \limits (\preccurlyeq _{\Psi \div A}, [\![{A\wedge \neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\). Since ÷_R satisfies \((\mathrm {C}{1,2}^{\scriptscriptstyle \div }_{\scriptscriptstyle \preccurlyeq })\), it follows that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{A\wedge \neg B}]\!])= \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge \neg B}]\!])\) and hence we finally have \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)= \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge \neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\), as required.

• (B) If ÷ = ÷_R, then (2): We first note that, like ÷_P, ÷_R satisfies the following property, which could be considered the analogue for contraction of the property \((\mathrm {P}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), satisfied by ∗_L and ∗_R:

  • \((\text {wP}^{\scriptscriptstyle \div }_{\scriptscriptstyle \preccurlyeq })\) If \(y\notin \min \limits (\preccurlyeq _{\Psi }, W)\), ρ_¬A(x,y) = 1 and ρ_Ψ(x,y) ≥ 0, then ρ_Ψ÷A(x,y) = 1^{Footnote 1}

  Now assume \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\nsubseteq [\![{A\vee B}]\!]\), so that there exists \(x\in \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\), such that x ∈ [ [¬A ∧¬B] ]. If \(x\in \min \limits (\preccurlyeq _{\Psi }, W)\), since x ∈ [ [¬B] ], we have \(x\in \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\). So, either way, \(x\in \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\). Assume for reductio that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)\nsubseteq [\![{\neg A}]\!]\), so that there exists \(y\in \min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\), such that y ∈ [ [A] ] and therefore, since x ∈ [ [¬A] ], ρ_¬A(x,y) = 1. Since \(x\in \min \limits (\preccurlyeq _{\Psi }, [\![{\neg B}]\!])\) and y ∈ [ [¬B] ], we have ρ_Ψ(x,y) ≥ 0. Since, by assumption, \(y\notin \min \limits (\preccurlyeq _{\Psi \div A}, W)\), it follows, by (KM\(^{\div }_{\preccurlyeq }\)), that \(y\notin \min \limits (\preccurlyeq _{\Psi }, W)\). Given, \(y\notin \min \limits (\preccurlyeq _{\Psi }, W)\), ρ_¬A(x,y) = 1, and ρ_Ψ(x,y) ≥ 0, we can now apply \((\text {wP}^{\scriptscriptstyle \div }_{\scriptscriptstyle \preccurlyeq })\), to obtain ρ_Ψ÷A(x,y) = 1. Since x,y ∈ [ [¬B] ], we then have \(y\notin \min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!])\). Contradiction. We can therefore conclude that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\subseteq [\![{\neg A}]\!]\). From this, it follows that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)= \min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg A\wedge \neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\). Since ÷_R satisfies \((\mathrm {C}{1,2}^{\scriptscriptstyle \div }_{\scriptscriptstyle \preccurlyeq })\), it follows that \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg A\wedge \neg B}]\!])= \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge \neg B}]\!])\) and hence we finally have \(\min \limits (\preccurlyeq _{\Psi \div A}, [\![{\neg B}]\!]) -\min \limits (\preccurlyeq _{\Psi \div A}, W)= \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge \neg B}]\!])-\min \limits (\preccurlyeq _{\Psi \div A}, W)\), as required.

From the syntactic characterisation to the semantic one: Assume x ∈ or \(y \in \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A}]\!])\). Then the required result follows simply by (KM\(^{\div }_{\preccurlyeq }\)). So assume that x∉ and \(y \notin \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A}]\!])\). We divide the remainder of the proof into two obvious parts:

• (A) Proof that, if ρ_Ψ(x,y)≠ 0, then ρ_Ψ÷A(x,y) = ρ_Ψ(x,y): It suffices to show that, if ρ_Ψ(x,y) = 1, then ρ_Ψ÷A(x,y) = 1 (establishing that, if ρ_Ψ(x,y) = − 1, then ρ_Ψ÷A(x,y) = − 1, is analogous). So assume that ρ_Ψ(x,y) = 1. We first note that the required conclusion that ρ_Ψ÷A(x,y) = 1 holds iff \(y\notin \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\): Indeed, by (KM\(^{\div }_{\preccurlyeq }\)), we have \(\min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)= \min \limits (\preccurlyeq _{\Psi \div A}, W)\cup \min \limits (\preccurlyeq _{\Psi \div A}, \{x, y\})\). Since \(\{x, y\}\subseteq W\), it then follows from this that \(y\in \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\) iff \(y\in \min \limits (\preccurlyeq _{\Psi \div A}, \{x, y\})\). Since, trivially, we have ρ_Ψ÷A(x,y) = 1 iff \(y\notin \min \limits (\preccurlyeq _{\Psi \div A}, \{x, y\})\), the required result then follows. We then split the proof into two cases:

  • (a) Assume \( \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, \{x, y\})\subseteq [\![{A\vee (\neg x\wedge \neg y)}]\!]\). Then, by (KM\(^{\div }_{\preccurlyeq }\)) and the syntactic characteristic principle (setting B = ¬x ∧¬y) we have:

    $$ \begin{array}{@{}rcl@{}} &&\min(\preccurlyeq_{({\Psi}\div A)\div\neg x\wedge \neg y}, W)\\ &&\quad\quad\quad\quad\quad\quad\quad= \min(\preccurlyeq_{\Psi\div A}, W)\cup \min(\preccurlyeq_{\Psi\div \neg A\vee (\neg x\wedge \neg y)}, W) \end{array} $$

    By assumption, \(y \!\notin \! \min \limits (\preccurlyeq _{\Psi \div A}, W)\). So it remains to be shown that \(y\!\notin \! \min \limits (\preccurlyeq _{\Psi \div \neg A\vee (\neg x\wedge \neg y)}, W)\). By (KM\(^{\div }_{\preccurlyeq }\)), \( \min \limits (\preccurlyeq _{\Psi \div \neg A\vee (\neg x\wedge \neg y)},\) \(W) = \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge (x\vee y)}]\!])\). Since we have already also assumed that \(y\notin \min \limits (\preccurlyeq _{\Psi }, W)\), we are just left with verifying that \(y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge (x\vee y)}]\!])\). So assume for reductio that \(y\in \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge (x\vee y)})]\!]\), so that y ∈ [ [A] ] and, if x ∈ [ [A] ], then ρ_Ψ(x,y) ≤ 0. From \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, \{x, y\})\subseteq [\![{A\vee (\neg x\wedge \neg y)}]\!]\) and ρ_Ψ(x,y) = 1, it follows that x ∈ [ [A] ]. Hence ρ_Ψ(x,y) ≤ 0. But this contradicts our assumption that ρ_Ψ(x,y) = 1. So \(y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge (x\vee y)})]\!]\) and we therefore have \(y\notin \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\), as required.

  • (b) Assume \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, \{x, y\})\nsubseteq [\![{A\vee (\neg x\wedge \neg y)}]\!]\). Then the reasoning is similar to the above, except that we proceed by showing that \(y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge (x\vee y)}]\!])\).

• (B) Proof that, if ρ_Ψ(x,y) = 0, then ρ_Ψ÷A(x,y) = ρ_¬A(x,y): Assume that ρ_Ψ(x,y) = 0. We again split the proof into two cases:

  • (a) Assume \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, \{x, y\})\subseteq [\![{A\vee (\neg x\wedge \neg y)}]\!]\). Then x,y ∈ [ [A] ] and so ρ_¬A(x,y) = 0. So we need to establish that ρ_Ψ÷A(x,y) = 0, or equivalently \(x, y\in \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\). It also follows, by (KM\(^{\div }_{\preccurlyeq }\)) and the syntactic characteristic principle (setting B = ¬x ∧¬y), that:

    $$ \begin{array}{@{}rcl@{}} &&\min(\preccurlyeq_{({\Psi}\div A)\div \neg x\wedge \neg y}, W) \\ &&\qquad\quad\quad\quad\qquad= \min(\preccurlyeq_{\Psi\div A}, W)\cup \min(\preccurlyeq_{\Psi\div (\neg A\vee (\neg x\wedge \neg y)}, W) \end{array} $$

    As we have already noted, by (KM\(^{\div }_{\preccurlyeq }\)), \( \min \limits (\preccurlyeq _{\Psi \div (\neg A\vee (\neg x\wedge \neg y)}, W) = \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge (x\vee y)})]\!]\). Furthermore, it follows from x,y ∈ [ [A] ] and ρ_Ψ(x,y) = 0 that \(x, y\in \min \limits (\preccurlyeq _{\Psi }, [\![{A\wedge (x\vee y)})]\!]\). Hence \(x, y\in \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\), as required.

  • (b) Assume \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, \{x, y\})\nsubseteq [\![{A\vee (\neg x\wedge \neg y)}]\!]\). Then, by (KM\(^{\div }_{\preccurlyeq }\)) and the syntactic characteristic principle (setting B = ¬x ∧¬y):

    $$ \begin{array}{@{}rcl@{}} &&\min(\preccurlyeq_{({\Psi}\div A)\div\neg x\wedge \neg y}, W)\\ &&\quad\quad\quad\quad\quad\quad\quad= \min(\preccurlyeq_{\Psi\div A}, W)\cup \min(\preccurlyeq_{\Psi\div A\vee (\neg x\wedge \neg y)}, W) \end{array} $$

    From the fact that \(\min \limits (\preccurlyeq _{\Psi }, \{x, y\})\nsubseteq [\![{A\vee (\neg x\wedge \neg y)}]\!]\) and hence, since ρ_Ψ(x,y) = 0, that \(\{x, y\}\nsubseteq [\![{A}]\!]\), we are left with two possibilities to consider:

    • (i) Assume x,y ∈ [ [¬A] ]. Then ρ_¬A(x,y) = 0. So we need to establish that ρ_Ψ÷A(x,y) = 0, or equivalently \(x, y\in \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\). By (KM\(^{\div }_{\preccurlyeq }\)), it follows that we have \( \min \limits (\preccurlyeq _{\Psi \div A\vee (\neg x\wedge \neg y)}, W) = \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge (x\vee y)}]\!])\). Since x,y ∈ [ [¬A] ] and ρ_Ψ(x,y) = 0, we have \(x, y\in \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge (x\vee y)}]\!])\) and so, finally, we recover \(x, y\in \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\), as required.

    • (ii) Assume x ∈ [ [A] ], y ∈ [ [¬A] ] (the other case, in which y ∈ [ [A] ], x ∈ [ [¬A] ] is analogous). Then ρ_¬A(x,y) = − 1. So we need to establish that ρ_Ψ÷A(x,y) = − 1, or equivalently \(x\notin \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\). We already know that \(x\notin \min \limits (\preccurlyeq _{\Psi \div A}, W)\). So it remains to be established that \(x\notin \min \limits (\preccurlyeq _{\Psi \div A\vee (\neg x\wedge \neg y)}, W)\). By (KM\(^{\div }_{\preccurlyeq }\)), \(\min \limits (\preccurlyeq _{\Psi \div (A\vee (\neg x\wedge \neg y)}, W) = \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge (x\vee y)}]\!])\). We have already assumed that \(x\notin \min \limits (\preccurlyeq _{\Psi }, W)\) and, since x ∈ [ [A] ], \(x\notin \min \limits (\preccurlyeq _{\Psi }, [\![{\neg A\wedge (x\vee y)}]\!])\). We therefore recover \(x\notin \min \limits (\preccurlyeq _{({\Psi }\div A)\div \neg x\wedge \neg y}, W)\), as required.

□

Proposition 19

Where i ∈ { P, R, N }, it is not the case that for any state Ψ and sentences A, B ∈ L there exists C ∈ L such that [(Ψ÷_iA) ÷_iB] = [Ψ ÷_iC]

Proof

We shall say that a rank associated with \(\preccurlyeq _{\Psi }\) is an equivalence class generated by the indifference relation \(\sim _{\Psi }\). All three operators are such that, if A ∈ [Ψ], then the number of ranks associated with \(\preccurlyeq _{\Psi \div A}\) is equal to n − 1, where n is the number of ranks associated with \(\preccurlyeq _{\Psi }\) (and equal to n if A∉[Ψ]). We can then find a countermodel by considering Ψ and A,B ∈ L such that A ∈ [Ψ] and B ∈ [Ψ÷A]: we will then have n − 2 ranks associated with \(\preccurlyeq _{({\Psi }\div A)\div B}\) and therefore no C ∈ L such that \(\preccurlyeq _{\Psi \div C}=\preccurlyeq _{({\Psi }\div A)\div B}\). Figure 6 depicts a countermodel relating to all three operators. □

Countermodel establishing Proposition 19

Full size image

Proposition 21

Let 〈i,j〉∈{〈N,N〉,〈R,R〉}. Then, if ∗ is defined from ÷_j using \((\mathrm {iLIRC_{\preccurlyeq }})\), then ∗ = ∗_i.

Proof

Let 〈i,j〉∈{〈N,N〉,〈R,R〉}. We need to show that the following equality holds: \(\rho _{\Psi \ast _{i} A}({x},{y}) = \rho _{({\Psi } \div _{j} \neg A) \ast _{\mathrm {N}} A}({x},{y})\).

We first note that our operators satisfy certain preservation conditions for strict preference. In particular ∗_N and ∗_R satisfy:

• (SPPres\(^{\ast }_{\preccurlyeq }\)) If \(y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) and x ≺_Ψy, then x ≺_Ψ∗Ay

whereas ÷_N and ÷_R satisfy:

• (SPPres\(^{\div }_{\preccurlyeq }\)) If \(y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\) and x ≺_Ψy, then x ≺_Ψ÷¬Ay

We divide the proof into two main cases:

• (1) Assume x ∈ or y ∈ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\). By \((\text {KM}^{\ast }_{\preccurlyeq })\), it follows that \(\min \limits (\preccurlyeq _{\Psi \ast _{i} A}, W)=\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\). By \((\mathrm {C}{1,2}^{\scriptscriptstyle \div }_{\scriptscriptstyle \preccurlyeq })\), we have \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])= \min \limits (\preccurlyeq _{\Psi \div _{j} \neg A}, [\![{A}]\!])\). Finally, again by \((\text {KM}^{\ast }_{\preccurlyeq })\), we recover the result that \( \min \limits (\preccurlyeq _{\Psi \div _{j} \neg A}, [\![{A}]\!])=\min \limits (\preccurlyeq _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}, W)\). These 3 equalities then yield \(\min \limits (\preccurlyeq _{\Psi \ast _{i} A}, W)=\min \limits (\preccurlyeq _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}, W)\). By \((\text {KM}^{\ast }_{\preccurlyeq })\), again, we also have \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])=\min \limits (\preccurlyeq _{\Psi \ast _{i} A}, W)\). Hence:

  $$ \min(\preccurlyeq_{\Psi}, [\![{A}]\!])=\min(\preccurlyeq_{\Psi\ast_{i} A}, W)= \min(\preccurlyeq_{({\Psi}\div_{j} \neg A)\ast_{\mathrm{N}} A}, W) $$

  With this in hand: \(\rho _{\Psi \ast _{i} A}({x},{y}) = \rho _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}({x},{y})=1\), if x ∈ and y∉ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), \(\rho _{\Psi \ast _{i} A}({x},{y}) = \rho _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}({x},{y})=0\), if x,y ∈ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), and \(\rho _{\Psi \ast _{i} A}({x},{y}) = \rho _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}({x},{y})=-1\), if x∉ and y ∈ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\).

• (2) Assume x,y∉ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\).

  • (a) Assume x ∈ or y ∈ \(\min \limits (\preccurlyeq _{\Psi }, W)\).

    • (i) Assume \(x,y\in \min \limits (\preccurlyeq _{\Psi }, W)\). Then ρ_Ψ(x,y) = 0. Since x,y∉ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), we must also have x,y ∈ [ [¬A] ] and hence ρ_A(x,y) = 0. By \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), it then follows that we have \(\rho _{\Psi \ast _{i} A}({x},{y})=\rho _{({\Psi } \div _{j} \neg A) \ast _{\mathrm {N}} A}({x},{y})=0\).

    • (ii) Assume that x ∈ and y∉ \(\min \limits (\preccurlyeq _{\Psi }, W)\) (the remaining case is analogous). Then ρ_Ψ(x,y) = 1. Furthermore, since \(y\notin \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), by (SPPres\(^{\ast }_{\preccurlyeq }\)) and (SPPres\(^{\div }_{\preccurlyeq }\)), \(\rho _{\Psi \ast _{i} A}({x},{y}) = \rho _{\Psi \div _{j} \neg A}({x},{y}) =1\). By reapplying (SPPres\(^{\ast }_{\preccurlyeq }\)) again, we then obtain \(\rho _{({\Psi } \div _{j} \neg A) \ast _{\mathrm {N}} A}({x},{y})=1\) and we are done.

  • (b) Assume x∉ and y∉ \(\min \limits (\preccurlyeq _{\Psi }, W)\). We know from the definitions of these operators that, for x,y∉ \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), we have \(\rho _{\Psi \div _{j} \neg A}({x},{y}) = \rho _{\Psi \ast _{i} A}({x},{y})\). Therefore \(\rho _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}({x},{y})=\rho _{({\Psi }\ast _{i} A)\ast _{\mathrm {N}} A}({x},{y})\). But, since, by \((\text {KM}^{\ast }_{\preccurlyeq })\), \(\rho _{({\Psi }\ast _{i} A)\ast _{\mathrm {N}} A}({x},{y})\subseteq [\![{A}]\!]\), it follows, by the definition of ∗_N, that \(\rho _{({\Psi }\ast _{i} A)\ast _{\mathrm {N}} A}({x},{y}) = \rho _{\Psi \ast _{i} A}({x},{y})\). We can therefore conclude that \(\rho _{\Psi \ast _{i} A}({x},{y})=\rho _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}({x},{y})\), as required.

□

Proposition 22

If ∗ is defined from ÷_P via \((\mathrm {iLIRC_{\preccurlyeq }})\) then ∗≠∗_L.

Proof

We provide a countermodel in Fig. 7. □

Countermodel establishing Proposition 22

Full size image

Proposition 23

If 〈i,j〉∈{〈L,P〉,〈N,N〉,〈R,R〉} then ∗_i and ÷_j jointly satisfy \((\mathrm {iLI\ast _{\preccurlyeq }})\).

Proof

Let 〈i,j〉∈{〈L,P〉,〈N,N〉,〈R,R〉}. We need to show that \(\rho _{\Psi \ast _{i} A}({x},{y}) = \rho _{({\Psi }\div _{j} \neg A)\ast _{i} A}({x},{y})\).

Regarding the case in which 〈i,j〉 = 〈L,P〉: Assume ρ_A(x,y) = 1. Then, since it is a property of lexicographic revision that, if ρ_A(x,y) = 1, then \(\rho _{\Psi \ast _{\mathrm {L}} A}({x},{y})=1\), it follows that \(\rho _{\Psi \ast _{\mathrm {L}} A}({x},{y}) = \rho _{({\Psi }\div _{\mathrm {P}} \neg A)\ast _{\mathrm {L}} A}({x},{y})=1\). Assume ρ_A(x,y) = 0. Then, by \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\), \(\rho _{\Psi \ast _{\mathrm {L}} A}({x},{y}) = \rho _{({\Psi }\div _{\mathrm {P}} \neg A)\ast _{\mathrm {L}} A}({x},{y})=\rho _{\Psi }({x},{y})\).

Regarding the case in which 〈i,j〉∈{〈N,N〉,〈R,R〉}, we divide the proof into two main cases:

• (1) Assume x ∈ or y ∈ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\). The proof proceeds as in the corresponding case in the proof of Proposition 21 above.

• (2) Assume x,y∉ \(\min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\).

  • (a) Assume x ∈ or y ∈ \(\min \limits (\preccurlyeq _{\Psi }, W)\). Again, the proof proceeds as in the corresponding case in the proof of Proposition 21.

  • (b) Assume x∉ and y∉ \(\min \limits (\preccurlyeq _{\Psi }, W)\). We know from the definitions of these operators that, for x,y∉ \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi }, [\![{A}]\!])\), we have \(\rho _{\Psi \div _{j} \neg A}({x},{y}) = \rho _{\Psi \ast _{i} A}({x},{y})\). Since ∗_R and ∗_N both satisfy \((\text {KM}^{\ast }_{\preccurlyeq })\) and \((\text {IIA}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and the latter tell us that ρ_Ψ(x,y) and ρ_A(x,y) jointly determine ρ_Ψ∗A(x,y), it follows that \(\rho _{({\Psi }\div _{j} \neg A)\ast _{i} A}({x},{y})=\rho _{({\Psi }\ast _{i} A)\ast _{i} A}({x},{y})\). For the final step, we note that ∗_R and ∗_N both satisfy:

  • \((\text {Idem}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) ρ_(Ψ∗A)∗A(x,y) = ρ_Ψ∗A(x,y)

  Indeed, in the presence of \((\text {KM}^{\ast }_{\preccurlyeq })\), \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) tells us that the posterior relative rank ρ_Ψ∗A(x,y) of a pair 〈x,y〉 of worlds is determined by the prior relative rank ρ_Ψ(x,y), with the nature of this mapping depending, for non-minimal A-worlds, on the relevant proposition and pair of worlds. \((\text {Idem}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) is then the requirement that, for any given value of ρ_A(x,y), if the row for value v points to value w, then the row for w also points to w. That this condition holds for ∗_R and ∗_N can be seen from Table 2. (Note, in passing, that \((\text {Idem}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) can more generally be shown to be derivable from \((\text {KM}^{\ast }_{\preccurlyeq })\), \((\text {IIAP}^{\scriptscriptstyle \ast }_{\scriptscriptstyle \preccurlyeq })\) and \((\mathrm {C}{1,2}^{\ast }_{\scriptscriptstyle \preccurlyeq })\)–\((\mathrm {C}{4}^{\ast }_{\scriptscriptstyle \preccurlyeq })\) and is hence also satisfied by ∗_L.)

  Hence \(\rho _{({\Psi }\ast _{i} A)\ast _{i} A}({x},{y}) = \rho _{\Psi \ast _{i} A}({x},{y})\) and we can conclude that \(\rho _{\Psi \ast _{i} A}({x},{y})=\rho _{({\Psi }\div _{j} \neg A)\ast _{\mathrm {N}} A}({x},{y})\), as required.

□

Proposition 24

Let 〈i,j〉∈{〈L,P〉,〈N,N〉,〈R,R〉}. Then if ÷ defined from ∗_i by \(\preccurlyeq _{\Psi \div A} = {\preccurlyeq }_{\Psi }{\oplus _{\mathrm {TQ2}}}{\preccurlyeq }_{{\Psi }{{\ast }_{i}}\neg A}\), then ÷ = ÷_j.

Proof

The result is obvious from the definitions of the various elementary contraction operators in Definition 10 and elementary revision operators in Definition 2. ⊕_TQ2 combination of \(\preccurlyeq _{\Psi }\) and \(\preccurlyeq _{\Psi \ast _{i} \neg A}\) yields the result that the minimal equivalence class under \(\preccurlyeq _{\Psi \div A}\), is given by \(\min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi \ast _{i} \neg A},W)\), which is equal to \( \min \limits (\preccurlyeq _{\Psi \div _{j} \neg A},W)\). Regarding the subsequent equivalence classes, ⊕_TQ2 combination gives us the result that, for x∉ and \(y \notin \min \limits (\preccurlyeq _{\Psi }, W)\cup \min \limits (\preccurlyeq _{\Psi \ast _{i} \neg A},W)\), \(\rho _{\Psi \div A}({x},{y})=\rho _{\Psi \ast _{i} \neg A}({x},{y})\). But as we noted in Section 5.1, for the same x and y, we have \(\rho _{\Psi \div _{j} A}({x},{y})=\rho _{\Psi \ast _{i} \neg A}({x},{y})\) and so \(\rho _{\Psi \div A}({x},{y})=\rho _{\Psi \div _{j} A}({x},{y})\). □

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Reprints and permissions