Belief Revision and Dynamic Logic

Abstract

We explore belief change policies in a modal dynamic logic that explicitly delineates knowledge, belief, plausibility and the dynamics of these notions. Taking a Kripke semantics counterpart to Grove semantics for AGM as a starting point, we analyse belief in a basic modal language containing epistemic and doxastic modalities. We critically discuss some philosophical presuppositions underlying various modelling assumptions commonly made in the literature, such as the limit assumption and negative introspection for knowledge. Finally, we introduce in the language a general dynamic mechanism and define various policies of iterated belief expansion, revision, contraction and two-dimensional belief change operations.

1 Introduction

The history of belief revision is one in which researchers from various fields have tackled the same problem from different perspectives, but it originated from philosophy. After earlier work of Isaac Levi and William Harper, Carlos Alchourrón, Peter Gärdenfors and David Makinson (often referred to by the acronym “${\mathsf {AGM}}$”) initiated the formal study of belief change operations in the 1980s. They analyzed belief change using three kinds of models: partial meet contractions and revisions (in terms of maximal non-implying sets [1]), safe contractions and revisions (in terms of minimal implying sets of sentences [2]), and entrenchment-based contractions and revisions (based on the comparative retractability of sentences [25]). Grove [29] provided a possible worlds semantics for partial meet contraction. Iterated belief change was addressed in the 1990s, with important contributions by Boutilier [16], Darwiche and Pearl [17] and Nayak [37]. More recently, van Benthem [9], and Baltag and Smets [4, 5] modelled epistemic and doxastic states and their transformations on simple relational structures, introducing a new complexity due to the analysis of higher-order belief and knowledge. The relevant problems were attacked in a plethora of ways that may sometimes be differentiated by the degree of abstraction adopted.¹ Influenced by van Benthem, we choose our level of abstraction in line with a modular and minimalist attitude. This means that we only assume constraints on models when they become necessary, with philosophical awareness, and we use formal languages as simple as we can.

• Minimality: We try to keep the assumptions on models to be minimal, and we try to keep our basic object language as simple as possible.

• Modularity: We analyse the key notions of knowledge and belief in terms of two primitive relations representing indistinguishability and plausibility. We also break down complex dynamic notions into simpler parts using the programmatic $\mathsf {PDL}$ language.

2 Grove Systems of Spheres

In retrospect it looks as if ${\mathsf {AGM}}$ followed a purely syntactic approach to belief revision. We think that this is not quite correct, for both belief sets and inputs for belief change were essentially individuated only up to logical equivalence. Still it was a very important step for the program of belief revision when Adam Grove [29] provided a possible worlds semantics for ${\mathsf {AGM}}$’s partial meet contractions. He used systems of spheres to model belief change, closely following the seminal work of Lewis [18] on counterfactuals. We summarise Grove’s semantics in some detail, and later show how to adapt the notation and interpretation to our needs.

Given a language $\fancyscript{L}$, define a theory $T$ over $\fancyscript{L}$ as a set of $\fancyscript{L}$-sentences that are logically closed, i.e., for which $\mathsf {cl}(T) \subseteq T$. Here $\mathsf {cl}(\cdot )$ is an operation that forms the logical closure of a set of sentences from $\fancyscript{L}$. A possible world for $\fancyscript{L}$ is an entity that assigns, for each atom of $\fancyscript{L}$, a truth value $1$ (for “true”) or $0$ (for “false”).² We denote by $W$ the set of all possible worlds, and by $\,[\![\varphi ]\!]\,$ or $\,[\![T]\!]\,$ the set of all possible worlds that satisfy a sentence $\varphi$ or a set of sentences $T$. For a set of worlds $V$, we denote by $\mathsf {Theory}(V)$ the set of sentences true at each world in $V$.

A Grove system of spheres centered around a set $\fancyscript{B}$ of possible worlds for $\fancyscript{L}$ is a set $\$_\fancyscript{B}\, = \, \{S|S\subseteq W\}$ that satisfies the following conditions³:

• 1. $\$_\fancyscript{B}$ is totally ordered by set-containment $\subseteq$,

• 2. $\fancyscript{B}\in \$_\fancyscript{B}$,

• 3. $\fancyscript{B}\subseteq U$ for every $U\in \$_\fancyscript{B}$,

• 4. The limit assumption: For any sentence $\varphi$, if there is a sphere $S\in \$_\fancyscript{B}$ which intersects $\,[\![\varphi ]\!]\,$, then there is a smallest sphere $S'\in \$_\fancyscript{B}$ which intersects $\,[\![\varphi ]\!]\,$.

A Grove system of spheres is called

• 5a. universal if in addition, $W = \bigcup \$_\fancyscript{B}$; or

• 5b. strongly universal if in addition, $W \in \$_\fancyscript{B}$.

The term “universal” is taken over from Lewis [18, p. 16]. Grove originally required his doxastic systems of spheres to be strongly universal. We choose to deviate from this by requiring not even universality. We do not want to rule out that an agent may consider some metaphysically possible worlds inconceivable.

Belief in a Grovean sphere system is identified with the innermost sphere $\fancyscript{B}$ of $\$_\fancyscript{B}$.⁴ More precisely, a belief set in Grove spheres is identified with the set of all sentences $\mathsf {Theory}(\fancyscript{B})$ that are true throughout the innermost sphere $\fancyscript{B}$ in $\$_\fancyscript{B}$. The belief set $\mathsf {Theory}(\fancyscript{B})$ is the one to be revised with the ${\mathsf {AGM}}$ operators of expansion, contraction and revision, which we will discuss below. We represent a Grove system of spheres centered around a set $\fancyscript{B}$ in the following way, shading the innermost sphere as characterizing the belief set $\fancyscript{B}$:

The sphere formulation is in no way necessary, as Grove notes: “a system of spheres is really an ordering on the set of worlds” [29, p. 160]. To see this, we can reformulate Grove spheres in terms of a relation $\le$ on $W$, which we call a Grove relation. A Grove relation centered around a set $\fancyscript{B}\subseteq W$ is a relation $\le _\fancyscript{B}$ on $W$ that satisfies the following conditions⁵:

• 1. $\le _\fancyscript{B}$ is connected and transitive,

• 2. $x\in W$ is $\le _\fancyscript{B}$-maximal iff $x\in \fancyscript{B}$.

• 3. The limit assumption for $\le _\fancyscript{B}$: For any sentence $\varphi$, if there are any worlds at which $\varphi$ is true, there are $\le _\fancyscript{B}$-maximal worlds w at which $\varphi$ is true, so $\{x\in \,[\![\varphi ]\!]\,|y\le _\fancyscript{B}x \, \text { for all } y \in \,[\![\varphi ]\!]\,\}$ is non-empty.

In a Grove relation, the set $\{\textit{w}\in W|\textit{v}\le _\fancyscript{B}\textit{w}$ for all $\textit{v}\in W\}$ is the belief set, identified by the maximal elements in $\le _\fancyscript{B}$. We again refer to that set with $\fancyscript{B}$. We represent Grove relations in the following way:

We have not drawn all arrows here, assuming that it is easy to see how the relations are transitively closed (Later we shall be even more economical in our use of arrows).

Formally, the difference between Grove spheres and relations is almost only one of taste, just requiring a Gestalt switch of the following kind:

We can be more specific about the connection between Grove spheres and orderings: A Grove ordering $\le _\fancyscript{B}$ is obtained from a system of spheres $\$_\fancyscript{B}$ by defining $\textit{v} \le _\fancyscript{B}\textit{w}$ (read: “v is at most as plausible as w”) iff for all $S\in \$_\fancyscript{B}$ such that $\textit{v} \in S$ it also holds that $w \in S$; the field $W_\fancyscript{B}$ of $\le _\fancyscript{B}$ is $\bigcup \$_\fancyscript{B}$. Conversely, a system of Grove spheres $\$_\fancyscript{B}$ is obtained from a Grove ordering $\le _\fancyscript{B}$ of $W$ by collecting all sets $S$ of the form $S_{\textit{w}} = \{\textit{v}\in W\!: \textit{w}\le _\fancyscript{B}\textit{v}\}$.

