Johan van Benthem

Home / Activities / Publications / Teaching / Research / Talks

Philosophy 359, 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 paper 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 Yap, Tomohiro Hoshi, Eric Pacuit, and others.
The course will quickly enable you to understand a range of research taking place right now. See the Supporting Activities below.

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.

Preliminary Schedule

Week 1          Introduction: grand program and technical basics

For a survey paper of the Grand Program, see this invited lecture at the 13th Congress of Logic, Methodology and Philosophy of Science
held in Beijing, August 2008. Some Stanford philosophers have really very similar aims, cf. John Perry's Admit Seminar on April 4th.

          For the technical basics in modal logic, bisimulation, complexity, connections with classical logics, etc., see this introductory chapter by
          Blackburn & van Benthem in the Handbook of Modal Logic.

Week 2          Epistemic logic: statics

Languages, bisimulation, expressive power, axiomatic completeness.

          Some basics are in this paper on a Farewell to Loneliness which appeared in Proceedings Logic Colloquium Muenster 2002.

Background paper on Logic and Information, with Maricarmen Martinez, to appear in the Handbook of the Philosophy of Information.

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 logical focus.

Week 3          Epistemic logic and dynamics of public hard information

Logic of public announcement: dynamic logic, updates, PAL completeness: see  paper for last week.

Dynamic epistemic logic DEL and completeness. Standard textbook, but we will explain things in class.

Special challenge: dealing with common knowledge, involves Kleene's Theorem and automata
(van Benthem, 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 version' TPAL
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, but here
is the most recent draft. These logics also have philosophical applications, cf. this paper on the Fitch Paradox.

Week 4          Dynamic-epistemic logic of  partial observation

We 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

          We discussed combined 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
          we discussed 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
          misleading true information leading to false beliefs. As a result, we raised the issue whether perhaps
          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 gave some
          complete logics, for radical and conservative revision. More details in the 2007 DLBR paper, and
          the 2008 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 different
          '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 <!phi>T,
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

Dissertations by Patrick Girard, Fenrong Liu, Olivier Roy. For Better or For Worse: a survey paper in a
forthcoming book edited
by Gruene & Hanson on preference change (Springer Theory and Decision Library).
        We discussed how preference can be reprented between worlds, and then lifted to propositions,
          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

          Check papers 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 approaches.
          Cf. papers by Krzysztof Apt, Cedric Degremont, and Jonathan 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
 Eric Pacuit [Stanford; co-organizer of an upcoming ESSLLI Workshop this August].

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 DEL.


            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.

Supporting Activities

 We 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 toward discussion.
Speakers lined up so far:

May 1 
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?

Tomohiro Hoshi (Stanford)
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, formerly Stanford)

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.]

May 15

No guest lecture!

May 22

Hans van Ditmarsch:
University of Otago, New Zealand & IRIT, France

Quantifying over Announcements

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 receiver.

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.

May 29

Cedric Degremont: 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 possible.

Sonja 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), knowledge-dependent, belief-based
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 arbitrary announcement
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 May 31 - June 1st.

Universiteit van Amsterdam

Logic in Action



Back to the top

Back to Home