Reasoning about Fuzzy Belief and Common Belief: With Emphasis on Incomparable Beliefs

1 Introduction

Epistemic logic has been studied in order to formalize reasoning about knowledge and belief (see [13; 7]) with widespread applications to many research areas, including computer science and artificial intelligence ([7; 16]), economics and game theory ([1]), and philosophy ([2; 13]). The logic of common knowledge and belief is one of the central concerns of epistemic logic (see [7; 16]).

In this paper we formalize reasoning about fuzzy belief and fuzzy common belief, especially incomparable beliefs, in multi-agent systems by using a logical system based on Fitting's many-valued modal logic (for this logic, see [8; 9; 10]), where incomparable beliefs are defined as beliefs whose degrees are not totally ordered. We remark that many-valued modal logics have already been studied from various perspectives (see [4; 14; 15]). Results in the paper are established while implicitly exploiting the duality-theoretic perspective on Fitting's logic that builds upon the author's previous study (see [14; 15]).

Let us explain our motivations for studying the logic of fuzzy belief and common belief. It is not so unusual that one believes something to some degree, or the degree of one's belief may be neither 0 nor 1. The notion of fuzzy belief is appropriate in such a case. Moreover, the notion of fuzzy common belief can be appropriate even in a case where any agent of a group does not have a fuzzy belief. To see this, consider the following question. Is there anything that all the people in the world believe? Strictly speaking, there may be no such thing as a common belief among all the people in the world. Even if so, there may be something that most of the people in the world believe. For instance, most but not all of the people in the world probably believe that any human being is mortal or that the law of identity (i.e., ϕ → ϕ) is valid (note that some logicians do not believe it). The notion of fuzzy common belief is appropriate in such a case as well as in a case where an agent of a group has a fuzzy belief.