This modelling importantly allows for ties between the plausibilities of possible worlds, and this can of course be expressed in both ways of modelling. In the systems of spheres modelling, this means that for two neighbouring spheres $S$ and $S'$ in $\$_\fancyscript{B}$ with $S \subseteq S'$, the set $S'-S$ has in general more than just one element. Expressed in orderings, this means that for many worlds $w$ there may be any number of distinct worlds $v$ such that both $\textit{v} \le _\fancyscript{B}\textit{w}$ and $\textit{w} \le _\fancyscript{B}\textit{v}$. The correspondence between systems of spheres and weak orderings is not perfect, however. The (strong) universality of a system of spheres $\$_\fancyscript{B}$ cannot be expressed by a weak ordering alone. This is why we need to specify the field $W_\fancyscript{B}$ of $\le _\fancyscript{B}$. We also take into account inconsistent belief states, represented by sphere systems $\$_\fancyscript{B}$ that contain the empty sphere $\emptyset$ as an element. But if a sphere in $\$_\fancyscript{B}$ is empty, it generates the same weak ordering $\le _\fancyscript{B}$, in the sense just explained, as the sphere system $\$_\fancyscript{B}\!-\!\{\emptyset \}$. We take the case of empty innermost spheres seriously, because we want to address belief expansion in Sect. 8.5.2. This requires representing trivialisation under expansion with information inconsistent with current beliefs. As the equivalent of empty spheres is not available in ordering semantics, we employ domain restriction in order to achieve similar results.

We need to comment on the interpretation of Grove spheres, or Grove orderings, understood as semantics for the classical ${\mathsf {AGM}}$ style belief revision. Semantically, a whole Grovean system of spheres (or a Grove ordering, or any other model for ${\mathsf {AGM}}$-style one-shot belief revision) represents or, loosely speaking, is a single agent’s belief state. In some way (though it is hard to say in what way exactly), it encodes a first-person point of view: the set of worlds considered (doxastically) possible by the agent, and their comparative plausibilities as judged by the agent. Like the ${\mathsf {AGM}}$ approach, this modelling does not make room for belief at a certain possible world, it only encodes the beliefs and conditional beliefs as they are present for a single agent at the actual world (“here and now”).

Another philosophical point: one should not identify knowledge with the “outer belief modality” in Grove spheres, i.e., with “irrevocable belief” in the sense of Segerberg [46]. Knowledge is not the same as irrevocable belief. While knowledge implies truth, irrevocable belief need not do so. Baltag and Smets’s [5, p. 16] claim that the idea of identifying knowledge and irrevocable belief “can be traced back to Stalnaker [47]” is not quite correct; Stalnaker just defines $\Box \varphi$ as $~\lnot \varphi > \varphi$, without any epistemic interpretation.⁶ Segerberg [46] uses this reading only “unofficially” and alternatively speaks of doxastic commitment. Leitgeb and Segerberg [34, p. 176] allow themselves some philosophical looseness, too, and use the slogan K stands for “knowledge”, not for ‘knowledge’. Our feeling is that this identification is made only for the sake of convenience, because it is then easy to define knowledge in terms of (conditional) belief—something that epistemologists were never able to achieve—, and it is easy to argue for positive and negative introspection concerning knowledge—something that epistemologists have never wanted to achieve. If agents were infallible, then irrevocable belief would come close to knowledge, because then irrevocable belief would be guaranteed to be true. But human agents are not infallible, even their most deeply rooted beliefs may turn out to be false. We will return to this topic in Sect. 8.3.

Finally, even though Grove spheres are inspired by Lewis systems of spheres [18], Lewis explicitly rejects the limit assumption. Lewis’ argument is about similarity relations on worlds underlying counterfactual reasoning, but similar worries hold for plausibility orders: there are no most similar worlds in which Franck Ribéry is taller than 180 cm. Lewis’ semantics for counterfactuals does not depend on the limit assumption. Likewise, we can define belief and conditional belief using sequences of increasingly plausible worlds that do not require the limit assumption. Furthermore, there are ${\mathsf {AGM}}$-inspired doxastic transformations of expansion, revision and contraction that do not require the limit assumption. Hence, following our minimalist attitude, we refrain to assume the limit assumption until necessary.⁷

3 Epistemic Doxastic Logic

In contrast to the use of Grove models within the ${\mathsf {AGM}}$ paradigm, we will model knowledge and belief with Kripke structures. Thus what we call ‘epistemic doxastic logic’ in this chapter ($\mathsf {EDL}$ for short) stands in the tradition of epistemic logic going back at least as far as the seminal work of Hintikka [31]. More recently, epistemic logic has been dynamified in the Dutch tradition and is now referred to as ‘dynamic epistemic logic’ (${\mathsf {DEL}}$ for short). The acronym ${\mathsf {DEL}}$ is sometimes used more generally to also include doxastic transformations (see for instance van Benthem [21]). We use ${\mathsf {DEL}}$ in this general sense, and we reserve the acronym $\mathsf {EDL}$ for our own version of ${\mathsf {DEL}}$ in this chapter. For us, $\mathsf {EDL}$ is the static core of our analysis of knowledge and belief. We will introduce dynamics in the next section and adapt our terminology accordingly.

In $\mathsf {EDL}$, all theorizing begins with knowledge-at-a-possible-world-w or belief-at-a-possible-world-w. So belief and knowledge are “local” in this way. A whole $\mathsf {EDL}$ model does not represent some agent’s or several agents’ doxastic and epistemic states. The worlds in an $\mathsf {EDL}$ model are ways our actual world might be, metaphysically, not epistemically speaking.

One should not get confused by some “global” structures within $\mathsf {EDL}$ models. It might look strange that within a cell of the epistemic partition of the worlds, there is only one doxastic plausibility relation. In the local interpretation, which we believe is the correct one, it would be more precise to say that within such a cell, every world has the same plausibility relation assigned to it, and that this relation is assigned to the cell rather than to every world within the cell only for notational convenience. If possible worlds are considered as indices of evaluation, we might say that in our modelling, the doxastic relation is really just as indexical as the epistemic relation.⁸

That the plausibility relation is the same at each world within a cell, however has a very good justification. A plausibility relation is a formal encoding of the agent’s doxastic state. The fundamental assumption is that agents fully know their own doxastic attitudes.⁹ There has to be an equally fundamental $\mathsf {EDL}$ axiom that captures this assumption. If we had just beliefs, the axiom should be something like $B\varphi \rightarrow KB\varphi$. But since we work with plausibility relations that allow us to express something like degrees of beliefs (entrenchments), we capture that agents are fully aware of their degrees of belief.¹⁰

Such a fundamental axiom is an expression of full (epistemic) introspection of doxastic attitudes. By viewing a global relation within a cell of the knowledge partition just as an abbreviated way of specifying that this very relation is assigned to each world within the cell, we can justify the use of global relations (restricted to cells) by the above introspection principles, while still staying firmly on the ground of the local tradition of ${\mathsf {DEL}}$.

It does not make sense to look at an $\mathsf {EDL}$ model and ask what an agent believes or knows in that model. One can only ask what an agent believes or knows at a certain world in that model. The situation changes in pointed models that come with a distinguished world. This is why Baltag, van Ditmarsch and Moss [6], for instance, define an ‘epistemic state’ (p. 387) or a ‘doxastic state’ (p. 397) as tuples $(M,s)$, where $M$ is a (relational/plausibility) model and $s$ is a state or world.¹¹ Unfortunately, the authors do not comment at all on why they add a distinguished world. Summing up, a pointed model represents the actual world, with all the actual beliefs being in turn represented in terms of possible (conceivable) worlds. It thus makes sense to ask what an agent believes or knows in a pointed model.

If our interpretation is right, it hardly makes sense to drop worlds from the model as a result of some doxastic action. Worlds in $\mathsf {EDL}$ models are metaphysically possible worlds, not doxastically or epistemically possible worlds, as in Grove models. But as ${\mathsf {DEL}}$ theorists point out, a doxastic or epistemic action normally changes what is true in a world like any other action. Unlike the case of non-doxastic or non-epistemic actions, the effects of doxastic and epistemic actions can be represented in the model. The corresponding model transformation consists in manipulating the relevant relations between possible worlds, that is, in actions like cutting links, refining partitions, or shifting plausibilities.¹² This tension between world-elimination and link-cutting is a salient one for us. We will come back to it in Sect. 8.4.1.

The established tradition in modal logic as applied in computer science and game theory is to model knowledge by an equivalence relation that represents indistinguishability for the agent. The idea is that an agent knows that $\varphi$ if and only if $\varphi$ is true in all possible worlds that the agent cannot distinguish from the real world. We should like to emphasize that this is decidedly not the ordinary notion of knowledge. For knowledge in anything close to the ordinary, general sense, and the sense studied by epistemologists, negative introspection is a paradigmatic non-theorem rather than a theorem for epistemic logic.¹³ More often than we like, we fail to know because we are wrong. In many such cases, we believe that we know $p$, but this belief is wrong. Thus, we don’t know (because $p$ is false), but don’t know that we don’t know (an exemplification of an important kind of unknown unknowns). It is abundantly clear that the Brouwerian principle $\lnot \varphi \rightarrow K\lnot K \varphi$ and the interaction principle $BK\varphi \rightarrow K\varphi$ are invalid for the ordinary, general notion of knowledge,¹⁴ but they come out as valid according to the standard ${\mathsf {DEL}}$ semantics. The notion of knowledge that is modelled by S5 structures is the knowledge of agents that are infallible. But humans are not. We can justify taking such structures only by restricting ourselves to specific domains or contexts in which agents do not make any mistakes, i.e., in which their doxastic possibilities do not rule out the actual world. Such contexts are provided by certain fields of research in computer science and game theory. We pretend that we are working in some such context and just ignore this problem as a matter of idealisation.

