Bisimulations on Planet Kripke Jelle Gerbrandy Abstract: %Nr: DS-1999-01 %Author: Jelle Gerbrandy %Title: Bisimulations on Planet Kripke Summarized in four words, the topic of this dissertation is Multi-Agent Dynamic Epistemic Semantics. The words `semantics' implies that model theory plays a central role, the phrase `epistemic' marks the fact that we are concerned with information (knowledge, belief), `dynamic' stands for the fact that change of information is addressed, and the phrase `multi-agent' says that there may be more than one agent involved. Epistemic semantics has been a subject that can stand on its own since the work of [3]Hintikka about knowledge and belief and the proposal of Kripke for a semantics of modal logic. These authors were concerned with extending propositional logic with a modal operator (I will write ` K '). Given a sentence P , we can make a new sentence K P that, in epistemic logic, is to be read as `it is believed that P.' The insight of Kripke and Hintikka was that this operator can be given a semantics using `possibilities' and a relation of accessability between these possibilities. The accessability relation obtains between possibilities w and v exactly when v is compatible with what is believed in w . One can then define that a sentence of the form K P is true in a world w just in case P is true in all models that are compatible with what is known in w . In this dissertation, this semantics is taken as a starting point. I study and develop extensions of this semantics in two dimensions: it is made `multi-agent' and `dynamic.' The `multi-agent' part is the topic of the [4]third chapter. Here, I study an extension of epistemic logic where there is not one single modal operator K, but a whole family of operators of the form Ka present in the language, where a is the name of an agent. A sentence Ka P can be read as: `Agent a believes that P is true;' its semantics is just like that of K, except that for each agent a there is a corresponding accessability relation in the model. The sem/gerbrand/antics for this multi-agent logic makes it possible to define a number of new operators that are interesting from a philosophical as well as from a logical perspective. Already familiar from the literature are operators for `common knowledge' and for `distributed knowledge.' Both of these operators raise issues about the status of the semantics. Both have interesting completeness proofs as well. Newly introduced in this thesis is the concept of combined knowledge, which is very similar to, but different from, distributed knowledge. Moreover, I briefly discuss how the meaning of these operators can be made dependent on the `topic' they are about. The two chapters after that, [5]chapters 4 and [6]5, are about the extension of epistemic logic with epistemic actions. I add `programs' to the language of epistemic logic that denote changes in the world. For example, there is a program that expresses that the agents a and b both learn that c learnt that P is true. In [7]chapter 4, I define a semantics for this extension of the language, and give a sound and complete axiomatization of the resulting logic. The logic as a number of interesting properties. One of these is that learning that a sentence is true does not always mean that you reach a state in which you believe that this sentence is true. In the last chapter, this property of the logic is used to explain certain puzzling phenomena that arise in communication. Several authors have written about information change in epistemic logic before. In [8]chapter 5, I compare the work of some of them with the semantics I defined in chapter 4. In the last two chapters I show some ways that the semantics developed in this thesis can be useful for a formal analysis of dialogue. [9]The sixth chapter is a discussion of some aspects of the concept of `common ground' as it is used in theory of dialogue. In particular, it is about the relation between changes in the common ground and changes in the separate information states of the dialogue participants separately. In [10]the last chapter, I discuss two puzzles that are related to information change: the `puzzle of the dirty children' and the `surprise exam paradox.' Both of these puzzles can be straightforwardly described in the language that was defined in the earlier chapters. The associated effects of change of information provide an explanation of some of the more salient aspects of these puzzles. The dissertation ends with a description of a simple dialogue game. I have not mentioned the first two chapters in this abstract yet. These chapters are more technical in character and are supposed to provide the background to the formal methods used in the thesis. Instead of the usual set-theory, I have used [11]non-well-founded set-theory in modeling epistemic logic. Since this theory is not very familiar, I have thought it useful to add a general introduction to this topic. The main reason for using such a non-standard framework is that it allows for a more straightforward and elegant way of defining operations that change models. Non-well-founded models for epistemic logic differ from the more standard Kripke models in that the latter way of modeling information allows for making distinctions that cannot be made in the former. In effect, using non-well-founded models means collapsing distinctions between Kripke models that are bisimilar. [12]The second chapter contains a number of results about bisimulation and its relation with modal logic that together provide circumstantial evidence that collapsing distinctions between bisimilar models is harmless. References 1. ftp://moon.philo.uva.nl/pub/gerbrand/proefschrift.dvi 2. ftp://moon.philo.uva.nl/pub/stokhof/Textures_Reader.sea.hqx 3. http://www.bu.edu/linguistics/APPLIED/FACULTY/hintikka.html 4. ftp://moon.philo.uva.nl/pub/gerbrand/chapter3.dvi 5. ftp://moon.philo.uva.nl/pub/gerbrand/chapter4.dvi 6. ftp://moon.philo.uva.nl/pub/gerbrand/chapter5.dvi 7. ftp://moon.philo.uva.nl/pub/gerbrand/chapter4.dvi 8. ftp://moon.philo.uva.nl/pub/gerbrand/chapter5.dvi 9. ftp://moon.philo.uva.nl/pub/gerbrand/chapter6.dvi 10. ftp://moon.philo.uva.nl/pub/gerbrand/chapter7.dvi 11. ftp://moon.philo.uva.nl/pub/gerbrand/chapter1.dvi 12. ftp://moon.philo.uva.nl/pub/gerbrand/chapter2.dvi