# Who’s the Expert? On Multi-source Belief Change

Joseph Singleton1 Richard Booth1
1Cardiff University
<EMAIL_ADDRESS>
###### Abstract

Consider the following belief change/merging scenario. A group of information
sources gives a sequence of reports about the state of the world at various
instances (e.g. different points in time). The true states at these instances
are unknown to us. The sources have varying levels of expertise, also unknown
to us, and may be knowledgeable on some topics but not others. This may cause
sources to report false statements in areas they lack expertise. What should
we believe on the basis of these reports? We provide a framework in which to
explore this problem, based on an extension of propositional logic with
expertise formulas. This extended language allows us to express beliefs about
the state of the world at each instance, as well as beliefs about the
expertise of each source. We propose several postulates, provide a couple of
families of concrete operators, and analyse these operators with respect to
the postulates.

##  1 Introduction

Consider the following belief change scenario in a hospital. We observe the
results of a blood test of patient 1, confirming condition X. Assuming the
test is reliable, the AGM paradigm (?) tells us how to revise our beliefs in
light of the new information. Dr. A then claims that patient 2 suffers from
the same condition, but Dr. B disagrees. Given that doctors specialise in
different areas and may make mistakes, who should we trust? Since the
_Success_ postulate ($\alpha\in K\ast\alpha$) assumes information is reliable,
we are outside the realm of AGM revision, and must instead apply some form of
_non-prioritised_ revision (?).

Suppose it now emerges that Dr. A had earlier claimed patient 1 did _not_
suffer from condition X, contrary to the test results. We now have reason to
suspect Dr. A may _lack expertise_ on diagnosing X, and may subsequently
revise beliefs about Dr. A’s domain of expertise and the status of patient 2
(e.g. by opting to trust Dr. B instead).

While simple, this example illustrates the key features of the belief change
problem we study: we consider multiple sources, whose expertise is _a priori_
unknown, providing reports on various instances of a problem domain. On the
basis of these reports we form beliefs both about the expertise of the sources
and the state of the world in each instance.

By including a distinguished _completely reliable_ source (the test results in
the example) we extend AGM revision. In some respects we also extend
approaches to non-prioritised revision (e.g. selective revision (?),
credibility-limited revision (?), and trust-based revision (?)), which assume
information about the reliability of sources is known up front. The problem is
also related to _belief merging_ (?) which deals with combining belief bases
from multiple sources; a detailed comparison will be given in Section 7.

Our work is also connected to trust and belief revision, if one interprets
trust as _belief in expertise_. As ? (?) note in recent work, trust and belief
are inexorably linked: we should accept reports from sources we believe are
trustworthy, and we should trust sources whose reports turn out to be
reliable. Trust and belief should also be revised in tandem, so that we may
increase or decrease trust in a source as more reports are received, and
revoke or reinstate previous reports from a source as its perceived
trustworthiness changes.111 This mutual dependence between trust and belief is
also the core idea in _truth discovery_ (?).

To unify the trust and belief aspects, we enrich a propositional language with
_expertise statements_ $E_{i}(\varphi)$, read as “source $i$ has expertise on
$\varphi$”. The output of our belief change problem is then a collection of
belief and knowledge sets in the extended language, describing what we _know_
and _believe_ about the expertise of the sources and the state of the world in
each instance. For example, we should _know_ reports from the reliable source
are true, whereas reports from ordinary sources may only be believed.

Following recent work on logical approaches to expertise (?; ?), we formally
model expertise using a partition of propositional valuations for each source.
Equivalently, each source has an _indistinguishibility equivalence relation_
over valuations. A source is an expert on a proposition $\varphi$ exactly when
they can distinguish every $\varphi$ valuation from every $\neg\varphi$
valuation.222 The relationship between this notion of expertise and _S5
epistemic logic_ is explored in a modal logic setting in ? (?), and we revisit
this connection in Section 7.  As in ? (?), we also use _soundness formulas_
$S_{i}(\varphi)$, which intuitively say that $\varphi$ is true _up the
expertise of_ $i$. For example, if $i$ has expertise on $p$ but not $q$, then
the conjunction $p\land q$ is sound for $i$ whenever $p$ holds, since we can
effectively ignore $q$. Formally, $\varphi$ is sound for $i$ if the “actual”
state of the world is indistinguishable from a $\varphi$ valuation. Note that
expertise does not depend on the “actual” state, whereas soundness does. This
provides a crucial link between expertise and truthfulness of information.

We then make the assumption that _sources only report sound propositions_.
That is, reports are only false due to sources overstepping the bounds of
their expertise. In particular, we assume sources are honest in their reports,
and that experts are always right.

Note that in our introductory example, the fact that we had a report from Dr.
A on patient 1 (together with reliable information on patient 1) was essential
for determining the expertise of Dr. A, and subsequently the status of patient
2\. While the patients are independent, reports on one can cause beliefs about
the other to change, as we update our beliefs about the expertise of the
sources.

In general we consider an arbitrary number of _cases_ , which are seen as
labels for instances of the domain. For example, a crowdsourcing worker may
label multiple images, or a weather forecaster may give predictions for
different locations. Each report in the input to the problem then refers to a
specific case. Via these cases and the presence of the completely reliable
source, we are able to model scenarios where some “ground truth” is available,
listing how often sources have been correct/incorrect on a proposition (e.g.
the _report histories_ of ? (?)). We can also generalise this scenario, e.g.
by having only partial information about “previous” cases.

Throughout the paper we make the assumption that _expertise is fixed across
cases_ : the expertise of a source does not depend on the particular instance
of the domain we look at. For instance, the expertise of Dr. A is the same for
patient 1 as for patient 2. This is a simplifying assumption, and may rule out
certain interpretations of the cases (e.g. if cases represent different points
in time, it would be natural to let expertise evolve over time).

#### Contribution.

Our contributions are threefold. First, we develop a logical framework for
reasoning about the expertise of multiple sources and the state of the world
in multiple cases. Second, we formulate a belief change problem within this
framework, which allows us to explore how trust and belief should interact and
evolve as reports are received from the various sources. Finally, we put
forward several postulates and two concrete classes of operators – with a
representation result for one class – and analyse these operators with respect
to the postulates.

#### Paper outline.

In Section 2 we develop the formal framework. Section 3 introduces the problem
and lists some core postulates. We give two constructions and specific example
operators in Section 4. Section 5 introduces some further postulates
concerning belief change on the basis of one new report. An analogue of
selective revision (?) is presented Section 6. Section 7 discusses related
work, and we conclude in Section 8. Note that some proofs are omitted in the
body of the paper and can be found in the appendix.

##  2 The Framework

Let $\mathcal{S}$ be a finite set of information sources. For convenience, we
assume there is a _completely reliable_ source in $\mathcal{S}$, which we
denote by $\ast$. For example, we can treat our first-hand observations as if
they are reported by $\ast$. Other sources besides $\ast$ will be termed
_ordinary sources_. Let $\mathcal{C}$ be a finite set of _cases_ , which we
interpret as labels for different instances of the problem domain.

#### Syntax.

There are two levels to our formal language. To describe properties of the
world in each case $c\in\mathcal{C}$, we assume a fixed finite set
$\mathcal{P}$ of propositional variables, and let $\mathcal{L}{}_{0}$ denote
the set of propositional formulas generated from $\mathcal{P}$ using the usual
propositional connectives. We use lower case Greek letters ($\varphi$, $\psi$
etc) for formulas in $\mathcal{L}{}_{0}$. The classical logical consequence
operator will be denoted by $\operatorname{Cn}_{0}$, and $\equiv$ denotes
equivalence of propositional formulas.

The extended _language of expertise_ $\mathcal{L}{}$ additionally describes
the expertise of the sources, and is defined by the following grammar:

$\Phi::=\varphi\mid\Phi\land\Phi\mid\neg\Phi\mid E_{i}(\varphi)\mid
S_{i}(\varphi)\\\ $

where $i\in\mathcal{S}$ and $\varphi\in\mathcal{L}{}_{0}$. We introduce
Boolean connectives $\lor$, $\rightarrow$, $\leftrightarrow$ and $\bot$ as
abbreviations. We use upper case Greek letters ($\Phi$, $\Psi$ etc) for
formulas in $\mathcal{L}{}$. For $\Gamma\subseteq\mathcal{L}{}$, we write
$\left[{\Gamma}\right]=\Gamma\cap\mathcal{L}{}_{0}$ for the propositional
formulas in $\Gamma$.

The intuitive reading of $E_{i}(\varphi)$ is source $i$ has expertise on
$\varphi$, i.e., $i$ is able to correctly identify the truth value of
$\varphi$ in any possible state. The intuitive reading of $S_{i}(\varphi)$ is
that $\varphi$ _sound_ for $i$ to report: that $\varphi$ is true up to the
expertise of $i$. That is, the parts of $\varphi$ on which $i$ has expertise
are true. Note that both operators are restricted to propositional formulas,
so we will not consider iterated formulas such as $E_{i}(S_{j}(\varphi))$.

#### Semantics.

Let $\mathcal{V}$ denote the set of propositional valuations over
$\mathcal{P}$. For each $\varphi\in\mathcal{L}{}_{0}$, the set of valuations
making $\varphi$ true is denoted by $\operatorname{mod}_{0}(\varphi)$. A
_world_
$W=\langle{\\{v_{c}\\}_{c\in\mathcal{C}},\\{\Pi_{i}\\}_{i\in\mathcal{S}}}\rangle$
is a possible complete specification of the environment we find ourselves in:

  * •

$v_{c}\in\mathcal{V}$ is the “true” valuation at case $c\in\mathcal{C}$;

  * •

$\Pi_{i}$ is a partition of $\mathcal{V}$ for each $i\in\mathcal{S}$,
representing the “true” expertise of source $i$; and

  * •

$\Pi_{\ast}$ is the unit partition $\\{\\{v\\}\mid v\in\mathcal{V}\\}$.

Let $\mathcal{W}$ denote the set of all worlds. Note that the partition
corresponding to the distinguished source $\ast$ is fixed in all worlds as the
finest possible partition, reflecting the fact that $\ast$ is completely
reliable.

For any partition $\Pi$ and valuation $v$, write $\Pi[v]$ for the unique cell
in $\Pi$ containing $v$. For a set of valuations $U$, write
$\Pi[U]=\bigcup_{v\in U}{\Pi[v]}$. For brevity, we write $\Pi[\varphi]$ for
$\Pi[\operatorname{mod}_{0}(\varphi)]$. Then $\Pi[\varphi]$ is the set of
valuations indistinguishable from a $\varphi$ valuation.

For our belief change problem we will be interested in maintaining a
collection of several belief sets, describing beliefs about each case
$c\in\mathcal{C}$. Towards determining when a world $W$ models such a
collection, we define semantics for $\mathcal{L}{}$ formulas with respect to a
world and a case:

$\begin{array}[]{lll}&W,c\models\varphi&\iff
v_{c}\in\operatorname{mod}_{0}(\varphi)\\\ &W,c\models
E_{i}(\varphi)&\iff\Pi_{i}[\varphi]=\operatorname{mod}_{0}(\varphi)\\\
&W,c\models S_{i}(\varphi)&\iff v_{c}\in\Pi_{i}[\varphi]\end{array}$

where $i\in\mathcal{S}$, $\varphi\in\mathcal{L}{}_{0}$, and the clauses for
conjunction and negation are the expected ones. Since
$\operatorname{mod}_{0}(\varphi)\subseteq\Pi_{i}[\varphi]$ always holds, we
have that $E_{i}(\varphi)$ holds iff there is no $\neg\varphi$ valuation which
is indistinguishable from a $\varphi$ valuation (c.f. ? (?)). Note that since
each source $i$ has only a single partition $\Pi_{i}$ used to interpret the
expertise formulas, the truth value of $E_{i}(\varphi)$ does not depend on the
case $c$. On the other hand, $S_{i}(\varphi)$ holds in case $c$ iff the
$c$-valuation of $W$ is indistinguishable from some model of $\varphi$. That
is, it is consistent with $i$’s expertise that $\varphi$ is true.

Also note that if $\varphi$ is a propositional tautology, $E_{i}(\varphi)$
holds for every source $i$. Thus, all sources are experts on _something_ ,
even if just the tautologies.

######  Example 1.

Let us extend the hospital example from the introduction. Let
$\mathcal{S}=\\{\ast,a,b\\}$ denote the reliable source, Dr. A and Dr. B, and
let $\mathcal{C}=\\{c_{1},c_{2}\\}$ denote patients 1 and 2. Consider
propositional variables $\mathcal{P}=\\{x,y\\}$, standing for condition X and
Y respectively. Suppose that Dr. A has expertise on diagnosing condition Y
only, whereas Dr. B only has expertise on X. For the sake of the example,
suppose that patient 1 suffers from both conditions, and patient 2 suffers
only from condition Y. This situation is modelled by the following world
$W=\langle{\\{v_{c}\\}_{c\in\\{c_{1},c_{2}\\}},\\{\Pi_{i}\\}_{i\in\\{\ast,a,b\\}}}\rangle$:

$\begin{array}[]{cc}v_{c_{1}}=xy;&v_{c_{2}}=\bar{x}y;\\\
\Pi_{a}=xy,\bar{x}y\mid
x\bar{y},\bar{x}\bar{y};&\Pi_{b}=xy,x\bar{y}\mid\bar{x}y,\bar{x}\bar{y}.\end{array}$

We have $W,c\models E_{a}(y)\land E_{b}(x)$ for each $c\in\\{c_{1},c_{2}\\}$.
Also note that $W,c_{1}\models x$ (patient 1 suffers from X), $W,c_{1}\models
S_{a}(\neg x)$ (it is sound for Dr. A to report otherwise; this holds since
$\Pi_{a}[\neg x]=\\{xy,\bar{x}y\\}\cup\\{x\bar{y},\bar{x}\bar{y}\\}\ni
xy=v_{c_{1}}$), but $W,c_{1}\models\neg S_{b}(\neg x)$ (the same formula is
_not_ sound for Dr. B; we have $\Pi_{b}[\neg
x]=\\{\bar{x}y,\bar{x}\bar{y}\\}=\operatorname{mod}_{0}(\neg x)\not\ni
xy=v_{c_{1}}$).

Say $\Phi$ is _valid_ if $W,c\models\Phi$ for all $W\in\mathcal{W}$ and
$c\in\mathcal{C}$. For future reference we collect a list of validities.

######  Proposition 1.

For any $i\in\mathcal{S}$, $c\in\mathcal{C}$ and
$\varphi,\psi\in\mathcal{L}{}_{0}$, the following formulas are valid

  1. 1.

$S_{i}(\varphi)\leftrightarrow S_{i}(\psi)$ and $E_{i}(\varphi)\leftrightarrow
E_{i}(\psi)$, whenever $\varphi\equiv\psi$

  2. 2.

$E_{i}(\varphi)\leftrightarrow E_{i}(\neg\varphi)$ and $E_{i}(\varphi)\land
E_{i}(\psi)\rightarrow E_{i}(\varphi\land\psi)$

  3. 3.

$E_{i}(p_{1})\land\cdots\land E_{i}(p_{k})\rightarrow E_{i}(\varphi)$, where
$p_{1},\ldots,p_{k}$ are the propositional variables appearing in $\varphi$

  4. 4.

$E_{i}(\varphi)\land S_{i}(\varphi)\rightarrow\varphi$, and
$S_{i}(\varphi)\land\neg\varphi\rightarrow\neg E_{i}(\varphi)$

  5. 5.

$S_{i}(\varphi)\land S_{i}(\neg\varphi)\rightarrow\neg E_{i}(\varphi)$

  6. 6.

$S_{\ast}(\varphi)\leftrightarrow\varphi$ and $E_{\ast}(\varphi)$

(1) states syntax-irrelevance properties. (2) says that expertise is symmetric
with respect to negation, and closed under conjunctions. Intuitively, symmetry
means that $i$ is an expert on $\varphi$ if they know _whether or not_
$\varphi$ holds. (3) says that expertise on each propositional variable in
$\varphi$ is sufficient for expertise on $\varphi$ itself. (4) says that, in
the presence of expertise, soundness of $\varphi$ is sufficient for $\varphi$
to in fact be true. (5) says that if both $\varphi$ and $\neg\varphi$ are true
up to the expertise of $i$, then $i$ cannot have expertise on $\varphi$.
Finally, (6) says that the reliable source $\ast$ has expertise on _all_
formulas, and thus $\varphi$ is sound for $\ast$ iff it is true.

#### Case-indexed Collections.

In the remainder of the paper we will be interested in forming beliefs about
each case $c\in\mathcal{C}$. To do so we use collections of belief sets
$G=\\{\Gamma_{c}\\}_{c\in\mathcal{C}}$, with
$\Gamma_{c}\subseteq\mathcal{L}{}$, indexed by cases. Say a world $W$ is a
_model_ of $G$ iff

$W,c\models\Phi\text{ for all }c\in\mathcal{C}\text{ and }\Phi\in\Gamma_{c},$

i.e. iff $W$ satisfies all formulas in $G$ in the relevant case. Let
$\operatorname{mod}(G)$ denote the models of $G$, and say that $G$ is
_consistent_ if $\operatorname{mod}(G)\neq\emptyset$. For $c\in\mathcal{C}$,
define the _$c$ -consequences_

$\operatorname{Cn}_{c}(G)=\\{\Phi\in\mathcal{L}{}\mid\forall
W\in\operatorname{mod}(G),W,c\models\Phi\\}.$

We write $\operatorname{Cn}(G)$ for the collection
$\\{\operatorname{Cn}_{c}(G)\\}_{c\in\mathcal{C}}$.

######  Example 2.

Suppose $\mathcal{C}=\\{c_{1},c_{2},c_{3}\\}$, and define $G$ by
$\Gamma_{c_{1}}=\\{S_{i}(p\land q)\\}$, $\Gamma_{c_{2}}=\\{E_{i}(p)\\}$ and
$\Gamma_{c_{3}}=\\{E_{i}(q)\\}$. Then, since expertise holds independently of
case, any model $W$ of $G$ has $W,c_{1}\models E_{i}(p)\land E_{i}(q)$. By
Proposition 1 part (3), $W,c_{1}\models E_{i}(p\land q)$. Since $W$ satisfies
$\Gamma_{c_{1}}$ in case $c_{1}$, Proposition 1 part (4) gives $W,c_{1}\models
p\land q$. Since $W$ was an arbitrary model of $G$, we have $p\land
q\in\operatorname{Cn}_{c_{1}}(G)$, i.e. $p\land q$ is a $c_{1}$-consequence of
$G$. This illustrates how information about distinct cases can be brought
together to have consequences for other cases.

For two collections $G=\\{\Gamma_{c}\\}_{c\in\mathcal{C}}$,
$D=\\{\Delta_{c}\\}_{c\in\mathcal{C}}$, write $G\sqsubseteq D$ iff
$\Gamma_{c}\subseteq\Delta_{c}$ for all $c$, and let $G\sqcup D$ denote the
collection $\\{\Gamma_{c}\cup\Delta_{c}\\}_{c\in\mathcal{C}}$. With this
notation, the case-indexed consequence operator satisfies analogues of the
Tarskian consequence properties.333 That is,  (i)
$G\sqsubseteq\operatorname{Cn}(G)$,  (ii) $G\sqsubseteq D$implies
$\operatorname{Cn}(G)\sqsubseteq\operatorname{Cn}(D)$, and  (iii)
$\operatorname{Cn}(\operatorname{Cn}(G))=\operatorname{Cn}(G)$.

Say a collection $G$ is _closed_ if $\operatorname{Cn}(G)=G$. Closed
collections provide an idealised representation of beliefs, which will become
useful later on. For instance, when $G$ is closed we have
$E_{i}(\varphi)\in\Gamma_{c}\text{ iff }E_{i}(\varphi)\in\Gamma_{d}$ for all
$c,d\in\mathcal{C}$; i.e. expertise statements are either present for all
cases or for none. We also have
$\operatorname{Cn}_{0}\left[{\Gamma_{c}}\right]=\left[{\Gamma_{c}}\right],$
i.e. the propositional parts of $G$ are (classically) closed.

