Iterated Belief Contraction from First Principles

1 Background

The theory of belief change purports to model how a current theory or body of beliefs, K, can be rationally modified in order to accommodate a new observation x. An observation, such as x, is represented as a sentence in a propositional language L, and a theory, such as K, is assumed to be a set of sentences in L, closed under a supra-classical consequence operation, Cn. Since the new piece of information x may contravene some current beliefs in K, chances are, some beliefs in K will be discarded before x is eased into it. Accordingly, three forms of belief change are recognised in the belief change framework:

1. CONTRACTION: Kx is the result of discarding some unwanted information x from the theory K
2. EXPANSION: K+ x is the result of simple-mindedly incorporating some information x into the theory K, and
3. REVISION: K∗ x is the result of incorporating some information x into the theory K in a manner so as to avoid internal contradiction in K∗ x.

The intuitive connection among these operators is captured by the following two identities named, respectively, after Isaac Levi and William Harper:

LEVI IDENTITY: K∗

x = (K¬x)+x , and

HARPER IDENTITY: K-

A belief change (revision, contraction and expansion) operation is AGM-RATIONAL if it satisfies the corresponding set of AGM rationality postulates. The three sets of postulates, along with motivation and interpretation for them, may be found in [G¨ardenfors, 1988]. It is well known that a revision operator constructed from an AGM-rational contraction operation via the Levi Identity is AGM rational; and conversely AGM-rational revision operations can be used to construct AGM-rational contraction operations via the Harper Identity. For convenience we reproduce the AGM postulates for contraction below.

The expansion operation is very easily constructed: K+ x = Cn(K ∪ {x}). Contraction and Revision operations are relatively more sophisticated operations since they deal with choice.

It is easily noticed that the AGM postulates of contraction deal with "one-shot" belief contraction. The only constraint of interest on iterated contraction that they impose is:

which is not really much of a constraint. 1 In particular, postulates (7-) and (8-) impose very little. Consider the following example to see how ineffective the AGM postulates are in dealing with sequential contraction.

Example 1 Suppose I believe on independent grounds that both a: Argentina will qualify for the FIFA world-cup final and b: Brazil will qualify for the FIFA world-cup final. 2 Thus my knowledge corpus is K = Cn(a, b), whereby a ∨ b ∈ K.

Since I believe a and b on independent grounds, arguably Ka = Cn(b) and Kb = Cn(a). Moreover, since my belief in a∨b is assumed to have no independent standing, we would expect a "correct" belief contraction operation to behave in a way such that both a ∨ b ̸∈ (Ka )-b and a ∨ b ̸∈ (Kb )-a .

This however is not mandated by the AGM postulates. We can plausibly argue that Ka∧b = Cn(b) given Brazil's past record.This will satisfy all the eight postulates of contraction. 3 However, since b ∈ Ka , the postulates do not constrain the content of (Ka )-b in any interesting way at all. In particular, the postulates cannot insist on the absence of a∨b in the resultant belief corpus, contrary to our intuition.

Not many researchers have examined iterated belief contraction in a principled way, an exception being Hans Rott who has advocated the following principle [Rott, 2001](p.221):

1 If ∅ ⊢ y, then by RECOVERY (Kx )-y = Kx . We assume throughout the paper that y is a removable belief, i.e., ̸⊢ y.

2 Both Argentina and Brazil had qualified to play in the quartersfinals by the time this paper was being written. Italy played France in the final and won the 2006-world-cup.

3 Readers acquainted with the semantics involved can verify it by considering the following plausibility rank-order over the worlds: ab ❁ ab ❁ ab ❁ ab where ab is the most preferred world.

Qualified Insertion

This is indeed an appealing suggestion. Its first part is simply Vacuity Specialised, justified by the AGM rationality postulates. As to the second part of this principle, since both x and y are individually removed fromK sequentially, it stands to reason that when the second contraction is non-vacuous, the result should consist of the beliefs that resist removal in individual contractions of K by x and y.

Despite the intuitive plausibility of Qualified Insertion, its inadequacy is established by the Example 2 below.

Example 2 Consider again the scenario in Example 1. We know that b ∈ Ka . In accordance with Qualified Insertion, then, (Ka )-b = Ka ∩ Kb . Moreover, a ∨ b ∈ Ka and a∨b ∈ Kb whereby a∨b ∈ Ka ∩Kb . Hence a∨b ∈ (Ka )-b . However, since a and b are the only reasons for a ∨ b to be in the knowledge corpus, a ∨ b should not be in (Ka )-b .

