# An Investigation of Darwiche and Pearl’s Postulates for Iterated Belief
Update

Quanlong Guan1, Tong Zhu1, Liangda Fang1, Junming Qiu1, Zhao-Rong Lai1, Weiqi
Luo1 Corresponding author

###### Abstract

Belief revision and update, two significant types of belief change, both focus
on how an agent modify her beliefs in presence of new information. The most
striking difference between them is that the former studies the change of
beliefs in a static world while the latter concentrates on a dynamically-
changing world. The famous AGM and KM postulates were proposed to capture
rational belief revision and update, respectively. However, both of them are
too permissive to exclude some unreasonable changes in the iteration. In
response to this weakness, the DP postulates and its extensions for iterated
belief revision were presented. Furthermore, Rodrigues integrated these
postulates in belief update. Unfortunately, his approach does not meet the
basic requirement of iterated belief update. This paper is intended to solve
this problem of Rodrigues’s approach. Firstly, we present a modification of
the original KM postulates based on belief states. Subsequently, we migrate
several well-known postulates for iterated belief revision to iterated belief
update. Moreover, we provide the exact semantic characterizations based on
partial preorders for each of the proposed postulates. Finally, we analyze the
compatibility between the above iterated postulates and the KM postulates for
belief update.

## Introduction

Belief revision focuses on how an agent change her beliefs when she encounters
new information inconsistent with her initial beliefs. The notable AGM
postulates, proposed by Alchourrón, Gärdenfors, and Makinson (1985), have
become a standard framework to capture the rational behavior of belief
revision. Katsuno and Mendelzon (1991b) proposed a characterization of all
revision operators that satisfy AGM postulates in terms of total preorders
over possible worlds.

Belief update, another significant type of belief change, concentrates on how
an agent will modify her beliefs about a dynamically-changing world in view of
new information. As in belief revision, Katsuno and Mendelzon (1991a) proposed
the KM postulates for regulating rational belief update, which models the
process of update as a function of belief sets. Furthermore, they offered a
semantic characterization based on partial preorders over possible worlds, and
clarified the distinctions between update and revision from the model-
theoretic perspective. There is only one total preorder for the belief set
$\psi$ in belief revision. In contrast, in belief update, a collection of
partial preorders is induced by $\psi$ where each preorder is associated to
each possible world satisfying $\psi$.

Although the AGM postulates have been considered as a basic framework for
belief revision, it is shown to be too permissive to exclude some unreasonable
revision operators in the iteration (Darwiche and Pearl 1997). The reason can
be attributed to the fact that it is comprised of merely a set of one-step
postulates, failing to properly deal with the sequential new information in
the process of iterated belief revision. To remedy this defect in belief
revision, Darwiche and Pearl supplemented the AGM paradigm with four
postulates (C1)-(C4) (called DP postulates) and use belief states to denote
the belief of an agent instead of belief sets. Two different belief states may
have the same belief sets, but not vice versa.

Likewise, we argue that the same problem as above exists for the KM postulates
in belief update. In details, the KM framework is unable to regulate the
preferences for subsequent updates during the iterated update process, leading
to some counter-intuitive results. We use the following examples to briefly
illustrate the problem:

######  Example 1.

Consider a table with two zones: left and right. There is a book, a novel and
a toy on any side on the table. We denote by $b$ (resp. $n$ / $t$) the
proposition “the book (resp. novel / toy) is on the left zone of the table”.
Initially, everything is on the right zone, and hence the initial belief set
$\psi$ is $\neg b\land\neg n\land\neg t$. We first instruct a robot to move at
least one of the book and the novel to the left zone, which is described as
the new information $\phi=b\lor n$. Suppose that updated belief set
$\psi\diamond\phi$ is $(b\leftrightarrow\neg n)\land\neg t$, that is, exactly
one of the book and novel is on the left zone, and the toy is on the right
zone. The robot is then given a fresh instruction to place the novel on the
left, which is the new information $\varphi=n$. According to the KM
postulates, it is acceptable that the updated belief set
$(\psi\diamond\phi)\diamond\varphi$ becomes $\neg b\land n$. However, after
updating by $\phi$, we believe that the toy was on the right zone. It seems
unreasonable to require the agent to give up this belief after putting the
novel on the left zone. ∎

The two updated beliefs $\psi\diamond\phi$ and
$(\psi\diamond\phi)\diamond\varphi$ in the above examples are all KM-
compatible. Since the KM postulates do not constrain the update strategy after
iteration, counter-intuitive results will emerge after multiple iterations.

One topic worth investigation is what will happen if we incorporate the
iterated revision postulates above to a belief update scenario. Following the
semantic characterization for every iterated postulate in belief revision,
Rodrigues (2015) integrated these postulates in belief update. However,
Rodrigues’s approach requires that the operator updates the initial belief set
with different preferences over possible worlds no matter how much new
information comes. For example, an agent has the initial belief $\psi$ and the
preference about the worlds $\leq$. She then receives two sequential new
pieces of information $\phi$ and $\varphi$. In the first phase, the new belief
$\psi\diamond\phi$ together with the new preference $\leq^{\prime}$ are
obtained according to the original belief $\psi$, the preference $\leq$ and
the new information $\phi$. However, in Rodrigues’s approach, the new belief
$(\psi\diamond\phi)\diamond\varphi$ is constructed from the initial belief set
$\psi$, the new preference $\leq^{\prime}$ and the sentence $\varphi$.
Clearly, it is more reasonable that the belief
$(\psi\diamond\phi)\diamond\varphi$ should come from the latest belief
$\psi\diamond\phi$ rather than the original one $\psi$. The operator defined
by Rodrigues (2015) obviously does not meet the basic requirement of iterated
belief update.

This paper is intended to fix the deficiency of Rodrigues’s approach. The main
contributions are the following. We first present a modification of the
original KM postulates, allowing belief update to be a function of belief
states. Subsequently, we extend the DP postulates for iterated belief revision
to iterated belief update, yielding postulates
(C1$\triangledown$)-(C4$\triangledown$). In addition, every postulate requires
that the update should result from the latest belief. Furthermore, we provide
the exact semantic characterizations based on partial preorders for every
postulate of iterated belief update. Finally, we analyze the compatibility
between the above iterated postulates and the KM postulates for belief update.
We identify an update operator that satisfies (C3$\triangledown$) and
(C4$\triangledown$). In particular, we show that each of (C1$\triangledown$)
and (C2$\triangledown$) is inconsistent with the KM postulates.

## Formal Preliminaries

Throughout this paper, we fix a finite set $\mathcal{P}$ of propositional
variables. We define $\mathcal{L}$ to be the propositional language built from
$\mathcal{P}$, the connectives $\neg$, $\land$ and $\lor$, and two Boolean
constants $\top$ (truth) and $\bot$ (falsity).

A propositional sentence $\psi$ is complete, iff for every sentence
$\varphi\in\mathcal{L}$, $\psi\models\varphi$ or $\psi\models\neg\varphi$. A
propositional sentence $\psi$ is consistent, iff there is no sentence
$\varphi\in\mathcal{L}$ s.t. $\psi\models\varphi$ and
$\psi\models\neg\varphi$. A possible world $w$ is a complete consistent set of
literals over $\mathcal{P}$, i.e., for every $p\in\mathcal{P}$, either $p\in
w$ or $\neg p\in w$. We use $\mathcal{M}$ to denote the set of all possible
worlds, and $[\phi]$ to denote the set of all possible worlds in which $\phi$
holds. For a finite set of worlds $W$, $\mathtt{Form}({W})$ denotes the
sentence $\bigvee_{w\in W}\left(\bigwedge_{l\in w}l\right)$. For ease of
representation, we sometimes use $w_{1},\cdots,w_{n}$ to denote the set
$\\{w_{1},\cdots,w_{n}\\}$.

A (partial) preorder $\leq$ over $\mathcal{M}$ is a reflexive, transitive
binary relation on $\mathcal{M}$. A preorder is total if for all
$w,w^{\prime}\in\mathcal{M}$, either $w\leq w^{\prime}$ or $w^{\prime}\leq w$.
We define $<$ as the strict part of $\leq$, i.e., $w<w^{\prime}$ iff $w\leq
w^{\prime}$ and $w^{\prime}\not\leq w$. We define $\approx$ as the symmetric
part of $\leq$, i.e., $w\approx w^{\prime}$ iff $w\leq w^{\prime}$ and
$w^{\prime}\leq w$.

## Background

In this section, we briefly review the AGM postulates for belief revision
(Alchourrón, Gärdenfors, and Makinson 1985), the DP postulates for iterated
belief revision (Darwiche and Pearl 1997), and the KM postulates for belief
update (Katsuno and Mendelzon 1991a).

### The Modified AGM Postulates on Belief States

The original AGM paradigm models the notion of belief revision as a function
that maps a belief set $\psi$ and a sentence $\phi$ to a new belief set
$\psi\circ\phi$. In this paper, a belief set is defined as a propositional
sentence. However, the revision function over belief sets only differentiates
what the agent believes and what she does not believe, but does not compare
the plausibility degree of different information which the agent does not
believe. This leads to improper behaviors of revision functions over belief
sets on iterated belief revision (Darwiche and Pearl 1997). To fix this
defect, Darwiche and Pearl proposed the notion of belief states (also referred
to as epistemic states), redefined revision function on belief states, and
reformulated the AGM postulates accordingly. Darwiche and Pearl did not
provide a standard definition of belief states, and only required that each
belief state $S$ is associated with a belief set $\mathtt{B}({S})$.

We use this abstract representation of the belief state herein.

The following are the modified AGM postulates which shift from belief sets to
belief states and are originated from (Darwiche and Pearl 1997).

(R*1)

$\mathtt{B}({S\circ\varphi})$ implies $\varphi$.

(R*2)

If $\mathtt{B}({S})\land\varphi$ is consistent, then
$\mathtt{B}({S\circ\varphi})\equiv\mathtt{B}({S})\land\varphi$.

(R*3)

If $\varphi$ is consistent, so is $\mathtt{B}({S\circ\varphi})$.

(R*4)

If $S_{1}=S_{2}$ and $\varphi\equiv\phi$, then
$\mathtt{B}({S_{1}\circ\varphi})\equiv\mathtt{B}({S_{2}\circ\phi})$.

(R*5)

$\mathtt{B}({S\circ\varphi})\land\phi\models\mathtt{B}({S\circ(\varphi\wedge\phi)})$.

(R*6)

If $\mathtt{B}({S\circ\varphi})\land\phi$ is consistent, then
$\mathtt{B}({S\circ(\varphi\wedge\phi)})\models\mathtt{B}({S\circ\varphi})\land\phi$.

Darwiche and Pearl provided a representation theorem for the modified AGM
postulates based on the notion of faithful total preorders and faith
assignments proposed by Katsuno and Mendelzon (1991b). Given a sentence
$\varphi$, a total preorder $\leq_{\varphi}$ over $\mathcal{M}$ is faithful to
$\varphi$, iff (1) $w\approx_{\varphi}w^{\prime}$ for every two possible
worlds $w,w^{\prime}\in[\varphi]$; and (2) $w<_{\varphi}w^{\prime}$ for every
two possible worlds $w\in[\varphi]$ and $w^{\prime}\in[\neg\varphi]$. A
faithful assignment is a function that maps each belief state $S$ to a total
preorder $\leq_{S}$ that is faithful to $\mathtt{B}({S})$. The following is
the representation theorem for the modified AGM postulates.

######  Theorem 1 ((Darwiche and Pearl 1997)).

A revision operator $\circ$ satisfies postulates (R*1)-(R*6) iff there exists
a faithful assignment that maps each belief state $S$ to a total preorder
$\leq_{S}$ s.t. $[\mathtt{B}({S\circ\varphi})]=\min([\varphi],\leq_{S})$.

### Iterated Belief Revision

In the AGM paradigm, there is no guidance on how to obtain the relationship
between the initial revision strategy and the subsequent one. To solve this
problem, Darwiche and Pearl proposed DP postulates that describe rational
iterated belief revision.

(C1)

If $\varphi\models\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\equiv\mathtt{B}({S\circ\varphi})$.

(C2)

If $\varphi\models\neg\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\equiv\mathtt{B}({S\circ\varphi})$.

(C3)

If $\mathtt{B}({S\circ\varphi})\models\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\models\phi$.

(C4)

If $\mathtt{B}({S\circ\varphi})\not\models\neg\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\not\models\neg\phi$.

Darwiche and Pearl proved that postulates (C1)-(C4) correspond to the
following semantics constraints (CR1)-(CR4) on possible worlds, respectively.

(CR1)

If $w_{1},w_{2}\in[\phi]$, then $w_{1}\leq_{S}w_{2}$ iff
$w_{1}\leq_{S\circ\phi}w_{2}$.

(CR2)

If $w_{1},w_{2}\in[\neg\phi]$, then $w_{1}\leq_{S}w_{2}$ iff
$w_{1}\leq_{S\circ\phi}w_{2}$.

