Truth-tracking in the framework of the KR paper¶
Introduction¶
In the KR paper we considered rationality postulates for multi-source belief change operators. In this document we consider when such operators are truth-tracking: when does an operator eventually find the “true” world? Or, if the true world cannot be pinned down uniquely, what information can we learn about it?
We will also consider the interaction between rationality and truth-tracking postulates, by looking at the conditions under which conditioning (and score-based?) operators with the basic postulates are truth-tracking.
In the belief change problem we assumed all reports were sound (the Soundness postulate). Here we go further and also assume that all sound statements will eventually be reported. Thus, we consider streams of reports which contain all (and only) sound reports for the “true” world.
Recall that a report is sound is it is true up to lack of expertise of the source. Equivalently, by the link between expertise and knowledge, a report is sound if the source does not know that it is false. By assuming we receive complete streams, in which all sound reports appear, we assume sources are willing to share all that they consider possible. Consequently, such streams should not be interpreted as telling us what sources believe (e.g. as is usually the case in belief revision and belief merging). Indeed, we do not model beliefs of sources at all in the framework.
For a concrete example, recall the example from the KR paper in which Dr. A lacks expertise on diagnosis of condition X. Nonetheless, it is likely that Dr. A has some (possibly erroneous) opinion on whether patient 1 suffers from X or not. In a complete stream, however, Dr. A has to withhold this opinion and report both that patient 1 does and does not suffer from X, since both positions are consistent with Dr. A’s expertise.
Nevertheless, streams of sound reports provide a starting framework to address truth-tracking with non-expert sources.
Framework recap¶
Let us first briefly recap the logical framework (with some minor notational changes compared to the KR version):
\(\N = \{1, 2, 3, \ldots\}\)
\(\Prop\): finite set of propositional variables
\(\V\): propositional valuations over \(\Prop\)
\(\P\): set of partitions of \(\V\). \(\Pi \subseteq 2^\V\) is a partition iff \(\emptyset \notin \Pi\), distinct sets in \(\Pi\) are disjoint, and \(\bigcup\Pi = \V\).
\(\Src\): finite set of sources, with \(\ast \in \Src\) the completely reliable source
\(\Srcm = \Src \setminus \{\ast\}\)
\(\C\): finite set of cases
\(\W\): set of worlds, where a world is \(W = \tuple{\{v_c\}_{c \in \C}, \{\Pi_i\}_{i \in \Src}} \in \V^\C \times \P^\Src\) with \(\Pi^W_\ast\) the unit partition
\(\L_0\): propositional language over \(\Prop\)
\(\Cn_0\): classical propositional consequence operator
\(\|\phi\| \subseteq \V\): models of \(\phi \in \L_0\)
\(\L\): the language extending \(\L_0\) with expertise formulas \(\E_i\phi\) and soundness formulas \(\S_i\phi\), where \(i \in \Src\) and \(\phi \in \L_0\)
\(\Pi[v]\): unique cell in \(\Pi\) containing \(v\)
\(\Pi[U] = \bigcup_{v \in U}{\Pi[v]}\)
\(\Pi[\phi] = \Pi[\|\phi\|]\)
\(W, c \models \phi\) iff \(v^W_c \in \|\phi\|\)
\(W, c \models \E_i\phi\) iff \(\Pi^W_i[\phi] = \|\phi\|\)
\(W, c \models \S_i\phi\) iff \(v^W_c \in \Pi^W_i[\phi]\)
\(\mods_c(\Phi) = \{W \mid W, c \models \Phi\}\)
\(\mods(G) = \bigcap_{c \in \C}{\mods_c(\Gamma_c)}\): models of a collection \(G = \{\Gamma_c\}_{c \in \C} \subseteq \L^\C\)
\(\Xsnd_\sigma = \{W \mid \forall \tuple{i, c, \phi} \in \sigma: W, c \models \S_i\phi\}\)
Truth-tracking preliminaries¶
[Note: the framework here mostly comes from [BGS16] and other references.]
A stream enumerates all sound reports from ordinary sources at a world; it is on the basis of such streams that we aim to find this “true” world.
Definition 1
A stream for a world \(W \in \W\) is an infinite sequence \(\rho \in (\Srcm \times \C \times \L_0)^\N\) such that, for all \(\tuple{i, c, \phi}\),
We refer to the \(\implies\) direction above as soundness of \(\rho\) for \(W\), and the \(\impliedby\) direction as completeness of \(\rho\) for \(W\).
Note that every \(W\) has some stream: the set \(\{\tuple{i, c, \phi} \mid W, c \models \S_i\phi\}\) is countable, so can be indexed by \(\N\) to form a stream.
For \(n \in \N\), \(\rho_n\) denotes the \(n\)-th element in \(\rho\), and \(\rho[n]\) denotes the finite initial segment of \(\rho\) of length \(n\).
For simplicity, we work first with “semantic” operators, which take finite sequences and output sets of worlds.
Definition 2
A method is a function \(L : (\Srcm \times \C \times \L_0)^* \to 2^\W\).
Note that we do not consider reports from the reliable source \(\ast\). Here \(L(\sigma)\) represents the set of worlds \(L\) considers possible given input \(\sigma\); its beliefs. If \(L(\sigma) \subseteq S\) for some \(S \subseteq \W\), then \(L\) believes \(S\) on the basis of \(\sigma\).
\(L\) is said to be consistent if \(L(\sigma) \ne \emptyset\) for all \(\sigma\). Note that any belief change operator \(\sigma \mapsto \tuple{B^\sigma, K^\sigma}\) induces a method by setting \(L(\sigma) = \mods(B^\sigma)\).
A question \(Q\) is a partition of \(\W\). That is, \(Q\) is a set of disjoint “answers” \(A \in Q\), with each world \(W\) appearing in a unique cell – the correct answer at \(W\) – denoted by \(Q[W]\).
-
Example 1.
Any formula \(\Phi \in \L\) and case \(c\) defines a question \(Q_{\Phi, c} = \{\mods_c(\Phi), \mods_c(\neg\Phi)\}\). 1 Intuitively, this question simply asks whether \(\Phi\) is true or false in case \(c\).
The finest question \(Q_\bot = \{\{W\} \mid W \in \W\}\) asks: what is the “true” world?
For any set \(X\) and function \(f: \W \to X\), the question \(Q_f\) is the partition formed by the equivalence relation \(W \sim_f W'\) iff \(f(W) = f(W')\).
In this way any data associated with a world defines a question. E.g. if \(f(W) = |\{i \in \Srcm \mid \Pi^W_i = \Pi_\ast\}|\) we ask for the number of expert sources; if \(f(W) = |\{c \in \C \mid W, c \models \phi\}|\) we ask for the number of cases where \(\phi\) holds, etc.
Note that \(Q_{\Phi, c}\) corresponds to \(f(W) = 1\) if \(W, c \models \Phi\) and \(f(W) = 0\) otherwise, and \(Q_\bot\) corresponds to the identity function \(f(W) = W\).
A method \(L\) solves \(Q\) if it always believes the correct answer, eventually, when fed a stream.
Definition 3
A method \(L\) solves \(Q\) if for all worlds \(W\) and for all streams \(\rho\) for \(W\), there is \(n \in \N\) such that \(L(\rho[m]) \subseteq Q[W]\) for all \(m \ge n\).
\(Q\) is solvable if there is some consistent method \(L\) which solves \(Q\).
Note that consistency is required for a reasonable notion of solvability, since the inconsistent method \(L(\sigma) \equiv \emptyset\) solves any question. Say an operator solves \(Q\) if its associated method solves \(Q\).
Questions are partially ordered by partition refinement, which we denote by \(\preceq\). 2 Coarser questions are “easier”, whereas finer partitions are “harder”. Naturally, if \(Q\) is solvable then any easier question is also solvable.
Proposition 1
If \(Q\) is solvable and \(Q \preceq Q'\), then \(Q'\) is also solvable.
Proof. The method \(L\) which solves \(Q\) also solves \(Q'\), since \(Q[W] \subseteq Q'[W]\) for any \(W\).
Since question-solving is based on streams of sound reports, it is clear that two distinct worlds satisfying exactly the same soundness statements cannot be distinguished by any solvable question. To formalise this, define a pre-order \(\specleq\) on \(\W\) by
Let \(\speclt\) and \(\speceq\) denote the strict and symmetric parts of \(\specleq\), respectively.
Remark. In [BGS16] the authors explore the topological interpretation of solvability; one considers the topology on the set of states generated by the “observable” propositions, from which sound and complete streams are formed. In our framework this is the topology on \(\W\) generated by sets of the form \(\mods_c(\S_i\phi)\). In this topology, \(\specleq\) is the specialisation preorder.
Lemma 1
\(W \specleq W'\) iff for all \(i \in \Srcm\) and \(c \in C\) we have \(\Pi^W_i[v^W_c] \subseteq \Pi^{W'}_i[v^{W'}_c]\). 3
Proof.
“if”: Take \(i, c, \phi\) and suppose \(W, c \models \S_i\phi\). Then \(v^W_c \in \Pi^W_i[\phi]\), so there is \(v \in \|\phi\|\) such that \(v^W_c \in \Pi^W_i[v]\). This means \(v \in \Pi^W_i[v^w_c]\), so by assumption \(v \in \Pi^{W'}_i[v^{W'}_c]\), and consequently \(v^{W'}_c \in \Pi^{W'}_i[v] \subseteq \Pi^{W'}_i[\phi]\). Hence \(W', c \models \S_i\phi\).
“only if”: Take \(v \in \Pi^W_i[v^W_c]\). Let \(\phi\) be a propositional formula such that \(\|\phi\| = \{v\}\). Then \(W, c \models \S_i\phi\), so \(W', c \models \S_i\phi\) too. That is, \(v^{W'}_c \in \Pi^{W'}_i[v]\), so \(v \in \Pi^{W'}_i[v^{W'}_c]\) as required.
Lemma 2
For two worlds \(W, W'\), the following are equivalent.
\(W\) and \(W'\) have exactly the same streams
\(W \speceq W'\)
For all \(i \in \Srcm\) and \(c \in C\), \(\Pi^W_i[v^W_c] = \Pi^{W'}_i[v^{W'}_c]\)
Proof.
\((2)\) and \((3)\) are easily seen to be equivalent in light of Lemma 1. We show \((1)\) and \((2)\) are equivalent.
\((1) \implies (2)\): Take \(i, c\) and \(\phi\) such that \(W, c \models \S_i\phi\). Let \(\rho\) be any stream for \(W\). Then by completeness of \(\rho\) for \(W\), \(\tuple{i, c, \phi} \in \rho\). By assumption, \(\rho\) is also a stream for \(W'\). Hence, by soundness of \(\rho\) for \(W'\), \(W', c \models \S_i\phi\). This shows \(W \specleq W'\). One can show \(W' \specleq W\) by an symmetric argument.
\((2) \implies (1)\): From \(W \speceq W'\) we have \(W, c \models \S_i\phi \iff W', c \models \S_i\phi\) for all \(i, c, \phi\). The condition for \(\rho\) to be a stream for \(W\) therefore coincides with that for a sequence \(\rho\) to be a stream for \(W'\), so \(W\) and \(W'\) have exactly the same streams.
Since it will play a special role throughout, we denote by \(Q^*\) the question defined by the equivalence relation \(\approx\). Thus, \(Q^*[W]\) is the set of \(W'\) with \(W' \approx W\). As claimed above, any solvable question cannot distinguish \(\approx\)-equivalent worlds, and is therefore coarser than \(Q^*\).
Lemma 3
If \(Q\) is solvable then \(Q^* \preceq Q\).
Proof.
Suppose \(L\) solves \(Q\). Take any world \(W\). We will show \(Q^*[W] \subseteq Q[W]\). Suppose \(W' \speceq W\). Let \(\rho\) be a stream for \(W\). Then by Lemma 2, \(\rho\) is also a stream for \(W'\). Since \(L\) solves \(Q\), there is \(n\) sufficiently large such that \(L(\rho[n]) \subseteq Q[W]\) and \(L(\rho[n]) \subseteq Q[W']\). Hence \(L(\rho[n]) \subseteq Q[W] \cap Q[W']\). Since \(L\) is consistent, \(Q[W] \cap Q[W'] \ne \emptyset\). Since \(Q\) is a partition, this means \(Q[W] = Q[W']\), and thus \(W' \in Q[W]\).
Fortunately, \(Q^*\) is itself solvable, since we work in a finite framework. To solve \(Q^*\) it suffices to guess that the true world is \(\specleq\)-minimal in \(\Xsnd_\sigma\); any worlds not above the true one will eventually be eliminated by completeness of streams.
Proposition 2
\(Q^*\) is solvable.
Proof.
Define \(L\) by
(where \(W \in \min_{\specleq}{\Xsnd_\sigma}\) iff \(W \in \Xsnd_\sigma\) and there is no \(W' \in \Xsnd_\sigma\) with \(W' \speclt W\)). Note that \(L\) is consistent since \(\W\) is finite and non-empty.
We show \(L\) solves \(Q^*\). Take any world \(W\) and a stream \(\rho\). First note that, by soundness of streams, \(W \in \Xsnd_{\rho[m]}\) for all \(m\), so we are always in the first case in the definition of \(L(\rho[m])\).
It suffices to show that for any \(W' \notin Q^*[W]\), there is \(n_{W'}\) such that \(W' \notin L(\rho[m])\) for \(m \ge n_{W'}\). Indeed, taking \(n = \max\{n_{W'} \mid W' \notin Q^*[W] \}\), we have \(L(\rho[m]) \subseteq Q^*[W]\) for \(m \ge n\).
So, take \(W'\) such that \(W' \not\speceq W\). We consider two cases.
Case 1: \(W \not\specleq W'\).
By definition, there are \(i, c, \phi\) such that \(W, c \models \S_i\phi\) but \(W', c \not\models \S_i\phi\). By completeness of \(\rho\), there is some \(n\) such that \(\rho_n = \tuple{i, c, \phi}\); clearly \(W' \notin \Xsnd_{\rho[m]}\) for \(m \ge n\), and thus \(W' \notin L(\rho[m])\).
Case 2: \(W \speclt W'\).
Since \(W \in \Xsnd_{\rho[m]}\) for all \(m\), \(W'\) can never be \(\specleq\)-minimal in \(\Xsnd_{\rho[m]}\). Hence \(W' \notin L(\rho[m])\). We may therefore take \(n = 1\).
These cases are exhaustive since \(W' \not\speceq W\). This completes the proof.
From Proposition 1, Lemma 3 and Proposition 2 we get the following.
Corollary 1
\(Q\) is solvable if and only if \(Q^* \preceq Q\).
Given this result, \(Q^*\) is the only question that really matters: all other questions are either unsolvable or formed by coarsening \(Q^*\). With this is mind, say a method (or operator) is truth-tracking if it solves \(Q^*\).
Example 2. We refer back to some of the example questions from Example 1.
The question \(Q_{\phi, c}\), for any propositional formula \(\phi \in \L_0\), is solvable if and only if either \(\phi\) or \(\neg\phi\) is a tautology. To see this it suffices to consider two worlds \(W_1, W_2\) where no sources have any expertise (i.e. \(\Pi^{W_j}_i = \{\V\}\)), and where \(v^{W_1}_c\) satisfies \(\phi\) but \(v^{W_2}_c\) does not. Then \(W_1 \speceq W_2\) but \(Q_{\phi,c}[W_1] \ne Q_{\phi,c}[W_2]\).
Similarly, \(Q_{\E_i\phi,c}\) is solvable iff either \(\phi\) or \(\neg\phi\) is a tautology, when \(|\Prop| \ge 2\). 4
This appears to be something of a negative result: we cannot learn the true value of any non-trivial (propositional) formula! But note that the counterexample requires worlds in which sources are lacking in expertise. As we will show in the next section, the situation is better in other worlds where there is sufficient expertise, and one can learn the true value of \(\phi\) when starting in such worlds. The fact that \(Q_{\phi, c}\) is not solvable merely says that one cannot learn \(\phi\) in all worlds, which is perhaps to be expected when dealing with non-expert sources.
The finest question \(Q_\bot\) is also not solvable, since there are always distinct \(W, W'\) with \(W \speceq W'\).
Generally, \(Q_f\) is solvable iff \(W \speceq W'\) implies \(f(W) = f(W')\), i.e. iff \(f\) has a unique value on each equivalence class of \(\speceq\).
Note that there do exist truth-tracking operators, since \(Q^*[W]\) is elementary: we have \(Q^*[W] = \mods(G^W)\), where \(G^W = \{\Gamma^W_c\}_{c \in \C}\),
For any \(L\) solving \(Q^*\), we can, for example, take \(B^\sigma = G^W\) where \(W\) is the minimal world in \(L(\sigma)\) according to some fixed ordering, to construct an operator solving \(Q^*\) (however, we will come to much more natural truth-tracking operators later on).
What information can be learned?¶
If the “true” world were \(W\), truth-tracking methods can eventually tell us we are in \(Q^*[W]\), but no more. But to what extent does \(Q^*[W]\) actually reveal information about \(W\)? Put differently, what properties of \(W\) are uniquely defined by \(W\)’s soundness statements?
Clearly this depends on what \(W\) looks like: in worlds where no sources have any expertise at all, partitions are uniquely defined (since every consistent formula is sound, and only the trivial partitions have this property), but any combination of valuations is possible. On the other hand, if all sources have total expertise then the valuation at each case is uniquely defined, but there may not be enough cases to uniquely define source partitions. Of particular interest is the case where \(Q^*[W]\) contains only \(W\); starting in such a world, truth-tracking methods are able to find the true state of affairs exactly.
In what follows, for a set \(S \subseteq \W\) we write \(S, c \models \Phi\) iff \(W, c \models \Phi\) for all \(W \in S\). Say \(S\) decides \(\Phi \in \L\) in case \(c\) iff either \(S, c \models \Phi\) or \(S, c \models \neg\Phi\). That is, the truth value of \(\Phi\) in case \(c\) is unambiguously defined across \(S\). If the truth value of \(\Phi\) does not depend on the case (e.g. if \(\Phi = \E_i\phi\)) then we simply say \(S\) decides \(\Phi\).
Learning valuations¶
We start by considering what one can learn about the valuations \(\{v^W_c\}_{c \in \C}\). For \(S \subseteq \W\) and \(c \in \C\), write
for the set of \(c\)-valuations appearing in \(S\).
Lemma 4
For any world \(W\) and case \(c\),
Proof.
\(\subseteq\): Take \(v \in \V^{Q^*[W]}_c\). Then there is \(W' \speceq W\) such that \(v = v^{W'}_c\). Take \(i \in \Srcm\). From Lemma 2 we have \(v \in \Pi^{W'}_i[v] = \Pi^W_i[v^W_c]\), as required.
\(\supseteq\): Take \(v \in \bigcap_{i \in \Srcm}{\Pi^W_i[v^W_c]}\). Define a world \(W'\) with the same partitions as \(W\) and the same valuations at cases \(d \ne c\), but with \(v^{W'}_c = v\). We will show \(W' \approx W\).
By Lemma 2 it suffices to show \(\Pi^{W'}_i[v^{W'}_d] = \Pi^W_i[v^W_d]\) for all \(i \in \Srcm\) and \(d \in \C\). For \(d \ne c\) this is clear since the components of \(W'\) are the same as \(W\). For \(d = c\), note that since \(v \in \Pi^W_i[v^W_c]\) we have \(\Pi^W_i[v] = \Pi^W_i[v^W_c]\); hence
as required. Thus \(W' \approx W\) and \(v \in \V^{Q^*[W]}_c\).
We now address when \(Q^*[W]\) decides a propositional formula \(\phi\). We need a group notion of expertise: for \(\Src' \subseteq \Src\) and \(\Gamma \subseteq \L_0\), write \(W \models \E_{\Src'}{\Gamma}\) if for each \(\psi \in \Gamma\) there is \(i \in \Src'\) such that \(W \models \E_i\psi\).
Lemma 5
For \(W \speceq W'\), \(i \in \Srcm\) and \(\phi \in \L_0\),
Proof. Suppose \(W, c \models \phi \land \E_i\phi\). By definition of the semantics, \(v^W_c \in \|\phi\|\) and \(\Pi^W_i[\phi] \subseteq \|\phi\|\). Thus \(\Pi^W_i[v^W_c] \subseteq \|\phi\|\). Since \(\Pi^W_i[v^W_c] = \Pi^{W'}_c[v^{W'}_c]\), we get \(v^{W'}_c \in \|\phi\|\) and thus \(W', c \models \phi\).
Lemma 6
\(Q^*[W]\) decides \(\phi \in \L_0\) in case \(c\) if and only if there is \(\Gamma \subseteq \L_0\) such that
\(W, c \models \Gamma\)
\(W \models \E_{\Srcm}{\Gamma}\)
Either \(\phi \in \Cn_0(\Gamma)\) or \(\neg\phi \in \Cn_0(\Gamma)\)
Proof.
“if”: Note that by (1), (2) and Lemma 5, \(W', c \models \Gamma\) holds for any \(W' \speceq W\). If \(\phi \in \Cn_0(\Gamma)\) then \(W', c \models \phi\) for all such \(W'\), so \(Q^*[W], c \models \phi\). otherwise \(\neg\phi \in \Cn_0(\Gamma)\) and \(Q^*[W], c \models \neg\phi\).
“only if”: For each \(i \in \Srcm\), let \(\psi_i\) be a propositional formula with \(\|\psi_i\| = \Pi^W_i[v^W_c]\). Clearly \(W, c \models \E_i\psi_i\). Let \(\Gamma = \{\psi_i\}_{i \in \Srcm}\). Then (1) and (2) hold.
For (3), first suppose \(Q^*[W], c \models \phi\). Then \(\V^{Q^*[W]}_c \subseteq \|\phi\|\). By Lemma 4,
so \(\phi \in \Cn_0(\Gamma)\). In the case where \(Q^*[W], c \models \neg\phi\) we get \(\neg\phi \in \Cn_0(\Gamma)\) by an identical argument.
We can now obtain equivalent conditions for \(Q^*[W]\) to define a unique valuation in case \(c\).
Theorem 1
The following are equivalent.
\(\V^{Q^*[W]}_c = \{v^W_c\}\)
\(Q^*[W]\) decides \(\phi\) in case \(c\) for all \(\phi \in \L_0\)
There is \(\Gamma \subseteq \L_0\) such that i) \(W, c \models \Gamma\); ii) \(W \models \E_{\Srcm}{\Gamma}\) and iii) \(\Cn_0(\Gamma)\) is a maximally consistent set.
Proof.
We show (1) and (2) are equivalent, and then that (2) and (3) are equivalent.
\((1) \implies (2)\): If \(W' \in Q^*[W]\) then, by (1), \(v^{W'}_c = v^W_c\). This means \(W', c \models \phi\) iff \(W, c \models \phi\), for all \(\phi \in \L_0\). Consequently, \(Q^*[W]\) decides \(\phi\).
\((2) \implies (1)\): Take \(v \in \V^{Q^*[W]}_c\). Then there is \(W' \in Q^*[W]\) such that \(v = v^{W'}_c\). Since \(Q^*[W]\) decides all propositional formulas, we have \(W', c \models p\) iff \(W, c \models p\), for all \(p \in \Prop\). Consequently \(v^{W'}_c\) and \(v^W_c\) satisfy exactly the same propositional variables, so \(v = v^{W'}_c = v^W_c\).
\((2) \implies (3)\): By (2) and Lemma 6, for each \(\phi \in \L_0\) there is \(\Gamma_\phi \subseteq \L_0\) such that \(W, c \models \Gamma_\phi\), \(W \models \E_{\Srcm}{\Gamma_\phi}\) and either \(\phi \in \Cn_0(\Gamma_\phi)\) or \(\neg\phi \in \Cn_0(\Gamma_\phi)\).
Set \(\Gamma = \bigcup_{\phi \in \L_0}{\Gamma_\phi}\). Then (i) and (ii) hold. For (iii) we need to show \(\Cn_0(\Gamma)\) is maximally consistent. It is clearly consistent, since \(\Gamma\) is (\(v^W_c\) is a model). For maximality, suppose \(\phi \notin \Cn_0(\Gamma)\). Then there is \(v \in \|\Gamma\| \setminus \|\phi\|\). Note that \(\Gamma_\phi \subseteq \Gamma\), so \(\|\Gamma\| \subseteq \|\Gamma_\phi\|\) and thus \(v \in \|\Gamma_\phi\| \setminus \|\phi\|\). This means \(\phi \notin \Cn_0(\Gamma_\phi)\); by the property of \(\Gamma_\phi\) from Lemma 6, we have \(\neg\phi \in \Cn_0(\Gamma_\phi)\). By monotonicity of \(\Cn_0\) this implies \(\neg\phi \in \Cn_0(\Gamma)\), and consequently \(\Cn_0(\Gamma) \cup \{\phi\}\) is inconsistent. This shows \(\Cn_0(\Gamma)\) is maximally consistent, and we are done.
\((3) \implies (2)\): Take any \(\phi \in \L_0\). We may apply Lemma 6 directly with \(\Gamma\): conditions (1) and (2) in that lemma hold by our assumption, and (3) is a standard property of maximally consistent sets.
Example 3. Suppose \(\Prop = \{p, q\}\), \(\C = \{c_1, c_2\}\) and \(\Src = \{\ast, i_1, i_2\}\). Consider the world \(W\), whose partitions and valuations are shown below:
Then \(\V^{Q^*[W]}_{c_1} = \{\bar{p}q\} = \{v^W_{c_1}\}\), and \(\V^{Q^*[W]}_{c_2} = \{pq, \bar{p}\bar{q}\} \ne \{v^W_{c_2}\}\). That is, \(W\)’s \(c_1\)-valuation can be uniquely determined by truth-tracking methods, but its \(c_2\)-valuation cannot be. Indeed, take \(\Gamma = \{p \limplies q, p \liff \neg q\}\). Then \(W, c_1 \models \Gamma\), \(W \models \E_{\Srcm}{\Gamma}\) (since \(i_1\) has expertise on \(p \limplies q\) and \(i_2\) has expertise on \(p \liff \neg q\)), and \(\Cn_0(\Gamma) = \Cn_0(\neg p \land q)\), which is maximally consistent.
Learning source partitions¶
We now present analogues of the results in the previous section, but applied to source partitions instead of valuations. For \(S \subseteq \W\) and \(i \in \Srcm\), write
for the partitions of source \(i\) appearing in worlds in \(S\).
Lemma 7
For any world \(W\), source \(i \in \Srcm\) and partition \(\Pi\),
Proof.
“if”: Suppose \(\{\Pi^W_i[v^W_c]\}_{c \in \C} \subseteq \Pi\). Then for any \(c\), \(\Pi[v^W_c] = \Pi^W_i[v^W_c]\).
Let \(W'\) be a world with the same components as \(W\), except that \(\Pi^{W'}_i = \Pi\). We claim \(W' \speceq W\), which we show via Lemma 2. For \(j \ne i\) and any case \(c\), clearly \(\Pi^{W'}_j[v^{W'}_c] = \Pi^W_j[v^W_c]\). For source \(i\), we have \(\Pi^{W'}_i[v^{W'}_c] = \Pi[v^{W'}_c] = \Pi[v^W_c] = \Pi^W_i[v^W_c]\). Hence \(W \speceq W'\).
“only if”: By Lemma 2, if \(\Pi = \Pi^{W'}_i\) for some \(W' \speceq W\) then \(\Pi^W_i[v^W_c] = \Pi[v^{W'}_c] \in \Pi\) for all \(c\). Thus the cell \(\Pi^W_i[v^W_c]\) is also a cell in \(\Pi\).
From Lemma 7, the partition for \(i\) is well-defined in \(Q^*[W]\) up to the cells containing the valuations \(v^W_c\).
Example 4. Suppose \(\Prop = \{p, q, r\}\), \(\C = \{c_1, c_2\}\) and \(i \in \Srcm\). Consider a world \(W\) where \(i\)’s partition is as follows, with the valuations indicated in green (note that for brevity we do not label the 8 valuations):
Then, by Lemma 7, a partition \(\Pi\) appears as \(\Pi^{W'}_i\) for some \(W' \speceq W\) if and only if it contains the leftmost and bottommost sets as cells. Any such \(\Pi\) consist of these cells together with a partition of the shaded area. Since there are 5 possible partitions of a set of 3 elements, it follows that \(|\P^{Q^*[W]}_i| = 5\).
This example already hints that if the cells containing valuations \(v^W_c\) cover the whole space \(\V\) or just omit a single valuation \(v\), then \(i\)’s partition is unique accross \(Q^*[W]\); this will be formalised below.
We can characterise the conditions under which \(Q^*[W]\) decides an expertise formula \(\E_i\phi\).
Lemma 8
Let \(i \in \Srcm\) and \(U \subseteq \V\). Then \(U \subseteq \bigcup_{c \in \C}{\Pi^W_i[v^W_c]}\) and \(W' \speceq W\) implies \(\Pi^{W'}_i[U] = \Pi^W_i[U]\).
Proof.
By definition,
Note that if \(v \in U\), by assumption there is \(c \in \C\) such that \(v \in \Pi^W_i[v^W_c]\), so \(\Pi^W_i[v^W_c] = \Pi^W_i[v]\). On the other hand, \(W' \speceq W\) means \(\Pi^W_i[v^W_c] = \Pi^{W'}_i[v^{W'}_c]\). Thus \(v \in \Pi^W_i[v] = \Pi^W_i[v^W_c] = \Pi^{W'}_i[v^{W'}_c]\), so \(\Pi^{W'}_i[v] = \Pi^{W'}_i[v^{W'}_c] = \Pi^W_i[v^W_c] = \Pi^W_i[v]\). Therefore
Lemma 9
\(Q^*[W]\) decides \(\E_i\phi\) if and only if, writing \(R = \bigcup_{c \in \C}{\Pi^W_i[v^W_c]}\), either \(R \supseteq \|\phi\|\), \(R \supseteq \|\neg\phi\|\), or there is some \(c \in \C\) such that \(\Pi^W_i[v^W_c]\) intersects with both \(\|\phi\|\) and \(\|\neg\phi\|\).
Proof.
“if”: If \(R \supseteq \|\phi\|\) or \(R \supseteq \|\neg\phi\|\), then by Lemma 8, for all \(W' \in Q^*[W]\) we have \(\Pi^{W'}_i[\phi] = \Pi^W_i[\phi]\) or \(\Pi^{W'}_i[\neg\phi] = \Pi^W_i[\neg\phi]\), respectively. Recalling that expertise is symmetric with respect to negation, we have \(W', c_0 \models \E_i\phi\) iff \(W, c_0 \models \E_i\phi\) in either case (where \(c_0\) is an arbitrary case). Therefore \(Q^*[W]\) decides \(\E_i\phi\).
For the final case, suppose there is some \(c \in \C\) such that \(\Pi^W_i[v^W_c]\) intersects with both \(\|\phi\|\) and \(\|\neg\phi\|\). Then there is \(v_1 \in \Pi^W_i[v^W_c] \cap \|\phi\|\) and \(v_2 \in \Pi^W_i[v^W_c] \cap \|\neg\phi\|\). If \(W' \in Q^*[W]\) then \(\Pi^{W'}_i[v^{W'}_c] = \Pi^W_i[v^W_c]\), so we have \(v_1, v_2 \in \Pi^{W'}_i[v^{W'}_c]\). Since \(v_1 \in \|\phi\|\) but \(v_2 \in \|\neg\phi\|\), this means
i.e. \(\Pi^{W'}_i[\phi] \not\subseteq \|\phi\|\). Hence \(W', c_0 \not\models \E_i\phi\), and thus \(Q^*[W]\) decides \(\E_i\phi\) negatively.
“only if”: We show the contrapositive. Suppose \(R \not\supseteq \|\phi\|\), \(R \not\supseteq \|\neg\phi\|\) and for all \(c \in \C\), either \(\Pi^W_i[v^W_c] \subseteq \|\phi\|\) or \(\Pi^W_i[v^W_c] \subseteq \|\neg\phi\|\). Then there is \(v \in \|\phi\| \setminus R\) and \(v' \in \|\neg\phi\| \setminus R\).
Let us construct worlds \(W_1, W_2\) with the same components as \(W\), except
That is, we first take the cells containing the valuations \(v^W_c\) from \(\Pi^W_i\); for \(W_1\) we partition the remainder \(\V \setminus R\) with a single cell, and for \(W_2\) we partition \(\V \setminus R\) into singleton cells. Then \(W_1, W_2 \in Q^*[W]\).
Since \(v, v'\) are in the same cell in \(\Pi^{W_1}_i\) (namely \(\V \setminus R\)) but differ on \(\phi\), we have \(W_1, c_0 \not\models \E_i\phi\).
We claim \(W_2, c_0 \models \E_i\phi\), i.e. \(\Pi^{W_2}_i[\phi] \subseteq \|\phi\|\). Indeed, take \(\tilde{v} \in \|\phi\|\). We show \(\Pi^{W_2}_i[\tilde{v}] \subseteq \|\phi\|\). If \(\tilde{v} \notin R\) this is clear since in that case \(\Pi^{W_2}_i[v] = \{v\}\). Suppose \(\tilde{v} \in R\). Then \(\tilde{v} \in \|\phi\| \cap \Pi^W_i[v^W_c]\) for some case \(c\). By our assumption, \(\Pi^W_i[v^W_c] \subseteq \|\phi\|\). Note that \(\Pi^W_i[v^W_c]\) is a cell in \(\Pi^{W_2}_i\) and contains \(\tilde{v}\); this means
This shows that \(\Pi^{W_2}_i[\phi] \subseteq \|\phi\|\), so \(W_2, c_0 \models \E_i\phi\). We have now found two worlds \(W_1, W_2\) in \(Q^*[W]\) which disagree on \(\E_i\phi\), and thus \(Q^*[W]\) does not decide \(\E_i\phi\).
We obtain an analogue of Theorem 1 for partitions: equivalent conditions under which \(Q^*[W]\) defines a unique partition for source \(i \in \Srcm\).
Theorem 2
The following are equivalent (where \(R = \bigcup_{c \in \C}{\Pi^W_i[v^W_c]}\)).
\(\P^{Q^*[W]}_i = \{\Pi^W_i\}\)
\(Q^*[W]\) decides \(\E_i\phi\) for all \(\phi \in \L_0\)
For all \(U \subseteq \V\), either \(R \supseteq U\) or \(R \supseteq \V \setminus U\)
\(|\V \setminus R| \le 1\)
Proof.
\((1) \implies (2)\): If \(W' \in Q^*[W]\) then, by (1), we have \(\Pi^{W'}_i = \Pi^W_i\). Hence \(W', c_0 \models \E_i\phi\) iff \(W, c_0 \models \E_i\phi\), for any \(\phi \in \L_0\). Hence \(Q^*[W]\) decides \(\E_i\phi\).
\((2) \implies (3)\): For contradiction, suppose that (2) holds but there is \(U \subseteq \V\) such that both \(R \not\supseteq U\) and \(R \not\supseteq \V \setminus U\). Then there is \(v \in U \setminus R\) and \(v'\) such that \(v' \notin U\) and \(v' \notin R\). Note that \(v \ne v'\).
Now, let \(\phi\) be a propositional formula with \(\|\phi\| = \{v\}\). By (2), \(Q^*[W]\) decides \(\E_i\phi\). Clearly \(R \not\supseteq \|\phi\|\) (since \(v \notin R\)) and also \(R \not\supseteq \|\neg\phi\|\) (since \(v' \in \|\neg\phi\|\) but \(v' \notin R\)). By Lemma 9, there must be some case \(c\) such that \(\Pi^W_i[v^W_c]\) intersects with both \(\|\phi\|\) and \(\|\neg\phi\|\). But \(\|\phi\|\) only contains \(v\), so we get \(v \in \Pi^W_i[v^W_c] \subseteq R\), i.e. \(v \in R\): contradiction.
\((3) \implies (4)\): We show the contrapositive. Suppose \(|\V \setminus R| > 1\). Then there are distinct \(v, v' \in \V \setminus R\). Set \(U = \{v\}\). Then \(R \not\supseteq U\) (since \(v \notin R\)) and \(R \not\supseteq \V \setminus U\) (since \(v' \in \V \setminus U\) but \(v' \notin R\)).
\((4) \implies (1)\): Take \(\Pi \in \P^{Q^*[W]}_i\). Write \(\mathcal{R} = \{\Pi^W_i[v^W_c]\}_{c \in \C}\). Then \(\mathcal{R}\) is a partition of \(R\). By Lemma 7, \(\Pi \supseteq \mathcal{R}\). We now consider two cases.
First, suppose \(|\V \setminus R| = 0\). Then \(\V = R\), so in fact \(\mathcal{R}\) is a partition of \(\V\), and thus \(\Pi = \mathcal{R}\). Since \(\Pi\) was arbitrary, this shows \(\P^{Q^*[W]}_i\) is a singleton set. Clearly \(\Pi^W_i \in \P^{Q^*[W]}_i\), so in fact \(\P^{Q^*[W]}_i = \{\Pi^W_i\}\) as required.
Now suppose \(|\V \setminus R| = 1\). Then \(R = \V \setminus \{v\}\) for some \(v \in \V\). Since \(\Pi \supseteq \mathcal{R}\), it must be the case that \(\Pi \setminus \mathcal{R}\) is a partition of \(\V \setminus R\). But \(\V \setminus R = \{v\}\). Since there is only one partition of a singleton set, we have \(\Pi = \mathcal{R} \cup \{\{v\}\}\). As in the first case, this shows \(\P^{Q^*[W]}_i\) contains a unique partition, and we are done.
Example 5. In Example 4 we have already seen an example where \(\P^{Q^*[W]}_i\) does not contain a unique partition; in that example the shaded region shows \(\V \setminus R\), which contained 3 valuations.
For a positive example, consider the world \(W\) from Example 3. Then \(\V \setminus R_{i_1} = \{p\bar{q}\}\) and \(\V \setminus R_{i_2} = \emptyset\). Consequently both the partitions of \(i_1\) and \(i_2\) can be found uniquely by truth-tracking methods.
Learning the true world exactly¶
Putting things together, we can establish conditions whereby \(W\) can be identified uniquely by truth-tracking methods.
Theorem 3
\(Q^*[W] = \{W\}\) if and only if
There is a collection \(G = \{\Gamma_c\}_{c \in \C} \subseteq \L_0^\C\) such that \(W \models G\), \(W \models \E_{\Srcm}{\Gamma_c}\) for each \(c \in \C\), and \(\Cn_0(\Gamma_c)\) is maximally consistent; and
For each \(i \in \Srcm\), \(|\V \setminus \bigcup_{c \in \C}{\Pi^W_i[v^W_c]}| \le 1\)
Truth-tracking operators¶
In this section we look to see when conditioning and score-based operators are truth-tracking. In doing so we will also see that truth-tracking is compatible with the rationality postulates of the KR paper: it is possible for an operator to satisfy all the basic postulates and simultaneously solve any solvable question.
Conditioning¶
In analogy with conditioning operators, we define a conditioning methods.
Definition 4
Given a mapping \(\X\) taking any finite sequence \(\sigma\) to a set \(\X_\sigma \subseteq \W\), and a total preorder \(\le\) on \(\W\), we define the conditioning operator \(L_{\X, {\le}}\) by
A method \(L\) is said to be a conditioning operator if \(L = L_{\X, {\le}}\) for some \(\X\) and \(\le\).
While at present a characterisation of truth-tracking methods among all conditioning methods is not known, we have a characterisation for a subclass where \(\X\) is “well-behaved” in a certain sense. In what follows, recall that \(\Xsnd_\sigma = \{W \mid \forall \tuple{i, c, \phi} \in \sigma: W, c \models \S_i\phi\}\). For a generic total preorder \(\le\), we let \(<\) denote its strict part. For \(S \subseteq \W\), we denote the set of worlds \(\speceq\)-equivalent to a world in \(S\) by \([S]_{\speceq}\).
Theorem 4
Suppose \(\X_\sigma = \X_\emptyset \cap \Xsnd_\sigma\) for all \(\sigma\). Then \(L = L_{\X, {\le}}\) is consistent and solves \(Q^*\) if and only if
\([\X_\emptyset]_{\speceq} = \W\); and
For all \(W \in \W\) and \(W' \in \X_\emptyset\):
Proof.
“if”: Suppose (1) and (2) hold. First we show \(L\) is consistent. Take any finite sequence \(\sigma\). Note that, since we do not consider reports from \(\ast\), \(\Xsnd_\sigma \ne \emptyset\). Take \(W \in \Xsnd_\sigma\). Then since \([\X_\emptyset]_{\speceq} = \W\), there is \(W' \in \X_\emptyset\) such that \(W' \speceq W\). But this means \(W'\) satisfies the same soundness statements as \(W\), so \(W' \in \Xsnd_\sigma\) also. Hence \(W' \in \X_\emptyset \cap \Xsnd_\sigma = \X_\sigma\), i.e. \(\X_\sigma\). Since \(\W\) is finite, there exist \(\le\)-minimal elements of \(\X_\sigma\), and \(L(\sigma) \ne \emptyset\) as required.
We now show that \(L\) solves \(Q^*\). Take any \(W \in \W\) and let \(\rho\) be a stream for \(W\). The proof is similar to that of Proposition 2. As in that proof, it suffices to show that for any \(W' \not\speceq W\) there is \(n_{W'}\) such that \(W' \notin L(\rho[m])\) for \(m \ge n_{W'}\).
Suppose \(W' \not\speceq W\). We consider two cases.
Case 1: \(W \not\specleq W'\).
By definition of \(\specleq\) there are \(i, c, \phi\) such that \(W, c \models \S_i\phi\) but \(W', c \not\models \S_i\phi\). By completeness of \(\rho\) there is \(n\) such that \(\rho_n = \tuple{i, c, \phi}\), and for \(m \ge n\) we have \(W' \notin \Xsnd_{\rho[m]}\). Since \(L(\rho[m]) \subseteq \X_{\rho[m]} \subseteq \Xsnd_{\rho[m]}\), we get \(W' \notin L(\rho[m])\) as required.
Case 2: \(W \speclt W'\).
By assumption there is \(W'' \in \X_\emptyset\) such that \(W'' \speceq W\) and \(W'' < W'\). From Lemma 2, \(\rho\) is also a stream for \(W''\), so \(W'' \in \Xsnd_{\rho[m]}\) for all \(m\). Hence \(W'' \in \X_\emptyset \cap \Xsnd_{\rho[m]} = \X_{\rho[m]}\). Combined with \(W'' < W'\), this shows that \(W'\) can never be \(\le\)-minimal in \(\X_{\rho[m]}\), for any \(m\). Therefore we may take \(n_{W'} = 1\).
“only if”: Suppose \(L\) is consistent and solves \(Q^*\). First we show (1), i.e. \([\X_\emptyset]_{\speceq} = \W\). Indeed, take \(W \in \W\). Let \(\rho\) be any stream for \(W\). Since \(L\) solves \(Q^*\), there is \(n\) such that \(L(\sigma) \subseteq Q^*[W]\), where \(\sigma = \rho[n]\). On the other hand \(L(\sigma) \subseteq \X_\emptyset\) always holds, so we have \(L(\sigma) \subseteq Q^*[W] \cap \X_\emptyset\). By consistency of \(L\), there is some \(W' \in Q^*[W] \cap \X_\emptyset\). This shows \(W \in [\X_\emptyset]_{\speceq}\).
Next we show \(\le\) satisfies (2). Suppose \(W \in \W\), \(W' \in \X_\emptyset\) and \(W \speclt W'\). Again, take any stream \(\rho\) for \(W\) and write \(\sigma = \rho[n]\), where \(n\) is sufficiently large so that \(L(\sigma) \subseteq Q^*[W] \cap \X_\emptyset\). By consistency, there is some \(W'' \in L(\sigma)\). Clearly \(W'' \in \X_\emptyset\) and \(W'' \speceq W\). We need to show \(W'' < W'\).
Now, since \(W \speclt W'\), any statement sound for \(W\) is also sound for \(W'\). Thus \(\rho\) is sound for \(W'\), so \(W' \in \Xsnd_\sigma\). Since we also assumed \(W' \in \X_\emptyset\), we have \(W' \in \X_\emptyset \cap \Xsnd_\sigma = \X_\sigma\). But \(L(\sigma) \subseteq Q^*[W]\); since \(W' \not\speceq W\) this means \(W' \in \X_\sigma \setminus L(\sigma) = \X_\sigma \setminus \min_{\le}{\X_\sigma}\). Since \(W''\) is \(\le\)-minimal in \(\X_\sigma\) and \(\le\) is total, it follows that \(W'' < W'\), as required.
Corollary 2
An elementary conditioning operator satisfying the basic postulates is truth-tracking if and only if (1) and (2) from Theorem 4 hold.
Proof. Consider an elementary conditioning operator corresponding to a mapping \(\X\) and total preorder \(\le\). The corresponding method is given by \(L(\sigma) = \mods(B^\sigma) = \Y_\sigma = \min_{\le}{\X_\sigma}\), so is itself a conditioning method. From the basic postulates and Proposition 3 in the KR paper, we have \(K^\sigma = \Cn(G^\sigma_{\textsf{snd}} \sqcup K^\emptyset)\); taking models of both sides we find \(\X_\sigma = \Xsnd_\sigma \cap \X_\emptyset\). Note that \(L\) is consistent by the basic postulate Consistency (noting that since our sequences do not involve \(\ast\), they are always \(\ast\)-consistent). The result now follows from Theorem 4.
If we think of \(\X_\emptyset\) as prior knowledge, property (1) in Theorem 4 says that no answer in \(Q^*\) – alternatively, no equivalence class of \(\speceq\) – is ruled out apriori. Property (2) is technical, but can be seen as a modification of Refinement, from the paper:
Refinement: If \(W \preceq W'\) then \(W \le W'\)
(where \(W \preceq W'\) iff \(\Pi^W_i \preceq \Pi^{W'}_i\) for all \(i\)). Recall that, by definition of partition refinement, \(\Pi^W_i \preceq \Pi^{W'}_i\) iff \(\Pi^W_i[v] \subseteq \Pi^{W'}_i[v]\) for all \(v \in \V\). Referring to Lemma 1, we see that \(\specleq\) is a modification of \(\preceq\), where we only care about \(v\) equal to some valuation in \(\{v^W_c\}_{c \in \C}\), and only about ordinary sources \(i \ne \ast\).
If we then consider the strict version of Refinement, but using \(\specleq\) instead of \(\preceq\), we obtain the following postulate:
If \(W \speclt W'\) then \(W < W'\).
Condition (2) can now be seen as a further modification of this postulate, in which we only consider apriori possible \(W'\) (since the ordering of \(W' \notin \X_\emptyset\) never affects \(L(\sigma)\)), and where some apriori possible \(W''\), which is \(\speceq\)-equivalent to \(W\), may take the place of \(W\) in the consequent.
Example 6. Recall the conditioning operator \(\vbc{}\) from the paper: \(\X_\sigma = \Xsnd_\sigma\), and \(W \le W'\) iff \(r(W) \le r(W')\), where
Then property (1) holds, since \(\X_\emptyset = \W\). However, property (2) does not hold in general. To see this, consider
and worlds \(W, W'\) as shown below.
Then \(W \speclt W'\). Clearly \(i\) does not have expertise on either \(p\) or \(q\) in \(W, W'\), so \(r(W) = r(W') = 0\) and \(W \simeq W'\). From Theorem 2, we in fact see that \(i\)’s partition is defined uniquely in \(Q^*[W]\), so for any \(W'' \speceq W\) we also have \(r(W'') = 0\). Hence \(W'' \simeq W'\). This means there is no world equivalent to \(W\) which is strictly preferred to \(W'\), and thus property (2) fails.
Consequently, \(\vbc{}\) is not truth-tracking. Concretely, if \(W\) above were the “true” world, \(\vbc{}\) would always (incorrectly) maintain that \(W'\) is a possibility.
Example 7. Recall another conditioning operator, \(\pbc{}\), where \(\X_\sigma = \Xsnd_\sigma\) again, and \(W \le W'\) iff \(r(W) \le r(W')\) with
Again, property (1) holds. This time property (2) does also. Indeed, suppose \(W \speclt W'\). Write \(\mathcal{R}_i = \{\Pi^W_i[v^W_c]\}_{c \in \C}\). We define a new world \(W''\) with the same valuations as \(W\), but with partitions given by
for \(i \in \Srcm\) (note that this is the same construction as \(W_2\) in the proof of Lemma 9). Then \(W'' \speceq W\). Then, for each \(i\), \(\Pi^{W''}_i\) refines \(\Pi^{W'}_i\), so \(|\Pi^{W''}_i| \ge |\Pi^{W'}_i|\). Hence \(r(W'') \le r(W')\). Moreover, since \(W \speclt W'\) strictly, there is \(i \in \Srcm\) such that \(\Pi^{W''}_i\) strictly refines \(\Pi^{W'}_i\), so \(|\Pi^{W''}_i| > |\Pi^{W'}_i|\). Hence \(r(W'') < r(W')\), and \(W'' < W\) as required.
Therefore \(\pbc{}\) is truth-tracking.
Score-based¶
We define score-based methods in the special case where the prior ranking \(r_0\) is flat.
Definition 5
Given a function \(d: \W \times (\Srcm \times \C \times \L_0) \to \N \cup \{\infty\}\), write
and
We then define the (flat) score-based operator \(L_d\) by
As with conditioning methods, we give a truth-tracking characterisation only for a restricted subclass of score-based methods. We need a preliminary definition: say that a finite sequence \(\sigma\) is pseudo-complete for \(W\) if for all \(i \in \Srcm\), \(c \in \C\) and \(\phi \in \L_0\), if \(W, c \models \S_i\phi\) then there is \(\psi \equiv \phi\) such that \(\tuple{i, c, \psi} \in \sigma\). That is, every sound report is equivalent to some report in \(\sigma\). Note that since we work in a finite framework, psuedo-complete sequences do indeed exist.
Theorem 5
Suppose \(d\) is such that
\(d(W, \tuple{i, c, \phi}) = \infty\) iff \(W, c \not\models \S_i\phi\); and
If \(\phi \equiv \psi\) then \(d(W, \tuple{i, c, \phi}) = d(W, \tuple{i, c, \psi})\).
Then \(L_d\) is consistent, and \(L_d\) solves \(Q^*\) if and only if the following property holds:
If \(W \speclt W'\) and \(\sigma\) is sound and pseudo-complete for \(W\), then there is \(W''\) such that \(r^d_\sigma(W'') < r^d_\sigma(W')\).
Proof.
First, note that by property (1), \(\X^d_\sigma = \Xsnd_\sigma\) for all inputs \(\sigma\). It follows that \(L_d\) is consistent. We show \(L = L_d\) solves \(Q^*\) iff the stated property holds.
“if”: Take any world \(W\) and a stream \(\rho\) for \(W\). The proof is similar to that of Proposition 2 and Theorem 4: we show that for all \(W' \not\speceq W\) there is \(n_{W'}\) such that \(W' \notin L(\rho[m])\) for all \(m \ge n_{W'}\).
Case 1: \(W \not\specleq W'\).
The argument is essentially the same as in the proof of Theorem 4.
Case 2: \(W \speclt W'\).
Since \(\rho\) is complete and we work in a finite framework, there is \(n\) such that \(\rho[m]\) is pseudo-complete for all \(m \ge n\). Since \(\rho\) is sound for \(W\), \(\rho[m]\) is also sound. For such \(m\), we may invoke the assumed property to find the existence of \(W''\) such that \(r^d_{\rho[m]}(W'') < r^d_{\rho[m]}(W')\). Consequently \(W'\) is not minimal with respect to \(r^d_{\rho[m]}\), so \(W' \notin L(\rho[m])\).
“only if”: Suppose \(L\) solves \(Q^*\). Take \(W, W'\) such that \(W \speclt W'\), and let \(\sigma\) be sound and psuedo-complete for \(W\). For any formula \(\phi \in \L_0\), let \(\{\psi^\phi_k\}_{k \in \N}\) enumerate the set of propositional formulas logically equivalent to \(\phi\). For any \(k \in \N\), let \(\sigma_k\) be the sequence obtained by replacing each report \(\tuple{i, c, \phi}\) with \(\tuple{i, c, \psi^\phi_k}\). Let \(\rho\) be the inifinite sequence formed by concatenating all the \(\sigma_k\).
We claim \(\rho\) is a stream for \(W\). Indeed, since \(\sigma\) is sound for \(W\) and \(\S_i\phi \equiv \S_i\psi\) whenever \(\phi \equiv \psi\), each \(\sigma_k\) is sound for \(W\). Hence \(\rho\) is also. For completeness, note that if \(W, c \models \S_i\psi\), psuedo-completeness of \(\sigma\) implies there is \(\phi\) such that \(\phi \equiv \psi\) and \(\tuple{i, c, \phi} \in \sigma\). Hence there is \(k \in \N\) such that \(\psi = \psi^\phi_k\), and thus \(\tuple{i, c, \psi} \in \sigma_k\). Hence \(\tuple{i, c, \psi} \in \rho\), so \(\rho\) is complete.
Since \(L\) solves \(Q^*\), there is \(n\) with \(L(\rho[m]) \subseteq Q^*[W]\) for all \(m \ge n\). Since \(W \speclt W'\), this means \(W' \notin L(\rho[m])\) for such \(m\). Now, let \(m = l \cdot |\sigma|\) be an integer multiple of \(|\sigma|\), with \(l > 0\) sufficiently large so that \(m \ge n\).
Note that by property (2), \(r^d_{\sigma_k}(\tilde{W}) = r^d_\sigma(\tilde{W})\) for any \(k \in \N\) and any \(\tilde{W}\). It follows that
Since \(W \speclt W'\), \(\rho\) is also sound for \(W'\). Thus \(W' \in \Xsnd_{\rho[m]} = \X^d_{\rho[m]}\). But \(W' \notin L(\rho[m])\), so \(W'\) is not minimal in \(\X^d_{\rho[m]}\) with respect to \(r^d_{\rho[m]}\). Thus there must be some \(W'' \in \X^d_{\rho[m]}\) with \(r^d_{\rho[m]}(W'') < r^d_{\rho[m]}(W')\). Dividing by \(l\) and using the above, we get \(r^d_{\sigma}(W'') < r^d_{\sigma}(W')\), as required.
Property (1) ensures that a report \(\tuple{i, c, \phi}\) is considered impossible at world \(W\) iff it is unsound. Property (2) ensures that the scores assigned to logically equivalent reports are equal. The property that then characterises truth-tracking, when (1) and (2) hold, is another variation of property (2) from Theorem 4, which characterised truth-tracking for conditioning operators.
Example 8. The score-based operator \(\excessmin{}\), given by
is truth-tracking. Clearly properties (1) and (2) hold. Let \(L\) be the corresponding method. Since \(\X^d_\sigma = \Xsnd_\sigma\) and \(\Y_\sigma = \argmin_{W \in \Xsnd_\sigma}{r^d_\sigma(W)}\) is elementary, \(L\) is a score-based method corresponding to the same scoring function \(d\).
To show the property of Theorem 5 is satisfied, suppose \(W \speclt W'\) and \(\sigma\) is a sound and psuedo-complete sequence for \(W\). We define \(W''\) from \(W\) in exactly the same way as in Example 7. Then \(W'' \speceq W\), \(\Pi^{W''}_i\) refines \(\Pi^{W'}_i\) for all \(i \in \Srcm\), and there is some \(i\) for which this is strict refinement.
From \(W'' \speceq W\) and soundness of \(\sigma\) for \(W\), we have \(r^d_{\sigma}(W'') < \infty\). From the refinement property it follows that \(\Pi^{W''}_i[\phi] \subseteq \Pi^{W'}_i[\phi]\), and thus \(d(W'', \tuple{i, c, \phi}) \le d(W', \tuple{i, c, \phi})\) for all \(\tuple{i, c, \phi} \in \sigma\). Hence \(r^d_\sigma(W'') \le r^d_\sigma(W')\).
Recall there is some \(i\) for which the refinement is strict. For this \(i\), there is \(v \in \V\) such that \(\Pi^{W''}_i[v] \subset \Pi^{W'}_i[v]\). It can be assumed without loss of generality that there is \(c \in \C\) such that \(v \in \Pi^{W''}_i[v^{W''}_c]\). 5 By psuedo-completeness of \(\sigma\), there is some formula \(\phi \in \L_0\) such that \(\|\phi\| = \{v\}\) and \(\tuple{i, c, \phi} \in \sigma\). We see that \(d(W'', \tuple{i, c, \phi}) < d(W', \tuple{i, c, \phi})\), and consequently \(r^d_\sigma(W'') < r^d_\sigma(W')\), as required.
General operators¶
The characterisations of truth-tracking for conditioning and score-based operators had a semantic flavour, since we looked at properties of \(\le\) or \(d\) at the level of worlds. We now offer a syntactic characterisation for operators satisfying the basic postulates.
We need some preliminary definitions and results. Write \(\Gsnd\) for the set of collections \(G\) which only contain formulas of the form \(\S_i\phi\) and \(\neg\S_i\phi\), for \(i \in \Srcm\) and \(\phi \in \L_0\). Write \(\Msnd\) for the maximally consistent collections among \(\Gsnd\), i.e.
Lemma 10
Let \(G = \{\Gamma_C\}_{c \in\ C} \in \Gsnd\). Then \(G \in \Msnd\) if and only if there is \(W \in \W\) such that
Moreover, for such \(G\) and \(W\) we have \(\mods(G) = Q^*[W]\).
Proof.
We show the first statement.
“if”: Suppose there is \(W\) with the stated property. Clearly \(W\) is a model of \(G\), so \(G\) is consistent. We need to show \(G\) is maximally consistent. Take \(G' \in \Gsnd\) consistent such that \(G \sqsubseteq G'\). We will show that \(G = G'\).
Indeed, since \(G'\) is consistent there is some \(W' \in \mods(G') \subseteq \mods(G)\). By construction of \(G\), \(W'\) and \(W\) satisfy exactly the same soundness statements. Now, take any \(c \in \C\). If \(\S_i\phi \in \Gamma'_c\) then \(W', c \models \S_i\phi\), so \(W, c \models \S_i\phi\) also. Hence \(\S_i\phi \in \Gamma_c\). On the other hand, if \(\neg\S_i\phi \in \Gamma'_c\) then \(W', c \not\models \S_i\phi\), so \(W, c \not\models \S_i\phi\) also, and \(\neg\S_i\phi \in \Gamma_c\). Since \(G' \in \Gsnd\), this covers all possible formulas in \(\Gamma'_c\). Thus \(\Gamma'_c \subseteq \Gamma_c\) for all \(c\), so \(G' \sqsubseteq G\). Since \(G \sqsubseteq G\) also, we have \(G = G'\) as required.
“only if”: Suppose \(G \in \Msnd\). Then \(G\) is consistent, so there is some \(W \in \mods(G)\). Let \(\Delta_c\) denote the set on the right-hand side in \((*)\). We will show that \(\Gamma_c = \Delta_c\), for each \(c \in \C\). The left-to-right inclusion is clear since \(W\) is a model of \(G\) and \(G \in \Gsnd\).
For the right-to-left inclusion, first suppose \(\S_i\phi \in \Delta_c\). Then \(W, c \models \S_i\phi\). Consider the collection \(G'\) obtained from \(G\) by adding \(\S_i\phi\) to case \(c\). Then clearly \(G \sqsubseteq G'\), \(G' \in \Gsnd\), and \(G'\) is consistent (since \(W\) is a model). Since \(G \in \Msnd\) we get \(G = G'\), i.e. \(\S_i\phi \in \Gamma_c\). Similarly, if \(\neg\S_i\phi \in \Delta_c\) then we can consider the collection \(G''\) obtained by adding \(\neg\S_i\phi\). By maximal consistency of \(G\) we find \(G = G''\), so \(\neg\S_i\phi \in \Gamma_c\). Consequently \(\Gamma_c = \Delta_c\), as required.
It only reamins to show that \(\mods(G) = Q^*[W]\). Indeed, by the expression for \(\Gamma_c\) in \((*)\) we have that \(W' \in \mods(G)\) iff \(W' \speceq W\).
Say a finite sequence \(\sigma\) is duplicate-free
- 1
Here we assume \(\Phi\) is neither a tautology nor a contradiction.
- 2
\(\Pi \preceq \Pi'\) iff for all \(x\), \(\Pi[x] \subseteq \Pi'[x]\). Equivalently, every cell in \(\Pi'\) is a union of cells from \(\Pi\).
- 3
This condition appears in the KR paper, where is called refinement at \(c\).
- 4
For the “only if” direction, consider the contrapositive. Take \(v \in \|\phi\|\), \(v' \in \|\neg\phi\|\), \(\tilde{v} \notin \{v, v'\}\). Let \(W_1, W_2\) have \(c\)-valuation \(\tilde{v}\) for all \(c\), and \(\Pi^{W_1}_i = \{\{\tilde{v}\}, \V \setminus \tilde{v}\}\), \(\Pi^{W_2}_i = \{\{\tilde{v}\}, \|\phi\| \setminus \{\tilde{v}\}, \|\neg\phi\| \setminus \{\tilde{v}\}\}\). Then \(W_1 \speceq W_2\) but \(W_1, c_0 \models \neg\E_i\phi\) and \(W_2, c_0 \models \E_i\phi\).
- 5
This follows from the fact that, since \(W \speclt W'\), there is \(c\) such that \(\Pi^W_i[v^W_c] \subset \Pi^{W'}_i[v^{W'}_c]\).