We thus conceive of the combination of the epistemic and doxastic relations in the following way. The epistemic relation creates a partition of the domain $W$, and each equivalence class of the partition contains a Grove relation (or a system of spheres). That we only have a single Grove relation (or a single system of spheres) for each epistemic indistinguishability class reflects the idea that an agent has the same doxastic state in each possible world within a cell of the knowledge partition. So we assume that agents are fully knowledgeable about (have full introspection concerning) their own doxastic states. If they were not, we would need to assign Grove spheres to each world individually. We represent the doxastic epistemic structure of a single agent as follows:

The domain is partitioned in two equivalence classes, and each “cell” contains a Grove relation, with maximal elements shaded in gray. The maximal elements of each cell are the states at which beliefs at a world in that very cell are to be evaluated. All worlds within a cell refer to the same belief set. So we picture Grovean sphere systems only within the cells of the knowledge partition (and each such cell contains exactly one such system). We impose this as a (the one standard) constraint on the interaction between the doxastic and epistemic relation, namely that the former is a subrelation of the latter: $\le \, \subseteq \, \sim$.

The fact that we have Grove relations $\le$ within each knowledge cell means that the domain of such Grove relations is not the whole of $W$ (i.e., that the relevant Grove systems are not universal). The structural properties of Grove relations are all restricted to each individual indistinguishability cell. There are no plausibility comparison across cells. Hence, if we want to stick to the single relation modelling, we have to use more complicated structures than Grove orderings.

A generalized Grove relation is a reflexive and transitive relation $\le$ over $W$ such that the relation $\sim$, defined by

$$ u\sim \textit{v}\quad \text {if and only if}\quad \text {either } u\le \textit{v} \text { or } \textit{v}\le u $$

is an equivalence relation.¹⁵ Notice that we do not assume the limit assumption for the generalized Grove relation. This definition derives the epistemic relation from the doxastic relation: Indistinguishability means comparability in terms of plausibility. The definition guarantees that $\sim$ contains $\le$. It is not required that generalized Grove relations are connected over the whole of $W$. They may have, and typically do have many belief sets (sets of doxastically possible worlds) on which systems of spheres are centered—one such structure in each cell of the partition. So $\le$ never makes any plausibility comparisons across cells. But it is easily verified that each cell with respect to $\sim$ is a Grove relation—without the limit assumption.

3.1 $\mathsf {EDL}$ Language and Semantics

We define epistemic doxastic models (for single agents), or $\mathsf {EDL}$ models for short, as structures $M = \langle W, \sim ,\le ,<,V \rangle$, with $W$ a non-empty set of worlds, an $V$ a valuation function assigning sets of possible worlds to propositional variables. We take $\le$ to be a generalised Grove relation. We define $\sim$ as above, and take $<$ as the strict subrelation of $\le$ in the usual way: $\textit{w}<\textit{v}$ iff $\textit{w}\le \textit{v}$ and $\textit{v}\not \le \textit{w}$.¹⁶ We read $\textit{w}\le \textit{v}$ as ‘v is at least as plausible as w’, and $\textit{w} <\textit{v}$ as ‘v is (strictly) more plausible than w’. To talk about $\mathsf {EDL}$ models, we use a basic $\mathsf {EDL}$ modal language with three modalities corresponding to the three accessibility relations:

$$ \begin{array}{lll} \varphi&{:}{:}=&p \,\,|\,\,\lnot \varphi \,\,|\,\,(\varphi \wedge \psi ) \,\,|\,\,[\sim ]\varphi \,\,|\,\,[\le ]\varphi \,\,|\,\,[<] \varphi \end{array} $$

As usual, we define dual diamond operators as, for example, $\langle \sim \rangle \varphi \, := \, \lnot [\sim ]\lnot \varphi$.

For the interpretation of the $\mathsf {EDL}$ language, we extend the valuation $V$ to a valuation $[\![\;\cdot \;]\!]^{M}$ assigning semantic values, or sets of possible worlds, to the sentences of the $\mathsf {EDL}$ langauge. Hence, in each epistemic doxastic model $M = \langle W,\,\sim ,\,\le ,\,<,\,V \rangle$, semantic values $[\![\varphi ]\!]^{M} \subseteq W$ are given by:

$$\begin{aligned}{}[\![p]\!]^{M}&= V(p) \\ [\![\lnot \varphi ]\!]^{M}&= W\setminus [\![\varphi ]\!]^{M}\\ [\![(\varphi \wedge \psi )]\!]^{M}&= [\![\varphi ]\!]^{M}\cap [\![\psi ]\!]^{M}\\ [\![[\sim ]\varphi ]\!]^{M}&= \{\textit{w}\in W|\text { if}\ \textit{w}\sim \textit{v}, \mathrm {\ then\ }\textit{v}\in [\![\varphi ]\!]^{M},\ \mathrm {for\,every}\ \textit{v}\in W\}\\ [\![[\le ]\varphi ]\!]^{M}&= \{\textit{w}\in W|\text { if }\ \textit{w}\le \textit{v}, \mathrm {\ then\ }\textit{v}\in [\![\varphi ]\!]^{M},\ \mathrm {for\,every}\ \textit{v}\in W\}\\ [\![[<]\varphi ]\!]^{M}&= \{\textit{w}\in W|\text { if}\ \textit{w}<\textit{v}, \mathrm {\ then\ }\textit{v}\in [\![\varphi ]\!]^{M},\ \mathrm {for\,every}\ \textit{v}\in W\}\\ \end{aligned}$$

For convenience, we sometimes use the more common notation $M, \textit{w}\models \varphi$ instead of $\textit{w} \in [\![\varphi ]\!]^{M}$.

3.2 Knowledge and Belief in $\mathsf {EDL}$

For reasons of simplicity and continuity with much of the literature, we assume that agents know that $\varphi$ in a world $w$ just in case $\varphi$ is true in all worlds v that they cannot distinguish from w:

$$\begin{aligned} M, \textit{w}\models K\varphi \quad \text {iff}\quad \text { for all } \textit{v} \text { such that } \textit{v}\sim \textit{w}, M,\textit{v}\models \varphi . \end{aligned}$$

In other words,

$$\begin{aligned} K\varphi \, := \, [\sim ]\varphi \end{aligned}$$

(8.1)

We thus have a semantics for $K\varphi$ that is widely accepted in computer science and game theory. As we explained above, we have philosophical scruples about it, but we wish to keep the focus of this chapter on belief.

So much for the epistemic part. For doxastic operators, we need to do more work. Our strategy is to derive the analysis of (various kinds of) belief by using the more primitive modalities $[\le ]$ and $[<]$. Following a strategy that can be traced back to at least Boutilier [15, p. 44], we have an intended semantics for belief that is in line with the ${\mathsf {AGM}}$ tradition:

$M, \textit{w}\models B\varphi$    iff    there is a $u$ such that $u\sim w$ and for all v with $u \le \textit{v}$, $M,\textit{v}\models \varphi$.

Notice the epistemic constraint $v\sim w$ in the semantic definition of $B\varphi$, in order to guarantee that beliefs are independently evaluated in each class of the epistemic partition. Given our assumption of connectedness inside each epistemic class, this semantics says that at some point along the plausibility order, $\varphi$ is true for every world at least as plausible. We can explicitly define this notion of belief in the $\mathsf {EDL}$ language:

$$\begin{aligned} B\varphi := \langle \sim \rangle [\le ]\varphi \end{aligned}$$

(8.2)

The right-hand-side of Eq. (8.2) says that some worlds among the epistemically indistinguishable worlds have $[\le ]\varphi$, which is precisely the semantics of $B\varphi$. Assuming the limit assumption would guarantee that $\varphi$ is true in all maximal worlds in the model, which is the more common definition of belief in the ${\mathsf {AGM}}$ tradition.

We can also express that a belief in $\varphi$ is stronger or more entrenched than a belief in $\psi$, which we denote by $B(\psi \prec \varphi )$.