(CR3)

If $w_{1}\in[\phi]$ and $w_{2}\in[\neg\phi]$, then $w_{1}<_{S}w_{2}$ only if
$w_{1}<_{S\circ\phi}w_{2}$.

(CR4)

If $w_{1}\in[\phi]$ and $w_{2}\in[\neg\phi]$, then $w_{1}\leq_{S}w_{2}$ only
if $w_{1}\leq_{S\circ\phi}w_{2}$.

######  Theorem 2 ((Darwiche and Pearl 1997)).

Let $\circ$ be a revision operator satisfying (R*1)-(R*6). Then, $\circ$
satisfies (Ci) iff the operator and its corresponding faithful assignment
satisfies (CRi) for $1\leq i\leq 4$.

### The KM Postulates for Belief Update

In the belief update literature, an agent is intended to modify her beliefs
about a dynamically-changing environment in view of new information. Katsuno
and Mendelzon (1991a) clarified the distinction between belief revision and
update. Furthermore, following the AGM paradigm, they presented the KM
postulates to characterize a family of rational belief update functions, which
map a belief set $\psi$ and a sentence $\varphi$ to a new belief set
$\psi\diamond\varphi$.

(U1)

$\psi\diamond\varphi$ implies $\varphi$.

(U2)

If $\psi$ implies $\varphi$, then $\psi\diamond\varphi\equiv\psi$.

(U3)

If both $\psi$ and $\varphi$ are consistent, so is $\psi\diamond\varphi$.

(U4)

If $\varphi\equiv\phi$, then $\psi\diamond\varphi\equiv\psi\diamond\phi$.

(U5)

$(\psi\diamond\varphi)\land\phi$ implies $\psi\diamond(\varphi\wedge\phi)$.

(U6)

If $\psi\diamond\varphi$ implies $\phi$ and $\psi\diamond\phi$ implies
$\varphi$, then $\psi\diamond\varphi\\!\equiv\\!\psi\diamond\phi$.

(U7)

If $\psi$ is complete, then
$(\\!\psi\diamond\varphi)\\!\land\\!(\psi\diamond\phi)$ implies
$\psi\diamond(\varphi\lor\phi)$.

(U8)

$(\psi_{1}\lor\psi_{2})\diamond\varphi\equiv(\psi_{1}\diamond\varphi)\lor(\psi_{2}\diamond\varphi)$.

To describe the process of belief update, Katsuno and Mendelzon proposed the
notion of faithful preorder associated with possible worlds. Formally, given a
possible world $w$, a preorder $\leq_{w}$ over $\mathcal{M}$ is faithful to
$w$, iff for every possible world $w^{\prime}$, $w^{\prime}\neq w$ only if
$w<_{w}w^{\prime}$. A faithful pointwise assignment is a function that maps
each possible world $w$ to a partial preorder that is faithful to $w$. The
following theorem shows the semantic characterization of KM postulates.

######  Theorem 3 ((Katsuno and Mendelzon 1991a)).

An update operator $\diamond$ satisfies postulates (U1)-(U8) iff there exists
a faithful pointwise assignment that maps each possible world $w$ to a partial
preorder $\leq_{w}$ s.t.
$[\psi\diamond\varphi]=\bigcup\limits_{w\in[\psi]}\min([\varphi],\\!\leq_{w})$.

## The Modified KM Postulates on Belief States

Similarly to belief revision, in order to regulate the update strategy in the
iteration, it is necessary to adopt the notion of belief state rather than
belief set as the belief of an agent.

In the following, we reformulate the KM postulates for belief update in the
context of belief state. We use $S\triangledown\varphi$ to denote the
resultant belief state via updating the previous one $S$ by the sentence
$\varphi$.

(U1$\triangledown$)

$\mathtt{B}({S\triangledown\varphi})$ implies $\varphi$.

(U2$\triangledown$)

If $\mathtt{B}({S})$ implies $\varphi$, then
$\mathtt{B}({S\triangledown\varphi})\equiv\mathtt{B}({S})$.

(U3$\triangledown$)

If both $\mathtt{B}({S})$ and $\varphi$ are consistent, so is
$\mathtt{B}({S\triangledown\varphi})$.

(U4$\triangledown$)

If $\varphi\equiv\phi$, then
$\mathtt{B}({S\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\phi})$.

(U5$\triangledown$)

$\mathtt{B}({S\triangledown\varphi})\land\phi$ implies
$\mathtt{B}({S\triangledown(\varphi\wedge\phi)})$.

(U6$\triangledown$)

If $\mathtt{B}({S\triangledown\varphi})$ implies $\phi$ and
$\mathtt{B}({S\triangledown\phi})$ implies $\varphi$, then
$\mathtt{B}({S\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\phi})$.

(U7$\triangledown$)

If $\mathtt{B}({S})$ is complete, then
$\mathtt{B}({S\triangledown\varphi})\land\mathtt{B}({S\triangledown\phi})$
implies $\mathtt{B}({S\triangledown(\varphi\vee\phi)})$.

(U8$\triangledown$)

$\mathtt{B}({S\triangledown\varphi})\equiv\bigvee\limits_{w_{i}\in[\mathtt{B}({S})]}\mathtt{B}({S_{i}\triangledown\varphi})$
for some set of belief states $\\{S_{1},\cdots,S_{n}\\}$ s.t.
$\mathtt{B}({S_{i}})\equiv\mathtt{Form}({w_{i}})$.

Postulates (U1$\triangledown$)-(U7$\triangledown$) are slightly different from
the original KM postulates (U1)-(U7). Postulates (U8) and (U8$\triangledown$)
aim both to achieve the distributive law of the update operator over
disjunction although they look quite different at first glance. This is
because the disjunction connective cannot directly apply to belief state. We
illustrate the shift from (U8) to (U8$\triangledown$) in the following. Since
$\psi\equiv\bigvee\limits_{w\in[\psi]}\mathtt{Form}({w})$, we can obtain
postulate (U8’) equivalent to (U8) via iteratively applying (U8).

(U8’)

$\psi\diamond\varphi\equiv\bigvee\limits_{w\in[\psi]}\left(\mathtt{Form}({w})\diamond\varphi\right)$.

According to postulate (U8’), the update of any belief set $\psi$ reduces to
the update of $[\psi]$-possible worlds. The notations $\mathtt{B}({S})$ and
$\mathtt{B}({S\triangledown\varphi})$ are the associated belief sets of the
initial belief state $S$ and the updated one $S\triangledown\varphi$,
respectively. Moreover, the update operator $\triangledown$ takes a belief
state and a sentence as input. In order to describe the update of each
possible world $w_{i}$ of $\mathtt{B}({S})$, we choose a belief state $S_{i}$
such that the model of its associated belief set $\mathtt{B}({S_{i}})$ is
exactly $w_{i}$. Hence, postulate (U8$\triangledown$) coincides with (U8) and
(U8’).

We hereafter provide the definition of faithful collective assignments over
belief states. For ease of presentation, we use $\leq^{S}$ for a collection
$\\{\leq^{S}_{w}\\}_{w\in[\mathtt{B}({S})]}$ of partial preorders.

######  Definition 1.

A faithful collective assignment is a function that maps each belief state $S$
to a collection $\leq^{S}$ of partial preorders s.t. for each belief state $S$
and each possible world $w\in[\mathtt{B}({S})]$, we have that

  * •

each preorder $\leq^{S}_{w}$ is faithful to $w$; and

  * •

there is a belief state $S^{\prime}$ s.t.
$\mathtt{B}({S^{\prime}})\equiv\mathtt{Form}({w})$ and
$\leq^{S}_{w}=\leq^{S^{\prime}}_{w}$.

We point out the difference among faithful assignments for (iterated) belief
revision, faithful pointwise assignments for belief update and faithful
collective assignments for iterated belief update. A faithful assignment
assigns each belief state to a single total preorder and a faithful pointwise
assignment maps each possible world to a single partial preorder. In contrast,
a faithful collective assignment associates each belief state with a
collection of partial preorders.

We hereafter show that Theorem 3 can be extended to the modified KM postulates
and faithful collective assignments.

######  Theorem 4.

An update operator $\triangledown$ satisfies postulates
(U1$\triangledown$)-(U8$\triangledown$) iff there exists a faithful collective
assignment that maps each belief state $S$ to a collection $\leq^{S}$ of
partial preorders s.t.
$[\mathtt{B}({S\triangledown\varphi})]=\bigcup\limits_{w\in[{\mathtt{B}({S})}]}\min([\varphi],\leq^{S}_{w})$.

## Iterated Belief Update on Belief States

We are ready to investigate the iteration of belief update with the help of
belief states. In this section, we first modify the iterated revision
postulates so as to suit the update operator, and then examine the rationale
of the proposed iterated update postulates with concrete examples. Moreover,
we provide the model-theoretic characterization of each of the DP postulates
in the context of belief update and prove the representation theorem. Finally,
we make a brief comparison between our approach and Rodrigues’s.

### Iterated Update Postulates and Examples

The iterated postulates can be easily transferred to belief update via
replacing the revision operator $\circ$ by the update one $\triangledown$. To
distinguish the iterated postulates for belief update and revision, we add a
symbol $\triangledown$ behind the name of the original iterated revision
postulate for the corresponding one in iterated belief update. For example,
(C1$\triangledown$) is “if $\varphi\models\phi$, then
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\varphi})$”
while (C1) is “if $\varphi\models\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\equiv\mathtt{B}({S\circ\varphi})$”.

######  Example 2 (Postulate (C1$\triangledown$)).

Let us continue Example 1. Let $\mathcal{P}=\\{b,n,t\\}$ and
$\mathcal{M}=\\{w_{0},\dots,w_{7}\\}$. The definition of each possible world
is shown in Table 1, in which an occurrence of $\top$ (resp. $\bot$) indicates
that the positive (resp. negative) literal of the corresponding proposition is
in the possible world. For example, all of the three cells of the rows “book”,
“novel” and “toy” and the column “$w_{0}$” are $\bot$, meaning that they are
all on the right zone of the table in the possible world $w_{0}$. The other
possible worlds are defined similarly. We provide a KM-compatible update
operator in Example 1 as follows. The initial belief state $S$ is assigned to
the set $\leq^{S}$ of partial preorders with one element $\leq^{S}_{w_{0}}$.

  * •

$w_{0}<^{S}_{w_{0}}w_{2},w_{4}<^{S}_{w_{0}}w_{1},w_{3},w_{5},w_{6},w_{7}$.

Then, the updated belief state $S\triangledown\phi$ are assigned the
collection $\leq^{S\triangledown\phi}$ of two preorders listed below.

  * •

$w_{2}<^{S\triangledown\phi}_{w_{2}}w_{4}<^{S\triangledown\phi}_{w_{2}}w_{0},w_{1},w_{3},w_{5},w_{6},w_{7}$.

  * •

$w_{4}<^{S\triangledown\phi}_{w_{4}}w_{3}<^{S\triangledown\phi}_{w_{4}}w_{0},w_{1},w_{2},w_{5},w_{6},w_{7}$.

The two worlds $w_{2}$ and $w_{3}$ are the minimal element satisfying
$\varphi$ w.r.t. $\leq^{S\triangledown\phi}_{w_{2}}$ and
$\leq^{S\triangledown\phi}_{w_{4}}$, respectively. According to the semantics
of the update operator (cf. Theorem 4), we have that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\equiv\mathtt{Form}({w_{2},w_{3}})\equiv\neg
b\land n$, discarding unjustifiably the belief that the toy is on the right
zone.

In contrast, from (C1$\triangledown$), we deduce that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\varphi})\\!\\!\equiv\\!\\!\neg
b\land n\land\neg t$, preserving the belief about the toy. ∎

possible worlds | $w_{0}$ | $w_{1}$ | $w_{2}$ | $w_{3}$ | $w_{4}$ | $w_{5}$ | $w_{6}$ | $w_{7}$
---|---|---|---|---|---|---|---|---
book | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\top$ | $\top$ | $\top$
novel | $\bot$ | $\bot$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\top$ | $\top$
toy | $\bot$ | $\top$ | $\bot$ | $\top$ | $\bot$ | $\top$ | $\bot$ | $\top$
Table 1: The definition of possible worlds in Example 2.

######  Example 3 (Postulates (C2$\triangledown$)).

We use the previous example to justify postulate (C2$\triangledown$). Let us
consider the following KM-compatible update operator. Initially, the belief
set $\mathtt{B}({S})\equiv\neg b\land\neg n\land\neg
t\equiv\mathtt{Form}({w_{0}})$. The associated partial preorder
$\leq^{S}_{w_{0}}$ of the belief state $S$ is:

  * •

$w_{0}<^{S}_{w_{0}}w_{2},w_{4}<^{S}_{w_{0}}w_{1},w_{3},w_{5},w_{6},w_{7}$.

