Logical Dynamics of Information and Interaction

Placeholder book cover

Johan van Benthem, Logical Dynamics of Information and Interaction, Cambridge University Press, 2011, 386pp., $90.00 (hbk), ISBN 9780521765794.

Reviewed by Kohei Kishida, University of Amsterdam


Modal logic originated as a branch of non-classical logic that concerned necessity and possibility as modes of truth or entailment; but it found a much broader range of applications both within and outside philosophy. On the one hand, it can be used to express various modes of truth -- analytic, metaphysical, deontic, epistemic, and so on -- that are interesting in philosophy, linguistics, and other disciplines. On the other hand, the rise of Kripke semantics has established modal logic as a mathematical study of relational structures -- and, in particular, of transitional structures of a system shifting from one state to another -- of the sort found in computer science, artificial intelligence, game theory and many other disciplines. These two directions of application developed somewhat separately, but the recent development in modal logic has provided a natural locus in which they are brought together. Johan van Benthem is among those who pioneered in this area and are leading its expansion. His book, based on his lectures and papers, gives a masterly guide to this vast region, from its early settlement to the front lines, with a view of even further frontiers.

The book being in a way a manifesto by van Benthem for a research program he dubs logical dynamics, a review of the book has to be at the same time a review of the program, which is to expand the scope of research in logic to encompass any rational or intelligent aspects found in agency and interactions among agents. I will try to convey general ideas of van Benthem's goals and of the approaches or stances he takes in carrying out his enterprise. The introductory Chapter 1 gives an overview of the book as well as of the program of logical dynamics; taking advantage of well-designed examples (including the celebrated puzzle of Muddy Children), it delineates principal themes and issues that the program (and so the book) will address, and describes key ideas and methods employed in addressing them.

Chapters 2 through 4 expound the basic core of logical dynamics, namely, dynamic epistemic logic(s). Chapter 2 introduces its static part, that is, epistemic logic for agents (and groups of agents), a kind of modal logic with a modal operator Ki for each agent i to be considered. It is modeled by 'possible world' semantics in the standard Kripke fashion, and has familiar axiomatic systems (K, T, S5, etc.). (We should note that, for van Benthem, the notion of possible world is a tool for the "art of modelling" that is not metaphysically loaded; we should read his book after first "dispel[ling] delusions of grandeur about possible worlds" (p. 24).) The chapter also discusses several concepts that are crucial in the metatheory of modal logic, namely, bisimulation and invariance under it (which are all the more significant when we take possible worlds primarily as a tool for modelling), expressive power, and computational complexity. (These themes recur in later chapters for the logics treated there.) Interestingly, van Benthem treats completeness as a "less dominant" theme, saying "To me, modal logics are not primarily about inferential life-styles like K, KD45, or S5, but about describing agency" (p. 21).

In the semantics laid out here, a model assigns to each agent i an epistemic accessibility (or 'epistemic alternative') relation among possible worlds, and a sentence Kiφ is deemed true at a world s just in case φ is true at all the worlds that are i's 'epistemic alternatives' to s. This version of epistemic logic, which is due to Hintikka 1962, has been conventionally taken as about agents' knowledge, with Kiφ read as 'i knows that φ.' Van Benthem takes it differently (and rightly, as many formal epistemologists would say), saying that he "drop[s] the claim that the K-operator stands for knowledge in any philosophical sense, making it a statement about current semantic information instead" (p. 42); and the same applies to the K operator of the logics laid out in later chapters. An adequate concept of knowledge has many more conceptual components than just the K operator; as part of his program, van Benthem shows in Chapters 5 and on how to provide formalism for these components.

In van Benthem's informational interpretation, the accessibility relation sit means that world t is consistent with the information which i currently has at world s. Hence, under the truth condition mentioned above, Kiφ means that the information which i has entails φ, by ruling out any possibility that φ is false. Also, given a group G of agents, its epistemic accessibility relation can be variously defined from those of its members, giving rise to various 'knowledge' operators for the group. For instance, 'φ is common knowledge in G' is true at s just in case φ is true at all worlds t that can be reached from s by concatenating →i for agents i in G (for instance, t such that sis'js''kt for some worlds s', s'' and agents i, j, k in G); it roughly means that, not only does each agent (in G) know that φ, each agent also knows that each agent knows that φ, which is in turn known to each agent, ad infinitum.

