Comparing strengths of beliefs explicitly Dick de Jongh Sujata Ghosh Institute for Logic, Language and Computation Institute of Artificial Intelligence Universiteit van Amsterdam Rijksuniversiteit Groningen Email: D.H.J.deJongh@uva.nl Email: Sujata.Ghosh@rug.nl Abstract—Inspired by a similar use in provability logic, for- The third time Fiona and Gregory apply. About both she is mulas p ÂB q and p B {t | M, t |= ψ}. of Belief logic with explicit ordering (KD45 −O), whose Thus, ÂB is also a global notion. We will now show language is defined as follows: that the universal modality U can also be expressed in KD45 −O. The modality Eϕ (the abbreviated form of Definition II.1 Given a countable set of atomic propositions ¬U ¬ϕ) can be defined as ϕ ÂB ⊥, and hence U ϕ itself Φ, formulas ϕ are defined inductively: as ⊥ B Y , where X >B Y iff X ≥B Y If one wants to base the strength of belief ordering on and not (Y ≥B X). the plausibility ordering of the worlds, then immediately 3) If X is non-empty, then X >B ∅. the following option comes to mind: the interpretation of ϕ ÂB ψ can be that there exist ϕ-worlds which are more The first condition says that larger sets of worlds are more plausible than any ψ-world (similar to the proposal in [9]). plausible, the second one that the sets containing the center For ϕ B . We have already seen that ordering ≥B between the sets of worlds in the plausibility Eϕ can be defined as ϕ ÂB ⊥, because of the 3rd condition models. We have put very minimal requirements on this that >B satisfies in the model. Using lin-axiom it is easy to ordering. In fact, as we will see in section II-B, belief can be show that U ϕ is equivalent to ⊥ B is the corresponding strict ordering, the following axioms need no introduction: From this the principle Bϕ → U Bϕ readily follows. The transitivity and the symmetry axioms for U follow because of ϕ 1 V (χ) iff ψ ÂB χ is true in the and the center axiom describes property 2. With U and E model. These follow from the first three ordering axioms. defined as indicated previously, one can easily show that the Moreover, if V (ψ) ⊆ V (χ) then V (ψ) ≥1 V (χ) (subset S5-axioms are derivable for U . It is also not very hard to condition), by the axiom: U (χ → ψ) → ψ 1 V (χ) (sufficient belief condition) by the axiom: Bψ ∧¬Bχ → Assume 0KD45 −O ϕ. We will have to construct a counter- ψ ÂB χ. model to ϕ as a KD45 −O-model. We take a finite adequate So, ≥1 behaves properly on the representable elements of set Φ containing ϕ. In this case an adequate set will be: a P(W ). What remains is to extend ≥1 to an ordering ≥ with set of formulas that is closed under subformulas containing the right properties over all of P(W ). with each formula ψ (a formula equivalent to) ¬ψ, containing Take an arbitrary subset X of W . We define R(X) to be with Bψ and Bχ (a formula equivalent to) B(ψ ∧ χ) and the largest subset of X that is representable. That such a set a formula (equivalent to) B(ψ ∨ χ). We also need Φ to exists follows from the fact that the representable subsets are contain with each formula Bϕ a formula (equivalent to) U Bϕ. closed under finite unions and the finiteness of the model. Finally, Φ contains B> and B⊥. It is easy to see that any We now define X ≥ Y iff R(X) ≥1 R(Y ). This imme- finite set is contained in a finite adequate set. We use the diately makes ≥ a quasi-linear order. That ≥ satisfies the Henkin method restricted to Φ. Consider the m.c. (maximally subset condition follows from the fact that, if X ⊆ Y , then consistent) subsets of Φ. In particular consider such an m.c. R(X) ⊆ R(Y ). set Φ0 containing ¬ϕ. When we now refer to U ψ we mean its translation into KD45 −O. It can be shown that the S5- We will conclude this proof with a lemma showing axioms to hold for this translation. The proof is made more that B is representable, i.e. B = R(B). From that result perspicuous by referring to U . it follows that, if B ⊆ X, then B ⊆ R(X). This is The relations RB and RU are defined as follows: clearly sufficient to ensure the sufficient belief condition. So, once we finish the proof of the following lemma, we are done. P RB Q iff (1) for all Bϕ in P , ϕ as well as Bϕ are in Q, (2) for all ¬Bϕ in P , ¬Bϕ in Q. P RU Q iff (1) for all U ϕ in P , ϕ as well as U ϕ are in Q, Lemma. B is representable. (2) for all ¬U ϕ in P , ¬U ϕ in Q Proof of Lemma. Consider w not in B. Then it is not the We have to show that RU is an equivalence relation and case that wRB w. This means that, for some particular B(ψw ) RB a Euclidean sub-relation of RU . Finally, within one U - in Φ, B(ψw ) is in w but ψw is not. Note that this implies that equivalence class there is one, nonempty set of B-reflexive ψw is true all over B. Consider the conjunction ψ of all ψw for elements, which forms a B-equivalence class. Since all these w in the complement of B. B(ψ) is a member of Φ while ψ things are standard we skip this part. is true in all elements of B, but is falsified at all elements u in We now take the submodel generated by RU from Φ0 . The the complement of B, since ψ implies ψu and ψu is falsified set of worlds W of our model will be the set of worlds in u. We have shown that B is represented by ψ. Since the counter-model constructed is finite, we also have M, s |= ¤ϕ iff M, t |= ϕ for all worlds t ≤ s. that the logic KD45−O is decidable. Before ending this section we mention some intuitively true formulas, which we which says that ϕ can be safely believed at some world s if it did not need as axioms, but are definitely worth thinking about. holds at all the worlds which are at least as plausible as s. In One of them is, the following we will introduce the safe belief modality in the setting of KD45−O, and give a complete axiomatization of (ϕ ÂB ⊥) → (> ÂB ¬ϕ), this logic. The language of the logic KD45−OS is defined as follows: which says that if ϕ is true somewhere then ¬ϕ is not as much to be believed as a tautology. The other direction of the Definition II.4 Given a countable set of atomic propositions implication can be derived. An equivalent formulation is, Φ, formulas ϕ are defined inductively: (ϕ ) → (⊥ B X. beliefs, and the relevant ordering axioms, viz. refl, trans, lin, This seems a very reasonable addition as it makes the models center, existence, U ϕ, given by where K̂ψ := ¬K¬ψ. They gave complete axiomatizations for ϕ := p | ¬ϕ | ϕ ∨ ϕ | P ϕ conditional doxastic logic (logic of conditional belief) as well as the logic of knowledge and safe beliefs. We do not consider We read P ϕ as “ϕ is plausible”. As mentioned above, knowledge but for this part of the discussion it can be replaced the intuitive meaning of P ϕ can be captured by the formula by U . Neither do we talk about conditional belief here, but ϕ ÂB ¬ϕ, and as such, the truth definition of P ϕ in the belief can be defined in terms of the existential modality and KD45−O model is given by, safe belief (i.e. in terms of safe belief and belief ordering) as M, s |= P ϕ iff {t | M, t |= ϕ} >B {t | M, t |= ¬ϕ}. follows: Bϕ := E¤ϕ Theorem II.6 P -logic is complete and its validities are com- Once we have in this manner the modal operator B as pletely axiomatized by the following axioms and rules: a defined concept, we can easily derive all its well-known (a) all propositional tautologies and inference rules properties in KD45−OS, but if that holds fully for its (b) plausibility axioms: relations with generally mean that we tend to believe in its happening rather c) monotonicity rule: than its not happening. That is the interpretation we take here. if ϕ → ψ then P ϕ → P ψ Hence, in terms of ordered formulas, P ϕ can be expressed as ϕ ÂB ¬ϕ. Of course, there are other possible notions of Proof: First of all, we show that any formula in P-logic plausibility, but here we interpret P ϕ as ‘more plausible than is equivalent to a formula with P -depth at most one. For that not’. We now explore this notion of ‘plausibility’ in terms of purpose we first derive the following schemes: belief ordering. 1) P ψ → (ϕ ↔ ϕ[>/P ψ]) 2) ¬P ψ → (ϕ ↔ ϕ[⊥/P ψ]) An important principle that will be valid for the plausibility operator P is U (ϕ → ψ) → (P ϕ → P ψ). This holds because Here, ϕ[>/P ψ] means ϕ with > substituted for some if U (ϕ → ψ), not only will belief in ψ be at least as strong occurrences of P ψ. We prove by induction on the complexity as in ϕ, but U (ϕ → ψ) implies U (¬ψ → ¬ϕ), so belief in of formulas ϕ with possible occurrences of > and ⊥. ¬ψ is not greater than in ¬ϕ. This leads to consequences like In the base case, that is for the atomic propositions and P (ϕ ∧ ψ) → P ϕ. propositional constants, the result follows immediately. The reason to take the set semantics for ordering formulas (cf. Definition II.2) becomes clear. If we would adhere to the Induction step. This is trivial for the boolean connectives. semantics we may have had for ÂB in terms of plausibility So, it suffices to prove it for P ϕ assuming it holds for ϕ. ordering for worlds (instead of sets of worlds), P ϕ would From the induction hypothesis for the first scheme it follows become equivalent to Bϕ, which obviously is undesirable. 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 Evidently, P ϕ is a global notion - its value does not P (ϕ[>/P ψ]). The proof for the second scheme is very similar. vary through the model. Again, P is clearly an introspective notion. Interestingly, the principles 4 and 5 for the modal To see that these schemes imply that each formula in operator P are derivable in this P -logic, but the K-axiom P -logic is equivalent to a formula with P -depth at most one, is not. That P ϕ ∧ P ψ → P (ϕ ∧ ψ) ought not to be a just note that ` ϕ ↔ ((P ψ ∧ ϕ) ∨ (¬P ψ ∧ ϕ)). Now, if we valid principle in the P -logic is clear if we interpret P ϕ as want to get rid of occurrences of P ψ in ϕ we can replace ϕ ϕ ÂB ¬ϕ. by ((P ψ ∧ ϕ[>/P ψ]) ∨ (¬P ψ ∧ ϕ[⊥/P ψ])). By doing this consecutively for all occurrences of P ψ with no occurrences Let us finally note that an interpretation of P ϕ as ϕ of P in ψ we obtain the desired result. as having probability more than 0.5 (or any other number between 0.5 and 1) leads to exactly the P -axioms provided Next, we show that any consistent set has a model. Assume one considers the probability statements themselves to always we have a consistent set in the P -logic which can be extended have probability 1. to a maximal consistent set Γ, say. Since we can restrict attention to formulas which are boolean combinations of We now consider a system having both belief and the atoms and formulas of the form P ϕ where ϕ no longer plausibility operator, viz. the BP -system. This system will contains P , a maximal consistent set is essentially only a provide pointers to discuss logics of belief and disbelief in the set of atoms, negations of atoms, such P ϕ’s and ¬P ϕ’s and next subsection. The language is that of the P -logic, together their boolean combinations. with the additional modal operator for belief, B. ϕ := p | ¬ϕ | ϕ ∨ ϕ | P ϕ | Bϕ We now make a model in our sense where P ϕ gets interpreted as ϕ >B ¬ϕ. The worlds will be simply defined Some validities of this logic in the KD45−O model are, by a number of atoms being true in it and the rest of • Bϕ → P ϕ the atoms false. Let us now consider the following model, • P ϕ → BP ϕ M = (S, ≤, ≥B , V ), where S is the set of all maximal • ¬P ϕ → B¬P ϕ consistent subsets. The ordering of the subsets is as follows: There are 5 equivalence classes in the ordering starting with Theorem II.7 BP -logic is complete and its validities are the highest grade of believability. We take membership of completely axiomatized by the following axioms and rules: those classes to determine the degree of belief in the sets. a) all propositional tautologies and inference rules (1) The whole set, which is of course represented by >. b) all KD45 axioms and rules (2) The sets represented by those ϕ for which P ϕ is in Γ c) all P axioms and rules (except for >). d) special axioms: (3) The sets represented by those ϕ for which ¬P ϕ is in Γ Bϕ → (ψ ↔ ψ[>/Bϕ]) as well as ¬P ¬ϕ. ¬Bϕ → (ψ ↔ ψ[⊥/Bϕ]) (4) The sets represented by those ϕ for which P ¬ϕ is in Γ (except for ⊥). Bϕ → P ϕ (5) The empty set, which is of course represented by ⊥. The proof is very similar to that for the P -logic. It uses These are all possibilities because of axiom P ϕ → ¬P ¬ϕ. the fact that the axioms force all formulas to be equivalent Finally we take B, the center, to be the whole set (so, there to boolean combinations of atoms and formulas of the form are no beliefs except the trivial one in >). P ϕ and Bϕ, where ϕ is boolean. It is noteworthy that the principle Bϕ ∧ P ψ → P (ϕ ∧ ψ) of [23] fails in the BP -logic. The two things we have to check are: First, that, if It is not difficult to construct a counterexample. a set is in class (2), then any larger one will be in (2) as well (or in (1)). This follows from the monotonicity D. Disbelief rule. Similarly for the other classes. Second, that, if a set Disbelief in a proposition is governed by exactly the X contains all of B, and another set Y doesn’t, then X opposite situation to the one discussed in the previous > Y . That is trivial: X has to be B, the whole set, and Y isn’t. subsection, Dϕ can be expressed as ¬ϕ ÂB ϕ, that is P ¬ϕ. As earlier, we can induce an ordering over all subsets With the huge amount of work going on in logics of satisfying the required conditions. All the single worlds have to beliefs and belief revision, consideration of disbelief as a be taken to be equally plausible, i.e. s ≤ t, for all s, t ∈ S. So, separate epistemic category came to fore in the latter part for each consistent set we can have a model in KD45−O. So, of last decade ([24], [25]). Consideration of changing or the axioms and rules given in Theorem 2.6 axiomatize the P - revising disbeliefs as a process analogous to belief revision logic of ‘more plausible then not’. It is also worth-mentioning was taken up by [26]. Belief-disbelief pairs i.e. simultaneous why (P ϕ ∧ P ψ) → P (ϕ ∧ ψ) will fail in general. There may consideration of belief and disbelief sets were also taken up be sets in (2), the intersection of which, is not in (2). ([27], [28]) through which various connections of possible inter-connectivity of beliefs and disbeliefs have come into b) all KD45 axioms and rules focus. As mentioned earlier our notion of explicit belief c) disbelief axioms: ordering provides another path into expressing the concept of Dϕ → (ψ ↔ ψ[>/Dϕ]) disbelief. ¬Dϕ → (ψ ↔ ψ[⊥/Dϕ]) The basic idea for disbelieving a proposition is that, the Dϕ → ¬D¬ϕ inclination to believe in its negation is stronger than that D⊥ to believe it. Consequently, disbelieving is a much weaker d) special axioms: notion than believing the negation of the proposition, but it Bϕ → (ψ ↔ ψ[>/Bϕ]) should imply that one does not believe in the proposition. In other words, Dϕ is implied by B¬ϕ and implies ¬Bϕ but ¬Bϕ → (ψ ↔ ψ[⊥/Bϕ]) not the other way around in either case. Bϕ → D¬ϕ e) anti-monotone rule: To exemplify the matter a bit, let us consider the following if ϕ → ψ then Dψ → Dϕ situation. Due to the unpredictable weather conditions, Pom’s belief in that she should not cycle from Amsterdam to Leiden Some interesting validities of this logic are, is much stronger than her belief that she should. When options like this are available, it is very natural to have this • B¬ϕ → Dϕ sort of ordering dilemma playing around people’s mind. This • Dϕ → ¬Bϕ can be interpreted as that Pom disbelieves that she should • Dϕ → BDϕ bike, which evidently implies that she does not believe that • ¬Dϕ → B¬Dϕ she should bike. But that ‘she believes that she should not • ¬Dϕ → DDϕ bike’ is a much stronger statement, which fails to express the • ¬Bϕ → DBϕ finer interplay of doubts that is always prevalent in one’s mind. On the other hand, as in P -logic and BP -logic, the corresponding intuitively incorrect principle, In general, if a person faces a decision based on whether Dϕ ∧ Dψ → D(ϕ ∨ ψ) can also be avoided in the a certain state of affairs is the case or an event happens, she BD-logic. 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 E. Preference disbelieves in it. Only in the case that her strength of belief There is a very close relationship between an agent’s beliefs in the two possibilities is equal, translated into our framework and her preferences which has been extensively discussed in as ϕ ≡B ¬ϕ, it is a real tossup for her. ([30], [3]). Based on the ideas from optimality theory, intrinsic preference on the basis of priority sequences P1 >> . . . >> Various principles for the ‘disbelief’ operator together Pn is formulated. Here, the Pi0 s are first-order formulas with with the ‘belief’ one have been discussed in [25] in the exactly one free variable, which is common to all of them. autoepistemic logic framework of [29]. As such, the possible Preferences over objects can be defined in terms of these world semantics provided there which is based on separate sequences. The basic idea is to define objective preference sets of worlds for beliefs and disbeliefs is not very interesting, by: and suffers from ‘disjointedness’ as well as ‘mirror-image’ P ref (d, e) ⇔ ∃i(Pi d∧¬Pi e)∧∀j < i (Pj d ↔ Pj e) problems. These questions will not arise in the semantics we propose here. The basic reason is the fact that ‘disbelief’ is For subjective preferences over objects, which in fact are given a global stance in contrast to ‘belief’ which is apparent considered to be influenced by beliefs, several options are from their respective interpretations. This also emphasizes the considered. We mention a few of them for the benefit of the fact that disbelieving something is different from both from readers, their meanings are more or less obvious. ‘not believing’ as well as ‘believing the negation’. P ref (d, e) ⇔ ∃i(B(Pi d) ∧ ¬B(Pi e) ∧ ∀j < i(B(Pj d) ↔ We now focus on getting a more feasible logic of belief and B(Pj e))) disbelief in similar lines to BP logic introduced earlier. From our formal understanding Dϕ is same as P ¬ϕ and hence we P ref (d, e) ⇔ ∃i(¬B(¬Pi d) ∧ B(¬Pi e) ∧ ∀j < i(B(¬Pj d) get the following dual axiomatization of the BD-logic - ↔ B(¬Pj e))) Theorem II.8 BD-logic is complete and its validities are P ref (d, e) ⇔ ∃i ((B(Pi d) ∧ ¬B(Pi e)) ∨ (¬B(¬Pi d)∧ completely axiomatized by the following axioms and rules: B(¬Pi e)) ∧ ∀j < i ((B(Pj d) ↔ B(Pj e)) ∧ (B(¬Pj d) ↔ B(¬Pj e)))) a) all propositional tautologies and inference rules 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 Fig. 2. A public announcement ψ is uttered is to be taken in a particular application is then delegated to the semantics. also, with the introduction of formulas like Ua ϕ. The notion P ref (d, e) ⇔ ∃i(Pi d ÂB Pi e ∧ ∀j < i(Pj d ≡B Pj e)). of comparative classes [17] which gives the set of worlds that an agent considers relevant while positioned at her current F. Multi-agent case world comes into play. Formally, a comparative class of some We have been focusing on beliefs and strengths of beliefs of world is just the set of worlds that are related to the current a single agent. The whole idea can be generalized to the multi- world by the plausibility order. To give meaning to agents’ agent framework. We only give some preliminary ideas here. beliefs, strength of beliefs, these relevant worlds are needed The technical details need to be worked out, and we leave it to be considered only, unlike the single agent case, where the for the future. The language of the logic of belief ordering in whole model is taken into account. As mentioned earlier, we the multi-agent case, KD45 −OM can be defined as follows: leave the technical details for later. Definition II.9 Given a finite set of agents A, and a countable III. DYNAMICS OF ORDERING FORMULAS set of atomic propositions Φ, formulas ϕ are defined induc- tively: Till now we have been talking about the static language of ϕ := ⊥ | p | ¬ϕ | ϕ ∨ ϕ | Ba ϕ | ϕ ⇑ψ ⇑ψ B Y , where >B denotes the corresponding strict ordering. The model satisfies the following conditions: 3) If X is non-empty, then X >⇑ψ B ∅. 1) If X ⊆ Y ⊆ S !ψ , then Y ≥!ψ B X The truth definitions of the formula [!ψ]ϕ in a KD45−O 2) if B !ψ is the new set of plausible worlds, truth on which model is given by, suffices to make an assertion to be believed, then B !ψ ⊆ X ⊆ S !ψ ∧ B !ψ 6⊆ Y ⊆ S !ψ ⇒ X >!ψ !ψ M, s |= [⇑ ψ]ϕ iff M⇑ψ , s |= ϕ. B Y , where >B denotes the corresponding strict ordering. We have the following theorem: 3) If X is non-empty, then X >!ψ B ∅. Theorem III.4 If we take L to be a complete axiomatization The truth definitions of the formula [!ψ]ϕ in a KD45−O of KD45−O with conditional beliefs, then its extension under model is given by, announcement of soft information with lexicographic upgrade is complete and its validities are completely axiomatized by M, s |= [!ψ]ϕ iff if M, s |= ψ, then M!ψ , s |= ϕ. the following axioms and rules in addition to L: Any logic L completing KD45−O to contain conditional (a) reduction axioms: beliefs will have to contain [⇑ ψ]q ↔ q 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 [⇑ ψ]B χ ϕ ↔ (E(ψ ∧ [⇑ ψ]χ) ∧ (B ψ∧[⇑ψ]χ [⇑ ψ]ϕ ∨ KD45−O model. We have the following theorem: B [⇑ψ]χ [⇑ ψ]ϕ)) [⇑ ψ](ϕ