Now, a robot is instructed to put the book and the novel on the opposite zone
and put the toy on the right zone, described as $\phi=(b\leftrightarrow\neg
n)\land\neg t$. From the semantics of the update operator, the updated belief
set $\mathtt{B}({S\triangledown\phi})$ is $(b\leftrightarrow\neg n)\land\neg
t\equiv\mathtt{Form}({w_{2},w_{4}})$, that is, only one of the book and novel
is on the left zone, and the toy must be on the right zone. Then, the updated
belief state $S\triangledown\phi$ is assigned the collection
$\leq^{S\triangledown\phi}$ of two partial preorders listed below.

  * •

$w_{2}<^{S\triangledown\phi}_{w_{2}}w_{6},w_{7}<^{S\triangledown\phi}_{w_{2}}w_{0},w_{1},w_{3},w_{4},w_{5}$.

  * •

$w_{4}<^{S\triangledown\phi}_{w_{4}}w_{0},w_{1}<^{S\triangledown\phi}_{w_{4}}w_{2},w_{3},w_{5},w_{6},w_{7}$.

Subsequently, the robot is informed to put the novel and the book on the same
zone, which is described as new information $\varphi=b\leftrightarrow n$.
Clearly, the minimal elements satisfying $\varphi$ w.r.t.
$\leq^{S\triangledown\phi}_{w_{2}}$ (resp.
$\leq^{S\triangledown\phi}_{w_{4}}$) are possible worlds $w_{6}$ and $w_{7}$
(resp. $w_{0}$ and $w_{1}$). By the semantics of the update operator, the
updated belief set $\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})$
becomes $b\leftrightarrow n\equiv\mathtt{Form}({w_{0},w_{1},w_{6},w_{7}})$.
However, as the agent has believed, after the update by $\phi$, that the toy
was on the right zone, it seems irrational to require the agent to give up
this belief.

As $\varphi\models\neg\phi$, according to postulate (C2$\triangledown$), we
can deduce that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\varphi})\equiv\neg
b\land\neg n\land\neg t$. In this way, it preserves the belief about the toy.
∎

######  Example 4 (Postulate (C3$\triangledown$)).

Consider the scenario where an alarm is in a warehouse. When the alarm sounds,
it means a fire breaks out. The proposition $a$ and $f$ denotes that “the
alarm sounds” and “the warehouse catches fire”, respectively. Let
$\mathcal{P}=\\{a,f\\}$ and $\mathcal{M}=\\{w_{0},\dots,w_{3}\\}$. Each
possible world is defined in Table 2. Initially, the belief set
$\mathtt{B}({S})$ is $\neg a\land\neg f\equiv\mathtt{Form}({w_{0}})$, meaning
that neither the alarm sounds nor the warehouse catches fire. The belief state
$S$ is associated with the following preorder $\leq^{S}_{w_{0}}$.

  * •

$w_{0}<^{S}_{w_{0}}w_{1}<^{S}_{w_{0}}w_{3}<^{S}_{w_{0}}w_{2}$.

At some point, some workers smoke, causing a fire in the warehouse, which is
described as the new information $\phi=f$. The updated belief set
$\mathtt{B}({S\triangledown\phi})$ is $\neg a\land
f\equiv\mathtt{Form}({w_{1}})$, that is, the alarm does not sound but the fire
is in the warehouse. Then, the updated belief state $S\triangledown\phi$ is
assigned to the set $\leq^{S\triangledown\phi}$ of preorders with one element
$\leq^{S\triangledown\phi}_{w_{1}}$.

  * •

$w_{1}<^{S\triangledown\phi}_{w_{1}}w_{0},w_{2},w_{3}$.

Subsequently, the alarm sounds, which is described as new information
$\varphi=a$. Obviously, the minimal elements satisfying $\varphi$ are possible
worlds $w_{2}$ and $w_{3}$. It follows from the semantics of the update
operator that the updated belief set
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\equiv
a\equiv\mathtt{Form}({w_{2},w_{3}})$. However, after updating by $\phi$, we
believe that there is a fire in the warehouse. It seems unreasonable to give
up this belief now when the alarm is also sounding.

As mentioned before, the alarm sounds only when there is a fire, hence
$\mathtt{B}({S\triangledown a})\models f$ holds. We infer from postulate
(C3$\triangledown$) that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$, allowing
to preserve the belief $\phi=f$ in the belief set
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})$. ∎

possible worlds | $w_{0}$ | $w_{1}$ | $w_{2}$ | $w_{3}$
---|---|---|---|---
alarm | $\bot$ | $\bot$ | $\top$ | $\top$
fire | $\bot$ | $\top$ | $\bot$ | $\top$
Table 2:  The definition of possible worlds in Example 4.

######  Example 5 (Postulate (C4$\triangledown$)).

Consider a scenario similar to Example 2. The initial belief set
$\mathtt{B}({S})$ is $\neg n\land\neg t\equiv\mathtt{Form}({w_{0},w_{4}})$.
The belief state $S$ is associated with the set $\leq^{S}$ of partial
preorders that contains two elements $\leq^{S}_{w_{0}}$ and
$\leq^{S}_{w_{4}}$.

  * •

$w_{0}<^{S}_{w_{0}}w_{4}<^{S}_{w_{0}}w_{1},w_{2},w_{3},w_{5},w_{6},w_{7}$.

  * •

$w_{4}<^{S}_{w_{4}}w_{0}<^{S}_{w_{4}}w_{1},w_{2},w_{3},w_{5},w_{6},w_{7}$.

A robot first moves the book to the left zone and hence the new information
$\phi=b$. Then, it is believed that the book is on the left zone, that is, the
updated belief set $\mathtt{B}({S\triangledown\phi})\equiv b\land\neg
n\land\neg t\equiv\mathtt{Form}({w_{4}})$. The associated partial preorder
$\leq^{S\triangledown\phi}_{w_{4}}$ of the belief state $S\triangledown\phi$
is:

  * •

$w_{4}<^{S\triangledown\phi}_{w_{4}}w_{0},w_{2}<^{S\triangledown\phi}_{w_{4}}w_{1},w_{3},w_{5},w_{6},w_{7}$.

The robot is subsequently instructed to put the novel on the left zone, which
is described as the new information $\varphi=n$. Accordingly, we get that the
updated belief set $\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})$
becomes $\neg b\land n\land\neg t\equiv\mathtt{Form}({w_{2}})$. However,
because $\mathtt{B}({S\triangledown\phi})\equiv b\land\neg n\land\neg t$, we
have no reason to believe that the book is on the right zone.

Since $\mathtt{B}({S\triangledown\phi})\not\models\neg\varphi$, postulate
(C4$\triangledown$) can be used to rule out the above irrational behaviour.
Postulate (C4$\triangledown$) requires
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\not\models\neg\phi$,
forbidding the unreasonable belief $\neg\phi\\!=\\!\neg b$ to be a consequence
of the new belief set. ∎

### Representation Theorem

We hereafter present the model-theoretic characterization of each of the DP
iterated postulates.

(CR1$\triangledown$)

For every $\mathcal{N}\subseteq[\phi]$, the following hold

Forth

for every $w\in[\mathtt{B}({S})]$ and
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$, there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})$.

Back

for every $w^{\prime}\\!\in\\![\mathtt{B}({S\triangledown\phi})]$ and
$w^{\prime\prime}\\!\in\\!\min(\mathcal{N}\\!,\\!\leq^{S\triangledown\phi}_{w^{\prime}})$,
there is $w\in[\mathtt{B}({S})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$.

(CR2$\triangledown$)

For every $\mathcal{N}\subseteq[\neg\phi]$, the following hold

Forth

for every $w\in[\mathtt{B}({S})]$ and
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$, there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})$.

Back