Chapters 3 and 4 'dynamify' this logic of 'knowledge'; as a first step, Chapter 3 lays out public announcement logic, or PAL for short, a kind of dynamic logic. In general, dynamic logics have 'effect' modalities [A]; the sentence [A]φ is supposed to mean that φ will be the case after an action (or event) A is (successfully) taken (or takes place). An encyclopedic variety of dynamic modalities appear in the rest of the book. PAL considers, in particular, the event !ψ (for any sentence ψ) in which agents publicly obtain the information that ψ (where 'publicly' signifies that it is 'common knowledge' that each agent has obtained the same information, as in cc'ing of emails as opposed to bcc'ing); it is customary to call !ψ 'public announcement,' but van Benthem rightly points out that PAL applies equally to a wider range of informational update events such as public observation.

Van Benthem's semantics of dynamic modalities involves updates of models. The event !ψ, in particular, eliminates all the worlds at which ψ is false, in effect making every agent in every world rule out the possibility that ψ is false; and [!ψ]φ is deemed true at world s in the original model just in case (if ψ is true then) φ is true at s in the new model. Then it is easy to see that [!ψ]p is equivalent to ψ→p (if ψ then p, materially) for atomic p; moreover, [!ψφ, [!ψ]( φ1φ2), and [!ψ] Kiφ are equivalent to ψ→¬[!ψ]φ, [!ψ]( φ1φ2) and ψKi[!ψ]φ, respectively. These equivalences reduce any sentence with [!ψ] to one without, by pushing [!ψ] of [!ψ]φ inward when φ is compound and eventually eliminating [!ψ] when φ is atomic, thereby reducing PAL to (static) epistemic logic and hence completely axiomatizing it. Most of the dynamic logics that appear in later chapters are also axiomatized by reduction to their static bases (although the reduction becomes hard in the presence of some operators such as common knowledge). Van Benthem provides arguments on pp. 61f. that such reduction does not reduce the significance of dynamic logics. It is interesting to observe that [!ψ]Kiψ is valid if ψ contains no modal operator, but not valid in general: it can be false when ψ is, for instance, a Moore-type sentence φ∧¬Kiφ, 'you don't know it but φ.'