We find that Qualified Insertion, though intuitive, fails to offer an acceptable account of Iterated Belief Contraction. We take this to be the starting point of this paper. In the next section we analyse this principle to arrive at what we consider to be a pivotal principle of iterated belief contraction.

2 Qualified Insertion - Qualified

We break Qualified Insertion into two sub-principles for convenience in referring to them as follows: 4

Vacuity Specialised If y ̸∈ Kx , then (Kx )-y = Kx .

Clearly, Vacuity Specialised is not controversial, and our examination in Example 2 indicates that Insertion is the culprit. Before we claim what is wrong with Insertion, we digress to another well known result [G¨ardenfors, 1988](p.65):

Factoring Either

Given the naming of this principle, it is only appropriate that we refer to the three "values" of Kx∧y as the three factors, here as well as in other variants of this principle below. Noting the logical equivalence between y and (x ∨ y) ∧ (x → y), and making appropriate substitutions in FACTORING we get:

Factoring 2 Either

From INSERTION and FACTORING 2, in turn, follows the following principle:

Factored Insertion If y ∈ Kx , then either

4 Our nomenclature is a bit inaccurate - Rott refers to the consequent of the second item as Insertion.

1. (Kx )-y = Kx ∩Kx∨y, or
2. (Kx )-y = Kx ∩Kx→y or
3. (Kx )-y = Kx ∩Kx∨y ∩ Kx→y .

It is our view that FACTORED INSERTION together with VACUITY SPECIALISED jointly constitute a central principle for iterated belief contraction. Before arguing our case, we make the following observation:

Observation 1 INSERTION implies, but is not implied by, FACTORED INSERTION, in presence of FACTORING 2.

The import of this observation may not be immediately obvious. How is it that FACTORED INSERTION fails to imply INSERTION in presence of FACTORING 2? The important point here is which "factor" kicks in when. Let's continue with our FIFA example.

Example 3 Let us model the scenario in Example 2 as follows. Let the truth vectors 11, 01, 10, 00 represent the four worlds over the atoms {a, b} (thus 10 is the interpretation that assigns 1 to a and 0 to b), and 11 ❁ 01 ❁ 10 ❁ 00 where α ❁ β means α is strictly preferred to β. Under this modelling, min([¬a]) = min(01, 00) = 01 whereby [Ka ] = {11, 01}; thus Ka = Cn(b). Similarly, Kb = Cn(a). More importantly, [Ka→b ] = {11, 10} whereby Ka→b = Cn(a) = Kb , and [Ka∨b] = {11, 00} whereby Ka∨b = Cn(a ↔ b). Note that Since Kb = Ka→b , FACTORING 2 is satisfied. 5 Similarly, our intuitive expectation, that (Ka )-b = Cn(true) is in accordance with FACTORED INSERTION since Ka ∩Ka∨b ∩ Ka→b = Cn(b) ∩ Cn(a ↔ b) ∩ Cn(a) = Cn(true). 6 However, since a ∨ b is in Ka ∩Kb but not in Cn(true), INSERTION is not satisfied. INSERTION is not satisfied because, while the "third factor" kicked in to satisfy FACTORED INSERTION, the "second factor" kicked in to satisfy FACTORING 2.

This example highlights an important point, namely, apart from factorising iterated contraction as in FACTORED INSERTION, we should also examine the "trigger conditions" for these factors. Towards this end, we start with FACTORING, and provide the following result.

Theorem 1 7 Given belief set K, sentences x and y and an AGM-rational belief contraction operation -,

1. If y ∈ Kx∧y then Kx∧y = Kx
2. If x ∈ Kx∧y then Kx∧y = Ky
3. If x ̸∈ Kx∧y and y ̸∈ Kx∧y then Kx∧y = Kx ∩Ky .