for every $w^{\prime}\\!\in\\![\mathtt{B}({S\triangledown\phi})]$ and
$w^{\prime\prime}\\!\in\\!\min(\mathcal{N}\\!,\\!\leq^{S\triangledown\phi}_{w^{\prime}})$,
there is $w\in[\mathtt{B}({S})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$.

(CR3$\triangledown$)

For every $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\subseteq[\phi]$ holds for every
$w\in[\mathtt{B}({S})]$, we have
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$ for
every $w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$.

(CR4$\triangledown$)

For every $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$ holds for some
$w\in[\mathtt{B}({S})]$, we have there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\cap[\phi]\neq\emptyset$.

The semantics (CR1$\triangledown$) requires that for every subset
$\mathcal{N}$ of possible worlds of $\phi$, the minimal elements of
$\mathcal{N}$ w.r.t. the collection $\leq^{S\triangledown\phi}$ of preorders
associated with the updated belief state $S\triangledown\phi$ should be in
accordance with that of the original one $S$. (CR2$\triangledown$) acts
similarly to (CR1$\triangledown$) except that it focuses on the subset of
possible worlds of $\neg\phi$. The semantics (CR3$\triangledown$) (resp.
(CR4$\triangledown$)) states that for every set $\mathcal{N}$ of possible
worlds, if all of the minimal elements of $\mathcal{N}$ w.r.t. the collection
$\leq^{S}$ of preorders satisfy (resp. falsify) $\phi$, then such property
should be retained after updating by the new information $\phi$.

Although each iterated update postulate is identical to the corresponding
iterated revision one, the semantics for iterated postulates in belief update
is distinct from that in belief revision. In contrast to belief revision,
which is based on a single preorder, an update strategy is defined as a
collection of preorders. We formalize the iterated update strategy in terms of
the minimal elements of preorders. When both of the initial and updated
collection of preorders contains a single preorder, we note that the semantics
for each iterated update postulate matches with that for the corresponding
iterated revision one.

The theorem below provides the correspondence between each of the above
postulates and its corresponding semantics, based on faithful collective
assignments.

######  Theorem 5.

Let $\triangledown$ be an update operator satisfying
(U1$\triangledown$)-(U8$\triangledown$). Then, $\triangledown$ satisfies
(Ci$\triangledown$) iff the operator and its corresponding faithful collective
assignment satisfies (CRi$\triangledown$) for $1\leq i\leq 4$.

### Comparison to Rodrigues’s Approach

Rodrigues (2015) migrated the iterated revision postulates to the update
scenarios. In his approach, the update operators act on belief sets rather
than belief states during the iteration. In addition to the standard update
operator $\diamond$, he defined a different update operator, denoted by
$\diamond_{\phi}$ for each sentence $\phi$. The update operator
$\diamond_{\phi}$ takes a belief set $\psi$ and a sentence $\varphi$ as input
where $\psi$ denotes the initial belief set and $\varphi$ denotes the latest
information and reflects the behavior of iterated update. The notation
$\psi\diamond_{\phi}\varphi$ means that the initial belief set will be updated
by $\phi$ and followed by $\varphi$ while $\psi\diamond\varphi$ denotes the
new belief set via updating $\psi$ by $\varphi$.

The following is the variant of postulate (C1) for iterated belief update and
its semantic characterization.

(C1$\diamond$)

If $\varphi\models\phi$, then
$\psi\diamond_{\phi}\varphi\equiv\psi\diamond\varphi$.

(CR1$\diamond$)

If $w_{1},w_{2}\in[\phi]$, then $w_{1}\leq^{\phi}_{w}w_{2}$ iff
$w_{1}\leq_{w}w_{2}$.

The semantics of the update operator $\diamond_{\phi}$ is the same as the
semantics in Theorem 3 except it uses the updated preorder $\leq^{\phi}_{w}$
instead of the initial one $\leq_{w}$. The update operator $\diamond_{\phi}$
therefore satisfies postulates (U1)-(U8).

######  Theorem 6 ((Rodrigues 2015)).

Let $\diamond_{\phi}$ be an update operator satisfying postulates (U1)-(U8).
Then, the operator $\diamond_{\phi}$ satisfies postulates (C1$\diamond$) iff
each of its corresponding faithful collective assignment $\leq^{\phi}_{w}$
satisfies (CR1$\diamond$).

In the case where $\varphi\models\phi$, postulate (C1$\diamond$) requires that
iteratively updating $\psi$ by the information $\phi$ and its subsequent one
$\varphi$ yields the same belief set as directly updating the $\psi$ by
$\varphi$. As for its corresponding semantics, for every possible world $w$,
the preorder $\leq^{\phi}_{w}$ is required to coincide with $\leq_{w}$ on each
pair of possible worlds in $[\phi]$.

We hereafter illustrate the update process of postulate (C1$\diamond$) with
the following example.

######  Example 6 (Postulate (C1$\diamond$)).

Consider again Example 2. Let us provide an update operator satisfying
postulate (C1$\diamond$). The initial belief set $\psi$ and two new
information $\phi$ and $\varphi$ are the same as those in Example 2. That is,
$\psi\equiv\mathtt{Form}({w_{0}})\equiv\neg b\land\neg n\land\neg t$,
$\phi=b\lor n$ and $\varphi=n$. The partial preorder $\leq_{w_{0}}$ is

  * •

$w_{0}<_{w_{0}}w_{2},w_{4}<_{w_{0}}w_{1},w_{3},w_{5},w_{6},w_{7}$.

By semantics (CR1$\diamond$), the new preorder $\leq^{\phi}_{w_{0}}$ should
coincide with $\leq_{w_{0}}$ on every pair of two possible worlds in
$[\phi]\\!=\\!\\{w_{2},w_{3},w_{4},w_{5},w_{6},w_{7}\\}$. Suppose that
$\leq^{\phi}_{w_{0}}$ is defined as:

  * •

$w_{0}<^{\phi}_{w_{0}}w_{1}<^{\phi}_{w_{0}}w_{2},w_{4}<^{\phi}_{w_{0}}w_{3},w_{5},w_{6},w_{7}$.

As the belief set $\psi$ involves only $w_{0}$, the preorders w.r.t. other
possible worlds do not affect the update result. Hence we do not adjust them.
In addition, $[\varphi]=\\{w_{2},w_{3},w_{6},w_{7}\\}$. It follows from
(C1$\diamond$) that
$\psi\diamond_{\phi}\varphi\equiv\psi\diamond\varphi\equiv\mathtt{Form}({w_{2}})\equiv\neg
b\land n\land\neg t$. ∎

As seen above, after receiving the new information $\phi$, the agent maintains
the initial belief set $\psi$, believing that nothing is on the left zone. The
order over possible worlds shifts from $\leq_{w_{0}}$ to
$\leq^{\phi}_{w_{0}}$. As a result, the final updated belief
$\psi\diamond_{\phi}\varphi$ is actually deduced from the initial belief set
$\psi$, the new order $\leq^{\phi}$ and the newly acquired information
$\varphi$. It does not meet the basic requirement of iterated belief update,
since it has no effect on the evolution of the belief set in light of the
sequential new information. Clearly, it is more rational that the final belief
should come from the latest belief set $\psi\diamond\phi$ rather than $\psi$.
This is achieved through the development of postulate (C1$\triangledown$) in
this paper.

We remark that the problems in (Rodrigues 2015) occurs on not only the
migration of postulate (C1$\diamond$) but also all those of the remaining
iterated postulates. Similarly, these deficiencies can be fixed via using the
corresponding postulate proposed in this section instead.

## (In)compatibility Results of
Iterated Belief Update

In this section, we are going to analyze the compatibility between the
presented postulates for iterated update and the modified KM postulates.

We hereafter provide a concrete update operator satisfying the modified KM
postulates. Given a possible world $w$ and a sentence $\phi$ s.t.
$w\in[\phi]$, we divide the entire set $\mathcal{M}$ of possible worlds into
three hierarchies: $\mathcal{H}^{w,\phi}_{0}=\\{w\\}$,
$\mathcal{H}^{w,\phi}_{1}=[\phi]\setminus\\{w\\}$ and
$\mathcal{H}^{w,\phi}_{2}=[\neg\phi]$.

######  Definition 2.

Let $S$ be a belief state associated with a belief set $\mathtt{B}({S})$ and a
collection $\leq^{S}$ of preorders over possible worlds. Let $\phi$ be a
sentence. The operator $\triangledown_{1}$ is defined as:

  1. 1.

$[\mathtt{B}({S\triangledown_{1}\phi})]=\bigcup\limits_{w\in[{\mathtt{B}({S})}]}\min([\phi],\leq^{S}_{w})$;

  2. 2.

for every $w\in[\mathtt{B}({S\triangledown_{1}\phi})]$ and
$w_{1},w_{2}\in\mathcal{M}$, $w_{1}\leq_{w}^{S\triangledown_{1}\phi}w_{2}$ iff
$w_{1}\in\mathcal{H}^{w,\phi}_{i}$, $w_{2}\in\mathcal{H}^{w,\phi}_{j}$ and
$i\leq j$.

The above two conditions impose the constraints on the updated belief set
$\mathtt{B}({S\triangledown_{1}\phi})$ and the subsequent update strategy
$\leq^{S\triangledown_{1}\phi}$, respectively. Clearly, condition (1) is the
same as the semantics of the update operator. As a result, the operator
$\triangledown_{1}$ satisfies postulates
(U1$\triangledown$)-(U8$\triangledown$) and hence being a KM-compatible update
operator. Condition (2) assigns to every possible world $w$ satisfying
$\mathtt{B}({S\triangledown_{1}\phi})$ a partial preorder
$\leq_{w}^{S\triangledown_{1}\phi}$. To be specific, the preorder
$\leq_{w}^{S\triangledown_{1}\phi}$ exactly characterizes a binary relation
over possible worlds $\mathcal{M}$ divided into three hierarchies:
$\mathcal{H}^{w,\phi}_{0}$, $\mathcal{H}^{w,\phi}_{1}$ and
$\mathcal{H}^{w,\phi}_{2}$. That is, (1) the possible world $w$ is the most
preferable, followed by the ones satisfying the new information $\phi$, and
finally the remaining ones falsifying $\phi$; and (2) every two possible
worlds in $[\phi]\setminus\\{w\\}$ (resp. $[\neg\phi]$) are equally plausible.

Recalling the scenario in Example 5, we illustrate the specific update process
of the operator $\triangledown_{1}$ as follows.

######  Example 7.

The initial belief state $S$ is associated with the belief set
$[\mathtt{B}({S})]=\\{w_{0},w_{4}\\}$ and a collection $\leq^{S}$ of partial
preorders as follows.

  * •

$w_{0}<^{S}_{w_{0}}w_{4}<^{S}_{w_{0}}w_{1},w_{2},w_{3},w_{5},w_{6},w_{7}$.

  * •

$w_{4}<^{S}_{w_{4}}w_{0}<^{S}_{w_{4}}w_{1},w_{2},w_{3},w_{5},w_{6},w_{7}$.

The new information $\phi=b$ corresponds to the set of possible worlds
$\\{w_{4},w_{5},w_{6},w_{7}\\}$. Clearly, the minimal elements satisfying
$\phi$ w.r.t. $\leq^{S}_{w_{0}}$ and $\leq^{S}_{w_{4}}$ are both the posssible
world $w_{4}$. By the semantics of the update operator, we get that
$\mathtt{B}({S\triangledown_{1}\phi})\equiv\mathtt{Form}({w_{4}})\equiv
b\land\neg n\land\neg m$. According to the definition of $\triangledown_{1}$,
the updated belief state $S\triangledown_{1}\phi$ would be assigned to a
collection $\leq^{S\triangledown_{1}\phi}$ of preorders.

  * •

$w_{4}<^{S\triangledown_{1}\phi}_{w_{4}}w_{5},w_{6},w_{7}<^{S\triangledown_{1}\phi}_{w_{4}}w_{0},w_{1},w_{2},w_{3}$

As seen above, the possible worlds of $\mathcal{M}$ are splitted into three
hierarchies: (1) the most preferable ones
$\mathcal{H}^{w_{4},\phi}_{0}=\\{w_{4}\\}$ are exactly the current belief set,
stating that only the book is on the left zone; (2) the second most preferable
ones $\mathcal{H}^{w_{4},\phi}_{1}=\\{w_{5},w_{6},w_{7}\\}$ are the other
three possible worlds satisfying $\phi$, stating that the book and at least
one of the novel and the toy are on the left zone; (3) the least preferable
ones $\mathcal{H}^{w_{4},\phi}_{2}=\\{w_{0},w_{1},w_{2},w_{3}\\}$ are the
possible worlds falsifying $\phi$, stating that the book is not on the left
zone.

Finally, the newly acquired information $\varphi=n$ corresponds to the set of
possible worlds $\\{w_{2},w_{3},w_{6},w_{7}\\}$. The minimal elements
satisfying $\varphi$ w.r.t. $\leq^{S\triangledown_{1}\phi}_{w_{4}}$ are the
two possible worlds $w_{6}$ and $w_{7}$. Hence, the final updated belief set
$\mathtt{B}({(S\triangledown_{1}\phi)\triangledown_{1}\varphi})=\mathtt{Form}({w_{6},w_{7}})$,
which argues that both the book and novel are on the left zone.∎

The following theorem confirms the compatibility results between two iterated
postulates and the KM postulates.

######  Theorem 7.

The update operator $\triangledown_{1}$ satisfies postulates
(C3$\triangledown$) and (C4$\triangledown$).

In the seminal paper (Darwiche and Pearl 1997), it is proved that all of the
DP postulates for iterated revision are compatible with the AGM paradigm (a
basic framework for belief revision). Unfortunately, we can not draw a similar
conclusion in the context of belief update. The following theorem shows that
neither postulate (C1$\triangledown$) nor (C2$\triangledown$) is compatible
with the KM postulates.

######  Theorem 8.

There are a belief state $S$ associated with a collection $\leq^{S}$ of
partial preorders and a sentence $\varphi$ s.t. no update operator
$\triangledown$ satisfies (U1$\triangledown$)-(U8$\triangledown$) along with
(C1$\triangledown$) (resp. (C2$\triangledown$)).

The incompatibility is due to the following reason. On the one hand, each of
postulates (C1$\triangledown$) and (C2$\triangledown$) requires that the two
belief states $S\triangledown\varphi$ and
$(S\triangledown\phi)\triangledown\varphi$ should associate with the same
belief set given a specific new information $\varphi$. One the other hand, it
is possible that the two sets $\leq^{S}$ and $\leq^{S\triangledown\phi}$ have
different numbers of partial preorders, resulting in two different belief sets
which $S\triangledown\varphi$ and $(S\triangledown\phi)\triangledown\varphi$
have.

## Discussions

Examples 2-5 justify the rationality of the DP postulates in iterated update
scenario. In the following, we provide two counterexamples to
(C1$\triangledown$) and (C2$\triangledown$), respectively.

possible worlds | $w_{0}$ | $w_{1}$ | $w_{2}$ | $w_{3}$
---|---|---|---|---
clean | $\bot$ | $\bot$ | $\top$ | $\top$
dirty | $\bot$ | $\top$ | $\bot$ | $\top$
Table 3:  The definition of possible worlds in Example 8.

######  Example 8 (Postulate (C1$\triangledown$)).

We simplify Example 1, and now the table contains only one zone and some
glasses that are clean or dirty are on the table. The proposition $c$ (resp.
$d$) denotes that “some clean (resp. dirty) glasses are on the table”. Each
possible world is defined in Table 3. Initially, no glass is on the table. The
initial belief set $\mathtt{B}({S})$ is $\neg c\land\neg
d\equiv\mathtt{Form}({w_{0}})$. The collection $\leq^{S}$ of partial preorders
associated to $S$ contains the following preorder:

  * •

$w_{0}<^{S}_{w_{0}}w_{1}<^{S}_{w_{0}}w_{2},w_{3}$.

We first ask a robot to place some glasses on the table, that is, the new
information $\phi=c\lor d$. According to the semantics of the update operator,
we obtain the new belief set $\mathtt{B}({S\triangledown\phi})\equiv\neg
c\land d$, believing only dirty glasses are on the table. Afterwards, we
require the robot to place some clean glasses on the table, that is, the new
information $\varphi=c$. Similarly, the belief set
$\mathtt{B}({S\triangledown\varphi})$ is $c$. Since $\varphi\models\phi$,
postulate (DP1$\triangledown$) requires that
$\mathtt{B}({S\triangledown\phi\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\varphi})\equiv
c$. However, there are dirty glasses on the table in the belief state
$S\triangledown\phi$. The robot should not change the state of the glasses
already on the table. It makes sense to believe $c\land d$ after receiving the
new information $\varphi$ from the belief state $S\triangledown\phi$.

######  Example 9 (Postulate (C2$\triangledown$)).

We simplify Example 1, and the only items on the table are a book and a novel.
Initially, the book and the novel can be found in any zone of the table, that
is, the initial belief set $\mathtt{B}({S})$ is $\top$. We first instruct a
robot to move the book and the novel to the left zone, which is described as
the new information $\phi=b\land n$. The updated belief set
$\mathtt{B}({S\triangledown\phi})$ is therefore $b\land n$. The new
instruction to place the novel on the right zone, which is the new information
$\varphi=\neg n$, is issued to the robot. There is no reason to abandon the
proposition $b$ stating that the book is on the left zone, however, imposed by
(C2$\triangledown$), we have
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})=\mathtt{B}({S\triangledown\varphi})=\neg
n$. ∎

