Vol-3197/paper8
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3197/paper8 |
| wikidataid | →Q117341826 |
| title | Truth-Tracking with Non-Expert Information Sources |
| pdfUrl | https://ceur-ws.org/Vol-3197/paper8.pdf |
| dblpUrl | https://dblp.org/rec/conf/nmr/Singleton022 |
| volume | Vol-3197→Vol-3197 |
| session | → |
Truth-Tracking with Non-Expert Information Sources
Truth-Tracking with Non-Expert Information Sources
Joseph Singleton1 , Richard Booth1
1
Cardiff University, Cardiff, UK
Abstract
We study what can be learned when receiving reports from multiple non-expert information sources. We suppose that sources
report all that they consider possible, given their expertise. This may result in false and inconsistent reports when sources
lack expertise on a topic. A learning method is truth-tracking, roughly speaking, if it eventually converges to correct beliefs
about the “actual” world. This involves finding both the actual state of affairs in the domain described by the sources, and
finding the extent of the expertise of the sources themselves. We investigate the extent to which truth-tracking is possible,
and describe what information can be learned even if the actual world cannot be pinned down uniquely. We find that a broad
spread of expertise among the sources allows the actual state of affairs to be found, even if no individual source is an expert
on all topics. On the other hand, narrower expertise at the individual level allows the actual expertise to be found more easily.
Finally, we turn to learning methods themselves: we provide a postulate-based characterisation of truth-tracking for general
methods under mild assumptions, before looking at a specific class of methods well-known from the belief change literature.
1. Introduction This is close to our setting, since incoming information
is not always assumed to be reliable, and information
In this paper we study truth-tracking in the logical frame- about the sources themselves is sought after. Work in
work of Singleton and Booth [1] for reasoning about mul- this area combines empirical results (e.g. how well meth-
tiple non-expert information sources. Broadly speaking, ods find the truth on test datasets for which true values
the goal of truth-tracking is to find the true state of the are known) and theoretical guarantees, and is typically
world given some input which describes it. In our case set in a probabilistic framework.
this involves finding the true state of some propositional On the other hand, formal learning theory [9] offers a
domain about which the sources give reports, and finding non-probabilistic view on truth-tracking, stemming from
the extent of the expertise of the sources themselves. the framework of Gold [10] for identification in the limit.
The general problem of truth-tracking has been stud- In this paradigm a learner receives an infinite sequence of
ied in various forms across many domains. Perhaps the information step-by-step, such that all true information
oldest approach goes back to de Condorcet [2], whose eventually appears in the sequence. The learner outputs
celebrated Jury Theorem states that a majority vote on a hypothesis at each step, and aims to stabilise on the cor-
a yes/no issue will yield the “correct” answer with prob- rect hypothesis after some finite number of steps. This
ability approaching 1 as the number of voters tends to framework has been combined with belief revision the-
infinity, provided that each voter is more reliable than ory [11, 12] and dynamic epistemic logic [13, 14, 15, 16].
random choice. This result has since been generalised in This is the approach we take, and in particular we
many directions (e.g. by Grofman et al. [3]). More widely, adapt the truth-tracking setting of Baltag et al. [12]. We
epistemic social choice [4] studies aggregation methods apply this to the logical framework of Singleton and
(e.g. voting rules) from the point of finding the “correct” Booth [1]. Briefly, this framework extends finite propo-
result with high probability, where individual votes are sitional logic with two new notions: that of a source
seen as noisy approximations. Of particular relevance having expertise on a formula, and a formula being sound
to our work is truth-tracking in judgement aggregation for a source to report. Intuitively, expertise on 𝜙 means
in social choice [5, 6], which also takes place in a logical the source has the epistemic capability to distinguish be-
framework. Belief merging has close links with judge- tween any pair of 𝜙 and ¬𝜙 states: they know whether or
ment aggregation, and generalised jury theorems have not 𝜙 holds in any state. A formula is sound for a source
been found here too [7]. if it is true up to their lack of expertise. For example, if a
In crowdsourcing, the problem of truth discovery [8] source has expertise on 𝜙 but not 𝜓, then 𝜙 ∧ 𝜓 is sound
looks at how information from unreliable sources can whenever 𝜙 holds, since we can ignore the 𝜓 part (on
be aggregated to find the true value of a number of vari- which the source has no expertise). The resulting logical
ables, and to find the true reliability level of the sources. language therefore addresses both the ontic facts of the
NMR 2022: 20th International Workshop on Non-Monotonic Reasoning,
world, through the propositional part, and the epistemic
August 07–09, 2022, Haifa, Israel state of the sources, via expertise and soundness.
$ singletonj1@cardiff.ac.uk (J. Singleton); boothr2@cardiff.ac.uk For the most part, formal learning theory supposes
(R. Booth) that all information received is true, and that all true
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0). information is eventually received.1 This is not a ten-
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
80
�able assumption with non-expert sources: some sources
may simply lack the expertise to know whether 𝜙 is true vA p̄q p̄q̄ ΠD
or false. Instead we make a different (and strong) as-
sumption: all and only sound reports are received. Thus,
sources report everything consistent with their expertise,
which necessitates inconsistent reports from non-experts.
Consequently, the input to our learning methods should
vB pq pq̄ ΠT
be distinguished from the inputs to belief revision and
belief merging methods [17, 18] – also propositional for-
mulas – which represent beliefs of the reporting sources. Figure 1: Example of a world 𝑊 , which formalises Example 1.
Here Prop = {𝑝, 𝑞}, 𝒮 = {D, T} and 𝒞 = {𝐴, 𝐵}.
Indeed, we do not model beliefs of the sources at all.
The following example informally illustrates the core
concepts of the logical framework and truth-tracking,
and will be returned to throughout the paper. 2. Preliminaries
Example 1. Consider a medical scenario in which patient In this section we recall the logical framework of Single-
𝐴 is checked for conditions 𝑝 and 𝑞. By examining 𝐴, a ton and Booth [1] for reasoning with non-expert sources.
doctor D has expertise to determine whether 𝐴 has at least
one of 𝑝 or 𝑞, but cannot tell which one(s) without a blood Syntax. Let Prop be a finite set of propositional vari-
test. A test is only available for 𝑝, however, so that the ables, and let ℒ0 denote the propositional language gen-
technician T performing the test has expertise on 𝑝 but not erated from Prop. We use ℒ0 to model the domain under-
𝑞. lying the truth-tracking problem; it describes the “ontic”
Supposing 𝐴 in fact suffers from 𝑞 but not 𝑝, D considers facts of the world, irrespective of the expertise of the
each of 𝑝 ∧ 𝑞, ¬𝑝 ∧ 𝑞 and 𝑝 ∧ ¬𝑞 possible, whereas T sources. Formulas in ℒ0 will be denoted by lower-case
considers both ¬𝑝∧𝑞 and ¬𝑝∧¬𝑞 possible. Assuming both Greek letters (𝜙, 𝜓, etc).
sources report all they consider possible, their combined Let 𝒮 be a finite set of sources. The language ℒ ex-
expertise leaves ¬𝑝 ∧ 𝑞 as the only possibility. Intuitively, tends ℒ0 with expertise and soundness formulas for each
this means we can find the true values of 𝑝 and 𝑞 in this source 𝑖 ∈ 𝒮, and is defined by the following grammar:
case.
Now consider a patient 𝐵 who suffers from both condi- Φ ::= 𝜙 | E𝑖 𝜙 | S𝑖 𝜙 | Φ ∧ Φ | ¬Φ,
tions. D cannot distinguish 𝐴 and 𝐵, so will provide the
same reports, and T considers both 𝑝 ∧ 𝑞 and 𝑝 ∧ ¬𝑞 pos- for 𝜙 ∈ ℒ0 and 𝑖 ∈ 𝒮. Formulas in ℒ will be denoted
sible. In this case T is more knowledgable than D – since by upper-case Greek letters (Φ, Ψ etc). Other logical
they consider fewer situations possible – but we cannot connectives (∨, →, ↔) are introduced as abbreviations.
narrow down the true value of 𝑞. Thus truth-tracking is We read E𝑖 𝜙 as “𝑖 has expertise on 𝜙”, and S𝑖 𝜙 as “𝜙
only possible for 𝑝. The second patient still provides useful is sound for 𝑖”. Note that we restrict the expertise and
information, though, since together with the reports on 𝐴, soundness formulas to propositional arguments, and do
T’s lack of expertise tells us all the (in)distinctions between not considered iterated formulas such as E𝑖 S𝑗 𝜙.
states they are able to make. Namely, T cannot distinguish
between 𝑝 ∧ 𝑞 and 𝑝 ∧ ¬𝑞. Thus we can find the truth about Semantics. Let 𝒱 denote the set of propositional valu-
T’s expertise. ations over Prop. We represent the expertise of a source
𝑖 with a partition Π𝑖 of 𝒱. Intuitively, this partition rep-
Paper outline. In Section 2 we outline the logical resents the distinctions between states the source is able
framework for reasoning about expertise. Section 3 in- to make: valuations in the same cell in Π𝑖 are indistin-
troduces the key concepts of truth-tracking and solvable guishable to 𝑖, whereas 𝑖 is able to tell apart valuations
questions. We characterise solvable questions in Sec- in different cells. We say 𝑖 has expertise on 𝜙 iff 𝑖 can
tion 4, and explore what they can reveal about the actual distinguish all 𝜙 states from ¬𝜙 states, and 𝜙 is sound
world in Section 5. Section 6 looks at learning methods for 𝑖 if the “actual” state is indistinguishable from some
themselves, and characterises truth-tracking methods. 𝜙 state.
We conclude in Section 7. Let 𝒞 be a finite set of cases, thought of as independent
instantiations of the domain of interest. For example, the
cases in Example 1 are the patients 𝐴 and 𝐵. We consider
the expertise of sources to be fixed across all cases.
1
But see Jain et al. [9, §8.1], which considers inaccurate data of A world is a pair 𝑊 = ⟨{𝑣𝑐 }𝑐∈𝒞 , {Π𝑖 }𝑖∈𝒮 ⟩, where
various kinds, and Baltag et al. [12], which considers erroneous
reports provided that all errors are eventually corrected. • 𝑣𝑐 ∈ 𝒱 is the “actual” valuation for case 𝑐;
81
� • Π𝑖 ⊆ 2𝒱 is a partition representing the expertise 3. Truth-Tracking
of 𝑖.
We adapt the framework for truth-tracking from [21,
Let 𝒲 denote the set of worlds. Note that 𝒲 is finite, 12], which finds its roots in formal learning theory. In
since 𝒱, 𝒞 and 𝒮 are. For 𝜙 ∈ ℒ0 , write ‖𝜙‖ ⊆ 𝒱 for this framework, a learning method receives increasing
the models of 𝜙, and write 𝑣 ⊩ 𝜙 iff 𝑣 ∈ ‖𝜙‖. The initial segments of an infinite sequence – called a stream
consequences of a set Γ ⊆ ℒ0 is denoted by Cn0 (Γ), – which enumerates all (and only) the true propositions
and we write Γ ⊩ 𝜙 if 𝜙 ∈ Cn0 (Γ). For a partition Π, observable at the “actual” world. Truth-tracking requires
let Π[𝑣] denote⋃︀the unique cell in Π containing 𝑣, and the method to eventually find the actual world (or some
write Π[𝑈 ] = 𝑣∈𝑈 Π[𝑣] for 𝑈 ⊆ 𝒱. For brevity, we property thereof), given any stream.
write Π[𝜙] instead of Π[‖𝜙‖]. We evaluate ℒ formulas As mentioned in the introduction, in our setting we
with respect to a world 𝑊 and a case 𝑐 as follows: cannot assume the sources themselves report only true
propositions. Instead, our streams will enumerate all the
𝑊, 𝑐 |= 𝜙 ⇐⇒ 𝑣𝑐 ⊩ 𝜙 sound reports. Thus, a stream may include false reports,
𝑊, 𝑐 |= E𝑖 𝜙 ⇐⇒ Π𝑖 [𝜙] = ‖𝜙‖ but such false reports only arise due to lack of expertise of
𝑊, 𝑐 |= S𝑖 𝜙 ⇐⇒ 𝑣𝑐 ∈ Π𝑖 [𝜙], the corresponding source.3 Moreover, all sound reports
will eventually arise. Since S𝑖 𝜙 means 𝜙 is possible from
where the clauses for conjunction and negation are as the point of view of 𝑖’s expertise, we can view a stream
standard. The semantics follows the intuition outlined as each source sharing all that they consider possible for
above: E𝑖 𝜙 holds when Π𝑖 separates the 𝜙 states from each case 𝑐 ∈ 𝒞. In particular, a non-expert source may
the ¬𝜙 states, and S𝑖 𝜙 holds when 𝑣𝑐 is indistinguishable report both 𝜙 and ¬𝜙 for the same case.
from some 𝜙 state. Thus, S𝑖 𝜙 means 𝜙 is true up to the
expertise of 𝑖: if we weaken 𝜙 according to 𝑖’s expertise, Definition 1. An infinite sequence of reports 𝜌 is a stream
the resulting formula (with models Π𝑖 [𝜙]) is true. for 𝑊 iff for all 𝑖, 𝑐, 𝜙:
Note that expertise and soundness are closely related
⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝜌 ⇐⇒ 𝑊, 𝑐 |= S𝑖 𝜙.
to S5 knowledge from epistemic logic. By taking the equiv-
alence relations associated with each partition Π𝑖 , we We refer to the left-to-right implication as soundness
obtain a (multi-agent) S5 Kripke model, and have the cor- of 𝜌 for 𝑊 , and the right-to-left direction as complete-
respondences S𝑖 𝜙 ≡ ¬K𝑖 ¬𝜙 and E𝑖 𝜙 ≡ A(𝜙 → K𝑖 𝜙), ness. Note that every world 𝑊 has some stream: the set
where K𝑖 denotes knowledge of source 𝑖 and A is the uni- {⟨𝑖, 𝑐, 𝜙⟩ | 𝑊, 𝑐 |= S𝑖 𝜙} is countable, so can be indexed
versal modality [19]. This gives expertise and soundness by N to form a stream. For 𝑛 ∈ N we let 𝜌𝑛 denote
precise interpretations in terms of knowledge; we refer the 𝑛-th report in 𝜌, and write 𝜌[𝑛] for the finite initial
the reader to [1, 20] for further discussion. segment of 𝜌 of length 𝑛.
Example 2. Take 𝑊 from Fig. 1, which formalises Ex- Example 3. Consider 𝑊 from Fig. 1 and case 𝐴. From
ample 1. Then 𝑊, 𝑐 |= ED (𝑝 ∨ 𝑞) for all 𝑐 ∈ 𝒞, since the point of view of D’s expertise, the “actual” valuation
‖𝑝 ∨ 𝑞‖ is a cell in ΠD . We also have 𝑊, 𝐴 |= ¬𝑝 ∧ SD 𝑝, could be 𝑝𝑞, 𝑝 ¯𝑞, 𝑝𝑞¯. Consequently, in a stream for 𝑊 , D
i.e. patient 𝐴 does not suffer from condition 𝑝, but it is will report 𝑝, ¬𝑝, 𝑞, ¬𝑞, 𝑝 ∨ 𝑞, and so on. A report that D
consistent with D’s expertise that they do. will not give is ¬(𝑝 ∨ 𝑞), since D has expertise to know
We write 𝑊, 𝑐 |= Γ, for a set of formulas Γ ⊆ ℒ, if this is false.
𝑊, 𝑐 |= Φ for all Φ ∈ Γ. For a set 𝑆 ⊆ 𝒲, we write Note that 𝑣𝐴 and 𝑣𝐵 are indistinguishable to D, so the
𝑆, 𝑐 |= Φ iff 𝑊, 𝑐 |= Φ for all 𝑊 ∈ 𝑆. reports of D in any stream will be the same for both cases.
In contrast, T can distinguish the two cases, and will report
¬𝑝 in case 𝐴 but not in 𝐵, and 𝑝 in case 𝐵 but not in 𝐴.
Reports. A report is a triple ⟨𝑖, 𝑐, 𝜙⟩, where 𝑖 ∈ 𝒮, 𝑐 ∈
𝒞 and 𝜙 ∈ ℒ0 with 𝜙 ̸≡ ⊥. In this paper, we interpret A question 𝑄 is a partition of 𝒲. That is, a question
such triples as source 𝑖 reporting that 𝜙 is possible in is a set of disjoint answers 𝐴 ∈ 𝑄, with each world 𝑊
case 𝑐. An input sequence 𝜎 is a finite sequence of reports. appearing in a unique cell 𝑄[𝑊 ] – the correct answer at
A method 𝐿 maps each input sequence 𝜎 to a set of 𝑊.
worlds 𝐿(𝜎) ⊆ 𝒲, called the conjecture of 𝐿 on 𝜎.2 We
say 𝐿 implies 𝑆 ⊆ 𝒲 on the basis of 𝜎 if 𝐿(𝜎) ⊆ 𝑆. 𝐿 Example 4. We consider some example questions.
is consistent if 𝐿(𝜎) ̸= ∅ for all input sequences 𝜎.
2 3
We depart from the original framework here by taking a semantic Alternatively, we can consider statements of the form “𝜙 is sound
view of belief change operators, with the output a set of worlds for 𝑖 in case 𝑐” as a higher-order “proposition”; a stream then
instead of formulas. enumerates all true propositions of this kind.
82
� 1. Any formula Φ ∈ ℒ and case 𝑐 defines a question answers of 𝑄, and thus 𝑄′ is easier than 𝑄. Naturally, if
𝑄Φ,𝑐 , whose two cells consist of the worlds satisfy- 𝑄 is solvable then so too is any easier question.
ing Φ, respectively ¬Φ, in case 𝑐. Intuitively, this
question asks whether Φ is true or false in case 𝑐. Proposition 2. If 𝑄 is solvable and 𝑄 ⪯ 𝑄′ , then 𝑄′ is
solvable.
2. The finest question 𝑄⊥ = {{𝑊 } | 𝑊 ∈ 𝒲}
asks: what is the “actual” world? Proof. The method which solves 𝑄 also solves 𝑄′ .
3. More generally, for any set 𝑋 and function 𝑓 : Since question solving is based on streams of sound
𝒲 → 𝑋, the equivalence relation given by 𝑊 ≃𝑓 reports, worlds satisfying the same soundness statements
𝑊 ′ iff 𝑓 (𝑊 ) = 𝑓 (𝑊 ′ ) defines a question 𝑄𝑓 . cannot be distinguished by any solvable question. To
formalise this, define a preorder ⊑ on 𝒲 by
In this way any data associated with a world gives
rise to a question. For example, if 𝑓 (𝑊 ) = {𝑖 ∈ 𝑊 ⊑ 𝑊 ′ ⇐⇒ ∀𝑖, 𝑐, 𝜙 : 𝑊, 𝑐 |= S 𝜙 =⇒ 𝑊 ′ , 𝑐 |= S 𝜙.
𝑖 𝑖
𝒮 | Π𝑊 𝑖 [𝑝] = ‖𝑝‖} we ask for the set of sources
with expertise on 𝑝; if 𝑓 (𝑊 ) = |{𝑐 ∈ 𝒞 | 𝑊, 𝑐 |= Thus, 𝑊 ⊑ 𝑊 ′ iff any report sound for 𝑊 is also sound
𝑝}| we ask for the number of cases where 𝑝 holds, for 𝑊 ′ . We denote by ⊏ and ≈ the strict and symmetric
etc. parts of ⊑, respectively.4
In fact, all questions are of this form: given 𝑄 we
Lemma 1. 𝑊 ⊑ 𝑊 ′ if and only if for all 𝑖 ∈ 𝒮 and
may define 𝑓 : 𝒲 → 𝑄 by 𝑓 (𝑊 ) = 𝑄[𝑊 ]; then 𝑊′ 𝑊′
𝑄𝑓 = 𝑄. 𝑐 ∈ 𝒞, Π𝑊 𝑊
𝑖 [𝑣𝑐 ] ⊆ Π𝑖 [𝑣𝑐 ].
A method solves 𝑄 if it eventually implies the correct Proof. “if”: Suppose 𝑊, 𝑐 |= S𝑖 𝜙. Then 𝑣𝑐𝑊 ∈ Π𝑊 𝑖 [𝜙],
answer when given any stream. so there is 𝑢 ∈ ‖𝜙‖ such that 𝑣𝑐𝑊 ∈ Π𝑊 𝑖 [𝑢]. Con-
𝑊′ 𝑊′
sequently 𝑢 ∈ Π𝑊 𝑖 [𝑣𝑐 ] ⊆ Π𝑖 [𝑣𝑐 ], which means
𝑊
Definition 2. A method 𝐿 solves a question 𝑄 if for all ′ ′ ′
𝑖 [𝑢] ⊆ Π𝑖 [𝜙]. Hence 𝑊 , 𝑐 |= S𝑖 𝜙. This
′
𝑣𝑐𝑊 ∈ Π𝑊 𝑊
worlds 𝑊 and all streams 𝜌 for 𝑊 , there is 𝑛 ∈ N such
shows 𝑊 ⊑ 𝑊 . ′
that 𝐿(𝜌[𝑚]) ⊆ 𝑄[𝑊 ] for all 𝑚 ≥ 𝑛. A question 𝑄 is
“only if”: Let 𝑢 ∈ Π𝑊 𝑖 [𝑣𝑐 ]. Let 𝜙 be any formula
𝑊
solvable if there is some consistent method 𝐿 which solves
with ‖𝜙‖ = {𝑢}. Then 𝑊, 𝑐 |= S𝑖 𝜙, so 𝑊 ⊑ 𝑊 ′ gives
𝑄. ′ ′
𝑊′ 𝑊′
𝑊 ′ , 𝑐 |= S𝑖 𝜙, i.e. 𝑣𝑐𝑊 ∈ Π𝑊 𝑖 [𝑢], so 𝑢 ∈ Π𝑖 [𝑣𝑐 ].
Note that we do not require 𝑊 ∈ 𝐿(𝜌[𝑚]). Since 𝑊′ 𝑊′
Hence Π𝑖 [𝑣𝑐 ] ⊆ Π𝑖 [𝑣𝑐 ].
𝑊 𝑊
we work in a finite framework, solvability can be also
expressed in terms of eliminating incorrect worlds. Note that Π𝑖 [𝑣𝑐 ] is the set of valuations indistinguish-
able from the “actual” valuation in case 𝑐, for source 𝑖. In
Proposition 1. A method 𝐿 solves 𝑄 if and only if for light of Lemma 1, we can interpret 𝑊 ⊑ 𝑊 ′ as saying
all 𝑊 , all streams 𝜌 for 𝑊 , and all 𝑊 ′ ∈
/ 𝑄[𝑊 ], there is that all sources are more knowledgeable in each case 𝑐 in
𝑛𝑊 ′ ∈ N such that 𝑊 ′ ∈ / 𝐿(𝜌[𝑚]) for all 𝑚 ≥ 𝑛𝑊 ′ . world 𝑊 than in 𝑊 ′ . However, 𝑊 ⊑ 𝑊 ′ does not say
anything about the partition cells not containing some
Proof. “if”: Taking 𝑛 = max{𝑛𝑊 ′ | 𝑊 ′ ∈ / 𝑄[𝑊 ]},
𝑣𝑐 .
which exists since 𝒲 is finite, 𝐿(𝜌[𝑚]) ⊆ 𝑄[𝑊 ] for
𝑚 ≥ 𝑛. Proposition 3. The following are equivalent.
“only if”: Taking 𝑛 from the definition of 𝐿 solving 𝑄,
we may simply take 𝑛𝑊 ′ = 𝑛 for all 𝑊 ∈ ′
/ 𝑄[𝑊 ]. 1. 𝑊 and 𝑊 ′ have exactly the same streams.
2. 𝑊 ≈ 𝑊 ′ .
4. Characterising Solvable 3. For all 𝑖 ∈ 𝒮 and 𝑐 ∈ 𝒞, Π𝑊 𝑊 𝑊 𝑊 ′ ′
𝑖 [𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ].
Questions
Proof. (2) and (3) are easily seen to be equivalent in light
In this section we explore solvability of questions, finding of Lemma 1. To show (1) is equivalent to (2), first suppose
that there is a unique “hardest” question which subsumes 𝑊 and 𝑊 ′ have the same streams, and suppose 𝑊, 𝑐 |=
all solvable questions. We show this is itself solvable, and S𝑖 𝜙. Taking an arbitrary stream 𝜌 for 𝑊 , completeness
thus obtain a precise characterisation of solvability. gives ⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝜌. But 𝜌 is a stream for 𝑊 ′ too, and
Questions are partially ordered by partition refinement: 4
𝑄 ⪯ 𝑄′ iff each 𝐴′ ∈ 𝑄′ can be written as a union of Baltag et al. [21] explore topological interpretations of solvability
by considering the topology on the set of worlds generated by ob-
answers from 𝑄. Equivalently, 𝑄[𝑊 ] ⊆ 𝑄′ [𝑊 ] for all servable propositions. In our setting, this is the topology generated
𝑊 . This can be interpreted as a difficulty ordering: if by sets of the form {𝑊 | 𝑊, 𝑐 |= S𝑖 𝜙}. In this topology, ⊑ is
𝑄 ⪯ 𝑄′ then each answer of 𝑄′ is just a disjunction of the specialisation preorder.
83
�soundness gives 𝑊 ′ , 𝑐 |= S𝑖 𝜙. Hence 𝑊 ⊑ 𝑊 ′ . A Note that these cases are exhaustive since 𝑊 ̸≈ 𝑊 ′ .
symmetrical argument shows 𝑊 ′ ⊑ 𝑊 . This completes the proof.
On the other hand, if 𝑊 ≈ 𝑊 ′ then 𝑊 and 𝑊 ′ satisfy
exactly the same soundness statements, so it is clear that Putting Propositions 2 and 4 and Lemma 2 together
any sequence 𝜌 is a stream for 𝑊 iff it is a stream for we obtain a characterisation of solvable questions.
𝑊 ′.
Theorem 1. 𝑄 is solvable if and only if 𝑄* ⪯ 𝑄.
Since it will play a special role throughout, we denote Given this result, 𝑄* is the only question that re-
by 𝑄* the question formed by the equivalence relation ≈. ally matters: any other question is either unsolvable or
Then 𝑄* [𝑊 ] is the set of 𝑊 ′ with 𝑊 ≈ 𝑊 ′ . Since no formed by coarsening 𝑄* . With this in mind, we make
solvable question can distinguish ≈-equivalent worlds, the following definition.
we have the following.
Definition 3. A method is truth-tracking if it solves 𝑄* .
Lemma 2. If 𝑄 is solvable then 𝑄* ⪯ 𝑄.
Example 5. We refer back to the questions of Example 4.
Proof. Suppose 𝐿 is a consistent method solving 𝑄. We
show 𝑄* [𝑊 ] ⊆ 𝑄[𝑊 ] for all 𝑊 . Indeed, let 𝑊 ′ ∈ 1. The question 𝑄𝜙,𝑐 , for any propositional formula
𝑄* [𝑊 ]. Then 𝑊 ′ ≈ 𝑊 . Taking any stream 𝜌 for 𝑊 , 𝜙 ∈ ℒ0 , is solvable if and only if either 𝜙 is a
there is 𝑛 such that 𝐿(𝜌[𝑚]) ⊆ 𝑄[𝑊 ] for 𝑚 ≥ 𝑛. On tautology or a contradiction. To see the “only if”
the other hand 𝜌 is also a stream for 𝑊 ′ by Proposition 3, part, consider the contrapositive. For any contin-
so there is 𝑛′ such that 𝐿(𝜌[𝑚]) ⊆ 𝑄[𝑊 ′ ] for 𝑚 ≥ 𝑛′ . gent formula 𝜙, take worlds 𝑊1 , 𝑊2 where no
𝑊
Setting 𝑚 = max{𝑛, 𝑛′ } and using the fact that 𝐿 is source has any expertise (i.e. Π𝑖 𝑘 = {𝒱}) but
𝑊1 𝑊2
consistent, we find ∅ ⊂ 𝐿(𝜌[𝑚]) ⊆ 𝑄[𝑊 ] ∩ 𝑄[𝑊 ]. ′ where 𝑣𝑐 ⊩ 𝜙, 𝑣𝑐 ⊩ ¬𝜙. Then 𝑊1 ≈ 𝑊2
Since 𝑄 is a partition, this means 𝑄[𝑊 ] = 𝑄[𝑊 ′ ], i.e. (e.g. by Proposition 3) but 𝑊1 ∈ / 𝑄𝜙,𝑐 [𝑊2 ].
𝑊 ′ ∈ 𝑄[𝑊 ]. Similarly, 𝑄E𝑖 𝜙,𝑐 is solvable iff either 𝜙 is a tau-
tology or contradiction, when |Prop| ≥ 2.
So, any solvable question is coarser than 𝑄* . Fortu-
nately, 𝑄 itself is solvable since we work in a finite
*
2. The finest question 𝑄⊥ is not solvable, since there
framework. For a sequence 𝜎, write 𝒳𝜎snd for the set of are always distinct 𝑊, 𝑊 ′ with 𝑊 ≈ 𝑊 ′ .
worlds 𝑊 such that 𝑊, 𝑐 |= S𝑖 𝜙 for all ⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝜎. To
solve 𝑄* it suffices to conjecture the ⊑-minimal worlds 3. In general, 𝑄𝑓 is solvable iff 𝑊 ≈ 𝑊 ′ implies
in 𝒳𝜎 .
snd 𝑓 (𝑊 ) = 𝑓 (𝑊 ′ ), i.e. iff 𝑓 takes a unique value on
each equivalence class of ≈.
Proposition 4. 𝑄* is solvable.
Proof. Set 𝐿(𝜎) = min⊑ 𝒳𝜎snd if 𝒳𝜎snd ̸= ∅, and 𝐿(𝜎) = 5. What Information can be
𝒲 otherwise (where 𝑊 ∈ min⊑ 𝒳𝜎snd iff 𝑊 ∈ 𝒳𝜎snd
and there is no 𝑊 ′ ∈ 𝒳𝜎snd with 𝑊 ′ ⊏ 𝑊 ). Note that
Learned?
𝐿 is consistent since 𝒲 is finite and non-empty. We Solving a question 𝑄 has a global character: we must
show that 𝐿 solves 𝑄* by Proposition 1. Take any world find the correct answer 𝑄[𝑊 ] starting from any world
𝑊 and a stream 𝜌. First note that, by soundness of 𝜌, 𝑊 . As we saw in Example 5, this rules out the possi-
𝑊 ∈ 𝒳𝜌[𝑛]snd
for all 𝑛 ∈ N, so we are always in the first bility of solving many interesting questions due to the
case in the definition of 𝐿. presence of “abnormal” worlds (e.g. those in which no
Take 𝑊 ′ ∈ / 𝑄* [𝑊 ]. Then 𝑊 ̸≈ 𝑊 ′ . Consider two sources have any expertise). In this section we take a
cases: more fine-grained approach by looking locally: given
• Case 1: 𝑊 ̸⊑ 𝑊 . By definition, there are 𝑖, 𝑐, 𝜙 some particular world 𝑊 , what can we learn about 𝑊
′
such that 𝑊, 𝑐 |= S𝑖 𝜙 but 𝑊 ′ , 𝑐 ̸|= S𝑖 𝜙. By via truth-tracking methods? Concretely, what properties
completeness of 𝜌 for 𝑊 , there is 𝑛 such that of 𝑊 are uniquely defined across 𝑄 [𝑊 ]?
*
𝜌𝑛 = ⟨𝑖, 𝑐, 𝜙⟩. Consequently 𝑊 ′ ∈ snd
/ 𝒳𝜌[𝑚] for Clearly this depends on 𝑊 . If no sources have exper-
tise then source partitions are uniquely defined (since
all 𝑚 ≥ 𝑛. Since 𝐿(𝜌[𝑚]) ⊆ 𝒳𝜌[𝑚] , we have
snd
all consistent formulas are sound, and only the trivial
𝑊′ ∈ / 𝐿(𝜌[𝑚]) as required. partitions have this property), but any combination of
• Case 2: 𝑊 ⊏ 𝑊 ′ . Since 𝑊 ∈ 𝒳𝜌[𝑛] snd
for all 𝑛, valuations is possible. On the other hand if all sources
𝑊 ′ can never be ⊑-minimal. Thus 𝑊 ′ ∈ / 𝐿(𝜌[𝑛]) have total expertise then valuations are uniquely defined,
for all 𝑛. but there may not be enough cases to uniquely identify
the source partitions. Of particular interest is the case
84
�where 𝑄* [𝑊 ] contains only 𝑊 ; starting in such a world, maximally consistent. This example shows how the exper-
truth-tracking methods are able to find the true world tise of multiple sources can be combined to find valuations
exactly. uniquely, but that this is not necessarily possible in all
In what follows, say 𝑆 decides Φ in case 𝑐 iff either cases.
𝑆, 𝑐 |= Φ or 𝑆, 𝑐 |= ¬Φ. That is, the truth value of Φ in
The remainder of this section proves Theorems 2 and 3.
case 𝑐 is unambiguously defined across 𝑆. If Φ does not
depend on the case (e.g. if Φ = E𝑖 𝜙) we simply say 𝑆 Lemma 3. For 𝑊 ≈ 𝑊 ′ , 𝑖 ∈ 𝒮 and 𝜙 ∈ ℒ0 ,
decides Φ.
𝑊, 𝑐 |= 𝜙 ∧ E𝑖 𝜙 =⇒ 𝑊 ′ , 𝑐 |= 𝜙.
5.1. Valuations Proof. From 𝑊, 𝑐 |= 𝜙 we have 𝑣𝑐𝑊 ∈ ‖𝜙‖, so
𝑊 𝑊
We start by considering when 𝑄* [𝑊 ] decides a proposi- Π𝑖 [𝑣𝑐 ] ⊆ Π𝑖 [𝜙].
𝑊
But 𝑊, 𝑐 |= E𝑖 𝜙 means Π𝑊 𝑖 [𝜙] =
tional formula 𝜙 in case 𝑐, i.e. when truth-tracking meth- ‖𝜙‖, so in fact Π 𝑊 𝑊
𝑖 [𝑣 𝑐 ] ⊆ ‖𝜙‖. Now using 𝑊 ≈ 𝑊 ,
′
𝑊′ 𝑊′ 𝑊′
ods are guaranteed to successfully determine whether we find 𝑣𝑐 ∈ Π𝑖 [𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ] ⊆ ‖𝜙‖. Hence
𝑊 𝑊
′
or not 𝜙 holds in the “actual” world. This leads to a pre- 𝑊 , 𝑐 |= 𝜙.
cise characterisation of when 𝑄 [𝑊 ] contains a unique
*
𝑄* [𝑊 ]
= 𝑖∈𝒮 Π𝑊 𝑊
⋂︀
valuation in case 𝑐, so that 𝑣𝑐𝑊 can be found exactly. Lemma 4. 𝒱𝑐 𝑖 [𝑣𝑐 ].
We need a notion of group expertise. For 𝒮 ′ ⊆ 𝒮 and 𝑄* [𝑊 ]
Γ ⊆ ℒ0 , write 𝑊 |= E𝒮 ′ Γ if for each 𝜓 ∈ Γ there is Proof. “⊆”: Suppose 𝑢 ∈ 𝒱𝑐 ′ . Then there is
𝑖 ∈ 𝒮 ′ such that 𝑊 |= E𝑖 𝜓. Then the group 𝒮 ′ have 𝑊 ≈ 𝑊′ such that . Let 𝑖 ∈ 𝒮. Then
′ 𝑊
𝑢 = 𝑣𝑐
𝑊′
expertise on Γ in a collective sense, even if no single 𝑢 ∈ Π𝑖 [𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ] by Proposition 3, as re-
𝑊 𝑊 𝑊
source has expertise on all formulas in Γ. We have that quired.
“⊇”: Suppose 𝑢 ∈ 𝑖∈𝒮 Π𝑊 𝑖 [𝑣𝑐 ]. Let 𝑊 be the
𝑊 ′
⋂︀
𝜙 is decided if 𝒮 have group expertise on a set of true
formulas Γ ⊆ ℒ0 such that either Γ ⊩ 𝜙 or Γ ⊩ ¬𝜙. world obtained from 𝑊 by setting the 𝑐-valuation to 𝑢,
keeping partitions and other valuations the same. We
Theorem 2. 𝑄* [𝑊 ] decides 𝜙 ∈ ℒ0 in case 𝑐 if and only need to show 𝑊 ′ ≈ 𝑊 . We do so via Proposition 3, by
if there is Γ ⊆ ℒ0 such that (i) 𝑊, 𝑐 |= Γ; (ii) 𝑊 |= E𝒮 Γ; showing condition (3). Take any 𝑖 ∈ 𝒮 and 𝑑 ∈ 𝒞. If 𝑑 ̸=
and (iii) either Γ ⊩ 𝜙 or Γ ⊩ ¬𝜙. ′
𝑐 then 𝑣𝑑𝑊 = 𝑣𝑑𝑊 ; since partitions are the same in 𝑊 ′
𝑊′ 𝑊′
𝑄* [𝑊 ] decides all propositional formulas – and thus as in 𝑊 we get Π𝑖 [𝑣𝑑 ] = Π𝑖 [𝑣𝑑 ]. For 𝑐 = 𝑑, note
𝑊 𝑊
′ ′
determines the 𝑐-valuation 𝑣𝑐𝑊 exactly – iff 𝒮 have group Π𝑊 𝑖 [𝑣𝑐 ] = Π𝑖 [𝑢]. By assumption 𝑢 ∈ Π𝑖 [𝑣𝑐 ], so
𝑊 𝑊 𝑊 𝑊
expertise on a maximally consistent set of true formulas. Π𝑊 𝑊′ 𝑊′
𝑖 [𝑢] = Π𝑖 [𝑣𝑐 ]. Hence Π𝑖 [𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ] as
𝑊 𝑊 𝑊 𝑊
For 𝑆 ⊆ 𝒲 and 𝑐 ∈ 𝒞, write 𝒱𝑐𝑆 = {𝑣𝑐𝑊 | 𝑊 ∈ 𝑆} for required.
the 𝑐-valuations appearing in 𝑆.
Proof of Theorem 2. “if”: Take 𝑊 ′ ∈ 𝑄* [𝑊 ]. Note that
Theorem 3. The following are equivalent. since 𝑊, 𝑐 |= Γ and 𝑊, 𝑐 |= E𝒮 Γ, we may apply
𝑄* [𝑊 ] 𝑊 Lemma 3 to each formula in Γ in turn to find 𝑊 ′ , 𝑐 |= Γ.
1. 𝒱𝑐 = {𝑣𝑐 }.
Now, if 𝑊, 𝑐 |= 𝜙 then we must have Γ ⊩ 𝜙, so
2. 𝑄* [𝑊 ] decides 𝜙 in case 𝑐, for all 𝜙 ∈ ℒ0 . 𝑊 ′ , 𝑐 |= 𝜙 too. Otherwise 𝑊, 𝑐 ̸|= 𝜙, so we must have
Γ ⊩ ¬𝜙 and 𝑊 ′ , 𝑐 ̸|= 𝜙. This shows 𝑊 ′ , 𝑐 |= 𝜙 if and
3. There is Γ ⊆ ℒ0 such that (i) 𝑊, 𝑐 |= Γ; only if 𝑊, 𝑐 |= 𝜙. Since 𝑊 ′ ∈ 𝑄* [𝑊 ] was arbitrary,
(ii) 𝑊 |= E𝒮 Γ; and (iii) Cn0 (Γ) is a maximally 𝑄* [𝑊 ] decides 𝜙 in case 𝑐.
consistent set. “only if”: Suppose 𝑄* [𝑊 ] decides 𝜙 in case 𝑐. For each
We illustrate Theorem 3 with an example. 𝑖 ∈ 𝒮, take some 𝜓𝑖 ∈ ℒ0 such that ‖𝜓𝑖 ‖ = Π𝑊 𝑊
𝑖 [𝑣𝑐 ].
Then 𝑊 |= E𝑖 𝜓𝑖 . Set Γ = {𝜓𝑖 }𝑖∈𝒮 . Clearly 𝑊, 𝑐 |= Γ
Example 6. Consider 𝑊 from Fig. 1. Then one can show and 𝑊 |= E𝒮 Γ. Now, take any 𝑢 ∈ ‖Γ‖. By Lemma 4,
𝑄* [𝑊 ] 𝑄* [𝑊 ] 𝑄* [𝑊 ]
𝑊
‖Γ‖ = 𝑖∈𝒮 Π𝑊 𝑊
. Hence there is some
⋂︀
𝒱𝐴 = {𝑝 ¯𝑞} = {𝑣𝐴 }, and 𝒱𝐵 = {𝑝𝑞, 𝑝𝑞¯} =
̸ 𝑖 [𝑣𝑐 ] = 𝒱𝑐
𝑊
{𝑣𝐵 }. That is, 𝑊 ’s 𝐴 valuation is uniquely determined 𝑊 ′ ∈ 𝑄* [𝑊 ] such that 𝑢 = 𝑣 𝑊 ′ . But 𝑄* [𝑊 ] decides
𝑐
by truth-tracking methods, but its 𝐵 valuation is not: there 𝜙 in case 𝑐, so 𝑊 ′ , 𝑐 |= 𝜙 iff 𝑊, 𝑐 |= 𝜙. Thus 𝑢 ⊩ 𝜙 iff
′
is some world 𝑊 ≈ 𝑊 whose 𝐵-valuation differs from 𝑊, 𝑐 |= 𝜙. Since 𝑢 ∈ ‖Γ‖ was arbitrary, we have Γ ⊩ 𝜙
𝑊 ’s. This matches the informal reasoning in Example 1, if 𝑊, 𝑐 |= 𝜙, and Γ ⊩ ¬𝜙 otherwise.
in which patient 𝐴 could be successfully diagnosed on both
𝑝 and 𝑞 but 𝐵 could not. Proof of Theorem 3. (1) implies (2): If 𝑊 ′ ∈ 𝑄* [𝑊 ] then
Formally, take Γ = {𝑝 ∨ 𝑞, ¬𝑝}. Then 𝑊, 𝐴 |= Γ, 𝑊 and 𝑊 ′ share the same 𝑐-valuation by (1), so clearly
𝑊 |= E𝒮 Γ (since D has expertise on 𝑝 ∨ 𝑞 and T has 𝑊, 𝑐 |= 𝜙 iff 𝑊 ′ , 𝑐 |= 𝜙, for any 𝜙. Hene 𝑄* [𝑊 ] decides
expertise on ¬𝑝), and Cn0 (Γ) = Cn0 (¬𝑝 ∧ 𝑞), which is 𝜙 in case 𝑐.
85
� vc1 Example 7. Suppose |Prop| = 3, 𝒞 = {𝑐1 , 𝑐2 } and
𝑖 ∈ 𝒮. Consider a world 𝑊 whose 𝑖-partition is shown
′
in Fig. 2. By Lemma 5, a partition Π appears as Π𝑊 𝑖
for some 𝑊 ′ ≈ 𝑊 if and only if it contains the leftmost
vc 2 and bottommost sets. Any such Π consists of these cells
together with a partition of the shaded area. Since there
Figure 2: World 𝑊 from Example 7. Note that for brevity are 5 possible partitions of a 3-element set, it follows that
we do not label the valuations. 𝑄* [𝑊 ]
|𝒫𝑖 | = 5.
Example 7 hints that if the cells containing the val-
𝑄* [𝑊 ]
(2) implies (1): Clearly 𝑣𝑐𝑊 ∈ 𝒱𝑐 . Suppose 𝑢 ∈ uations 𝑣𝑐𝑊 cover the whole space of valuations 𝒱, or
*
𝑄 [𝑊 ] just omit a single valuation, then 𝑖’s partition is uniquely
𝒱𝑐 . Then there is 𝑊 ′ ∈ 𝑄* [𝑊 ] such that 𝑢 =
′ defined in 𝑄* [𝑊 ]. That is, truth-tracking methods can
𝑣𝑐𝑊 . Let 𝑝 ∈ Prop. Since 𝑊, 𝑊 ′ ∈ 𝑄* [𝑊 ] and 𝑄* [𝑊 ] determine the full extent of 𝑖’s expertise if the “actual”
decides 𝑝 in case 𝑐, we have 𝑢 ⊩ 𝑝 iff 𝑣𝑐𝑊 ⊩ 𝑝. Since 𝑝 world is 𝑊 . Indeed, we have the following analogue of
was arbitrary, 𝑢 = 𝑣𝑐𝑊 . Theorem 3 for partitions.
(2) implies (3): Applying Theorem 2 to each 𝜙 ∈
ℒ0 , there is a set Γ𝜙 ⊆ ℒ0 such that 𝑊, 𝑐 |= Γ𝜙 , Theorem 4. The following are equivalent.
𝑊 |= ⋃︀E𝒮 Γ𝜙 , and either Γ𝜙 ⊩ 𝜙 or Γ𝜙 ⊩ ¬𝜙. Set
𝑄* [𝑊 ]
Γ = 𝜙∈ℒ0 Γ𝜙 . Clearly 𝑊, 𝑐 |= Γ – so Γ is con- 1. 𝒫𝑖 = {Π𝑊
𝑖 }.
sistent – and 𝑊 |= E𝒮 Γ. To show Cn0 (Γ) is maxi-
mally consistent, suppose 𝜙 ∈ / Cn0 (Γ). From mono- 2. 𝑄* [𝑊 ] decides E𝑖 𝜙 for all 𝜙 ∈ ℒ0 .
tonicity of classical consequence and Γ𝜙 ⊆ Γ, we get 3. |𝒱 ∖ 𝑅| ≤ 1, where 𝑅 = 𝑐∈𝒞 Π𝑊
⋃︀ 𝑊
𝑖 [𝑣𝑐 ].
𝜙∈ / Cn0 (Γ𝜙 ). Hence Γ𝜙 ⊩ ¬𝜙, and Γ ⊩ ¬𝜙 too. This
means Cn0 (Γ) ∪ {𝜙} is inconsistent, and we are done. Note that 𝑅 = 𝑐∈𝒞 Π𝑊 𝑖 [𝑣𝑐 ] is the set of valuations
⋃︀ 𝑊
(3) implies (2): Take 𝜙 ∈ ℒ0 . Then we may apply indistinguishable from the actual state at some case 𝑐.
Theorem 2 with Γ from (3) – noting that the maximal Theorem 4 (3) says this set needs to essentially cover
consistency property ensure either Γ ⊩ 𝜙 or Γ |= ¬𝜙 – the whole space 𝒱, omitting at most a single point. In
to see that 𝑄* [𝑊 ] decides 𝜙 in case 𝑐. this sense, it is easier to find Π𝑊𝑖 uniquely when 𝑖 has
less expertise, since the cells Π𝑊𝑖 [𝑣𝑐 ] will be larger. In
𝑊
5.2. Source Partitions the extreme case where 𝑖 has total expertise, i.e. Π𝑊 𝑖 =
{{𝑣} | 𝑣 ∈ 𝒱}, we need at least 2|Prop| − 1 cases with
We now apply the analysis of the previous section to
distinct valuations in order to find Π𝑊 𝑖 exactly.
the set of source partitions {Π𝑊
𝑖 }𝑖∈𝒮 . For 𝑆 ⊆ 𝒲 and
𝑖 ∈ 𝒮, write 𝒫𝑖𝑆 = {Π𝑊 𝑖 | 𝑆 ∈ 𝑊 } for the 𝑖-partitions Example 8. In Example 7 we have already seen an ex-
appearing in 𝑆. When 𝑆 = 𝑄* [𝑊 ], these are exactly ample of a world 𝑊 for which 𝒫𝑖
𝑄* [𝑊 ]
does not contain a
those partitions which agree with Π𝑊
𝑖 at each valuation unique partition. For a positive example, consider the world
𝑣𝑐𝑊 . 𝑊 from Fig. 1. Then 𝒱 ∖ 𝑅D = {𝑝 𝑞 } and 𝒱 ∖ 𝑅T = ∅, so
¯¯
𝑄* [𝑊 ] both the partitions of D and T can be found uniquely by
Lemma 5. Π ∈ 𝒫𝑖 if and only if {Π𝑊 𝑊
𝑖 [𝑣𝑐 ]}𝑐∈𝒞 ⊆
truth-tracking methods.
Π.
The remainder of this section proves Theorem 4.
Proof. “if”: Suppose {Π𝑊 𝑖 [𝑣𝑐 ]}𝑐∈𝒞 ⊆ Π. Let 𝑊 be
𝑊 ′
obtained from 𝑊 by setting 𝑖’s partition to Π, keeping Lemma 6. Let 𝑖 ∈ 𝒮 and 𝑈 ⊆ 𝒱. Then 𝑈 ⊆
valuations and other source partitions the same. We 𝑊 𝑊
≈ 𝑊 ′ implies Π𝑊
⋃︀
𝑐∈𝒞 Π𝑖 [𝑣𝑐 ] and 𝑊 𝑖 [𝑈 ] =
claim 𝑊 ′ ≈ 𝑊 . Indeed, take any 𝑗 ∈ 𝒮 and 𝑐 ∈ 𝒞. 𝑊 ′
Π𝑖 [𝑈 ].
′
If 𝑗 ̸= 𝑖 then Π𝑊 𝑗 = Π𝑊 𝑖 ; since valuations are the
same we get Π𝑗 [𝑣𝑐 ] = Π𝑊
𝑊 𝑊 ′
𝑊′
𝑗 [𝑣𝑐 ]. For 𝑗 = 𝑖, note
Proof. It suffices to show that for all 𝑢 ∈ 𝑈 we
𝑊′
that since Π𝑊 𝑖 [𝑣𝑐 ] ∈ Π by assumption, and 𝑣𝑐
𝑊 𝑊
∈ have Π𝑊 𝑖 [𝑢] = Π𝑖 [𝑢], since by definition Π[𝑈 ] =
Π𝑊 we have By construction 𝑢∈𝑈 Π[𝑢]. Let 𝑢 ∈ 𝑈 . Then there is 𝑐 ∈ 𝒞 such that
𝑊 𝑊 𝑊 𝑊
⋃︀
𝑖 [𝑣𝑐 ], Π[𝑣 𝑐 ] = Π 𝑖 [𝑣𝑐 ].
𝑊′ 𝑊′ 𝑊′ 𝑢 ∈ Π𝑊 𝑖 [𝑣𝑐 ]. Hence Π𝑖 [𝑢] = Π𝑖 [𝑣𝑐 ]. But since
𝑊 𝑊 𝑊 𝑊
of 𝑊 ′ , this means Π𝑊 𝑊
𝑖 [𝑣𝑐 ] = Π[𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ].
* 𝑊′ 𝑊′
By Proposition 3, 𝑊 ′ ≈ 𝑊 . Hence Π ∈ 𝒫𝑖
𝑄 [𝑊 ]
. 𝑊 ≈ 𝑊 , Π𝑖 [𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ]. This means 𝑢 ∈
′ 𝑊 𝑊
′
𝑊′ 𝑊′ 𝑊′ 𝑊′
“only if”: This is clear from Proposition 3. Π𝑊𝑖 [𝑣𝑐 ], so Π𝑖 [𝑢] = Π𝑖 [𝑣𝑐 ] = Π𝑖 [𝑣𝑐 ] =
𝑊 𝑊
Π𝑖 [𝑢], as required,
𝑊
86
�Lemma 7. 𝑄* [𝑊 ] decides E𝑖 𝜙 if and only if, writing 𝑅 = Finally, for (3) implies (1) we also show the contra-
𝑊 𝑊 𝑄* [𝑊 ]
⋃︀
𝑐∈𝒞 Π𝑖 [𝑣𝑐 ], either (i) ‖𝜙‖ ⊆ 𝑅; (ii) ‖¬𝜙‖ ⊆ 𝑅; or positive. Suppose there is Π ∈ 𝒫𝑖 ∖ {Π𝑊𝑖 }. Write
(iii) there is some 𝑐 ∈ 𝒞 such that Π𝑊 𝑊
𝑖 [𝑣𝑐 ] intersects with ℛ = {Π𝑖 [𝑣𝑐 ]}𝑐∈𝒞 , so that ℛ is a partition of 𝑅. By
𝑊 𝑊
both ‖𝜙‖ and ‖¬𝜙‖. Lemma 5, ℛ ⊆ Π. Note that ℛ ⊆ Π𝑊 𝑖 too. Since
Π ̸= Π𝑊𝑖 , we in fact have ℛ ⊂ Π and ℛ ⊂ Π𝑖 . Hence
𝑊
Proof. “if”: First suppose (i) holds. Take 𝑊 ∈ 𝑄 [𝑊 ]. Π ∖ ℛ and Π𝑊 ∖ ℛ are distinct partitions of 𝒱 ∖ 𝑅. Since
′ *
𝑖
From ‖𝜙‖ ⊆ 𝑅, 𝑊 ≈ 𝑊 ′ and Lemma 6 we get a one-element set has a unique partition, 𝒱 ∖ 𝑅 must
𝑊′
Π𝑖 [𝜙] = Π𝑖 [𝜙]. Consequently, 𝑊 |= E𝑖 𝜙 iff contain at least two elements.
𝑊 ′
𝑊 |= E𝑖 𝜙. Since 𝑊 ′ was arbitrary, either all worlds
in 𝑄* [𝑊 ] satisfy E𝑖 𝜙, or all do not. Hence 𝑄* [𝑊 ] de-
5.3. Learning the Actual World Exactly
cides E𝑖 𝜙.
If (ii) holds, a similar argument shows that 𝑄 [𝑊 ] Putting Theorems 3 and 4, we obtain a precise characteri-
*
decides E𝑖 ¬𝜙. But it is easily checked that E𝑖 𝜙 ≡ E𝑖 ¬𝜙, sation of when 𝑊 can be found exactly by truth-tracking
so 𝑄* [𝑊 ] also decides E𝑖 𝜙. methods, i.e when 𝑄* [𝑊 ] = {𝑊 }.
Finally, suppose (iii) holds. Then there is 𝑐 ∈ 𝒞 and
𝑢 ∈ ‖𝜙‖, 𝑣 ∈ ‖¬𝜙‖ such that 𝑢, 𝑣 ∈ Π𝑊 Corollary 1. 𝑄* [𝑊 ] = {𝑊 } if and only if
𝑖 [𝑣𝑐 ]. We
𝑊
claim 𝑄 [𝑊 ] |= ¬E𝑖 𝜙. Indeed, take 𝑊 ∈ 𝑄 [𝑊 ].
* ′ *
1. There is a collection {Γ𝑐 }𝑐∈𝒞 ⊆ ℒ𝒞0 such that
𝑊′ 𝑊′ 𝑊′ 𝑊′
Then Π𝑊 𝑖 [𝑣 𝑊
𝑐 ] = Π 𝑖 [𝑣𝑐 ], so 𝑢, 𝑣 ∈ Π 𝑖 [𝑣𝑐 ]. In for each 𝑐, (i) 𝑊, 𝑐 |= Γ𝑐 ; (ii) 𝑊 |= E𝒮 Γ𝑐 ;
particular, 𝑢 and 𝑣 differ on 𝜙 but are contained in the (iii) Cn0 (Γ𝑐 ) is maximally consistent; and
′
same cell in Π𝑊 𝑖 . Hence 𝑊 |= ¬E𝑖 𝜙.
′
2. For each each 𝑖 ∈ 𝒮, |𝒱 ∖ 𝑐∈𝒞 Π𝑊 𝑊
⋃︀
“only if”: We show the contrapositive. Suppose none 𝑖 [𝑣𝑐 ]| ≤ 1.
of (i), (ii), (iii) hold. Then there is 𝑢 ∈ ‖𝜙‖ ∖ 𝑅 and
𝑣 ∈ ‖¬𝜙‖ ∖ 𝑅. Let us define two worlds 𝑊1 , 𝑊2 from
𝑊 by modifying 𝑖’s partition:
6. Truth-Tracking Methods
So far we have focussed on solvable questions, and the
Π𝑊 1
= {Π𝑊 𝑊
𝑖 [𝑣𝑐 ]}𝑐∈𝒞 ∪ {𝒱 ∖ 𝑅},
𝑖 extent to which they reveal information about the actual
Π𝑊
𝑖
2
= {Π𝑊 𝑊
𝑖 [𝑣𝑐 ]}𝑐∈𝒞 ∪ {{𝑤} | 𝑤 ∈ 𝒱 ∖ 𝑅}. world. We now turn to the methods which solve them.
We give a general characterisation of truth-tracking meth-
Then 𝑊1 , 𝑊2 ∈ 𝑄* [𝑊 ] by Lemma 5. We claim that ods under mild assumptions, before discussing the family
𝑊1 |= ¬E𝑖 𝜙 but 𝑊2 |= E𝑖 𝜙, which will show 𝑄* [𝑊 ] of conditioning methods from Singleton and Booth [1].
does not decide E𝑖 𝜙.
First, note that since 𝑢, 𝑣 ∈ / 𝑅, we have Π𝑊 1
𝑖 [𝑢] =
Π𝑖 [𝑣] = 𝒱 ∖ 𝑅. Since 𝑢 and 𝑣 differ on 𝜙 but share the
𝑊1 6.1. A General Characterisation
same partition cell, 𝑊1 |= ¬E𝑖 𝜙. For sequences 𝜎, 𝛿, write 𝜎 ≡ 𝛿 iff 𝛿 is obtained from 𝜎
To show 𝑊2 |= E𝑖 𝜙, take 𝑤 ∈ ‖𝜙‖. If 𝑤 ∈ / 𝑅 then by replacing each report ⟨𝑖, 𝑐, 𝜙⟩ with ⟨𝑖, 𝑐, 𝜓⟩, for some
Π𝑊𝑖 [𝑤] = {𝑤} ⊆ ‖𝜙‖. Otherwise there is 𝑐 ∈ 𝒞 such 𝜓 ≡ 𝜙. For 𝑘 ∈ N, let 𝜎 𝑘 denote the 𝑘-fold repetition of
2
that 𝑤 ∈ Π𝑊 𝑖 [𝑣𝑐 ]. Thus Π𝑖 [𝑣𝑐 ] intersects with ‖𝜙‖.
𝑊 𝑊 𝑊
𝜎. Consider the following properties which may hold of
Since (iii) does not hold, this in fact implies Π𝑊 𝑊
𝑖 [𝑣𝑐 ] ⊆ a learning method 𝐿.
‖𝜙‖, and consequently Π𝑖 [𝑤] = Π𝑖 [𝑣𝑐 ] ⊆ ‖𝜙‖.
𝑊2 𝑊 𝑊
Since 𝑤 ∈ ‖𝜙‖ was arbitrary, we have shown Π𝑊 2 Equivalence If 𝜎 ≡ 𝛿 then 𝐿(𝜎) = 𝐿(𝛿).
𝑖 [𝜙] =
𝑊2
Since the reverse inclusion
⋃︀
𝑤∈‖𝜙‖ 𝑖Π [𝑤] ⊆ ‖𝜙‖. Repetition 𝐿(𝜎 𝑘 ) = 𝐿(𝜎).
always holds, this shows 𝑊2 |= E𝑖 𝜙, and we are done.
Soundness 𝐿(𝜎) ⊆ 𝒳𝜎snd .
Proof of Theorem 4. The implication (1) to (2) is clear Equivalence says that 𝐿 should not care about the syn-
since if 𝑊 ′ ∈ 𝑄* [𝑊 ] then Π𝑊
′
= Π𝑊 by (1), so tactic form of the input. Repetition says that the output
𝑖 𝑖
𝑊 |= E𝑖 𝜙 iff 𝑊 |= E𝑖 𝜙, and thus 𝑄* [𝑊 ] decides E𝑖 𝜙.
′ from 𝐿 should not change if each source repeats their
To show (2) implies (3) we show the contrapositive. reports 𝑘 times. Soundness says that all reports in 𝜎 are
Suppose |𝒱 ∖𝑅| > 1. Then there are distinct 𝑢, 𝑣 ∈ 𝒱 ∖𝑅. conjectured to be sound.
Let 𝜙 be any propositional formula with ‖𝜙‖ = {𝑢}. For methods satisfying these properties, we have a pre-
We show by Lemma 7 that 𝑄* [𝑊 ] does not decide E𝑖 𝜙. cise characterisation of truth-tracking, i.e. necessary and
Indeed, all three conditions fail: ‖𝜙‖ ̸⊆ 𝑅 (since 𝑢 ∈
/ 𝑅), sufficient conditions for 𝐿 to solve 𝑄* . First, some new
‖¬𝜙‖ ̸⊆ 𝑅 (since 𝑣 ∈ ‖¬𝜙‖ ∖ 𝑅) and no Π𝑊 𝑊 notation is required. Write 𝛿 ⪯ 𝜎 iff for each ⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝛿
𝑖 [𝑣𝑐 ]
intersects with ‖𝜙‖ (otherwise 𝑢 ∈ Π𝑖 [𝑣𝑐 ] ⊆ 𝑅).
𝑊 𝑊
87
�there is 𝜓 ≡ 𝜙 such that ⟨𝑖, 𝑐, 𝜓⟩ ∈ 𝜎. That is, 𝜎 contains From 𝑊 ′ ∈ 𝒳𝜎snd and S𝑖 𝜙 ≡ S𝑖 𝜓 we get 𝑊 ′ , 𝑐 |= S𝑖 𝜙.
everything 𝛿 does, up to logical equivalence. Set This shows 𝑊 ⊑ 𝑊 ′ .
⋃︁ {︁ snd }︁ Now suppose 𝑊 ⊑ 𝑊 ′ and let ⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝜎. Then
𝑇𝜎 = 𝒳𝜎snd ∖ 𝒳𝛿 | 𝛿 ̸⪯ 𝜎 ⊆ 𝒲. since 𝑊 ∈ 𝑇𝜎 ⊆ 𝒳𝜎snd we have 𝑊, 𝑐 |= S𝑖 𝜙, and 𝑊 ⊑
𝑊 ′ gives 𝑊 ′ , 𝑐 |= S𝑖 𝜙. Consequently 𝑊 ′ ∈ 𝒳𝜎snd .
Then 𝑊 ∈ 𝑇𝜎 iff 𝜎 is sound for 𝑊 and any 𝛿 sound for Now for (ii), first suppose 𝑊 ′ ∈ 𝑄* [𝑊 ]. Then 𝑊 and
𝑊 has 𝛿 ⪯ 𝜎. In this sense 𝜎 contains all soundness 𝑊 ′ satisfy exactly the same soundness statements, so
statements for 𝑊 – up to equivalence – so can be seen as 𝑊 ′ ∈ 𝑇𝜎 also. Conversely, suppose 𝑊 ′ ∈ 𝑇𝜎 . Then
a finite version of a stream. Let us call 𝜎 a pseudo-stream 𝑊 ′ ∈ 𝒳𝜎snd , so (i) gives 𝑊 ⊑ 𝑊 ′ . But we also have
for 𝑊 whenever 𝑊 ∈ 𝑇𝜎 . 𝑊 ′ ∈ 𝑇𝜎 and 𝑊 ∈ 𝒳𝜎snd , so (i) again gives 𝑊 ′ ⊑ 𝑊 .
Hence 𝑊 ≈ 𝑊 ′ , i.e. 𝑊 ′ ∈ 𝑄* [𝑊 ].
Theorem 5. A method 𝐿 satisfying Equivalence, Rep-
etition and Soundness is truth-tracking if and only if it The next two results show that initial segments of
satisfies the following property. streams are (eventually) pseudo-streams, and that any
pseudo-stream gives rise to a stream.
Credulity 𝑇𝜎 , 𝑐 ̸|= S𝑖 𝜙 =⇒ 𝐿(𝜎), 𝑐 |= ¬S𝑖 𝜙.
Lemma 9. If 𝜌 is a stream for 𝑊 , there is 𝑛 such that
Before the proof, we comment on our interpretation 𝑊 ∈ 𝑇
𝜌[𝑚] for all 𝑚 ≥ 𝑛.
of Credulity. It says that whenever ¬S𝑖 𝜙 is consistent
with 𝑇𝜎 – those 𝑊 for which 𝜎 is a pseudo-stream – Proof. Let ̂︀· be a function which selects a representative
𝐿(𝜎) should imply ¬S𝑖 𝜙. Since the number of sound formula for each equivalence class of ℒ0 /≡, so that 𝜙 ≡
statements decreases with increasing expertise, this is a 𝜙 ̂︀ and 𝜙 ≡ 𝜓 implies 𝜙 ̂︀ is equal to 𝜓.̂︀ Note that since
principle of maximal trust: we should believe 𝑖 has the ex- Prop is finite, and since 𝒮 and 𝒞 are also finite, there
pertise to rule out 𝜙 in case 𝑐, whenever this is consistent are only finitely many reports of the form ⟨𝑖, 𝑐, 𝜙⟩. ̂︀ By
with 𝑇𝜎 . That is, some amount of credulity is required completeness of 𝜌 for 𝑊 , we may take 𝑛 sufficiently
to find the truth. Our assumption that learning methods large so that 𝑊, 𝑐 |= S𝑖 𝜙 ̂︀ implies ⟨𝑖, 𝑐, 𝜙⟩
̂︀ ∈ 𝜌[𝑛], for all
receive complete streams ensures that, if a source in fact 𝑖, 𝑐, 𝜙. Now, take 𝑚 ≥ 𝑛. We need to show 𝑊 ∈ 𝑇𝜌[𝑚] .
lacks this expertise, they will eventually report 𝜙 and this Clearly 𝑊 ∈ 𝒳 snd , since 𝜌 is sound for 𝑊 . Suppose
𝜌[𝑚]
belief can be be retracted. A stronger version of Credulity
𝑊 ∈ 𝒳𝛿snd . We need to show 𝛿 ⪯ 𝜌[𝑚]. Indeed, take
spells this out explicitly in terms of expertise:
⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝛿. Then 𝑊, 𝑐 |= S𝑖 𝜙. Since S𝑖 𝜙 ≡ S𝑖 𝜙, ̂︀
∀𝜎, 𝑖, 𝑐, 𝜙 : 𝑇𝜎 , 𝑐 ̸|= ¬E𝑖 𝜙 =⇒ 𝐿(𝜎), 𝑐 |= E𝑖 𝜙. (1) we have 𝑊, 𝑐 |= S𝑖 𝜙.
̂︀ Hence ⟨𝑖, 𝑐, 𝜙⟩
̂︀ appears in 𝜌[𝑛],
and consequently in 𝜌[𝑚] too. Since 𝜙 ≡ 𝜙, ̂︀ this shows
(1) implies Credulity in the presence of Soundness, and is 𝛿 ⪯ 𝜌[𝑚].
thus a sufficient condition for truth-tracking (when also
Lemma 10. If 𝑊 ∈ 𝑇𝜎 and 𝑁 = |𝜎|, there is a stream
taken with Equivalence and Repetition).5
𝜌 for 𝑊 such that 𝜌[𝑁 𝑘] ≡ 𝜎 𝑘 for all 𝑘 ∈ N.
Theorem 5 also shows truth-tracking cannot be per-
formed deductively: the method 𝐿(𝜎) = 𝒳𝜎snd , which Proof. First note that 𝑊 ∈ 𝑇𝜎 implies 𝜎 ̸= ∅, so 𝑁 >
does not go beyond the mere information that each re- 0. Since ℒ0 is countable, we may index the set of ℒ0
port is sound, fails Credulity. Some amount of inductive formulas equivalent to 𝜙 ∈ ℒ0 as {𝜙𝑛 }𝑛∈N . Let 𝜎𝑛
or non-monotonic reasoning, as captured by Credulity, is be obtained from 𝜎 by replacing each report ⟨𝑖, 𝑐, 𝜙⟩
necessary. with ⟨𝑖, 𝑐, 𝜙𝑛 ⟩. Then 𝜎 ≡ 𝜎𝑛 . Let 𝜌 be the sequence
The rest of this section works towards the proof of obtained as the infinite concatenation 𝜎1 ∘ 𝜎2 ∘ 𝜎3 ∘ · · ·
Theorem 5. We collect some useful properties of pseudo- (this is possible since 𝜎 is of positive finite length). Then
streams. First, pseudo-streams provide a way of accessing 𝜌[𝑁 𝑘] = 𝜎1 ∘ · · · ∘ 𝜎𝑘 , and consequently 𝜌[𝑁 𝑘] ≡ 𝜎 𝑘 .
𝑄* via a finite sequence: 𝑇𝜎 is a cell in 𝑄* whenever it It remains to show 𝜌 is a stream for 𝑊 . Soundness
is non-empty. of 𝜌 follows from 𝑊 ∈ 𝑇𝜎 ⊆ 𝒳 snd , since every report
𝜎
Lemma 8. If 𝑊 ∈ 𝑇𝜎 , then (i) 𝑊 ′ ∈ 𝒳𝜎snd iff 𝑊 ⊑ 𝑊 ′ ; in 𝜌 is equivalent to some report in 𝜎 by construction.
and (ii) 𝑇𝜎 = 𝑄* [𝑊 ]. For completeness, suppose 𝑊, 𝑐 |= S𝑖 𝜙. As in the proof
of Lemma 8, considering the singleton sequence 𝛿 =
Proof. Suppose 𝑊 ∈ 𝑇𝜎 . For (i), first suppose 𝑊 ′ ∈ ⟨𝑖, 𝑐, 𝜙⟩, we get from 𝑊 ∈ 𝑇𝜎 that there is 𝜓 ≡ 𝜙
𝒳𝜎snd and 𝑊, 𝑐 |= S𝑖 𝜙. Considering the singleton se- such that ⟨𝑖, 𝑐, 𝜓⟩ ∈ 𝜎. Hence there is 𝑛 ∈ N such that
quence 𝛿 = ⟨𝑖, 𝑐, 𝜙⟩ we have 𝑊 ∈ 𝒳𝛿snd . From 𝑊 ∈ 𝑇𝜎 𝜙 = 𝜓𝑛 , so ⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝜎𝑛 , and thus ⟨𝑖, 𝑐, 𝜙⟩ ∈ 𝜌.
we get 𝛿 ⪯ 𝜎, i.e. there is 𝜓 ≡ 𝜙 such that ⟨𝑖, 𝑐, 𝜓⟩ ∈ 𝜎.
5
We conjecture (1) is strictly stronger than Credulity.
88
� Next we obtain an equivalent formulation of Credulity corresponding to each new report ⟨𝑖, 𝑐, 𝜙⟩. In this pa-
which is less transparent as a postulate for learning meth- per, we take a report ⟨𝑖, 𝑐, 𝜙⟩ to correspond to the fact
ods, but easier to work with. that S𝑖 𝜙 holds in case 𝑐; this fits with our assumption
throughout that sources only report sound statements.7
Lemma 11. Suppose 𝐿 satisfies Soundness. Then 𝐿 sat- Thus, the worlds under consideration given a sequence
isfies Credulity if and only if 𝐿(𝜎) ⊆ 𝑇𝜎 for all 𝜎 with 𝜎 are exactly those satisfying all soundness statements
𝑇𝜎 ̸= ∅. in 𝜎, i.e. 𝒳𝜎snd . Note that 𝒳𝜎snd represents the indefeasible
Proof. “if”: Suppose 𝑇𝜎 , 𝑐 ̸|= S𝑖 𝜙. Then there is 𝑊 ∈ knowledge given by 𝜎: worlds outside 𝒳𝜎 are elimi-
snd
𝑇𝜎 such that 𝑊, 𝑐 ̸|= S𝑖 𝜙. By our assumption and nated and cannot be recovered with further reports, since
Lemma 8, 𝐿(𝜎) ⊆ 𝑇𝜎 = 𝑄* [𝑊 ]. Thus every world 𝒳𝜎∘𝛿 ⊆ 𝒳𝜎 . The plausibility order allows us to rep-
snd snd
in 𝐿(𝜎) agrees with 𝑊 on soundness statements, so resent defeasible beliefs about the most plausible worlds
𝐿(𝜎), 𝑐 |= ¬S 𝜙. within 𝒳 snd
𝜎 .
𝑖
“only if”: Suppose there is some 𝑊 ∈ 𝑇𝜎 , and Definition 4. For a total preorder ≤ on 𝒲, the condi-
take 𝑊 ′ ∈ 𝐿(𝜎). We need to show 𝑊 ′ ∈ 𝑇𝜎 ; by tioning method 𝐿≤ is given by 𝐿≤ (𝜎) = min≤ 𝒳𝜎snd .
Lemma 8, this is equivalent to 𝑊 ≈ 𝑊 ′ . First suppose
𝑊, 𝑐 |= S𝑖 𝜙. Then 𝑊 ∈ 𝑇𝜎 implies there is 𝜓 ≡ 𝜙 Note that since 𝒳𝜎snd ̸= ∅ for all 𝜎 8 and 𝒲 is finite,
such that ⟨𝑖, 𝑐, 𝜓⟩ ∈ 𝜎. By Soundness for 𝐿, we have 𝐿≤ is consistent. Moreover, 𝐿≤ satisfies Equivalence,
𝑊 ′ ∈ 𝐿(𝜎) ⊆ 𝒳𝜎snd . Consequently 𝑊 ′ , 𝑐 |= S𝑖 𝜓 and Repetition and Soundness.
thus 𝑊 ′ , 𝑐 |= S𝑖 𝜙. This shows 𝑊 ⊑ 𝑊 ′ . Now sup-
pose 𝑊, 𝑐 ̸|= S𝑖 𝜙. Then 𝑇𝜎 , 𝑐 ̸|= S𝑖 𝜙. By Credulity, Example 9. We recall two concrete choices of ≤ from
𝐿(𝜎), 𝑐 |= ¬S𝑖 𝜙. Hence 𝑊 ′ , 𝑐 ̸|= S𝑖 𝜙. This shows Singleton and Booth [1].
𝑊 ′ ⊑ 𝑊 . Thus 𝑊 ≈ 𝑊 ′ as required.
1. Set 𝑊 ≤ 𝑊 ′ iff 𝑟(𝑊 ) ≤ 𝑟(𝑊 ′ ), where
Finally, we prove the characterisation of truth- ∑︁
tracking. 𝑟(𝑊 ) = − |{𝑝 ∈ Prop | Π𝑊𝑖 [𝑝] = ‖𝑝‖}|.
𝑖∈𝒮
Proof of Theorem 5. Suppose 𝐿 satisfies Equivalence,
Repetition and Soundness. The most plausible worlds in this order are those in
“if”: Suppose Credulity holds. We show 𝐿 solves 𝑄* . which source have as much expertise on the propo-
Take any world 𝑊 and stream 𝜌 for 𝑊 . By Lemma 9, sitional variables as possible, on aggregate. We
there is 𝑛 such that 𝑊 ∈ 𝑇𝜌[𝑚] for all 𝑚 ≥ 𝑛. By denote the corresponding conditioning method by
Lemma 8, 𝑇𝜌[𝑚] = 𝑄* [𝑊 ] for such 𝑚. In particu- 𝐿vbc , standing for variable-based conditioning.
lar, 𝑇𝜌[𝑚] ̸= ∅. By Credulity and Lemma 11, we get 2. Set 𝑊 ≤ 𝑊 ′ iff 𝑟(𝑊 ) ≤ 𝑟(𝑊 ′ ), where
𝐿(𝜌[𝑚]) ⊆ 𝑇𝜌[𝑚] = 𝑄* [𝑊 ].
“only if”: Suppose 𝐿 solves 𝑄* . We show Credulity
∑︁ 𝑊
𝑟(𝑊 ) = − |Π𝑖 |.
via Lemma 11. Suppose there is some 𝑊 ∈ 𝑇𝜎 , and 𝑖∈𝒮
write 𝑁 = |𝜎| > 0. By Lemma 10, there is a stream
𝜌 for 𝑊 such that 𝜌[𝑁 𝑘] ≡ 𝜎 𝑘 for all 𝑘 ∈ N. By Rep- This order aims to maximise the number of cells
etition and Equivalence, 𝐿(𝜎) = 𝐿(𝜎 𝑘 ) = 𝐿(𝜌[𝑁 𝑘]). in each source’s partitions, thereby maximising the
But 𝐿 solves 𝑄* , so for 𝑘 sufficiently large we have number of propositions on which they have exper-
𝐿(𝜌[𝑁 𝑘]) ⊆ 𝑄* [𝑊 ] = 𝑇𝜎 . Hence, going via some tise. Note that the propositional variables play no
large 𝑘, we obtain 𝐿(𝜎) ⊆ 𝑇𝜎 as required. special role. We denote the corresponding condi-
tioning operator by 𝐿pbc , for partition-based con-
6.2. Conditioning Methods ditioning.
In this section we turn to the family of conditioning meth- A straightforward property of ≤ characterises truth-
ods, proposed in [1] and inspired by similar methods in tracking for conditioning methods. For a generic total
the belief change literature [22]. While our interpreta- preorder ≤, let < denote its strict part.
tion of input sequences is different – we read ⟨𝑖, 𝑐, 𝜙⟩ as
𝑖 reporting 𝜙 is possible in case 𝑐, whereas Singleton and Theorem 6. 𝐿≤ is truth-tracking if and only if
Booth [1] read this as 𝑖 believes 𝜙 – this class of methods
𝑊 ⊏ 𝑊 ′ =⇒ ∃𝑊 ′′ ≈ 𝑊 such that 𝑊 ′′ < 𝑊 ′ . (2)
can still be applied in our setting.
Conditioning methods operate by successively restrict-
7
ing a fixed plausibility total preorder 6 to the information Singleton and Booth [1] consider more general conditioning meth-
ods in which this choice is not fixed.
6 8
A total preorder is a reflexive, transitive and total relation. For example, if Π𝑊𝑖 = {𝒱} for all 𝑖 then 𝑊 ∈ 𝒳𝜎 for all 𝜎 .
snd
89
� 𝑊 and 𝑊 ′ shown in Fig. 3, where we assume
p̄q p̄q̄ p̄q p̄q̄ Prop = {𝑝, 𝑞}, 𝒮 = {𝑖} and 𝒞 = {𝑐}. Then
′
𝑊 ⊏ 𝑊 ′ (e.g. by Lemma 1). Note that 𝑖 does not
vcW vcW have expertise on 𝑝 or 𝑞 in both 𝑊 and 𝑊 ′ , so
𝑟(𝑊 ) = 𝑟(𝑊 ′ ) = 0. Moreover, 𝑖’s partition is
pq pq̄ pq pq̄ uniquely determined in 𝑄* [𝑊 ] by Theorem 4, so
if 𝑊 ′′ ≈ 𝑊 then 𝑟(𝑊 ′′ ) = 0 also. That is, there
′ is no 𝑊 ′′ ≈ 𝑊 such that 𝑊 ′′ < 𝑊 ′ . Hence (2)
ΠW
i ΠW
i fails, and 𝐿vbc is not truth-tracking. Intuitively, the
problem here is that since 𝑖’s expertise is not split
Figure 3: Worlds which demonstrate 𝐿vbc is not truth- along the lines of the propositional variables when
tracking.
𝑊 is the actual world, 𝐿vbc will always maintain
𝑊 ′ as a possibility.
Like Credulity, (2) is a principle of maximising trust in 2. The partition-based conditioning method 𝐿pbc is
sources. Recall from that Lemma 1 that 𝑊 ⊏ 𝑊 ′ means truth-tracking. Indeed, if 𝑊 ⊏ 𝑊 ′ we may
all sources are more knowledgeable in each case in 𝑊 construct 𝑊 ′′ from 𝑊 by modifying the parti-
than in 𝑊 ′ , and there is at least one source and case each source 𝑖 so that all valuations out-
tion of ⋃︀
for which this holds strictly. If we aim to trust sources side of 𝑐∈𝒞 Π𝑊 𝑊
𝑖 [𝑣𝑐 ] lie in their own cell. Then
′′ ′
′′
as much as possible, we might impose 𝑊 < 𝑊 ′ here; 𝑊 ≈ 𝑊 . One can show that Π𝑊 𝑖 refines Π𝑊
𝑖
then 𝑊 ′ is strictly less plausible and will be ruled out for all 𝑖 ∈ 𝒮, and there is some 𝑖 for which the
in favour of 𝑊 . This yields a sufficient condition for refinement is strict. Hence the partitions in 𝑊 ′′
truth-tracking, but to obtain a necessary condition we contain strictly more cells, so 𝑊 ′′ < 𝑊 ′ .
need to allow a “surrogate” world 𝑊 ′′ ≈ 𝑊 to take the
place of 𝑊 .
7. Conclusion
Proof of Theorem 6. Write 𝐿 = 𝐿≤ . Since 𝐿 satisfies
Equivalence, Repetition and Soundness, we may use The- Summary. In this paper we studied truth-tracking in
orem 5. Furthermore, it is sufficient by Lemma 11 to the presence of non-expert sources. The model assumes
show that (2) holds if and only if 𝐿(𝜎) ⊆ 𝑇𝜎 , whenever sources report everything true up to their lack of exper-
𝑇𝜎 ̸= ∅. tise, i.e. all that they consider possible. We obtained
“if”: Suppose 𝑊 ⊏ 𝑊 ′ . Let 𝜎 be some pseudo- precise characterisations of when truth-tracking meth-
stream for 𝑊 , so that 𝑊 ∈ 𝑇𝜎 .9 Note that since ods can uniquely find the valuations and partitions of a
𝑊 ∈ 𝑇𝜎 ⊆ 𝒳𝜎snd and 𝑊 ⊏ 𝑊 ′ , we have 𝑊 ′ ∈ 𝒳𝜎snd world 𝑊 . We then gave a postulational characterisation
also. By assumption, 𝐿(𝜎) ⊆ 𝑇𝜎 = 𝑄* [𝑊 ]. Since of truth-tracking methods under mild assumptions, be-
𝑊 ̸≈ 𝑊 ′ , this means 𝑊 ′ ∈ 𝒳𝜎snd ∖ 𝐿(𝜎). That is, 𝑊 ′ fore looking specifically at the conditioning methods of
lies in 𝒳𝜎snd but is not ≤-minimal. Consequently there Singleton and Booth [1].
is 𝑊 ′′ ∈ 𝒳𝜎snd such that 𝑊 ′′ < 𝑊 ′ . Since 𝐿 is con-
sistent, we may assume without loss of generality that Limitations and future work. Conceptually, the as-
𝑊 ′′ ∈ 𝐿(𝜎). Hence 𝑊 ′′ ∈ 𝑄* [𝑊 ], so 𝑊 ′′ ≈ 𝑊 . sumption that streams are complete is very strong. As
“only if”: Suppose there is some 𝑊 ∈ 𝑇𝜎 , and let seen in Example 3, completeness requires sources to
𝑊 ′ ∈ 𝐿(𝜎). We need to show 𝑊 ′ ∈ 𝑇𝜎 = 𝑄* [𝑊 ], i.e. give jointly inconsistent reports whenever Π𝑖 [𝑣𝑐 ] con-
𝑊 ≈ 𝑊 ′ . Since 𝑊 ′ ∈ 𝐿(𝜎) ⊆ 𝒳𝜎snd , Lemma 8 gives tains more than just 𝑣𝑐 . Such reports provide informa-
𝑊 ⊑ 𝑊 ′ . Suppose for contradiction that 𝑊 ̸≈ 𝑊 ′ . tion about the source’s expertise: if 𝑖 reports both 𝜙
Then 𝑊 ⊏ 𝑊 ′ . By (2), there is 𝑊 ′′ ≈ 𝑊 such that and ¬𝜙 we know ¬E𝑖 𝜙. To provide all sound reports
𝑊 ′′ < 𝑊 ′ . But 𝑊 ′ is ≤-minimal in 𝒳𝜎snd , so this must sources must also have negative introspection over their
mean 𝑊 ′′ ∈ / 𝒳𝜎snd . On the other hand, 𝑊 ′′ ∈ 𝑄* [𝑊 ] = own knowledge, i.e. they know when they do not know
𝑇𝜎 ⊆ 𝒳𝜎 : contradiction.
snd something. Indeed, our use of partitions makes expertise
closely related to S5 knowledge [1, 20], which has been
criticised in the philosophical literature as too strong. In
Example 10. We revisit the methods of Example 9.
reality, non-expert sources may have beliefs about the
1. The variable-based conditioning method 𝐿vbc is world, and may prefer to report only that which they
not truth-tracking. Indeed, consider the worlds believe. A source may even believe a sound report 𝜙 is
false, since soundness only says the source does not know
9
For example, pick some stream 𝜌 and apply Lemma 9 to obtain a ¬𝜙. For example, in Example 1 the doctor D may think it
pseudo-stream.
90
�is more likely that 𝐴 suffers from 𝑝 than 𝑞, but we cannot [10] E. M. Gold, Language identification in the limit,
express this in our framework. Information and Control 10 (1967) 447–474. doi:10.
On the technical side, our results on solvability of 𝑄* 1016/s0019-9958(67)91165-5.
and the characterisation of Theorem 5 rely on the fact that [11] K. Kelly, O. Schulte, V. Hendricks, Reliable belief
we only consider finitely many worlds. In a sense this revision, in: Logic and Scientific Methods, Springer,
trivialises the problem of induction as studied by Kelly 1997, pp. 383–398.
et al. [11], Baltag et al. [21], among others. In future work [12] A. Baltag, N. Gierasimczuk, S. Smets,
it would be interesting to see which results can be carried Truth-Tracking by Belief Revision, Stu-
over to the case where Prop is infinite. dia Logica 107 (2019) 917–947. URL:
https://doi.org/10.1007/s11225-018-9812-x.
doi:10.1007/s11225-018-9812-x.
Acknowledgments [13] N. Gierasimczuk, Bridging learning theory and
dynamic epistemic logic, Synthese 169 (2009) 371–
We thank the reviewers for their detailed comments,
384.
which are useful for improving both current and future
[14] N. Gierasimczuk, Learning by erasing in dynamic
versions of this paper.
epistemic logic, in: International Conference on
Language and Automata Theory and Applications,
References Springer, 2009, pp. 362–373.
[15] N. Gierasimczuk, Knowing one’s limits: logical anal-
[1] J. Singleton, R. Booth, Who’s the expert? On multi- ysis of inductive inference, Ph.D. thesis, ILLC, 2010.
source belief change, in: KR (forthcoming), 2022. [16] A. Baltag, N. Gierasimczuk, A. Özgün, A. L. V. San-
URL: https://arxiv.org/abs/2205.00077. doval, S. Smets, A dynamic logic for learning the-
[2] N. de Condorcet, Essai sur l’application de l’analyse ory, Journal of Logical and Algebraic Methods in
à la probabilité des décisions rendues à la pluralité Programming 109 (2019) 100485.
des voix, 1785. [17] C. E. Alchourrón, P. Gärdenfors, D. Makinson, On
[3] B. Grofman, G. Owen, S. L. Feld, Thirteen theorems the logic of theory change: Partial meet contraction
in search of the truth, Theory and decision 15 (1983) and revision functions, Journal of symbolic logic
261–278. (1985) 510–530.
[4] E. Elkind, A. Slinko, Rationalizations of voting [18] S. Konieczny, R. Pino Pérez, Merging information
rules, in: F. Brandt, V. Conitzer, U. Endriss, J. Lang, under constraints: a logical framework, Journal of
A. D. Procaccia (Eds.), Handbook of Computational Logic and computation 12 (2002) 773–808.
Social Choice, Cambridge University Press, 2016, [19] V. Goranko, S. Passy, Using the universal modality:
pp. 169–196. Gains and questions, Journal of Logic and Compu-
[5] S. Hartmann, J. Sprenger, Judgment ag- tation 2 (1992) 5–30.
gregation and the problem of tracking the [20] J. Singleton, A logic of expertise,
truth, Synthese 187 (2012) 209–221. URL: https:// ESSLLI 2021 Student Session (2021).
doi.org/10.1007/s11229-011-0031-5. doi:10.1007/ Https://arxiv.org/abs/2107.10832.
s11229-011-0031-5. [21] A. Baltag, N. Gierasimczuk, S. Smets, On the
[6] Z. Terzopoulou, U. Endriss, Optimal truth-tracking solvability of inductive problems: A study in
rules for the aggregation of incomplete judgments, epistemic topology, Electronic Proceedings in
in: Proceedings of the 12th International Sympo- Theoretical Computer Science 215 (2016) 81–98.
sium on Algorithmic Game Theory (SAGT-2019), URL: http://dx.doi.org/10.4204/EPTCS.215.7. doi:10.
2019. 4204/eptcs.215.7.
[7] P. Everaere, S. Konieczny, P. Marquis, The epistemic [22] W. Spohn, Ordinal conditional functions: A dy-
view of belief merging: Can we track the truth?., namic theory of epistemic states, in: Causation
in: ECAI, 2010, pp. 621–626. in decision, belief change, and statistics, Springer,
[8] Y. Li, J. Gao, C. Meng, Q. Li, L. Su, B. Zhao, W. Fan, 1988, pp. 105–134.
J. Han, A Survey on Truth Discovery, SIGKDD Ex-
plor. Newsl. 17 (2016) 1–16. URL: http://doi.acm.org/
10.1145/2897350.2897352. doi:10.1145/2897350.
2897352.
[9] S. Jain, D. Osherson, J. S. Royer, A. Sharma, Systems
that Learn: An Introduction to Learning Theory,
MIT, 1999.
91