In propositional logic, $\operatorname{mod}_{0}$ is a 1-to-1 correspondence
between closed sets of formulas and sets of valuations. This is not so in our
setting, since some subsets of $\mathcal{W}$ do not arise as the models of any
collection. Instead, we have a 1-to-1 correspondence into a restricted
collection of sets of worlds. Borrowing the terminology of ? (?), say a set of
worlds $S\subseteq\mathcal{W}$ is _elementary_ if ${S=\operatorname{mod}(G)}$
for some collection $G=\\{\Gamma_{c}\\}_{c\in\mathcal{C}}$.444 Non-elementary
sets can also exist for weaker logics (such as Horn logic (?)) which lack the
syntactic expressivity to identify all sets of models. In our framework,
$\mathcal{C}$-indexed collections are not expressive enough to specify
_combinations of valuations_ , since each $\Gamma_{c}$ only says something
about the valuation for $c$.

Elementariness is characterised by a certain closure condition. Say that two
worlds $W,W^{\prime}$ are _partition-equivalent_ if
$\Pi^{W}_{i}=\Pi^{W^{\prime}}_{i}$ for all sources $i$, and say $W$ is a
_valuation combination_ from a set $S\subseteq\mathcal{W}$ if for all cases
$c$ there is $W_{c}\in S$ such that $v^{W}_{c}=v^{W_{c}}_{c}$. Then a set is
elementary iff it is closed under valuation combinations of partition-
equivalent worlds.

######  Proposition 2.

$S\subseteq\mathcal{W}$ is elementary if and only if the following condition
holds: for all $W\in\mathcal{W}$ and $W_{1},W_{2}\in S$, if $W$ is partition-
equivalent to both $W_{1},W_{2}$ and $W$ is a valuation combination from
$\\{W_{1},W_{2}\\}$, then $W\in S$.

##  3 The Problem

With the framework set out, we can formally define the problem. We seek an
operator with the following behaviour:

  * •

Input: A sequence of reports $\sigma$, where each report is a triple
$\langle{i,c,\varphi}\rangle\in\mathcal{S}\times\mathcal{C}\times\mathcal{L}{}_{0}$
and $\varphi\not\equiv\bot$. Such a report represents that source $i$ reports
$\varphi$ to hold in case $c$. Note that we only allow sources to make
_propositional_ reports.

  * •

Output: A pair $\langle{B^{\sigma},K^{\sigma}}\rangle$, where
$B^{\sigma}=\\{B^{\sigma}_{c}\\}_{c\in\mathcal{C}}$ is a collection of _belief
sets_ $B^{\sigma}_{c}\subseteq\mathcal{L}{}$ and
$K^{\sigma}=\\{K^{\sigma}_{c}\\}_{c\in\mathcal{C}}$ is a collection of
_knowledge sets_ $K^{\sigma}_{c}\subseteq\mathcal{L}{}$.

###  3.1 Basic Postulates

We immediately narrow the scope of operators under consideration by
introducing some basic postulates which are expected to hold. In what follows,
say a sequence $\sigma$ is _$\ast$ -consistent_ if for each $c\in\mathcal{C}$
the set
$\\{\varphi\mid\langle{\ast,c,\varphi}\rangle\in\sigma\\}\subseteq\mathcal{L}{}_{0}$
is classically consistent. Write $G^{\sigma}_{\mathsf{snd}}$ for the
collection with
$(G^{\sigma}_{\mathsf{snd}})_{c}=\\{S_{i}(\varphi)\mid\langle{i,c,\varphi}\rangle\in\sigma\\}$,
i.e. the collection of soundness statements corresponding to the reports in
$\sigma$.

######  _Closure_

$B^{\sigma}=\operatorname{Cn}(B^{\sigma})$ and
$K^{\sigma}=\operatorname{Cn}(K^{\sigma})$

######  _Containment_

$K^{\sigma}\sqsubseteq B^{\sigma}$

######  _Consistency_

If $\sigma$ is $\ast$-consistent, $B^{\sigma}$ and $K^{\sigma}$ are consistent

######  _Soundness_

If $\langle{i,c,\varphi}\rangle\in\sigma$, then $S_{i}(\varphi)\in
K^{\sigma}_{c}$

######  _K-bound_

$K^{\sigma}\sqsubseteq\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup
K^{\emptyset})$

######  _Prior-Extension_

$K^{\emptyset}\sqsubseteq K^{\sigma}$

######  _Rearrangement_

If $\sigma$ is a permutation of $\rho$, then $B^{\sigma}=B^{\rho}$ and
$K^{\sigma}=K^{\rho}$

######  _Equivalence_

If $\varphi\equiv\psi$ then
$B^{\sigma\cdot\langle{i,c,\varphi}\rangle}=B^{\sigma\cdot\langle{i,c,\psi}\rangle}$
and
$K^{\sigma\cdot\langle{i,c,\varphi}\rangle}=K^{\sigma\cdot\langle{i,c,\psi}\rangle}$

_Closure_ says that the belief and knowledge collections are closed under
logical consequence. In light of earlier remarks, this implies that the
propositional belief sets $\left[{B^{\sigma}_{c}}\right]$ are closed under
(propositional) consequence, and that $E_{i}(\varphi)\in B^{\sigma}_{c}$ iff
$E_{i}(\varphi)\in B^{\sigma}_{d}$. _Containment_ says that everything which
is known is also believed. _Consistency_ ensures the output is always
consistent, provided we are not in the degenerate case where $\ast$ gives
inconsistent reports. _Soundness_ says we _know_ that all reports are sound in
their respective cases. This formalises our assumption that sources are
_honest_ , i.e. that false reports only arise due to lack of expertise. By
Proposition 1 part (4) it also implies _experts are always right_ : if a
source has expertise on their report then it must be true. While _Soundness_
places a lower bound on knowledge, _K-bound_ places an upper bound: knowledge
cannot go beyond the soundness statements corresponding to the reports in
$\sigma$ together with the prior knowledge $K^{\emptyset}$. That is, from the
point view of knowledge, a new report of $\langle{i,c,\varphi}\rangle$ only
allows us to learn $S_{i}(\varphi)$ in case $c$ (and to combine this with
other reports and prior knowledge). Note that the analogous property for
belief is _not_ desirable: we want to be more liberal when it comes to
beliefs, and allow for _defeasible inferences_ going beyond the mere fact that
reports are sound. _Prior-Extension_ says that knowledge after a sequence
$\sigma$ extends the prior knowledge on the empty sequence $\emptyset$.
_Rearrangement_ says that the order in which reports are received is
irrelevant. This can be justified on the basis that we are reasoning about
_static worlds_ for each case $c$, so that there is no reason to see more
“recent” reports as any more or less important or truthful than earlier
ones.555This argument is from (?). Consequently, we can essentially view the
input as a _multi-set_ of belief sets – one for each source – bringing us
close to the setting of belief merging. This postulate also appears as the
commutativity postulate (Com) in the work of ? (?). Finally, _Equivalence_
says that the syntactic form of reports is irrelevant.

Taking all the basic postulates together, the knowledge component $K^{\sigma}$
is fully determined once $K^{\emptyset}$ is chosen.

######  Proposition 3.

Suppose an operator satisfies the basic postulates. Then

  1. 1.

$K^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup K^{\emptyset})$

  2. 2.

$K^{\emptyset}=\operatorname{Cn}(\emptyset)$ iff
$K^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})$ for all $\sigma$.

The choice of $K^{\emptyset}$ depends on the scenario one wishes to model.
While $\operatorname{Cn}(\emptyset)$ is a sensible choice if the sequence
$\sigma$ is all we have to go on, we allow
$K^{\emptyset}\neq\operatorname{Cn}(\emptyset)$ in case _prior knowledge_ is
available (for example, the expertise of particular sources may be known ahead
of time).

Another important property of knowledge, which follows from the basic
postulates, says that _knowledge is monotonic_ : knowledge after receiving
$\sigma$ and $\rho$ together is just the case-wise union of $K^{\sigma}$ and
$K^{\rho}$.

######  _K-conjunction_

$K^{\sigma\cdot\rho}=\operatorname{Cn}(K^{\sigma}\sqcup K^{\rho})$

_K-conjunction_ reflects the idea that one should be cautious when it comes to
knowledge: a formula should only be accepted as known if it won’t be given up
in light of new information.

######  Proposition 4.

Any operator satisfying the basic postulates satisfies _K-conjunction_.

The postulates also imply some useful properties linking _trust_ (seen as
belief in expertise) and _belief/knowledge_.

######  Proposition 5.

Suppose an operator satisfies the basic postulates. Then

  1. 1.

If $\varphi\in K^{\sigma}_{c}$ and $\neg\psi\in\operatorname{Cn}_{0}(\varphi)$
then $\neg E_{i}(\psi)\in K^{\sigma\cdot\langle{i,c,\psi}\rangle}_{c}$.

  2. 2.

If $\langle{i,c,\varphi}\rangle\in\sigma$ and $E_{i}(\varphi)\in
B^{\sigma}_{c}$ then $\varphi\in B^{\sigma}_{c}$.

(1) expresses how knowledge can negatively affect trust: we should distrust
sources who make reports we know to be false. (2) expresses how trust affects
belief: we should believe reports from trusted sources. It can also be seen as
a form of _success_ for ordinary sources, and implies AGM success when
$i=\ast$ (by Proposition 1 part (6) and _Closure_). We illustrate the basic
postulates by formalising the introductory hospital example.

######  Example 3.

Set $\mathcal{S},\mathcal{C}$ and $\mathcal{P}$ as in Example 1, and consider
the sequence

$\sigma=(\langle{\ast,c_{1},x}\rangle,\langle{a,c_{2},x}\rangle,\langle{b,c_{2},\neg
x}\rangle,\langle{a,c_{1},\neg x}\rangle).$

What do we know on the basis of this sequence, assuming the basic postulates?
First note that by _Soundness_ , Proposition 1 part (6) and _Closure_ , the
report from $\ast$ gives $x\in K^{\sigma}_{c_{1}}$, i.e. reliable reports are
known. _Soundness_ also gives $S_{a}(x)\land S_{b}(\neg x)\in
K^{\sigma}_{c_{2}}$. Combined with Proposition 1 parts (2), (4) and _Closure_
, this yields $\neg(E_{a}(x)\land E_{b}(x))\in K^{\sigma}_{c}$ for all $c$,
formalising the intuitive idea that Drs. A and B cannot both be experts on X,
since they give conflicting reports. Considering the final report from $a$, we
get $x\land S_{a}(\neg x)\in K^{\sigma}_{c_{1}}$, and thus $\neg E_{a}(x)\in
K^{\sigma}_{c}$ by _Closure_. So in fact Dr. A is known to be a non-expert on
X.

What about beliefs? The basic postulates do not require beliefs to go beyond
knowledge, so we cannot say much in general. An “optimistic” operator,
however, may opt to believe that sources are experts unless we know otherwise,
and thus maximise the information that can be (defeasibly) inferred from the
sequence (in the next section we will introduce concrete operators obeying
this principle). In this case we may believe that at least one source has
expertise on $x$ (i.e. $E_{a}(x)\lor E_{b}(x)\in B^{\sigma}_{c}$). Combined
with $\neg E_{a}(x)\in K^{\sigma}_{c}$, _Closure_ and _Containment_ , we get
$E_{b}(x)\in B^{\sigma}_{c_{2}}$. Symmetry of expertise together with
Proposition 5 part (2) then gives $\neg x\in B^{\sigma}_{c_{2}}$, i.e. we
trust Dr. B in the example and believe patient 2 does not suffer from
condition X.

###  3.2 Model-based Operators

While an operator is a purely syntactic object, it will be convenient to
specify $K^{\sigma}$ and $B^{\sigma}$ in semantic terms by selecting a set of
_possible_ and _most plausible_ worlds for each sequence $\sigma$. We call
such operators _model-based_.

######  Definition 1.

An operator is _model-based_ if for every $\sigma$ there are sets
$\mathcal{X}_{\sigma},\mathcal{Y}_{\sigma}\subseteq\mathcal{W}$ such that  (i)
$\mathcal{X}_{\sigma}\supseteq\mathcal{Y}_{\sigma}$;  (ii) $\Phi\in
K^{\sigma}_{c}$iff $W,c\models\Phi$ for all $W\in\mathcal{X}_{\sigma}$; and
(iii) $\Phi\in B^{\sigma}_{c}$iff $W,c\models\Phi$ for all
$W\in\mathcal{Y}_{\sigma}$.

In other words, $K^{\sigma}_{c}$ (resp., $B^{\sigma}_{c}$) contains the
formulas which hold at case $c$ in _all worlds_ in $\mathcal{X}_{\sigma}$
(resp., $\mathcal{Y}_{\sigma})$. It follows from the relevant definitions that
$\mathcal{X}_{\sigma}\subseteq\operatorname{mod}(K^{\sigma})$, and equality
holds if and only if $\mathcal{X}_{\sigma}$ is elementary (similarly for
$\mathcal{Y}^{\sigma}$ and $B^{\sigma}$). Model-based operators are
characterised by our first two basic postulates.

######  Theorem 1.

An operator satisfies _Closure_ and _Containment_ if and only if it is model-
based.

Since we take _Closure_ and _Containment_ to be fundamental properties, all
operators we consider from now on will be model-based. We introduce our first
concrete operator.

######  Definition 2.

Define the model-based operator $\mathsf{weak\text{-}mb}$ by

$\mathcal{X}_{\sigma}=\mathcal{Y}_{\sigma}=\\{W\mid W,c\models
S_{i}(\varphi)\text{ for all }\langle{i,c,\varphi}\rangle\in\sigma\\}.$

That is, the possible worlds $\mathcal{X}_{\sigma}$ are exactly those
satisfying the soundness constraint for each report in $\sigma$, i.e. false
reports are only due to lack of expertise of the corresponding source.
Syntactically,
$K^{\sigma}=B^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})$.

Clearly $\mathsf{weak\text{-}mb}$ satisfies _Soundness_ , and one can show
that it satisfies all of the basic postulates of Section 3.1.666 For
_Consistency_ , note that for any $\ast$-consistent sequence $\sigma$ one can
form a world $W$ such that $v_{c}$ is a model of all reports from $\ast$ at
case $c$, and $\Pi_{i}=\\{\mathcal{V}\\}$ for all $i\neq\ast$. This satisfies
all the soundness constraints, so
$W\in\mathcal{X}_{\sigma}=\mathcal{Y}_{\sigma}$. In fact, it is the _weakest_
operator satisfying _Closure_ , _Containment_ and _Soundness_ , in that for
any other operator
$\sigma\mapsto\langle{\hat{B}^{\sigma},\hat{K}^{\sigma}}\rangle$ with these
properties we have $B^{\sigma}\sqsubseteq\hat{B}^{\sigma}$ and
$K^{\sigma}\sqsubseteq\hat{K}^{\sigma}$ for any $\sigma$.

######  Example 4.

Consider $\mathsf{weak\text{-}mb}$ applied to the sequence
$\sigma=(\langle{\ast,c,p}\rangle,\langle{i,c,\neg p\land q}\rangle)$. By
_Soundness_ , _Closure_ and the validities from Proposition 1, we have $p\in
K^{\sigma}_{c}$ and $\neg E_{i}(p)\in K^{\sigma}_{c}$. In fact, by _Closure_ ,
we have $\neg E_{i}(p)\in K^{\sigma}_{d}$ for all cases $d$. However, we
cannot say much about $q$: neither $q$, $\neg q$, $E_{i}(q)$ nor $\neg
E_{i}(q)$ are in $B^{\sigma}_{c}=K^{\sigma}_{c}$.

##  4 Constructions

For model-based operators in Definition 1, the sets $\mathcal{X}_{\sigma}$ and
$\mathcal{Y}_{\sigma}$ – which determine knowledge and belief – can depend on
$\sigma$ in a completely arbitrary manner. This lack of structure leads to
very wide class of operators, and one cannot say much about them in general
beyond the satisfaction of _Closure_ and _Containment_. In this section we
specialise model-based operators by providing two constructions.

###  4.1 Conditioning Operators

Intuitively, $\mathcal{Y}_{\sigma}$ is supposed to represent the _most
plausible_ worlds among the possible worlds in $\mathcal{X}_{\sigma}$. This
suggests the presence of a _plausibility ordering_ on $\mathcal{X}_{\sigma}$,
which is used to select $\mathcal{Y}_{\sigma}$. For our first construction we
take this approach: we condition a fixed plausibility total preorder777 A
total preorder is a reflexive, transitive and total relation.  on the
knowledge $\mathcal{X}_{\sigma}$, and obtain $\mathcal{Y}_{\sigma}$ by
selecting the minimal (i.e. most plausible) worlds.

######  Definition 3.

An operator is a _conditioning operator_ if there is a total preorder $\leq$
on $\mathcal{W}$ and a mapping
$\sigma\mapsto\langle{\mathcal{X}_{\sigma},\mathcal{Y}_{\sigma}}\rangle$ as in
Definition 1 such that
$\mathcal{Y}_{\sigma}=\min_{\leq}{\mathcal{X}_{\sigma}}$ for all $\sigma$.

Note that $\leq$ is independent of $\sigma$: it is fixed before receiving any
reports. All conditioning operators are model-based by definition. Clearly
$\mathcal{Y}_{\sigma}$ is determined by $\mathcal{X}_{\sigma}$ and the
plausibility order, so that to define a conditioning operator it is enough to
specify $\leq$ and the mapping $\sigma\mapsto\mathcal{X}_{\sigma}$. Write
$W\simeq W^{\prime}$ iff both $W\leq W^{\prime}$ and $W^{\prime}\leq W$. We
now present examples of how such an ordering can be defined.

######  Definition 4.

Define the conditioning operator $\mathsf{var\text{-}based\text{-}cond}$ by
setting $\mathcal{X}_{\sigma}$ in the same way as $\mathsf{weak\text{-}mb}$ in
Definition 2, and $W\leq W^{\prime}$ iff $r(W)\leq r(W^{\prime})$, where

$r(W)=-\sum_{i\in\mathcal{S}}\left|\left\\{p\in\mathcal{P}\mid\Pi^{W}_{i}[p]=\operatorname{mod}_{0}(p)\right\\}\right|.$

$\mathsf{var\text{-}based\text{-}cond}$ aims to trust each source on _as many
propositional variables_ as possible. One can check that
$\mathsf{var\text{-}based\text{-}cond}$ satisfies the basic postulates.

######  Example 5.

Revisiting the sequence $\sigma=(\langle{\ast,c,p}\rangle,\langle{i,c,\neg
p\land q}\rangle)$ from Example 4 with
$\mathsf{var\text{-}based\text{-}cond}$, the knowledge set $K^{\sigma}_{c}$ is
the same as before, but we now have $q\land E_{i}(q)\in B^{\sigma}_{c}$. This
reflects the “credulous” behaviour of the ranking $\leq$: while it is not
possible to believe $i$ is an expert on $p$, we should believe they _are_ an
expert on $q$ so long as this does not conflict with soundness. For the
propositional beliefs generally, we have
$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(p\land q)$. That is,
$\mathsf{var\text{-}based\text{-}cond}$ takes the $q$ part of the report from
$i$ (on which $i$ is credulously trusted) while ignoring the $\neg p$ part
(which is false due to report from $\ast$).

######  Definition 5.

Define a conditioning operator $\mathsf{part\text{-}based\text{-}cond}$ with
$\mathcal{X}_{\sigma}$ as for $\mathsf{var\text{-}based\text{-}cond}$, and
$\leq$ defined by the ranking function

$r(W)=-\sum_{i\in\mathcal{S}}{|\Pi^{W}_{i}|}.$