Examples 8 and 9 show that (C1$\triangledown$) and (C2$\triangledown$) leads
to counterintuitive results which they aim to avoid, respectively. Postulates
(C1$\triangledown$) and (C2$\triangledown$), however, are able to rule out
inadequate update behaviors as shown in Examples 2 and 3, respectively. We
remark that although the DP postulates are controversial in iterated belief
revision111The criticism comes from convincing counterexamples in which the DP
postulates cause counterintuitive results. Meyer (2001) and Stalnaker (2009)
put forward counterexamples to postulate (C1). Several counterexamples to
postulate (C2) are provided by Cantwell (1999) and Konieczny and Pino Pérez
(2000). In addition, postulate (C2) was discussed by Lehmann (1995),
Delgrande, Dubois, and Lang (2006) and Jin and Thielscher (2007). Hansson
(2016) offered two counterexamples to (C3) and (C4), respectively., they still
are the cornerstone of iterated belief change. Many subsequent work on
iterated belief change are based on the DP postulates. For example, belief
contraction is a type of belief change that studies the problem of how to
remove a certain information from a belief set. A revision operator can be
obtained from a contraction operator via the Levi identity (Levi 1978) and
vice versa via the Harper identity (Harper 1976). Chopra et al. (2008)
proposed four postulates for iterated belief contraction via slightly
modifying the DP postulates. Booth and Chandler (2019) considered the four
postulates as the benchmark of iterated belief contraction and use them to
evaluate their proposed iterated contraction operators. Reasoning about
actions, an important topic of knowledge representation and reasoning, studies
the change of agents’ beliefs due to the effect of action. Belief revision
were incorporated into the situation calculus, a well-known framework of
reasoning about actions (Shapiro et al. 2011; Fang and Liu 2013; Schwering,
Lakemeyer, and Pagnucco 2017). These works considered the DP postulates as key
properties of iterated belief revision and verified the satisfaction of the DP
postulates by their approaches so as to demonstrate the advantage of their
approaches. Hence, the four postulates (C1$\triangledown$)-(C4$\triangledown$)
we propose in this paper is a cornerstone of the subsequent research to
iterated belief update.

## Conclusions

In this paper, we have investigated the iteration of belief update. Inspired
by Darwiche and Pearl, we first presented a modification of the KM postulates
framework over belief states. With the help of belief states, we migrated the
DP postulates for iterated revision to the belief update scenario,
contributing to four iterated update postulates. Furthermore, we offered the
exact semantic characterizations based on partial preorders for each of the
resulting postulates. At last, the (in)compatibility results between the
iterated update postulates and the KM postulates are provided. We showed that,
unlike in revision, each of postulates (C1$\triangledown$) and
(C2$\triangledown$) for iterated update is incompatible with the KM
postulates.

Despite being the most influential approach to iterated belief revision, the
DP postulates are still too liberal to rule out unintended revision operators.
To strengthen the DP postulates, some additional postulates are proposed, for
example, natural (Nat) postulate (Boutilier 1996), lexicographic (Lex)
postulate (Nayak, Pagnucco, and Peppas 2003), and independence (Ind) postulate
(Booth and Meyer 2006; Jin and Thielscher 2007). We extended the above three
postulates to iterated belief update. In addition, we studied their semantic
characterization and proved the representation theorem. The (in)compatibility
results between them and the KM postulates are also analyzed. Due to space
limitation, these results were presented in Appendix.

## References

  * Alchourrón, Gärdenfors, and Makinson (1985) Alchourrón, C. E.; Gärdenfors, P.; and Makinson, D. 1985.  On the Logic of Theory Change: Partial Meet Contraction and Revision Functions.  _Journal of Symbolic Logic_ , 50(2): 510–530.
  * Booth and Chandler (2019) Booth, R.; and Chandler, J. 2019.  From iterated revision to iterated contraction: Extending the Harper Identity.  _Artificial Intelligence_ , 277: 103171:1–103171:20.
  * Booth and Meyer (2006) Booth, R.; and Meyer, T. 2006.  Admissible and Restrained Revision.  _Journal of Artificial Intelligence Research_ , 127–151.
  * Boutilier (1996) Boutilier, C. 1996.  Iterated Revision and Minimal Change of Conditional Beliefs.  _Journal of Philosophical Logic_ , 263–305.
  * Cantwell (1999) Cantwell, J. 1999.  Some Logics of Iterated Belief Change.  _Studia Logica_ , 63(1): 49–84.
  * Chopra et al. (2008) Chopra, S.; Ghose, A.; Meyer, T. A.; and Wong, K. 2008.  Iterated Belief Change and the Recovery Axiom.  _Journal of Philosophical Logic_ , 37(5): 501–520.
  * Darwiche and Pearl (1997) Darwiche, A.; and Pearl, J. 1997.  On the Logic of Iterated Belief Revision.  _Artificial Intelligence_ , 89(1): 1–29.
  * Delgrande, Dubois, and Lang (2006) Delgrande, J. P.; Dubois, D.; and Lang, J. 2006.  Iterated Revision as Prioritized Merging.  In _Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (KR-2016)_ , 210–220.
  * Fang and Liu (2013) Fang, L.; and Liu, Y. 2013.  Multiagent Knowledge and Belief Change in the Situation Calculus.  In _Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-2013)_ , 304–312.
  * Hansson (2016) Hansson, S. O. 2016.  Iterated Descriptor Revision and the Logic of Ramsey Test Conditionals.  _Journal of Philosophical Logic_ , 45(4): 429–450.
  * Harper (1976) Harper, W. L. 1976.  Rational Conceptual Change.  In _Proceedings of the Biennial Meeting of the Philosophy of Science Association_ , volume 2, 462–494.
  * Jin and Thielscher (2007) Jin, Y.; and Thielscher, M. 2007.  Iterated belief revision, revised.  _Artificial Intelligence_ , 171(1): 1–18.
  * Katsuno and Mendelzon (1991a) Katsuno, H.; and Mendelzon, A. O. 1991a.  On the Difference between Updating a Knowledge Base and Revising it.  In _Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning (KR-1991)_ , 387–394.
  * Katsuno and Mendelzon (1991b) Katsuno, H.; and Mendelzon, A. O. 1991b.  Propositional Knowledge Base Revision and Minimal Change.  _Artificial Intelligence_ , 52(3): 263–294.
  * Konieczny and Pino Pérez (2000) Konieczny, S.; and Pino Pérez, R. 2000.  A framework for iterated revision.  _Journal of Applied Non-Classical Logics_ , 10: 339–367.
  * Lehmann (1995) Lehmann, D. 1995.  Belief Revision, Revised.  In _Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-1995)_ , 1534–1540.
  * Levi (1978) Levi, I. 1978.  _Subjunctives, Dispositions and Chances_ , 303–335.  Springer Netherlands.
  * Meyer (2001) Meyer, T. 2001.  Basic Infobase Change.  _Studia Logica_ , 67(2): 215–242.
  * Nayak, Pagnucco, and Peppas (2003) Nayak, A. C.; Pagnucco, M.; and Peppas, P. 2003.  Dynamic Belief Revision Operators.  _Artificial Intelligence_ , 146(2): 193–228.
  * Rodrigues (2015) Rodrigues, S. 2015.  _On the Iteration of Katsuno and Mendelzon Update_.  Master’s thesis, University of Madeira.
  * Schwering, Lakemeyer, and Pagnucco (2017) Schwering, C.; Lakemeyer, G.; and Pagnucco, M. 2017.  Belief revision and projection in the epistemic situation calculus.  _Artificial Intelligence_ , 251: 62–97.
  * Shapiro et al. (2011) Shapiro, S.; Pagnucco, M.; Lespérance, Y.; and Levesque, H. J. 2011.  Iterated belief change in the situation calculus.  _Artificial Intelligence_ , 175(1): 165–192.
  * Stalnaker (2009) Stalnaker, R. 2009.  Iterated Belief Revision.  _Erkenntnis_ , 189–209.

##  Appendix A Extending Iterated Belief Update with Strengthened Iterated
Postulates

We first review the three strengthened iterated revision postulates: (Nat)
postulate (Boutilier 1996), (Lex) postulate (Nayak, Pagnucco, and Peppas
2003), and (Ind) postulate (Booth and Meyer 2006; Jin and Thielscher 2007),
and their corresponding semantic characterizations.

(Nat)

If $\mathtt{B}({S\circ\phi})\models\neg\varphi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\equiv\mathtt{B}({S\circ\varphi})$.

(Lex)

If $\varphi\not\models\neg\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\models\phi$.

(Ind)

If $\mathtt{B}({S\circ\varphi})\not\models\neg\phi$, then
$\mathtt{B}({(S\circ\phi)\circ\varphi})\models\phi$.

The semantic counterparts of the three postulates and the representation
theorem (Boutilier 1996; Nayak, Pagnucco, and Peppas 2003; Booth and Meyer
2006; Jin and Thielscher 2007) are given in the following.

(NatR)

If $w_{1},w_{2}\notin[\mathtt{B}({S\circ\phi})]$, then $w_{1}\leq_{S}w_{2}$
iff $w_{1}\leq_{S\circ\phi}w_{2}$.

(LexR)

If $w_{1}\in[\phi]$ and $w_{2}\in[\neg\phi]$, then $w_{1}<_{S\circ\phi}w_{2}$.

(IndR)

If $w_{1}\in[\phi]$ and $w_{2}\in[\neg\phi]$, then $w_{1}\leq_{S}w_{2}$ only
if $w_{1}<_{S\circ\phi}w_{2}$.

######  Theorem 9.

Let $\circ$ be a revision operator satisfying (R*1)-(R*6). Then, $\circ$
satisfies (Nat) (resp. (Lex)/(Ind)) iff the operator and its corresponding
faithful assignment satisfies (NatR) (resp. (LexR)/(IndR)).

We hereafter show their migration to iterated belief update. Similarly, we
denote the resulting iterated update postulates by (Nat$\triangledown$),
(Lex$\triangledown$) and (Ind$\triangledown$), which can be obtained by
replacing the revision operator $\circ$ in the corresponding revision
postulate by the update operator $\triangledown$. The exact semantic
characterizations based on partial preorders for these postulates are listed
in the following.

(NatR$\triangledown$)

For every $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min([\phi],\leq^{S}_{w})\cap\mathcal{N}=\emptyset$ holds for every
$w\in[\mathtt{B}({S})]$, the following hold

Forth

for every $w\in[\mathtt{B}({S})]$ and
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$, there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})$.

Back

for every $w^{\prime}\\!\in\\![\mathtt{B}({S\triangledown\phi})]$ and
$w^{\prime\prime}\\!\in\\!\min(\mathcal{N}\\!,\\!\leq^{S\triangledown\phi}_{w^{\prime}})$,
there is $w\in[\mathtt{B}({S})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$.

(LexR$\triangledown$)

For every $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\mathcal{N}\cap[\phi]\neq\emptyset$, we have
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$ for
every $w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$.

(IndR$\triangledown$)

For every $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$ holds for some
$w\in[\mathtt{B}({S})]$, we have
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$ for
every $w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$.

The semantics (NatR$\triangledown$) requires that for every subset
$\mathcal{N}$ of possible worlds such that every minimal element of $[\phi]$
w.r.t. $\leq^{S}$ is not in $\mathcal{N}$, the minimal elements of
$\mathcal{N}$ w.r.t. $\leq^{S\triangledown\phi}$ ought to be the same as that
w.r.t. the preorders $\leq^{S}$. The semantics (LexR$\triangledown$) means
that for every subset $\mathcal{N}$ with at least one possible world of
$\phi$, all of the minimal elements of $\mathcal{N}$ w.r.t. the collection
$\leq^{S\triangledown\phi}$ of preorders associated with the updated belief
state should satisfy $\phi$. The semantics (IndR$\triangledown$) restricts
$\leq^{S\triangledown\phi}$ in a similar way as (LexR$\triangledown$), except
that it focuses on a subset $\mathcal{N}$ such that its minimal elements
w.r.t. $\leq^{S}$ to contain at least one possible world satisfying $\phi$. In
such case, it is required that the minimal elements of $\mathcal{N}$ w.r.t.
the preorders $\leq^{S\triangledown\phi}$ contains no elements of $[\phi]$,
neither.

Theorem 10 shows the correspondence between each of the above three postulates
and its corresponding semantics, based on faithful collective assignments.

######  Theorem 10.

Let $\triangledown$ be an update operator satisfying
(U1$\triangledown$)-(U8$\triangledown$). Then, $\triangledown$ satisfies
(Nat$\triangledown$) (resp. (Lex$\triangledown$)/(Ind$\triangledown$)) iff the
operator and its corresponding faithful collective assignment satisfies
(NatR$\triangledown$) (resp. (LexR$\triangledown$)/(IndR$\triangledown$)).

We also investigate the affiliation among the DP postulates and the above
postulates for iterated belief update. Postulates (Lex$\triangledown$) and
(Ind$\triangledown$) can be viewed as the reinforcements of
(C3$\triangledown$) and (C4$\triangledown$). Besides, postulate
(Nat$\triangledown$) is stronger than (C2$\triangledown$).

######  Theorem 11.

Let $\triangledown$ be an update operator satisfying
(U1$\triangledown$)-(U8$\triangledown$). Then, the following hold

  * •

$\triangledown$ satisfies (Lex$\triangledown$) only if it satisfies
(Ind$\triangledown$).

  * •

$\triangledown$ satisfies (Ind$\triangledown$) only if it satisfies
(C3$\triangledown$) and (C4$\triangledown$).

  * •

$\triangledown$ satisfies (Nat$\triangledown$) only if it satisfies
(C2$\triangledown$).

Finally, we provide some (in)compatibility results between the above iterated
update postulates and the modified KM postulates.

######  Theorem 12.

The update operator $\triangledown_{1}$ satisfies postulates
(Lex$\triangledown$) and (Ind$\triangledown$).

######  Theorem 13.

There are a belief state $S$ associated with a collection $\leq^{S}$ of
partial preorders and a sentence $\varphi$ s.t. no update operator
$\triangledown$ satisfies (U1$\triangledown$)-(U8$\triangledown$) along with
(Nat$\triangledown$).

Theorem 12 confirms that postulates (Lex$\triangledown$) and
(Ind$\triangledown$) are compatible with the modified KM postulates. In
contrast, Theorem 13 shows the incompatibility between postulate
(Nat$\triangledown$) and the modified KM postulates.

##  Appendix B Supplemental Proofs

Proof of Theorem 4

###### Proof.

($\Rightarrow$): Assume that $\triangledown$ satisfies postulates
(U1$\triangledown$)-(U8$\triangledown$). For every belief state $S$, we
construct a collection $\\{\leq^{S}_{w}\\}_{w\in[\mathtt{B}({S})]}$ of binary
relations over $\mathcal{M}$ as follow.

  * •

Base case ($|{[\mathtt{B}({S})]}|=1$): $w_{1}\leq^{S}_{w}w_{2}$ iff $w_{1}=w$,
or $[\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{2}})})]=\\{w_{1}\\}$.

  * •