Proof Sketch: The third claim easily follows from the AGM postulates (7-) and (8-). The first two claims are symmetric; so it is sufficient to show only claim (1). We use the standard properties of the epistemic entrenchment relation ≤, and the well known construction of contraction via it, namely, y ∈ Kx iff both y ∈ K and either that ⊢ y or x < x ∨ y. We use x < y and x ∼ y as short-hand for (x ≤ y)∧(y ̸≤ x) and (x ≤ y) ∧ (y ≤ x) respectively. We will use ≡ for logical equivalence. From the assumption y ∈ Kx∧y, in the principal case it follows that x ∧ y < (x ∧ y) ∨ y ≡ y. From this it follows that (x ∧ y) ∼ x < y. Now consider some arbitrary sentence z. It will be in Kx just in case (in the principal case) x < x ∨ z. Similarly, it will be in Kx∧y just in case (in the principal case) x ∧ y < (x ∧ y) ∨ z. It is sufficient to show that these two conditions are equivalent. (i) Suppose x < x ∨ z. We know x < y where by x < y ∨ z. Since (x ∧ y) ∨ z ≡ (x ∨ z) ∧ (y ∨ z) and x ∼ x ∧ y it follows x ∧ y < (x ∧ y) ∨ z. (ii) Suppose x ∧ y < (x ∧ y) ∨ z ≡ (x ∨ z) ∧ (y ∨ z). It trivially follows that x < x ∨ z.

5 That's a bit too quick. We need also to verify for other values of x and y. But that's not the point we are trying to make here.

6 This intuition is, of course, debatable. One might say that since Brazil has a better track record than Argentina, we should still have a → b ∈ (Ka )-b . That is fine. Ka ∩Ka∨b = Cn(b) ∩ Cn(a ↔ b) = Cn(a → b), again is in accord with FACTORED INSERTION.

7 Note that the first two items are equivalent. We nonetheless treat them separately since they eventually lead to distinct principles in PRINCIPLED FACTORED INSERTION below.

Theorem 1 tells us how to reduce contraction by a conjunction to known contractions by the individual conjuncts. An immediate corollary of it is applicable to the principle FACTORING 2.

Corollary 1 Given belief set K, sentences x and y and an AGM-rational belief contraction operation -,

1. If x→ y ∈ Ky thenKy = Kx∨y
2. If x∨ y ∈ Ky thenKy = Kx→y
3. If both x→ y ̸∈ Ky and x ∨ y ̸∈ Ky then Ky = Kx∨y ∩ Kx→y .

Now, our goal was to examine the conditions that trigger different factors of FACTORED INSERTION. If we qualify each item in FACTORED INSERTION by the corresponding condition in Corollary 1 as is:

Naive Factored Insertion Given y ∈ Kx ,

1. If x → y ∈ Ky , then (Kx )-y = Kx ∩Kx∨y
2. If x ∨ y ∈ Ky , then (Kx )-y = Kx ∩Kx→y
3. If both x → y ̸∈ Ky and x ∨ y ̸∈ Ky , then (Kx )-y = Kx ∩Kx∨y ∩ Kx→y .

then, we will be no better off, since it will lead us to all the problems associated with INSERTION:

Observation 2 NAIVE FACTORED INSERTION is logically equivalent to INSERTION.

However, we notice that in Theorem 1, in reducing contraction by a conjunction to contraction by individual conjuncts, the conditions in question perform a "check" on the result of the contraction by the conjunction. In FACTORED INSERTION, the intention is to reduce iterated contraction to oneshot contractions. Accordingly we would expect the appropriate conditions to perform checks on the result of the sequential contraction, not on the result of the one-shot contractions. Accordingly we suggest the following principle instead.

Principled Factored Insertion Given y ∈ Kx ,

1. If x ∨ y ∈ (Kx )-y , then (Kx )-y = Kx ∩Kx→y
2. If both x→ y ̸∈ (Kx )-y and x∨y ̸∈ (Kx )-y , then (Kx )-y = Kx ∩Kx∨y ∩ Kx→y

Let us revisit our favourite FIFA example again.

Example 4 Let the scenario be as in previous examples. We are trying to construct (Ka )-b . We know from Example 1 that both b ∈ Ka and a ∨ b ̸∈ (Ka )-b . Since b ∈ Ka , we consider PRINCIPLED FACTORED INSERTION. Since we already know that a ∨ b ̸∈ (Ka )-b , the second case does not apply. So the result of this iterated contraction will crucially depend on whether or not a → b is in (Ka )-b . If a → b ∈ (Ka )-b , then the first case will apply, and we will get (Ka )-b = Ka ∩ Ka∨b = Cn(b) ∩ Cn(a ↔ b) = Cn(a → b). Else, the third case will apply, and we will get Ka ∩ Ka∨b ∩ Ka→b = Cn(b) ∩ Cn(a ↔ b) ∩ Cn(a) = Cn(true).

