Considerations on a Similarity-Based Approach to Beleif Change

1 Introduction

A belief set of facts, assertions, etc. will of course change over time with the addition or de~ tion of information. In this paper I am concerned with a foundational character­ isation of belief contraction and revision. The questions addressed are familiar: given a belief set and a sentence to be added to the belief set, what can we say about the revised belief set? And: given a belief set and a sentence to be contracted, again, what can be said about the re­ sult? For reasons that will become apparent, I focus on belief contraction rather than the revision of beliefs.

Two assumptions are made in addressing these ques­ tions. First, that a change is successful, so that after a sentence is contracted from a belief set, that sentence is no longer believed in the resulting belief set(s). Sec­ ond, I assume that belief change is founded on a notion of similarity among belief sets. Thus if a sentence a is to be contracted from (added to) belief set K, then the result will be the belief set most similar to K in which a is not believed (is believed). This reduces the notion of belief change to that of similarity between belief sets . The focus here is on an abstract characterisation of be­ liefs, so we will be concerned with syntax-independent characterisations of change functions .

Clearly, there is not a great deal that can be said in general about similarity between belief sets. In the ap­ proach presented here, it is assumed that every belief set K has associated with it a binary metric of relative simi­ larity to K, and that this metric is a total preorder. That is, if ~K is the relative similarity metric associated with K then ~K is reflexive, transitive and connected; as well K is the minimum element in the order. I assume further that for every sentence a there is a ~K-least belief set or set of belief sets in which a is believed. Given such a similarity order, contraction and revision functions can be defined. Subsequent to this modelling, corresponding postulates validated by these functions are determined.

The approach is intended to provide a minimal notion of belief change, in that for the postulates that obtain, all should arguably hold for any syntax-independent, suc­ cessful change functions. Consequently, the approach is more basic than, and so subsumes, the AGM approach to belief change. However, as shown at the end of Section 3, the approach does not subsume the Katsuno-Mendelzon approach to belief update. A benefit of the present ap­ proach is that it allows a very "fine-grained" investiga­ tion of principles underlying belief revision where dis­ tinct notions are, in fact , distinguished. Consequently the semantics illustrates that in the AGM approach , there are a number of distinct (albeit very basic, and perhaps beyond debate) principles composing the ap­ proach. Secondly, the approach is arguably intuitive and plausible, in that it is based on commonsense intuitions regarding belief revision and contraction. By imposing constraints on the semantic theory, additional postulates may be satisfied. Arguably, such constraints will reflect plausible intuitions concerning belief change, and so the approach will help provide insight into different belief change functions. Finally, and perhaps surprisingly, at this very basic level it proves to be the case that revision and contraction functions comprise distinct notions, with contraction being the more gen~ral. This is in contrast with the AGM approach, where revision and contraction are in a certain sense interdefinable.

One omission in this paper is that iterated revision is not addressed. The reason for this is that, at this point, our interests lie with a comparison to the AGM approach and , for the present, uniterated revision . The final section briefly considers how the notion of similarity may be used in iterated revision.

Section 2 briefly reviews the AGM approach and the Grove construction . Section 3 presents the approach, while Section 4 provides a conclusion .

2 Background

Belief sets change over time, with the addition and dele­ tion of information. In general, there is no purely logical reason for making one choice rather than another among the sentences to be retracted or kept . Hence from a logi­ cal view there may be several ways of specifying a belief change function. However , general properties of such functions can be investigated.