$$\begin{aligned} B(\psi \prec \varphi ) \, := \, \langle \sim \rangle (\lnot \psi \wedge [\le ]\varphi ) \end{aligned}$$

(8.3)

If we set $\psi = \bot$ in definition (8.3), we recover definition (8.2). Another doxastic notion that we can define is conditional belief of $\varphi$ given $\psi$ (cf., for instance, [4, 5, 12, 14]):

$$\begin{aligned} B(\varphi \,|\,\psi ) \, := \, \langle \sim \rangle \psi \rightarrow \langle \sim \rangle {(\psi \wedge [\le ]{(\psi \rightarrow \varphi )})} \end{aligned}$$

(8.4)

If we set $\psi = \top$ in definition (8.4), we again recover exactly definition (8.2). Notice that we didn’t need to use the strict modality $[<]\varphi$ to define belief so far. But if we were to work over partial orders, we could use it to define belief, comparative entrenchment of belief and conditional belief in the following way:

$$\begin{aligned} B \varphi \, := \, [\sim ](\lnot \varphi \rightarrow \langle <\rangle (\varphi \wedge [<] \varphi )) \end{aligned}$$

(8.5)

$$\begin{aligned} B(\psi \prec \varphi ) \, := \, [\sim ](\lnot \varphi \rightarrow \langle <\rangle ((\varphi \wedge \lnot \psi )\wedge [<] \varphi )) \end{aligned}$$

(8.6)

$$\begin{aligned} B(\varphi \,|\,\psi ) \, := \, [\sim ]((\psi \wedge \lnot \varphi )\rightarrow \langle <\rangle ((\psi \wedge \varphi )\wedge [<] (\psi \rightarrow \varphi ))) \end{aligned}$$

(8.7)

Again, if we set $\psi = \bot$ in definition (8.6) or $\psi = \top$ in definition (8.7), we recover definition (8.5), as expected.

Finally, if we set $\psi = \lnot \varphi$ in definition (8.4) or (8.7), we get the notion of irrevocable belief (Segerberg [46]), i.e., belief that is sustained even in the face of contradicting evidence. Since $\langle <\rangle (\varphi \wedge \lnot \varphi )$ cannot be true anywhere, $B(\varphi \,|\,\lnot \varphi )$ reduces to $[\sim ]\varphi$. But this means that irrevocable belief reduces to knowledge-as-indistinguishability. In contrast to Baltag and Smets [4, 5, pp. 14–15, 28], we have argued against such an identification on Sect. 8.2, because even the strongest beliefs may be wrong. But with the means used in this chapter we cannot express the difference.¹⁷

We can now address the idea that agents have full introspection of their doxastic states. This is in fact built firmly into our notions of belief. Notice that the definitions (8.2)–(8.7) of belief have either $\langle \sim \rangle$ or $[\sim ]$ as their main operator.¹⁸ Given our semantics for the indistinguishability relations, it is clear that we get the characteristic S5 axioms of positive and negative introspection with respect to $[\sim ]$. But given definition (8.1), this means that if the agent has certain beliefs at a world w that can be expressed by $B\varphi$, $B(\psi \prec \varphi )$ or $B(\varphi |\psi )$, then, by the very definition of these expressions, KB $\varphi$, KB $(\psi \prec \varphi )$ or $\textit{KB}(\varphi |\psi )$, respectively, are also true at w.¹⁹

One advantage of our modular and minimalist approach is that we can express precisely what we mean when we talk of knowledge and (comparative firmness of) belief. We are very economical with the assumptions we impose on our models, and we relegate them to explicit definitions in our language. We refrain as much as we can to use background assumptions.

3.3 Axiomatisation of $\mathsf {EDL}$

The axiomatisation of static $\mathsf {EDL}$ is based on standard propositional logic. Figure 8.1 shows the axioms for the static part of our modal logic in building blocks. We have the standard set of S5 axioms for the knowledge-as-indistinguishability modality $[\sim ]$. For the non-strict plausibility relation $[\le ]$ which takes $\le$ as an accessibility relation, we have the S4.3 axioms that correspond to connected relations. For strict plausibility $[<]$, we have K4 plus (Mod$<$). This latter axiom is interesting. As far as we know, it has not been used in epistemic or doxastic logics so far, but van Benthem [7, p. 200] has stated and analyzed it early on in the context of temporal logic. Being a Sahlqvist formula (cf. Blackburn, de Rijke and Venema [13]), (Mod$<$) enforces the modularity (or ‘almost-connectedness’ or ‘virtual connectivity’²⁰) to the right of the strict plausibility relation $<$: If $u<v$, $u<w$, $u<z$ and $v<w$, then either $v<z$ or $z<w$. Finally, we need interaction principles between $[\sim ]$, $[\le ]$ and $[<]$. These principles are there to counteract the modal undefinability of $<$ in terms of $\le$, as has been noted in van Benthem, Girard and Roy [10]. They guarantee that the relation $<$ is adequate under bulldozing (cf. Segerberg [45]) of the canonical model, so that $w<v$ iff $w\le v$ and $v\not \le w$. In a similar fashion, it is well-known that we cannot modally express that $\sim$ is the same as $\le \cup \le ^{-1}$, but the canonical model can be adapted accordingly. Since the interaction principles are fairly strong, we are not claiming that our axiomatisation is free of redundancies. We prefer to have fully independent axiomatizations for each of our modal operators instead.

Fig. 8.1

Axiomatisation of static $\mathsf {EDL}$. For the reader’s convenience, we have added a few variants using the possibility operator $\Diamond$, since these are sometimes more intuitive

We have not assumed the limit assumption up until now, and we are still inclined against endorsing it. However, should one insist to include it, we suggest to add the so-called Löb axiom (Löb$<$), which corresponds to transitivity and converse well-foundedness (and thus irreflexivity), as an optional extra. It is known to exclude infinite chains and so is the natural counterpart to the limit assumption in ordering semantics.²¹ While the limit assumption is not important in the static contexts of (conditional and unconditional) belief, it will turn out to be necessary for many important belief change operations on epistemic doxastic models.

4 Epistemic Doxastic $\mathsf {PDL}$ Logic

Epistemic doxastic $\mathsf {PDL}$ logic, $\mathsf {EDPDL}$ for short, is a variant of the now well-established $\mathsf {PDL}$ logic (propositional dynamic logic), whose first interpretation over relational structures can be found in Pratt [41], and further elaborated in Fischer and Ladner [24]. The original purpose of $\mathsf {PDL}$ was to provide a logic of programs in a modal framework, taking programs as modal operators or binary relations between states (transitions between states of a machine). The interpretation of $\mathsf {PDL}$ modalities $\langle \pi \rangle \varphi$ according to [24] is: ‘$\pi$ can terminate with $\varphi$ holding on termination’. However, this interpretation is not what we are after. The part of $\mathsf {PDL}$ that is relevant to us is the modal calculus of relation combination, which we exploit to formalise belief change. Formally, we extend the language of $\mathsf {EDL}$ by adding the $\mathsf {PDL}$ operations of test, choice and composition to the basic ingredients of our language:

$$ \begin{array}{lll} \pi &{}{:}{:}=&{} \sim \,\,|\,\,\le \,\,|\,\,< \,\,|\,\,\varphi ?\,\,|\,\,\pi \, \cup \,\, \pi ' \,\,|\,\,\pi \, ; \, \pi ' \\ \varphi &{} {:}{:}= &{} p \,\,|\,\,\lnot \varphi \,\,|\,\,(\varphi \wedge \psi ) \,\,|\,\,[\pi ]\varphi \end{array} $$

As usual, we define dual box operators $[\pi ]\varphi \, := \, \lnot \langle \pi \rangle \lnot \varphi$ for each program $\pi$. In this notation, the special modalities $[\pi ]\varphi$ with $\pi \in \{\sim , \le , <\}$ are just the basic modalities $[\sim ]\varphi , [\le ]\varphi$ and $[<] \varphi$ of the previous section. In each epistemic doxastic model $M = \langle W, \sim ,\le ,<,V \rangle$, semantic values $[\![\varphi ]\!]^{M} \subseteq W$ and $[\![\pi ]\!]^{M} \subseteq W^2$ are given by:

$$\begin{aligned}{}[\![p]\!]^{M}&= V(p) \\ [\![\lnot \varphi ]\!]^{M}&= W\setminus [\![\varphi ]\!]^{M}\\ [\![(\varphi \wedge \psi )]\!]^{M}&= [\![\varphi ]\!]^{M}\cap [\![\psi ]\!]^{M}\\ [\![\langle \pi \rangle \varphi ]\!]^{M}&= \{u\in W|u[\![\pi ]\!]^{M} \textit{v} \text { and } \textit{v}\in [\![\varphi ]\!]^{M},\ \text {for some }\textit{v}\in W\}\\ [\![\sim ]\!]^{M}&= \,\sim \\ [\![\le ]\!]^{M}&= \,\le \\ [\![<]\!]^{M}&= \,< \\ [\![\varphi ?]\!]^{M}&= \{\langle u,u \rangle |u\in [\![\varphi ]\!]^{M}\}\\ [\![\pi _1;\pi _2]\!]^{M}&= \{\langle u,\textit{v} \rangle |u[\![\pi _1]\!]^{M} \textit{w} \text { and } \textit{w}[\![\pi _2]\!]^{M}v,\ \mathrm {for\, some }\,\textit{w}\in W\}\\ [\![\pi _1\cup \pi _2]\!]^{M}&= [\![\pi _1]\!]^{M}\cup [\![\pi _2]\!]^{M} \end{aligned}$$

As usual, we also write $u[\![\pi ]\!]^{M} \textit{v}$ for $\langle u,\textit{v} \rangle \in [\![\pi ]\!]^{M}$ and $M,u\models \varphi$ for $u\in [\![\varphi ]\!]^{M}$. Incorporating $\mathsf {PDL}$ in our axiomatisation is simple, especially since we are only appealing to the fragment of $\mathsf {PDL}$ without the Kleene star. In line with our modular approach, the $\mathsf {PDL}$ operators or test, choice and composition are recursively introduced (Fig. 8.2).

Fig. 8.2

Axiomatization of general $\mathsf {PDL}$ part

4.1 Doxastic $\mathsf {PDL}$ Transformations

To formalise belief change, we use a special case of $\mathsf {PDL}$-transformations as defined in Girard, Seligman and Liu [27]. This latter chapter was directly motivated by Fact 19 from van Benthem and Liu [11]: every relation-changing operation that is definable in $\mathsf {PDL}$ without iteration has a complete set of reduction axioms in dynamic epistemic logic. We fully exploit this idea in the remainder of the chapter. For the details of the general case of $\mathsf {PDL}$-transformations, the reader should consult Sect. 1 of [27]. We give here a self-contained specification of the special case of $\mathsf {PDL}$-transformations required for our purposes. Basically, a doxastic $\mathsf {PDL}$ -transformation ${\mathrm {\Lambda }}$ is a transformation on models that has two components: (1) a domain restriction provided by some sentence denoted $|{\mathrm {\Lambda }}|$,²² and (2) $\mathsf {PDL}$-definable transformations of the relations $\sim$, $\le$ and $<$. Even though we feel unconfortable about world-elimination, as we already explained, we will use domain restrictions to differentiate between expansion and revision. We are very much aware of philosophical difficulties that may ensue, and will treat them with care.

Given a model $M = \langle W, \sim ,\le ,<,V \rangle$ and a $\mathsf {PDL}$-transformation ${\mathrm {\Lambda }}$, the result of transforming $M$ with ${\mathrm {\Lambda }}$ is the model ${\mathrm {\Lambda }}M = \langle {\mathrm {\Lambda }}W, {\mathrm {\Lambda }}(\sim ), {\mathrm {\Lambda }}(\le ), {\mathrm {\Lambda }}(<), {\mathrm {\Lambda }}V \rangle$. ${\mathrm {\Lambda }}M$ is computed by setting ${\mathrm {\Lambda }}W = [\![|{\mathrm {\Lambda }}|]\!]^{M}$ and taking all relations ${\mathrm {\Lambda }}(\sim )$, ${\mathrm {\Lambda }}(\le )$ and ${\mathrm {\Lambda }}(<)$ that are defined explicitly for each particular program to be restricted to $({\mathrm {\Lambda }}W)^2$. Likewise the valuation ${\mathrm {\Lambda }}V$ is simply the valuation $V$ restricted to the domain ${\mathrm {\Lambda }}W$.

We also define computable translations $\varphi ^{\mathrm {\Lambda }}$ of sentences corresponding to $\mathsf {PDL}$-transformations on models:

$$\begin{aligned} \begin{array}{ll} \begin{array}{ll} p^{{\mathrm {\Lambda }}} &{} = p\\ (\lnot \varphi )^{{\mathrm {\Lambda }}} &{} = \lnot \varphi ^{{\mathrm {\Lambda }}}\\ (\varphi \wedge \psi )^{{\mathrm {\Lambda }}} &{} = (\varphi ^{{\mathrm {\Lambda }}}\wedge \psi ^{{\mathrm {\Lambda }}})\\ (\langle \pi \rangle \varphi )^{{\mathrm {\Lambda }}} &{} = \langle \pi ^{{\mathrm {\Lambda }}}\rangle \varphi ^{{\mathrm {\Lambda }}}\\ \end{array} &{} \begin{array}{ll} \sim ^{{\mathrm {\Lambda }}}&{}=\ {\mathrm {\Lambda }}(\sim ) \, ; \, |{\mathrm {\Lambda }}|?\\ \le ^{{\mathrm {\Lambda }}}&{} =\ {\mathrm {\Lambda }}(\le ) \, ; \, |{\mathrm {\Lambda }}|?\\ <^{{\mathrm {\Lambda }}} &{} =\ {\mathrm {\Lambda }}(<) \, ; \, |{\mathrm {\Lambda }}|?\\ (\varphi ?)^{{\mathrm {\Lambda }}} &{} = (\varphi ^{{\mathrm {\Lambda }}})?\\ (\pi _1 \, ; \, \pi _2)^{{\mathrm {\Lambda }}} &{}= \pi _1^{{\mathrm {\Lambda }}} \, ; \, \pi _2^{{\mathrm {\Lambda }}}\\ (\pi _1\, \cup \,\, \pi _2)^{{\mathrm {\Lambda }}} &{}= \pi _1^{{\mathrm {\Lambda }}}\, \cup \,\, \pi _2^{{\mathrm {\Lambda }}}\\ \end{array} \end{array} \end{aligned}$$

As demonstrated in [27], the translation $\varphi ^{\mathrm {\Lambda }}$ guarantees that the following lemma holds:

Lemma 8.1

For each state $u$ of ${\mathrm {\Lambda }}M$ and v of $M$, and for each sentence $\varphi$,

$$\begin{aligned} M,u\models \varphi ^{{\mathrm {\Lambda }}}&\quad \textit{iff} \quad {\mathrm {\Lambda }}M, u\models \varphi , \textit{ and } \\ u[\![\pi ^{{\mathrm {\Lambda }}}]\!]^{M}\textit{v}&\quad \textit{iff} \quad \textit{v} \in {\mathrm {\Lambda }}W \textit{ and } u[\![\pi ]\!]^{{\mathrm {\Lambda }}M}\textit{v}. \end{aligned}$$

We represent $\mathsf {PDL}$-transformations in the following way:

Name of a $\mathsf {PDL}$-transformation
${\mathrm {\Lambda }}$	$|{\mathrm {\Lambda }}|$
	$\sim := {\mathrm {\Lambda }}(\sim )$
	$\le := {\mathrm {\Lambda }}(\le )$
	$< :={\mathrm {\Lambda }}(<)$

A well-known special case of a $\mathsf {PDL}$-transformation is the public announcement of a sentence $\varphi$, first studied by Plaza in 1989 and now republished in [40]:

Public Announcement
$\varphi !$	$\varphi$
	$\sim :=\sim$
	$\le :=\le$
	$<:=<$

In this representation, ‘$\sim \, := \, \sim$’ means that the relation $\sim$ is assigned to its restriction to the new domain in the new model, i.e., $\varphi !(\sim )=\; \sim \cap \; (\varphi ! W)^2 =\; \sim \cap \; ([\![\varphi ]\!]^{M})^2$. Thus, all a public announcement does is to restrict the domain by eliminating $\lnot \varphi$-worlds. All relations are kept as they were, but restricted to the new domain. To ease notation, we omit writing identity assignment such as ‘$\sim \, := \, \sim$’ in transformations. We also omit writing the domain restriction when $|{\mathrm {\Lambda }}|= \top$. Thus the public announcement transformation can be succinctly written as:

Public Announcement
$\varphi !$	$\varphi$

With this established, we expand our language of doxastic epistemic $\mathsf {PDL}$ logic with modalities $[{\mathrm {\Lambda }}]\varphi$ for each $\mathsf {PDL}$-transformation ${\mathrm {\Lambda }}$ with the following semantics:

$M, \textit{w}\models [{\mathrm {\Lambda }}]\varphi$    iff    ${\mathrm {\Lambda }}M, \textit{w} \models \varphi$.

We stipulate that $M, \textit{w}\models [{\mathrm {\Lambda }}]\varphi$ is vacuously true in case $M, \textit{w}\not \models |{\mathrm {\Lambda }}|$.