$\mathsf{part\text{-}based\text{-}cond}$ aims to maximise the _number of
cells_ in the sources’ partitions, and thereby maximise the number of
propositions on which they have expertise. Unlike
$\mathsf{var\text{-}based\text{-}cond}$, the propositional variables play no
special role. As expected, $\mathsf{part\text{-}based\text{-}cond}$ satisfies
the basic postulates.

######  Example 6.

Applying $\mathsf{part\text{-}based\text{-}cond}$ to $\sigma$ from Examples 4
and 5, we no longer extract $q$ from the report of $i$: $q\notin
B^{\sigma}_{c}$ and $E_{i}(q)\notin B^{\sigma}_{c}$. Instead, we have
$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(p)$, and $E_{i}(p\lor
q)\in B^{\sigma}_{c}$.

Note that both $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$ are based on the general principle of
maximising the expertise of sources, subject to the constraint that all
reports are sound. This intuition is formalised by the following postulate for
conditioning operators. In what follows, write $W\preceq W^{\prime}$ iff
$\Pi^{W}_{i}$ refines $\Pi^{W^{\prime}}_{i}$ for all $i\in\mathcal{S}$, i.e.
if all sources have broadly more expertise in $W$ than in $W^{\prime}$.888
$\Pi$ refines $\Pi^{\prime}$ if $\forall A\in\Pi$, $\exists B\in\Pi^{\prime}$
such that $A\subseteq B$.

######  _Refinement_

If $W\preceq W^{\prime}$ then $W\leq W^{\prime}$

Since $\preceq$ is only a partial order on $\mathcal{W}$ there are many
possible total extensions; $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$ provide two specific examples.

We now turn to an axiomatic characterisation of conditioning operators. Taken
with the basic postulates from Section 3.1, conditioning operators can be
characterised using an approach similar to that of ? (?) in their account of
_generalised AGM belief revision_.999 Note that while the result is similar,
our framework is not an instance of theirs.  This involves a technical
property ? call _Acyc_ , which finds its roots in the _Loop_ property of ?
(?).

######  _Duplicate-removal_

If $\rho_{1}=\sigma\cdot\langle{i,c,\varphi}\rangle$ and
$\rho_{2}=\rho_{1}\cdot\langle{i,c,\varphi}\rangle$ then
$B^{\rho_{1}}=B^{\rho_{2}}$ and $K^{\rho_{1}}=K^{\rho_{2}}$

######  _Conditional-consistency_

If $K^{\sigma}$ is consistent then so is $B^{\sigma}$

######  _Inclusion-vacuity_

$B^{\sigma\cdot\rho}\sqsubseteq\operatorname{Cn}(B^{\sigma}\sqcup K^{\rho})$,
with equality if $B^{\sigma}\sqcup K^{\rho}$ is consistent

######  _Acyc_

If $\sigma_{0},\ldots,\sigma_{n}$ are such that $K^{\sigma_{j}}\sqcup
B^{\sigma_{j+1}}$ is consistent for all $0\leq j<n$ and $K^{\sigma_{n}}\sqcup
B^{\sigma_{0}}$ is consistent, then $K^{\sigma_{0}}\sqcup B^{\sigma_{n}}$ is
consistent

_Inclusion-vacuity_ is so-named since it is analogous to the combination of
_Inclusion_ and _Vacuity_ from AGM revision, if one informally views
$B^{\sigma\cdot\rho}$ as the revision of $B^{\sigma}$ by $K^{\rho}$.
_Conditional-consistency_ is another consistency postulate, which follows from
_Consistency_ , _Closure_ and _Soundness_. _Acyc_ is the analogue of the
postulate of ?, which rules out cycles in the plausibility order constructed
in the representation result.

As with the result of ?, a technical condition beyond Definition 3 is required
to obtain the characterisation: say that a conditioning operator is
_elementary_ if for each $\sigma$ the sets of worlds $\mathcal{X}_{\sigma}$
and $\mathcal{Y}_{\sigma}=\min_{\leq}\mathcal{X}_{\sigma}$ are
elementary.101010 Equivalently, there is a total preorder $\leq$ such that
$\operatorname{mod}(B^{\sigma})=\min_{\leq}\operatorname{mod}(K^{\sigma})$ for
all $\sigma$.

######  Theorem 2.

Suppose an operator satisfies the basic postulates of Section 3.1.111111
Strictly speaking, we only need _Closure_ , _Containment_ , _K-conjunction_ ,
_Equivalence_ and _Rearrangement_.  Then it is an elementary conditioning
operator if and only if it satisfies _Duplicate-removal_ , _Conditional-
consistency_ , _Inclusion-vacuity_ and _Acyc_.

The proof roughly follows the lines of Theorem 4.9 in (?), although some
differences arise due to the form of our input as finite sequences of reports.
We note that while the requirement that $\mathcal{X}_{\sigma}$ and
$\mathcal{Y}_{\sigma}$ are elementary is a technical condition,121212
_Inclusion-vacuity_ may fail for non-elementary conditioning.  the
characterisation in Proposition 2 implies a simple sufficient condition for
elementariness.

######  Proposition 6.

Suppose $\leq$ is such that $W\simeq W^{\prime}$ whenever $W$ and $W^{\prime}$
are partition-equivalent. Then $\min_{\leq}{S}$ is elementary for any
elementary set $S\subseteq\mathcal{W}$.

Proposition 6 implies that $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$ are elementary. Indeed, for both
operators $\mathcal{X}_{\sigma}=\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$
so is elementary by definition. Since the ranking $\leq$ for each operator
only depends on the partitions of worlds,
$\mathcal{Y}_{\sigma}=\min_{\leq}{\mathcal{X}_{\sigma}}$ is elementary also.

###  4.2 Score-based operators

The fact that the plausibility order $\leq$ of a conditioning operator is
fixed may be too limiting. For example, consider

$\sigma=(\langle{i,c,p}\rangle,\langle{j,c,\neg
p}\rangle,\langle{i,d,p}\rangle).$

If one sets $\mathcal{X}_{\sigma}$ to satisfy the soundness constraints (i.e.
as in $\mathsf{weak\text{-}mb}$), there is a possible world
$W_{1}\in\mathcal{X}_{\sigma}$ with $W_{1},d\models\neg E_{i}(p)\land
E_{j}(p)\land\neg p$ (i.e. $W_{1}$ sides with source $j$ and $p$ is false at
$d$) and another world $W_{2}\in\mathcal{X}_{\sigma}$ with $W_{2},d\models
E_{i}(p)\land\neg E_{j}(p)\land p$ (i.e. $W_{2}$ sides with source $i$).
Appealing to symmetry, one may argue that neither world is _a priori_ more
plausible than the other, so any fixed plausibility order should have
$W_{1}\simeq W_{2}$. If these worlds are maximally plausible (e.g. if taking
the “optimistic” view outlined in Example 3), conditioning gives $p\notin
B^{\sigma}_{d}$ and $\neg p\notin B^{\sigma}_{d}$. However, there is an
argument that $W_{2}$ should be considered more plausible than $W_{1}$ _given
the sequence $\sigma$_, since $W_{2}$ validates the final report
$\langle{i,d,p}\rangle$ whereas $W_{1}$ does not. Consequently, there is an
argument that we should in fact have $p\in B^{\sigma}_{d}$.131313At the very
least, the case $p\in B^{\sigma}_{d}$ should not be _excluded_. This shows
that we need the plausibility order to be responsive to the input sequence for
adequate belief change.141414 In Section 5 we make this argument more precise
by providing an impossibility result which shows conditioning operators with
some basic properties cannot accept $p$ in sequences such as this.

As a result of this discussion, we look for operators whose plausibility
ordering can depend on $\sigma$. One approach to achieve this in a controlled
way is to have a ranking for each _report_ $\langle{i,c,\varphi}\rangle$, and
combine these to construct a ranking for each sequence $\sigma$. We represent
these rankings by _scoring functions_ , and call the resulting operators
_score-based_.

######  Definition 6.

An operator is _score-based_ if there is a mapping
$\sigma\mapsto\langle{\mathcal{X}_{\sigma},\mathcal{Y}_{\sigma}}\rangle$ as in
Definition 1 and functions $r_{0}:\mathcal{W}\to\mathbb{N}\cup\\{\infty\\}$,
$d:\mathcal{W}\times(\mathcal{S}\times\mathcal{C}\times\mathcal{L}{}_{0})\to\mathbb{N}\cup\\{\infty\\}$
such that $\mathcal{X}_{\sigma}=\\{W\mid r_{\sigma}(W)<\infty\\}$ and
$\mathcal{Y}_{\sigma}=\operatorname{argmin}_{W\in\mathcal{X}_{\sigma}}{r_{\sigma}(W)}$,
where

$r_{\sigma}(W)=r_{0}(W)+\sum\nolimits_{\langle{i,c,\varphi}\rangle\in\sigma}{d(W,\langle{i,c,\varphi}\rangle)}.$

Here $r_{0}(W)$ is the _prior implausibility score_ of $W$, and
$d(W,\langle{i,c,\varphi}\rangle)$ is the _disagreement score_ for world $W$
and $\langle{i,c,\varphi}\rangle$. The set of most plausible worlds
$\mathcal{Y}_{\sigma}$ consists of those $W$ which minimise the sum of the
prior implausibility and the total disagreement with $\sigma$. Note that by
summing the scores of each report $\langle{i,c,\varphi}\rangle$ with equal
weight, we treat each report independently. Score-based operators generalise
elementary conditioning operators with _K-conjunction_.

######  Proposition 7.

Any elementary conditioning operator satisfying _K-conjunction_ is score-
based.

We now give a concrete example.

######  Definition 7.

Define a score-based operator $\mathsf{excess\text{-}min}$ by setting
$r_{0}(W)=0$ and

$d(W,\langle{i,c,\varphi}\rangle)=\begin{cases}|\Pi^{W}_{i}[\varphi]\setminus\operatorname{mod}_{0}(\varphi)|,&W,c\models
S_{i}(\varphi)\\\ \infty,&\text{ otherwise. }\end{cases}$

The set of possible worlds $\mathcal{X}_{\sigma}$ is the same as for the
earlier operators. All worlds are _a priori_ equiplausible according to
$r_{0}$. The disagreement score $d$ is defined as the number of propositional
valuations in the “excess” of $\Pi^{W}_{i}[\varphi]$ which are not models of
$\varphi$, i.e. the number of $\neg\varphi$ valuations which are
indistinguishable from some $\varphi$ valuation. The intuition here is that
_sources tend to only report formulas on which they have expertise_. The
minimum score 0 is attained exactly when $i$ has expertise on $\varphi$; other
worlds are ordered by how much they deviate from this ideal.

One can verify that $\mathsf{excess\text{-}min}$ satisfies the basic
postulates of Section 3.1. It can also be seen that $\mathcal{X}_{\sigma}$ and
$\mathcal{Y}_{\sigma}$ are elementary, and $\mathsf{excess\text{-}min}$ fails
_Duplicate-removal_ and _Inclusion-vacuity_. It follows from Theorem 2 that
$\mathsf{excess\text{-}min}$ is _not_ a conditioning operator.

######  Example 7.

To illustrate the differences between $\mathsf{excess\text{-}min}$ and
conditioning, consider a more elaborate version of the example given at the
start of this Section:

$\sigma=(\langle{i,c,p\rightarrow q}\rangle,\langle{j,c,p\rightarrow\neg
q}\rangle,\langle{\ast,c,p}\rangle,\langle{i,d,p}\rangle,\langle{i,d,q}\rangle).$

Here the reports of $i$ and $j$ in case $c$ are consistent, but inconsistent
when taken with the reliable information $p$ from $\ast$. Should we believe
$q$ or $\neg q$? Both our conditioning operators
$\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$ decline to decide, and have
$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(p)$. However, since
$\mathsf{excess\text{-}min}$ takes into account each report in the sequence,
the fact that $i$ reports both $p$ and $q$ in case $d$ leads to $E_{i}(p)\land
E_{i}(q)\in B^{\sigma}_{c}$. This gives $E_{i}(p\rightarrow q)\in
B^{\sigma}_{c}$ by Proposition 1 part (3), so we can make use of the report
from $i$ in case $c$: we have
$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(p\land q)$. This example
shows that score-based operators can be _more credulous_ than conditioning
operators (e.g. we can believe $E_{i}(p)$ when $i$ reports $p$), and can
consequently hold stronger propositional beliefs.

##  5 One-step Revision

The postulates of Section 3.1 only set out very basic requirements for an
operator. In this section we introduce some more demanding postulates which
address how beliefs should change when a sequence $\sigma$ is extended by a
new report $\langle{i,c,\varphi}\rangle$. First, we address how propositional
beliefs should be affected by reliable information.

######  _AGM- $\ast$_

For any $\sigma$ and $c\in\mathcal{C}$ there is an AGM operator $\star$ for
$\left[{B^{\sigma}_{c}}\right]$ such that
$\left[{B^{\sigma\cdot\langle{\ast,c,\varphi}\rangle}_{c}}\right]=\left[{B^{\sigma}_{c}}\right]\star\varphi$
whenever $\neg\varphi\notin K^{\sigma}_{c}$

_AGM- $\ast$_ says that receiving information from the reliable source $\ast$
acts in accordance with the well-known AGM postulates (?) for propositional
belief revision (provided we are not in the degenerate case where the new
report $\varphi$ was already _known_ to be false). Since AGM revision
operators are characterised by total preorders over valuations (?; ?), it is
no surprise that our order-based constructions are consistent with _AGM-
$\ast$_.

######  Proposition 8.

$\mathsf{var\text{-}based\text{-}cond}$,
$\mathsf{part\text{-}based\text{-}cond}$ and $\mathsf{excess\text{-}min}$
satisfy _AGM- $\ast$_.

Thus, we do indeed extend AGM revision in the case of reliable information.
What about non-reliable information? First note that the analogue of _AGM-
$\ast$_ for ordinary sources $i\neq\ast$ is _not_ desirable. In particular, we
should not have the _Success_ postulate:

$\varphi\in B^{\sigma\cdot\langle{i,c,\varphi}\rangle}_{c}.$

Indeed, the sequence in Example 4 with $\varphi=\neg p\land q$ already shows
that _Success_ would conflict with the basic postulates. However, there are
weaker modifications of _Success_ which may be more appropriate. We consider
two such postulates.

######  _Cond-success_

If $E_{i}(\varphi)\in B^{\sigma}_{c}$ and $\neg\varphi\notin B^{\sigma}_{c}$,
then $\varphi\in B^{\sigma\cdot\langle{i,c,\varphi}\rangle}_{c}$

######  _Strong-cond-success_

If $\neg(E_{i}(\varphi)\land\varphi)\notin B^{\sigma}_{c}$, then $\varphi\in
B^{\sigma\cdot\langle{i,c,\varphi}\rangle}_{c}$

_Cond-success_ says that if $i$ is deemed an expert on $\varphi$, which is
consistent with current beliefs, then $\varphi$ is accepted after $i$ reports
it. That is, the acceptance of $\varphi$ is _conditional_ on prior beliefs
about the expertise of $i$ (on $\varphi$). _Strong-cond-success_ weakens the
antecedent by only requiring that $E_{i}(\varphi)$ and $\varphi$ are jointly
consistent with current beliefs (i.e. $i$ need not be considered an expert on
$\varphi$). In other words, we should believe reports if there is no reason
not to. It is easily shown that _Closure_ and _Strong-cond-success_ implies
_Cond-success_. We once again revisit our examples.

######  Proposition 9.

$\mathsf{var\text{-}based\text{-}cond}$,
$\mathsf{part\text{-}based\text{-}cond}$ and $\mathsf{excess\text{-}min}$
satisfy _Cond-success_ , and $\mathsf{excess\text{-}min}$ additionally
satisfies _Strong-cond-success_.

By omission, the reader may suppose that the conditioning operators fail
_Strong-cond-success_. This is correct, and we can in fact say even more: _no_
conditioning operator with a few basic properties – all of which are satisfied
by $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$ – can satisfy _Strong-cond-success_.
In what follows, for a permutation $\pi:\mathcal{S}\to\mathcal{S}$ with
$\pi(\ast)=\ast$, write $\pi(W)$ for the world with $v^{\pi(W)}_{c}=v^{W}_{c}$
and $\Pi^{\pi(W)}_{i}=\Pi^{W}_{\pi(i)}$. We have an impossibility result.

######  Proposition 10.

No elementary conditioning operator satisfying the basic postulates can
simultaneously satisfy the following properties:

  1. 1.

$K^{\emptyset}=\operatorname{Cn}(\emptyset)$

  2. 2.

If $\pi$ is a permutation of $\mathcal{S}$ with $\pi(\ast)=\ast$,
$W\simeq\pi(W)$

  3. 3.

_Refinement_

  4. 4.

_Strong-cond-success_

(1) says that before any reports are received, we only know tautologies. As
remarked earlier, this is not an _essential_ property, but is reasonable when
no prior knowledge is available. (2) is an anonymity postulate: it says that
permuting the “names” of sources does not affect the plausibility of a world,
and is a desirable property in light of (1). _Refinement_ , introduced in
Section 4.1, says that worlds in which all sources have more expertise are
preferred.

Proposition 10 highlights an important difference between conditioning and
score-based operators, and hints that a fixed plausibility order may be too
restrictive: we need to allow the order to be responsive to new reports in
order to satisfy properties such as _Strong-cond-success_.

##  6 Selective Change

In the previous section we saw how a single formula $\varphi$ may be accepted
when it is received as an additional report. But what can we say about
propositional beliefs when taking into account the _whole sequence_ $\sigma$?
To investigate this we introduce an analogue of _selective revision_ (?), in
which propositional beliefs are formed by “selecting” part of each input
report (intuitively, some part consistent with the source’s expertise). In
what follows, write $\sigma\upharpoonright
c=\\{\langle{i,\varphi}\rangle\mid\langle{i,c,\varphi}\rangle\in\sigma\\}$ for
the $c$-reports in $\sigma$.

######  Definition 8.

A _selection scheme_ is a mapping $f$ assigning to each $\ast$-consistent
sequence $\sigma$ a function
$f_{\sigma}:\mathcal{S}\times\mathcal{C}\times\mathcal{L}{}_{0}\to\mathcal{L}{}_{0}$
such that $f_{\sigma}(i,c,\varphi)\in\operatorname{Cn}_{0}(\varphi)$. An
operator is _selective_ if there is a selection scheme $f$ such that for all
$\ast$-consistent $\sigma$ and $c\in\mathcal{C}$,

$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(\\{f_{\sigma}(i,c,\varphi)\mid\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c\\}).$

Thus, an operator is selective if its propositional beliefs in case $c$ are
formed by weakening each $c$-report and taking their consequences. Note that
for $\sigma=\emptyset$ we get
$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(\emptyset)$, so
selectivity already rules out non-tautological prior propositional beliefs.
Also note that in the presence of _Closure_ , _Containment_ and _Soundness_ ,
selectivity implies that
$\left[{B^{\sigma}_{c}}\right]=\left[{B^{\rho}_{c}}\right]$, where $\rho$ is
obtained by replacing each report $\langle{i,c,\varphi}\rangle$ with
$\langle{\ast,c,f_{\sigma}(i,c,\varphi)}\rangle$.

Selectivity can be characterised by a natural postulate placing an upper bound
on the propositional part of $B^{\sigma}_{c}$. In what follows, let
$\Gamma^{\sigma}_{c}=\\{\varphi\in\mathcal{L}{}_{0}\mid\exists
i\in\mathcal{S}:\langle{i,\varphi}\rangle\in\sigma\upharpoonright c\\}$.

######  _Boundedness_

If $\sigma$ is $\ast$-consistent,
$\left[{B^{\sigma}_{c}}\right]\subseteq\operatorname{Cn}_{0}(\Gamma^{\sigma}_{c})$

