Comparing strengths of beliefs explicitly

Abstract

-Inspired by a similar use in provability logic, formulas p ÂB q and p <B q are introduced in the existing logical framework for discussing beliefs to express that the strength of belief in p is greater than (or equal to) that in q. This explicit mention of the comparison in the logical language aids in defining several other concepts in a uniform way, viz. older and rather clear concepts like the operators for universality (which possibilities ought to be considered), together with newer notions like plausibility (in the sense of 'more plausible than not') and disbelief. Moreover, it assists in studying the properties of the concept of greater strength of belief itself. A heavy part is played in our investigations by the relationship between the standard plausibility ordering of the worlds and the strength of belief ordering. If we try to define the strength of belief ordering in terms of the world plausibility ordering we get some undesirable consequences, so we have decided to keep the relation between the two orderings as light as possible to construct a system that allows for widely different interpretations. Finally, after a brief discussion on the multi-agent setting, we move on to talk about the dynamics - the change of ordering under the influence of hard and soft information. Index Terms-doxastic logic, belief, disbelief, plausibility

I. INTRODUCTION

Being subject to doubts and dilemmas while making decisions is like second nature to the human mind. The difference in the strengths of beliefs of an agent regarding the occurrence of different events may clear doubts of this kind. In betting on games, people make their choices for putting their money on different teams, based on their strengths of beliefs about which team will win. Similarly, when voting, one’s preference for the candidates is again based on the strength of beliefs about one candidate’s ability to perform compared to the others. Thus, this notion is inherently present in various fields of research like decision theory, game theory and others.

Before proceeding further, let us first consider the following real life situation where comparison of strength of beliefs plays a key role in decision-making for recruitments.

Alice often has applications for jobs in her departmental store. The first time Burt and Cora apply. Alice believes both can do the job, but her belief in Cora being able to do it is stronger than that Burt will be able to do it. She chooses Cora.

The second time Deirdre and Egon apply. She believes that Egon can do the job whereas she is is ambiguous about Deirdre: she neither has the belief that Deirdre can do it, nor that she cannot. She chooses Egon.

The third time Fiona and Gregory apply. About both she is ambiguous, but her strength of belief in Gregory being able to do it is stronger than that in Fiona. She chooses Gregory, maybe she has to help him along a little.

The fourth time the applicants are Harold and Irma. She believes neither can do the job. She decides to take neither and hold another round of applications.

All these situations regarding the belief states of Alice can be aptly described, if we talk not only about her beliefs but also compare the strength of her beliefs in the applicants. One can argue that these situations can be described by the very well-studied notion of preference, but the essence of describing the mental states of Alice will be lost then. This paper addresses the notion of comparison of the strength of beliefs of an agent directly. A great volume of literature and extensive philosophical debates are available on reasoning about knowledge and belief of agents. This paper adds a new notion to this line of work, viz. comparing the strengths of beliefs, and very pertinently, doing this in a qualitative manner. The ordering introduced here operates on formulas.

The introduction of explicit notions of ordering for comparing strengths of beliefs in the logical language has various applications. It aids in defining several other concepts in a uniform way, viz. older and rather clear concepts like the operators for universality, together with newer notions like plausibility and disbelief. Moreover it assists in studying the properties of the concept of greater strength of belief itself. In the semantics, the question - which worlds are going to be a part of the model, gets in our approach a clearer formal and intuitive understanding. It also becomes more evident that the universality operator cannot be identified with the knowledge operator even if they both share the S5-properties. Above all it has its advantages in an explicit study of the properties of the orderings themselves, semantically and axiomatically. All these investigations can be carried over to a dynamic setting. A pleasant fact is that we can fit the system easily into the framework of dynamic epistemic logic ([ 1 ], see also [ 2 ]) as explained in section III.

As mentioned in a brief interlude later, the explicit belief ordering also aids in providing an additional feather to the already existing close relationship between beliefs and preferences which is thoroughly discussed in [ 3 ].

Before entering into the actual study, let us first discuss the previous work on provability logics which inspired this idea of explicit belief ordering. In Provability Logic, an extensive overview of which can be found in [ 4 ], ¤' is interpreted as 9x P roofPA(x; '), which means that there is a proof x in the axiomatization PA (Peano Arithmetic) for the statement '. With PA understood, we also write it in the form - 9x P roof (x; '). In this framework, to handle Rosser’s form of incompleteness, one introduces witness comparisons of proofs with formulas like ¤' 4 ¤Ã := 9x(P roof (x; ') ^ 8y < x :P roof (y; Ã)), which is interpreted as that ' has a proof that is at least as small as any (possible) proof of Ã. Similarly, ¤' Á ¤Ã := 9x(P roof (x; ') ^ 8y · x :P roof (y; Ã)) means that ' has a proof that is smaller than any (possible) proof of Ã. Logics for these witness comparison formulas were successfully introduced by [ 5 ], and the completeness proof for this logic was simplified in [ 6 ].

Motivated by the ideas above, formulas ' ÂB à and ' <B à are introduced in the existing logical framework for discussing beliefs to express that the strength of belief in ' is greater than (or equal to) that in Ã. We should note here that in the Rosser framework proofs of ' and à are compared only if one of these proofs really exists, whereas strengths of beliefs are also discussed when neither ' nor à are really believed, which makes them less concrete, and therefore we express their comparison as ' ÂB Ã, rather than B'  BÃ. As mentioned earlier, these formulas can be used to express notions like ‘disbelief’ (the inclination to believe in :' is greater than the inclination to believe in '), and its dual ‘more plausible than not’, which can be represented by :' ÂB ' and ' ÂB :', respectively.

Let us now mention some related works in this area. In [ 7 ], [ 8 ], orderings of formulas are considered but their interpretations are probabilistic in nature. A binary sentential operator is introduced in the language with the intended interpretation ‘at least as probable as’. While [ 8 ] takes the explicit ordering operator in a simple language consisting of the truth-functional connectives only, [ 7 ] discusses this issue in a modal setting. Related as well are Lewis’s proposal for a plausibility ordering of formulas [ 9 ] and Spohn’s work on giving plausibility ordering of possible worlds in terms of ordinal functions [ 10 ]. More recently, we find some similar work in the economics literature [ 11 ]. Also, the notion of epistemic entrenchment [ 12 ] gives a syntactic ordering of formulas, which is studied in connection with belief revision. The ordering influences the abandoning and retaining of formulas when a belief contraction or revision takes place. In our setting the dynamics operates rather differently, as the reader will see.

With this background, we now provide a brief summary regarding the structure of this paper. Explicit beliefordering over formulas is introduced in section 2. Several possible interpretations of the belief-ordered formulas, viz. plausibility and disbelief are discussed, together with the inter-relationship of these ordering formulas and safe belief, and also, preference. Complete axiomatizations of the new belief logic with explicit ordering (KD45¡O), with safe belief added (KD45¡OS), plausibility logic (P -logic), logic of belief and plausibility (BP -logic) and logic of belief and disbelief (BD-logic) are provided. The section ends with a short discussion on the multi-agent setting. Section III brings in dynamics to the whole framework and discusses the influence of hard information as well as soft information over these ordering formulas, and provides complete axiomatizations to the dynamic logics under consideration. The conclusions are drawn in section IV.

II. COMPARING STRENGTH OF BELIEFS EXPLICITLY Modal logic is a useful tool to study knowledge and belief of human agents, which has been a main issue of concern to philosophers as well as computer scientists. Von Wright’s work [ 13 ] is generally accepted as initiating this line of research, which was further extended by [ 14 ]. Subsequently a huge research area has been developed, trying to provide answers to various philosophical issues as well as aiding into the development of several areas of computer science, like distributed systems, security protocols, database theory and others.

Possible-world semantics [ 15 ] has been used to model knowledge as well as belief. An extensive discussion together with all pre-requisite definitions can be found in [ 16 ]. In this work we are only concerned with beliefs of agents, comparison of their strengths as well as some related notions like universality, safe beliefs, plausibility, disbelief and others. Various debates and discussions are still going strong among the philosophers regarding the axioms that characterize belief - for this paper we will stick to the KD45-model of belief.

In the following, we talk about Kripke structures as well as the plausibility models [ 2 ], [ 17 ] as and when needed while talking about beliefs. The readers should note that plausibility models are more general in nature in the sense that one can always build up a KD45 Kripke structure from them as described in [ 17 ].

With this brief overview, we now move on to introduce explicit ordering of beliefs in the logical language, which is the essential new feature of this paper. This explicit mention of such comparison of beliefs provides an informative and uniform way to discuss certain relevant issues like disbeliefs, plausibility and others.

To introduce this comparison of strengths of beliefs explicitly in the logical language, we add new relation symbols to the existing modal language of belief to form the language of Belief logic with explicit ordering (KD45 ¡O ), whose language is defined as follows:

Definition II.1 Given a countable set of atomic propositions

©, formulas ' are defined inductively:

' := ? j p j :' j ' _ ' j B' j ' <B Ã j where p 2 ©.

The intuitive reading of the formula B' is “' is believed”, and that of ' <B à is “belief in ' is at least as strong as belief in Ô. We introduce the notations ' ÂB à for (' <B Ã) ^ :(à <B ') and ' ´B à for (' <B Ã) ^ (à <B '). Intuitively, they can be read as “belief in ' is stronger than that in Ô and “belief in ' and à are of same strength”, respectively. We now move on to define a model for this logic.

Definition II.2 A KD45 ¡O model is defined to be a structure

M = (S; ·; ¸B ; V ), where S is a non-empty finite set of states, V is a valuation assigning truth values to atomic propositions in states, · is a quasi-linear1 order relation (a plausibility ordering) over S, and ¸B is a quasi-linear order relation over P (S), satisfying the conditions 1) If X µ Y , then Y ¸B X

2) If B is the set of all ·-minimal worlds (the set of most

plausible worlds, called the center), then B µ X and