In the AGM approach of Alchourron, Gii.rdenfors, and Makinson [AGM85 ; Gii.r88], standards for revision and contraction functions are given by various rationality postulates. The goal is to describe belief change at the knowledge level, that is on an abstract level, independent of how beliefs are represented and manipulated. Belief states are modelled by sets of sentences closed under the logical consequence operator of some logic in some lan­ guage L , where the logic includes classical propositional logic. A belief set is a set J( of sentences which satis­ fies the constraint : If J( logically entails {3 then {3 E K J( +a is the deductive closure of J( U {a}, and is called the expansion of J( by a . !{ 1. is the inconsistent knowl­ edge base (i.e. K1. = L) . Tis the set of all belief sets.

For contraction, some beliefs are retracted but no new beliefs are added. A contraction function .:.. is a function from T x L to T satisfying the following postulates .

(I<.:.. 1) f{.:.. rjJ is a belief set ..

(I{ .:..3) If¢; tJ. K , then f{ .:..¢; = K

(I<.:._ 4) If not r ¢;, then rP tJ. f{- ¢;.

(I< .:..5) If ¢J E K , then J{ ~ (K .:..<jJ) + ¢;.

• (I< .:..6) Iff- rjJ = '!f;, then J{ .:..¢; = J{ .:..'!j;.
• (I< .:.. 7) K .:.. <P n K .:.. '!f; ~ K .:.. ( r/J A '!fJ).

(I< .:.. 8) If 1/J tJ. K .:.. ( ¢; 1\ '!f;), then J{ .:.. ( ¢; 1\ '!f;) t;;; J{ .:.. '!f;.

A revision function + is a function from T x L to T satisfying the following postulates.

(K+l) K+a is a belief set.

(I{ +2) a E J{ +a.

• (K+3) K+a ~ J{ +a.
• (I< +4) If ·a tJ. K, then f{ +a ~ f{ +a.
• (!<+5) K+a = K1. iffr ·a.
• (I< +6) If r a= {3, then J{ +a=]{ +f3.
• (!<+7) K+(a/\{3) ~ (I<+a)+f3 .
• (I< +s) If ·f3 tJ. ]{+a, then (I< +a)+ {3 ~ ]{+(a 1\ {3).

Katsuno and Mendelzon [KM92] explore a distinct no­ tion of belief change, comprising belief update and era­ sure, wherein an agent changes its beliefs in response to changes in its external environment. Our interests here centre on the AGM approach; however in Section 3.4, I briefly consider this approach.

In [Gro88] a modelling of the AG M postulates is given based on Lewis' system of spheres semantics [Lew73]. ML is the set of all maximal consistent sets of sentences of L. Intuitively, an element of ML can be thought of as corresponding to an intepretation in the language, or alternatively to a possible world. Define Ia I = {IE ML I a E I} for system of spheres M .

Definition 2.1 ([Gro88]) A set of subsets S of ML is a system of spheres centred on X where X ~ ML , if it satisfies the conditions:

• Sl S is totally ordered by ~·
• S2 X is the minimum of S under~ ·
• S3 ML E S .
• S4 If iai =!= 0 then there is a least (wrt ~) sphere c(a) such that c( a) n Ia I =!= 0 and J n Ia I =!= 0 implies c(a) ~ J for every J E S .

fs(a) is defined to pick out the least (if such there be) interpretations containing a; i.e. fs(a) = Iaine( a). The principal result is a correspondence between systems of spheres and the AGM postulates, in that , informally, for any system of spheres centred on IKI there is a corre­ sponding revision function that satisfies the AGM postu­ lates and, conversely, for any revision function satisfying the AGM postulates there is a corresponding system of spheres centred on IKI.

In the next section, we take the Grove modelling as our point of departure, essentially advocating a modelling based on a system of spheres but where belief sets replace possible worlds in the modelling.

3 Similarity Orderings on Belief Sets

Contraction of belief sets is addressed first, followed by revision. The central intuition is that in contracting a from J{ , we want to select the most similar belief set( s) to J{ in which a is not believed. (As a point of interest, the AGM approach assumes that one wants to retain as much of the information in the belief set as possible; this criterion would constitute a specific similarity measure.) A belief set ]{ has associated with it a (binary) metric ~K of relative similarity to J{, and this metric is a total preorder. As well J{ is the minimum element in the order . For every a there is a ~K-least belief set or set of belief sets in which a is believed. This last constraint is analogous to the Limit Assumption of [Lew73].

For contracting a from J{, we select the belief sets most similar to J{ in which a is not believed. Since there may be more than one such belief set, and since there is nothing to distinguish these belief sets, the contraction of a from K corresponds to this set of belief sets. This is in contrast with the AGM approach, where a contraction function has as value a single belief set .

3.1 A Modelling for Belief Change

K, K1, K2, .. . will denote belief sets. Recall that T is the set of belief sets. When we come to the revision and contraction postulates, it will be convenient to be able to talk about the belief sets in which a sentence a is believed.

Definition 3.1 KB(a) ={I< IKE T and a E K}

Definition 3.2 A similarity order model on belief sets centred on K is given by M = (K, KB, -:5.K} where

1. K E KB
2. KB ~ T and K1. E KB
3. -:5.K~ (KB x KB) where -:5.K satisfies the conditions:
4. P1 -:5.K is connected (and so reflexive). So for K1,K2 E KB, we have K1 -:5.K K2 or K2 -:5.K /{1·
5. P2 -:5.K is transitive. That is, if K1 -:5.K K2 and K2 -:5.K K3 then K1 -:5.K K3.
6. P3 K is the minimum of -:5.K. So for every K1 E KB, K -:5.K K1, andifK1 -:5.K K thenK1 = K.
7. P4 If 'rf a then there is K 1 E KB such that f{ 1 'rf a and for every K2 if K2 'r/ a then K1 -:5.K K2.

P4 states that for every sentence a there is a -:5.K-least belief set or belief sets in which a is believed. This con­ dition is analogous to (S ~ 3) of [Gro88], expressing the Limit Assumption.

3.2 Belief Change: Contraction

minC( a) is defined as the least set of belief sets in which a is consistent.

Definition 3.3 minC(a) {1<1 E T ·a and if K2 'rf ·a then K1 -:5.K K2} .

We can now define belief contraction.

Definition 3.4 The contraction of a from theory K zn M is given by:

Given this semantics we can ask what postulates are sat­ isfied. For reference I distinguish the postulates in a definition. The numbering is with reference to the cor­ responding (or most similar) AG M postulates.

Definition 3.5 The following constitute the set of KB contraction postulates.

• (I< o 1) f{ o a is a non-empty set of belief sets.
• (I< o3) If K 'rf a then K oa = {K}.
• (J< o4) If'rfathenKoanKB(a)= 0.
• (I< o 6) If I- a = (J then f{ o a = f{ o (J.

(I< o 7) If 'rf ·( a 1\ (J) then: if f{ o (J <1, KB( a) then f{ o a= f{ o (a 1\ (J) \ I<B(a).

Postulates (K o 3), (I< o 4), and (K o 6) are essentially the same as their AGM counterparts. For (K o 1) , con­ traction isn't guaranteed to result in a single belief set. This corresponds to the fact that in the semantics there may be minimal, equivalently-similar belief sets in which a isn't believed. The AGM postulate (I<.:. 2) reflects the requirement that no new beliefs occur in a contraction. In our case, the most similar belief set(s) to f{ in which a isn't believed may indeed contain new information . Consider for example a nonmonotonic belief set wherein Bird(Opus), Penguin(Opus), and ·Fly(Opus) are be­ lieved. If Penguin( Opus) is contracted, then if we have the usual default rules concerning birds and flying , we might elect to replace ·Fly( Opus) by Fly( Opus) in the resultant belief set. (I< o 3) reflects the fact that a be­ lief set is most similar to itself, and so if ·a is consistent with f{, contracting a results in the set off{. (I< o 4) as­ serts that contraction is successful while (I< o 6) reflects the fact that it is the content of a that determines the contraction and not its syntactic expression.

The AGM recovery postulate (I<.:. 5) is missing: if K I- a then f{ and K o a may be quite different and, in fact, K o a may contain information not contained in f{ (since we don't have an equivalent to (K.:. 2)). Hence ( K o a) + a may be different from f{ . It proves to be the case that equivalents to the AGM postulates (I<.:. 7) and (I< .:. 8) are consequences of the KB contraction pos­ tulates. The quite different-looking (I< o 7) and (K o 8) are employed because they readily yield a representa­ tion result. (I< o 7) is quite strong: if the contraction of (J from f{ results in at least one belief set in which ·a is consistent, then J( o a consists of just those belief sets in f{ o (a 1\ (J) in which ·a is consistent. Semanti­ cally, (I< o 8) asserts that iff{ o a and f{ o (a 1\ (J 1\ 1) are equivalently-similar then so is f{ o (a 1\ (J).

There are number of interesting results following from these postulates . We have already noted that (I<.:. 7) and (K.:. 8) are consequences of the postulates. A selec­ tion of other results are given in the following theorem.

Theorem 3.1

1. If'rf a then: K oa = K o(J iff K oa n KB((J) = 0 and K o (J n KB(a) = 0.
2. J( o (a 1\ (J) = J( o aU J( o (J or f{ o (a 1\ (J) = J( o a or f{ o (a 1\ (J) = f{ o (J.
3. IfKoa~ I<o(J then K o (a/\1) ~ Ko(fJA!) ·
4. If K o a~ K o (a/\(J) and J( o (J ~ J( o (fJA!) then f{ oa ~ J( o(a 1\i)·

The first result states that if every belief set in J( o a is consistent with ·fJ, and if every belief set in J( o (J is consistent with ·a, then f{ o a and J( o (J coincide. The second result is analogous to the "factoring" result of the AGM postulates [Gar88 , p. 57 (3.27)], but expressed in terms of sets of belief sets. The final result essentially expresses a notion of transitivity in our representation theorem; this in turn is based on the fact that if J{ o a C J( o a 1\ {3 then any minimal belief set in which ·a ~ consistent is also a minimal belief set in which ·( a 1\{3) is consistent, justifying an assertion that J{ o a ~K J( o {3.

We obtain the following results relating the KB con­ traction postulates to similarity order models.

Theorem 3.2 Let M be any similarity order model on belief sets centred on J( . If J{ o a is defined according to Definition 3.4 then the KB contraction postulat es are satisfied in M.

Theorem 3.3 Let o be a fun ction from T x L to 2 7 satisfying the J( B contract ion postulat es. Then for any fixed theory J( E T there is a similarity order model on belief sets centred on J( satisfying Definition 3.4 for all a E L.

We can determine what conditions are required to re­ cover the other AGM postulates. This can be accom­ plished in two ways. First , we can consider criteria which satisfy individual postulates . Second, we can consider a criterion that would en masse as it were, yield the AGM postulates. (A third, and most interesting, possibility is given in Theorem 3.8 in the final subsection of this section .)

In the first case, for example, one can obtain a pos­ tulate equivalent to (I<.:. 2) by restrict ing the similarity relation to belief sets strictly weaker than J{. To ob­ tain a postulate equivalent to (I< .:. 1) there are various strategies that can be employed. To obtain a single belief set from a contraction, one could define some selection function that returns a single belief set given a set of equally-similar belief sets. For example, this function could select an arbitrary belief set, or it might select a belief set on the basis of some other criterion , for exam­ ple, the overall simplicity of the belief set. Or it might determine some representative belief set, for example, the intersection of the set .

Alternately, one might decide that the semantics be refined so that the contraction function returns a sin­ gle belief set. Again, there are various alternatives. For example, one could require that the similarity order be antisymmetric, so that if I<; ~K I<j then I<j -/iK I<; unless I{; = J(i. Alternately, one could require that equally-similar belief sets be closed under intersection, so that if K; and Kj were equally-similar to I< then so would be K; nKj; the contraction then would return the minimal (in terms of containment) belief set. For either strategy, the imposition of additional constraints would not be ad hoc, but rather should reflect reasonable as­ sumptions in the semantics. So if ~K were a total order on belief sets, then one would be compelled to accept the assumption that there are no "ties" in similarity of belief sets. If one decided that contraction is closed un­ der intersections, then presumably one should be able to justify this choice. The point here is that the approach allows such distinctions to be made.

On the other hand, one obtains the full set of AGM contraction postulates by asserting that successive weak­ enings of I< are less similar to I< . This reflects a criterion of informational economy, that we retain as much as pos­ sible of our old beliefs. The use of a selection function , below, is one of a number of ways to guarantee that a single belief set results from a contraction. We obtain:

Theorem 3.4 Let M = (K, KB, ~K) be a similar­ ity order model on belief sets centred on J{ such that: KB = {I<' E T I I<' ~ I<} and if I<' ~ I<" then K" ~K I<'. Let S be any selection function on J{ o a such that S( I< o a) = nS' for some S' ~ I< o a. Then the AGM contraction postulates are satisfied in M by the fun ction S(I< o a).

Note that in the above theorem, if we allowed an arbi­ trary similarity order model, and we defined a new con­ traction operator to be n K'E(K 0 a) !{' (as suggested for example in [Neb92]) that the only new AGM postulate satisfied is ( J{ .:. 1) .

3.3 Belief Change: Revision

We turn now to belief revision. The main result is that, surprisingly, this function is not interdefinable with con­ traction , and in fact is weaker .

Given a similarity order model M , we define min(a) as the least set of belief sets in which a is true , following which we define belief revision.

Definition 3.6 min(a) = {!<1 E I<B(a ) I K1 ~K I< 2 for every J( 2 E I<B( a)}.

Definition 3. 7 The revision of theory f{ by a in M is given by: I<oa = min(a).

Revision postulates are given in the next definition, with numbering in reference to the corresponding (or most similar) AGM revision postulates.

Definition 3.8 The following constitute the set of KB revision postulates .

• (I< o 1) I< o a is a non- empty set of belief sets.
• ( f{ o 2) ]{ o a ~ KB (a).
• (Ko3) If I< 1- a then Koa = {K} .
• (Ko6) Ifl- a = {3 then I<oa = I<o{J.
• (K o 7) If K o anKB({J) ::j; 0 then]{ o (a/\{3) = ]{ o an I<B({J) .
• (Ko8) If I< oa; n I<B(a;+l) ::j; 0 for 0 ~ i < n , and I< o ann KB(a0 ) ::j; 0 then K o (ao 1\ an)~ I< o ao .

(I< o 2) and (I< o 6) are the only postulates the same as their AGM counterparts . For (K o 1) , revision, like contraction, isn't guaranteed to result in a unique belief set. (I< o 2) reflects the requirement that the revision be successful. (I< o 3) is an obvious weakening of (I< +3) ; it is difficult to think of a situation where it shouldn't hold. In contrast , it seems feasible that a revision function may not satisfy the AGM postulates (K+3) and (!<+4), since if a is consistent with J(, it may be that f{ +a isn't the most similar belief set to f{ in which a is believed; for this to hold we could again bring in an assumption of informational economy. ( [{ +s) is missing: if If ·a there is nothing forbidding [{ o a = K1.. (K o 7) and (K o 8) again are dissimilar from their AGM counterparts.

Again, various reasonable and interesting results fol­ lowing from these postulates. Several examples are given in the following theorem.

Theorem 3.5

1. Koa = Ko/3 iff Koa ~ KB(f3) and Kof3 c KB( a) .
2. If K o a ~ KB(f3) then K o (a A /3) = K o a.
3. If K o a; ~ KB(ai+I) for 0 ~ i < n and K o an ~ KB(a0 ) then Koa; = Koa;+I forO~ i < n.
4. 4- K o anK o/3 = 0 or K o (aA/3) ~ [{ o a or [{ o (a/\ f3) ~ K of3.

For the third result, if K o a; ~ KB( a;+I) then se­ mantically (see below) the least a; belief sets are no more similar to [{ than the least a;+1 belief sets. If a chain of such containments forms a "loop", then the revisions are equally similar and, in fact, equal. The final result pro­ vides a weaker version of the AGM "factoring" result (see [Gar88, p. 57 (3.16)]). It is also weaker than the corre­ sponding result for contraction (Theorem 3.1.2). As well, the AGM postulates (K+7) and (K+8) are not logical consequences of the KB revision postulates, in contradis­ tinction to the AGM contraction postulates (I<;_ 7) and (I<;... 8) whose analogues are logical consequences of the KB contraction postulates.

In addition, we do not obtain the representation re­ sult for revision that we do for contraction. Define a weak similarity order model on belief sets centred on [{ to be a similarity order model on belief sets except rather than being connected, it is reflexive only. We obtain the following results relating the KB revision postulates to weak similarity order models.

Theorem 3.6 Let M be a weak similarity order model on belief sets centred on K . If we define K o a = min( a) then the KB revision postulates are satisfied in M.

Theorem 3. 7 Let o be a function from T x L to 2 7 satisfying the KB revision postulates. Then for any fixed theory [{ E T there is a weak similarity order model on belief sets centred on [{ satisfying [{ o a = min( a) for all a E L .

As with contraction we can ask what conditions are required to recover the other AGM postulates. We can specify that revision has a unique belief set as its value via strategies sketched previously. To obtain an equiva­ lent of (I< +s) we would require (and not unreasonably) that the inconsistent belief set be the most dissimilar of belief sets to any consistent belief set. Other postulates are dealt with by imposing similar conditions.

3.4 Discussion

As in the AGM approach, the present approach leaves open how a specific contraction or revision function may be defined. Rather, the approach provides constraints that contraction and revision functions must obey. If one accepts that a notion of similarity as developed here underlies belief change then one presumably would ac­ cept the respective postulate sets that would limit prop­ erties of an acceptable change function. One can further restrict the class of acceptable functions by placing ad­ ditional restrictions on the notion of similarity. Thus if the range of a contraction function for belief set [{ is re­ stricted to be a subsumed belief set of K, this together with a selection function restricts the satisfying contrac­ tion functions to those satisfying the AGM postulates.

On the other hand, one could propose a specific metric of similarity for a (say) revision operator. For example, if we equated a belief set with a set of possible worlds rather than a set of sentences, then Dalal 's approach [Dal88] is easily expressed using similarity: for belief set [{ the most similar belief sets to [{ not the same as [{ would be those composed of possible worlds differing in one literal from a world in [{. The next closest set of belief sets would be those composed of worlds differing in two literals from a world in [{, and so on. The result of revising [{ by a would be the maximal, nearest belief set in which a is true.

As mentioned, revision proves to be weaker than con­ traction. In detail, in the proof of Theorem 3.3 a sim­ ilarity order model is defined such that for belief sets [{ 1 and [{ 2 there are a and f3 such that [{ 1 E [{ o a and [{2 E [{ o {3. Theorem 3.1.2 yields that for every a and {3 : [{ o a~ [{ o (a 1\ f3) or [{ o f3 ~ [{ o (a 1\ {3) . [{ o a ~ J{ o (a 1\ {3) for exam pie asserts that every belief set in J{ o a is in [{ o (a 1\ f3), or informally the belief sets in J{ o a and K o (a 1\ f3) are equivalently similar, so the belief sets in K o f3 are no more similar to K than the be­ lief sets in J{ o(a/\{3), whence /{1 ~K /{2 · For revision , there is no such relation among belief sets, and the belief sets in [{ o a, J{ o f3, [{ o (a 1\ f3), and [{ o (a V f3) may be distinct. We thus lose the capability to define connectiv­ ity in Theorem 3.7. This difference in turn relies on the fact that contraction yields belief sets consistent with a sentence, whereas revision yields belief sets in which a sentence is provable.

Interestingly, a revision operator satisfying the AGM postulates is obtained in terms of KB contraction and the Levi identity, but AGM contraction is not recoverable from KB revision using the Harper identity.

Theorem 3.8 Let M be any similarity order model cen­ tred on [{ with [{ o a defined as in Definition 3.4 where

1. o : KB x L ,...... KB
2. K1 ~K K1. for every K1 E KB.

Define J{ o a = ( J{ o ·a) + a. Then [{ o a satisfies the AGM revision postulates.

See the discussion at the end of Section 3.2 for meet­ ing the first proviso in the theorem; the second proviso states that the incoherent belief set is maximally dis­ similar to [{. The theorem is interesting, in that it ar­ guably demonstrates that AG M revision is founded on assumptions of similarity (as given in KB contraction) plus informational economy (as implicit in the expansion in the Levi identity) plus uniqueness (proviso one) plus the avoidance of incoherent belief states (proviso two).

We don't obtain a similar result for revision and the Harper identity.

Theorem 3.9 Let M be any similarity order model cen­ tred on K with K a a defined as in Definition 3. 7 where

1. a : KB x L ,...... KB

2. K1 ~K J{.l. for every K1 E KB.

Define K o a = J{ n (k a ·a:). Then K o a satis­ fies (K.:.. 1}, (K.:.. 2), (K.:.. 4) provided J{ f. K1., and (K .:..6).

Not surprisingly, the KB contraction/revision func­ tions are weaker than the corresponding AGM functions .

Theorem 3.10 Let f be a function satisfying the AGM contraction (revision) postulates. Then f satisfies the KB contraction (revision) postulates.

More surprising is the fact that the contraction postu­ lates are not strictly weaker than the KM erasure postu­ lates [KM92), in that (K o 3) is not a consequence of the erasure postulates . However the KB revision postulates subsume the update postulates.

Theorem 3.11 Let f be a function satisfying the KM update postulates. Then f satisfies the KB revision pos­ tulates .

It is an interesting, but unexplored, question to deter­ mine whether there is anything about contraction and revision as defined here that lends them most naturally to the AGM and KM approaches respectively.

4 Conclusion

A foundational approach has been presented in which to investigate belief change. The central intuition is that change to a belief set J{ by a sentence a is with reference to the belief set( s) most similar to K . The approach is quite basic, in that various of the AGM postulates don't hold, or only hold in a weaker form. Arguably the ap­ proach is not too basic, in that interesting properties still obtain, as given in the set of KB contraction and revision postulates. Moreover, the approach allows fine-grained control over the properties of contraction and revision functions. This is illustrated by the fact that of the basic AGM postulates that don't hold in the approach, each may be independently satisfied in some augmentation of the approach. An advantage of the approach then, as a foundational approach to revision, is that while the semantic basis is intuitive, such additional assumptions must be explicitly recognised and made. As a corol­ lary, the approach arguably demonstrates that AGM re­ vision can be viewed as being founded on a number of distinct assumptions including similarity, informational economy, and the avoidance of incoherent belief states.

A further result of this inquiry is that it appears that, at their core, revision and contraction constitute distinct functions, with revision being the weaker. A question for future work to ask what it is about the AGM approach that leaves revision and contraction there interdefinable but not here. A second question concerns the relation of the approach to update and erasure.

There has been substantial recent interest in iterated belief revision. Iterated revision has not been addressed here, mainly because our foremost interest is in develop­ ing an approach that in some sense is more basic than the AGM approach. Clearly iteration could be addressed by investigating relations among similarity orders; in f~ct it may be that iterated change is more easily addressed here than in the AGM approach, primarily because here we have stepped back from some of the commitments of the AG M approach. A straightforward approach for in­ corporating iterated revision is, in a model, to define a mapping from pairs of belief sets to ordinals, giving the relative similarity of every pair of belief sets. From this it is an easy step to define an epistemic state for a belief set, K, corresponding to the total preorder expressing the relative similarity of each belief set to K.

Acknowledgements

I thank Maurice Pagnucco for his extensive and very helpful comments on an earlier version of this paper. As well I thank two reviewers for their comments.