_Boundedness_ says that the propositional beliefs in case $c$ should not go
beyond the consequences of the formulas reported in case $c$. In some sense
this can be seen as an iterated version of _Inclusion_ from AGM revision, in
the case where
$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(\emptyset)$. We have the
following characterisation.

######  Theorem 3.

A model-based operator is selective if and only if it satisfies _Boundedness_.

This result allows us to easily analyse when conditioning and score-based
operators are selective; we show in the appendix that
$\mathsf{var\text{-}based\text{-}cond}$,
$\mathsf{part\text{-}based\text{-}cond}$ and $\mathsf{excess\text{-}min}$ are
all selective.

###  6.1 Case independence

In the definition of a selection scheme, we allow $f_{\sigma}(i,c,\varphi)$ to
depend on the case $c$. If one views $f_{\sigma}(i,c,\varphi)$ as a weakening
of $\varphi$ which accounts for the lack of expertise of $i$, this is somewhat
at odds with other aspects of the framework, where expertise is independent of
case. For this reason it is natural to consider _case independent_ selective
schemes.

######  Definition 9.

A selection scheme $f$ is _case independent_ if $f_{\sigma}(i,c,\varphi)\equiv
f_{\sigma}(i,d,\varphi)$ for all $\ast$-consistent $\sigma$ and
$i\in\mathcal{S}$, $c,d\in\mathcal{C}$ and $\varphi\in\mathcal{L}{}_{0}$.

Say an operator is _case-independent-selective_ if it is selective according
to some case independent scheme. This stronger notion of selectivity can again
be characterised by a postulate which bounds propositional beliefs. For any
set of cases $H\subseteq\mathcal{C}$, sequence $\sigma$ and $c\in\mathcal{C}$,
write

$\displaystyle\Gamma^{\sigma,H}_{c}=\\{\varphi\in\mathcal{L}{}_{0}\mid\exists
i\in\mathcal{S}:$
$\displaystyle\langle{i,\varphi}\rangle\in\sigma\upharpoonright c$
$\displaystyle\text{ and }\forall d\in
H:\langle{i,\varphi}\rangle\notin\sigma\upharpoonright d\\}.$

######  _H-Boundedness_

For any $\ast$-consistent $\sigma$, $H\subseteq\mathcal{C}$ and
$c\in\mathcal{C}$,

$\left[{B^{\sigma}_{c}}\right]\subseteq\operatorname{Cn}_{0}\left(\Gamma^{\sigma,H}_{c}\cup\bigcup_{d\in
H}{\left[{B^{\sigma}_{d}}\right]}\right)$

Note that _Boundedness_ is obtained as the special case where $H=\emptyset$.
We illustrate with an example.

######  Example 8.

Consider case $c$ in the following sequence:

$\sigma=(\langle{i,c,p}\rangle,\langle{j,c,q}\rangle,\langle{j,d,q}\rangle,\langle{k,d,r}\rangle)$

_Boundedness_ requires that
$\left[{B^{\sigma}_{c}}\right]\subseteq\operatorname{Cn}_{0}(\\{p,q\\})$.
However, the instance of _H-Boundedness_ with $H=\\{d\\}$ makes use of the
fact that $j$ reports $q$ in both cases $c$ and $d$, and requires
$\left[{B^{\sigma}_{c}}\right]\subseteq\operatorname{Cn}_{0}(\\{p\\}\cup\left[{B^{\sigma}_{d}}\right])$.
This also has an interesting implication for case $d$: if
$\varphi\in\left[{B^{\sigma}_{c}}\right]$, then
$p\rightarrow\varphi\in\left[{B^{\sigma}_{d}}\right]$. This follows since
$\beta\in\operatorname{Cn}_{0}(\\{\alpha\\}\cup\Gamma)$ iff
$\alpha\rightarrow\beta\in\operatorname{Cn}_{0}(\Gamma)$ for
$\alpha,\beta\in\mathcal{L}{}_{0}$. Intuitively, this says that if $p$ (from
$i$) and $q$ (from $j$) is enough to accept $\varphi$ in case $c$, then
$\varphi$ is accepted in case $d$ _if $p$ is_, given that the report of $q$
from $j$ is repeated for $d$.

######  Theorem 4.

A model-based operator is case-independent-selective if and only if it
satisfies _H-Boundedness_.

The question of whether our concrete operators satisfy _H-Boundedness_
(equivalently, whether they are case-independent-selective) is still open.

##  7 Related Work

#### Belief merging.

In the framework of ? (?), a merging operator $\Delta$ maps a multiset of
propositional formulas $\Phi=\\{\varphi_{1},\ldots,\varphi_{n}\\}$ and an
integrity constraint $\mu$ to a formula $\Delta_{\mu}(\Phi)$. This can be seen
as the special case of our framework with a single case $c$: for $\Phi$, $\mu$
we consider the sequence $\sigma_{\Phi,\mu}$ where $\ast$ reports $\mu$ and
each source $i$ reports $\varphi_{i}$. Any operator then gives rise to a
merging operator
$\Delta_{\mu}(\Phi)=\bigwedge\left[{B^{\sigma_{\Phi,\mu}}_{c}}\right]$.

We go beyond this setting by considering multiple cases and explicitly
modelling expertise (and trust, via beliefs about expertise). While it may be
possible to model expertise _implicitly_ in belief merging (for example, say
$i$ is not trusted on $\psi$ if $\Delta_{\mu}(\Phi)\not\vdash\psi$ when
$\varphi_{i}\vdash\psi$), bringing expertise to the object level allows us to
express more complex beliefs about expertise, such as $E_{a}(x)\lor E_{b}(x)$
in Example 3. It also facilitates postulates which refer directly to
expertise, such as the weakenings of _Success_ in Section 5.

However, our problem is more specialised than merging, since we focus
specifically on conflicting information due to lack of expertise. Belief
merging may be applied more broadly to other types of _information fusion_ ,
e.g. subjective beliefs or goals (?), where notions of objective expertise do
not apply. While our framework _could_ be applied in these settings, our
postulates may no longer be desirable.

#### Epistemic logic.

Our notions of expertise and soundness are related to _S5 knowledge_ from
epistemic logic (?). In such logics, an agent _knows_ $\varphi$ at a state $x$
if $\varphi$ holds at all states $y$ “accessible” from $x$. Knowledge is thus
determined by an _epistemic accessibility relation_ , which describes the
distinctions between states the agent can make. The logic of S5 arises when
this relation is an equivalence relation (or equivalently, a partition).

Our previous work (?) – in which expertise and soundness were introduced in a
modal logic framework – showed that “expertise models” are in 1-to-1
correspondence with S5 models, such that $E(\varphi)$ holds iff
$A(\varphi\rightarrow K\varphi)$ holds in the S5 model, where $A$ is the
universal modality. By symmetry of expertise, we can also replace $\varphi$
with its negation. Thus, expertise has a precise epistemic interpretation: it
is the ability to _know whether_ $\varphi$ holds in _any possible state_.
Similarly, $S(\varphi)$ translates to $\neg K\neg\varphi$. That is, $\varphi$
is sound exactly when the source does not _know_ $\varphi$ is false.

In the present framework, if we set $W,c\models K_{i}(\varphi)$ iff
$\Pi_{i}[v_{c}]\subseteq\operatorname{mod}_{0}(\varphi)$ and $W,c\models
A\Phi$ iff $\forall v:\ W_{c=v},c\models\Phi$, where $W_{c=v}$ is the world
obtained from $W$ by setting $v^{\prime}_{c}=v$, then we have
$E_{i}(\varphi)\equiv A(\varphi\rightarrow K_{i}(\varphi))$ and
$S_{i}(\varphi)\equiv\neg K_{i}(\neg\varphi)$. While $K_{i}$ is not quite an
S5 modality (the 5 axiom requires iterating $K_{i}$, which is not possible in
our framework), this shows the fundamental link between expertise, soundness
and knowledge.

##  8 Conclusion

#### Summary.

In this paper we studied a belief change problem – extending the classical AGM
framework – in which beliefs about the state of the world in multiple cases,
as well as expertise of multiple sources, must be inferred from a sequence of
reports. This allowed us to take a fresh look at the interaction between trust
(seen as _belief in expertise_) and belief. By inferring the expertise of the
sources from the reports, we have generalised some earlier approaches to non-
prioritised revision which assume expertise (or reliability, credibility,
priority etc) is known up-front (e.g. (?; ?; ?; ?)). We went on to propose
some concrete belief change operators, and explored their properties through
examples and postulates.

We saw that conditioning operators satisfy some desirable properties, and our
concrete instances make useful inferences that go beyond
$\mathsf{weak\text{-}mb}$. However, we have examples in which intuitively
plausible inferences are blocked, and conditioning is largely incompatible
with _Strong-cond-success_. Score-based operators, and in particular
$\mathsf{excess\text{-}min}$, offer a way around these limitations, but may
come at the expense of some other seemingly reasonable postulates, such as
_Duplicate-removal_.

#### Future work.

There are many possibilities for future work. Firstly, we have a
representation result only for conditioning operators. A characterisation of
score-based operators – either the class in general or the specific operator
$\mathsf{excess\text{-}min}$ – remains to be found. This would help to further
clarify the differences between conditioning and score-based operators. We
have also not considered any computational issues. Determining the complexity
of calculating the results of our example operators, and the complexity for
conditioning and score-based operators more broadly, is left to future work.
Secondly, there is scope for deeper postulate-based analysis. For example,
there should be postulates governing how beliefs change in case $c$ in
response to reports in case $d$. We could also consider more postulates
relating trust and belief, and compare these postulates with those of ? (?).
Finally, our framework only deals with three levels of trust on a proposition:
we can believe $E_{i}(\varphi)$, believe $\neg E_{i}(\varphi)$, or neither.
Future work could investigate how to extend our semantics to talk about
_graded expertise_ , and thereby permit more fine-grained _degrees of trust_
(?; ?; ?).

## Acknowledgements

We thank the anonymous KR 2022 reviewers for their thoughtful comments and
suggestions.

##  Appendix A Proofs

###  A.1 Proof of Proposition 1

###### Proof.

  * 1.

If $\varphi\equiv\psi$ then
$\operatorname{mod}_{0}(\varphi)=\operatorname{mod}_{0}(\psi)$; since the
semantics for $\mathcal{S}_{i}(\varphi)$ and $E_{i}(\varphi)$ only refer to
$\operatorname{mod}_{0}(\varphi)$ (and likewise for $\psi$), we have that
$S_{i}(\varphi)\leftrightarrow S_{i}(\psi)$ and $E_{i}(\varphi)\leftrightarrow
E_{i}(\psi)$ are valid.

  * 2.

For the first validity, suppose $W,c\models E_{i}(\varphi)$. Then
$\operatorname{mod}_{0}(\varphi)=\Pi_{i}[\varphi]$. We show $W,c\models
E_{i}(\neg\varphi)$. Indeed, take $v\in\Pi_{i}[\neg\varphi]$. Then there is
$v^{\prime}\in\operatorname{mod}_{0}(\neg\varphi)$ such that
$v\in\Pi_{i}[v^{\prime}]$. Thus $v^{\prime}\in\Pi_{i}[v]$ also. Supposing for
contradiction that $v\in\operatorname{mod}_{0}(\varphi)$, we get

$v^{\prime}\in\Pi_{i}[v]\subseteq\Pi_{i}[\varphi]=\operatorname{mod}_{0}(\varphi).$

But then
$v^{\prime}\in\operatorname{mod}_{0}(\neg\varphi)\cap\operatorname{mod}_{0}(\varphi)=\emptyset$;
contradiction. Hence $v\notin\operatorname{mod}_{0}(\varphi)$, i.e.
$v\in\operatorname{mod}_{0}(\neg\varphi)$. This shows that
$\Pi_{i}[\neg\varphi]\subseteq\operatorname{mod}_{0}(\neg\varphi)$, so
$W,c\models E_{i}(\neg\varphi)$.

We have shown that $E_{i}(\varphi)\rightarrow E_{i}(\neg\varphi)$ is valid.
For the converse note that, by symmetry, $E_{i}(\neg\varphi)\rightarrow
E_{i}(\neg\neg\varphi)$ is valid; since $E_{i}(\neg\neg\varphi)$ is equivalent
to $E_{i}(\varphi)$ by (1) we get $E_{i}(\varphi)\leftrightarrow
E_{i}(\neg\varphi)$.

For the second validity, suppose $W,c\models E_{i}(\varphi)\land E_{i}(\psi)$.
Note that

$\Pi_{i}[\varphi\land\psi]\subseteq\Pi_{i}[\varphi]=\operatorname{mod}_{0}(\varphi)$

and, similarly,
$\Pi_{i}[\varphi\land\psi]\subseteq\operatorname{mod}_{0}(\psi)$. Hence

$\Pi_{i}[\varphi\land\psi]\subseteq\operatorname{mod}_{0}(\varphi)\cap\operatorname{mod}_{0}(\psi)=\operatorname{mod}_{0}(\varphi\land\psi),$

which shows $W,c\models E_{i}(\varphi\land\psi)$.

  * 3.

Let $\varphi$ be a propositional formula, and let $p_{1},\ldots,p_{k}$ be the
variables appearing in $\varphi$. Let
$\widehat{\mathcal{L}{}_{0}}\subseteq\mathcal{L}{}_{0}$ be the propositional
formulas over $p_{1},\ldots p_{k}$ generated only using conjunction and
negation. Then there is some $\psi\in\widehat{\mathcal{L}{}_{0}}$ with
$\varphi\equiv\psi$.

Suppose $W,c\models E_{i}(p_{1})\land\cdots\land E_{i}(p_{k})$. By this
assumption and the properties in (2), one can show by induction that
$W,c\models E_{i}(\theta)$ for all $\theta\in\widehat{\mathcal{L}{}_{0}}$. In
particular, $W,c\models E_{i}(\psi)$. Since $\varphi\equiv\psi$, we get
$W,c\models E_{i}(\varphi)$.

  * 4.

Suppose $W,c\models E_{i}(\varphi)\land S_{i}(\varphi)$. Then
$v_{c}\in\Pi_{i}[\varphi]=\operatorname{mod}_{0}(\varphi)$, so
$W,c\models\varphi$. Hence $E_{i}(\varphi)\land
S_{i}(\varphi)\rightarrow\varphi$ is valid. Similarly,
$S_{i}(\varphi)\land\neg\varphi\rightarrow\neg E_{i}(\varphi)$ is valid.

  * 5.

Suppose $W,c\models S_{i}(\varphi)\land S_{i}(\neg\varphi)$, and, for
contradiction, $W,c\models E_{i}(\varphi)$. On the one hand we have
$W,c\models E_{i}(\varphi)\land S_{i}(\varphi)$, so (4) gives
$W,c\models\varphi$. On the other hand, $W,c\models E_{i}(\varphi)$ gives
$W,c\models E_{i}(\neg\varphi)$ by (2), so $W,c\models E_{i}(\neg\varphi)\land
S_{i}(\neg\varphi)$; by (4) again we have $W,c\models\neg\varphi$. But then
$W,c\models\varphi\land\neg\varphi$ – contradiction.

  * 6.

Since the distinguished source $\ast$ has the unit partition $\Pi_{\ast}$ in
any world $W$, we have $\Pi_{\ast}[\varphi]=\operatorname{mod}_{0}(\varphi)$,
so $W,c\models E_{\ast}(\varphi)$. Similarly, $W,c\models S_{i}(\varphi)$ iff
$v_{c}\in\Pi_{\ast}[\varphi]=\operatorname{mod}_{0}(\varphi)$ iff
$W,c\models\varphi$.

∎

###  A.2 Proof of Proposition 2

###### Proof (sketch).

“if”: Suppose the stated condition holds for $S\subseteq\mathcal{W}$. Form a
collection $G=\\{\Gamma_{c}\\}_{c\in\mathcal{C}}$ by setting
$\Gamma_{c}=\\{\Phi\in\mathcal{L}{}\mid
S\subseteq\operatorname{mod}_{c}(\Phi)\\}$. Clearly
$S\subseteq\operatorname{mod}(G)$. For the reverse inclusion, suppose
$W\in\operatorname{mod}(G)$. For any set of valuations
$U\subseteq\mathcal{V}$, let $\varphi_{U}$ be any propositional sentence with
$\operatorname{mod}_{0}(\varphi_{U})=U$. For each $c\in\mathcal{C}$, consider
the sentence

$\Phi_{c}=\bigvee_{W^{\prime}\in
S}\left(\varphi_{\\{v^{W^{\prime}}_{c}\\}}\land\bigwedge_{i\in\mathcal{S}}\bigwedge_{U\subseteq\mathcal{V}}R_{W^{\prime},i,U}\right)$

where

$R_{W^{\prime},i,U}=\begin{cases}E_{i}(\varphi_{U}),&W^{\prime},c_{0}\models
E_{i}(\varphi_{U})\\\ \neg E_{i}(\varphi_{U}),&\text{ otherwise }\end{cases}$

for some fixed case $c_{0}\in\mathcal{C}$. It is straightforward to see that
each $W^{\prime}\in S$ satisfies its corresponding disjunct at case $c$, so
$\Phi_{c}\in\Gamma_{c}$. Hence $W\in\operatorname{mod}(G)$ implies
$W,c\models\Phi_{c}$ for each $c$. Consequently, for each $c$ there is some
$W_{c}\in S$ such that  (i) $v^{W}_{c}=v^{W_{c}}_{c}$; and  (ii) for each
$i\in\mathcal{S}$ and $U\subseteq V$, $W,c\models E_{i}(\varphi_{U})$ iff
$W_{c},c\models E_{i}(\varphi_{U})$.  From (i), $W$ is a valuation combination
from $\\{W_{c}\\}_{c\in\mathcal{C}}$. From (ii) it can be shown that in fact
$\Pi^{W}_{i}=\Pi^{W_{c}}_{i}$ for each $c$ and $i$; that is, $W$ is partition-
equivalent to each $W_{c}$. In particular, all the $W_{c}$ are partition-
equivalent to each other. Repeatedly applying the closure condition assumed to
hold for $S$, we see that $W\in S$ as required.

“only if”: Suppose $S$ is elementary, i.e. $S=\operatorname{mod}(G)$ for some
collection $G=\\{\Gamma_{c}\\}_{c\in\mathcal{C}}$, and let $W,W_{1},W_{2}$ be
as in the statement of the Proposition. Take $c\in\mathcal{C}$ and
$\Phi\in\Gamma_{c}$. We will show $W,c\models\Phi$. By assumption, there is
$n\in\\{1,2\\}$ such that $v^{W}_{c}=v^{W_{n}}_{c}$. It can be shown by
induction on $\mathcal{L}{}$ formulas that, since $W$ and $W_{n}$ are
partition-equivalent and have the same $c$ valuation, $W,c\models\Phi$ iff
$W_{n},c\models\Phi$. But $W_{n}\in S=\operatorname{mod}(G)$ implies
$W_{n},c\models\Phi$, so $W,c\models\Phi$ too. Since $\Phi\in\Gamma_{c}$ was
arbitrary, we have $W\in\operatorname{mod}(G)=S$ as required.

∎

###  A.3 Proof of Proposition 3

###### Proof.

  1. 1.

The “$\sqsubseteq$” inclusion is just _K-bound_. For the “$\sqsupseteq$”
inclusion, note that $G^{\sigma}_{\mathsf{snd}}\sqsubseteq K^{\sigma}$ by
_Soundness_ , and $K^{\emptyset}\sqsubseteq K^{\sigma}$ by _Prior-Extension_.
Hence

$G^{\sigma}_{\mathsf{snd}}\sqcup K^{\emptyset}\sqsubseteq K^{\sigma}.$

By monotonicity of $\operatorname{Cn}$,

$\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup
K^{\emptyset})\sqsubseteq\operatorname{Cn}(K^{\sigma})=K^{\sigma}$

where we use _Closure_ in the final step.

  2. 2.

“if”: Suppose $K^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})$ for
all $\sigma$. Taking $\sigma=\emptyset$ we obtain