B 6µ Y imply X >B Y , where X >B Y iff X ¸B Y

and not (Y ¸B X ).

3) If X is non-empty, then X >B ;.

The first condition says that larger sets of worlds are more plausible, the second one that the sets containing the center are more plausible than those not containing it, and the third one that non-empty sets are more plausible than the empty set. Truth on the center suffices to make an assertion to be believed. Note that all the models are considered to be finite. This assumption ensures the existence of minimal worlds in terms of the plausibility ordering of the model. The truth definition for formulas ' in a KD45 ¡O model M is as usual with the following clauses for the belief and ordering modalities.

M; s j= B' iff M; t j= ' for all ·-minimal worlds t.

1A binary relation · on a non-empty set S is said to be quasi-linear if it is reflexive, transitive and linear, i.e. a total pre-order.

M; s j= ' <B Ã iff ft j M; t j= 'g ¸B ft j M; t j= Ãg.

We consider <B to be a global notion, if ' <B Ã is true anywhere in the model, it is true everywhere. So, it is either true or false throughout the whole model; <B is a global notion like B. Of course, being global in the model is strongly connected with introspection. From the definition of ÂB , it follows that, M; s j= ' ÂB Ã iff ft j M; t j= 'g >B ft j M; t j= Ãg.

Thus, ÂB is also a global notion. We will now show that the universal modality U can also be expressed in KD45 ¡O . The modality E' (the abbreviated form of :U :') can be defined as ' ÂB ?, and hence U ' itself as ? <B :'. To clarify matters we should mention here - U ' expresses that ' is true in all possible worlds in the model, whereas E' stands for existence of a possible world in the model where ' is true. The formula ' ÂB ? which defines E' expresses clearly which worlds should be considered in the model: those worlds of which the existence is expressed by a positive strength of belief, those possibilities which the agent does not want to exclude. Evidently, we have, M; s j= U ' iff M; t j= ' for all worlds t.

Thus U is definable in the language above, but to get the properties of the universal modality, we will need to have the S5-axioms that hold for U [ 18 ] plus the axiom B' ! U B', which expresses that B is a global notion in a model where U expresses universality. In such a model there is only one center.

