On the Logic of Common Belief and Common Knowledge

L. Lismont, P. MONGIN

Theory and Decision

1994, vol. 37, pp.75-106

Departments: Economics & Decision Sciences, GREGHEC (CNRS)

The paper surveys the currently available axiomatizations of common belief (CB) and common knowledge (CK) by means of modal propositional logics. (Throughout, knowledge - whether individual or common - is defined as true belief.) Section 1 introduces the formal method of axiomatization followed by epistemic logicians, especially the syntax-semantics distinction, and the notion of a soundness and completeness theorem. Section 2 explains the syntactical concepts, while briefly discussing their motivations. Two standard semantic constructions, Kripke structures and neighbourhood structures, are introduced in Sections 3 and 4, respectively. It is recalled that Aumann's partitional model of CK is a particular case of a definition in terms of Kripke structures. The paper also restates the well-known fact that Kripke structures can be regarded as particular cases of neighbourhood structures. Section 3 reviews the soundness and completeness theorems proved w.r.t. the former structures by Fagin, Halpern, Moses and Vardi, as well as related results by Lismont. Section 4 reviews the corresponding theorems derived w.r.t. the latter structures by Lismont and Mongin. A general conclusion of the paper is that the axiomatization of CB does not require as strong systems of individual belief as was originally thought - only monotonicity has thus far proved indispensable. Section 5 explains another consequence of general relevance: despite the ''infinitary'' nature of CB, the axiom systems of this paper admit of effective decision procedures, i.e., they are decidable in the logician's sense