Inductive case ($|{[\mathtt{B}({S})]}|>1$):

By (U8$\triangledown$),
$\mathtt{B}({S\triangledown\varphi})\equiv\bigvee\limits_{w_{i}\in[\mathtt{B}({S})]}\mathtt{B}({S_{i}\triangledown\varphi})$
for some set of belief states $\\{S_{1},\cdots,S_{n}\\}$ s.t.
$\mathtt{B}({S_{i}})\equiv\mathtt{Form}({w_{i}})$.

We let $\leq^{S}_{w}=\leq^{S_{i}}_{w_{i}}$ where $w=w_{i}$.

We first show that each relation $\leq^{S}_{w}$ is a partial preorder faithful
to $w$ for every belief state $S$ and every $w\in[\mathtt{B}({S})]$. When
$|{[\mathtt{B}({S})]}|>1$, each $\leq^{S}_{w}$ is $\leq^{S^{\prime}}_{w}$ for
some $S^{\prime}$ s.t. $|{[\mathtt{B}({S^{\prime}})]}|=1$ and
$w\in[\mathtt{B}({S^{\prime}})]$. Hence, it suffices to verify the base case
where $|{[\mathtt{B}({S})]}|=1$ and $w\in[\mathtt{B}({S})]$.

  * •

Reflexivity: Clearly, $w\leq^{S}_{w}w$. Suppose that $w^{\prime}\neq w$. By
the postulates (U1$\triangledown$) and (U3$\triangledown$), we get that
$\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime}})})\equiv\mathtt{Form}({w^{\prime}})$.
It follows from the definition of $\leq^{S}_{w}$ that
$w^{\prime}\leq^{S}_{w}w^{\prime}$.

  * •

Transitivity: Assume that $w_{1}\leq^{S}_{w}w_{2}$ and
$w_{2}\leq^{S}_{w}w_{3}$. We hereafter prove that $w_{1}\leq^{S}_{w}w_{3}$.

    * –

The case where $w_{1}=w$: it directly follows from the definition of
$\leq^{S}_{w}$.

    * –

The case where $w_{1}\neq w$ and $w_{2}=w$: it is impossible since
$\leq^{S}_{w}$ is faithful, which is independently verified later.

    * –

The case where $w_{1}\neq w$ and $w_{2}\neq w$: Let
$\varphi=\mathtt{Form}({w_{1},w_{2},w_{3}})$. Since $w_{1}\leq^{S}_{w}w_{2}$
and $w_{1}\not=w$, it follows from the definition of $\leq^{S}_{w}$ that
$[\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{2}})})]=\\{w_{1}\\}$. By
(U5$\triangledown$),
$[\mathtt{B}({S\triangledown\varphi})\land\mathtt{Form}({w_{1},w_{2}})]\subseteq[\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{2}})})]$.
So, $w_{2}\notin[\mathtt{B}({S\triangledown\varphi})]$. Similarly, as
$w_{2}\leq^{S}_{w}w_{3}$ and $w_{2}\not=w$, we can obtain that
$[\mathtt{B}({S\triangledown\mathtt{Form}({w_{2},w_{3}})})]=\\{w_{2}\\}$ and
$w_{3}\notin[\mathtt{B}({S\triangledown\varphi})]$. These, together with
postulates (U1$\triangledown$) and (U3$\triangledown$), imply that
$[\mathtt{B}({S\triangledown\varphi})]=\\{w_{1}\\}$. Hence,
$\mathtt{B}({S\triangledown\varphi})\models\mathtt{Form}({w_{1},w_{3}})$.
Besides, it follows from (U1$\triangledown$) that
$\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{3}})})\models\mathtt{Form}({w_{1},w_{3}})$
and $\mathtt{Form}({w_{1},w_{3}})\models\varphi$. By (U6$\triangledown$), we
get that
$[\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{3}})})]=[\mathtt{B}({S\triangledown\varphi})]=\\{w_{1}\\}$.
it follows from the definition of $\leq^{S}_{w}$ that
$w_{1}\leq^{S}_{w}w_{3}$.

  * •

Faithfulness: Let $w^{\prime}$ be a possible world distinct to $w$. Clearly,
$w\leq^{S}_{w}w^{\prime}$. By (U2$\triangledown$), we get that
$\mathtt{B}({S\triangledown\mathtt{Form}({w,w^{\prime}})})\equiv\mathtt{Form}({w})$.
So $w^{\prime}\not\leq^{S}_{w}w$.

Finally we prove that
$[\mathtt{B}({S\triangledown\varphi})]\\!=\\!\bigcup\limits_{w\in[\mathtt{B}({S})]}\min([\varphi],\leq^{S}_{w})$.

The case where $\varphi$ is inconsistent, $[\varphi]=\emptyset$: it directly
follows from (U1$\triangledown$) that
$[\mathtt{B}({S\triangledown\varphi})]=\emptyset$. Therefore,
$[\mathtt{B}({S\triangledown\varphi})]=\bigcup\limits_{w\in[\mathtt{B}({S})]}\min([\varphi],\leq^{S}_{w})=\emptyset$.

The case where $\varphi$ is consistent: we first show that
$[\mathtt{B}({S\triangledown\varphi})]=\min([\varphi],\leq^{S}_{w})$ when
$\mathtt{B}({S})\equiv\mathtt{Form}({w})$.

  * •

We prove that
$[\mathtt{B}({S\triangledown\varphi})]\subseteq\min([\varphi],\leq^{S}_{w})$
by contradiction. Assume that $w_{1}\in[\mathtt{B}({S\triangledown\varphi})]$
and $w_{1}\not\in\min([\varphi],\leq^{S}_{w})$. There is $w_{2}\in[\varphi]$
s.t. $w_{2}<^{S}_{w}w_{1}$. By (U1$\triangledown$) and the definition of
$\leq^{S}_{w}$, we get that
$[\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{2}})})]=\\{w_{2}\\}$. It
follows from (U5$\triangledown$) that
$[\mathtt{B}({S\triangledown\varphi})\land\mathtt{Form}({w_{1},w_{2}})]\subseteq[\mathtt{B}({S\triangledown(\mathtt{Form}({w_{1},w_{2}})\land\varphi)})]=[\mathtt{B}({S\triangledown\mathtt{Form}({w_{1},w_{2}})})]$.
It follows that
$w_{1}\notin[\mathtt{B}({S\triangledown\varphi})\land\mathtt{Form}({w_{1},w_{2}})]$.
Hence, $w_{1}\notin[\mathtt{B}({S\triangledown\varphi})]$, which contradicts
with the assumption.

  * •

We prove that
$\min([\varphi],\leq^{S}_{w})\subseteq[\mathtt{B}({S\triangledown\varphi})]$.
Assume that $w^{\prime}\in\min([\varphi],\leq^{S}_{w})$, it remains to verify
that $w^{\prime}\in[\mathtt{B}({S\triangledown\varphi})]$. In the case where
$w^{\prime}=w$, we get that $\mathtt{B}({S})\models\varphi$. It directly
follows from (U2$\triangledown$) that
$w^{\prime}\in[\mathtt{B}({S\triangledown\varphi})]$. In the case where
$w^{\prime}\not=w$. Let $[\varphi]=\\{w_{1},\dots,w_{n}\\}$. Clealy,
$\varphi\equiv\mathtt{Form}({w^{\prime},w_{1}})\lor\cdots\lor\mathtt{Form}({w^{\prime},w_{n}})$.
Since $w^{\prime}\in\min([\varphi],\leq^{S}_{w})$, for every
$w_{i}\in[\varphi]$, it holds that $w_{i}\not<^{S}_{w}w^{\prime}$. Thus, we
get that (1) $w^{\prime}\leq^{S}_{w}w_{i}$; or (2)
$w^{\prime}\not\leq^{S}_{w}w_{i}$ and $w_{i}\not\leq^{S}_{w}w^{\prime}$. For
Case (1), it follows from the definition of $\leq^{S}_{w}$ that
$w^{\prime}\in[\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime},w_{i}})})]$.
For Case (2), it follows from the definition of $\leq^{S}_{w}$ that
$[\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime},w_{i}})})]\not=\\{w^{\prime}\\}\not=\\{w_{i}\\}$.
This, together with postulates (U1$\triangledown$) and (U3$\triangledown$),
implies that
$[\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime},w_{i}})})]=\\{w^{\prime},w_{i}\\}$,
hence
$w^{\prime}\in[\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime},w_{i}})})]$.
Therefore, we can obtain that
$w^{\prime}\in[\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime},w_{1}})})\land\cdots\land\mathtt{B}({S\triangledown\mathtt{Form}({w^{\prime},w_{n}})})]$.
From (U1$\triangledown$), it holds that
$w^{\prime}\in[\mathtt{B}({S\triangledown(\mathtt{Form}({w^{\prime},w_{1}})\lor\cdots\lor\mathtt{Form}({w^{\prime},w_{n}}))})]=[\mathtt{B}({S\triangledown\varphi})]$.

We now consider the situation where $|{[\mathtt{B}({S})]}|>1$. According to
postulate (U8$\triangledown$) and the definition of $\leq^{S}_{w}$, there is a
set of belief state $\\{S_{1},\cdots,S_{n}\\}$ s.t.
$[\mathtt{B}({S\triangledown\varphi})]\\!=\\!\bigcup\limits_{w_{i}\in[\mathtt{B}({S})]}[\mathtt{B}({S_{i}\triangledown\varphi})]\\!=\\!\bigcup\limits_{w_{i}\in[\mathtt{B}({S})]}\min([\varphi],\leq^{S_{i}}_{w_{i}})\\!=\\!\bigcup\limits_{w_{i}\in[\mathtt{B}({S})]}\min([\varphi],\leq^{S}_{w_{i}})$
and $\mathtt{B}({S_{i}})\equiv\mathtt{Form}({w_{i}})$.

($\Leftarrow$): Assume that there is a faithful collective assignment that
maps each belief state $S$ to a collection $\leq^{S}$ of partial preorders. We
define an operator $\triangledown$ by
$[\mathtt{B}({S\triangledown\varphi})]=\bigcup\limits_{w\in[\mathtt{B}({S})]}\min([\varphi],\leq^{S}_{w})$.
It is easily verified that (U1$\triangledown$), (U3$\triangledown$) and
(U4$\triangledown$) hold. In addition, when $\mathtt{B}({S})$ is inconsistent,
(U2$\triangledown$), (U5$\triangledown$), (U6$\triangledown$),
(U7$\triangledown$) and (U8$\triangledown$) hold. In the following, we only
prove that $\triangledown$ satisfies postulates (U2$\triangledown$),
(U5$\triangledown$), (U6$\triangledown$), (U7$\triangledown$) and
(U8$\triangledown$) when $\mathtt{B}({S})$ is consistent.

  * •

(U2$\triangledown$): Assume that $\mathtt{B}({S})\models\varphi$.

By postulate (U8$\triangledown$), which is independently proved later,
$[\mathtt{B}({S\triangledown\varphi})]=\bigcup\limits_{w_{i}\in[\mathtt{B}({S})]}[\mathtt{B}({S_{i}\triangledown\varphi})]$
for some set of belief states $\\{S_{1},\cdots,S_{n}\\}$ s.t.
$\mathtt{B}({S_{i}})\equiv\mathtt{Form}({w_{i}})$.