There are various possible ways of interpreting the formula ' <B Ã in plausibility models expressing the belief modality. The foremost question is whether to try to define semantically ' ÂB Ã in terms of the plausibility ordering of the worlds. If one wants to base the strength of belief ordering on the plausibility ordering of the worlds, then immediately the following option comes to mind: the interpretation of ' ÂB Ã can be that there exist '-worlds which are more plausible than any Ã-world (similar to the proposal in [ 9 ]). For ' <B Ã it can be given as follows: for each Ã-world there exist '-worlds which are at least as plausible. If one does this however, B' becomes equivalent to ' <B :?. In fact, no distinction in strength of belief can be made between propositions which are believed. This is not at all our aim. A more pleasurable consequence of this definition is that conditional belief BÃ' can equivalently be expressed as - (Ã ^ ') ÂB (Ã ^ :'). Ultimately though we think that the price is too high: this interpretation of the ordered formulas gives rise to more unintended validities in the logic KD45¡O (cf. section II-C). There are more sophisticated reductions of strengths of beliefs to the plausibility ordering of the worlds but we think that they will all have undesirable consequences. This is only partly due to the fact that belief is identified with truth in the most plausible worlds, which seems necessary for a dynamic interpretation. To do away with this issue we decided to define another set-plausibility ordering ¸B between the sets of worlds in the plausibility models. We have put very minimal requirements on this ordering. In fact, as we will see in section II-B, belief can be interpreted in terms of belief ordering and safe beliefs. How this will relate the world ordering and the set ordering is an interesting study, but we leave it for the future.

We should mention here that the idea of modeling epistemic notions in terms of set orders is not really new. In [ 19 ], [ 20 ], preferential structures are considered where a preference ordering over worlds is lifted to an ordering of sets of worlds. Plausibility measures are considered in [ 21 ] to give a semantics of default logic. These measures can be identified with a partial ordering on sets of worlds and they also provide an interpretation of the notion of beliefs. We are not going into a detailed comparison of these works with ours due to lack of space, but just note that an essential difference is that in our case the ordering of the sets of worlds is only partly determined by the ordering of the worlds.

Alice’s belief states (as described in the introduction) can now be formally presented as follows: suppose each of the applicants’ names denotes the proposition that “he (she) can do the job”. Cora ÂB Burt in the first case; (B(Egon) ^ :B(Deirdre) ^ :B(:Deirdre)) implies that Egon ÂB Deirdre in the second case, with the third case simply being Gregory ÂB Fiona again, and the fourth one, B(:Harold)^B(:Irma). The readers can easily see that in the second case there is some reasoning going on which leads to Egon being given the job, because Alice’s belief in the ability of Egon is stronger than her belief in the ability of Deirdre. Even in the fourth example where Alice believes that both Harold and Irma are unable to perform, her belief in the ability of one might be higher than that of the other. Then, if forced to choose, she could do without another round of applications.

A. Axioms and Completeness

Let us first look into some interesting validities of this logic. ² (' ÂB Ã) ! E(' ^ :Ã) ² ' <B ' ^ Ã ² ' _ Ã <B ' ² B(' <B Ã) ! (' <B Ã)

Before providing a complete axiomatization of KD45¡O, we discuss the motivations behind some of these axioms. Since, by the set-ordering relation in the KD45¡O model, ¸B is a reflexive, transitive and connected relation over P(S), and >B is the corresponding strict ordering, the following axioms need no introduction: ' <B ' (refl-axiom) (' <B Ã) ^ (Ã <B Â) ! ' <B Â (' <B Ã) _ (Ã ÂB ') (lin-axiom)

From these axioms, it follows that, (trans-axiom)

and so we get the transitivity of >B. We have already seen that E' can be defined as ' ÂB ?, because of the 3rd condition that >B satisfies in the model. Using lin-axiom it is easy to show that U ' is equivalent to ? <B :'. The following axiom takes care of the 2nd condition. Since the ordering formulas are either globally true or globally false in the model, we have: (' <B Ã) ! B(' <B Ã) (' ÂB Ã) ! B(' ÂB Ã) (intros-axiom1) (intros-axiom2)

It immediately follows that,

:(' <B Ã) ! B:(' <B Ã) :(' ÂB Ã) ! B:(' ÂB Ã) The inverses of all these implications above follow from the lin-axiom. This means that all these ordering statements can be considered to be B-statements, i.e. ' <B Ã, ' ÂB Ã, U ', E' are all B-statements. As a result, the inclusion formula concerning the belief and the universal modality, viz. U ' ! B' also follows. The following axiom and rule take care of replacement with equivalent formulas in the ordering formulas: (U <B -axiom)

We can conclude then

which means that logically equivalent formulas can be substituted for each other in the ordering formulas as well and hence everywhere. We now have the gen-rule for the universal modality, the K-axiom for U also follows from these principles. We move on to get the other sound ordering axiom, which will help us to get the S5-properties of the universal modality U [ 18 ]. It is: The existence axiom is basically the equivalent ordered formula for U ' ! '. We end with the axiom which forces the KD45¡O models to have a unique center B and hence makes B a global property.

EB' ! B'

From this the principle B' ! U B' readily follows. The transitivity and the symmetry axioms for U follow because of the very significant property of U ' being a B-statement, the un.center-axiom applies to U -statements as well.

Thus we have the following theorem which is the most basic and important result of this work. (' <B Ã) ^ (Ã <B Â) ! ' <B Â

Proof: The readers can easily verify the soundness of these ordering axioms. The U <B -axiom is covered by property 1 of Definition II.2, existence axiom by property 3, and the center axiom describes property 2. With U and E defined as indicated previously, one can easily show that the S5-axioms are derivable for U . It is also not very hard to show completeness using finite sets of sentences.

Assume 0KD45 ¡O '. We will have to construct a countermodel to ' as a KD45 ¡O -model. We take a finite adequate set © containing '. In this case an adequate set will be: a set of formulas that is closed under subformulas containing with each formula à (a formula equivalent to) :Ã, containing with Bà and B (a formula equivalent to) B(à ^ Â) and a formula (equivalent to) B(à _ Â). We also need © to contain with each formula B' a formula (equivalent to) U B'. Finally, © contains B> and B?. It is easy to see that any finite set is contained in a finite adequate set. We use the Henkin method restricted to ©. Consider the m.c. (maximally consistent) subsets of ©. In particular consider such an m.c. set ©0 containing :'. When we now refer to U à we mean its translation into KD45 ¡O . It can be shown that the S5axioms to hold for this translation. The proof is made more perspicuous by referring to U .

The relations RB and RU are defined as follows: P RBQ P RU Q iff (1) for all B' in P , ' as well as B' are in Q,

(2) for all :B' in P , :B' in Q. iff (1) for all U ' in P , ' as well as U ' are in Q,

(2) for all :U ' in P , :U ' in Q We have to show that RU is an equivalence relation and RB a Euclidean sub-relation of RU . Finally, within one U equivalence class there is one, nonempty set of B-reflexive elements, which forms a B-equivalence class. Since all these things are standard we skip this part.

We now take the submodel generated by RU from ©0. The set of worlds W of our model will be the set of worlds in this submodel and the RB and RU the restrictions of the original RB and RU to this submodel. RU is now the universal relation.

As before, we write B for the set of RB-reflexive elements. The axiom B' ! U B' implies that this set is unique and a B-equivalence class. The world plausibility ordering is given as follows: any world in B is more plausible than any in W n B, and within these two sets, the worlds are equi-plausible. So, with respect to the modal operators B and U the model behaves properly, and we have a proper world-ordering as well. We will now have to order P(W ) in a proper way.

Let us say that à represents subset X of W if X is the set of nodes where à is true, which we may write as V (Ã) = X. We say that X is representable if for some Bà in ©, à represents X. By the conditions on © the representable sets are closed under unions and intersections, and contain W itself and the empty set.

The representable subsets of © are quasi-linearly ordered by the relation ¸1 defined by V (Ã) ¸1 V (Â) iff à <B  is true in the model, V (Ã) >1 V (Â) iff à ÂB  is true in the model. These follow from the first three ordering axioms.

Moreover, if V (Ã) µ V (Â) then V (Ã) ¸1 V (Â) (subset condition), by the axiom: U (Â ! Ã) ! Ã <B Â. Finally if V (Ã) properly contains B and V (Â) does not, then V (Ã) >1 V (Â) (sufficient belief condition) by the axiom: BÃ ^:BÂ ! Ã ÂB Â.

So, ¸1 behaves properly on the representable elements of P(W ). What remains is to extend ¸1 to an ordering ¸ with the right properties over all of P(W ).

Take an arbitrary subset X of W . We define R(X) to be the largest subset of X that is representable. That such a set exists follows from the fact that the representable subsets are closed under finite unions and the finiteness of the model.

We now define X ¸ Y iff R(X) ¸1 R(Y ). This immediately makes ¸ a quasi-linear order. That ¸ satisfies the subset condition follows from the fact that, if X µ Y , then R(X) µ R(Y ).

We will conclude this proof with a lemma showing that B is representable, i.e. B = R(B). From that result it follows that, if B µ X, then B µ R(X). This is clearly sufficient to ensure the sufficient belief condition. So, once we finish the proof of the following lemma, we are done.

Lemma. B is representable.

Proof of Lemma. Consider w not in B. Then it is not the case that wRBw. This means that, for some particular B(Ãw) in ©, B(Ãw) is in w but Ãw is not. Note that this implies that Ãw is true all over B. Consider the conjunction à of all Ãw for w in the complement of B. B(Ã) is a member of © while à is true in all elements of B, but is falsified at all elements u in the complement of B, since à implies Ãu and Ãu is falsified in u. We have shown that B is represented by Ã.

Since the counter-model constructed is finite, we also have that the logic KD45¡O is decidable. Before ending this section we mention some intuitively true formulas, which we did not need as axioms, but are definitely worth thinking about. One of them is, which says that if ' is true somewhere then :' is not as much to be believed as a tautology. The other direction of the implication can be derived. An equivalent formulation is, To make this true, the model needs an extra clause 4, saying that, This seems a very reasonable addition as it makes the models more symmetric. A more general version of this possible axiom is,

(' ÂB Ã) ! (:Ã ÂB :'). which, if considered definitely increases the already-existing probabilistic flavor of the axiomatization. Another possible principle with a similar flavor is

(' ÂB Ã) ! (' ^ :Ã) ÂB (Ã ^ :').

This one exemplifies the notion that if ' is more believed than Ã, then that should be based on the idea that the common part of ' and à is irrelevant in the estimation of their relative strengths of belief. Readers can note here that if we strengthen this formula above to its bi-implication, then (' ÂB Ã) ! (:à ÂB :') follows.

B. Safe Belief

The notion of ‘safe belief’ has been introduced in [ 17 ] which also corresponds to “Stalnaker knowledge” [ 22 ], where evidence is considered as true information. The authors gave this name to single out those beliefs “that are safe to hold, in the sense that no future learning of truthful information will force us to revise them.” The safe belief modality is generally denoted by ¤. Evidently, ‘safe beliefs’ are truthful (¤' j= ') and positively introspective (¤' j= ¤¤'), but not necessarily negatively introspective (in general, :¤' 6j= ¤:¤').

Adding safe belief to our ordering framework is interesting both from the technical as well as intuitive point of view. We already have an understanding of the interplay between beliefs and the comparison of strength of beliefs. Our study will be incomplete, if we do not investigate the lively relationship between the very relevant and important issue of safe beliefs together with our notion of belief orderings.

In the plausibility models, the truth definition of ¤' is given by the following clause: (' ÂB ?) ! (> ÂB :'), (' <B >) ! (? <B :'). if S 6= X then S >B X .

M; s j= ¤' iff M; t j= ' for all worlds t · s. which says that ' can be safely believed at some world s if it holds at all the worlds which are at least as plausible as s. In the following we will introduce the safe belief modality in the setting of KD45¡O, and give a complete axiomatization of this logic. The language of the logic KD45¡OS is defined as follows:

Definition II.4 Given a countable set of atomic propositions

©, formulas ' are defined inductively:

' := ? j p j :' j ' _ ' j B' j ¤' j ' <B Ã where p 2 ©.

We now present the axioms of the logic KD45¡OS. Together with the axioms and rules of the KD45-logic of beliefs, and the relevant ordering axioms, viz. refl, trans, lin, center, existence, U <B -axiom and the S4-axioms and rules for the safe belief ¤ operator, we will have the following extra axioms, (¤' ^ :¤Ã) ! (' ÂB Ã) (' <B Ã) ! ¤(' <B Ã) (' ÂB Ã) ! ¤(' ÂB Ã)

(¤order-axiom) (¤intros-axiom1) (¤intros-axiom2) In addition to all these, the following axiom relates the operator ¤ with B.

¤' ! B'

(¤B-axiom)

U ' ! ¤' The intros-axioms(1-2) and the un.center axioms of KD45¡O are derivable from KD45¡OS. We can also derive: Regarding the ¤order-axiom, it should be mentioned that, unlike belief (center axiom), relating safe belief and belief ordering in this manner may be considered questionable. It says that, if ' is safely believed and à is more strongly believed than ', then à can also be safely believed. This seems alright at a first glance, but if we consider the subjectivity of the ordering, this axiom may lead to some dispute. Still, technical reasons make it very desirable, the relationship between the world and set orderings becomes much closer, so we decided to keep this axiom. So, we have the following theorem.

Theorem II.5 The logic KD45¡OS is sound and its validities can be completely axiomatized by the following axioms and rules.

a) all KD45¡O axioms and rules b) S4-axioms and rules for the modal operator ¤ c) ordering axioms: ' <B ' (refl-axiom) (' <B Ã) ^ (Ã <B Â) !

' <B Â (trans-axiom) d) ¤' ! B'

e) inclusion rule:

' ! à (¤' ^ :¤Ã) ! (' ÂB Ã) (' <B Ã) ! ¤(' <B Ã) (' ÂB Ã) ! ¤(' ÂB Ã)

We should mention here that, according to [ 17 ], belief and conditional belief can be expressed in terms of knowledge and safe belief as,

BÃ' := K^ Ã ! K^ (Ã ^ ¤(Ã ! ')),