Note that it is the "slight" difference in the conditions attached to different factors that made the difference. We assumed that a ∈ Kb , hence a ∨ b ∈ Kb . If we used NAIVE FACTORED INSERTION, then the the second factor would have kicked in. But since, by assumption, a ∨ b ̸∈ (Ka )-b , in case of PRINCIPLED FACTORED INSERTION, it will be a factor other than the second one that kicks in, making all the difference.

3 Some Properties of Principled Iterated Contraction

We have noticed that PRINCIPLED FACTORED INSERTION performs reasonably well in our toy example. In this, short, section we examine some properties that this principle entails.

By a PRINCIPLED ITERATED CONTRACTION OPERATION we understand any AGM-rational contraction operation that also satisfies PRINCIPLED FACTORED INSERTION. It is understood that such contraction operations will automatically satisfy VACUITY SPECIALISED since, being AGMrational, they satisfy VACUITY. We assume in the following observations that the contraction operation - is a PRINCIPLED ITERATED CONTRACTION OPERATION.

Observation 3 Given that y ∈ Kx , if x ⊢ y then (Kx )-y = Kx ∩Ky .

The following immediate corollary to Observation 3 indicates that things are as they should be.

Observation 4 Given that y ∈ Kx , if ¬x ⊢ y then (Kx )-y = Kx ∩Ky .

From Observation 4 we straightforwardly get the following corollary that lends PRINCIPLED ITERATED CONTRACTION further credence:

Observations 3 and 4 are simple, yet quite interesting. On the first count, they identify conditions under which INSERTION holds in general, i.e., (Kx )-y is identified with Kx ∩Ky . On the second count, these two properties appear to be the analogues of the first two of the four well known postulates advocated by Darwiche and Pearl [Darwiche and Pearl, 1997] for iterated belief revision:

Postulates DP1 and DP2 indicate what happens in the case of iterated revision when the two pieces of evidence x and y are logically related. The result is given purely in terms of K∗ y . Similarly, Observations 3 and 4 tell us what happens when the two beliefs to be removed, x and y are logically related. The result is provided purely in terms of Kx and Ky .

Another interesting fact about these two simple observations is that they record properties of LEXICOGRAPHIC STATE CONTRACTION introduced in [Nayak et al., 2003]. This suggests a deeper connection between PRINCIPLED ITERATED CONTRACTION and LEXICOGRAPHIC STATE CONTRACTION. We take up this issue in the next section.

4 Lexicographic Contraction

LEXICOGRAPHIC CONTRACTION is the contractioncounterpart of of LEXICOGRAPHIC REVISION introduced in [Nayak, 1994; Nayak et al., 2003]. Like most approaches to iterated belief change, this approach has been semantically motivated. In this section we revisit LEXICOGRAPHIC REVISION and LEXICOGRAPHIC CONTRACTION as a prelude to showing that the iterated belief contraction operation generated by Lexicographic Contraction must be a PRINCIPLED ITERATED CONTRACTION operation.

4.1 Lexicographic State Revision

The lexicographic approach to iterated belief revision is captured by a particular account of state revision [Nayak et al., 2003]. The semantics of Lexicographic Revision is given in terms of an evolving belief state, where a belief state is represented as a plausibility ordering over the interpretations generated by the background language.

Definition 1 Let Ω be the set of possible worlds (interpretations) of the background language L, and ⊑ a total preorder (a connected, transitive and reflexive relation) over Ω. For any set Σ ⊆ Ω and world ω ∈ Ω we will say ω is a ⊑- minimal member of Σ if and only if both ω ∈ Σ and ω ⊑ ω′ for all ω′ ∈ Σ, and denote it as ω ∈ min⊑(Σ). We will often drop the parentheses for readability.

By ω1 ⊑ ω2 we will understand that ω2 is not more plausible than ω1. The expression ω1 ≡ ω2 will be used as a shorthand for (ω1 ⊑ ω2 and ω2 ⊑ ω1). The symbol ❁ will denote the strict part of ⊑. For any set S ⊆ L we will denote by [S] the set {ω ∈ Ω | ω |= s for every s ∈ S }. For readability, we will abbreviate [{s}] to [s]. Intuitively, the preorder ⊑ will be the semantic analogue of the revision operation ∗, and will represent the belief state of an agent. We will say that K⊑ is the belief set associated with the preorder ⊑. It is defined as the set of sentences satisfied by the ⊑-minimal worlds, i.e.

