ADVANCED MODAL LOGIC, Spring 2008
Purpose of the Course
This course will present the technical background in modal logic to
current work on logics of rational agency and intelligent interaction.
For a historical
describing my idiosyncratic (though much more true than most)
views on how logic developed in the 20th century,
see this chapter in the Handbook
of the Philosophy of Logic
. For some lively reports from the
research front, see this year's PHIBOOK
We will also tie up with recent dissertations by students in
Amsterdam and at Stanford: Patrick Girard
, Fenrong Liu
, Olivier Roy
are a few names, but there are many more people whose work will come
by, e.g., Audrey
, Eric Pacuit
The course will quickly enable you to understand a range of research
taking place right now. See the Supporting
Feel free to email questions and comments: lots of interesting things
have been brought up in class by many of you -- and as
you must already have noticed, I have not been able to answer all of
them, since many questions are still open in this area.
Week 1 Introduction:
grand program and technical basics
For the technical basics in modal logic,
bisimulation, complexity, connections with classical logics, etc., see
Blackburn & van
Benthem in the Handbook
of Modal Logic.
bisimulation, expressive power, axiomatic completeness.
Some basics are in this
paper on a Farewell
to Loneliness which appeared in Proceedings Logic
Colloquium Muenster 2002.
paper on Logic and
Information, with Maricarmen Martinez, to appear in the Handbook of the Philosophy of
We worked through the technical
basics of modal and epistemic logic that we will need,
emphasizing multi-agent aspects of
epistemic logic beyond standard discussions of
the formalism, and then moving up to
forms of knowledge for groups. Now we are
in a position to see how the dynamic aspects can be brought into
Week 3 Epistemic
logic and dynamics of public hard information
public announcement: dynamic logic, updates, PAL completeness:
see paper for last week.
epistemic logic DEL and completeness. Standard
textbook, but we will explain things in class.
challenge: dealing with common knowledge, involves Kleene's Theorem and
van Eijck & Kooi 2006) or modal mu-calculus (van
Benthem & Ikegami 2008).
We have gone through the basics of public
announcement logic PAL, with an emphasis on understanding
the basic methodology of 'recursion
equations' for knowledge achieved after update, and how this preserves
bisimulation invariance and
completeness. Following that, we have looked at a recent 'protocol
of PAL which describes constrained
historical scenarios for learning and communication, mixing purely
epistemic information with
irreducibly procedural information. This was presented at TARK 2007,
is the most recent
draft. These logics also have
philosophical applications, cf. this paper on the Fitch
Week 4 Dynamic-epistemic
logic of partial observation
surveyed the 'postcard' version of EL + PAL, then looked at connections
with epistemology (Fitch
Paradox) which suggest extensions of PAL in turn [Hoshi and by now 6
co-authors], then returned to
'link cutting' versions of update, and eventually full product update
using event models: examples
(email: cc versus bcc; master's thesis of Ji Ruan), number of
worlds can grow, event models and
preconditions, language, logic. A few issues: (a) background in
branching trees of events (we will
return to this in epistemic-temporal logic; of which DEL forms a
well-chosen fragment), (b) special
case: describing games (e.g., van Ditmarsch'
thesis on "Clue": model size grows from start to mid-
game, then shrinks toward end game, (c) 'protocols' can be dealt with
to some extent by preconditions
(but delicate issue), (d) which properties of M and E are preserved in
the product model MxE?, (e)
epistemology once more: see 7 Bridges
paper. Give up the usual uniformity: describing successful
functioning in interaction with different agents should count as a
hallmark of 'rationality'.
Week 5 Beliefs,
conditional logic, and belief revision in dynamic logic
logics of knowledge, belief, and conditionals, for the next
step of the description of
rational agents: their
capacity for 'self-correction'.
This adds plausibility orderings to epistemic ranges, and
some possible interaction axioms such as epistemic belief
introspection. Then we gave a
complete logic for
belief change under hard information, which hides some 'ugly '
scenarios, such as
information leading to false beliefs. As a result, we raised the issue
a larger repertoire
of epistemic-doxastic notions is needed, with the example of 'safe
belief' in between
K and B. Next, we
turned to belief revision, now done in dynamic
logic style as an account of belief
change under soft
information, viewed as transformations of the plausibility order. We
complete logics, for
radical and conservative revision. More details in the 2007 DLBR paper, and
Stanford thesis of Patrick Girard. Contrast this with the postulational
approach of 'AGM'.
Finally, we discussed
a general format for revision using DEL-style technology shiting the
'policies' into a
plausibility-based event model as input: Priority
Update proposed by Baltag & Smets.
Evening talks by Tomohiro Hoshi on adding
protocols as form of 'procedural information' to PAL/DEL,
its technical theory, and
philosophical applications: e.g., K phi now becomes different from K
throwing new light on the problem of
logical omniscience: Modal Distribution holds for thee first notion,
but no longer for the second. Assaf
Sharon discussed evidence and knowledge, and provided arguments
against omniscience, or even
Hawthorne's weaker variants, showing how even upward monotonicity
of the evidence relation fails if you
take Carnap-style probabilistic (or related more qualitative) scenarios.
Week 6 Preference
statics and dynamics
We discussed how preference can be
reprented between worlds, and then lifted to propositions,
by Patrick Girard, Fenrong Liu, Olivier Roy. For
Better or For Worse
: a survey paper in a
forthcoming book edited by
& Hanson on
Theory and Decision Library
but also vice versa, from priority
graphs to induced world order. Then we looked at dynamic
actions changing such orders, and the
resulting complete logics of preference change. But
eventually, it seems that
preference is entangled with knowledge and belief inside models,
so we considered how that works, too. Finally, we briefly discussed
extensive games as a
setting where information update, belief
revision, and preference change play at the same
time, as a prelude to a dynamic analysis
of multi-agent scenarios which steps back from
the usual hard-wired assumptions of
'standard rationality' for agents, allowing for alternatives.
Week 7 Games
structure, solution procedures, and information flow
under Logic and Games at my research
website. Our topics: games in dynamic-
epistemic logic, game
solution as iterated public announcement (Rational Dynamics), dynamic
logics that analyze
belief change in extensive games - bringign together our earlier
Cf. papers by Krzysztof Apt, Cedric Degremont,
Zvesper; and talk by Sonja Smets.
Week 8 Temporal
logics, protocols, and infinite behaviour over time
Papers with Eric Pacuit, Jelle Gerbrandy, Tomohiro Hoshi.
This class will be taught by
Week 9 Further
topics in current research
Guest presentations by Sonja Smets (games and dynamic
rationality), Cedric Degremont
(dynamic doxastic logic and doxastic temporal logic): information
below, as well as
former Amsterdam & Bloomington student Joshua Sack on probabilitic
You can audit
the course, but if you need credit, get in touch by early May about a
small individual project resulting in a paper.
will have some guests after every block
of topics in the course: epistemic
dynamics, temporal structure, etc.
Format: Thursday evening sessions, 7:30 - at most 9 PM, with brief presentations aimed
Speakers lined up so far:
Assaf Sharon (Stanford)
The presentation will be based on the paper "Evidence and the Openness
of Knowledge" by Assaf Sharon and Levi Spectre.
"This article is driven by a simple idea: in the analysis of knowledge,
the logic of evidence must have a pivotal role.
A proper account of empirical knowledge, in other words, must march in
step with the relation of evidential support.
Appealing as this idea may seem, even among contemporary
epistemologists who address evidence in their theories,
little attention has been given to the actual workings of empirical
evidence. Founding the theory of knowledge on
the basis of empirical evidence, we argue, has ramifications for
epistemology that are wide-ranging as they are
fundamental. Specifically, we argue that, since the relation of
evidential support is not closed under known
entailment, empirical knowledge is also open.
Our argument proceeds in the following form. We inspect some of the
most promising arguments in favor of
epistemic closure and argue that, in face of a proper understanding of
empirical knowledge and its relation to
evidence, they fail. Reflecting on this failure and on the logic of
evidence to which it is traced, we present a
positive argument against the validity of closure and specify its
advantage over the standard argument for
epistemic openness, namely the argument from particular externalist
theories of knowledge. In contrast to
common opinion, we claim, it is not externalist "belief-sensitivity"
that is most congenial to epistemic
openness, but rather an evidentialist account of knowledge.
Without attempting at a full-fledged theory of evidence, we show that
on the modest assumption that evidence
cannot support both a proposition and its negation, or, alternatively,
that information that reduces the probability
of some proposition cannot constitute evidence for its truth, the
relation of evidential support is not closed under
known entailment. We then turn to argue that given a minimal dependence
of knowledge of empirical truths on
evidence, there is good reason to reject a number of intuitively
appealing epistemic principles, including not only
the principle of epistemic closure, but also other, weaker principles.
We present a number of significant benefits
of this position, namely, offering a unified solution to a range of
central epistemological puzzles as well as
an account of their force and resilience to solution outside an
evidential framework. Finally, we turn to
confront potential oppositions to our position.
Another way of stating the objective of this article is as setting a
challenge for epistemic closure: if, as
we argue, the openness of evidence can be established, how can
knowledge of empirical truths be closed?
I will talk about the system TPAL,
which has been introduced in one of Johan's lectures. TPAL introduces a
new semantic structure of 'protocols' on PAL that constrains the
permissible sequences of public announcements.
Giving the framework of TPAL, I will point to some of the research
directions that people (in cluding myself)
have been pursuing recently. Two specific examples from my
current dissertation research are: technical
extensions of TPAL, and epistemological applications, such as
representation of explicit knowledge.
May 8 Audrey Yap (University of Victoria,
What I will talk about on Thursday is the addition of a past-looking
operator to both DEL and TDEL.
In the context of my own work in adding a past operator to DEL, I will
talk about some reasons why
we might want such an operator, and some of the expressive power it
adds, such as the way in which
it allows for talk about learning. But when we look at the way in which
DEL models need to be
modified in order to keep track of the history, we find structures that
look very much like ETL
models. This suggests adding such operators to TDEL, whose models
already have a temporal
structure. So I will also mention joint work with Tomohiro Hoshi
extending his work on TDEL
with the addition of a past modal operator, as well as some further
things we can do in adding the
Past operator to TDEL, for instance, the interaction between past
operators and protocols.
[Paper has been circulated by email.]
No guest lecture!
Hans van Ditmarsch:
of Otago, New Zealand & IRIT, France
Public announcement logic is an extension of multi-agent epistemic
logic with dynamic operators
to model the informational consequences of announcements to the entire
group of agents. Arbitrary
announcement logic is an extension of public announcement logic with a
dynamic modal operator
that expresses what is true after arbitrary announcements. Intuitively,
 phi expresses that phi is
true after an arbitrary announcement psi. An example validity is
<> (Kp v K ~p):
there is always a way to make the value of an atom p known.
I will also present various syntactic fragments and semantic notions
involving knowledge and change,
such as the successful formulas as those for which [phi]phi is valid
(after announcing phi, phi is true),
the knowable as those for which, for all agents, phi -> <> K
phi is valid, and so on: positive, preserved, ...
Some variants of the language provide new opportunities. Instead of
'announcements', we can consider
'informative events', or even 'events'. Some results persist for such
generalizations. Instead of quantifying
over announcements, we can quantify over announcements made by specific
subgroups of agents only.
This interpretation provides a link from knowledge, via knowability, to
ability. Given that announcements
may contain announcements, this interpretation also allows us to
describe protocols, and specify
postconditions of, for example, security protocols between a sender and
Yet another 'version' (quoted to scare: it is technically quite
different) interprets 'an informative event
has taken place' with *refinement* of the current information state, in
the formal sense that is the dual
of simulation. (I.e., from the three conditions for bisimulation, only
'atoms' and 'back' are required.)
This version has promising theoretical results, and can be translated
to bisimulation quantified logics.
Belief Change in Temporal Doxastic Logic.
I will present a recent paper written with Johan van Benthem in which
we compare two modal frameworks
for multi-agent belief revision: dynamic doxastic logics computing
stepwise updates and temporal doxastic
logics describing global system evolutions, both based on plausibility
pre-orders. We prove representation
theorems showing under which conditions a doxastic temporal model can
be represented as the stepwise
evolution of a doxastic model under successive 'priority updates'. I
will also discuss a protocol version of
one of Johan's dynamic logic of belief revision (which is a natural
"belief"-based counterpart to TPAL).
I might discuss a few concrete applications as well.
Joshua Sack: Extending
Probabilistic Dynamic Epistemic Logic
Abstract: Probabilistic epistemic logic (PEL) brings together
qualitative representations of uncertainty
from epistemic logic and quantitative representations of uncertainty
from probabilistic logic. Combining
these two, one can express sentences such as ``Ann believes the
probability the coin landed heads is
either 1 or 0". In his paper "Probabilistic Dynamic Epistemic
Logic", Kooi added dynamics to PEL,
allowing us to express qualitative and quantitative uncertainty of
agents that would result from a
public announcement. This and further work on probabilistic
dynamic epistemic logic (PDEL)
has assumed that every subset of the sample space is measurable.
This talk will propose a method for relaxing the restriction that every
set is measurable in PDEL.
We will look at two potential sources of motivation for doing this in a
dynamic setting. One is
that it may shed light on model transformations, that could be useful
in proving completeness of
a system that adds a previous time operator to PDEL. Another is
from an example given by
Halpern, Fagin, and Tuttle that was meant to motivate why an agent's
sample space should
in some cases be different than the set of worlds the agent considers
Smets: From Dynamic Belief Revision to Dynamic Rationality.
My talk (based on joint work with Alexandru Baltag and Jonathan
Zvesper) is about using recent
developments in Logic to better understand and model ``rationality" in
extensive games, by taking
into account the dynamics of belief. The main idea is that, in
order to correctly factor in the evolution
of players' beliefs (about each other) throughout the game, we need a
novel notion of ``dynamic
rationality". This is a context-dependent (time-dependent),
and ``future-oriented" concept, that presupposes what one may call
``epistemic freedom of choice".
To formalize this notion, we use a belief-revision-friendly version of
Dynamic Epistemic Logic,
obtained by extending Johan van Benthem's logic of conditional belief
and public announcements
with an operator for ``arbitrary announcements" (quantifying over
public announcements). Each
move (to a node v') in an extensive game with perfect information can
be ``simulated" by a public
announcement (that node v' is reachable during the current play). The
operator can be used to capture properties that are ``stable" during
the current play.
I apply the concept of dynamic rationality to propose a new solution to
a famous debate (between
Aumann on one hand, and Stalnaker and Reny), concerning the epistemic
conditions for the
so-called backward-induction solution. ``Backward induction" is the
oldest, simplest and perhaps
the most natural solution concept in Game Theory. But the reasoning
underlying this solution
seems to give rise to a fundamental paradox (the so-called ``BI
paradox"). I use the concepts
developed in this talk to address the paradox, and I argue that the
correct epistemic condition
underlying the backward induction method is more general and weaker
than Aumann's: `
`common knowledge of stable belief in (dynamic) rationality".
There will also be a Stanford Workshop
on Logic and Formal Epistemology
31 - June 1st.
to the top
Back to Home