B' := B>', where K^ Ã := :K:Ã. They gave complete axiomatizations for conditional doxastic logic (logic of conditional belief) as well as the logic of knowledge and safe beliefs. We do not consider knowledge but for this part of the discussion it can be replaced by U . Neither do we talk about conditional belief here, but belief can be defined in terms of the existential modality and safe belief (i.e. in terms of safe belief and belief ordering) as follows:

B' := E¤'

Once we have in this manner the modal operator B as a defined concept, we can easily derive all its well-known properties in KD45¡OS, but if that holds fully for its relations with <B remains to be seen.

C. Plausibility

Comparing the strength of beliefs explicitly has its various advantageous applications. By plausibility of a proposition we generally mean that we tend to believe in its happening rather than its not happening. That is the interpretation we take here. Hence, in terms of ordered formulas, P ' can be expressed as ' ÂB :'. Of course, there are other possible notions of plausibility, but here we interpret P ' as ‘more plausible than not’. We now explore this notion of ‘plausibility’ in terms of belief ordering.

An important principle that will be valid for the plausibility operator P is U (' ! Ã) ! (P ' ! P Ã). This holds because if U (' ! Ã), not only will belief in à be at least as strong as in ', but U (' ! Ã) implies U (:à ! :'), so belief in :à is not greater than in :'. This leads to consequences like P (' ^ Ã) ! P '.

The reason to take the set semantics for ordering formulas (cf. Definition II.2) becomes clear. If we would adhere to the semantics we may have had for ÂB in terms of plausibility ordering for worlds (instead of sets of worlds), P ' would become equivalent to B', which obviously is undesirable.