It follows from the definition of $\triangledown$ that
$[\mathtt{B}({S_{i}\triangledown\varphi})]\\!=\\!\min([\varphi],\leq^{S_{i}}_{w_{i}})$.
Since $\mathtt{B}({S})\models\varphi$, $w_{i}\in[\varphi]$. By the
faithfulness of $\leq^{S}_{w}$, we get that
$[\mathtt{B}({S_{i}\triangledown\varphi})]=\\{w_{i}\\}$. Therefore,
$[\mathtt{B}({S\triangledown\varphi})]=[\mathtt{B}({S})]$.

  * •

(U5$\triangledown$): In the case where
$\mathtt{B}({S\triangledown\varphi})\land\phi$ is inconsistent,
(U5$\triangledown$) trivially holds. We now consider the converse case. Let
$w_{1}\in[\mathtt{B}({S\triangledown\varphi})\land\phi]$. Then
$w_{1}\in[\mathtt{B}({S\triangledown\varphi})]$. By the definition of
$\triangledown$, there is $w\\!\in\\![\mathtt{B}({S})]$ s.t.
$w_{1}\\!\in\\!\min([\varphi],\leq^{S}_{w})$. Since
$[\varphi\land\phi]\subseteq[\varphi]$ and $w_{1}\in[\phi]$, we get that
$w_{1}\in\min([\varphi\land\phi],\leq^{S}_{w})$. It follows from the
definition of $\triangledown$ that
$w_{1}\in[\mathtt{B}({S\triangledown(\varphi\wedge\phi)})]$, hence
$\mathtt{B}({S\triangledown\varphi})\land\phi\models\mathtt{B}({S\triangledown(\varphi\wedge\phi)})$.

  * •

(U6$\triangledown$): Suppose that
$\mathtt{B}({S\triangledown\varphi})\models\phi$ and
$\mathtt{B}({S\triangledown\phi})\models\varphi$. We first prove that
$[\mathtt{B}({S\triangledown\varphi})]\subseteq[\mathtt{B}({S\triangledown\phi})]$
by contradiction. Assume that $w_{1}\in[\mathtt{B}({S\triangledown\varphi})]$
and $w_{1}\notin[\mathtt{B}({S\triangledown\phi})]$. Since
$\mathtt{B}({S\triangledown\varphi})\models\phi$, $w_{1}\in[\phi]$. As
$w_{1}\notin[\mathtt{B}({S\triangledown\phi})]$, by the definition of
$\triangledown$, for every $w\in[\mathtt{B}({S})]$,
$w_{1}\notin\min([\phi],\\!\\!\leq^{S}_{w})$. Thus, there exist
$w_{2}\in[\phi]$ s.t. $w_{2}\in\min([\phi],\leq^{S}_{w})$ and
$w_{2}<^{S}_{w}w_{1}$. It follows that
$w_{2}\in[\mathtt{B}({S\triangledown\phi})]$. Since
$\mathtt{B}({S\triangledown\phi})\models\varphi$, $w_{2}\in[\varphi]$. As
$w_{2}<^{S}_{w}w_{1}$, we get that $w_{1}\notin\min([\varphi],\leq^{S}_{w})$.
It follows from the definition of $\triangledown$ that
$w_{1}\notin[\mathtt{B}({S\triangledown\varphi})]$, which contradicts with
that $w_{1}\in[\mathtt{B}({S\triangledown\varphi})]$. Similarly, it can be
verified that
$[\mathtt{B}({S\triangledown\varphi})]\supseteq[\mathtt{B}({S\triangledown\phi})]$.

  * •

(U7$\triangledown$): Suppose that $\mathtt{B}({S})$ is complete. Let
$\mathtt{B}({S})\equiv\mathtt{Form}({w})$. We prove by contradiction. Assume
that
$w_{1}\in[\mathtt{B}({S\triangledown\varphi})\land\mathtt{B}({S\triangledown\phi})]$
and $w_{1}\notin[\mathtt{B}({S\triangledown(\varphi\lor\phi)})]$. By the
definition of $\triangledown$, $w_{1}\in\min([\varphi],\leq^{S}_{w})$,
$w_{1}\in\min([\phi],\leq^{S}_{w})$ and
$w_{1}\notin\min([\varphi\lor\phi],\leq^{S}_{w})$. Clealy, there exist
$w_{2}\in[\varphi\lor\phi]$ s.t.
$w_{2}\in\min([\varphi\lor\phi],\leq^{S}_{w})$ and $w_{2}<^{S}_{w}w_{1}$. In
the case where $w_{2}\in[\varphi]$, we get that
$w_{1}\notin\min([\varphi],\leq^{S}_{w})$, which contradicts with that
$w_{1}\in\min([\varphi],\leq^{S}_{w})$. In another case where
$w_{2}\in[\phi]$, we get that $w_{1}\notin\min([\phi],\leq^{S}_{w})$, which
contradicts with that $w_{1}\in\min([\phi],\leq^{S}_{w})$.

  * •

(U8$\triangledown$): It follows from the definition of $\triangledown$ that
$[\mathtt{B}({S\triangledown\varphi})]=\bigcup\limits_{w_{i}\in[\mathtt{B}({S})]}\min([\varphi],\leq^{S}_{w_{i}})$.
From the faithfulness, for every $w_{i}\in[\mathtt{B}({S})]$, there is a
belief state $S_{i}$ s.t. $\mathtt{B}({S_{i}})\equiv\mathtt{Form}({w_{i}})$
and $\leq^{S}_{w_{i}}=\leq^{S_{i}}_{w_{i}}$. By the definition of
$\triangledown$,
$[\mathtt{B}({S_{i}\triangledown\varphi})]=\min([\varphi],\leq^{S_{i}}_{w_{i}})$.
Since $\leq^{S}_{w_{i}}=\leq^{S_{i}}_{w_{i}}$, we get that
$[\mathtt{B}({S_{i}\triangledown\varphi})]=\min([\varphi],\leq^{S}_{w_{i}})$.
Therefore,
$\mathtt{B}({S\triangledown\varphi})\equiv\bigvee\limits_{w_{i}\in[\mathtt{B}({S})]}\mathtt{B}({S_{i}\triangledown\varphi})$
for some set of belief states $\\{S_{1},\cdots,S_{n}\\}$ s.t.
$\mathtt{B}({S_{i}})\equiv\mathtt{Form}({w_{i}})$.

∎

Proof of Theorem 5

###### Proof.

  * •

(C1$\triangledown$) $\Leftrightarrow$ (CR1$\triangledown$).

($\Rightarrow$): Assume that $\triangledown$ satisfies (C1$\triangledown$). We
here only show that the forth part of (CR1$\triangledown$). The back part can
be similarly shown. Let $\mathcal{N}\subseteq[\phi]$, $w\in[\mathtt{B}({S})]$
and $w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$. We define $\varphi$
as $\mathtt{Form}({\mathcal{N}})$. Clearly, $\varphi\models\phi$. By
(C1$\triangledown$),
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\equiv\mathtt{B}({S\triangledown\varphi})$.
It directly follows from the semantics of the update operator that

$\bigcup\limits_{w\in[{\mathtt{B}({S})}]}\min([\varphi],\leq^{S}_{w})=\bigcup\limits_{w^{\prime}\in[{\mathtt{B}({S\triangledown\phi})}]}\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}}).$

Clearly,
$w^{\prime\prime}\in\bigcup\limits_{w\in[{\mathtt{B}({S})}]}\min([\varphi],\leq^{S}_{w})$.
By the above equation,
$w^{\prime\prime}\in\bigcup\limits_{w^{\prime}\in[{\mathtt{B}({S\triangledown\phi})}]}\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})$.
Hence, there is $w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})$.

($\Leftarrow$): Assume that $\leq^{S}$ and $\leq^{S\triangledown\phi}$ satisfy
(CR1$\triangledown$). Suppose that $\varphi\models\phi$. We here only show
that
$[\mathtt{B}({S\triangledown\varphi})]\subseteq[\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})]$.
The opposite direction
$[\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})]\subseteq[\mathtt{B}({S\triangledown\varphi})]$
can be similarly proved. Let
$w^{\prime\prime}\in[\mathtt{B}({S\triangledown\varphi})]$. It follows from
the semantics of the update operator that there is $w\in[\mathtt{B}({S})]$
s.t. $w^{\prime\prime}\in\min([\varphi],\leq^{S}_{w})$. By the forth part of
(CR1$\triangledown$), there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})$.
So
$w^{\prime\prime}\in[\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})]$.

  * •

(C2$\triangledown$) $\Leftrightarrow$ (CR2$\triangledown$). The proof is
symmetric with the one above.

  * •

(C3$\triangledown$) $\Leftrightarrow$ (CR3$\triangledown$).

($\Rightarrow$): Assume that $\triangledown$ satisfies (C3$\triangledown$).
Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\subseteq[\phi]$ holds for every
$w\in[\mathtt{B}({S})]$. We define $\varphi$ as
$\mathtt{Form}({\mathcal{N}})$. By the semantics of the update operator,
$\mathtt{B}({S\triangledown\varphi})\models\phi$. By (C3$\triangledown$), we
obtain that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$. By the
semantics of the update operator again, for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.

($\Leftarrow$): Assume that $\leq^{S}$ and $\leq^{S\triangledown\phi}$ satisfy
(CR3$\triangledown$). Suppose that
$\mathtt{B}({S\triangledown\varphi})\models\phi$. By the semantics of the
update operator, for every $w\in[\mathtt{B}({S})]$,
$\min([\varphi],\leq^{S}_{w})\subseteq[\phi]$. By (CR3$\triangledown$), we
obtain that for every $w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.
Hence, $\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$.

  * •

(C4$\triangledown$) $\Leftrightarrow$ (CR4$\triangledown$).

($\Rightarrow$): Assume that $\triangledown$ satisfies (C4$\triangledown$).
Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$ for some
$w\in[\mathtt{B}({S})]$. We define $\varphi$ as
$\mathtt{Form}({\mathcal{N}})$. By the semantics of the update operator,
$\mathtt{B}({S\triangledown\varphi})\not\models\neg\phi$. By
(C4$\triangledown$), we obtain that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\not\models\neg\phi$.
By the semantics of the update operator again, there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\cap[\phi]\neq\emptyset$.

($\Leftarrow$): Assume that $\leq^{S}$ and $\leq^{S\triangledown\phi}$ satisfy
(CR4$\triangledown$). Suppose that
$\mathtt{B}({S\triangledown\varphi})\models\neg\phi$. By the semantics of the
update operator, there is $w\in[\mathtt{B}({S})]$,
$\min([\varphi]\leq^{S}_{w})\cap[\phi]\neq\emptyset$. By (CR4$\triangledown$),
we get that there is $w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})\cap[\phi]\neq\emptyset$.
Hence,
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\not\models\neg\phi$.

∎

Proof of Theorem 7

###### Proof.

It directly follows from the fact that postulate (Lex$\triangledown$) entails
postulates (C3$\triangledown$) and (C4$\triangledown$) and that
$\triangledown_{1}$ satisfies postulate (Lex$\triangledown$), which are
independently proved later in Theorem 11 and Theorem 12 respectively, ∎

Proof of Theorem 8

###### Proof.

We first consider postulate (C1$\triangledown$). We will construct a belief
state $S$ associated with a collection $\leq^{S}$ of partial preorders and a
sentence $\phi$ s.t. there does not exist any collection
$\leq^{S\triangledown\phi}$ of partial preorders s.t. $\leq^{S}$ and
$\leq^{S\triangledown\phi}$ satisfy (CR1$\triangledown$).

Let $\mathcal{P}=\\{p_{1},p_{2},p_{3}\\}$ and
$\mathcal{M}=\\{w_{1},\dots,w_{8}\\}$222We remark that this proof holds no
matter what the truth assignment on each possible world $w_{i}$ is. Hence, we
do not fix a truth assignment on each world.. Let $S$ be a belief state with
its associated belief set $[\mathtt{B}({S})]=\\{w_{1},w_{2}\\}$ and its
assigned partial preorders $\leq^{S}_{w_{1}}$ and $\leq^{S}_{w_{2}}$ as
follows.

  * •

$\\!\\!w_{1}\\!<^{S}_{w_{1}}\\!\\!w_{2}\\!<^{S}_{w_{1}}\\!\\!w_{3}\\!<^{S}_{w_{1}}\\!\\!w_{4}\\!<^{S}_{w_{1}}\\!\\!w_{6}\\!<^{S}_{w_{1}}\\!\\!w_{5}\\!<^{S}_{w_{1}}\\!\\!w_{7}\\!<^{S}_{w_{1}}\\!\\!w_{8}$.

  * •

$\\!\\!w_{2}\\!<^{S}_{w_{2}}\\!\\!w_{1}\\!<^{S}_{w_{2}}\\!\\!w_{3}\\!<^{S}_{w_{2}}\\!\\!w_{5}\\!<^{S}_{w_{2}}\\!\\!w_{6}\\!<^{S}_{w_{2}}\\!\\!w_{4}\\!<^{S}_{w_{2}}\\!\\!w_{7}\\!<^{S}_{w_{2}}\\!\\!w_{8}$.