$K^{\sigma}=\operatorname{Cn}(G^{\emptyset}_{\mathsf{snd}})=\operatorname{Cn}(\emptyset).$

“only if”: Suppose $K^{\emptyset}=\operatorname{Cn}(\emptyset)$. Take any
sequence $\sigma$. By _K-bound_ ,

$K^{\sigma}\sqsubseteq\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup\operatorname{Cn}(\emptyset))=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})$

On the other hand, _Soundness_ and _Closure_ give
$\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})\sqsubseteq K^{\sigma}$. Hence
$K^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})$.

∎

###  A.4 Proof of Proposition 4

###### Proof.

Suppose an operator satisfies the basic postulates, and take sequences
$\sigma$ and $\rho$. By Proposition 3,

$K^{\sigma\cdot\rho}=\operatorname{Cn}(G^{\sigma\cdot\rho}_{\mathsf{snd}}\sqcup
K^{\emptyset})$

Note that $G^{\sigma\cdot\rho}_{\mathsf{snd}}=G^{\sigma}_{\mathsf{snd}}\sqcup
G^{\rho}_{\mathsf{snd}}$. Hence we may write

$\displaystyle K^{\sigma\cdot\rho}$
$\displaystyle=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup
G^{\rho}_{\mathsf{snd}}\sqcup K^{\emptyset})$
$\displaystyle=\operatorname{Cn}((G^{\sigma}_{\mathsf{snd}}\sqcup
K^{\emptyset})\sqcup(G^{\rho}_{\mathsf{snd}}\sqcup K^{\emptyset}))$

By Proposition 3 again, we have
$K^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup K^{\emptyset})$
and $K^{\rho}=\operatorname{Cn}(G^{\rho}_{\mathsf{snd}}\sqcup K^{\emptyset})$.
It is easily verified that for any collections $G,D$, we have

$\operatorname{Cn}(G\sqcup
D)=\operatorname{Cn}(\operatorname{Cn}(G)\sqcup\operatorname{Cn}(D)).$

Consequently,

$\displaystyle K^{\sigma\cdot\rho}$
$\displaystyle=\operatorname{Cn}(\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}}\sqcup
K^{\emptyset})\sqcup\operatorname{Cn}(G^{\rho}_{\mathsf{snd}}\sqcup
K^{\emptyset}))$ $\displaystyle=\operatorname{Cn}(K^{\sigma}\sqcup K^{\rho})$

as required for _K-conjunction_. ∎

###  A.5 Proof of Proposition 5

###### Proof.

  1. 1.

Suppose $\varphi\in K^{\sigma}_{c}$ and
$\neg\psi\in\operatorname{Cn}_{0}(\varphi)$. Write
$\rho=\sigma\cdot\langle{i,c,\psi}\rangle$. By _Soundness_ , $S_{i}(\psi)\in
K^{\rho}_{c}$. By _K-conjunction_ , $\varphi\in
K^{\sigma}_{c}\subseteq(K^{\sigma}\sqcup
K^{\langle{i,c,\psi}\rangle})_{c}\subseteq\operatorname{Cn}_{c}(K^{\sigma}\sqcup
K^{\langle{i,c,\psi}\rangle})=K^{\rho}_{c}$. Since
$\neg\psi\in\operatorname{Cn}_{0}(\varphi)$ and $\varphi\in K^{\rho}_{c}$,
_Closure_ gives $\neg\psi\in K^{\rho}_{c}$. Recalling from Proposition 1 part
(4) that $S_{i}\psi\land\neg\psi\rightarrow\neg E_{i}(\psi)$, _Closure_ gives
$\neg E_{i}(\psi)\in K^{\rho}_{c}$, as desired.

  2. 2.

Suppose $\langle{i,c,\varphi}\rangle\in\sigma$ and $E_{i}(\varphi)\in
B^{\sigma}_{c}$. By _Soundness_ and _Containment_ , $S_{i}(\varphi)\in
B^{\sigma}_{c}$. From Proposition 1 part (4) again we have
$E_{i}(\varphi)\land S_{i}(\varphi)\rightarrow\varphi$. By _Closure_ ,
$\varphi\in B^{\sigma}_{c}$.

∎

###  A.6 Proof of Theorem 1

###### Proof.

For ease of notation in what follows, write
$\operatorname{mod}_{c}(\Phi)=\\{W\in\mathcal{W}\mid W,c\models\Phi\\}$.

“if”: Suppose an operator $\sigma\mapsto\langle{B^{\sigma},K^{\sigma}}\rangle$
is model-based. For _Closure_ , we need to show that
$B^{\sigma}_{c}\supseteq\operatorname{Cn}_{c}(B^{\sigma})$ and
$K^{\sigma}_{c}\supseteq\operatorname{Cn}_{c}(K^{\sigma})$, for each $c$. Take
any $\Phi\in\operatorname{Cn}_{c}(B^{\sigma})$. Then
$\operatorname{mod}(B^{\sigma})\subseteq\operatorname{mod}_{c}(\Phi)$. From
the relevant definitions, one can easily check that
$\mathcal{Y}_{\sigma}\subseteq\operatorname{mod}(B^{\sigma})$, so we have
$\mathcal{Y}_{\sigma}\subseteq\operatorname{mod}_{c}(\Phi)$. That is,
$W,c\models\Phi$ for all $W\in\mathcal{Y}_{\sigma}$. By definition of model-
based operators, $\Phi\in B^{\sigma}_{c}$. The fact that
$K^{\sigma}_{c}\supseteq\operatorname{Cn}_{c}(K^{\sigma})$ follows by an
identical argument upon noticing that
$\mathcal{X}_{\sigma}\subseteq\operatorname{mod}(K^{\sigma})$.

_Containment_ follows from
$\mathcal{X}_{\sigma}\supseteq\mathcal{Y}_{\sigma}$: if $\Phi\in
K^{\sigma}_{c}$ then $W,c\models\Phi$ for all $W\in\mathcal{X}_{\sigma}$, and
in particular this holds for all $W\in\mathcal{Y}_{\sigma}$. Hence $\Phi\in
B^{\sigma}_{c}$, so $K^{\sigma}\sqsubseteq B^{\sigma}$.

“only if”: Suppose an operator satisfies _Closure_ and _Containment_. For any
$\sigma$, set

$\mathcal{X}_{\sigma}=\operatorname{mod}(K^{\sigma})$
$\mathcal{Y}_{\sigma}=\operatorname{mod}(B^{\sigma})$

We show the three properties required in Definition 1.
$\mathcal{X}_{\sigma}\supseteq\mathcal{Y}_{\sigma}$ follows from _Containment_
and the definition of a model of a collection. For the second property, note
that $\Phi\in K^{\sigma}_{c}$ iff $\Phi\in\operatorname{Cn}_{c}(K^{\sigma})$
by _Closure_ , i.e. iff
$\operatorname{mod}(K^{\sigma})\subseteq\operatorname{mod}_{c}(\Phi)$. By
choice of $\mathcal{X}_{\sigma}$, this holds exactly when $W,c\models\Phi$ for
all $W\in\mathcal{X}_{\sigma}$, as required. The third property is proved
using an identical argument. ∎

###  A.7 Proof of Theorem 2

First, a preliminary result.

######  Lemma 1.

For any model-based operator and sequence $\sigma$,
$\mathcal{X}_{\sigma}=\operatorname{mod}(K^{\sigma})$ iff
$\mathcal{X}_{\sigma}$ is elementary, and
$\mathcal{Y}_{\sigma}=\operatorname{mod}(B^{\sigma})$ iff
$\mathcal{Y}_{\sigma}$ is elementary.

###### Proof.

We prove the result for $\mathcal{X}_{\sigma}$ and $K^{\sigma}$ only. The
“only if” direction is clear from the definition of an elementary set. For the
“if” direction, suppose $\mathcal{X}_{\sigma}$ is elementary, i.e.
$\mathcal{X}_{\sigma}=\operatorname{mod}(G)$ for some collection $G$. Since
$\Phi\in K^{\sigma}_{c}$ iff
$\mathcal{X}_{\sigma}\subseteq\operatorname{mod}_{c}(\Phi)$, we have
$K^{\sigma}_{c}=\operatorname{Cn}_{c}(G)$, i.e.
$K^{\sigma}=\operatorname{Cn}(G)$. Consequently
$\operatorname{mod}(K^{\sigma})=\operatorname{mod}(\operatorname{Cn}(G))=\operatorname{mod}(G)=\mathcal{X}_{\sigma}$.
∎

A result slightly more general than Theorem 2 is available, from which Theorem
2 immediately follows.

######  Proposition 11.

Suppose an operator satisfies _Closure_ , _Containment_ , _K-conjunction_ and
_Equivalence_. Then it is an elementary conditioning operator if and only if
it satisfies _Rearrangement_ , _Duplicate-removal_ , _Conditional-consistency_
, _Inclusion-vacuity_ and _Acyc_.

###### Proof.

Take some operator $\sigma\mapsto\langle{B^{\sigma},K^{\sigma}}\rangle$
satisfying _Closure_ , _Containment_ , _K-conjunction_ and _Equivalence_.

“if”: Suppose the operator in question additionally satisfies _Rearrangement_
, _Duplicate-removal_ , _Conditional-consistency_ , _Inclusion-vacuity_ and
_Acyc_. For any $\sigma$, set

$\mathcal{X}_{\sigma}=\operatorname{mod}(K^{\sigma})$
$\mathcal{Y}_{\sigma}=\operatorname{mod}(B^{\sigma})$

Then – by _Closure_ and _Containment_ as shown in the proof of Theorem 1 – our
operator is model based corresponding to this choice of $\mathcal{X}_{\sigma}$
and $\mathcal{Y}_{\sigma}$. Clearly both are elementary. We will construct a
total preorder $\leq$ over $\mathcal{W}$ such that
$\mathcal{Y}_{\sigma}=\min_{\leq}{\mathcal{X}_{\sigma}}$; this will show the
operator is an elementary conditioning operator.

First, fix a function $c:\mathcal{L}{}_{0}/{\equiv}\to\mathcal{L}{}_{0}$ which
chooses a fixed representative of each equivalence class of logically
equivalent propositional formulas, i.e. any mapping such that
$c([\varphi]_{\equiv})\equiv\varphi$. To simplify notation, write
$\widehat{\varphi}$ for $c([\varphi]_{\equiv})$. Then
$\varphi\equiv\widehat{\varphi}$. Write
$\widehat{\mathcal{L}{}_{0}}=\\{\widehat{\varphi}\mid\varphi\in\mathcal{L}{}_{0}\\}$.
Note that $\widehat{\mathcal{L}{}_{0}}$ is finite (since we work with only
finitely many propositional variables) and every formula in
$\mathcal{L}{}_{0}$ is equivalent to exactly one formula in
$\widehat{\mathcal{L}{}_{0}}$. For a sequence $\sigma$, let $\widehat{\sigma}$
be the result of replacing each report $\langle{i,c,\varphi}\rangle$ with
$\langle{i,c,\widehat{\varphi}}\rangle$. Note that by _Rearrangement_ and
_Equivalence_ , $\mathcal{X}_{\widehat{\sigma}}=\mathcal{X}_{\sigma}$ and
$\mathcal{Y}_{\widehat{\sigma}}=\mathcal{Y}_{\sigma}$.

Now, for any world $W$, set

$\mathcal{R}(W)=\\{\langle{i,c,\varphi}\rangle\in\mathcal{S}\times\mathcal{C}\times\widehat{\mathcal{L}{}_{0}}\mid
W\in\mathcal{X}_{\langle{i,c,\varphi}\rangle}\\}$

Note that $\mathcal{R}(W)$ is finite. For any pair of worlds $W_{1}$, $W_{2}$,
let $\rho(W_{1},W_{2})$ be some enumeration of
$\mathcal{R}(W_{1})\cap\mathcal{R}(W_{2})$. We establish some useful
properties of $\rho(W_{1},W_{2})$.

[1em]1em

######  Claim 1.

If $\rho(W_{1},W_{2})\neq\emptyset$,
$W_{1},W_{2}\in\mathcal{X}_{\rho(W_{1},W_{2})}$.

###### Proof.

By _K-conjunction_ , for any sequences $\sigma$, $\rho$ we have
$K^{\sigma\cdot\rho}=\operatorname{Cn}(K^{\sigma}\sqcup K^{\rho})$. Taking the
models of both sides, we have
$\mathcal{X}_{\sigma\cdot\rho}=\mathcal{X}_{\sigma}\cap\mathcal{X}_{\rho}$. It
follows that for $\rho(W_{1},W_{2})\neq\emptyset$,

$\mathcal{X}_{\rho(W_{1},W_{2})}=\bigcap_{\langle{i,c,\varphi}\rangle\in\rho(W_{1},W_{2})}{\mathcal{X}_{\langle{i,c,\varphi}\rangle}}$

If $\langle{i,c,\varphi}\rangle\in\rho(W_{1},W_{2})$ then
$W_{1},W_{2}\in\mathcal{X}_{\langle{i,c,\varphi}\rangle}$ by definition. Hence
$W_{1},W_{2}\in\mathcal{X}_{\rho(W_{1},W_{2})}$. ∎

[1em]1em

######  Claim 2.

If a sequence $\sigma$ contains no equivalent reports (i.e. no distinct tuples
$\langle{i,c,\varphi}\rangle$, $\langle{i,c,\psi}\rangle$ with
$\varphi\equiv\psi$) and $W_{1},W_{2}\in\mathcal{X}_{\sigma}$, there is a
sequence $\delta$ such that $W_{1},W_{2}\in\mathcal{X}_{\delta}$ and
$\rho(W_{1},W_{2})$ is a permutation of $\widehat{\sigma}\cdot\delta$.

###### Proof.

If $\sigma=\emptyset$ then we can simply take $\delta=\rho(W_{1},W_{2})$. So
suppose $\sigma\neq\emptyset$. By the same argument as in the proof of 1, we
have

$\mathcal{X}_{\sigma}=\bigcap_{\langle{i,c,\varphi}\rangle\in\sigma}{\mathcal{X}_{\langle{i,c,\varphi}\rangle}}$

Take any $\langle{i,c,\varphi}\rangle\in\widehat{\sigma}$. Then
$\varphi\in\widehat{\mathcal{L}{}_{0}}$, and there is $\psi\equiv\varphi$ such
that $\langle{i,c,\psi}\rangle\in\sigma$. By _Equivalence_ , we have

$W_{1},W_{2}\in\mathcal{X}_{\sigma}\subseteq\mathcal{X}_{\langle{i,c,\psi}\rangle}=\mathcal{X}_{\langle{i,c,\varphi}\rangle}$

i.e. $\langle{i,c,\varphi}\rangle\in\mathcal{R}(W_{1})\cap\mathcal{R}(W_{2})$.
Hence $\langle{i,c,\varphi}\rangle$ appears in $\rho(W_{1},W_{2})$. By the
assumption that $\sigma$ contains no equivalent reports, $\widehat{\sigma}$
contains no duplicates. It follows that $\rho(W_{1},W_{2})$ can be permuted so
that $\widehat{\sigma}$ appears as a prefix. Taking $\delta$ to be the
sequence that remains after $\widehat{\sigma}$ in this permutation, we clearly
have that $\rho(W_{1},W_{2})$ is a permutation of
$\widehat{\sigma}\cdot\delta$. Since $\sigma\neq\emptyset$ implies
$\widehat{\sigma}\neq\emptyset$ and thus $\rho(W_{1},W_{2})\neq\emptyset$, by
_Rearrangement_ , _K-conjunction_ and 1 we get

$W_{1},W_{2}\in\mathcal{X}_{\rho(W_{1},W_{2})}=\mathcal{X}_{\widehat{\sigma}\cdot\delta}=\mathcal{X}_{\widehat{\sigma}}\cap\mathcal{X}_{\delta}\subseteq\mathcal{X}_{\delta}$

and we are done. ∎

Now define a relation $R$ on $\mathcal{W}$ by

$WRW^{\prime}\iff W=W^{\prime}\text{ or }W\in\mathcal{Y}_{\rho(W,W^{\prime})}$

We have that any world in $\mathcal{Y}_{\sigma}$ $R$-precedes all worlds
$\mathcal{X}_{\sigma}$.

[1em]1em

######  Claim 3.

If $W\in\mathcal{Y}_{\sigma}$, then for all
$W^{\prime}\in\mathcal{X}_{\sigma}$ we have $WRW^{\prime}$

###### Proof.

By _Rearrangement_ , _Equivalence_ and _Duplicate-removal_ , we may assume
without loss of generality that $\sigma$ contains no distinct equivalent
reports.

Let $W\in\mathcal{Y}_{\sigma}$ and $W^{\prime}\in\mathcal{X}_{\sigma}$. Then
$W\in\mathcal{X}_{\sigma}$ too. By 2 and _Rearrangement_ , there is some
sequence $\delta$ such that
$\mathcal{Y}_{\rho(W,W^{\prime})}=\mathcal{Y}_{\widehat{\sigma}\cdot\delta}$
and $W,W^{\prime}\in\mathcal{X}_{\delta}$. Consequently
$W\in\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\delta}=\mathcal{Y}_{\widehat{\sigma}}\cap\mathcal{X}_{\delta}$.
Thus $B^{\widehat{\sigma}}\sqcup K^{\delta}$ is consistent. From _Inclusion-
vacuity_ we get

$\mathcal{Y}_{\widehat{\sigma}\cdot\delta}=\mathcal{Y}_{\widehat{\sigma}}\cap\mathcal{X}_{\delta}$

Thus

$W\in\mathcal{Y}_{\widehat{\sigma}}\cap\mathcal{X}_{\delta}=\mathcal{Y}_{\widehat{\sigma}\cdot\delta}=\mathcal{Y}_{\rho(W,W^{\prime})}$

so $WRW^{\prime}$ as required. ∎

Now let $\leq_{0}$ be the transitive closure of $R$. Then $\leq_{0}$ is a
(partial) preorder. By 3, every world in $\mathcal{Y}_{\sigma}$ is
$\leq_{0}$-minimal in $\mathcal{X}_{\sigma}$. In fact, the converse is also
true.

[1em]1em

######  Claim 4.

If $W\in\mathcal{X}_{\sigma}$ and there is no
$W^{\prime}\in\mathcal{X}_{\sigma}$ with $W^{\prime}<_{0}W$, then
$W\in\mathcal{Y}_{\sigma}$.

###### Proof.

As before, assume without loss of generality that $\sigma$ contains no
distinct equivalent reports.

Take $W$ as in the statement of the claim. Then
$\mathcal{X}_{\sigma}\neq\emptyset$, so $\mathcal{Y}_{\sigma}\neq\emptyset$ by
_Conditional-consistency_. Let $W^{\prime}\in\mathcal{Y}_{\sigma}$. By 3,
$W^{\prime}RW$ and thus $W^{\prime}\leq_{0}W$. But by assumption,
$W^{\prime}\not<_{0}W$. So we must have $W\leq_{0}W^{\prime}$. By definition
of $\leq_{0}$ as the transitive closure of $R$, there are $W_{0},\ldots W_{n}$
such that $W_{0}=W$, $W_{n}=W^{\prime}$ and

$W_{j}RW_{j+1}\qquad(0\leq j<n)$

Without loss of generality, $n>0$ and each of the $W_{j}$ are distinct. From
the definition of $R$, we therefore have that

$W_{j}\in\rho(W_{j},W_{j+1})\qquad(0\leq j<n)$

Now set

$\displaystyle\rho_{j}$ $\displaystyle=\rho(W_{j},W_{j+1})\qquad(0\leq j<n)$
$\displaystyle\rho_{n}$ $\displaystyle=\rho(W_{0},W_{n})$