One can just subdivide the most plausible worlds (the center) into more and less plausible ones to rectify this, but besides endangering the transition to dynamics this will not yet be really satisfactory in its own right. It will result in interpreting P ' into something like ‘' is weakly believed’. This would make the modal logic of P a normal modal logic (of weak belief). In particular P ' ^ P Ã ! P (' ^ Ã) would become valid, which is not very intuitive.

For example, you may judge it more plausible than not that your next client will be male. Similarly, you may consider it to be plausible that your next client will be a foreigner. But, it doesn’t follow that it is more plausible than not that the next client will be a foreign male, most of one’s foreign clients may be female.

We now move on to showing an independent axiomatization of the plausibility logic P . The language of the P -logic is given by

' := p j :' j ' _ ' j P '

We read P ' as “' is plausible”. As mentioned above, the intuitive meaning of P ' can be captured by the formula ' ÂB :', and as such, the truth definition of P ' in the KD45¡O model is given by,

M; s j= P ' iff ft j M; t j= 'g >B ft j M; t j= :'g.

Theorem II.6 P -logic is complete and its validities are com

pletely axiomatized by the following axioms and rules: (a) all propositional tautologies and inference rules (b) plausibility axioms:

P Ã ^ P ' ! P (Ã ^ P ') P Ã ^ :P ' ! P (Ã ^ :P ') P ' ! :P :'

P >

c) monotonicity rule:

if ' ! Ã then P ' ! P Ã

Proof: First of all, we show that any formula in P-logic is equivalent to a formula with P -depth at most one. For that purpose we first derive the following schemes: 1) P Ã ! (' $ '[>=P Ã]) 2) :P Ã ! (' $ '[?=P Ã])

