Belief Revision, Revised

1 Introduction

Intelligent agents must gather information about the world elaborate theories about it and revise those theo­ ries i1; view of new information that, sometimes, contra­ dicts the beliefs previously held. Belief revision is there­ fore a central topic in Knowledge Representation. It has been studied in different forms: numeric or symbolic, procedural or declarative , logical or probabilistic. One of the most successful framework in which belief revi­ sion has been studied has been proposed by Alchourr6n , Gardenfors and Makinson, and is known as the AGM framework. It deals with operations of revision that re­ vise a theory (the set of previous beliefs) by a formula (the new information). It proposes a set of rationality postulates that any reasonable revision should satisfy. A large number of researchers in AI have been attracted by and have developed this approach further : both in the abstract and by devising revision procedures that satisfy the AGM rationali ty postulates. Even though iterated revisions are a central concern in AI applications , those postulates do not mention iterated revisions explicitly. A closer look shows that the AGM postulates do not say anything on the way a revision may depend on its first argument , the theory being revised. If one considers iterated revisions, shouldn't one put some requirement on this dependence? This paper will show that some such requirements should be considered. It is time to take stock of what has been accomplished and assess the general approach. Noticeable progress has been made in three directions:

*This work was partially supported by the Jean and He­ lene Alfassa fund for resea.rch in Artificial Intelligence and by grant. 136/94-1 of the Israel Science Foundation on "New Perspectives on Nonmonotonic Reasoning".

• in distinguishing revisions of a theory about an un­ changing world from updates of a theory about an evolving situation under an assumption of in­ ertia [Katsuno and Mendelzon, 1992),
• in relating the AGM rationality postulates to properties of nonmonotonic consequence rela­ tions [Makinson and Gardenfors, 1989; Gardenfors, 1990; Gardenfors and Makinson, 1994],
• and in the explicit consideration of iterated revisions , their properties and postulates for them.

The third point needs to be expanded upon. Many au­ thors ([Boutilier and Goldszmidt, 1993; Boutilier, 1993; Darwiche and Pearl , 1994; Williams , 1994; Nayak et al., 1995]) have recently expressed interest in iterated revi­ sions. One may definitely consider iterated revisions in the AGM framework, but one may notice that AGM consistently avoided mentioning iterations of their * op­ erator in their rationali ty postulates. Natural proper­ ties of iterated revisions, such as postulate Cl below, have therefore been largely ignored (until [Darwiche and Pearl , 1994]).

This work proposes a slightly modified, more conve­ nient, framework in which to study iterated belief revi­ Sions.

In section 2, the AGM postulates will be recalled . In section 3, two additional postulates concerning iterated revisions will be described, and a triviality result proved. Then in section 4 a new framework and notation will be described. A set of rationali ty postulates is proposed and discussed in section 5. Formal properties of the postu­ lates are proved in section 6. A family of models, that of widening ranked models, is described in section 7. The revisions they define are exactly those that satisfy the postulates proposed in section 5. Methodological consequeuces of this representation result are discussed. Sec­ tion 8 concludes by stressing open problems.

2 The AGM framework