Chapter 4 treats information update in full generality, by laying out dynamic epistemic logic, or DEL, which deals with various modes of obtaining information and not just obtaining publicly. For instance, when an agent i has received a private email, another agent j may not know its content, or may not even know that i has received it; or j may know it whereas i believes otherwise. The semantics is given by product update, the key idea of which is to introduce a Kripke frame E of events rather than of worlds; in E, i may be, while j may not be, able to distinguish an event e (for instance, i's peeking at a card in red suits, without revealing it to j) from another event f (a card in black suits). E also assigns to each event e a precondition, determining the worlds in M at which e can take place. The product update of a model M by E gives a new model, M×E, in which worlds are pairs (s, e) of a world s from M and an event e in E such that e can take place at s; then, at (s, e), or s-after-e, i rules out t-after-f just in case she either already knew at s that t was not the case or knows at s-after-e that f did not take place. So, for instance, even if i cannot rule out t (where the card is black) at s (where the card is red), if she can distinguish e (her peeking and finding the card red) from any event f that can take place at t, then i can rule out t (-after-f for any f) at s-after-e (thereby learning that the card is red).

In Chapters 5 through 9, van Benthem turns to the enterprise of formalizing components of logical dynamics that are missing from the dynamic logic of the K operator. First, in Chapter 5, he gives an explicit expression to the dynamics of inference. Consider the following simple example of inference: (a) An agent i learns that pq and that ¬p, and then (b) she infers that q. In the semantics of Chapters 2 through 4 -- in which the truth value of a sentence is relative to worlds alone -- a model undergoes an update at step (a) but no change at (b) (consider a 4-row truth table for p and q; at (a), i rules out and strikes through three rows, but then, before and after (b), the table looks just the same). Thus the type of semantics cannot express what takes place at (b), or what takes place when an agent makes an inference. Van Benthem fills in this gap with various modal operators for an agent's 'awareness.' Their semantics distinguishes between cases in which i pays attention to q and in which she does not (consider how different the truth table is before and after i check-marks the q entry of its remaining row); formally, the truth value of a sentence is no longer relative to worlds, but to pairs consisting of a world and a set of sentences (to which i pays attention).

Chapter 6 shows how a logic of questions can be incorporated into the framework of dynamic epistemic logic. One advantage of expressing questions in the multi-agent setting of this framework is that the logic can express by whom (say, an agent i) and to whom (another j) a given question is given -- an aspect of the question that carries information by itself, such as that i does not know the answer or that i thinks it possible that j knows the answer. A further advantage is, then, that the semantics of dynamic epistemic logic is already complete with natural machinery to express such information, namely, a precondition of the question action.

In the dynamic epistemic logic of Chapters 2 through 4, the kind of information the K operator expresses is 'hard,' as van Benthem calls it, in the sense that once an agent rules out a possibility by learning something, no event can ever make her retract it. In contrast, Chapter 7 discusses 'soft information' that can be retracted, and incorporates various formalisms for belief revision into the framework of information update. In the semantics, each agent i at each world s orders worlds (with a pre-order, i.e., a reflexive and transitive relation) according to how plausible she finds them (at s); then the sentence Biφ, 'i believes that φ,' means that φ is true in all the worlds that i finds the most (maximally, to be precise) plausible. The belief can then be updated either in the hard fashion of Chapters 3 and 4, or in soft fashions by revising the plausibility order in various ways.

Starting with the Monty Hall problem as a motivating example, Chapter 8 incorporates probability into dynamic epistemic logic. Then the language contains sentences of the form Pi(φ)=q (for a rational number q), which means that the probability (for an agent i) that φ is q, and a possible-world model M has a probability distribution (for each agent at each world) over worlds. Moreover, an event model E has probability distributions, which naturally induce probability distributions in the new possible-world model M×E that results from the product update. (As van Benthem makes clear, this setup involves subjective probability over which world is the case and both objective and subjective probabilities over which event takes place.)

The chapters so far only dealt with epistemic and doxastic aspects of logical dynamics, but no pragmatic aspects; Chapter 9 introduces preference to the framework. In the semantics, each agent at each world (pre-)orders worlds according to her preference (van Benthem uses the word 'betterness,' to avoid various connotations of 'preference'), in just the same way as in the plausibility semantics of Chapter 7. So, in a manner similar to the soft information update of Chapter 7, preference orders can also be updated, by suggestions or commands.

Chapter 10 gives "pilot studies rather than grand theory" (p. 222) of how the formalisms laid out so far (or some of them) interact with each other, in a setting of games. (Here I notice that materials from Chapters 5 and 6 are absent.) For instance, a game tree can be regarded as a (static) possible-world model with accessibility relations for moves connecting nodes; so, even without dynamic epistemic logic, backward induction on a tree can be defined in the logic of preference of Chapter 9, and knowledge operators can express games with imperfect information. A certain kind of tree can also be regarded dynamically, as generated by successive updates of models (Chapter 11 investigates this insight thoroughly); hence dynamic epistemic logic can also express games. Moreover, the same logic can also express game-changing events; for instance, promises can eliminate branches of a tree (in the way public announcements of Chapter 3 rule out possibilities). This hard type of game change can be generalized to soft information and belief as well. Thus, it becomes a part of logical dynamics how, for instance, agents can foresee undesirable Nash equilibria and then avoid them through communications, contracts, etc.

Chapter 11 discusses the relation between dynamic epistemic logic and epistemic temporal logic, a variant of temporal logic. Roughly speaking, when worlds in a model are regarded as points of time, sequences of update (by various events) of the model into one after another yield a discrete branching-time structure; van Benthem formalizes this insight into a representation theorem.

The chapters so far mostly discussed knowledge, belief, preference and other modal operators for individual agents; Chapter 12 discusses these concepts for groups of agents. One theme is to use dynamic epistemic logic to express how agents communicate with each other to merge the information they individually have, and then form (or fail to form) 'common knowledge.' Another theme is how agents, each with their own plausibility and preference orders, merge their orders together and form ones for the group. Moreover, an individual agent can be regarded as a group of agents; the agent may have or receive different 'signals' for different plausibility (or preference) orders, and merge them into her own order -- this gives a more fine-grained analysis of belief revision.

The last quarter of the book is devoted to discussions of how the framework of logical dynamics presented in the book, its machinery, and its future developments are related (or even applicable) to neighboring disciplines. Chapter 13 relates insights from logical dynamics to philosophical issues. First, van Benthem dynamically explicates the Fitch paradox and the paradox of the knower: the phenomenon observed in Chapter 3 of self-refuting assertions (such as a Moore-type sentence φ∧¬Kiφ) offers an illumination of how (the dynamic version of) the so-called Verificationist Thesis, "A formula φ that is true may come to be known" (p. 271), can fail (van Benthem stresses that making self-refuting assertions can nonetheless be informative and bring about knowledge). Also, after briefly surveying various accounts of knowledge in the philosophical literature -- knowledge as justified true belief, most notably -- van Benthem claims that logical dynamics aptly captures a pattern that they share in terms of robustness under informational dynamics.

Other topics of the chapter include different conceptions (semantic, syntactic, and correlation-based) of information; characteristic features of rational agents and agency; logical-dynamic aspects of agency found in science and mathematics; and the relationship between different logics. Taking advantage of Kripke semantics for intuitionistic logic, van Benthem compares intuitionistic logic to the dynamic epistemic logic of information. Moreover, in his discussion of the question of what logic is, van Benthem extends the same sort of comparison to non-monotonic, substructural, and other logics on the one hand and logical dynamics on the other: Their relationship is one of 'abstraction' and 'representation,' in which the latter framework aims to elucidate phenomena behind the consequence relations of the former, using the explicit vocabulary of modal operators on the basis of classical logic. (Indeed, this explanation-oriented stance of van Benthem's is evident throughout the book.)

Chapter 14 discusses the relation between logical dynamics and computation: expressed in terms of logical dynamics, a conversation can be regarded as a process of computation; on the other hand, computation can be 'epistemized' and 'gamified,' to be merged with the interactive agency in logical dynamics. Chapter 15 extends Chapter 10 by further discussing the link between logical dynamics and game theory. In Chapter 16, van Benthem discusses the connection between logic and cognitive science: after describing how the research in logic (which he maintains to be primarily a normative subject) and the empirical study of human cognition have recently influenced each other, he lays out what he calls 'modest psychologism.' Chapter 17 concludes the book.

The book contains some typographical and editorial errors (e.g., in Chapter 3, the three-line footnotes 1 and 6 are identical, and footnote 4 is missing; in Chapter 8, there are two Sections 8.7, and Mr. Monty Hall first opens a wrong door), but I would say they are few for a book of this size. While van Benthem often mentions that logical dynamics can help tackle certain philosophical issues or questions, he tends to merely sketch how, rather than to fully take up the issues and questions by himself, which philosophical readers may find tantalizing.

Each of Chapters 2 through 12 closes with a section discussing further directions and open problems for the machinery presented in the chapter. Yet there seem to be some issues that should be, but are not, mentioned in those sections or in the book -- I mention two here. The first concerns the awareness operators laid out in Chapter 5. As van Benthem says, the book is generally guided by "a Tandem Principle from computer science: Never study static notions without studying the dynamic processes that use them" (p. 276). The notion of awareness, however, seems to be studied without much regard to what dynamic roles awareness plays. An agent's knowledge that φ is labeled 'explicit' or 'implicit' depending on whether or not she pays attention to φ; yet it is left unexamined what difference these labels make to her actions or to her judgments other than those regarding φ. A natural place for this topic would have been Chapter 10.

Another topic that I find missing from the book is the updating of languages. In the formalism presented in the book, dynamic processes update models semantically, but, syntactically, the vocabulary of a (so-called object) language is fixed and stays the same throughout the processes. This is fine, as long as that language is just a tool that we use to describe the behavior of the system of agents; but if it is a language that the agents use, or if it is at least something that corresponds to what the agents use in reasoning and inference (otherwise the awareness operators would seem pointless), logical dynamics should consider it in a dynamic light. In a scientific or any kind of inquiry, we do not only learn what is true or plausible, but also discover that it is helpful to name certain things or to introduce certain notions. New notions can help the inquiry both conceptually, by making clearer the conceptual relationship among what we know, and computationally, by reducing the amount of resources needed to store the information or to infer things from it.

I just mentioned two issues that the book does not address but that I believe should be dealt with in logical dynamics; yet I do not mean to indicate shortcomings of the book. As van Benthem says in the concluding chapter, "This book is just a beginning, and there are further things on the horizon" (p. 344). The goal of the book, as I take it, is instead to lay out the program of logical dynamics, its scope, themes, methods, stances, and, most importantly, fruits and insights, to students and researchers of logic as well as of neighboring disciplines, not least of philosophy, and to invite them to contribute their insights to further expansion of this program of an interdisciplinary nature. I agree with van Benthem that "things have changed, and contacts between logic and philosophy deserve a new try" (p. 277), and his thorough exposition of logical dynamics has demonstrated to me, and should demonstrate to any reader, that such contacts can be immensely fruitful, between logic and philosophy as well as other disciplines. For this reason I find van Benthem's book to be a masterly success.


J. Hintikka (1962) Knowledge and Belief, Cornell University Press.