A technical difficulty with $\mathsf {PDL}$-transformations is that they may not always transform models into new models of the right kind. A doxastic epistemic model $M$ may be transformed by a $\mathsf {PDL}$-transformation ${\mathrm {\Lambda }}$ in such a way that ${\mathrm {\Lambda }}M$ is not a doxastic epistemic model. To avoid this issue, we do not accept any possible doxastic $\mathsf {PDL}$-transformation, but instead provide a class of doxastic $\mathsf {PDL}$-transformations that are proper, in the sense that they always return doxastic epistemic model.

5 ${\mathsf {AGM}}$ Operations

In this section we provide a class of $\mathsf {PDL}$-transformations which are candidates of unrestricted transformations in the style of Alchourrón, Gärdenfors and Makinson (compare [1, 2, 17, 25, 29, 32]); we refer to them as “${\mathsf {AGM}}$ operations” or “doxastic transformations”. We base our selection on those given in Rott [42].²³ We first study the operations of belief expansion and belief revision, which can be nicely treated in $\mathsf {EDPDL}$ logic. We then move to a study of the operation of belief contraction. Our selection is partly for the sake of exposition, but we include standard ${\mathsf {DEL}}$ doxastic change operations to be found in recent work such as van Benthem [9] or Baltag and Smets [4].

5.1 Expansion and Revision

The operations of expansion and revision are about adding beliefs to belief states. We start with three types of doxastic change, that we categorise as conservative, radical and moderate. A conservative doxastic transformation by $\varphi$ is one that only shifts around maximal $\varphi$-worlds (or, in the case of contraction, $\lnot \varphi$-worlds), and leaves the ordering between the other worlds intact. A moderate doxastic transformation by $\varphi$ is one that shifts around all $\varphi$-worlds (or, in the case of contraction, $\lnot \varphi$-worlds) in a uniform way. A radical doxastic transformation by $\varphi$ is one that only preserves $\varphi$-worlds (or, in the case of contraction, almost only $\lnot \varphi$-worlds).

We use the following abbreviations:

$$ \begin{array}{lll} \sim ^{\varphi }&{}{:}{:}= &{} (\varphi ? \, ; \, \sim \, ; \, \varphi ?)\\ \le ^{\varphi }&{}{:}{:}= &{} (\varphi ? \, ; \, \le \, ; \, \varphi ?)\\ <^{\varphi }&{}{:}{:}= &{} (\varphi ? \, ; \, < \, ; \, \varphi ?)\\ \max \varphi &{}{:}{:}=&{} (\varphi \wedge [<] \lnot \varphi ) \end{array} $$

Notice that the sentence $\max \varphi$ is only true in the most plausible $\varphi$-worlds, i.e., $\varphi$-worlds such that all worlds more plausible, if there are any, satisfy $\lnot \varphi$.²⁴

5.2 Expansion

We start with expansion. Generally speaking, expanding one’s beliefs with $\varphi$ is to start believing $\varphi$ without caring about consistency. If $\varphi$ is not consistent with what the agent believes, then her beliefs trivialise and she now believes $\bot$. But it is important to note that her belief state does not trivialise. In the semantics using Grovean systems of spheres, we can represent this nicely by adding an empty sphere to $\$_\fancyscript{B}$. Unfortunately, no such picture is possible with the pure ordering approach. We have to stipulate here that if $\varphi$ is inconsistent with the beliefs supported by $\le$, which we write as $\lnot [\sim ]\langle \le \rangle \varphi$, then the belief set that results from the expansion is the trivial one, $\mathsf {cl}(\bot )$. We achieve this by introducing the domain restriction $|[\sim ]\langle \le \rangle \varphi |$ in expansion transformations. Notice that this restriction doesn’t really restrict the domain, because of our underlying assumption that the plausibility order is uniform inside epistemic classes. So either all worlds in a class satisfy $[\sim ]\langle \le \rangle \varphi$, or none do. In the latter case, the agent ends-up believing $\bot$.

We first look at conservative expansion. Conservative expansion by $\varphi$ reorders maximal $\varphi$-worlds and leaves the rest of the model intact. That is, the order stays intact among the worlds that are not maximal $\varphi$-worlds (those that either do not satisfy $\varphi$ or for which there are strictly more plausible worlds that satisfy $\varphi$), and it makes every maximal $\varphi$-world equally plausible to each other as well as strictly more plausible than any other world:

Conservative expansion
$\mathsf {CE}\varphi$	$[\sim ]\langle \le \rangle \varphi$
	$\le := \le ^{\lnot \mathsf{{max} (\varphi )}}\, \cup \,\, (\sim \, ; \, \max \varphi ?)$
	$<:= <^{\lnot \mathsf{{max} (\varphi )}}\, \cup \,\, (\lnot \max \varphi ? \, ; \, \sim \, ; \, \max \varphi ?)$

To say that beliefs of agents trivialise under expansion with information $\varphi$ that is inconsistent with their beliefs amounts to saying that $M,w\models [\mathsf {CE}\varphi ] B \bot$ in case $M,w\not \models [\sim ]\langle \le \rangle \varphi$. Notice that conservative expansion is not successful if we do not assume the limit assumption. If there are no maximal $\varphi$-worlds, then nothing happens to the doxastic structure.

Second, consider the operation of moderate expansion, which differs from the conservative operation by reordering all $\varphi$-worlds instead of only the maximal ones. Hence, moderate expansion preserves the order among the $\varphi$-worlds and among the $\lnot \varphi$-world, and makes every $\varphi$-world strictly more plausible than every $\lnot \varphi$-world. In this case, the old maximal $\varphi$-worlds become the most plausible ones overall. Formally, moderate expansion $\mathsf {ME}\varphi$ is defined by:

Moderate expansion
$\mathsf {ME}\varphi$	$[\sim ]\langle \le \rangle \varphi$
	$\le := \le ^{\varphi }\, \cup \,\, \le ^{\lnot \varphi }\, \cup \,\, (\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$
	$<:= <^{\varphi }\, \cup \,\, <^{\lnot \varphi }\, \cup \,\, (\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$

Finally, radical expansion is an action which reduces to a domain restriction. If $\varphi$ is consistent with the agent’s beliefs, then we only keep the $\varphi$-worlds. Thus, if there are maximal worlds that are $\varphi$-worlds, radical expansion deletes all $\lnot \varphi$-worlds; otherwise beliefs trivialise. This is all that is required, so relations are simply restricted as they were to the new domain. Formally, radical expansion $\mathsf {RE}\varphi$ is defined by:

Radical expansion
$\mathsf {RE}\varphi$	$\varphi \wedge [\sim ]\langle \le \rangle \varphi$

Figure 8.3 displays the three kinds of expansion acting on the same model. Every expansion returns the same set of maximal states. The difference is in the ordering of the remaining worlds. We have chosen a model in which some $p$-worlds are among the maximal worlds. Radical expansion restricts the domain to $p$-worlds, exemplifying the way in which it is radical compared to the other ones.

Now that we have precise definitions of expansion as doxastic transformation, we can specify distinguished modalities for each of them: $[\mathsf {CE}\varphi ], [\mathsf {ME}\varphi ]$, and $[\mathsf {RE}\varphi ]$. So for instance, the sentence $[\mathsf {CE}\varphi ]B\psi$ says that $\psi$ is believed after moderately expanding with $\varphi$. As we have no restriction on iterations of doxastic actions, we can also express and analyse complex sentences such as the validities $[\mathsf {CE}p] [\mathsf {RE}p] B\psi \leftrightarrow [\mathsf {RE}p]B\psi$ and $[\mathsf {RE}p] [\mathsf {RE}q] \psi \leftrightarrow [\mathsf {RE}(p\wedge q)]\psi$. In a multi-agent language, we could also analyse higher-order beliefs about doxastic change. For instance, with $s$ = “Robert is a spy” and $l$ = “Robert is a liar”, the sentence $B_r [\mathsf {RE}_b s] B_b l$ expresses that “Robert believes that Bernadette believes that Robert is a liar after radically expanding her belief by the fact that Robert is a spy”.

Fig. 8.3

Three kinds of expansion by $p$. Models are closed under transitivity and reflexivity

5.3 Revision

Revision is exactly like expansion, except that agents do not get trivial beliefs when revising with information that was not consistent with their initial beliefs. Thus the only difference between revision and expansion is in the way the beliefs are retrieved from a plausibility ordering. For revisions, the standard rules apply, and thus an agent simply cannot have an inconsistent belief set! We can accommodate this nicely with conservative and moderate revision, but radical revision is problematic. We can get two interpretations, but neither works properly as a revision. We start with conservative and moderate revision:

Conservative revision
$\mathsf {CR}\varphi$	$\le :=\le ^{\lnot \mathsf{{max} (\varphi )}}\, \cup \,\, (\sim \, ; \, {\max \varphi }?)$
	$<:= <^{\lnot \mathsf{{max} (\varphi )}}\, \cup \,\, (\lnot \max \varphi ? \, ; \, \sim \, ; \, \max \varphi ?)$
Moderate revision
$\mathsf {MR}\varphi$	$\le :=\le ^{\varphi }\, \cup \,\, \le ^{\lnot \varphi }\, \cup \,\, (\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$
	$<:=<^{\varphi }\, \cup \,\, <^{\lnot \varphi }\, \cup \,\, (\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$

Moderate revision precisely corresponds to the lexicographic upgrade, and conservative revision to the elite change of van Benthem [9, p. 141]. We will see in Sect. 8.5.4 that these operations can be regarded as the natural limiting cases of a common idea (viz., that of bounded revision). However, there is an important difference. While moderate revision has no need whatsoever for the limit assumption, conservative revision needs it badly. Like conservative expansion, conservative revision might not be successful without the limit assumption. If it is not met, then there may not be any maximal $\varphi$-worlds and conservative revision may not effect anything.

We can give two interpretations of radical revision as described in Rott [42]. An important aspect of radical revision by $\varphi$ is that $\lnot \varphi$-worlds can never be recovered. One way of incorporating this is by using a domain restriction $|\varphi |$ that removes $\lnot \varphi$-worlds from the model altogether. Another way is to have no domain restriction, like in conservative and moderate revision, but cut every link between $\varphi$ and $\lnot \varphi$-worlds.

The first approach, in which we guarantee irrevocable revision with a domain restriction, is the following doxastic transformation:

Radical revision, version 1
$\mathsf {RR}\varphi$	$\varphi$

This version of radical revision by $\varphi$ is the same as a public announcement of $\varphi$ as we’ve analysed above. In the terminology of van Benthem [9], radical revision is a change under hard information, whereas conservative and moderate revisions are two alternatives of change under soft information.

The way in which this version of radical revision captures the irrevocability of $\varphi$ is by deleting all the $\lnot \varphi$-worlds. This is indeed a radical way of guaranteeing that $\lnot \varphi$-worlds cannot be recovered. This approach also captures success of revision for Boolean sentences, but not without a price. The price to pay is that beliefs of agents trivialise in $\lnot \varphi$-worlds when radically revising by $\varphi$. Indeed, assume that $M, \textit{w}\models \lnot \varphi$ in some model $M$. Because of the domain restriction $|\varphi |$, we get that $M,\textit{w}\models [\mathsf {RR}\varphi ] B\bot$. Success comes at the price of triviality, which is not what revision operators have been invented for.

One way to make sure that belief sets do not trivialise under revision is to avoid restricting the domain, as in conservative and moderate revision, with the following transformation:

Radical revision, version 2
$\mathsf {RR}\varphi$	$\sim :=\sim ^{\varphi }\,\cup \, \sim ^{\lnot \varphi }$
	$\le :=\le ^{\varphi }\,\cup \, \le ^{\lnot \varphi }$
	$<:=<^{\varphi }\,\cup \, <^{\lnot \varphi }$

The way in which this version of radical revision is irrevocable comes from the definition of our epistemic relation. We did not introduce a free transition as a basic program. We have been using the relation $\sim$ instead. For instance, in moderate revision, we can make sure that all $\varphi$-worlds become more plausible than $\lnot \varphi$-worlds by re-defining $<$ as $<^{\varphi }\, \cup \,\, <^{\lnot \varphi }\, \cup \,\, (\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$, where $\sim$ is used to create new plausibility links in $(\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$. Now, in our second interpretation of radical revision, once we cut links between $\varphi$ and $\lnot \varphi$-worlds, these links are no longer recoverable! This is nice, but also comes with its own cost, again when radical revision is evaluated in $\lnot \varphi$-worlds.²⁵

Let us highlight the problem about interpreting (possibly untruthful) public announcement and radical revision with the help of an example. Take a very simple model with two epistemically indistinguishable and equiplausible worlds w and v, with $p$ and $q$ true at w, but false at v (Fig. 8.4). Consider a radical revision by $p$. If radical revision goes by domain restriction, $v$ simply vanishes, and we get that both $[\mathsf {RR}p] Bp$ and $K[\mathsf {RR}p]Bp$ are true at $w$. However, if radical revision goes by a “link-cutting” action then again $[\mathsf {RR}p] Bp$ is true at $w$, but false at v—surprisingly, even $[\mathsf {RR}p] B\lnot p$ is true at v. Hence, since $\textit{v}\sim \textit{w}$, $K[\mathsf {RR}p]Bp$ is false at w. Suppose that in the initial situation the agent is actually located at v, but cannot distinguish v from w. So all the agent knows or believes at the beginning is $p\leftrightarrow q$. Now the agent receives a public (but not truthful!) announcement that $p$ and as a result performs some kind of radical revision on $p$. What would happen? Metaphysically, world $v$ would not cease to exist—this is what makes domain restriction strange.²⁶ The agent would (wrongly) believe that $p$, but of course she would not know that $p$. But she would not know or believe that $\lnot p$ either – this is what makes link-cutting problematic. Intuitively, while the beliefs have changed—and this is why $[\mathsf {RR}p] Bp$ should come out true at $v$—, the knowledge has not increased. The agent located at $v$ is still not able to epistemically distinguish her world from $w$. None of our modellings have this option.

Fig. 8.4

Small example illustrating a problem with radical revision. Models are closed under reflexivity

The versions of revision we have been investigating are illustrated as operating on the same initial model in Fig. 8.5.

Fig. 8.5

Three kinds of revision by $p$. Models are closed under transitivity and reflexivity

5.4 Two-Dimensional Belief Change Operators

We continue our brief overview of revision operations in the framework of $\mathsf {EDL}$ with two-dimensional change operations in the sense of Rott [44]. These models are meant to increase the expressive power of purely qualitative, relational, thus non-numerical models for belief change. The extent to which an input sentence $\varphi$ is accepted, is specified by a reference sentence $\psi$. The first two-dimensional belief change operation we consider is bounded revision. The idea of bounded revision is to accept $\varphi$ as long as $\psi$ holds along with $\varphi$—and just a little longer. Bounded revision satisfies (generalizations of) the semantically motivated postulates of Darwiche and Pearl [17], as well as a “Same beliefs condition” according to which the posterior beliefs of the agent should not depend on the reference sentence (although the posterior belief state does). For further motivation we refer to [44]. Bounded revision $\mathsf {BdR}_{\psi }\varphi$ is defined by:

Bounded revision
$\mathsf {BdR}_{\psi }\varphi$	$\le := \le ^{\varphi \wedge [<](\varphi \rightarrow \psi )}\,\cup \,\le ^{\lnot (\varphi \wedge [<](\varphi \rightarrow \psi ))}\,\cup \,$
	$(\lnot ({\varphi \wedge [<](\varphi \rightarrow \psi )})? \, ; \, \sim \, ; \, (\varphi \wedge [<](\varphi \rightarrow \psi ))?)$
	$<:= <^{\varphi \wedge [<](\varphi \rightarrow \psi )} \,\cup \, <^{\lnot (\varphi \wedge [<](\varphi \rightarrow \psi ))} \,\cup \,$
	$(\lnot ({\varphi \wedge [<](\varphi \rightarrow \psi )})? \, ; \, \sim \, ; \, (\varphi \wedge [<](\varphi \rightarrow \psi ))?)$

It is not difficult to verify that bounded revision reduces to the unary operation of conservative revision if the reference sentence $\psi$ is fixed to $\bot$, and that it reduces to the unary operation of moderate revision if the reference sentence $\psi$ is fixed to $\top$. In general, bounded revision requires the limit assumption, since for instance, if $\varphi$ and $\psi$ are inconsistent with each other, minimal $\varphi$-worlds are needed to ensure the success of the revision operation. By a deliberate choice of the reference sentence $\psi$, however, one may in many cases make sure that there is a broad enough range of worlds that satisfy $\varphi \wedge [<](\varphi \rightarrow \psi )$, and then the operation performs well even if the model does not satisfy the limit assumption. Figure 8.6 gives an illustration of bounded revision in a finite model.

Fig. 8.6

Bounded revision by $p$ with respect to reference sentence $q$. Models are closed under transitivity and reflexivity

Another interesting two-dimensional operation is revision by comparison (Fermé and Rott [23]). It is motivated by the same concerns as bounded revision. But while the idea of bounded revision is to accept $\varphi$ as long as $\psi$ holds along with it (and a little longer), revision by comparison accepts $\varphi$ with a strength that at least equals that of the acceptance of $\psi$. In contrast to bounded revision, revision by comparison does not satisfy the Darwiche-Pearl postulates. In its intended cases of application, it is a revision operation, but it can also have the effects of a contraction operation (see Sect. 8.5.5): If the reference sentence is too weak (more precisely, if the input sentence is at least as surprising as the negation of the reference sentence), then the revision fails, and instead a severe contraction with respect to the reference sentence is performed, provided that there are maximal nonmodels of the reference sentence.²⁷ In at least one way of presenting it (namely by manipulations of prioritized belief bases, cf. Rott [42]), revision by comparison is an extremely natural belief change operation.

The definition of revision by comparison given in Fermé and Rott [23, p. 14] can be represented in our framework as follows:

Revision by comparison
$\mathsf {RbC}_{\psi }\varphi$	$\le := \le ^{\varphi }\, \cup \; (\lnot [\le ]\psi ? \, ; \, \le ) \; \cup \;(\lnot \varphi ? \, ; \, \sim \, ; \, [<] \psi ?)$
	$< := <^{\varphi }\, \cup \; (\lnot [<] \psi ? \, ; \, <) \; \cup \; (\lnot \varphi ? \, ; \, \sim \, ; \, (\varphi \wedge [\le ]\psi )?)$

Figure 8.7 gives an illustration of revision by comparison in a finite model. We are representing two cases, the successful one in which the input sentence gets accepted, and the unsuccessful one in which the reference sentence gets withdrawn.

Fig. 8.7

Revision by comparison by $p$ with respect to stronger and weaker reference sentences $q$: the successful case of a revision and the unsuccessful case reducing to a severe withdrawal of $q$. Models are closed under transitivity and reflexivity

If we set the reference sentence to $\top$, then revision by comparison reduces to a unary revision operation that is more radical than moderate revision but somewhat less radical than the revision operations we have called radical:

Radical revision, version 3
$\mathsf {RR_3}\varphi$	$\le :=\le ^{\varphi }\, \cup \, (\lnot \varphi ? \, ; \, \sim )$
	$< :=<^{\varphi }\, \cup \; (\lnot \varphi ? \, ; \, \sim \, ; \, \varphi ?)$

We deal with another interesting limiting case of revision by comparison obtained by setting the input sentence to $\bot$ in the next section.²⁸

5.5 Contraction

The operation of contraction is about withdrawing beliefs from belief states. The main idea is that a contraction by $\varphi$ is effected by promoting the maximal $\lnot \varphi$-worlds, and possibly some more worlds, to the ranks of the maximal worlds (i.e., the maximal $\top$-worlds).

To be successful, each of the following operations requires the use of $\max {\lnot \varphi }$, and most of them require the use of $\max \top$ as well. Thus the difficulty with belief contraction is that we need to identify maximal states: the states where $[<]\varphi$ or, respectively, $[<]\bot$ hold. But without something like the limit assumption, there is no guarantee that maximal states exist in models. We can still define the operations with $\mathsf {PDL}$-transformations, as we did for all other operations, but unless we have some means of ensuring the existence of maximal worlds, contraction even with atomic information might not be successful. Now, the way we have proposed to get the limit assumption is by introducing the Löb axiom. We know that our logic is sound over the appropriate class of frames in which there are maximal worlds, but we do not know how to prove completeness. Setting this technical question aside for future research, we proceed in this section assuming that models always have maximal worlds, which we identify as those worlds in which $\max {\lnot \varphi }$ or $[<]\bot$ is true.

Our first contraction operation is very simple. It has been studied by various authors and is perhaps best known under the names severe withdrawal (Pagnucco and Rott [39]) and mild contraction (Levi [36]). The incisions into sets of beliefs induced by severe withdrawal are substantially greater than those induced by (iterable generalisations of) ${\mathsf {AGM}}$ contraction functions.

Severe withdrawal
$\mathsf {SW}\varphi$	$\le :=\le \, \cup \,\, (\sim \, ; \, [<] \varphi ?)$
	$<:= (\lnot [<] \varphi ? \, ; \, <)$

Notice that severe withdrawal has no need of identifying maximal $\top$-worlds. But if the limit assumption is not met, then there may be no maximal $\lnot \varphi$-worlds and severe withdrawal may weaken the beliefs of the agent without getting rid of $\varphi$. Figure 8.8 gives an illustration of a successful severe withdrawal:

Fig. 8.8

Severe withdrawal of $p$. Models are closed under transitivity and reflexivity

It is easy to check that a revision by comparison $\mathsf {RbC}_{\psi }\varphi$ reduces to a severe withdrawal of the reference sentence, $\mathsf {SW}\psi$, if we substitute $\bot$ for $\varphi$.²⁹

The following three kinds of contraction are modelled in analogy to conservative, moderate and radical revision. In line with the basic ${\mathsf {AGM}}$ theory, the way the corresponding contraction operations proceed is by putting the maximal $\lnot \varphi$-worlds and the maximal $\top$-worlds on a par, in a maximal position. We now move to the investigation of conservative, moderate and radical contraction (Fig. 8.9).

Fig. 8.9

Four kinds of contractions with respect to $p$. Models are closed under transitivity and reflexivity

Conservative contraction, like conservative revision above, keeps most of the structure intact and reorders maximal worlds. First, the order is preserved among the non-maximal $\lnot \varphi$-worlds. Second, the maximal $\lnot \varphi$-worlds are upgraded on top of non-maximal $\varphi$-worlds and made as plausible as the maximal $\top$-worlds. Formally, conservative contraction is the following doxastic transformation:

Conservative contraction
$\mathsf {CC}\varphi$	$\le := \le ^{\lnot \mathsf{{max} (\lnot \varphi )}}\cup ({\sim \, ; \, \max {\lnot \varphi }?}) \cup ({\sim \, ; \, \max {\top }?})$
	$<:=<^{\lnot \mathsf{{max} (\lnot \varphi )}}\, \cup \,\, ({(\lnot \max {\lnot \varphi }\wedge \lnot \max \top )? \, ; \, \sim \, ; \, \max {\lnot \varphi }?})$

Moderate contraction is defined in analogy to moderate revision, but it is hard to come up with a motivation for it. Why should the idea of being open-minded about $\varphi$ result in a belief state that gives a lot of credit to $\lnot \varphi$? We present it for reasons of uniformity [42].

Moderate contraction
$\mathsf {MC}\varphi$	$\le := \le ^{\lnot \varphi }\, \cup \,\, \le ^{\varphi } \cup ((\varphi \wedge \lnot \max \top )? \, ; \, \sim \, ; \, \lnot \varphi ?)$
	$\cup (\sim \, ; \, \max {\top }?) \cup (\sim \, ; \, \max {\lnot \varphi }?)$
	$<:=<^{\varphi }\, \cup \,\, <^{\lnot \varphi } \cup ((\varphi \wedge \lnot \max \top )? \, ; \, \sim \, ; \, \lnot \varphi ?)$
	$\cup ((\lnot \max {\lnot \varphi }\wedge \lnot \max {\top })? \, ; \, \sim \, ; \, \max \top ?)$

We finally turn to radical contraction to which similar, and even stronger, cautionary remarks concerning its reasonableness apply.

Radical contraction
$\mathsf {RC}\varphi$	$|\lnot \varphi \vee \max \top |$
	$\le :=\le ^{\lnot \varphi } \cup (\sim \, ; \, \max {\lnot \varphi }? \, ; \, ) \cup ({\sim \, ; \, \max \top ?})$
	$<:=<^{\lnot \varphi } \cup ((\lnot \varphi \wedge \lnot \max {\lnot \varphi })? \, ; \, \sim \, ; \, \max \top ?)$

6 Conclusion

We have explored ${\mathsf {AGM}}$ belief change policies in a modal dynamic logic that explicitly delineates knowledge, belief, plausibility and the dynamics of these notions. Taking a Kripke semantics counterpart to Grove semantics for ${\mathsf {AGM}}$ as a starting point, we used a basic modal language containing one epistemic modality $[\sim ]\varphi$ and two plausibility modalities $[\le ]\varphi$ and $[<]\varphi$, and defined several notions of belief. We critically discussed the philosophical presuppositions underlying various modelling assumptions commonly made in the literature, such as negative introspection for knowledge and the limit assumption. Then, we introduced $\mathsf {PDL}$-transformations to define various policies of iterated belief expansion, revision, contraction and two-dimensional belief change operations. $\mathsf {EDPDL}$ thus formalises our minimalist and modular attitude.