Since $W^{\prime}RW$, i.e. $W_{n}RW_{0}$, we in fact have
$W_{j}\in\mathcal{Y}_{\rho_{j}}$ for all $j$ (including $j=n$). For $j<n$, we
also have $W_{j+1}\in\mathcal{X}_{\rho_{j}}$.151515 If $\rho_{j}\neq\emptyset$
this follows from 1. Otherwise,
$W_{j+1}\in\mathcal{Y}_{\rho_{j+1}}\subseteq\mathcal{X}_{\rho_{j+1}}=\mathcal{X}_{\rho_{j+1}\cdot\emptyset}=\mathcal{X}_{\rho_{j+1}}\cap\mathcal{X}_{\emptyset}\subseteq\mathcal{X}_{\emptyset}=\mathcal{X}_{\rho_{j}}$
by _K-conjunction_.  Consequently, for $j<n$ we have

$W_{j+1}\in\mathcal{X}_{\rho_{j}}\cap\mathcal{Y}_{\rho_{j+1}}$

i.e. $K^{\rho_{j}}\sqcup B^{\rho_{j+1}}$ is consistent. Moreover,
$W_{0}\in\mathcal{X}_{\rho_{n}}\cap\mathcal{Y}_{\rho_{0}}$, so
$K^{\rho_{n}}\sqcup B^{\rho_{0}}$ is consistent. We can now apply _Acyc_ : we
get that $K^{\rho_{0}}\sqcup B^{\rho_{n}}$ is also consistent. On the one
hand, _Inclusion-vacuity_ and consistency of $K^{\rho_{n}}\sqcup B^{\rho_{0}}$
gives

$B^{\rho_{0}\cdot\rho_{n}}=\operatorname{Cn}(B^{\rho_{0}}\sqcup K^{\rho_{n}})$

On the other, consistency of $B^{\rho_{n}}\sqcup K^{\rho_{0}}$ and
_Rearrangement_ gives

$B^{\rho_{0}\cdot\rho_{n}}=B^{\rho_{n}\cdot\rho_{0}}=\operatorname{Cn}(B^{\rho_{n}}\sqcup
K^{\rho_{0}})$

Combining these and taking models, we find

$\mathcal{Y}_{\rho_{0}}\cap\mathcal{X}_{\rho_{n}}=\mathcal{Y}_{\rho_{n}}\cap\mathcal{X}_{\rho_{0}}$

In particular, since $W_{0}$ lies in the set on the left-hand side, we have
$W_{0}\in\mathcal{Y}_{\rho_{n}}$.

Now, since $W_{0},W_{n}\in\mathcal{X}_{\sigma}$ and
$\rho_{n}=\rho(W_{0},W_{n})$, 2 gives that there is $\delta$ with
$W_{0},W_{n}\in\mathcal{X}_{\delta}$ such that $\rho_{n}$ is a permutation of
$\widehat{\sigma}\cdot\delta$. Recalling that
$W_{n}=W^{\prime}\in\mathcal{Y}_{\sigma}=\mathcal{Y}_{\widehat{\sigma}}$ by
assumption, we have
$W_{n}\in\mathcal{Y}_{\widehat{\sigma}}\cap\mathcal{X}_{\delta}$, i.e.
$B^{\widehat{\sigma}}\sqcup K^{\delta}$ is consistent. Applying _Inclusion-
vacuity_ once more, we get

$B^{\rho_{n}}=B^{\widehat{\sigma}\cdot\delta}=\operatorname{Cn}(B^{\widehat{\sigma}}\sqcup
K^{\delta})=\operatorname{Cn}(B^{\sigma}\sqcup K^{\delta})$

Taking models of both sides,

$\mathcal{Y}_{\rho_{n}}=\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\delta}\subseteq\mathcal{Y}_{\sigma}$

But we already saw that $W_{0}\in\mathcal{Y}_{\rho_{n}}$. Hence
$W_{0}\in\mathcal{Y}_{\sigma}$. Since $W_{0}=W$, we are done. ∎

To complete the proof we extend $\leq_{0}$ to a _total_ preorder and show that
this does not affect the minimal elements of each $\mathcal{X}_{\sigma}$.
Indeed, let $\leq$ be any total preorder extending $\leq_{0}$ and preserving
strict inequalities, i.e. $\leq$ such that  (i) $W\leq_{0}W^{\prime}$implies
$W\leq W^{\prime}$; and  (ii) $W<_{0}W^{\prime}$implies $W<W^{\prime}$.
161616 Such $\leq$ always exists. Indeed, note that $\leq_{0}$ induces a
partial order on the equivalence classes of $\mathcal{W}$ with respect to the
symmetric part of $\leq_{0}$ given by $W\simeq_{0}W^{\prime}$ iff
$W\leq_{0}W^{\prime}$ and $W^{\prime}\leq_{0}W$. This partial order can be
extended to a linear order $\leq^{*}$ on the equivalence classes. Taking
$W\leq W^{\prime}$ iff $[W]\leq^{*}[W^{\prime}]$, we obtain a total preorder
on $\mathcal{W}$ with the desired properties.

[1em]1em

######  Claim 5.

For any sequence $\sigma$,
$\mathcal{Y}_{\sigma}=\min_{\leq}{\mathcal{X}_{\sigma}}$

###### Proof.

Take any $\sigma$. For the left-to-right inclusion, take
$W\in\mathcal{Y}_{\sigma}$. Then $W\in\mathcal{X}_{\sigma}$. Let
$W^{\prime}\in\mathcal{X}_{\sigma}$. By 3, $WRW^{\prime}$, so
$W\leq_{0}W^{\prime}$ and $W\leq W^{\prime}$. Hence $W$ is $\leq$-minimal in
$\mathcal{X}_{\sigma}$.

For the right-to-left inclusion, take $W\in\min_{\leq}{\mathcal{X}_{\sigma}}$.
Then for any $W^{\prime}\in\mathcal{X}_{\sigma}$ we have $W\leq W^{\prime}$.
In particular, $W^{\prime}\not<W$. By property (ii) of $\leq$, we have
$W^{\prime}\not<_{0}W$. Since $W^{\prime}$ was an arbitrary member of
$\mathcal{X}_{\sigma}$ and $W\in\mathcal{X}_{\sigma}$, the conditions of 4 are
satisfied, and we get $W\in\mathcal{Y}_{\sigma}$. ∎

This shows that our operator is an elementary conditioning operator as
required.

“only if”: Now suppose the operator is an elementary conditioning operator.
i.e. there is a total preorder $\leq$ on $\mathcal{W}$ and a mapping
$\sigma\mapsto\langle{\mathcal{X}_{\sigma},\mathcal{Y}_{\sigma}}\rangle$ such
that for each $\sigma$, $\mathcal{Y}_{\sigma}=\min_{\leq}{X_{\sigma}}$,
$\mathcal{X}_{\sigma}$ and $\mathcal{Y}_{\sigma}$ are elementary, and
$K^{\sigma}$, $B^{\sigma}$ are determined by $\mathcal{X}_{\sigma}$,
$\mathcal{Y}_{\sigma}$ respectively according to Definition 1. By
elementariness and Lemma 1,
$\mathcal{X}_{\sigma}=\operatorname{mod}(K^{\sigma})$ and
$\mathcal{Y}_{\sigma}=\operatorname{mod}(B^{\sigma})$.

The following claim will be useful at various points.

[1em]1em

######  Claim 6.

Suppose $\sigma$ and $\rho$ are such that
$\mathcal{X}_{\sigma}=\mathcal{X}_{\rho}$. Then $K^{\sigma}=K^{\rho}$ and
$B^{\sigma}=B^{\rho}$.

###### Proof.

Since the total preorder $\leq$ is fixed, we have

$Y_{\sigma}=\min\nolimits_{\leq}{\mathcal{X}_{\sigma}}=\min\nolimits_{\leq}{\mathcal{X}_{\rho}}=\mathcal{Y}_{\rho}$

Now, $\mathcal{X}_{\sigma}=\mathcal{X}_{\rho}$ means
$\operatorname{mod}(K^{\sigma})=\operatorname{mod}(K^{\rho})$, so
$\operatorname{Cn}(K^{\sigma})=\operatorname{Cn}(K^{\rho})$. By _Closure_ ,
$K^{\sigma}=K^{\rho}$. Similarly, $\mathcal{Y}_{\sigma}=\mathcal{Y}_{\rho}$
gives $B^{\sigma}=B^{\rho}$. ∎

We take the postulates to be shown in turn.

  * •

_Rearrangement_ : Suppose $\sigma$ is a permutation of $\rho$. Without loss of
generality, $\sigma,\rho\neq\emptyset$. Repeated application of _K-
conjunction_ gives

$\mathcal{X}_{\sigma}=\bigcap_{\langle{i,c,\varphi}\rangle\in\sigma}{\mathcal{X}_{\langle{i,c,\varphi}\rangle}}$

Since $\sigma$ and $\rho$ contain exactly the same reports – just in a
different order – commutativity and associativity of intersection of sets
gives $\mathcal{X}_{\sigma}=\mathcal{X}_{\rho}$. _Rearrangement_ follows from
6.

  * •

_Duplicate-removal_ : Let $\sigma$, $\rho_{1}$ and $\rho_{2}$ be as in the
statement of _Duplicate-removal_. Then by _K-conjunction_ ,

$\displaystyle\mathcal{X}_{\rho_{2}}$
$\displaystyle=\mathcal{X}_{\rho_{1}\cdot\langle{i,c,\varphi}\rangle}$
$\displaystyle=\mathcal{X}_{\rho_{1}}\cap\mathcal{X}_{\langle{i,c,\varphi}\rangle}$
$\displaystyle=\mathcal{X}_{\sigma\cdot\langle{i,c,\varphi}\rangle}\cap\mathcal{X}_{\langle{i,c,\varphi}\rangle}$
$\displaystyle=\mathcal{X}_{\sigma}\cap\mathcal{X}_{\langle{i,c,\varphi}\rangle}\cap\mathcal{X}_{\langle{i,c,\varphi}\rangle}$
$\displaystyle=\mathcal{X}_{\sigma}\cap\mathcal{X}_{\langle{i,c,\varphi}\rangle}$
$\displaystyle=\mathcal{X}_{\rho_{1}}$

and we may conclude by 6.

  * •

_Conditional-consistency_ : Suppose $K^{\sigma}$ is consistent, i.e.
$\mathcal{X}_{\sigma}\neq\emptyset$. Since $\mathcal{W}$ is finite,
$\mathcal{X}_{\sigma}$ is finite and thus some $\leq$-minimal world must exist
in $\mathcal{X}_{\sigma}$. Hence $\mathcal{Y}_{\sigma}\neq\emptyset$, so
$B^{\sigma}$ is consistent.

  * •

_Inclusion-vacuity_ : Take any sequences $\sigma$, $\rho$. First we show
$B^{\sigma\cdot\rho}\sqsubseteq\operatorname{Cn}(B^{\sigma}\sqcup K^{\rho})$,
or equivalently,
$\mathcal{Y}_{\sigma\cdot\rho}\supseteq\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\rho}$.
Suppose $W\in\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\rho}$. Since
$\mathcal{Y}_{\sigma}\subseteq\mathcal{X}_{\sigma}$, we have
$W\in\mathcal{X}_{\sigma}\cap\mathcal{X}_{\rho}=\mathcal{X}_{\sigma\cdot\rho}$
by _K-conjunction_. We need to show $W$ is minimal. Take any
$W^{\prime}\in\mathcal{X}_{\sigma\cdot\rho}$. Then
$W^{\prime}\in\mathcal{X}_{\sigma}$, so
$W\in\mathcal{Y}_{\sigma}=\min_{\leq}{\mathcal{X}_{\sigma}}$ gives $W\leq
W^{\prime}$. Hence
$W\in\min_{\leq}{X_{\sigma\cdot\rho}}=\mathcal{Y}_{\sigma\cdot\rho}$.

Now suppose $B^{\sigma}\sqcup K^{\rho}$ is consistent, i.e.
$\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\rho}\neq\emptyset$. Take some
$\widehat{W}\in\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\rho}$. We need to show
$B^{\sigma\cdot\rho}\sqsupseteq\operatorname{Cn}(B^{\sigma}\sqcup K^{\rho})$,
i.e.
$\mathcal{Y}_{\sigma\cdot\rho}\subseteq\mathcal{Y}_{\sigma}\cap\mathcal{X}_{\rho}$.
To that end, let $W\in\mathcal{Y}_{\sigma\cdot\rho}$. Then
$W\in\mathcal{X}_{\sigma\cdot\rho}=\mathcal{X}_{\sigma}\cap\mathcal{X}_{\rho}\subseteq\mathcal{X}_{\rho}$,
so we only need to show $W\in\mathcal{Y}_{\sigma}$. Take any
$W^{\prime}\in\mathcal{X}_{\sigma}$. Then $\widehat{W}\in\mathcal{Y}_{\sigma}$
gives $\widehat{W}\leq W^{\prime}$. But
$\widehat{W}\in\mathcal{X}_{\sigma}\cap\mathcal{X}_{\rho}=\mathcal{X}_{\sigma\cdot\rho}$
and $W\in\mathcal{Y}_{\sigma\cdot\rho}$ gives $W\leq\widehat{W}$. By
transitivity of $\leq$, we have $W\leq W^{\prime}$. Hence
$W\in\min_{\leq}{\mathcal{X}_{\sigma}}=\mathcal{Y}_{\sigma}$.

  * •

_Acyc_ : Let $\sigma_{0},\ldots,\sigma_{n}$ be as in the statement of _Acyc_.
Without loss of generality, $n>0$. Then there are $W_{0},\ldots,W_{n}$ such
that

$\displaystyle W_{j}$
$\displaystyle\in\mathcal{X}_{\sigma_{j}}\cap\mathcal{Y}_{\sigma_{j+1}}\qquad(0\leq
j<n)$ $\displaystyle W_{n}$
$\displaystyle\in\mathcal{X}_{\sigma_{n}}\cap\mathcal{Y}_{\sigma_{0}}$

Note that $W_{j}\in\mathcal{X}_{\sigma_{j}}$ for all $j$. For $j<n$, we also
have $W_{j}\in\mathcal{Y}_{\sigma_{j+1}}=\min_{\leq}{X_{\sigma_{j+1}}}$. It
follows that $W_{j}\leq W_{j+1}$ for such $j$, so

$W_{0}\leq\cdots\leq W_{n}$

But we also have
$W_{n}\in\mathcal{Y}_{\sigma_{0}}=\min_{\leq}{\mathcal{X}_{\sigma_{0}}}$ and
$W_{0}\in\mathcal{X}_{\sigma_{0}}$, so $W_{n}\leq W_{0}$. By transitivity of
$\leq$, the chain flattens: we have

$W_{0}\simeq\cdots\simeq W_{n}$

Now note that since $W_{n-1}\in\mathcal{Y}_{\sigma_{n}}$, $W_{n-1}$ is minimal
in $\mathcal{X}_{\sigma_{n}}$. But $W_{n}\in\mathcal{X}_{\sigma_{n}}$ and
$W_{n-1}\simeq W_{n}$ by the above, so in fact
$W_{n}\in\mathcal{Y}_{\sigma_{n}}$ too. Hence

$\displaystyle W_{n}$
$\displaystyle\in\mathcal{Y}_{\sigma_{0}}\cap\mathcal{Y}_{\sigma_{n}}$
$\displaystyle\subseteq\mathcal{X}_{\sigma_{0}}\cap\mathcal{Y}_{\sigma_{n}}$
$\displaystyle=\operatorname{mod}(K^{\sigma_{0}}\sqcup B^{\sigma_{n}})$

i.e. $K^{\sigma_{0}}\sqcup B^{\sigma_{n}}$ is consistent, as required for
_Acyc_.

∎

###  A.8 Proof of Proposition 6

###### Proof.

We use the characterisation of elementary sets from Proposition 2. Take
$S\subseteq\mathcal{W}$ elementary. Suppose $W\in\mathcal{W}$,
$W_{1},W_{2}\in\min_{\leq}{S}$ are such that $W$ is partition-equivalent to
both $W_{1},W_{2}$ and $W$ is a valuation combination from
$\\{W_{1},W_{2}\\}$. By hypothesis we have $W\simeq W_{1}\simeq W_{2}$.

Now since $\min_{\leq}{S}\subseteq S$, we have $W_{1},W_{2}\in S$. Since $S$
is elementary, $W\in S$. But now $W\simeq W_{1}$ and $W_{1}\in\min_{\leq}{S}$
gives $W\in\min_{\leq}{S}$. This shows the required closure property for
$\min_{\leq}{S}$, and we are done. ∎

###  A.9 Proof of Proposition 7

###### Proof.

Suppose an operator with _K-conjunction_ is an elementary conditioning
operator corresponding to some mapping
$\sigma\mapsto\langle{\mathcal{X}_{\sigma},\mathcal{Y}_{\sigma}}\rangle$ and
total preorder $\leq$, i.e. where $\mathcal{X}_{\sigma}$ and
$\mathcal{Y}_{\sigma}$ are elementary and
$\mathcal{Y}_{\sigma}=\min_{\leq}{\mathcal{X}_{\sigma}}$ for any $\sigma$.
Write

$k(W)=|\\{W^{\prime}\in\mathcal{W}\mid W^{\prime}\leq W\\}|$

Then we have $W\leq W^{\prime}$ iff $k(W)\leq k(W^{\prime})$. Set

$r_{0}(W)=\begin{cases}\infty,&W\notin\mathcal{X}_{\emptyset}\\\
k(W),&W\in\mathcal{X}_{\emptyset}\end{cases}$

and

$d(W,\langle{i,c,\varphi}\rangle)=\begin{cases}\infty,&W\notin\mathcal{X}_{\langle{i,c,\varphi}\rangle}\\\
0,&W\in\mathcal{X}_{\langle{i,c,\varphi}\rangle}\\\ \end{cases}$

For the empty sequence, we clearly have $r_{\emptyset}(W)<\infty$ iff
$W\in\mathcal{X}_{\emptyset}$. By construction of $r_{0}$ we also have
$\operatorname{argmin}_{W\in\mathcal{X}_{\emptyset}}{r_{\emptyset}(W)}=\min_{\leq}{X_{\emptyset}}=\mathcal{Y}_{\emptyset}$.

Now take any sequence $\sigma\neq\emptyset$. By elementariness and Lemma 1, we
have $\operatorname{mod}(K^{\rho})=\mathcal{X}_{\rho}$ for any $\rho$.
Repeated applications of _K-conjunction_ therefore gives

$\mathcal{X}_{\sigma}=\bigcap_{\langle{i,c,\varphi}\rangle\in\sigma}{\mathcal{X}_{\langle{i,c,\varphi}\rangle}}$

We also have
$\mathcal{X}_{\sigma}=\mathcal{X}_{\sigma\cdot\rho}=\mathcal{X}_{\sigma}\cap\mathcal{X}_{\emptyset}\subseteq\mathcal{X}_{\emptyset}$.
Since $r_{0}(W)<\infty$ iff $W\in\mathcal{X}_{\emptyset}$ and
$d(W,\langle{i,c,\varphi}\rangle)<\infty$ iff
$W\in\mathcal{X}_{\langle{i,c,\varphi}\rangle}$, it follows that
$r_{\sigma}(W)<\infty$ iff $W\in\mathcal{X}_{\sigma}$.

Finally, note that if $W\in\mathcal{X}_{\sigma}$ then
$r_{\sigma}(W)=r_{0}(W)$. Hence
$\operatorname{argmin}_{W\in\mathcal{X}_{\sigma}}{r_{\sigma}(W)}=\operatorname{argmin}_{W\in\mathcal{X}_{\sigma}}{r_{0}(W)}=\min_{\leq}{\mathcal{X}_{\sigma}}=\mathcal{Y}_{\sigma}$,
and the operator is score-based. ∎

###  A.10 Proof of Proposition 8

We require some preliminary results. For a case $c\in\mathcal{C}$ and
valuation $v\in\mathcal{V}$, write $\mathcal{W}_{c\ :\
v}=\\{W\in\mathcal{W}\mid v^{W}_{c}=v\\}$ for the set of worlds whose $c$
valuation is $v$.