An inconsistent belief state is represented by an empty relation ⊑⊥: for every pair ω, ω′ ∈ Ω, ω ̸⊑⊥ ω′ . Note that this violates connectedness, and hence the plausibility relation ⊑ is, strictly speaking, no longer a total preorder. However, this is a special case, and merits special treatment.

A modified Grove-Construction [Grove, 1988] is used to construct the revision from a given plausibility relation:

Definition 2 (⊑ to *)

The plausibility ordering (belief state) ⊑, in light of new evidence e, is stipulated to evolve to the new ordering ⊑varoaste via the use of a state revision operator varoast as follows.

1. SPECIAL CASES:
2. (a) If [e] = ∅ then, and only then, ⊑varoaste =⊑⊥
3. (b) Else, if ⊑=⊑⊥, then ω1 ⊑varoaste ω2 iff either ω1 |= e or ω2 |= ¬e.
4. GENERAL CASE: Given nonempty prior (⋢=⊑⊥) and satisfiable evidence([e] ̸= ∅),
5. (a) If ω |= e and ω′ |= e then ω ⊑varoaste ω′ iff ω ⊑ ω′
6. (b) If ω |= ¬e and ω′ |= ¬e then ω ⊑varoaste ω′ iff ω ⊑ ω′
7. (c) If ω |= e and ω′ |= ¬e then ω ❁ varoaste ω′

4.2 Lexicographic Contraction

As in the case of lexicographic revision, we take it that the pre-contraction plausibility ordering (belief state) ⊑, after suspension of belief x, evolves to the new ordering ⊑⊖x via the use of a state contraction operator ⊖ as follows.

Definition 3 (Lexicographic State Contraction⊖)

1. SPECIAL CASES:
2. (a) (⊑⊤)⊖x =⊑⊤ for all x.
3. (b) (⊑⊥)⊖x =⊑⊤ for all x.
4. GENERAL CASE: Given non-trivial pre-contraction state ⊑, ⊑⊥̸=⋢=⊑⊤,
5. (a) If ω |= x and ω′ |= x then ω ⊑⊖x ω′ iff ω ⊑ ω′
6. (b) If ω |= ¬x and ω′ |= ¬x then ω ⊑⊖x ω′ iff ω ⊑ ω′
7. (c) Let χ ∈ {x, ¬x} and χ be its complement. If ω |= χ and ω′ |= χ, then ω ⊑⊖x ω′ iff for every chain ω0 ❁ ω1 ❁ · · · ❁ ω in [χ] of length n, there exists a chain ω′0 ❁ ω′1 ❁ · · · ❁ ω′ of length n in [χ].

Corresponding conditions 2(a) and 2(b) in LEXICOGRAPHIC REVISION and LEXICOGRAPHIC CONTRACTION are more or less identical: irrespective of whether x is a piece of evidence to be incorporated into the current knowledge corpus (or a belief to be suspended) the prior ordering between any two worlds, ω and ω′ that both satisfy x (or both invalidate x), should not be disturbed in the process. These conditions are also accepted in the Darwiche-Pearl approach to belief revision. Condition 2(c) in LEXICOGRAPHIC CONTRACTION states the effect of a contraction by x on two worlds, one of which satisfies x and the other does not: the ranking of all worlds in [¬x] are simultaneously shifted so that the best (minimal) worlds in [¬x] attain the same rank as the ⊑-minimal worlds (i.e., the worlds in [K]). This is reminiscent of Spohn's account of belief contraction via Ordinal Conditional Functions [Spohn, 1988], and we take it that this is the relational analogue of Spohn's account of iterated belief contraction. This definition of ⊖ captures in a simple way a generalised version of the Harper Identity provided in [Nayak et al., 2006]. Figure 1 provides a simple illustration of lexicographic state contraction. The "state space" Ω is partitioned by the pre-contraction plausibility preorder ⊑ into eight "cells", 0, 1, . . . 7, the worlds in i being preferable to those in i + 1, for 0 ≤ i ≤ 6, while the worlds in the same cell are equally preferable. These cells are further partitioned by [x] and [¬x]: the cells X0, . . . , X7 constituting [x], and the cells Y0, . . . , Y4 constituting [¬x]. After the contraction by x, the "best" worlds in [x] as well as the "best" worlds in[¬x] are accorded the most preferred status in the post-contraction state; the second most preferred worlds consisting of the precontraction "next best" worlds from [x] and [¬x], and so on.