Here, '[>=P Ã] means ' with > substituted for some occurrences of P Ã. We prove by induction on the complexity of formulas ' with possible occurrences of > and ?. In the base case, that is for the atomic propositions and propositional constants, the result follows immediately. Induction step. This is trivial for the boolean connectives. So, it suffices to prove it for P ' assuming it holds for '. From the induction hypothesis for the first scheme it follows that (P Ã ^ ') $ (P Ã ^ '[>=P Ã]) is provable. Now assume P Ã and P '. By an axiom P (' ^ P Ã) follows. From the fact just proved it follows that P ('[>=P Ã] ^ P Ã) and hence P ('[>=P Ã]). The proof for the second scheme is very similar.

To see that these schemes imply that each formula in P -logic is equivalent to a formula with P -depth at most one, just note that ` ' $ ((P à ^ ') _ (:P à ^ ')). Now, if we want to get rid of occurrences of P à in ' we can replace ' by ((P à ^ '[>=P Ã]) _ (:P à ^ '[?=P Ã])). By doing this consecutively for all occurrences of P à with no occurrences of P in à we obtain the desired result.

Next, we show that any consistent set has a model. Assume we have a consistent set in the P -logic which can be extended to a maximal consistent set ¡, say. Since we can restrict attention to formulas which are boolean combinations of atoms and formulas of the form P ' where ' no longer contains P , a maximal consistent set is essentially only a set of atoms, negations of atoms, such P '’s and :P '’s and their boolean combinations.

We now make a model in our sense where P ' gets interpreted as ' >B :'. The worlds will be simply defined by a number of atoms being true in it and the rest of the atoms false. Let us now consider the following model, M = (S; ·; ¸B; V ), where S is the set of all maximal consistent subsets. The ordering of the subsets is as follows: There are 5 equivalence classes in the ordering starting with the highest grade of believability. We take membership of those classes to determine the degree of belief in the sets. (1) The whole set, which is of course represented by >. (2) The sets represented by those ' for which P ' is in ¡ (except for >). (3) The sets represented by those ' for which :P ' is in ¡ as well as :P :'. (4) The sets represented by those ' for which P :' is in ¡ (except for ?). (5) The empty set, which is of course represented by ?. These are all possibilities because of axiom P ' ! :P :'. Finally we take B, the center, to be the whole set (so, there are no beliefs except the trivial one in >).

The two things we have to check are: First, that, if a set is in class (2), then any larger one will be in (2) as well (or in (1)). This follows from the monotonicity rule. Similarly for the other classes. Second, that, if a set X contains all of B, and another set Y doesn’t, then X > Y . That is trivial: X has to be B, the whole set, and Y isn’t.

As earlier, we can induce an ordering over all subsets satisfying the required conditions. All the single worlds have to be taken to be equally plausible, i.e. s · t, for all s; t 2 S. So, for each consistent set we can have a model in KD45¡O. So, the axioms and rules given in Theorem 2.6 axiomatize the P logic of ‘more plausible then not’. It is also worth-mentioning why (P ' ^ P Ã) ! P (' ^ Ã) will fail in general. There may be sets in (2), the intersection of which, is not in (2).

Evidently, P ' is a global notion - its value does not vary through the model. Again, P is clearly an introspective notion. Interestingly, the principles 4 and 5 for the modal operator P are derivable in this P -logic, but the K-axiom is not. That P ' ^ P Ã ! P (' ^ Ã) ought not to be a valid principle in the P -logic is clear if we interpret P ' as ' ÂB :'.

Let us finally note that an interpretation of P ' as ' as having probability more than 0.5 (or any other number between 0.5 and 1) leads to exactly the P -axioms provided one considers the probability statements themselves to always have probability 1.

We now consider a system having both belief and the plausibility operator, viz. the BP -system. This system will provide pointers to discuss logics of belief and disbelief in the next subsection. The language is that of the P -logic, together with the additional modal operator for belief, B.

' := p j :' j ' _ ' j P ' j B' Some validities of this logic in the KD45¡O model are, ² B' ! P ' ² P ' ! BP ' ² :P ' ! B:P '

Theorem II.7 BP -logic is complete and its validities are

completely axiomatized by the following axioms and rules:

a) all propositional tautologies and inference rules

b) all KD45 axioms and rules

c) all P axioms and rules

d) special axioms:

B' ! (Ã $ Ã[>=B'])

The proof is very similar to that for the P -logic. It uses the fact that the axioms force all formulas to be equivalent to boolean combinations of atoms and formulas of the form P ' and B', where ' is boolean. It is noteworthy that the principle B' ^ P Ã ! P (' ^ Ã) of [ 23 ] fails in the BP -logic. It is not difficult to construct a counterexample.

D. Disbelief

Disbelief in a proposition is governed by exactly the opposite situation to the one discussed in the previous subsection, D' can be expressed as :' ÂB ', that is P :'.

With the huge amount of work going on in logics of beliefs and belief revision, consideration of disbelief as a separate epistemic category came to fore in the latter part of last decade ([ 24 ], [ 25 ]). Consideration of changing or revising disbeliefs as a process analogous to belief revision was taken up by [ 26 ]. Belief-disbelief pairs i.e. simultaneous consideration of belief and disbelief sets were also taken up ([ 27 ], [ 28 ]) through which various connections of possible inter-connectivity of beliefs and disbeliefs have come into focus. As mentioned earlier our notion of explicit belief ordering provides another path into expressing the concept of disbelief.

The basic idea for disbelieving a proposition is that, the inclination to believe in its negation is stronger than that to believe it. Consequently, disbelieving is a much weaker notion than believing the negation of the proposition, but it should imply that one does not believe in the proposition. In other words, D' is implied by B:' and implies :B' but not the other way around in either case.

To exemplify the matter a bit, let us consider the following situation. Due to the unpredictable weather conditions, Pom’s belief in that she should not cycle from Amsterdam to Leiden is much stronger than her belief that she should. When options like this are available, it is very natural to have this sort of ordering dilemma playing around people’s mind. This can be interpreted as that Pom disbelieves that she should bike, which evidently implies that she does not believe that she should bike. But that ‘she believes that she should not bike’ is a much stronger statement, which fails to express the finer interplay of doubts that is always prevalent in one’s mind.

In general, if a person faces a decision based on whether a certain state of affairs is the case or an event happens, she may not have enough evidence to believe that the state of affairs is the case or is not the case. Then she may base her decision on whether she thinks the state of affairs plausible or disbelieves in it. Only in the case that her strength of belief in the two possibilities is equal, translated into our framework as ' ´B :', it is a real tossup for her.

Various principles for the ‘disbelief’ operator together with the ‘belief’ one have been discussed in [ 25 ] in the autoepistemic logic framework of [ 29 ]. As such, the possible world semantics provided there which is based on separate sets of worlds for beliefs and disbeliefs is not very interesting, and suffers from ‘disjointedness’ as well as ‘mirror-image’ problems. These questions will not arise in the semantics we propose here. The basic reason is the fact that ‘disbelief’ is given a global stance in contrast to ‘belief’ which is apparent from their respective interpretations. This also emphasizes the fact that disbelieving something is different from both from ‘not believing’ as well as ‘believing the negation’.

We now focus on getting a more feasible logic of belief and disbelief in similar lines to BP logic introduced earlier. From our formal understanding D' is same as P :' and hence we get the following dual axiomatization of the BD-logic

Theorem II.8 BD-logic is complete and its validities are

completely axiomatized by the following axioms and rules:

a) all propositional tautologies and inference rules

b) all KD45 axioms and rules

c) disbelief axioms:

D' ! (Ã $ Ã[>=D']) :D' ! (Ã $ Ã[?=D']) D' ! :D:'

D?

d) special axioms:

B' ! (Ã $ Ã[>=B']) :B' ! (Ã $ Ã[?=B']) B' ! D:'

e) anti-monotone rule:

if ' ! Ã then DÃ ! D' Some interesting validities of this logic are, ² B:' ! D' ² D' ! :B' ² D' ! BD' ² :D' ! B:D' ² :D' ! DD' ² :B' ! DB'

On the other hand, as in P -logic and BP -logic, the corresponding intuitively incorrect principle, D' ^ DÃ ! D(' _ Ã) can also be avoided in the BD-logic.

E. Preference

There is a very close relationship between an agent’s beliefs and her preferences which has been extensively discussed in ([ 30 ], [ 3 ]). Based on the ideas from optimality theory, intrinsic preference on the basis of priority sequences P1 >> : : : >> Pn is formulated. Here, the Pi0s are first-order formulas with exactly one free variable, which is common to all of them. Preferences over objects can be defined in terms of these sequences. The basic idea is to define objective preference by:

P ref (d; e) , 9i(Pid^:Pie)^8j < i (Pj d $ Pj e) For subjective preferences over objects, which in fact are considered to be influenced by beliefs, several options are considered. We mention a few of them for the benefit of the readers, their meanings are more or less obvious. P ref (d; e) , 9i(B(Pid) ^ :B(Pie) ^ 8j < i(B(Pj d) $ B(Pj e))) P ref (d; e) , 9i(:B(:Pid) ^ B(:Pie) ^ 8j < i(B(:Pj d) $ B(:Pj e))) P ref (d; e) , 9i ((B(Pid) ^ :B(Pie)) _ (:B(:Pid)^ B(:Pie)) ^ 8j < i ((B(Pj d) $ B(Pj e)) ^ (B(:Pj d) $ B(:Pj e)))) It is clear that the above three approaches are different attempts to express that up to a certain level of the priority sequence the degree of belief in the objects d and e having the mentioned properties is the same and that at the next level the degree of belief in d having the right property is greater than that in e having it. Here we can express this directly in the language as below, and the way greater strength of belief is to be taken in a particular application is then delegated to the semantics.

P ref (d; e) , 9i(Pid ÂB Pie ^ 8j < i(Pj d ´B Pj e)).

F. Multi-agent case

We have been focusing on beliefs and strengths of beliefs of a single agent. The whole idea can be generalized to the multiagent framework. We only give some preliminary ideas here. The technical details need to be worked out, and we leave it for the future. The language of the logic of belief ordering in the multi-agent case, KD45 ¡OM can be defined as follows:

Definition II.9 Given a finite set of agents A, and a countable

set of atomic propositions ©, formulas ' are defined inductively:

' := ? j p j :' j ' _ ' j Ba' j ' <Ba à where p 2 ©.

The indices in the belief and universality modality and in the ordering formula denote the agents whose beliefs or strengths of beliefs are considered. The operators ÂBa and Ua are defined in the usual way. The fact that U is also indexed may surprise the reader for a moment but it is the only coherent way to extend the one agent case. Existence of a location for a proposition to be true meant for us that for the one agent belief in the proposition was stronger than belief in a contradiction. With more agents we may have agents who differ in regard to the existence of propositions: more worlds will have to be added to the model, and it will not stop there: there is no reason for EaEb to be equivalent to Ea or Eb, etc. It is appropriate to add a real universality operator U that corresponds to the agent’s Ua as the common knowledge operator corresponds to the knowledge of the individual agents. With regard to axioms the upshot is for example that the existence axiom ' ! (' ÂBa ?) will have to be weakened to Ua(' ! (' ÂBa ?)).

Likewise, the models for KD45 ¡OM have to be multiagent generalizations of those for KD45 ¡O . The basic idea to consider here is that we can no longer rule out worlds that are impossible for an agent a. They might well be possible for another agent b and also have to be considered while talking about agent a’s belief about agent b’s beliefs and so on.

Evidently, the earlier plausibility ordering and set ordering

of worlds will get indexed by agents (one for each agent), and the global concept of belief will give way to more local concepts of beliefs. This fact becomes apparent in the syntax ψ

Fig. 2. A public announcement à is uttered also, with the introduction of formulas like Ua'. The notion of comparative classes [ 17 ] which gives the set of worlds that an agent considers relevant while positioned at her current world comes into play. Formally, a comparative class of some world is just the set of worlds that are related to the current world by the plausibility order. To give meaning to agents’ beliefs, strength of beliefs, these relevant worlds are needed to be considered only, unlike the single agent case, where the whole model is taken into account. As mentioned earlier, we leave the technical details for later.

III. DYNAMICS OF ORDERING FORMULAS

Till now we have been talking about the static language of belief ordering and its corresponding models, representing the information states (possible worlds) of an agent. We move on to discuss the effect of information-update procedures which change the models under consideration.

It should be mentioned here that we will see an extensive use of the notion of conditional belief while discussing the dynamics of belief change. Conditional beliefs [ 2 ] pre-encode beliefs in a static way in situations which arise after new information comes in. Formulas of the form BÃ' (believing in ', given Ã) express that we believe in ', once we assume that à is the case. This induces that if à is learnt then it is to be believed that ' was the case (before the learning) [ 17 ]. This does not literally tell us what happens after à is learnt. For example, if ' is unknown but true and one learns that :B' ^ ' then afterwards B' will be true, contrary to what was learnt.

In [ 2 ], van Benthem discusses three different update procedures influencing the beliefs of an agent, viz. the influence of hard information like public announcement of à (the not-Ã-worlds get deleted from the model and only the Ã-worlds remain), and of soft information with lexicographic upgrade (introducing a preference for the Ã-worlds, all the Ã-worlds become more plausible than all the not-Ã-worlds - within these zones, the existing ordering remains), and lastly the impact of soft information with elite upgrade (the best Ã-worlds come out on top, beside that the previous ordering remains). We currently just focus on the effect of hard information and soft information with lexicographic upgrade.

ψ

While discussing the influence of ‘hard’ information over beliefs, [ 2 ] considered the following reduction axioms for the logic of public announcement in terms of ‘belief’ and ‘conditional belief’, where [!Ã]' is to be read as ‘after the public announcement of Ã, ' is true’.

² [!Ã]q $ (Ã ! q) ² [!Ã]:' $ (Ã ! :[!Ã]') ² [!Ã](' ^ Â) $ ([!Ã]' ^ [!Ã]Â) ² [!Ã]B' $ (Ã ! BÃ[!Ã]') ² [!Ã]BÂ' $ (Ã ! BÃ^[!Ã]Â[!Ã]')

In fact, the effect of public announcements of à over an ordered model should be clear from the figures 2 and 3. Under the announcement of Ã, the earlier model M, say (cf. fig 2), reduces to a model relativized to à (cf. fig 3), which is essentially a submodel of M, whose domain set is the set where à holds.

Let us now first investigate how the KD45¡O model changes under the influence of a public announcement !Ã, say. The definition is as follows:

Definition III.1 A KD45 ¡O model is defined as in definition

II.2 as the structure M = (S; ·; ¸B; V ). Under the influence of public announcement of à the model becomes M!à = (S!Ã; ·!Ã; ¸!BÃ; V !Ã) where S!à = fs 2 S : M; s j= Ãg, ·!Ã=·ºS!ãS!à , ¸!BÃ=¸BºP(S!Ã)£P(S!Ã), and V !à = V ºS!à .

The model satisfies the following conditions:

1) If X µ Y µ S!Ã, then Y ¸!BÃ X 2) if B!Ã is the new set of plausible worlds, truth on which suffices to make an assertion to be believed, then B!Ã µ X µ S!Ã ^ B!Ã 6µ Y µ S!Ã ) X >!BÃ Y , where >!BÃ denotes the corresponding strict ordering. 3) If X is non-empty, then X >!BÃ ;.

The truth definitions of the formula [!Ã]' in a KD45¡O model is given by,

M; s j= [!Ã]' iff if M; s j= Ã, then M!Ã; s j= '.

Any logic L completing KD45¡O to contain conditional beliefs will have to contain

BÃ' ^ :BÃÂ ! (Ã ^ ') ÂB (Ã ^ Â).

This axiom ensures that the updated model still has the necessary property 2 of Definition II.2 and thus will be a KD45¡O model. We have the following theorem: Theorem III.2 If we take L to be a complete axiomatization of KD45¡O together with conditional beliefs, then its extension under public announcement is complete and its validities are completely axiomatized by the following axioms and rules in addition to L: (a) PAL reduction axioms for atomic facts, Boolean operations, belief and conditional belief (b) PAL reduction [!Ã](' <B Â) $

axioms for ordering formulas: Ã ! ((Ã ^ [!Ã]') <B (Ã ^ [!Ã]Â)) [!Ã](' ÂB Â) $

à ! ((à ^ [!Ã]') ÂB (à ^ [!Ã]Â))

B. Influence of soft information

Following [ 2 ], we considered the influence of hard information over beliefs. Van Benthem continued by discussing the effect of the arrival of soft information on beliefs, which does not influence the existence of the possible worlds, only their plausibility ordering. We now give the definition of the changed models under the influence of soft information with lexicographic upgrade and the corresponding reduction formulas.

Definition III.3 A KD45 ¡O model is defined as in def

inition II.2 as the structure M = (S; ·; ¸B; V ). Under the influence of soft information Ã, say the model becomes M*Ã = (S*Ã; ·*Ã; ¸*BÃ; V *Ã) where S*Ã = S, ·*Ã=· ºK£K [ ·ºL£L [ f(u; v) : u 2 K and v 2 Lg, where K = fs 2 S : M; s j= Ãg, L = S n K, ¸*BÃ=¸B, and V *Ã = V .

Once again, the model M*Ã satisfies the conditions, *Ã X 1) If X µ Y , then Y ¸B 2) if B*Ã is the new set of plausible worlds, truth on which suffices to make an assertion to be believed, then B*Ã µ X ^ B*Ã 6µ Y ) X >*BÃ Y , where >*BÃ denotes the corresponding strict ordering. 3) If X is non-empty, then X >*BÃ ;.

The truth definitions of the formula [!Ã]' in a KD45¡O model is given by,

M; s j= [* Ã]' iff M*Ã; s j= '.

We have the following theorem:

Theorem III.4 If we take L to be a complete axiomatization of KD45¡O with conditional beliefs, then its extension under announcement of soft information with lexicographic upgrade is complete and its validities are completely axiomatized by the following axioms and rules in addition to L: (a) reduction axioms: [* Ã]q $ q [* Ã]:' $ :[* Ã]' [* Ã](' ^ Â) $ ([* Ã]' ^ [* Ã]Â) [* Ã]BÂ' $ (E(Ã ^ [* Ã]Â) ^ (BÃ^[*Ã]Â[* Ã]' _ B[*Ã]Â[* Ã]')) [* Ã](' <B Â) $ EÃ ^ (((Ã ^ [* Ã]') <B (Ã ^ [* Ã]Â)) _ ([* Ã]' <B [* Ã]Â)) [* Ã](' ÂB Â) $ EÃ ^ (((Ã ^ [* Ã]') ÂB (Ã ^ [* Ã]Â)) _ ([* Ã]' ÂB [* Ã]Â))

The product-update model [ 2 ] or the more general version of the action-priority update model [ 17 ] may not be of much use in the modelling of the ordering formulas, because the first order frame conditions of KD45 ¡ O-models are not all universal Horn sentences (e.g. the linearity condition), which is required for easy passage to this type of update models [ 2 ].

IV. CONCLUSION AND FURTHER WORK

An explicit ordering of formulas to compare the strengths of beliefs is introduced. A complete axiomatization for this belief logic with explicit ordering is provided. This notion aids in giving intuitive formulations for various related concepts like universality as well as some other epistemic attitudes - much older and thoroughly discussed notions like universality and preference, together with relatively newer ones like plausibility and disbelief. Independent axiomatizations for the logics of plausibility, belief and plausibility as well as belief and disbelief are also provided. Interplay of belief ordering with the concept of safe beliefs is discussed. Lastly, we delved into the dynamics of this ordering concept, e.g. the effect of hard as well as soft information over the ordering formulas. A few possible avenues for future work are discussed below.

a) Interpreting the ordered formulas: We have provided different ways of interpreting these ordered belief formulas, and a complete axiomatization is provided with respect to a most general one. It will be interesting to find extensions for other possible applications and their properties, specially to get more interesting inter-connections between the world-ordering and the set-ordering.

b) Dynamic setting: As evident from the discussions in section 3, the whole system fits very well into the dynamic epistemic logic framework. But clearly this is the just the start of serious research in this area. There are various notions in this context that need to be thoroughly investigated, especially the relation to conditional belief. There are also important model-theoretic issues that one can look into. In short, a lot of possibilities have emerged with the introduction of this ordering of beliefs in the already existing dynamic logic framework dealing with epistemic attitudes.

REFERENCES

References

[1] J. Gerbrandy , “Bisimulation on planet kripke, ” Ph.D. dissertation , University of Amsterdam, 1999 .

[2] J. v. Benthem , “ Dynamic logic for belief revision , ” Journal of Applied Non-Classical Logic , vol. 17 , no. 2 , pp. 129 - 155 , 2007 .

[3] F. Liu , “ Changing for the better: Preference dynamics and agent diversity , ” Ph.D. dissertation , University of Amsterdam, 2008 .

[4] S. Artemov and L. Beklemishev , “Provability logic,” in Handbook of Philosophical Logic, 2nd ed., D. Gabbay and F. Guenthner , Eds. Kluwer, Dordrecht, 2004 , vol. 13 .

[5] D. Guaspari and R. Solovay , “Rosser sentences, ” Annals of Mathematical Logic , vol. 16 , pp. 81 - 89 , 1979 .

[6] D. d . Jongh, “ A simplification of a completeness proof of Guaspari and Solovay,” Studia Logica , vol. 46 , pp. 187 - 192 , 1987 .

[7] K. Segerberg , “ Qualitative probability in a modal setting,” in Proceedings of the 2nd Scandinavian Logic Symposium , J. Fenstad, Ed. Amsterdam: North-Holland, 1971 .

[8] P. Gardenfors , “ Qualitative probability as an intentional logic , ” Journal of Philosophical Logic , vol. 4 , pp. 171 - 185 , 1975 .

[9] D. Lewis , Counterfactuals. Blackwell and Harvard U.P., 1973 .

[10] W. Spohn , “ Ordinal conditional functions. a dynamic theory of epistemic states,” in Causation in Decision, Belief Change , and Statistics, W. Harper and B. Skyrms , Eds. Kluwer, Dordrecht, 1988 , vol. II.

[11] O. Board , “Dynamic inetractive epistemology, ” Games and Economic Behavior , vol. 49 , pp. 49 - 80 , 2004 .

[12] P. Ga ¨rdenfors and D. Makinson, “Revisions of knowledge systems and epistemic entrenchment ,” in Proceedings of the Second Conference on Theoretical Aspects of Reasoning about Knowledge , M. Vardi, Ed. Los Altos: Morgan Kaufmann, 1988 , pp. 83 - 95 .

[13] G. v. Wright , “Deontic logic,” Mind, vol. 60 , pp. 1 - 15 , 1951 .

[14] J. Hintikka , Knowledge and Belief . Ithaca, N.Y.: Cornell University Press, 1962 .

[15] S. Kripke , “ Semantical considerations on modal logics,” Acta Philosophica Fennica , vol. 16 , pp. 83 - 94 , 1963 .

[16] J. Halpern and Y. Moses , “ A guide to completeness and complexity for modal logics of knowledge and belief , ” Artificial Intelligence , vol. 54 , pp. 319 - 379 , 1992 .

[17] A. Baltag and S. Smets , “ A qualitative theory of dynamic interactive belief revision,” in Logic and the Foundations of Game and Decision Theory, Texts in Logic and Games, G. Bonanno, W. van der Hoek, and M. Wooldridge, Eds., vol. 3 . Amsterdam University Press, 2008 , pp. 9 - 58 .

[18] V. Goranko and S. Passy , “ Using the universal modality: Gains and questions , ” Journal of Logic and Computation , vol. 2 , no. 1 , pp. 5 - 30 , 1992 .

[19] J. Halpern , “ Defining relative likelihood in partially-ordered preferential structures , ” Journal of AI Research , vol. 7 , pp. 1 - 24 , 1997 .

[20] -- , Reasoning About Uncertainty . MIT Press, 2003 .

[21] N. Friedman and J. Halpern , “ Plausibility measures and default reasoning , ” Journal of the ACM , vol. 48 , no. 4 , pp. 648 - 685 , 2001 .

[22] R. Stalnaker , “ On logics of knowledge and belief,” Philosophical Studies , vol. 128 , no. 1 , pp. 169 - 199 , 2006 .

[23] J. Burgess , “Probability logic, ” Journal of Symbolic Logic , vol. 34 , no. 2 , pp. 264 - 274 , 1969 .

[24] A. Ghose and R. Goebel , “ Belief states as default theories: Studies in non-prioritised belief change ,” in Proceedings of the 13th European Conference on Artificial Intelligence , H. Prade, Ed., 1998 , pp. 8 - 12 .

[25] A. Gomolinska , “ On the logic of acceptance and rejection,” Studia Logica , vol. 60 , pp. 233 - 251 , 1998 .

[26] A. Gomolinska and D. Pearce , “Disbelief change,” Electronic essays on the occasion of the fiftieth birthday of Peter Gardenfors , 2001 .

[27] S. Chopra , J. Heidema , and T. Meyer, “ Logics of belief and disbelief ,” in Proceedings of the ninth International Workshop on Non-Monotonic Reasoning , 2002 .

[28] M. Chakraborty and S. Ghosh , “ Belief-disbelief interface: A bi-logical approach ,” Fundamenta Informaticae, to appear.

[29] R. Moore , “ Semantical considerations on nonmonotonic logic , ” Artificial Intelligence , vol. 25 , pp. 75 - 94 , 1985 .

[30] D. d. Jongh and F. Liu , “Optimality, belief and preference,” in Proceedings of the Workshop on Rationality and Knowledge , ESSLLI, S. Artemov and R. Parikh , Eds., 2006 .