######  Lemma 2.

For any model-based operator, sequence $\sigma$, case $c$, and valuation $v\
in\mathcal{V}$,

$v\in\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]\iff\mathcal{Y}_{\sigma}\cap\mathcal{W}_{c\
:\ v}\neq\emptyset$

###### Proof.

“$\implies$”: We show the contrapositive. Suppose
$\mathcal{Y}_{\sigma}\cap\mathcal{W}_{c\ :\ v}=\emptyset$. Let $\psi$ be any
propositional formula such that
$\operatorname{mod}_{0}(\psi)=\mathcal{V}\setminus\\{v\\}$. Now for any
$W\in\mathcal{Y}_{\sigma}$, we have $W\notin\mathcal{W}_{c\ :\ v}$, i.e.
$v^{W}_{c}\neq v$. Hence $v^{W}_{c}\in\operatorname{mod}_{0}(\psi)$, so
$W,c\models\psi$. By definition of the belief set of a model-based operator,
we have $\psi\in B^{\sigma}_{c}$. But $\psi$ is a propositional formula, so
$\psi\in\left[{B^{\sigma}_{c}}\right]$. Since
$v\notin\operatorname{mod}_{0}(\psi)$, we have
$v\notin\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]$.

“$\impliedby$”: Suppose there is some
$W\in\mathcal{Y}_{\sigma}\cap\mathcal{W}_{c\ :\ v}$. Let
$\varphi\in\left[{B^{\sigma}_{c}}\right]$. Then, in particular, $\varphi\in
B^{\sigma}_{c}$, so $W,c\models\varphi$ by $W\in\mathcal{Y}_{\sigma}$ and the
definition of the model-based belief set. That is,
$v=v^{W}_{c}\in\operatorname{mod}_{0}(\varphi)$. Since
$\varphi\in\left[{B^{\sigma}_{c}}\right]$ was arbitrary, we have
$v\in\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]$.

∎

We have a sufficient condition for _AGM- $\ast$_ for score-based operators.

######  Lemma 3.

Suppose a score-based operator is such that for each $c\in\mathcal{C}$ and
$\varphi\in\mathcal{L}{}_{0}$ there is a constant $M\in\mathbb{N}$ with

$d(W,\langle{\ast,c,\varphi}\rangle)=\begin{cases}M,&W,c\models\varphi\\\
\infty,&W,c\models\neg\varphi\end{cases}$

for all $W$. Then _AGM- $\ast$_ holds.

###### Proof.

Take a score-based operator with the stated property. Let $\sigma$ be a
sequence and take $c\in\mathcal{C}$. Without loss of generality, there is some
$\varphi\in\mathcal{L}{}_{0}$ such that $\neg\varphi\notin K^{\sigma}_{c}$
(otherwise _AGM- $\ast$_ trivially holds). Since any score-based operator is
model-based and therefore satisfies _Closure_ , we have that $K^{\sigma}$ is
inconsistent iff $K^{\sigma}_{c}=\mathcal{L}{}$. But since $K^{\sigma}_{c}$
does not contain $\neg\varphi$, it must be the case that $K^{\sigma}$ is
consistent.

Now, set

$k(v)=\min\\{r_{\sigma}(W)\mid W\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\
v}\\}$

where $\min\emptyset=\infty$. Note that $k(v)=\infty$ if and only if
$\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ v}=\emptyset$. Then $k$ defines a
total preorder $\preceq$ on valuations, where $v\preceq v^{\prime}$ iff
$k(v)\leq k(v^{\prime})$. Define a propositional revision operator $\star$ for
$\left[{B^{\sigma}_{c}}\right]$ by

$\left[{B^{\sigma}_{c}}\right]\star\varphi=\\{\psi\in\mathcal{L}{}_{0}\mid\min\nolimits_{\preceq}{\operatorname{mod}_{0}(\varphi)}\subseteq\operatorname{mod}_{0}(\psi)\\}$

To show that $\star$ satisfies the AGM postulates (for
$\left[{B^{\sigma}_{c}}\right]$) it is sufficient to show that the models of
$\left[{B^{\sigma}_{c}}\right]$ are exactly the $\preceq$-minimal valuations.

[1em]1em

######  Claim 7.

$\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]=\min_{\preceq}{\mathcal{V}}$.

###### Proof.

“$\subseteq$”: let $v\in\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]$.
By Lemma 2, there is some $W\in\mathcal{Y}_{\sigma}\cap\mathcal{W}_{c\ :\ v}$.
Since $W\in\mathcal{X}_{\sigma}$ too, by definition of $k$ we have $k(v)\leq
r_{\sigma}(W)<\infty$. Now let $v^{\prime}\in\mathcal{V}$. Without loss of
generality assume $k(v^{\prime})<\infty$. Then there is some
$W^{\prime}\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ v^{\prime}}$ such
that $k(v^{\prime})=r_{\sigma}(W^{\prime})$. But
$W^{\prime}\in\mathcal{X}_{\sigma}$ and $W\in\mathcal{Y}_{\sigma}$ gives
$r_{\sigma}(W)\leq r_{\sigma}(W^{\prime})$, so

$k(v)\leq r_{\sigma}(W)\leq r_{\sigma}(W^{\prime})=k(v^{\prime})$

i.e. $v\preceq v^{\prime}$. Hence $v$ is $\preceq$-minimal.

“$\supseteq$”: let $v\in\min_{\preceq}\mathcal{V}$. Since $K^{\sigma}$ is
consistent, there is some $\hat{W}\in\mathcal{X}_{\sigma}$. Writing
$\hat{v}=v^{\hat{W}}_{c}$, we have
$\hat{W}\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ \hat{v}}$, so
$v\preceq\hat{v}$ implies

$k(v)\leq k(\hat{v})\leq r_{\sigma}(\hat{W})<\infty$

Hence there must be some $W\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ v}$
such that $k(v)=r_{\sigma}(W)$. We claim that, in fact,
$W\in\mathcal{Y}_{\sigma}$. Indeed, for any
$W^{\prime}\in\mathcal{X}_{\sigma}$ we have $v\preceq v^{W^{\prime}}_{c}$, so

$r_{\sigma}(W)=k(v)\leq k(v^{W^{\prime}}_{c})\leq r_{\sigma}(W^{\prime})$

That is, $W\in\mathcal{Y}_{\sigma}\cap\mathcal{W}_{c\ :\ v}$. By Lemma 2,
$v\in\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]$.

∎

So, $\star$ is indeed an AGM operator for $\left[{B^{\sigma}_{c}}\right]$. Now
take $\varphi\in\mathcal{L}{}_{0}$ such that $\neg\varphi\notin
K^{\sigma}_{c}$. Write $\rho=\sigma\cdot\langle{\ast,c,\varphi}\rangle$. We
claim the following.

[1em]1em

######  Claim 8.

$\operatorname{mod}_{0}\left[{B^{\rho}_{c}}\right]=\min\nolimits_{\preceq}{\operatorname{mod}_{0}(\varphi)}$.

###### Proof.

“$\subseteq$”: let $v\in\operatorname{mod}_{0}\left[{B^{\rho}_{c}}\right]$. By
Lemma 2 again, there is some $W\in\mathcal{Y}_{\rho}\cap\mathcal{W}_{c\ :\
v}$. Since $\langle{\ast,c,\varphi}\rangle\in\rho$ and
$d(W,\langle{\ast,c,\varphi}\rangle)\leq r_{\rho}(W)<\infty$, we must have
$W,c\models\varphi$ by the assumed property of the score function $d$. Hence
$v=v^{W}_{c}\in\operatorname{mod}_{0}(\varphi)$.

Now since $\mathcal{Y}_{\rho}\subseteq\mathcal{X}_{\rho}$, we have
$W\in\mathcal{Y}_{\rho}\subseteq\mathcal{X}_{\rho}\subseteq\mathcal{X}_{\sigma}$,
so $W\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ v}$. By definition of $k$,
we have $k(v)\leq r_{\sigma}(W)$. Take any
$v^{\prime}\in\operatorname{mod}_{0}(\varphi)$. Without loss of generality,
assume $k(v^{\prime})<\infty$, so that there is some
$W^{\prime}\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ v^{\prime}}$ with
$k(v^{\prime})=r_{\sigma}(W^{\prime})$. Since
$v^{W^{\prime}}_{c}=v^{\prime}\in\operatorname{mod}_{0}(\varphi)$, we have
$W^{\prime},c\models\varphi$. Consequently, by the property of $d$ again,
$d(W^{\prime},\langle{\ast,c,\varphi}\rangle)=M$. Since
$W^{\prime}\in\mathcal{X}_{\sigma}$ gives $r_{\sigma}(W^{\prime})<\infty$, it
follows that

$r_{\rho}(W^{\prime})=r_{\sigma}(W^{\prime})+M<\infty$

so $W^{\prime}\in\mathcal{X}_{\rho}$.

Recall that $W,c\models\varphi$ too, so
$d(W,\langle{\ast,c,\varphi}\rangle)=M$ also. From $W\in\mathcal{Y}_{\rho}$
and $W^{\prime}\in\mathcal{X}_{\rho}$ we get

$\displaystyle r_{\sigma}(W)$ $\displaystyle=r_{\rho}(W)-M$ $\displaystyle\leq
r_{\rho}(W^{\prime})-M$
$\displaystyle=r_{\rho}(W^{\prime})-d(W^{\prime},\langle{\ast,c,\varphi}\rangle)$
$\displaystyle=r_{\sigma}(W^{\prime})$

This yields

$k(v)\leq r_{\sigma}(W)\leq r_{\sigma}(W^{\prime})=k(v^{\prime})$

and $v\preceq v^{\prime}$ as required.

“$\supseteq$”: let $v\in\min_{\preceq}{\operatorname{mod}_{0}(\varphi)}$.
Since $\neg\varphi\notin K^{\sigma}_{c}$, there is some
$\hat{W}\in\mathcal{X}_{\sigma}$ such that $\hat{W},c\models\varphi$. Writing
$\hat{v}=v^{\hat{W}}_{c}$, we have
$\hat{v}\in\operatorname{mod}_{0}(\varphi)$. Hence $v\preceq\hat{v}$. This
implies

$k(v)\leq k(\hat{v})\leq r_{\sigma}(\hat{W})<\infty$

so there must be some $W\in\mathcal{X}_{\sigma}\cap\mathcal{W}_{c\ :\ v}$ with
$k(v)=r_{\sigma}(W)$. Since $v^{W}_{c}=v\in\operatorname{mod}_{0}(\varphi)$,
we have $W,c\models\varphi$. By the assumed property of $d$, we get
$d(W,\langle{\ast,c,\varphi}\rangle)=M$. Hence

$r_{\rho}(W)=r_{\sigma}(W)+d(W,\langle{\ast,c,\varphi}\rangle)=r_{\sigma}(W)+M<\infty$

so $W\in\mathcal{X}_{\rho}$ too. We will show that $W\in\mathcal{Y}_{\rho}$.
Let $W^{\prime}\in\mathcal{X}_{\rho}$. Then we must have
$d(W^{\prime},\langle{\ast,c,\varphi}\rangle)=M$ and
$W^{\prime},c\models\varphi$. That is,
$v^{W^{\prime}}_{c}\in\operatorname{mod}_{0}(\varphi)$. By minimality of $v$,
we have $v\preceq v^{W^{\prime}}_{c}$. Noting that
$W^{\prime}\in\mathcal{X}_{\rho}\subseteq\mathcal{X}_{\sigma}$, we get

$r_{\sigma}(W)=k(v)\leq k(v^{W^{\prime}}_{c})\leq r_{\sigma}(W^{\prime})$

Consequently,

$r_{\rho}(W)=r_{\sigma}(W)+M\leq
r_{\sigma}(W^{\prime})+M=r_{\rho}(W^{\prime})$

This shows $W\in\mathcal{Y}_{\rho}$, i.e.
$\mathcal{Y}_{\rho}\cap\mathcal{W}_{c\ :\ v}\neq\emptyset$. By Lemma 2, we are
done.

∎

Noting that
$\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]\star\varphi=\min_{\preceq}{\operatorname{mod}_{0}(\varphi)}$,
it follows from 8 that
$\operatorname{Cn}_{0}(\left[{B^{\rho}_{c}}\right])=\operatorname{Cn}_{0}(\left[{B^{\sigma}_{c}}\right]\star\varphi)$.
But $\left[{B^{\rho}_{c}}\right]$ is deductively closed by _Closure_ , and
$\left[{B^{\sigma}_{c}}\right]\star\varphi$ is deductively closed by
construction. Hence
$\left[{B^{\rho}_{c}}\right]=\left[{B^{\sigma}_{c}}\right]\star\varphi$, as
required for _AGM- $\ast$_.

∎

As a consequence of Proposition 7 (and the construction of $d$ in its proof),
one can apply Lemma 3 with $M=0$ for conditioning operators with _K-
conjunction_ and a certain natural property.

######  Corollary 1.

Suppose an elementary conditioning operator satisfying _K-conjunction_ has the
property that

$W\in\mathcal{X}_{\langle{\ast,c,\varphi}\rangle}\iff W,c\models\varphi$

Then _AGM- $\ast$_ holds.

We can now prove Proposition 8.

###### Proof of Proposition 8.

For the conditioning operators $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$, it is easily verified that the
condition in Corollary 1 holds, and thus _AGM- $\ast$_ does also.

For the score-based operator $\mathsf{excess\text{-}min}$, we may use Lemma 3
with $M=0$. ∎

###  A.11 Proof of Proposition 9

As a first step in the proof, we present sufficient conditions for
conditioning operators to satisfy _Cond-success_. In fact, we do not need to
impose any condition on the total preorder $\leq$: a natural constraint on the
mapping $\sigma\mapsto\mathcal{X}_{\sigma}$ (together with some basic
postulates) is enough.

######  Lemma 4.

Suppose an elementary conditioning operator satisfies _K-conjunction_ ,
_Soundness_ and

$W,c\models\varphi\implies W\in\mathcal{X}_{\langle{i,c,\varphi}\rangle}$

Then _Cond-success_ holds.

###### Proof.

Suppose an elementary conditioning operator corresponding to the mapping
$\sigma\mapsto\langle{\mathcal{X}_{\sigma},\mathcal{Y}_{\sigma}}\rangle$ and
total preorder $\leq$ satisfies _K-conjunction_ , _Soundness_ and has the
stated property.

Let $\sigma$ be a sequence and $c\in\mathcal{C}$. Suppose $E_{i}(\varphi)\in
B^{\sigma}_{c}$ and $\neg\varphi\notin B^{\sigma}_{c}$. Write
$\rho=\sigma\cdot\langle{i,c,\varphi}\rangle$. We need to show $\varphi\in
B^{\rho}_{c}$.

By $\neg\varphi\notin B^{\sigma}_{c}$, there is some
$W\in\mathcal{Y}_{\sigma}$ such that $W,c\models\varphi$. Hence
$W\in\mathcal{X}_{\langle{i,c,\varphi}\rangle}$. By elementariness and _K-
conjunction_ , we have
$\mathcal{X}_{\rho}=\mathcal{X}_{\sigma}\cap\mathcal{X}_{\langle{i,c,\varphi}\rangle}$.
Since $W\in\mathcal{Y}_{\sigma}\subseteq\mathcal{X}_{\sigma}$, we get
$W\in\mathcal{X}_{\rho}$.

Now take any $W^{\prime}\in\mathcal{Y}_{\rho}$. Then $W^{\prime}$ is
$\leq$-minimal in $\mathcal{X}_{\rho}$, so $W^{\prime}\leq W$. But $W$ is
$\leq$-minimal in $\mathcal{X}_{\sigma}$, so
$W^{\prime}\in\mathcal{Y}_{\rho}\subseteq\mathcal{X}_{\rho}\subseteq\mathcal{X}_{\sigma}$
gives $W^{\prime}\in\mathcal{Y}_{\sigma}$ also. Consequently,
$E_{i}(\varphi)\in B^{\sigma}_{c}$ means $W^{\prime},c\models E_{i}(\varphi)$.
On the other hand, _Soundness_ together with
$\langle{i,c,\varphi}\rangle\in\rho$ and $W^{\prime}\in\mathcal{X}_{\rho}$
means $W^{\prime},c\models S_{i}(\varphi)$. Hence $W^{\prime},c\models
E_{i}(\varphi)\land S_{i}(\varphi)$. From Proposition 1 part (4), we get
$W^{\prime},c\models\varphi$.

We have shown that $\varphi$ holds in case $c$ at an arbitrary world in
$\mathcal{Y}_{\rho}$. Hence $\varphi\in B^{\rho}_{c}$, as required.

∎

Similarly, we have sufficient conditioning for score-based operators to
satisfy _Strong-cond-success_ : the postulate follows if worlds in which $i$
makes a expert, truthful report are strictly more plausible than worlds in
which $i$ makes a false report.

######  Lemma 5.

Suppose a score-based operator is such that for any $i\in\mathcal{S}$,
$c\in\mathcal{C}$, $\varphi\in\mathcal{L}{}_{0}$ and
$W,W^{\prime}\in\mathcal{W}$,

$\displaystyle W,c$ $\displaystyle\models E_{i}(\varphi)\land\varphi\text{ and
}W^{\prime},c\models\neg\varphi$ $\displaystyle\implies
d(W,\langle{i,c,\varphi}\rangle)<d(W^{\prime},\langle{i,c,\varphi}\rangle)$

Then _Strong-cond-success_ holds.

###### Proof.

Suppose a score-based operator has the stated property. Take $\sigma$ such
that $\neg(E_{i}(\varphi)\land\varphi)\notin B^{\sigma}_{c}$. Write
$\rho=\sigma\cdot\langle{i,c,\varphi}\rangle$. We need to show that
$\varphi\in B^{\rho}_{c}$.

First note that by $\neg(E_{i}(\varphi)\land\varphi)\notin B^{\sigma}_{c}$ and
the definition of $B^{\sigma}$ for score-based operators, there is
$W\in\mathcal{Y}_{\sigma}$ such that $W,c\models E_{i}(\varphi)\land\varphi$.

Take any $W^{\prime}\in\mathcal{Y}_{\rho}$. Suppose, for the sake of
contradiction, that $W^{\prime},c\not\models\varphi$. Then by the hypothesised
property of the score function $d$, we have

$d(W,\langle{i,c,\varphi}\rangle)<d(W^{\prime},\langle{i,c,\varphi}\rangle)$

Now, $W\in\mathcal{Y}_{\sigma}$ and
$W^{\prime}\in\mathcal{Y}_{\rho}\subseteq\mathcal{X}_{\rho}\subseteq\mathcal{X}_{\sigma}$
gives $r_{\sigma}(W)\leq r_{\sigma}(W^{\prime})$. Thus

$\displaystyle r_{\rho}(W)$
$\displaystyle=r_{\sigma}(W)+d(W,\langle{i,c,\varphi}\rangle)$
$\displaystyle\leq r_{\sigma}(W^{\prime})+d(W,\langle{i,c,\varphi}\rangle)$
$\displaystyle<r_{\sigma}(W^{\prime})+d(W^{\prime},\langle{i,c,\varphi}\rangle)$
$\displaystyle=r_{\rho}(W^{\prime})<\infty$

i.e. $r_{\rho}(W)<r_{\rho}(W^{\prime})<\infty$. But this means
$W\in\mathcal{X}_{\rho}$ and $W^{\prime}$ is not minimal in
$\mathcal{X}_{\rho}$ under $r_{\rho}$, contradicting
$W^{\prime}\in\mathcal{Y}_{\rho}$. Hence $W^{\prime},c\models\varphi$.

Since $W^{\prime}$ was an arbitrary member of $\mathcal{Y}_{\rho}$, we have
shown $\varphi\in B^{\rho}_{c}$, and thus _Strong-cond-success_ is shown. ∎

The main result now follows.

###### Proof of Proposition 9.

