## Johan van BenthemHome
/ Activities / Publications / Teaching
/ Research / Talks |

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.

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.

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*

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.

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

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*

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 behaviou**r over time*

Eric Pacuit
[Stanford; co-organizer of an upcoming ESSLLI Workshop
this August].

(dynamic doxastic logic and doxastic temporal logic): information below, as well as

former Amsterdam & Bloomington student Joshua Sack on probabilitic DEL.

**Credits
**

**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".

NOTE:

There will also be a Stanford Workshop on Logic and Formal Epistemology May 31 - June 1st.

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

NOTE:

There will also be a Stanford Workshop on Logic and Formal Epistemology May 31 - June 1st.