Representation Theorems for Multiple Belief Changes

1 Introduction

Belief change is the process through which a ratio­ nal agent acquires new beliefs or retracts previously held ones. A very influential work on belief change goes back to Alchourr6n , Gardenfors and Makinson [Aichourr6n et al. 1985 ], who developed a formal mech­ anism for the revision and the contraction of beliefs , which has been now widely referred to as the AGM theory. For a set of existing beliefs , represented by a deductively closed set J{ of propositional sentences , and a new belief, represented by a propositional sen­ tence A, three kinds of belief change operations are considered in the AGM theory: expansion, contrac­ tion and n~ vision, denoted by J( + A, f{ - A and K * A, respectively. A set of rationality postulates for belief contractions and belief revisions, based on the idea of minimal change, are given and two differ­ ent tools , partial meet model and epistemic entrench­ ment ordering , for constructing belief change opera­ tions haw~ been developed in [Alchourr6n et al. 1985 ] and [Gadenfors and Makinson 1988], respectively. Al­ though AGM's belief change operators appear to capture of what is required of an ideal system of belief change, they are not suitable to characterize changes of beliefs with sets of new beliefs , especially with infinite sets . A

number of studies on extending and generalizing these operations so as to enable a treatment of belief change by sets of sentences then come out [Fuhrmann 1988] [Niederee 1991] [Rott 1992] [Hansson 1992] [Fuhrmann and Hansson 94] [Zhang 1995] [Zhang 1996] . The ex­ tended operators for expansion, contraction and revision are usually called multiple ones while the original oper­ ators are referred to as singleton ones . A framework for multiple belief changes is not only interesting but also useful. We will benefit from it at least in the following aspects:

• The new information an agent accepts often involves si­ multaneously more than one belief, or even infinitely many, especially when the underlying language is ex­ tended to the first-order logic.
• It has been found that there are fundamental differences between iterated belief changes and simultaneous belief changes. The revisions of a belief set by a sentence A and then by a sentence B are by no means identical to the revision simultaneously by the set {A, B}. A framework for multiple changes will provide a possibility to describe the relationship between two sorts of belief changes (see [Zhang 1995 ]) . A ready example is the supplementary postulates for multiple revisions(see subsection 2.2 of this paper) .
• Connections between belief change and non-monotonic reasoning have been widely investigated in the liter­ ature [Makinson and Gardenfors 1991) [Brewka 1991) [Nebel 1992) [Gardenfors and Makinson 1994) [Zhang 1996). The key idea is translating B E K *A into . Af--B and vice versa. As claimed in [Gardenfors and Makinson 1994) this translation makes sense only on the finit e level. 'The idea of infinite revision functions seems to make good intuitive sense.' (see [Makinson and Gardenfors 1991 )P.190)

There have been several proposals for multiple belief changes ([Fuhrmann 1988] [Rott 1992] [Hansson 1992] [Fuhrmann and Hansson 94] [Zhang 1995] [Zhang 1996]) . This paper is by no means to present an alternative one. Instead of that, we attempt to combine these approaches and develop some necessary tools to improve and sys­ temize them. We will outline, in section 2, the two main paradigms of multiple belief changes: package con­ traction, developed by [Fuhrmann and Hansson 1994 ] , and general belief change operations, developed by

[Zhang 1996]. It seems, however , that both paradigms fail to capture full characterization of multiple belief changes. The former succeeds in specifying the basic properties of multiple contractions but fails to give the generalization of the supplementary postulates , whereas the latter presents a full extension of AGM's postulates for belief changes but without providing a representa­ tion theorem for its framework. In section 3 we will devote to present a representation theorem for the gen­ eral contraction , partially using the similar result of the package contraction. In section 4 we will argue with a counterexample that the postulates available for general contractions are not strong enough to characterize the multiple contractions. An additional principle , called Limit Postulate , is introduced , which reflects the rela­ tionship between the contraction by an infinite set and the ones by its finite subsets. The related representation result for Limit Postulate is then given. Section 5 will conclude the paper with a discussion on the application of this research to non-monotonic reasoning.

Unfortunately, space limitations do not allow a full presentation. All the proofs of lemmas and theorems and some of the lemmas which lead to the main results of the present paper are omitted.

Throughout this paper , we consider the first-order lan­ guage C with the standard logical connectives --,, V, 1\, --+, and ....... The set of all subsets of C is denoted by F. If F = { A1, · · ·,An} is a set of sentences, 1\F is an abbreviation of A1 1\ ···I\ An. We shall assume that the underlying logic includes classical first-order logic and is compact. The notation f- means classical first-order derivability and Cn the corresponding closure operator. We call a set J{ of sentences a belief set, which means that K = Cn( K) . The set of all belief set in C is denoted by /(. The notation K + F will denote Cn(I{ U F).

2 Postulates for Multiple Belief Change

In this section we try to give a survey of the current research on multiple belief change. Two types of mul­ tiple contraction and one type of multiple revision are discussed and their relationships is then established.

2.1 Multiple Contraction

[Fuhrmann and Hansson 1994 ] introduced two types of multiple contraction operations: package contraction and choice contraction 1 . They may all be viewed as gen­ eralizations of AGM contraction operation, but the for­ mer seems more acceptable. The so-called package con­ traction means contracting a belief set by removing all members of a set of sentences from it . For characterizing this operation, six basic postulates as generalizations of the corresponding basic postulates for AGM contraction are given as follows:

1 Similar formalisms are also introduced by (Rott 1992] and (Hansson 1992] .

• (K[-]1) K[-]F = Cn(I<[-]F).
• (K[-]2) K[-]F <;;;I<.
• (K[-]3) If¢ it' F , then F n (K[-]F) = ¢.
• (K[-]4) If¢ f- F, then K <;;; K[-]F.

(K[-]5) If A E K\K[-]F, then there is some subsetS of J( such that I<[-]F <;;;SandS It' F, butS U {A} f­ F.

(K[-]6) If F1 =K F2, then K[-]F1 = K[-]F2 .

Here r f- F represents that there is some A E F such that r f- A; F1 =K F2 represents V X <;;; K(X f- F1 ,__. X f- F2).

A model for package contractions based on partial meet method has been constructed and the representa­ tion theorem for these basic postulates was also ·given in [Fuhrmann and Hansson 1994 ]. Although two tentative generalizations of AGM's supplementary postulates were given in the same paper, unfortunately, one of them was found to be inconsistent with the basic ones(personal communication).

Another kind of multiple contractions, called the gen­ eral contraction introduced by [Zhang 1996], is moti­ vated by a quite different idea. It seems to lay more emphasis on 'contracting' rather than 'removing'. The principal idea of general contractions is contracting a be­ lief set so that the resulting set is consistent with a set of sentences.

Formally, for a given belief set K, a function I\ 8 : :F--+ :F2, is a general contraction operation over !{ if it satisfies the following postulates:

• (J< e 1) K e F=Cn(I< e F).
• (K e 2) K e F <;;; I<.

(I< 8 3) If F U K is consistent , then K 8 F = I<.

(I< 8 4) IfF is consistent, then Fu(I<e F) is consistent.

• (I< 8 5) VA E K(F f- ·A--+ K <;;; K 8 F +A).

(K 8 6) If Cn(Fl) = Cn(F2), then K 8 F1 = K 8 F2.

(K 8 7) K 8 F1<;;;K e (F1VF2)+F1.

(I< 8 8) If F1 U (K 8 (F1 V F2)) is consistent, then I\ H ( F1 V F2) <;;; K 8 F1.

Here F1 V F2 = {A V B : A E F1 1\ B E F2}.

Among the above postulates , ( K 8 1 )-(I< 8 4) and (I< 8 6) are direct generalizations of the AGM postulates (I< -1)-(K -4) and (I{ -6) , respectively. The postulate (K 8 5), being claimed as the generalization of AGM's Recovery (the most controversial among the AGM pos­ tulates for contractions), seems to be stronger than its original. Here we provide an equivalent property, called Saturation, which somewhat supports the postulate.

Lemma 2.1 If e satisfies (I<e 1)-(K8 4) , then (Ke .5) is equivalent to the following property:

2 In the following , J( will be omtted from 'Ke ' for con vemence.

(e Sat) (I\ 8 F +F) n K ~ K 8 F(Saturation).

Saturation expresses the idea that if a piece of knowl­ edge could be kept in the new knowledge base, it does not need to be abandoned when the contraction is con­ ducted.

The postulate (I( 8 6) seems to be too weak when we consider the relationship between general contrac­ tions and package contractions. Instead, the following stronger principle is suggestible:

(8 6s) If VA E I\(F1 1- ·A..-.. F2 1- ·A) , then K 8 F1 = I< H F2.

It is obvious that (I( 8 6s) implies (I( 8 6), but the in­ verse needs the presence of (I( 8 7) and (I< 8 8).

The postulates (K 8 7) and (K 8 8) are clearly non­ intuitiw. A slight improvement may be done by giving the following alternatives:

(K 8 7') If F1 ~ F2 , then K 8 F2 ~ K 8 F1 + F2 .

(I{ 8 8') If F1 ~ F2 and F2 UK 8 F1 is consistent, then K 8 F1~K 8 F2.

In fac:t , (I\ e 7) and (I( 8 8) are equivalent to (I( 8 7') and (I( 8 8'), respectively, by noting the fact that F1 V F2 H Cn(Fl) n Cn(F2).

In this paper we will call (8 1)-(8 5) and (8 6s) the basic postulates for general contractions , whereas (8 7 1 ) and ( 8 8') the supplementary postulates.

An explicit construction of a general ·contraction has been given in [Zhang 1996 ] (also see section 4 of this paper) , which shows that the set of postulates for gen­ eral contractions is consistent , but it does not lead to a representation theorem for this sort of multiple contrac­ tions .

Despite the differences in motivation for two types of multiple contractions , they are closely related. In fact , the general contraction can be defined by the pack­ age contraction and , inversely, the latter can be par­ tially defined in terms of the former. To show this, let us start with two notations . For any F E F,

Proposition 2.2 Let J( E JC and ' [-]' be a package contraction function over K . Define a general contrac­ tion fun ction '8 ' over f{ a.s follows: for any F E F ,

If ' [ -] ' satz.s.fie.s all the basic postulates for package con­ trartion.s , thrn ( e ' satisfies all the basic postulates for general rontrartions.

Proposition 2.3 Let :Fv = {F E :F : VA , B E F(A V B E F)} and 8 be a general contraction function over !\. Defin e a package contraction function[-] : :Fv---> :Fv over]{ a.s follows : For any F E Fv ,

If 8 satisfies all the basic postulates for general contrac­ tions, thrn [ -] satisfies all the basic postulates for pack­ age rontractions.

2.2 Multiple Revision

There are few investigations for multiple revision. A reason for this may be that it is widely agreed that revi­ sions can be reduced to contractions. As a kind of gen­ eralizations of AGM revision operation, [Zhang 1995 ] [Zhang 1996] introduced a multiple revision function '® ', called general revision. Formally, for any belief set K, a function ® : :F ____, :F is a general revision function over K if it satisfies the following postulates:

(K ® 1) K ® F=Cn(K ® F).

(K ® 2) F~ K ® F .

(K ® 3) K ® F~K+F.

(K ® 4) Iff{ U F is consistent , then K + F ~ K ® F.

( J( ® 5) J( ® F is inconsistent if and only ifF is incon­ sistent.

(K ® 6) If Cn(Fl) = Cn(F2), then K ® F1 = K ® F2.

(K ® 7) K ® (F1UF2)~K ® F1+F2.

(K ® 8) If F2U(K® Fl) is consistent, then K ® F1 +F2 ~ K ® (F1 U F2) .

In analogy with Levi identity and Harper identity in the AGM framework , the relationship between the gen­ eral contraction and the general revision has been estab­ lished by the following definitions :

(Def 8 ) K 8 Fd~(K ® F)nK

Theorem 2.4 {Zhang 1996} If 8 (® ) satisfies (!{8 1)­ (K 8 8)((K ® 1)- (K ® 8)) , then ® (8 ) obtained from Def® (De/8 )) satisfies (I( ® 1)- (I< ® 8)((!( 8 1)­ (K 8 8)) .

This result enables us to lay more emphasis on the task of characterizing contraction operations.

3 Partial Meet Model for General Contractions

As mentioned above , the general contraction is successful in generalizing the AGM supplementary postulates, but fails to give a representation result whereas the package contraction is just opposite. In this section we try to give a representation theorem for the general contraction.

According to the relationship of package contractions and general contraction, a partial meet model for the general contraction can readily be constructed. The only problem is whether and how this kind of model can be suitably restricted so that the supplementary postulates for general contractions are also satisfied. This section will try to give an answer for it.

In the AGM theory the notation K l_ A represents the set of maximal subsets of K that does not imply A. This notation can be easily generalized to the following form:

Definition 3.1 For J{ E K and F E :F, K' E KIIF if and only if

1. K' ~ K;

2. F U K' is consistent, and

3. 't:JJ{" ~ K(K' C /{ 11 --+ !{' U F is inconsistent).

It is easy to see that KII{A} = J{ .l --,A. The following notations are useful.

Definition 3.2 For any J{ E K, a selection function for J{ is a function S : UK --+ 2uK such that

Definition 3.3 An operation K 8 : :F --+ :F is a partial meet contraction over]{ if and only if there exists a se­ lect function S such that for any F E :F,

We will omit J{ form 'Ke '.

A similar proof of representation theorem for the pack­ age contraction leads to the following representation re­ sult for the general contraction on the basic postulates.

Theorem 3.4 For any belief set J{ I e satisfies all the basic postulates for general contractions if and only if it is a partial meet contraction.

Definition 3.5 Let ]{ E K. A selection function S for J{ is complete if for all H E UK

A partial meet contraction function is complete if it can be generated by such a selection function.

Definition 3.6 Let J{ E K. A selection function S for J{ is (transitively) rational when there is a (transitive) relation ::=; on UK such that for any H E UK ,

The contraction function generated from such S is called a (transitively) relational partial meet contraction func­ tion.

One of the main results in this paper is the following representation theorem.

Theorem 3. 7 (The first representation theorem) For any belief set J{ I e satisfies postulates (K e 1)- (I< e 8) if and only if8 is a complete transitively rational partial meet contraction function.

It should be remarked that there is an important dif­ ference between representation theorems of general con­ tractions and of singleton contractions that the com­ pleteness of selection functions is needed just one direc­ tion in singleton contractions rather than both.

The following lemmas are found to be critical for the proof of the theorem.

Lemma 3.8 Let J{ E K and S be a complete select func­ tion forK . For any 6. E UK and FE :F, ifF is consis­ tent and n S(KIIF) ~ 6. , then 6. E S(I<IIF) or 6. = K.

Lemma 3.9 Let K E K, F E :F and r be a closed subset of K. IfF u K is inconsistent but r u F is consistent, then

Lemma 3.10' If 8 is a complete relational partial meet contraction, the,n ( J{ e 7) holds.

Lemma 3.11 LetS be a complete selection function for K. If Ft ~ F2 and F2 U (n S(KIIFt)) is consistent, then (I<I1F2) n S(KIIFt) =f ¢

Lemma 3.12 Let S be a transitively rational selection function. If Ft ~ F2 and (KIIF2) n S(KIIFt) =f ¢, then

Lemma 3.13 If 8 is a complete transitively rational partial meet contraction, then ( J{ e 8) holds.

There are two limiting cases of singleton contractions: maxichoice contractions and full meet contractions, be­ ing investigated in the AGM theory, which are viewed as the lower and upper bounds of partial meet contractions , and therefore, are useful sometimes for understanding contraction operations sometimes. Here we present two similar representation results for general contractions. Assuming that the maxichoice contractions and the full meet contraction for general contractions are defined as usual, then we have

Proposition 3.14 A function 8 : :F --+ :F is a maxi­ choice contraction over a belief set /{ if and only if it satisfies (K 8 1) -(K 8 5), (K 8 6s) and the condition: If A E J{ \ J{ 8 F , then there exists B E J{ such that F f- --,B and A --+ B E K 8 F.

Proposition 3.15 A function 8 : :F--+ :F is a full meet contraction over a belief set J{ if and only if it satisfies (K 8 1) -(K 8 5), (K 8 6s) and the condition:

If F1 ~ F2 and F1 UK is inconsistent, then K 8 }\ ~ K e F2.

4 Limited Postulation for General Contractions

In this section, we use the approach of nice-ordered par­ tition models, developed by [Zhang 1996 ), to show why we think that the postulates available for the general contraction are insufficient to characterize infinite belief changes. An additional postulate for the general con­ traction is introduced and its representation theorem is provided.

In order to construct a model for the general contrac­ tion operation, [Zhang 1996 ) introduced the notion of nice-ordered partition with the motivation of capturing the idea of degrees of reliability of information.

Definition 4.1 {Zhang 1996 J For any belief set J{ , let P be a partition of J{ and < a total-ordering relation f"l P. The triple I:= (K, P, <) is called a total-ordered partition (TOP) of I<. For any p E P , if A E p, p is called the rank of A, denoted by b(A) .

A total-ordered partition I: = (K, P , <) is a nice­ ordered partition {NOP) if it satisfies the following Logical Constraint: '

The idea underlying this definition is that different pieces of knowledge in a knowledge base are accepted with different degrees of reliability. It could be supposed that the knowledge base has been grouped according to degrees of reliability of knowledge. The rank of a piece of knowledge represents the group it belongs to. Ac­ cording to the above definition the less rank a sentence is, the higher degree of reliability it has. The relation­ ship between NOP and epistemic entrenchment has been studied in [Zhang 1996 ]. Roughly speaking, the latter can be viewed as a special case of the former in some sense.

An explicit construction for multiple contraction func­ tions is then given as follows :

Definition 4.2 [Zhang 19961 Let E = (K, P , <) be an NOP of a belief set K . Define a fun ction 8 : :F ---+ :F, called NOP contraction over K , as follows: for any FE F

i). IfF U I< is consistent , then K e F = K ; otherwise, ii). B E K S F if and only if B E f{ and there exists A E K such that F f- ·A and

In particular, when F is finite, then B E K e F if and only if

The following result expresses the fact that an NOP con­ traction must be a general contraction and, therefore, the set of postulates for general contractions is consis­ tent.

Theorem 4.3 [Zhang 19961 IF 8 is an NOP contrac­ tion over J( ' then it satisfies (I< e 1) - ( J{ e 8).

A natural question is now whether a general contrac­ tion funct ion must be an NOP contraction. For the finite case the following lemma gives an affirmative answer.

Lemma 4.4 If '8 ' is a general contraction function over a belief set J{ , then there exists a unique NOP, ~ = (K, P, <) , of]( such that for any finite set F of sentences, B E K 8 F iff B E K and

For the infinite case, however , the answer is negative. Before we illustrate why, let us first introduce a variant of NOP contraction functions.

Definition 4.5 Let E = (K, P, <)be an NOP of a belief set K . Defin e a .contraction function 8 : :F __.. :F over I< as follows: for any F E :F

i). IfF u K is consistent, then K e F = K , otherwise; ii). B E K e F if and only if B E K and there exists A E K such that F f- ·A and

It is easy to see that two types of NOP contractions agree on finite arguments. The following example shows that they branch in the infinite case.

Example 4.1 We consider a propositional language {, only including propositional variables po , P1 , · · ·. Let }( = Cn( {po, p1 , · · ·} ) . Constructing an NOP P of K as follows: 1. P = {P-oo } U {P-n : nEw} , where

• ii) For any A E }(such that Art Cn(¢) ,
• If A = Pi 1 1\ · · · 1\ Pin , then A E P-min{i 1 ,. . . ,in} ' specially, Pi E P-i ; otherwise,
• If A' is the unique complete disjunctive normal form of A , then each disjunctive branch of A' is of the form:

where * is empty or negative '· '. Since A E K, there exists a disjunctive branch of A' which be­ longs to K . Suppose that all such branches have been assigned into P-i., ···, P -Jm , respectively, then A E P_m,.x{J. ,. .. ,jrn}·

2. For any nEw, P-oo < P-n· For any m , n E w, P-m < P-n if and only if m > n.

It is not difficult to show that E = (K, P , <)is an NOP of K.

According to definitions of e and 8, we have

• (1). IfF= {·p; 0 , .. ·,·Pin}(io < ... < in) , then Ke F=Ke F=Cn({p;n+"Pin+» · · ·} U F) n K.

Now we change E into E' in this way of bringing all the formulas with the form Po Vpi(i = 1, 2, ···)into P_00 and doing the corresponding changes in order to make the resulting partition an NOP.

It is not difficult to check that if F = {'Pia, 'Pi" · · -} (0 < i 0 < i 1 < ··-),then (with respect to the NOPE'):

The above example and Lemma 4.4 tell us the fact that the available postulates for general contractions are not sufficient to uniquely determine an NOP contraction as a general contraction function is given. We need some additional principles to describe the relationship between a belief set contracted by a infinite set of sentences and by its finite subsets. In fact, we can easily see from the above example that there is a situation in which an in­ finite set is inconsistent with all the contractions by its finite subsets (noting that it must consistent with the contraction by itself) . In this case the available postu­ lates for general contractions are insufficient to restrict the relation between the contraction by the infinite set and the ones by its finite subsets .

A reasonable thought is to assume that the contrac­ tion by a infinite set is some limiting case of the ones by its finitP subset. This motivates us to introduce the following Limit Postulat e for the general contraction:

Let Cr = {F : F t;;; Cn(F) and F is finite} ,

In other words, B E !{ 8 F if and only if there exists a ~nite subset F o~ Cn(!) such that for e~ch finite subset F' of Cn(F) , ifF t;;; F', then BE I\ 8 F'.

An equivalent assumption for the general revision is readily given in terms of (Def8 ) and (Def@) as follows (an easy check is necessary):

Before we switch to present the representation theo­ rem for the Limit Postulate we have to make a choice between the two types of NOP contractions (see Defi­ nition 4.2 and 4.5). By comparing Equations 2 and 3 we find that e is more acceptable than e. Note that even though the proposition Po has the lowest degree of reliability in the old knowledge base , the agent believes extremely in Po V Pi ( i = 1, 2, · · -). Therefore, when the fact tells that some p:s are false , he will conclude that Po is true. In the remaining part of this paper , an NOP contraction will only refer to e.

TheorP.m 4.6 If e is an NOP contraction function , then e satisfies (I< 8 LP) .

Theorem 4. 7 Let 8 be a general contraction function over f{ . If 8 satisfi es (I< 8 LP) , then there exists an NOP, ~ = (K, P , <), off{ such that 8 is exactly the NOP contraction generated by ~.

The Lemma 4.4 and the above theorems lead to an­ other main result of this paper:

Theorem 4.8 (The second representation theorem) For any belief set f{ , 8 satisfies ( [{ 8 1)- ( [{ 8 8) and (I< 8 LP) if and only if 8 is an NOP contraction over J{.

5 Conclusions and Future Work

Two representation theorems for the general contraction are presented in this paper. The first one illustrates that the AGM partial meet contraction can be smoothly ex­ tended to the case of multiple changes. The second one persuades us that confining our attention only to the generalization of postulates for singleton belief change would fail to get a full characterization of infinite be­ lief changes. This result also provides a powerful tool to investigate the connection between belief revision and non-monotonic reasoning. In (Zhang et al. 1997] , we in­ troduced a non-monotonic logic the semantic of which bases on the theory of multiple belief revision and one of the inference rules in which, finite supracompactness, is just the counterpart of the Limit Postulate.