Public and private communication are different: Results on relative expressivity (Q1024135)

There are few expressivity results in dynamic epistemic logic. This publication contains such results and is therefore a welcome addition to the literature. What is the point of expressivity? In logic, there is an intimate relation between relational structures and languages used to describe properties of these structures. Some languages can describe more properties than others. We can measure this as follows. Imagine having two different structures. If there is a formula in one of these languages that is true in one structure and false in the other structure, but there is no such formula in the other language, then we conclude that the first language is more expressive than the other language: it is able to `express' a structural difference that cannot be expressed in the other language. Now it may well be that there are yet other structures with a difference that can be expressed in the second but not in the first language: being more expressive is not a total order. Familiar with this structural way to explain expressivity, it surprised us to see Renne define expressivity by way of embedding languages into one another: a language is more expressive than another one if there is an (inductively defined) translation from the latter into the former such that every formula is translated to a logically equivalent formula. But this way of viewing expressivity indeed amounts to the same. In Renne's setting the structures are \textit{pointed multi-agent Kripke models} and the languages are languages of so-called \textit{dynamic epistemic logics}: they contain \textit{epistemic} modal operators modelling belief or knowledge, they may also contain \textit{infinitary epistemic} modal operators (interpreted as fixpoints) standing for common knowledge (or common belief), and they contain \textit{dynamic} modal operators modelling change of belief or knowledge. So, for example, \(K_i p\) stands for `agent \(i\) knows that \(p\)', \(C_{ij} p\) stands for `agents \(i\) and \(j\) commonly know that \(p\)', and \(\neg K_i p \wedge [p \rightarrow i] K_i p\) stands for `agent \(i\) does not know that \(p\) and/but after the announcement of \(p\) to agent \(i\), agent \(i\) knows that \(p\)'. The simplest form of dynamics is known as `public announcement' or \textit{public communication}, as in the dynamic operator \([\phi \rightarrow A]\) where \(A\) is the finite set of all agents, and \(\phi\) the communicated information. There are many types of non-public communication, the author focusses on \textit{private communication} and private communication to a single agent, that we name for convenience \textit{individual communication}. To private communication comes the operator \([\phi \rightarrow G]\) where \(G\) is a (strict) subset of \(A\), and with individual communication comes \([\phi \rightarrow i]\) with \(i \in A\), as in the above example. Although the interpretation of the epistemic operators is indeed `typically' that \(K\) stands for 'knows', in which case the operator is interpreted employing a (structural) accessibility relation that is an equivalence relation, the business of expressivity is conducted such that any structural property may be assumed, where most general case is that no property is assumed: the class of all (pointed) Kripke models. In this more general setting we can now describe Renne's results. If we mention no structural restriction the result is for this most general class. It was known that epistemic logic with public communication is equally expressive as epistemic logic. It was also known that epistemic logic with public communication and common knowledge is more expressive than without common knowledge, and even, if there are at least two agents, when restricted to the class of models with equivalence relations. Given that restriction, if there is a single agent only, the transitivity of an equivalence relation spoils the fun: single-agent epistemic logic with public communication and common knowledge is equally expressive as epistemic logic (because in that case single-agent common knowledge amounts to individual knowledge, modulo a technical issue concerning reflexivity in the closure operation). Further, it was known that epistemic logic with private communication and common knowledge is more expressive than epistemic logic with public communication and common knowledge. Renne's novel results now are that epistemic logic with public communication and common knowledge is more expressive than epistemic logic with private communication and common knowledge, but that, surprisingly, on the class of models with transitive relations epistemic logic with individual communication and common knowledge is equally expressive as epistemic logic with common knowledge. As transitivity corresponds to so-called positive introspection (to know what you know), the author ventures to explain this result by stating that `believing our beliefs imposes a kind of self-dialog', which unlike dialog with other agents should therefore not be expected to increase expressive power; and indeed, it does not. However, the information received by that single agent is not, as the author says, restricted to information about that agent (`single-recipient communication of agent \(i\)'s knowledge to a group \(G\) having \(i \in G\) is in fact a communication received only by \(i\) himself', p.~243) but can be about any agent. I still agree with the intuition: given that all dynamics is individual communication to a given agent, the system is like single-agent epistemic logic with public communication and common knowledge, plus a couple of non-active processes representing the other agents. As stated above, that logic is equally expressive as epistemic logic. Never mind the extra processes. There are a number of other recent results in this area that should be mentioned in this review. A recently proposed notion of \textit{conditional common knowledge} is far more expressive than the notion of common knowledge. We omit details. This makes some of the expressivity hierarchy above collapse, e.g., epistemic logic with public announcement and conditional common knowledge is equally expressive as that logic without public announcement. An overview of such expressivity results is found in [\textit{B. Kooi}, J. Appl. Non-Class. Log. 17, No.~2, 231--253 (2007; Zbl 1185.03014)]. Another result is that epistemic logic with public announcement and (some kind of) quantification over announcements is more expressive than epistemic logic (even without taking common knowledge into account). This is reported in [\textit{P. Balbiani} et al., Rev. Symb. Log. 1, No.~3, 305--334 (2008; Zbl 1208.03019)]. And indeed, as the author states, we are still eagerly awaiting the work by Baltag and Moss on expressivity results for dynamic epistemic logics.