For the conditioning operators $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$, _Cond-success_ follows from Lemma 4
since $W,c\models\varphi$ implies $W,c\models S_{i}(\varphi)$. For the score-
based operator $\mathsf{excess\text{-}min}$, one can easily check that the
condition in Lemma 5 holds, and thus _Strong-cond-success_ and _Cond-success_
follow. ∎

###  A.12 Proof of Proposition 10

###### Proof.

Take distinct sources $i_{1},i_{2}\in\mathcal{S}\setminus\\{\ast\\}$, distinct
cases $c,d\in\mathcal{C}$, and distinct valuations
$v_{1},v_{2}\in\mathcal{V}$. Let $\varphi_{1},\varphi_{2}\in\mathcal{L}{}_{0}$
be propositional formulas with $\operatorname{mod}_{0}(\varphi_{k})=v_{k}$
($k\in\\{1,2\\}$). Suppose for contradiction that some elementary conditioning
operator – satisfying the basic postulates – has the stated properties.

Define a sequence

$\sigma=(\langle{\ast,c,\varphi_{1}\lor\varphi_{2}}\rangle,\langle{i_{1},c,\varphi_{1}}\rangle,\langle{i_{2},c,\varphi_{2}}\rangle).$

Let $\Pi_{\bot}$ denote the unit partition $\\{\\{u\\}\mid
u\in\mathcal{V}\\}$, and let $\widehat{\Pi}$ denote the partition

$\\{\\{v_{1},v_{2}\\}\\}\cup\\{\\{u\\}\mid
u\in\mathcal{V}\setminus\\{v_{1},v_{2}\\}\\},$

i.e. the partition obtained from $\Pi_{\bot}$ by merging the cells of $v_{1}$
and $v_{2}$.

Consider worlds $W_{1}$, $W_{2}$ given by

$\displaystyle v^{W_{k}}_{c^{\prime}}$
$\displaystyle=v_{k}\qquad(c^{\prime}\in\mathcal{C})$
$\displaystyle\Pi^{W_{k}}_{i}$
$\displaystyle=\begin{cases}\widehat{\Pi},&(k=1\text{ and }i=i_{2})\text{ or
}(k=2\text{ and }i=i_{1})\\\ \Pi_{\bot},&\text{ otherwise }\end{cases}$

That is, $W_{1}$ has $v_{1}$ as its valuation for all cases, $i_{2}$ has
partition $\widehat{\Pi}$, and all other sources have the finest partition
$\Pi_{\bot}$; similarly $W_{2}$ has $v_{2}$ for its valuations and all sources
except $i_{1}$ have $\Pi_{\bot}$.

Let $\leq$ denote the total preorder associated with the conditioning
operator.

[1em]1em

######  Claim 9.

$W_{1}\simeq W_{2}$.

###### Proof.

Let $\pi$ be the permutation of $\mathcal{S}$ which swaps $i_{1}$ and $i_{2}$.
It is easily observed that $\pi(W_{1})$ is partition-equivalent to $W_{2}$. By
reflexivity of partition refinement, $\pi(W_{1})\preceq W_{2}$ and
$W_{2}\preceq\pi(W_{1})$. By _Refinement_ , we get $\pi(W_{1})\simeq W_{2}$.
By property (2), $W_{1}\simeq\pi(W_{1})$. By transitivity of ${\simeq}$ we get
$W_{1}\simeq W_{2}$ as desired. ∎

Now, from the basic postulates, property (1) and Proposition 3 we have
$K^{\sigma}=\operatorname{Cn}(G^{\sigma}_{\mathsf{snd}})$. By elementariness
and Lemma 1, we get
$\mathcal{X}_{\sigma}=\operatorname{mod}(K^{\sigma})=\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$.
It is easily checked that both $W_{1}$ and $W_{2}$ satisfy the soundness
statements corresponding to $\sigma$, and thus
$W_{1},W_{2}\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})=\mathcal{X}_{\sigma}$.

[1em]1em

######  Claim 10.

$W_{1},W_{2}\in\mathcal{Y}_{\sigma}$.

###### Proof.

We show $W_{1}$ and $W_{2}$ are $\leq$-minimal in $\mathcal{X}_{\sigma}$. Take
any $W\in\mathcal{X}_{\sigma}$. Then
$W\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$, so $W,c\models
S_{\ast}(\varphi_{1}\lor\varphi_{2})$, i.e. $V^{W}_{c}\in\\{v_{1},v_{2}\\}$.
We consider two cases.

  * •

Case 1 ($v^{W}_{c}=v_{1}$). By
$W\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$ again we have $W,c\models
S_{i_{2}}(\varphi_{2})$, i.e

$v_{1}=v^{W}_{c}\in\Pi^{W}_{i_{2}}[\varphi_{2}]=\Pi^{W}_{i_{2}}[v_{2}].$

It follows that $\\{v_{1},v_{2}\\}\subseteq\Pi^{W}_{i_{2}}[v_{2}]$, and that
$\widehat{\Pi}$ refines $\Pi^{W}_{i_{2}}$. Since $\widehat{\Pi}$ is the
partition of $i_{2}$ in $W_{1}$, and all other sources have the finest
partition $\Pi_{\bot}$, we get $W_{1}\preceq W$. By _Refinement_ , $W_{1}\leq
W$. Since $W_{1}\simeq W_{2}$ we have $W_{2}\leq W$ also.

  * •

Case 2 ($v^{W}_{c}=v_{2}$). Applying a near-identical argument to that used in
case 1 with soundness of the report $\langle{i_{1},c,\varphi_{1}}\rangle$, we
get $W_{1},W_{2}\leq W$.

In either case, both $W_{1}\leq W$ and $W_{2}\leq W$, so
$W_{1},W_{2}\in\mathcal{Y}_{\sigma}$. ∎

Now we consider case $d$. Since

$W_{1},d\models E_{i_{1}}(\varphi_{1})\land\varphi_{1}$

and $W_{1}\in\mathcal{Y}_{\sigma}$,
$\neg(E_{i_{1}}(\varphi_{1})\land\varphi_{1})\notin B^{\sigma}_{d}$. Writing
$\rho=\sigma\cdot\langle{i_{1},d,\varphi_{1}}\rangle$, we get from _Strong-
cond-success_ that $\varphi_{1}\in B^{\rho}_{d}$.

Note that $W_{2},d\models S_{i_{1}}(\varphi_{1})$, so
$W_{2}\in\operatorname{mod}(G^{\rho}_{\mathsf{snd}})=\operatorname{mod}(K^{\rho})=\mathcal{X}_{\rho}$.
Since $W_{2}$ is $\leq$-minimal in $\mathcal{X}_{\sigma}$ and

$X_{\rho}=\operatorname{mod}(G^{\rho}_{\mathsf{snd}})\subseteq\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})=\mathcal{X}_{\sigma},$

$W_{2}$ is also $\leq$-minimal in $\mathcal{X}_{\rho}$, i.e.
$W_{2}\in\mathcal{Y}_{\rho}$. Now $\varphi_{1}\in B^{\rho}_{d}$ gives
$W_{2},d\models\varphi_{1}$. Since $v^{W_{2}}_{d}=v_{2}$ and
$\operatorname{mod}_{0}(\varphi_{1})=\\{v_{1}\\}$, this means $v_{1}=v_{2}$.
But $v_{1}$ and $v_{2}$ were assumed to be distinct: contradiction.

∎

###  A.13 Proof of Theorem 3

###### Proof.

“if”: Suppose a model-based operator satisfies _Boundedness_. Take any
$\ast$-consistent $\sigma$. For $c\in\mathcal{C}$, set

$M_{c}=\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right].$

By _Boundedness_ , we have
$M_{c}\supseteq\operatorname{mod}_{0}(\Gamma^{\sigma}_{c})$. Now set

$F_{\sigma}(i,c,\varphi)=\operatorname{mod}_{0}(\varphi)\cup M_{c}.$

Define a selection function $f_{\sigma}$ by letting $f_{\sigma}(i,c,\varphi)$
be any formula with
$\operatorname{mod}_{0}(f_{\sigma}(i,c,\varphi))=F_{\sigma}(i,c,\varphi)$.
Since $F_{\sigma}(i,c,\varphi)$ contains the models of $\varphi$, clearly
$f_{\sigma}(i,c,\varphi)\in\operatorname{Cn}_{0}(\varphi)$. Therefore $f$ is
indeed a selection function.

We claim that, for any $c\in\mathcal{C}$,

$M_{c}=\bigcap_{\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c}{F_{\sigma}(i,c,\varphi)}.$

The “$\subseteq$” inclusion is clear since, by definition,
$F_{\sigma}(i,c,\varphi)\supseteq M_{c}$. For the “$\supseteq$” inclusion,
suppose for contradiction that there is some
$v\in\bigcap_{\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c}{F_{\sigma}(i,c,\varphi)}$ with $v\notin M_{c}$.

Take any $\varphi\in\Gamma^{\sigma}_{c}$. Then there is $i\in\mathcal{S}$ such
that $\langle{i,\varphi}\rangle\in\sigma\upharpoonright c$, and hence $v\in
F_{\sigma}(i,c,\varphi)$. But $v\notin M_{c}$ by assumption, so
$v\in\operatorname{mod}_{0}(\varphi)$. This shows
$v\in\operatorname{mod}_{0}(\Gamma^{\sigma}_{c})$. But
$\operatorname{mod}_{0}(\Gamma^{\sigma}_{c})\subseteq M_{c}$ by _Boundedness_
, so $v\in M_{c}$; contradiction.

From this we get

$\displaystyle\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]$
$\displaystyle=M_{c}$
$\displaystyle=\bigcap_{\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c}{F_{\sigma}(i,c,\varphi)}$
$\displaystyle=\bigcap_{\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c}{\operatorname{mod}_{0}(f_{\sigma}(i,c,\varphi))}$
$\displaystyle=\operatorname{mod}_{0}\left(\\{f_{\sigma}(i,c,\varphi)\mid\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c\\}\right)$

Since $\left[{B^{\sigma}_{c}}\right]$ is deductively closed (by _Closure_ ,
which holds for all model-based operators), we get

$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}\left(\\{f_{\sigma}(i,c,\varphi)\mid\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c\\}\right)$

as required for selectivity.

“only if”: Suppose a model-based operator is selective according to some
selection scheme $f$. Take any $\ast$-consistent $\sigma$ and
$c\in\mathcal{C}$. Write

$\Delta=\\{f_{\sigma}(i,c,\varphi)\mid\langle{i,\varphi}\rangle\in\sigma\upharpoonright
c\\}.$

so that $\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(\Delta)$. For
$\langle{i,\varphi}\rangle\in\sigma\upharpoonright c$ we have
$f_{\sigma}(i,c,\varphi)\in\operatorname{Cn}_{0}(\varphi)\subseteq\operatorname{Cn}_{0}(\Gamma^{\sigma}_{c})$
from the definition of a selection scheme and the fact that
$\varphi\in\Gamma^{\sigma}_{c}$. Hence
$\Delta\subseteq\operatorname{Cn}_{0}(\Gamma^{\sigma}_{c})$, so

$\left[{B^{\sigma}_{c}}\right]=\operatorname{Cn}_{0}(\Delta)\subseteq\operatorname{Cn}_{0}(\operatorname{Cn}_{0}(\Gamma^{\sigma}_{c}))=\operatorname{Cn}_{0}(\Gamma^{\sigma}_{c})$

as required for _Boundedness_. ∎

###  A.14  Proof that $\mathsf{var\text{-}based\text{-}cond}$,
$\mathsf{part\text{-}based\text{-}cond}$ and $\mathsf{excess\text{-}min}$ are
selective

This characterisation in Theorem 3 allows us to easily analyse when
conditioning and score-based operators are selective. In the case of
conditioning operators with $K^{\emptyset}=\operatorname{Cn}(\emptyset)$, we
in fact have a precise characterisation. First, some terminology: say that a
world $W$ _refines $W^{\prime}$ at $c$_ if for all $i\in\mathcal{S}$ we have
$\Pi^{W}_{i}[v^{W}_{c}]\subseteq\Pi^{W^{\prime}}_{i}[v^{W^{\prime}}_{c}]$.
Intuitively, this means each source is more knowledgable in case $c$ in world
$W$ than they are in $W^{\prime}$. Write $\mathcal{W}_{c\ :\
v}=\\{W\in\mathcal{W}\mid v^{W}_{c}=v\\}$ for the set of worlds whose $c$
valuation is $v$. We have the following.

######  Proposition 12.

Suppose an elementary conditioning operator satisfies the basic postulates and
has $K^{\emptyset}=\operatorname{Cn}(\emptyset)$. Then it is selective if and
only if for all $W$, $c$, $v$ there is $W^{\prime}\in\mathcal{W}_{c\ :\ v}$
such that $W^{\prime}\leq W$ and $W$ refines $W^{\prime}$ at all cases $d\neq
c$.

While the condition on $\leq$ in Proposition 12 is somewhat technical, it is
implied by the very natural _partition-equivalence_ property from Section 2.
Consequently, $\mathsf{var\text{-}based\text{-}cond}$ and
$\mathsf{part\text{-}based\text{-}cond}$ are selective. For the score-based
operator $\mathsf{excess\text{-}min}$, one can show _Boundedness_ holds
directly using a property of the disagreement scoring function $d$ similar to
the property of $\leq$ above. Consequently, $\mathsf{excess\text{-}min}$ is
also selective.

We first state some preliminary results.

######  Lemma 6.

Suppose $W$ refines $W^{\prime}$ at $c$. Then for any $i\in\mathcal{S}$ and
$\varphi\in\mathcal{L}{}_{0}$,

$W,c\models S_{i}(\varphi)\implies W^{\prime},c\models S_{i}(\varphi)$

###### Proof.

Suppose $W,c\models S_{i}(\varphi)$. Then $v^{W}_{c}\in\Pi^{W}_{i}[\varphi]$,
i.e. $\operatorname{mod}_{0}(\varphi)\cap\Pi^{W}_{i}[v^{W}_{c}]\neq\emptyset$.
By refinement,
$\Pi^{W}_{i}[v^{W}_{c}]\subseteq\Pi^{W^{\prime}}_{i}[v^{W^{\prime}}_{c}]$.
Hence
$\operatorname{mod}_{0}(\varphi)\cap\Pi^{W^{\prime}}_{i}[v^{W^{\prime}}_{c}]\neq\emptyset$,
so $v^{W^{\prime}}_{c}\in\Pi^{W^{\prime}}_{i}[\varphi]$. That is,
$W^{\prime},c\models S_{i}(\varphi)$. ∎

######  Lemma 7.

For any $W\in\mathcal{W}$ and $c\in\mathcal{C}$, there is a $\ast$-consistent
sequence $\sigma$ – containing only reports for case $c$ – such that for all
$W^{\prime}\in\mathcal{W}$,

$W^{\prime}\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})\iff W\text{
refines }W^{\prime}\text{ at }c.$

###### Proof.

For a valuation $v\in\mathcal{V}$, let $\varphi(v)$ be a propositional formula
such that $\operatorname{mod}_{0}(\varphi(v))=\\{v\\}$. Take $\sigma$ to be
any enumeration of reports of the form

$\langle{i,c,\varphi(v)}\rangle$

where $i\in\mathcal{S}$ and $v\in\Pi^{W}_{i}[v^{W}_{c}]$. Note that such a
sequence exists since there are only finitely many sources and valuations.
Clearly $\sigma$ contains only $c$-reports. Since $\Pi^{W}_{\ast}$ is the unit
partition, the only report from $\ast$ is
$\langle{\ast,c,\varphi(v^{W}_{c})}\rangle$. Hence $\sigma$ is
$\ast$-consistent. We show the desired equivalence.

$\implies$: Suppose
$W^{\prime}\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$. Take any
$i\in\mathcal{S}$. We need to show
$\Pi^{W}_{i}[v^{W}_{c}]\subseteq\Pi^{W^{\prime}}_{i}[v^{W^{\prime}}_{c}]$.
Take $v\in\Pi^{W}_{i}[v^{W}_{c}]$. By construction of $\sigma$,
$\langle{i,c,\varphi(v)}\rangle\in\sigma$. Hence $W^{\prime},c\models
S_{i}(\varphi(v))$, i.e.
$v^{W^{\prime}}_{c}\in\Pi^{W^{\prime}}_{i}[\varphi(v)]=\Pi^{W^{\prime}}_{i}[v]$.
This shows $v\in\Pi^{W^{\prime}}_{i}[v^{W^{\prime}}_{c}]$ as required.

$\impliedby$: Suppose $W$ refines $W^{\prime}$ at $c$. Take any
$\langle{i,c,\varphi(v)}\rangle\in\sigma$. Then $v\in\Pi^{W}_{i}[v^{W}_{c}]$,
so $v^{W}_{c}\in\Pi^{W}_{i}[v]=\Pi^{W}_{i}[\varphi(v)]$. This shows
$W,c\models S_{i}(\varphi(v))$, and Lemma 6 gives $W^{\prime},c\models
S_{i}(\varphi(v))$. Hence
$W^{\prime}\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$.

∎

###### Proof of Proposition 12.

Take an elementary conditioning operator with the basic postulates and
$K^{\emptyset}=\operatorname{Cn}(\emptyset)$.

“if”: Suppose the stated property holds. Since all conditioning operators are
model-based, by Theorem 3 it suffices to show _Boundedness_. To that end, let
$\sigma$ be $\ast$-consistent and take $c\in\mathcal{C}$. We need
$\left[{B^{\sigma}_{c}}\right]\subseteq\operatorname{Cn}_{0}(\Gamma^{\sigma}_{c})$;
or equivalently, by _Closure_ ,
$\operatorname{mod}_{0}\left[{B^{\sigma}_{c}}\right]\supseteq\operatorname{mod}_{0}(\Gamma^{\sigma}_{c})$.

Take any $v\in\operatorname{mod}_{0}(\Gamma^{\sigma}_{c})$. Since $\sigma$ is
$\ast$-consistent, $B^{\sigma}$ is consistent by _Consistency_. Hence
$\mathcal{Y}_{\sigma}\neq\emptyset$. Take any $W\in\mathcal{Y}_{\sigma}$. By
the property in the statement of the result, there is
$W^{\prime}\in\mathcal{W}_{c\ :\ v}$ such that $W^{\prime}\leq W$ and $W$
refines $W^{\prime}$ at all cases $d\neq c$.

We claim $W^{\prime}\in\mathcal{X}_{\sigma}$. By Proposition 3, elementariness
and Lemma 1, we have
$\mathcal{X}_{\sigma}=\operatorname{mod}(K^{\sigma})=\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})$.
Take any $\langle{i,d,\varphi}\rangle\in\sigma$. We consider cases.

  * •

Case 1 ($d=c$). Here $\langle{i,\varphi}\rangle\in\sigma\upharpoonright c$, so
$\varphi\in\Gamma^{\sigma}_{c}$. Hence
$v\in\operatorname{mod}_{0}(\Gamma^{\sigma}_{c})\subseteq\operatorname{mod}_{0}(\varphi)$.
Since $W^{\prime}\in\mathcal{W}_{c\ :\ v}$, $v$ is the $c$-valuation of
$W^{\prime}$. Hence $W^{\prime},c\models\varphi$, and $W^{\prime},c\models
S_{i}(\varphi)$ follows.

  * •

Case 2 ($d\neq c$). By assumption, $W$ refines $W^{\prime}$ at $d$. Since
$W\in\mathcal{Y}_{\sigma}\subseteq\mathcal{X}_{\sigma}$, we have $W,d\models
S_{i}(\varphi)$. By Lemma 6, $W^{\prime},d\models S_{i}(\varphi)$ also.

We have shown
$W^{\prime}\in\operatorname{mod}(G^{\sigma}_{\mathsf{snd}})=\mathcal{X}_{\sigma}$.
Now recall that $W\in\mathcal{Y}_{\sigma}$ – so $W$ is $\leq$-minimal in