Let $\phi=\mathtt{Form}({w_{3},w_{4},w_{5},w_{6}})$. By the semantics of the
update operator, $[\mathtt{B}({S\triangledown\phi})]=\\{w_{3}\\}$. The
collection $\leq^{S\triangledown\phi}$ contains only one partial preorder
$\leq^{S\triangledown\phi}_{w_{3}}$. Assume that the forth part of
(CR1$\triangledown$) holds. That is, for every $\mathcal{N}\subseteq[\phi]$,
$w\in[\mathtt{B}({S})]$ and
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$, there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})$.
We will show that the back part of (CR1$\triangledown$) does not hold, that
is, there is $\mathcal{N}_{3}\subseteq[\phi]$,
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ and
$w^{\prime\prime}\in\min(\mathcal{N}_{3},\leq^{S\triangledown\phi}_{w^{\prime}})$
s.t. $w^{\prime\prime}\notin\min(\mathcal{N}_{3},\leq^{S}_{w})$ holds for
every $w\in[\mathtt{B}({S})]$.

Let $\mathcal{N}_{0}=\\{w_{4},w_{5}\\}$, $\mathcal{N}_{1}=\\{w_{5},w_{6}\\}$
and $\mathcal{N}_{2}=\\{w_{4},w_{6}\\}$. Since
$\mathcal{N}_{0}\subseteq[\phi]$,
$w_{4}\in\min(\mathcal{N}_{0},\leq^{S}_{w_{1}})$, by the assumption above, we
have $w_{4}\in\min(\mathcal{N}_{0},\leq^{S\triangledown\phi}_{w_{3}})$.
Similarly, as $w_{5}\in\min(\mathcal{N}_{0},\leq^{S}_{w_{2}})$, we have
$w_{5}\in\min(\mathcal{N}_{0},\leq^{S\triangledown\phi}_{w_{3}})$. It holds
that $w_{5}\not<^{S\triangledown\phi}_{w_{3}}w_{4}$ and
$w_{4}\not<^{S\triangledown\phi}_{w_{3}}w_{5}$. Therefore, $w_{4}$ and $w_{5}$
are either equivalently plausible
($w_{4}\approx^{S\triangledown\phi}_{w_{3}}w_{5}$) or incomparable
($w_{4}\neq^{S\triangledown\phi}_{w_{3}}w_{5}$ and
$w_{5}\neq^{S\triangledown\phi}_{w_{3}}w_{4}$) w.r.t.
$\leq^{S\triangledown\phi}_{w_{3}}$. Similarly, since
$\mathcal{N}_{1}\subseteq[\phi]$,
$w_{5}\in\min(\mathcal{N}_{1},\leq^{S}_{w_{2}})$ and
$w_{6}\in\min(\mathcal{N}_{1},\leq^{S}_{w_{1}})$, we get that $w_{5}$ and
$w_{6}$ are either equivalently plausible or incomparable w.r.t.
$\leq^{S\triangledown\phi}_{w_{3}}$. In addition, as
$\mathcal{N}_{2}\subseteq[\phi]$,
$w_{4}\in\min(\mathcal{N}_{2},\leq^{S}_{w_{1}})$ and
$w_{6}\in\min(\mathcal{N}_{2},\leq^{S}_{w_{2}})$, we get that $w_{4}$ and
$w_{6}$ are either equivalently plausible or incomparable w.r.t.
$\leq^{S\triangledown\phi}_{w_{3}}$.

Let $\mathcal{N}_{3}=\\{w_{4},w_{5},w_{6}\\}$. Clearly,
$\mathcal{N}_{3}\subseteq[\phi]$. It can be verified that
$\min(\mathcal{N}_{3},\leq^{S\triangledown\phi}_{w_{3}})=\\{w_{4},w_{5},w_{6}\\}$,
hence $w_{6}\in\min(\mathcal{N}_{3},\leq^{S\triangledown\phi}_{w_{3}})$. By
the back part of (CR1$\triangledown$), we get that
$w_{6}\in\min(\mathcal{N}_{3},\leq^{S}_{w_{1}})$ or
$w_{6}\in\min(\mathcal{N}_{3},\leq^{S}_{w_{2}})$. However, neither
$w_{6}\in\min(\mathcal{N}_{3},\leq^{S}_{w_{1}})$ nor
$w_{6}\in\min(\mathcal{N}_{3},\leq^{S}_{w_{2}})$, which is a contradiction.

The proof for (C2$\triangledown$) is similar to the above case except that we
take into consideration $\phi=\mathtt{Form}({w_{3}})$. ∎

Proof of Theorem 10

###### Proof.

  * •

(Nat$\triangledown$) $\Leftrightarrow$ (NatR$\triangledown$).

($\Rightarrow$): Assume that $\triangledown$ satisfies (Nat$\triangledown$).
We here only show that the forth part of (NatR$\triangledown$). The back part
can be similarly shown. Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min([\phi],\leq^{S}_{w})\cap\mathcal{N}=\emptyset$ holds for every
$w\in[\mathtt{B}({S})]$. We define $\varphi$ as
$\mathtt{Form}({\mathcal{N}})$. It follows from the semantics of the update
operator that $\mathtt{B}({S\triangledown\phi})\models\neg\varphi$. By
(Nat$\triangledown$),
$\mathtt{B}({(S\triangledown\phi)\\!\triangledown\\!\varphi})\\!\equiv\\!\mathtt{B}({S\triangledown\varphi})$.
By the semantics of the update operator again, we get

$\bigcup\limits_{w\in[{\mathtt{B}({S})}]}\min([\varphi],\leq^{S}_{w})=\bigcup\limits_{w^{\prime}\in[{\mathtt{B}({S\triangledown\phi})}]}\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}}).$

Hence, for every $w\in[\mathtt{B}({S})]$ and
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S}_{w})$, there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})$.

($\Leftarrow$): Assume that $\leq^{S}$ and $\leq^{S\triangledown\phi}$ satisfy
(NatR$\triangledown$). Assume that
$\mathtt{B}({S\triangledown\phi})\models\neg\varphi$. We only show that
$[\mathtt{B}({S\triangledown\varphi})]\subseteq[\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})]$.
The opposite direction
$[\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})]\subseteq[\mathtt{B}({S\triangledown\varphi})]$
can be similarly proved. Since
$\mathtt{B}({S\triangledown\phi})\models\neg\varphi$, it follows from the
semantics of the update operator that for every $w\in[\mathtt{B}({S})]$,
$\min([\phi],\leq^{S}_{w})\cap[\varphi]=\emptyset$. Let
$w^{\prime\prime}\in[\mathtt{B}({S\triangledown\varphi})]$. From the semantics
of the update operator again, there is $w\in[\mathtt{B}({S})]$ s.t.
$w^{\prime\prime}\in\min([\varphi],\leq^{S}_{w})$. By the forth part of
(NatR$\triangledown$), there is
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$ s.t.
$w^{\prime\prime}\in\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})$.
So
$w^{\prime\prime}\in[\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})]$.

  * •

(Lex$\triangledown$) $\Leftrightarrow$ (LexR$\triangledown$).

($\Rightarrow$): Assume that $\triangledown$ satisfies (Lex$\triangledown$).
Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\mathcal{N}\cap[\phi]\neq\emptyset$. We define $\varphi$ as
$\mathtt{Form}({\mathcal{N}})$. Clearly, $\varphi\not\models\neg\phi$. By
(Lex$\triangledown$),
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$. It
directly follows from the semantics of the update operator that for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.

($\Leftarrow$): Assume that $\leq^{S}$ and $\leq^{S\triangledown\phi}$ satisfy
(LexR$\triangledown$). Let $\varphi\not\models\neg\phi$. Clearly,
$[\varphi]\cap[\phi]\neq\emptyset$. By (LexR$\triangledown$), for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$. It
follows from the semantics of the update operator that
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$.

  * •

(Ind$\triangledown$) $\Leftrightarrow$ (IndR$\triangledown$).

($\Rightarrow$): Assume that $\triangledown$ satisfies (Ind$\triangledown$).
Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$ for some
$w\in[\mathtt{B}({S})]$. We define $\varphi$ as
$\mathtt{Form}({\mathcal{N}})$. It follows from the semantics of the update
operator that $\mathtt{B}({S\triangledown\varphi})\not\models\neg\phi$. By
(Ind$\triangledown$),
$\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$. By the
semantics of the update operator again, for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.

($\Leftarrow$): Assume that $\leq^{S}$ and $\leq^{S\triangledown\phi}$ satisfy
(IndR$\triangledown$). Assume that
$\mathtt{B}({S\triangledown\varphi})\not\models\neg\phi$. It follows from the
semantics of the update operator that there is $w\in[\mathtt{B}({S})]$,
$\min([\varphi],\leq^{S}_{w})\cap[\phi]\neq\emptyset$. By
(IndR$\triangledown$), for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min([\varphi],\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.
Hence, $\mathtt{B}({(S\triangledown\phi)\triangledown\varphi})\models\phi$.

∎

Proof of Theorem 11

###### Proof.

  * •

(Lex$\triangledown$) $\Rightarrow$ (Ind$\triangledown$). By Theorem 10, it
suffices to verify that (LexR$\triangledown$) implies (IndR$\triangledown$).
Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$ for some
$w\in[\mathtt{B}({S})]$. Clearly, $\mathcal{N}\cap[\phi]\neq\emptyset$. By
(LexR$\triangledown$), for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.

  * •

(Ind$\triangledown$) $\Rightarrow$ (C3$\triangledown$). By Theorem 5 and
Theorem 10, it suffices to verify that (IndR$\triangledown$) implies
(CR3$\triangledown$). Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\subseteq[\phi]$ holds for every
$w\in[\mathtt{B}({S})]$. Clearly,
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$. By
(IndR$\triangledown$), for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.

  * •

(Ind$\triangledown$) $\Rightarrow$ (C4$\triangledown$). By Theorem 5 and
Theorem 10, it suffices to verify that (IndR$\triangledown$) implies
(CR4$\triangledown$). Let $\mathcal{N}\subseteq\mathcal{M}$ s.t.
$\min(\mathcal{N},\leq^{S}_{w})\cap[\phi]\neq\emptyset$ holds for some
$w\in[\mathtt{B}({S})]$. By (IndR$\triangledown$), for every
$w^{\prime}\in[\mathtt{B}({S\triangledown\phi})]$,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\subseteq[\phi]$.
Therefore,
$\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}})\cap[\phi]\neq\emptyset$.

  * •

(Nat$\triangledown$) $\Rightarrow$ (C2$\triangledown$). By Theorem 5 and
Theorem 10, it suffices to verify that (NatR$\triangledown$) implies
(CR2$\triangledown$). Let $\mathcal{N}\subseteq[\neg\phi]$. It follows that
$\min([\phi],\leq^{S}_{w})\cap\mathcal{N}=\emptyset$ for every
$w\in[\mathtt{B}({S})]$. By (NatR$\triangledown$), we get that

$\bigcup\limits_{w\in[{\mathtt{B}({S})}]}\min(\mathcal{N},\leq^{S}_{w})=\bigcup\limits_{w^{\prime}\in[{\mathtt{B}({S\triangledown\phi})}]}\min(\mathcal{N},\leq^{S\triangledown\phi}_{w^{\prime}}).$

∎

Proof of Theorem 12

###### Proof.

As a corollary of Theorem 11, postulate (Ind$\triangledown$) holds in
$\triangledown_{1}$. By Theorem 10, it suffices to verify that $\leq^{S}$ and
$\leq^{S\triangledown_{1}\phi}$ satisfy (LexR$\triangledown$). Let
$\mathcal{N}\subseteq\mathcal{M}$ s.t. $\mathcal{N}\cap[\phi]\neq\emptyset$.
Let $w^{\prime}\in[\mathtt{B}({S\triangledown_{1}\phi})]$. By the construction
of the operator $\triangledown_{1}$ (cf. Definition 2), $w^{\prime}\in[\phi]$
and for every
$w_{1}\in\mathcal{H}^{w^{\prime},\phi}_{0}\cup\mathcal{H}^{w^{\prime},\phi}_{1}$
and $w_{2}\in\mathcal{H}^{w^{\prime},\phi}_{2}$,
$w_{1}<^{S\triangledown_{1}\phi}_{w^{\prime}}w_{2}$. That is, for every
$w_{1}\in[\phi]$ and $w_{2}\in[\neg\phi]$,
$w_{1}<^{S\triangledown_{1}\phi}_{w^{\prime}}w_{2}$. This, together with
$\mathcal{N}\cap[\phi]\neq\emptyset$, implies that
$\min(\mathcal{N},\leq^{S\triangledown_{1}\phi}_{w^{\prime}})\subseteq[\phi]$.
∎

Proof of Theorem 13

###### Proof.

It directly follows from the fact that (Nat$\triangledown$) entails
(C2$\triangledown$) (cf. Theorem 11) and Theorem 8. ∎