Here, we would like to clarify our philosophical standpoint. We consider that the degree of a belief ϕ by an agent i is equivalent to the truth degree of the proposition that i believes ϕ (in fact, this is imprecise; to be precise, see B2 in Definition 11; not Ta but Ua is appropriate also here), that is, degrees of belief can ultimately be reduced to degrees of truth in this way (in the sense of Ua as in B2), which we call "the reduction thesis about belief degrees" (this has no relation with Peirce's reduction thesis). We may identify the reduction thesis with the axiom B2 in Definition 11. Although the thesis may be contested, we work under the assumption of it in this paper. We believe that the reduction thesis is philosophically justifiable to some degrees, but anyway it is certainly beneficial (and would thus be justifiable) from a technical point of view as is shown in the results of the paper.

Epistemic logic based on classical logic is inadequate to formalize reasoning about fuzzy (common) belief, which is due to the fact that either 0 or 1 is assigned to every formula in classical epistemic logic. We are thus led to consider epistemic logic based on many-valued logic, since the truth value of a proposition may be neither 0 nor 1 in manyvalued logic. Among many existing many-valued logics, we employ a modified version of Fitting's lattice-valued logic, the reasons of which are explained later, and we add to the lattice-valued logic epistemic operators including a common belief operator, thus developing a logical system for reasoning about fuzzy belief and common belief.

Several authors have already developed logical systems to formalize reasoning about fuzzy belief (see, e.g., [3; 6; 11]), for example, by combining probabilistic logic and epistemic logic. However, there seems to have been no study of reasoning about fuzzy common belief via the combination of many-valued logic and epistemic logic. Moreover, the degrees of beliefs are supposed to be totally ordered in the previously proposed systems. For this reason, the notion of incomparable beliefs cannot be formalized in them.

There are indeed many incomparable beliefs in ordinary life. For instance, consider the following situations: (1) Suppose that there are two collections X, Y of grains here, that X is taller and thinner than Y and that it is not obvious whether or not each collection of grains makes a heap, as shown in the following figure (of course, this is based on the well-known sorites paradox, which motivates many-valued logic).

Let a (resp. b) be the degree of one's belief that X (resp. Y ) makes a heap. Then, a and b may be incomparable, since their magnitudes are incomparable. (2) Suppose that a child believes that she loves her mother and that she loves her father. Then, the degrees of her two beliefs can be incomparable. Thus, one's beliefs are sometimes incomparable.

Hence, it would be significant to be able to formalize the notion of incomparable beliefs in a logical system. In our system, a degree of a belief is expressed as an element of a lattice which is not necessarily totally ordered. Therefore, the notion of incomparable beliefs can be formalized in our system, which is impossible in previously developed systems for reasoning about fuzzy belief such as those in [3; 6; 11]. This is one of the reasons why we employ a version of Fitting's lattice-valued logic as the underlying logic of our system for reasoning about fuzzy belief and common belief.

We remark that Fitting's lattice-valued logic (for different lattice-valued logics, see [17]) may be considered as a kind of fuzzy logic, but the prelinearity axiom (ϕ → ψ) ∨ (ψ → ϕ) is not necessarily valid in Fitting's logic, while it is valid in fuzzy logics such as Łukasiewicz logic and G¨odel logic (for these logics, see [12]). We also note that the lattice of truth values is finite in Fitting's logic (see also [4]), since L-valued modal logic may not be recursively axiomatizable for an infinite lattice L. In practice or in the real world, a sufficiently large finite lattice and an infinite lattice would not make a significant difference (we could not distinguish between them).

This paper is organized as follows. In Section 2, latticevalued logic L-VL is discussed. In Section 3, a logic of fuzzy belief in an n-agent system, L-Kn, is discussed. In the two sections, we mainly aim to reformulate algebraic axiomatizations in [14] in terms of Hilbert-style deductive systems. In Section 4, the usual Kripke semantics for a common belief operator is naturally extended to the L-valued case and then a logic of fuzzy belief and common belief, L-KCn , is discussed. Especially, we develop a Hilbert-style deductive system for L-KCn and show that it is sound and complete with respect to the extended Kripke semantics and that L-KCn is decidable and enjoys the finite model property. We remark that we can also obtain other versions of these results such as KD45-style, S5-style, K45-style, and S4-style ones.

2 Lattice-Valued Logic: L-VL

Throughout this paper, let L denote a finite distributive lattice with the top element 1 and the bottom element 0. Then, as is well known, L forms a finite Heyting algebra. For a, b ∈ L, let a → b denote the pseudo complement of a relative to b. Let 2 denote the two-element Boolean algebra.

Definition 1. We augment L with unary operations Ta(-)'s for all a ∈ L defined as follows: Ta(x) = 1 if x = a and Ta(x) = 0 if x ̸= a. We also augment L with unary operations Ua(-)'s for all a ∈ L defined by: Ua(x) = 1 if x ≥ a and Ua(x) = 0 if x ≱ a

We define L-valued logic L-VL as follows. The connectives of L-VL are ∧, ∨, →, 0, 1, Ta and Ua for each a ∈ L, where Ta and Ua are unary connectives, 0 and 1 are nullary connectives, and the others are binary connectives. Let PV denote the set of propositional variables. Then, the set of formulas of L-VL, which is denoted by Form, are recursively defined in the usual way. Let ϕ ↔ ψ be the abbreviation of (ϕ → ψ) ∧ (ψ → ϕ) and ¬ϕ the abbreviation of ϕ → 0. The intended meaning of Ta(ϕ) is that the truth value of a proposition ϕ is an element a of L. The intended meaning of Ua(ϕ) is that the truth value of ϕ is more than or equal to a. L-valued semantics is then introduced as follows.

Definition 2. A function v : Form → L is an L-valuation on Form iff it satisfies the following:

1. v(Ta(ϕ)) = Ta(v(ϕ)) for each a ∈ L;
2. v(Ua(ϕ)) = Ua(v(ϕ)) for each a ∈ L;
3. v(ϕ∧ψ) = inf(v(ϕ), v(ψ));
4. v(ϕ∨ψ) = sup(v(ϕ), v(ψ));
5. v(ϕ→ψ) = v(ϕ) → v(ψ);
6. v(a) = a for a = 0, 1.

Then, ϕ ∈ Form is called valid in L-VL iff v(ϕ) = 1 for any L-valuation v on Form.

If L is the two-element Boolean algebra 2, then the above semantics coincides with the ordinary two-valued semantics for classical logic, where note that T1(ϕ) ↔ ϕ and T0(ϕ) ↔ ¬ϕ are valid in 2-VL, whence all Ta's and Ua's are actually redundant in 2-VL. We then give a Hilbert-style axiomatization of L-VL.

Definition 3. ϕ ∈ Form is provable in L-VL iff it is either an instance of one of the following axioms or deduced from provable formulas by one of the following rules of inference: The axioms are

A1. all instances of tautologies of intuitionistic logic;

• A2. (Ta(ϕ) ∧ Tb(ψ)) → Ta@b (ϕ@ψ) for @ =→, ∧, ∨; Tb(ϕ) → (T@(b) (@(ϕ)) for @ = Ta, Ua;

• A4. ∨a∈L Ta(ϕ); (Ta(ϕ) ∧ Tb(ϕ)) ↔ 0 for a ̸= b; Ta(ϕ) ∨ ¬Ta(ϕ);
• A5. T1(Ta(ϕ)) ↔Ta(ϕ); T0(Ta(ϕ)) ↔ (Ta(ϕ) → 0); Tb(Ta(ϕ)) ↔ 0 for b ̸= 0, 1;
• A6. T1(ϕ) →ϕ; T1(ϕ∧ψ) ↔T1(ϕ) ∧T1(ψ);
• A7. Ua(ϕ) ↔ ∨{Tx(ϕ) ; a ≤ x and x ∈ L};
• A8. (∧a∈L(Ta(ϕ) ↔Ta(ψ))) → (ϕ↔ψ),

where a, b ∈ L and ϕ, ψ ∈ Form. The rules of inference are

• R1. From ϕ and ϕ→ψ infer ψ;
• R2. From ϕ ↔ ψ infer χ ↔ χ′ , where χ′ is the formula obtained from χ by replacing an occurrence of ϕ with ψ;
• R3. From ϕ→ψ infer T1(ϕ) →T1(ψ),

where ϕ, ψ, χ ∈ Form.

(Ta(ϕ) ∧ Tb(ψ)) → Ta→b(ϕ → ψ) intuitively means that if the truth value of ϕ is a and the truth value of ψ is b then the truth value of ϕ → ψ is a → b. The intuitive meanings of the axioms in A2 can be explained in similar ways. Note that Ta(b) and Ua(b) in A2 are either 0 or 1. An axiom ∨a∈L Ta(ϕ) in A4 is called the L-valued excluded middle, since the 2-valued excluded middle coincides with the ordinary excluded middle.

The notion of deducibility for L-VL is defined in the usual way: For ϕ ∈ Form and X ⊂ Form, ϕ is deducible from X in L-VL iff ϕ can be deduced from X and the axioms of L-VL by the inference rules of L-VL. We then have the following deduction theorem for L-VL, which can be shown in almost the same way as delta deduction theorems for fuzzy logics with Baaz delta (see [5, Theorem 6]).

Proposition 4. Let ϕ, ψ1, ..., ψk ∈ Formwhere k ∈ ω\{0}. If ϕ is deducible from {ψ1, ..., ψk} in L-VL, then T1(ψ1∧...∧ ψk) → ϕ is provable in L-VL.

In the following, we show that the above axiomatization of L-VL is sound and complete with respect to the L-valued semantics. We first define the notion of L-VL consistency as follows: For X ⊂ Form, X is L-VL consistent iff 0 is not deducible from X in L-VL. Note that a maximal L-VL consistent subset of Form is closed under the inference rules of L-VL by the maximality of it.

Lemma 5. Let X be a maximal L-VL consistent subset of Form. Then, for any ϕ ∈ Form, there is a unique a ∈ L such that Ta(ϕ) ∈ X.

Proof. Let ϕ ∈ Form. Assume that there is no a ∈ L such that Ta(ϕ) ∈ X. Since X is closed under ∧ and T1, it follows from the maximality of X and Proposition 4 that for each a ∈ L, there is ψa ∈ X such that (ψa ∧ Ta(ϕ)) ↔ 0 is provable in L-VL. Let ψ = ∧a∈L ψa. Note that ψ ∈ X. Now, (ψ ∧ Ta(ϕ)) ↔ 0 is provable in L-VL. By A1, (ψ ∧ ∨a∈L Ta(ϕ)) ↔ 0 is also provable in L-VL. Thus it follows from A1, A4, and R2 that ψ ↔ 0 is provable in LVL. Then, since X is closed under modus ponens, we have 0 ∈ X by ψ ∈ X, which is a contradiction. Hence there is a ∈ L such that Ta(ϕ) ∈ X. The uniqueness of such a ∈ L is shown by using the L-VL consistency of X and the following axiom in A4: (Ta(ϕ)∧Tb(ϕ)) ↔ 0 for a ̸= b.

Theorem 6. For ϕ ∈ Form, ϕ is provable in L-VL iff ϕ is valid in L-VL.

Proof. It is straightforward to show the soundness. We show the completeness by proving the contrapositive. Assume that ϕ is not provable in L-VL. Then, T1(ϕ) is not provable in L-VL by A6. If {¬T1(ϕ)} is not L-VL consistent, then it follows from A1 and an axiom Ta(ϕ) ∨ ¬Ta(ϕ) in A4 that T1(ϕ) is provable in L-VL, which is a contradiction. Thus, {¬T1(ϕ)} is L-VL consistent. By a standard argument using Zorn's lemma we have a maximal L-VL consistent subset X of Form containing ¬T1(ϕ). Then we define a function vX from Form to L as follows: For ψ ∈ Form, vX(ψ) = a ⇔ Ta(ψ) ∈ X. Then it follows from Lemma 5 that vX is well defined. Since ¬T1(ϕ) ∈ X, we have T1(ϕ) /∈ X by A1, which implies that vX(ϕ) ̸= 1. Now it remains to show that vX is an L-valuation. We first verify that vX(ψ → χ) = vX(ψ) → vX(χ). Let a = vX(ψ) and b = vX(χ). Then we have Ta(ψ),Tb(χ) ∈ X. Thus, since X is closed under modus ponens, it follows from A2 that Ta→b(ψ → χ) ∈ X. Therefore, by the definition of vX, we have vX(ψ → χ) = a → b = vX(ψ) → vX(χ). The other cases are similarly verified.

By using the above theorem, it is straightforward to show the following three propositions.

Proposition 7. Let a ∈ L and ϕ, ψ ∈ Form. (i) Ua(ϕ ∧ ψ) ↔ Ua(ϕ) ∧ Ua(ψ) is provable in L-VL. (ii) (ϕ → ψ) → (Ua(ϕ) → Ua(ψ)) is provable in L-VL.

Proposition 8. Let a, b ∈ L with a ̸= 0 and ϕ ∈ Form. (i) Ua(Ub(ϕ)) ↔ Ub(ϕ) is provable in L-VL. (ii) Ua(Tb(ϕ)) ↔ Tb(ϕ) is provable in L-VL.

Although the law of excluded middle does not necessarily hold in L-VL, it holds for a special kind of formulas. The same thing holds also for De Morgan's law and for the commutativity of Ua and ∨.

Proposition 9. Let a, b ∈ L with a ̸= 0 and ϕ, ψ ∈ Form. Assume that Ua(ϕ) ↔ ϕ and Ua(ψ) ↔ ψ are provable in L-VL. (i) ϕ ∨ ¬ϕ is provable in L-VL. (ii) ¬(ϕ ∧ χ) ↔ (¬ϕ ∨ ¬χ) and ¬(ϕ ∨ χ) ↔ (¬ϕ ∧ ¬χ) are provable in LVL. (iii) Ub(ϕ ∨ ψ) ↔ Ub(ϕ) ∨ Ub(ψ) is provable in L-VL.

3 Logic of Fuzzy Belief: L-Kn

In this section, we introduce a logical system for reasoning about fuzzy belief in an n-agent system for a non-negative integer n, which is denoted by L-Kn. The connectives of LKn are unary connectives Bi for i = 1, ..., n and the connectives of L-VL. Then, let Formn denote the set of formulas of L-Kn. The intended meaning of Bi(ϕ) is that the i-th agent believes that ϕ. Thus, the intended meaning of BiUa(ϕ) is that the i-th agent believes ϕ at least to the degree of a or the degree of the i-th agent's belief ϕ is more than or equal to a.

An example of reasoning about fuzzy belief is: If the degree of the i-th agent's belief ϕ is a and if the degree of the i-th agent's belief ψ is more than or equal to a, then the degree of the i-th agent's belief ϕ → ψ is 1. This reasoning is expressed in L-Kn as (BiTa(ϕ) ∧ BiUa(ψ)) → BiT1(ϕ →

ψ), which is both valid and provable in the following semantics and proof system for L-Kn.

An example of reasoning about incomparable beliefs is: If the degree of the i-th agent's belief ϕ and the degree of the i-th agent's belief ψ are incomparable (examples of incomparable beliefs ϕ, ψ are in Section 1), then it does not hold that either if the i-th agent believes ϕ then the i-th agent believes ψ or if the i-th agent believes ψ then the i-th agent believes ϕ. This is expressed in L-Kn as follows (let a and b be incomparable in L with a ∨ b ̸= 1): (BiTa(ϕ) ∧ BiTb(ψ)) → ¬T1((Biϕ → Biψ) ∨ (Biψ → Biϕ)), which is both valid and provable in the following semantics and proof system for a lattice L in which there are such a and b (there are indeed many such lattices L). Recall that (Biϕ → Biψ) ∨ (Biψ → Biϕ) is valid in classical epistemic logic, which is a so-called paradox of material implication. The paradox is avoided in our logical system.

L-valued Kripke semantics for L-Kn is defined as follows.

Definition 10. Let (M, R1, ..., Rn) be a Kripke n-frame, i.e., Ri is a binary relation on a set M for each i = 1, ..., n. Then, a function e : M × Formn → L is an L-Kn valuation on (M, R1, ..., Rn) iff it satisfies the following for each w ∈ M:

1. e(w,Bi(ϕ)) = ∧{e(w′ , ϕ) ; wRiw′ } for i = 1, ..., n;
2. e(w,Ta(ϕ)) = Ta(e(w, ϕ)) for each a ∈ L;
3. e(w,Ua(ϕ)) = Ua(e(w, ϕ)) for each a ∈ L;
4. e(w, ϕ@ψ) = e(w, ϕ)@e(w, ψ) for @= ∧, ∨,→;
5. e(w, a) = a for a = 0, 1.

We call (M, R1, ..., Rn, e) an L-Kn Kripke model. Then, ϕ ∈ Formn is said to be valid in L-Kn iff e(w, ϕ) = 1 for any L-Kn Kripke model (M, R1, ..., Rn, e) and any w ∈ M.

If L is the two-element Boolean algebra, then the above Kripke semantics coincides with the usual Kripke semantics for the K-style logic of belief in an n-agent system. A Hilbert-style axiomatization of L-Kn is given as follows.

Definition 11. ϕ ∈ Formn is provable in L-Kn iff it is either an instance of one of the following axioms or deduced from provable formulas by one of the following rules of inference: The axioms are A1, ..., A8 in Definition 3 and

where a ∈ L and ϕ, ψ ∈ Formn. The rules of inference are R1, R2, R3 in Definition 3 and

We may call the axiom B2 the reduction thesis about belief degrees (see Section 1). If B2 is contested, it is possible to develop another deductive system without B2 that corresponds to Kripke semantics with L-valued accessibility relations. LKn consistency (and L-KCn consistency in the next section) are defined in the same way as L-VL consistency. The axiomatic system above is sound and complete.

Theorem 12. For ϕ ∈ Formn, ϕ is provable in L-Kn iff ϕ is valid in L-Kn.

Proof. It is straightforward to show the soundness. We show the completeness by proving the contrapositive. Assume that ϕ is not provable in L-Kn. Let Con be the set of all maximal L-Kn consistent subsets of Formn. We can consider the LKn Kripke model (Con, R1, ..., Rn, e) such that for each i = 1, ..., n and V,W ∈ Con, VRiW iff, for any a ∈ L and ψ ∈ Formn, Ua(Biψ) ∈ V implies Ua(ψ) ∈ W and that for each propositional variable p, e(W, p) = a iff Ta(p) ∈ W.

We claim that, for any ψ ∈ Formn and W ∈ Con,

We show the claim by induction on the structure of formulas. We consider only the case that ψ is of the form Bi(χ) for i ∈ {1, ..., n}, since arguments in the other cases are similar to those in the proof of Theorem 6. In order to show that e(W,Biχ) = a iff Ta(Biχ) ∈ W, it suffices to show that e(W,Biχ) ≥ a iff Ua(Biχ) ∈ W, since by A7 we have: Ta(Biχ) ∈ W iff Ux(Biχ) ∈ W for any x ∈ L with x ≤ a and Ux(Biχ) /∈ W for any x ∈ L with x ≰ a. If Ua(Biχ) ∈ W, then Ua(χ) ∈ V for any V ∈ Con with WRiV , whence by the induction hypothesis, we have e(W,Biχ) = ∧{e(V, χ) ; WRiV } ≥ a. We next show the converse by proving the contrapositive. Assume Ua(Biχ) /∈W. Let

We first verify that G ∪ {¬Ua(χ)} is L-Kn consistent. Suppose for contradiction that G∪{¬Ua(χ)} is not L-Kn consistent. Then, there is ζ ∈ G such that ζ → Ua(χ) is provable in L-Kn. Thus, Biζ → BiUa(χ) is provable in L-Kn. Since Biζ ∈ W by the definition of G, we have BiUa(χ) ∈ W and so Ua(Biχ) ∈ W by B2, which contradicts Ua(Biχ) /∈ W. Thus, G ∪ {¬Ua(χ)} is L-Kn consistent. By a standard argument using Zorn's lemma, we have a maximal L-Kn consistent subset H of Formn containing G∪{¬Ua(χ)}. Since H contains ¬Ua(χ), it follows from the induction hypothesis that e(H, χ) ≱ a. Since H contains G, it follows from B2 that WRiH. Thus we have e(W,Biχ) ≱ a. This completes the proof of the above claim. Now it is straightforward to verify that (Con, R1, ..., Rn, e) is a counter-model for ϕ.

4 Logic of Fuzzy Common Belief: L-KCn

In this section, we introduce a logical system for reasoning about fuzzy belief and common belief in an n-agent system, which is denoted by L-KCn . The connectives of L-KCn are unary connectives E and C, and the connectives of L-Kn. Let FormCn denote the set of formulas of L-KCn . The intended meaning of E(ϕ) is that every agent in the system believes that ϕ. The intended meaning of C(ϕ) is that it is a common belief among all the agents in the system that ϕ (for the difference between E(ϕ) and C(ϕ), see, e.g., [7]). Thus, the intended meaning of UaC(ϕ) is that ϕ is a common belief at least to the degree of a or the degree of a common belief ϕ is more than or equal to a.

An example of reasoning about fuzzy common belief is: If the degree of a common belief ϕ in the n-agent system is a, then the degree of any agent's belief ϕ is more than or equal to a. This reasoning is expressed in L-KCn as TaC(ϕ) →

(UaB1(ϕ)∧...∧UaBn(ϕ)), which is both valid and provable in the following semantics and proof system for L-KCn .

L-valued Kripke semantics for L-KCn is defined as follows. For a non-negative integer k, Ek (ϕ) is defined by E1 (ϕ) = E(ϕ) and Ek+1 (ϕ) = E(Ek (ϕ)).

Definition 13. Let (M,R1, ...,Rn) be a Kripke n-frame. Then, a function e : M × FormCn → L is an L-KCn valuation on (M,R1, ...,Rn) iff it satisfies the following for each w ∈ M:

1. e(w,E(ϕ)) = ∧{e(w,Bi(ϕ)) ; i = 1, ..., n };
2. e(w,C(ϕ)) = ∧{e(w,Ek (ϕ)) ; k ∈ ω \ {0} };
3. The other conditions are as in Definition 10.

We call (M,R1, ...,Rn, e) an L-KCn Kripke model. Then, ϕ ∈ FormCn is said to be valid in L-KCn iff e(w, ϕ) = 1 for any L-KCn Kripke model (M, R1, ..., Rn, e) and any w ∈ M.

If L is the two-element Boolean algebra, then the above Kripke semantics coincides with the usual Kripke semantics for the (K-style) logic of common belief in an n-agent system (for logics of common knowledge and belief, see [7]). The following notion of reachability is useful for understanding the common belief operator C.

Definition 14. Let (M, R1, ..., Rn) be a Kripke n-frame and w,w′ ∈ M. For a non-negative integer k, w is reachable from w′ in k steps iff there are w0, ...,wk ∈ M such that w0 = w′ , wk = w, and for any l ∈ {0, ..., k - 1}, there is i ∈ {1, ..., n} with wlRiwl+1.

Proposition 15. Let (M,R1, ...,Rn, e) be an L-KCn Kripke model. For w ∈ M, a ∈ L and ϕ ∈ FormCn , e(w, C(ϕ)) ≥ a iff, for any k ∈ ω\{0}, if w′ is reachable from w in k steps, then e(w′ , ϕ) ≥ a.

We now give a Hilbert-style axiomatization of L-KCn .

Definition 16. ϕ ∈ FormCn is provable in L-KCn iff it is either an instance of one of the following axioms or deduced from provable formulas by one of the following rules of inference: The axioms are A1, ..., A8, B1, B2 in Definition 3 and Definition 11, and

• E1. E(ϕ) ↔ (B1(ϕ) ∧ ... ∧Bn(ϕ));
• C1. CUa(ϕ) ↔UaC(ϕ);
• C2. UaC(ϕ) →UaE(ϕ∧C(ϕ)),

where a ∈ L and ϕ ∈ FormCn . The rules of inference are R1, R2, R3, R4 in Definition 3 and Definition 11, and

Using the axioms B1 and B2, we can show the following.

Proposition 17. Let a ∈ L and ϕ ∈ FormCn . (i) EUa(ϕ) ↔ UaE(ϕ) is provable in L-KCn . (ii) E(ϕ∧ψ) ↔ E(ϕ)∧E(ψ) is provable in L-KCn .

The following theorem states that the above axiomatization of L-KCn is sound and complete with respect to L-valued Kripke semantics for L-KCn .

Theorem 18. For ϕ ∈ FormCn , ϕ is provable in L-KCn iff ϕ is valid in L-KCn .

Our proof of the above theorem is rather long and so we put it in the last part of this section. L-KCn enjoys the finite model property:

Theorem 19. For ϕ ∈ FormCn , ϕ is provable in LKCn iff e(w, ϕ) = 1 for any finite L-KCn Kripke model (M, R1, ..., Rn, e) and any w ∈ M.

Proof. The proof of Theorem 18 given below contains the proof of this theorem, since a counter-model (ConC(ϕ),R1, ...,Rn, e) in the proof of Theorem 18 is actually a finite L-KCn Kripke model.

By Theorem 18 and Theorem 19, we obtain the decidability of L-KCn .

Theorem 20. For ϕ ∈ FormCn , it is effectively decidable whether or not ϕ is valid in L-KCn .

Finally, we give the proof of Theorem 18 (though we omit some details) by generalizing the proof of [7, Theorem 4.3]

Proof of Theorem 18. It is straightforward to verify the soundness. The completeness is proved as follows. To show the contrapositive, assume that ϕ is not provable in L-KCn . Let SubC(ϕ) be the set of the following formulas: (i) all subformulas of ϕ; (ii) B1ψ, ..., Bnψ for each subformula Eψ of ϕ; (iii) ψ ∧ Cψ, B1(ψ ∧ Cψ), ..., Bn(ψ ∧ Cψ), E(ψ ∧ Cψ) for each subformula Cψ of ϕ. Let

Define ConC(ϕ) as the set of all maximal L-KCn consistent subsets of Sub+C (ϕ). Then, we can consider the L-KCn Kripke model (ConC(ϕ),R1, ...,Rn, e) such that for each i = 1, ..., n and V,W ∈ ConC(ϕ), VRiW iff, for any a ∈ L and ψ ∈ Sub+C (ϕ), Ua(Biψ) ∈ V implies Ua(ψ) ∈ W and that for each propositional variable p ∈ SubC(ϕ), e(W, p) = a iff Ta(p) ∈ W. Then we claim that, for a ∈ L, ψ ∈ SubC(ϕ) and W ∈ ConC(ϕ),

If the claim holds, then (ConC(ϕ),R1, ...,Rn, e) is a counter-model for ϕ, since there is W ∈ ConC(ϕ) with T1(ϕ) /∈ W (i.e., e(W, ϕ) ̸= 1) by the assumption that ϕ is not provable in L-KCn (such W is obtained as follows: Construct a maximal L-KCn consistent subset X of FormCn containing ¬T1(ϕ) and then let W = X ∩ Sub+C (ϕ)). Thus, to show the completeness, it suffices to verify the claim. Note that the above claim is equivalent to the following: For a ∈ L with a ̸= 0, ψ ∈ SubC(ϕ) and W ∈ ConC(ϕ), e(W, ψ) ≥ a iff Ua(ψ) ∈ W, since we have: Ta(ψ) ∈ W iff Ux(ψ) ∈ W for any x ∈ L with x ≤ a and Ux(ψ) /∈ W for any x ∈ L with x ≰ a. We show the claim by induction on the structure of formulas. We consider only the case that ψ is of the form C(χ), since arguments in the other cases are similar to those in the proofs of Theorem 6 and Theorem 12.

Suppose that ψ is of the formC(χ). It suffices to show that, for any W ∈ ConC(ϕ) and a ∈ L with a ̸= 0, e(W, Cχ) ≥ a iff UaC(χ) ∈ W. We first show that UaC(χ) ∈ W implies e(W,Cχ) ≥ a. Assume UaC(χ) ∈ W. We claim that, for any k ∈ ω \ {0}, if V ∈ ConC(ϕ) is reachable fromW in k steps, then both Ua(χ) and UaC(χ) are in V . This is shown by induction on k ∈ ω\{0}. We first consider the case k = 1. By C2, UaC(χ) → UaE(χ ∧ C(χ)) is provable in L-KCn . Then, by W ∈ ConC(ϕ), we have UaE(χ ∧ C(χ)) ∈ W, whence UaEχ ∈ W and UaE(Cχ) ∈ W by (ii) in Proposition 17 and (i) in Proposition 7. If V is reachable fromW in 1 step, then it follows from E1 and the definition of Ri that Ua(χ) and UaC(χ) are in V. We next consider the case k = k′ + 1 for k′ ∈ ω \ {0}. If V is reachable fromW in k′ +1 steps, then there is V ′ ∈ ConC(ϕ) such that V is reachable from V ′ in 1 step and that V ′ is reachable fromW in k′ steps. By the induction hypothesis, both Ua(χ) and UaC(χ) are in V ′ . By arguing as in the case k = 1, it is verified that both Ua(χ) and UaC(χ) are in V . Thus, the claim has been proved. Hence, for any k ∈ ω \ {0}, if V is reachable from W in k steps, then Ua(χ) ∈ V and so e(V, χ) ≥ a by the induction hypothesis for the first claim. By Proposition 15, we have e(W, Cχ) ≥ a.

In order to complete the proof, we show that e(W, Cχ) ≥ a implies UaC(χ) ∈ W. Assume e(W, Cχ) ≥ a. Define

where note that both V and {∧ V ; V ∈ Γ} are finite sets. We first show that if Ua(ζ) → UaE(χ ∧ ζ) is provable in LKCn , then UaC(χ) ∈ W. Assume that Ua(ζ) → UaE(χ∧ ζ) is provable in L-KCn . Then, by (i) in Proposition 17 and (i) in Proposition 7, Ua(ζ) → E(Ua(χ) ∧ Ua(ζ)) is provable in L-KCn . Then it follows from R5 and C1 that Ua(ζ) → UaC(χ) is provable in L-KCn . Since (∧ W) → ζ is provable in L-KCn by W ∈ Γ, Ua(∧ W) → Ua(ζ) is provable in LKCn by (ii) in Proposition 7. By these facts, Ua(∧ W) → UaC(χ) is provable in L-KCn . Since Ua(∧ W) ↔ (∧ W) is provable in L-KCn by Proposition 8, (∧ W) → UaC(χ) is provable in L-KCn . Hence, we have UaC(χ) ∈ W. Now it only remains to show that the assumption of this argument holds, i.e., Ua(ζ) → UaE(χ∧ζ) is provable in L-KCn , which we omit because of the limitation of space.

5 Conclusions

We have studied the logic of fuzzy belief and common belief with emphasis on incomparable beliefs (which cannot be formalized in previously known systems in [3; 6; 11]), establishing completeness and decidability results (implicitly based on duality-theoretic intuitions). We can also obtain many other versions of the results such as KD45-style and S5-style ones (and many more). We will study their complexity issues in future work.

We emphasize that our system based on L-valued logic can treat both qualitative fuzziness and quantitative fuzziness in the context of epistemic reasoning, while systems based on [0, 1]-valued logic or probabilistic logic (such as those in [3; 6; 11]) can only encompass the latter.

In the previous work such as [14; 15], we studied the mathematically profound aspects of Fitting's many-valued modal logic. The results in the paper suggest that Fitting's logic be beneficial also in the context of artificial intelligence.

We consider that fuzzy reasoning is useful to understand some epistemic problems such as two generals' problem or coordinated attack problem (for this problem, see, e.g., [7]). In theory, the two generals cannot attack at any time, while, in practice, they will attack after they have sent messages a few times. We can understand this as follows. The more times they send messages, the higher the degrees of their beliefs become. Even if the degrees cannot reach 1, the generals will attack when they become sufficiently high. This seems to be a very natural understanding of coordinated attack problem, which is impossible if we stick to classical logic and becomes possible only if we allow fuzzy reasoning.

In the paper we considered the reduction thesis about belief degrees as being provisionally true. Although the reduction thesis would be justified to some degrees by its theoretical merit, in future work, we will discuss in more detail to what extent the reduction thesis is justifiable, since it would be of philosophical interest.