The AG M framework studies revision operations, de­ noted *, that operate on two arguments: a theory (any set of formulas closed under logical deduction) K on the left and a formula a on the right. Thus K*a is the re­ sult of revising theory [{ by formula a , using revision method *· The original AGM rationality postulates are the following. We use the customary notation Cn(X) for the set of all logical consequences of a set X of formulas. The logical connectives always have precedence over the * operation.

• K* 1 K*a is a theory.
• K*2 a E K*a.
• K*3 K-~<a ~ Cn(K, a).
• K*4 If ·a fl.!(, then Cn(K, a)~ K*a.
• K*5 If f{*a is inconsistent , then a is a logical contradict ion.
• K*6 If f= a <-+ b, then K*a = !{* b.
• K*7 K*a/\b~Cn(K*a , b).
• K*8 If ·b fl. K*a , then Cn(I{*a , b) ~ K *a 1\ b

3 Additional postulates

The following additional postulate was proposed in [Dar­ wiche and Pearl, 1994]:

Thejustification for Cl is that, if an agent learns, first, some partial information (a) and then the full informa­ tion (a 1\ b) , the partial information should not make a difference. Detailed arguments in favor of Cl may be found in [Darwiche and Pearl , 1994] and below in this paper, after the presentation of 15, in section 5. That Cl is consistent with the AGM postulates is seen from the considerat ion of the trivial revision defined by:

The trivial revision satisfies C1 and the AGM postu­ lates. The following shows that C1 is a powerful postu­ late.

Theorem 1 Any revision operation * that satisfies K*l -K*6 and C1 satisfies K*7, K*8 and the postulates C3 and C4 proposed in [Darwiche and Pearl, 1994].

In other terms , Cl is an elegant , slightly more power­ ful , version of the AGM postulates K*7 and K*8. The proof is similar to that of the corresponding lemmas of section 6.

The postulate C2 proposed in [Darwiche and Pearl , 1994] has been shown inconsistent with the AGM postu­ lates in [Freund and Lehmann, 1994]. Even the weaker C2' proposed in [Nayak et a/. , 1995], is inconsistent. An even weaker postulate is:

The justification for Dl is that , if an agent succes­ sively learns two contradictory pieces of information , it should not , at the end , hold beliefs it would not hold if it had not learned the false , intermediate informa­ tion. Such beliefs could only be the result of information known to be incorrect. The next result is a triviality re­ sult.

Theorem 2 The only revision operation that satisfies K*1 -K*6 , C1 and D1 is the trivial revision defined above.

A lemma is needed.

Lemma 1 Let * be a revision satisfying K* 1-K*6 , C1 and Dl. If b f= ·a, then K*a*b ~ Cn(K, b).

Proof: By Cl , K*a/\·b*b= f{*a/\·b*·aVb*b. But the left hand side is K*a*b , and K*a*b ~ Cn(K*a/\·b*·aVb, b). One concludes by Dl: K*a*b ~ Cn(K, b). I

The proof of Theorem 2 will be presented now.

Proof: Suppose ·-,a E J( , the only interesting case. Let k be the conjunction of all formulas of [{ (a finite lan­ guage is assumed) and K0 be the set of all tautolo­ gies. Then , [{ = K0*k and a f= ·k. By Lemma 1, then, K*a = f{0*ha ~ Cn(I<0 , a) = Cn(a) . I

4 The revised framework

Central to the present analysis is the concept of a belief state resulting from a finite sequence of revisions. In this work, the underlying language is supposed to be a pro­ positional calculus on a finit e set of atomic propositions. The individual revisions considered are represented by consistent formulas: the formula describes the new infor­ mation received that triggers the revision. The letters: a , b and c will be used to stand for arbitrary consistent formul as. Arbitrary finite sequences of individual revi­ sions, i. e., finite sequences of consistent formulas , will be represented by: p, a and r. The empty sequence is denoted A. Concatenation of sequences is denoted · and formulas will be identified with sequences of length one. For example: the sequence a · a · r consists of, first , the formulas of the sequence a, then the formula a and finally the formulas of the sequence r. The belief set resulting from a sequence a of individual revisions , will be denoted by [a]. The square brackets ([ ]) represent a revision procedure. For example: [A] is the belief set resulting from revising the initial belief set by an empty sequence of revisions, it is the initial belief set. A theory is a set of formulas that is closed under logical conse­ quence. Material implication is denoted -+ .

In order to understand and evaluate the set of new rationality postulates presented in section 5, it helps to consider the correspondence between the new notation introduced above and the traditional AGM notation. As explained above [a · a] represents the belief set that re­ sults from revising the initial belief set by, first, the for­ mulas of a, and then the formula a. Similarly [a] repre­ sents the belief set that is the result of revising the initial belief set with the elements of a. The belief set [a · a], therefore, represents the result of revising the belief set [a] by the formula a. It may seem that we may identify

[u ·a] with what AGM would have denoted [u] *a. Nev­ ertheless, an important difference exists. The notation used by AGM implicitly implies that, if [u] = [r], then, [a-] * a = [ T] * a, whereas the set of postulates of section 5 does not imply: a rev1s1on by a formula that is a member of the cur­ rent belief set is useless. As an example, consider an agent, in a shuttered room, that believes the sun is shin­ ing. Suppose it opens a shutter and sees that, indeed, the weather outside conforms to its beliefs. Postulate Non _ postulate If [u] = [r], then [a-. a]= [r. a]. 14 says that this agent should not modify its belief set , and, moreover, also says that this confirmation of the The framework of this paper allows the agent to base its revision, i.e., [a- · a], not only on the belief set [a-], but also on the way the agent got to this belief set, i.e., on the sequence a- itself. It must be pointed at that , though the framework presented here does not include the non­ postulate, this postulate is expressible and therefore may be added to the set of basic postulates to be presented below, if one wishes to do so. But theorem 5 will show that the only revision that satisfies the rationality pos­ tulates of section 5 and the non-postulate is the trivial reVISIOn. 5 5.1 Rationality Postulates The postulates The following postulates are proposed to characterize reasonable revision methods. They have to be under­ stood, for any sequences a- , T and for any formulas a, b. 11 [ u] is a consistent theory. 12 aE [u ·a]. 13 If bE [u ·a], then a--+ bE [u]. 14 If a E [u], then [u · r] = [u ·a· r]. sunny weather outside should in no way influence fur­ ther revisions. This seems reasonable as far as theory revision is concerned, it seems unreasonable for theory update (in a changing world) . Suppose, indeed, that , an hour after the scenario described above, our agent opens a shutter and realizes it is raining. In the case it did not open the shutter earlier , it may well want to assume it has been raining for some .time and be­ lieve a flood warning has ben put out already. In the case it did open the shutter, on the contrary, it will be­ lieve the flood warning has not been put out yet. Note that , in the study of theory update found in [Katsuno and Mendelzon, 1992], the equivalence r.p o 11- = r.p when r.p F 11- is their postulate (U2), and is therefore part of the system. It follows that , for them , if r.p F fl- , for any v , r.p o 11- o v = r.p o v . The fact that the similar 14 is un­ acceptable for theory update raises serious doubts as to whether the Katsuno-Mendelzon approach is capable of dealing properly with iterated updates . Notice that 14 is unreasonable if the theory being revised is inconsis­ tent, but this case is excluded in the present framework: revising the inconsistent theory by a consistent formula must change the theory, by 12. Postulate 14 expresses a property akin to the Cumulativity of [Kraus et al. , 1990]: learning that a plausible consequence is indeed 15 If b Fa, then [a- . a. b. r] =[a-. b. r]. true does not change the set of plausible consequences. 16 If b ~ [ l h [ b l [ b l Note also that the property: If r.p E K , then K* r.p = K , -, a- · a t en a- · a · · r - a- · a · a 1\ · T G 1 h h h }? · ' - · follows from the A M postu ates, w en t e t eory \ IS 17 [u. ·b . b] ~ Cn([u], b). consistent . Postulate 14, therefore, does not imply any Note that the formula a 1\ b appearing in 16 is indeed a consistent formula if ·b ~[a-· a] by 11 and 12. strengthening of the AG M postulates, or of the Katsuno­ Mendelzon ones for theory updates, as was pointed out just above.

5.2 Discussion of the postulates

Postulate 11 requires belief sets to be consistent theories. It corresponds exactly to the AGM postulates K*l and K*5. The only reason 11 looks stronger than K*5 is that the only revisions considered here are revisions by consistent formulas. 11, therefore, does not represent any strengthening of the AGM postulates.

Postulate 12 requires the last element of a sequence of revisions to be a member of the belief set obtained. Since a is a consistent formula , this requirement is compatible with 11 . It corresponds exactly to K*2 .

Postulate 13 expresses the fact that the agent should be aware of the results of possible revisions: if it would accept b after a revision by a it should, already now, accept that if a is true then b is true. It is similar to the property (S) of [Kraus et a!., 1990]. It corresponds exactly to AGM's K*3.

The next three postulates have the same structure: they assert that two different sequences of revisions are equivalent , i.e., they produce the same belief set. Pos­ tulate 14 deals with the case a revision is superfluous and can be eliminated, by virtue of previous revisions:

Postulate 15 is perhaps the most remarkable of the list. It concerns the case a revision is made superfluous by virtue of the following revision: if one revises first by a and then by a 1\ b, the second revision confirms all the in­ formation contained in the first one, and, therefore, the first revision is superfluous. Suppose for example that an agent listens to some reliable source of information saying: " c is true ... , and d is also true" . It should not make a difference for the agent to , either wait until the end of the sentence and revise by c 1\ d, or, revise first by c on hearing the first part of the sentence and then revising by c 1\ d on realizing it did not hear all of the sentence. Note that revising first by c and then by d is not equivalent to the above, since the agent learned that c and dare true together, whereas learning d alone, even after learning c, could convince the agent to abandon c. Postulate 15 is an adaptation to the new framework of Cl. In this new framework , it is not enough to say that, in the situations considered, the first revision (by a) can­ not influence the belief set that results from the second one (by b) , the postulate must also say explicitly that the first revision cannot influence the result of any further revision (by T). Postulate 15 does not correspond to any of the AGM postulates and indeed , Cl, does not follow from the AGM postulates. Postulate 15, therefore, rep­ resents a definite strengthening of the AGM postulates , but it seems very difficult to find reasons to reject it. The question whether 15 should be accepted for updates is more delicate. My present feeling is that it should: learning , first , a and then a 1\ b should not make me think that there have been two changes in the world, but probably that, when I learned a , a 1\ b was already true.

Postulate 16 deals with the case in which a formula , a, used to revise a belief set, may be repeated in the next revision, i.e., when revising first by a and then by b is equivalent to revising by a and then by a 1\ b. Note immediately that, in the presence of 15, 16 is equivalent to:

16' says that, if a certain condition is met , two suc­ cessive revisions may be col lapsed into one revision by the conj unction of the two formulas involved. The con­ dition to be met is that the second revision is a mild one, i.e., ·b ~ [0' ·a]. It stands to reason that there may be a difference between revising by a 1\ b one one hand and revising 0' first by a and then by b only if the sec­ ond revision is a severe revision , i.e., ·bE [0' ·a]. If it is not a severe revision , we expect the result to contain the formul a a, and, therefore, we expect 16 to be satisfied. Postulate 16' corresponds to AGM's postulate K*8 and a special case of K*7. Postulate 16, therefore, does not represent any strengthening of the AGM postulates.

Postulate 17 is an instance of the Principle of Mini­ mal Change. If, after a sequence 0' of revisions, an agent learns ·band, then, b, it certainly believes b, but any ad­ ditional belief it may have can only come from the beliefs it held after the sequence 0': none of the beliefs triggered by learning ·b should survive learning b. Postulate 17 is not a consequence of K*l - K*8 , and even not a conse­ quence of the additional K*9 of [Freund and Lehmann , 1994] . Translated back in the traditional AGM frame­ work , one gets Dl above, which is a weakening of C2. It is the strongest possible weakening of C2 that is consis­ tent , and should therefore be considered as the correct expression of the intuitions behind it.

If one considers the postulates above, not from the point of view of theory revision , i.e., changing beliefs on a static situation , but from the point of view of theory update [Katsuno and Mendelzon, 1992], i.e., changing beliefs on a changing situation, one would probably ac­ cept all the postulates above, under the usual assump­ tions (priority to new information) , except for 14 and 17. The confirmation of the truth of a proposition believed to be true should probably influence further updates by giving a posterior time stamp to the information . Learn­ ing that a proposition b has changed from false to true may provide the agent with new information expressing the consequences of a change.

The set of rationality postulates presented above is very similar to the set proposed by AGM. On one point it is slightly weaker: the non-postulate, and two other points it is slightly stronger: 15 and 17. Since postulates

15 and 17 seem secure, i.e., diffi cult to reject, the postu­ lates 11-17 may probably be considered as a reasonable formalization of the intuitions of AGM. 17 is probably less secure than 15, but the system 11-16 is amenable to a study that is very close to the one to presented now.

6 Properties of the postulates

Some consequences of postulates 11- 16 (the last postu­ late is not used in this section) will be described now. Many of the proofs have been omitted.

In the rest of this section, 0' f-> [0'] is supposed to be a revision system satisfying 11- 16. One interesting aspect of the postulates above is that no postulate similar to K*6 , expressing invariance under replacement of a for­ mul a by a logically equivalent formula is needed.

Lemma 2 If a is logically equivalent to a', then [ 0' · a · T] = [ (T · a' · T ].

Proof: By 12 and 11 , since a f= a', a' E [0' ·a]. By 14, then , we have [0' ·a · T] = [0' ·a ·a' · T] . But , since a' f= a , by 15, [0' ·a· a'· T] = [0' ·a'· T] . I

The next results, lemmas 3 and 4 show that our system enjoys all the properties of the AGM system.

Lemma 3 If ·a ~ [0'], then [0' ·a]= Cn([O'], a).

Proof: By 13, [0' ·a]~ Cn([O'], a). By 11 and 12, [0' ·a] is a theory that contains a. To show Cn([O'], a)~ [0' ·a], it is therefore enough to show that [0'] ~ [0' ·a]. Sup­ pose bE [0']. By 14, we have both [0' · b] = [0'] and [0' · b ·a]= [0' ·a]. We conclude that ·a ~ [0' · b], and , that, by 16', we have [0' · b ·a]= [0' · b 1\ a]. By 11 and 12, then, bE [0' · b ·a]= [0' ·a]. I

The next result expresses the AGM postulates K*7 and K*8.

Lemma 4 [0' ·a 1\ b] ~ Cn([O' ·a], b) and, if ·b ~ [0' ·a], then one also has Cn([O' ·a], b)~ [0' ·a 1\ b].

Proof: If ·b E [0' ·a], Cn( [O' ·a], b) is the full language and the the first claim is proved. It is left to us to prove that , if ·b ~ [0' ·a], then, Cn([O' ·a], b)= [0' ·a 1\ b]. But, by lemma 3, Cn([O' ·a], b)= [0' ·a· b], and by 16', [0' ·a · b] = [0' ·a 1\ b] . I

We have shown that, for a fixed 0', the theories [0' ·a], obey all of the AGM postulates. The next batch of re­ sults, lemmas 5, 6 and 7 concern the influence of a mild revision before a severe revision.

Lemma 5 If ·a ~ [0'], but ·bE [0'], then [0' ·a· b · p] = [(T . b . p] .

Proof: By 15, [0' ·a· b · p] = [CT · a V b ·a· b · p]. Since ·a ~ [CT], we know that ·(a V b)~ [CT], and , by lemma 3, [0' ·a V b] = Cn([O'], a V b). Since ·b E [CT], we conclude that a E [0' ·a V b]. Postulate 15, then, implies that we have [0' ·a V b ·a· b · p] = [0' ·a V b · b · p]. By 15, again, [0' ·a V b · b · p] = [0' · b · p] and we are done. I

The next result concerns disjunction: it has an interest of its own . As one would expect, if the same conclusion is arrived at by two different but parallel sequences of re­ visions: CT · b · T and CT · c · T , where c has replaced b, then it could have been arrived at by the sequence CT · b V c · T.

Lemma 6 If a E [u ·b · r] and a E [u · c · r], then we have a E [u · b V c · r].

\iVe may now state our main result concerning the effect of an intermediate mild revision. This result is very im­ portant, because it is, in a sense paradoxical. One of the main aims of Belief Revision is to provide revision sys­ tems that satisfy the Principle of Minimal Change: as much as possible of the old theory should be kept in the revised theory. In case of a mild revision this principle is fully enforced by lemma 3. But in the case of a severe revision, the postulates (ours or AGM's) do not seem to enforce the principle in any way. The next lemma shows that , essentially, the Principle of Minimal Change for severe revisions is inconsistent with the very natural postulates 11- 16. The effect of a mild revision essentially fades away at the first severe revision: the identity of the formula by which one performed a mild revision is for­ gotten after the first severe revision. Therefore no part of the old theory that was brought about by the mild revision can be kept in the new theory: the best one could hope for is to keep those parts of the old theory that were brought about by the previous severe revision. We shall not try, here, to discuss the implications of this result, if there are , for the epistemology of science.

The previous lemmas present basic consequences of the postulates 11- 16. They are also needed for prov­ ing the representation theorem of section 7. The next lemmas show that the postulates 11- 16 imply proper­ ties that are similar to the C3 and C4 of [Darwiche and Pearl, 1994].

Lemma 8, describes a strengthening of both 15 and property C3. It resembles 14, but the order between a and b is different. The proof of lemma 8 provides a proof that C3 is a consequence of Cl and the AG M postulates.

Next lemma is similar to Darwiche and Pearl's C4. Its proof provides a proof that C4 follows from Cl and the AGM postulates.

Lemma 9 If ·b f{. [u ·a], then ·b f{. [u · b ·a].

7 Iterated revisions in widening ranked models

A class of revision procedures, defined by a family of ranked models, will be presented now. Any procedure of this class satisfies the postulates presented in section 5. A word of caution and explanation is needed here to clarify the role those models. The models to be pre­ sented are an extremely useful technical tool to study rationality postulates, they are not intended to describe the ontology of theory revision. The reader may, justifi­ ably, feel that the models presented do not provide for a proper ontology of theory revision, because the revi­ sions they define do not satisfy, or do not comply enough with, the Principle of Minimal Change. This point will be discussed at the close of this section and taken again in more depth in section 8.

The general framework is that of a ranked model, de­ fined in [Lehmann and Magidor, 1992]. The agent uses a plausiblity ranking over possible state of affairs. Each state of affairs is labelled with a propositional model. After any sequence of revisions the agent sees itself at a certain implausibility rank n and considers plausible a non-empty set of states of affairs of rank n. When revis­ ing, then, by a formula a, the agent examines whether there is a state of affairs among the ones it considers plausible that satisfies a. If there is one, it continues to see itself at the same implausibility rank n , but down­ sizes its set of plausible states to those that satisfy a. If, on the contrary, there is no state that satisfies a among the plausible states, it increases its implausibility rank to the smallest rank, m, above n at which there is a state of affairs that satisfies a. It considers plausible any state of rank m that satisfies a.

Two additional restrictions are put on the ranked model. First, the set of possible states of affairs (i.e. , propositional models) at an implausible rank is a super­ set of the set at a more plausible rank: the set of propositional models widens with higher implausibility ranks. This enforces the condition that less assump­ tions, less default information is available at less plausi­ ble ranks: a sequence of contradicting revisions (by band ·b successively) essentially cannot give the agent new in­ formation. Secondly, any propositional model must ap­ pear at some implausibility rank, and therefore at any rank of sufficient implausibility. The purpose of this last requirement is to ensure that the agent always, i.e. , after any sequence of revisions, ends up with a non-empty set of plausible states of affairs.

Eyen though the underlying language considered is fi­ nite, we cannot restrict our attention to models in which the ranks are natural numbers , we need to allow ordi­ nals as ranks. Consider, for example, a revision system in which b E [a · ·a ·a ... · a] and b E [a· ·a ·a ... · ·a] for any sequence of revisions by a and its negation alter­ natively. The rank corresponding to [-.b] must be infi­ nite. The formal definition of a widening ranked model will be given now. As explained above, the ranks are ordinals. Note that, since the ranks are ordinals (a well­ ordered family) , the smoothness condition of [Lehmann and Magidor, 1992] becomes superfluous. Some initial segment of the class of ordinals will be denoted by N, and the set of all propositional models by W. It is easy to see that the initial segment N does not need to be very long: w + w is always sufficient, if the language is finite.

Definition 1 An widening ranked model consists of is a function M : N r---. 2 W - 0 such that,

1. for any n, mEN, if n :S m, then M(n) s;;: M(m) , and
2. for any w E W, there is some n EN such that wE M(n).

The value of M(n) is the set of all models that represent some state of affairs of implausibility n. Notice that , on a finite language, in any widening ranked model, there is a rank n such that for every m >= n, M(m) = W. Any widening ranked model, M, defines a system of iterated revisions in the following way. Any sequence of revisions (J defines a rank r( (J) and some set of propositional mod­ els, p((J) ~ M(1·((J)).

Definition 2 The definition is by induction on the length of (J.

• 1·(A) = 0 and p(A) = M(O).
• If there is in p( (J) some element that satisfies a, one has r((J ·a)= r((J) and p((J ·a) is defined to be the (non-empty) subset of p( (J) containing all models of p((J) that satzsfy a. If no element ofp((J) satisfies a, r( (J · a) is defined to be the smallest n > 1·( (J') such that some element of M(n) satisfies a. Note that definition 1 implies there is such an n. The set p((J ·a) is defined to be the (non-empty) subset of M ( n) containing all models that satisfy a.

Now, given any widening ranked model, M, a system of iterated revisions may be defined.

Definition 3 For any sequence (J, [(}'] is the set of for­ mulas that are satisfied in all models of p( (J).

The following soundness result is straightforward.

Theorem 3 The revision procedure defined (as in defi­ nition 3) by any widening ranked model satisfies postu­ lat es 11 -17.

The soundness of 17 follows from part 1 of definition 1. The fact that [(}'] is consistent is ensured by the fact that p((J) is never empty.

The widening ranked models are technically much eas­ ier to manipulate and grasp than the rationality pos­ tulates 11- 16 . It is, therefore, important to prove the converse of theorem 3.

Theorem 4 Any revision procedure that satisfies 11 -17 is defined by some widening ranked model.

The proof of this result has been obtained, so far, only under the assumption of a finite number of atomic propo­ sitions, and is too long to be presented here.

Since the only widening ranked model that defines a revision that satisfies the non-postulate is the triv­ ial widening ranked model in which all ranks contain all propositional models, we have the following.

Theorem 5 The only revision that satisfies 11 -17 and the non-postulate is the trivzal revision.

The trivial revision is defined by:

As noted above , on a finite language, any widening ranked model is trivial from a certain rank onwards: all ranks are full, they contain all possible propositional models. Therefore, any revision satisfying11- 17 becomes trivial for long enough sequences of revisions.

It seems, at the present stage of this work, that 17 corresponds exactly to the widening property of ranked models. It is clear that any ranked model in which every propositional model appears at unbounded ranks defines a revision that satisfies 11- 16. The converse seems to hold , but has not been fully proved yet.

I expressed, at the beginning of this section, the feeling that the revisions defined by widening ranked models are probably not the revisions one would like to use because they seem to provide severe revisions that methodically neglect the Principle of Minimal Change. This point will be discussed in section 8, but two preliminary re­ marks may be made here. First, it may be the case that suitable restrictions on the ranked models ensure compliance with the Principle of Minimal Change. The trivial ranked model in which every propositional model appears at every rank certainly does. Secondly, since any revision satisfying 11- 17 may be defined by such a. model, the conclusion could be that no reasonable re­ vision procedure can satisfy the Principle of Minimal Change in a meaningful way. Since postulates 11- 17 are very closely related to the AG M original postulates, this would probably signals that no reasonable revision sat­ isfying the AGM postulates complies with the Principle of Minimal Change.

8 Conclusion

A new framework: syntax, semantics and postulates, for theory revision has been presented. Much of what has been done in the new framework may be translated back into the original AGM framework, but this new frame­ work seems more conducive to experimentation with new postulates: for example, the strength of postulate Cl or the triviality result of section 3 were only discovered in the new framework. A set of natural rationality postu­ lates has been proposed. It is surprinsingly powerful. A number of questions have received only partial answers. Representation theorems for weaker systems should be sought for. The quest for a suitable system for belief update is probably the most intriguing question of this type. Such a system must reject 14, and must therefore be essentially different from [Katsuno and Mendelzon, 1992]. The postulate 15 provides an intriguing new ax­ iom to be introduced into Conditional Logic, or, equiv­ alently, in the treatment of embedded conditional asser­ tions: a > (b > c) <-+ b > c, if b f= a.

It is probably the opinion of most readers that revi­ sions defined by widening ranked models (or just ranked models, for that effect) are not satisfactory because they do not properly implement the Principle of Minimal Change. This work shows that this defect is a nec­ essary consequence of two postulates, 15 and 16 that embody some other principle of informational economy. The proper conclusion is probably that not all reasonable principles of revision are compatible.

The underlying philosophical assumptions of AGM seem to imply that contraction is the more basic opera­ tion , revision being only a derived operation consisting of a retraction followed by an expansion (the Levi iden­ tity). AI researchers will probably find this thesis ques­ tionable. It seems the operation of revising a theory in view of new information is more basic to AI than that of retracting previously received information upon learning that this previous information was obtained from some unreliable source. If such a retraction has to be per­ formed it seems that it will be because new information implying the unreliability of the source has been gained and therefore this retraction is really a revision by this new information. The question of the meaning of the new rationali ty postulates for retraction needs further study.

To conclude, I would like, using a remark of P. Schobbens , to give an example of the kind of philosoph­ ical questions that are raised by this work , but do not seem to have been remarked before. Suppose an agent learns, first, a long conjunction a 1\ b 1\ ... 1\ z and then its negation ·a V ·b V ... V --,z. Postulate 17 implies it will forget about the first information, since it has been contradicted by the second one. But one could argue that this is not the right thing to do. Granted, the first information is incorrect, but it could be almost correct. If one makes this assumption, upon receiving the second information, one will conclude that few components, per­ haps only one, of the conjunction are false, most of them still believed to hold true. This analysis distinguishes, I think, between two kinds of retractions. In the first one, one retracts a proposition because the source from which it has been obtained is now known to be unreliable. In this case, there is no reason to suppose the proposition is approximately correct. In the second kind of retraction, one retracts a proposition because some new informa­ tion came to contradict it. In this case, one may have reason to believe the proposition is still approximately correct. This distinction should lead to two different sets of postulates for retractions .

9 Acknowledgments

This work takes on where a previous joint work with Michael Freund [Freund and Lehmann , 1994]leaves off. The work of Darwiche and Pearl [Darwiche and Pearl , 1994] was instrumental in convincing me to look for rationality postulates for iterated revisions. Thanks are due to David Makinson, Mark Ryan , Pierre-Yves Schobbens and Emil Weydert for useful comments.