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