Earlier we indicated that there is a close connection between Lexicographic Contraction and Principled Iterated Contraction. For this purpose we need to generate a contraction operation from a given plausibility preorder in order to make this connection. We use a slight variation of the standard transformation.

Definition 4 (⊑ to -)

Our last result (Theorem 2) below shows that if the two sequential contractions in (Kx )-y are constructed from the belief states ⊑ and ⊑⊖x respectively, where K is the belief set K⊑ associated with the belief state ⊑, then PRINCIPLED FACTORED INSERTION is satisfied.

Theorem 2 Let ⊑ be the original belief state, K its associated belief set K⊑, and ⊖ the lexicographic state contraction operation. If we define, for every sentence α and β,

1. Kα using the contraction operation -⊑ generated from ⊑ via Definition 4, and
2. (Kα )-β , the result of removing β from Kα , using the contraction operation -(⊑⊖α) generated from ⊑⊖α via Definition 4

then the (dynamic) contraction operation - thus defined is a PRINCIPLED ITERATED CONTRACTION OPERATION.

Proof Sketch: Note that, given a preorder ⊑ and sentence x, we have ⊑⊖x , denoted ⊑′ below for readability, is a total preorder. Hence the operation -(⊑⊖x), defined as required, is an AGM-rational belief contraction operation. A point to be noted is that the two contraction operations in an expression of the form (Kx )-y are technically different operations, the first corresponding to - := -⊑ and the second to -′ := -⊑′ , and so it should more accurately be represented as (Kx )-′ y . 8

We need to show that the operation pair (-, -′ ) satisfies the property PRINCIPLED FACTORED INSERTION. It is easily shown that in presence of the condition y ∈ Kx , the conditions

1. x ∨ y ∈ (Kx )-′ y amounts to min⊑′[¬y] ⊆ [x], and
2. the two conditions x → y ̸∈ (Kx )-′ y and x ∨ y ̸∈ (Kx )-′ y jointly amount to ∃ω, ω′ ∈ min⊑′[¬y] s.t. ω ∈ [x] and ω′ ∈ [¬x].

Note that these three cases are mutually exclusive, and it suffices in these cases to show respectively that

The information contained in (1), (2) and (3), together with the definition of the operation ⊖, in particular, that the relative ordering of worlds inside [x] (respectively [¬x]) is not disturbed, help to carry out the proofs of (A), (B) and (C), correspondingly. For instance, the fact from (1), that min⊑′ [¬y] ⊆ [¬x] and the condition that for ω, ω′ ∈ [¬x], ω ⊑′ ω′ iff ω ⊑ ω′ drive the proof of (A).

A point to note that the condition (2c) in Definition 3 is not used in the proof.

A natural question to raise at this point is whether the property PRINCIPLED FACTORED INSERTION, together with the AGM postulates of contraction, fully characterises Lexicographic Contraction. It is easily verified that it does not. Given y ∈ Kx , if we equate (Kx )-y with Kx ∩Kx∨y when ̸⊢ x ∨ y, and with Kx ∩ Kx∨y when ̸⊢ x → y otherwise, it will satisfy PRINCIPLED FACTORED INSERTION, and yet a non-Lexicographic state contraction operation, PRIORITY, 9 will lead to such contraction behaviour.

5 Conclusion

Our aim was to examine iterated belief contraction in a principled way. We started with Rott's QUALIFIED INSERTION that, upon examination, was found to be wanting. We then showed that a judicious combination of QUALIFIED INSERTION with FACTORING leads to what we consider to be a pivotal principle of iterated belief change. We have argued that while Lexicographic State Contraction satisfies it, this principle is too weak to completely characterise a Lexicographic Contraction. We hope to completely characterise Lexicographic Contraction in our future work.

8 See the dynamics of revision operations in [Nayak et al., 2003] for motivation.

9 See [Nayak et al., 2006]. This can be pictured as a variation of Figure 1 where in the post-contraction state, Y0, . . . , Y4 get the ranks 0, . . . , 4; X0 retains rank 0, and X1, . . . ,X7 get ranks 5, . . . , 11. That is, every non-best world in [x] is dis-preferred to every world in [¬x], subject to other relevant conditions.