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 afairs in the domain described by the sources, and ifnding 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 afairs 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.
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 methtiple 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] ofers 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 cora 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 theinfinity, 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 proporesult 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 beframework. 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@cardif.ac.uk (J. Singleton); boothr2@cardif.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 information is eventually received.1 This is not a tenCPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) able assumption with non-expert sources: some sources may simply lack the expertise to know whether is true or false. Instead we make a diferent (and strong) assumption: all and only sound reports are received. Thus, sources report everything consistent with their expertise, which necessitates inconsistent reports from non-experts.
be distinguished from the inputs to belief revision and belief merging methods [17, 18] – also propositional formulas – which represent beliefs of the reporting sources.
vA vB p¯q pq p¯q¯ pq¯ ΠD ΠT
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 test. A test is only available for , however, so that the technician T performing the test has expertise on but not .
ables, and let ℒ0 denote the propositional language generated from Prop. We use ℒ0 to model the domain underlying the truth-tracking problem; it describes the “ontic”
Supposing in fact sufers 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 ℒ exexpertise 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 sufers 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 ES . 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 valuations over Prop. We represent the expertise of a source with a partition Π of . Intuitively, this partition repPaper 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 indistintroduces 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 diferent cells. We say has expertise on if 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. 1But see Jain et al. [9, §8.1], which considers inaccurate data of various kinds, and Baltag et al. [12], which considers erroneous reports provided that all errors are eventually corrected.
A world is a pair = ⟨{}∈ , {Π}∈ ⟩, where
• ∈ is the “actual” valuation for case ;
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 ⊩ if ∈ ‖ ‖. 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 the point of view of ’s expertise, we can view a stream as each source sharing all that they consider possible for each case ∈ . In particular, a non-expert source may report both and ¬ for the same case. where the clauses for conjunction and negation are as standard. The semantics follows the intuition outlined above: E holds when Π separates the states from the ¬ states, and S holds when is indistinguishable from some state. Thus, S means is true up to the expertise of : if we weaken according to ’s expertise, the resulting formula (with models Π[ ]) is true.
Note that expertise and soundness are closely related to S5 knowledge from epistemic logic. By taking the equivalence relations associated with each partition Π, we obtain a (multi-agent) S5 Kripke model, and have the correspondences S ≡ ¬ K¬ and E ≡ A( → K ), where K denotes knowledge of source and A is the universal modality [19]. This gives expertise and soundness precise interpretations in terms of knowledge; we refer the reader to [1, 20] for further discussion.
ample 1. Then , |= ED( ∨ ) for all ∈ , since ‖ ∨ ‖ is a cell in ΠD. We also have , |= ¬ ∧ SD, i.e. patient does not sufer from condition , but it is consistent with D’s expertise that they do.
We write , |= Γ, for a set of formulas Γ ⊆ ℒ , if , |= Φ for all Φ ∈ Γ. For a set ⊆ , we write , |= Φ if , |= Φ for all ∈ .
Reports. A report is a triple ⟨, , ⟩, where ∈ , ∈ and ∈ ℒ0 with ̸≡ ⊥ . In this paper, we interpret such triples as source reporting that is possible in case . An input sequence is a finite sequence of reports.
worlds ( ) ⊆ , called the conjecture of on .2 We say implies ⊆ on the basis of if ( ) ⊆ . is consistent if ( ) ̸= ∅ for all input sequences .
for if for all , , : ⟨, , ⟩ ∈
⇐⇒ , |= S.
We refer to the left-to-right implication as soundness of for , and the right-to-left direction as completeness. Note that every world has some stream: the set {⟨, , ⟩ | , |= S } is countable, so can be indexed by N to form a stream. For ∈ N we let denote the -th report in , and write [] for the finite initial segment of of length .
the point of view of D’s expertise, the “actual” valuation could be , ¯, ¯. Consequently, in a stream for , D will report , ¬, , ¬, ∨ , and so on. A report that D will not give is ¬( ∨ ), since D has expertise to know this is false.
reports of D in any stream will be the same for both cases.
¬ in case but not in , and in case but not in .
A question is a partition of . That is, a question is a set of disjoint answers ∈ , with each world appearing in a unique cell [ ] – the correct answer at .
Example 4. We consider some example questions. • Π ⊆ 2 is a partition representing the expertise of . 3. Truth-Tracking 2We depart from the original framework here by taking a semantic view of belief change operators, with the output a set of worlds instead of formulas. 3Alternatively, we can consider statements of the form “ is sound for in case ” as a higher-order “proposition”; a stream then enumerates all true propositions of this kind. 1. Any formula Φ ∈ ℒ and case defines a question Φ,, whose two cells consist of the worlds satisfying Φ, respectively ¬Φ, in case . Intuitively, this question asks whether Φ is true or false in case . 2. The finest question ⊥ = {{ } | ∈ } asks: what is the “actual” world?
→ , the equivalence relation given by ≃ ′ if ( ) = ( ′) defines a question . answers of , and thus ′ is easier than . Naturally, if is solvable then so too is any easier question. Proposition 2. If is solvable and ⪯ ′, then ′ is solvable.
reports, worlds satisfying the same soundness statements 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 | Π [] = ‖‖} we ask for the set of sources with expertise on ; if ( ) = |{ ∈ | , |= Thus, ⊑ ′ if 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 =⇒ ′, |= S.
may define : → by ( ) = [ ]; then = .
answer when given any stream.
worlds and all streams for , there is ∈ N such that ( []) ⊆ [ ] for all ≥ . A question is solvable if there is some consistent method which solves .
Note that we do not require ∈ ( []). Since we work in a finite framework, solvability can be also expressed in terms of eliminating incorrect worlds.
all , all streams for , and all ′ ∈/ [ ], there is ′ ∈ N such that ′ ∈/ ( []) for all ≥ ′ . Proof. “if”: Taking = max{ ′ | ′ ∈/ [ ]}, which exists since is finite, ( []) ⊆ [ ] for ≥ .
“only if”: Taking from the definition of solving , we may simply take ′ = for all ′ ∈/ [ ].
that there is a unique “hardest” question which subsumes all solvable questions. We show this is itself solvable, and thus obtain a precise characterisation of solvability.
⪯ ′ if each ′ ∈ ′ can be written as a union of answers from . Equivalently, [ ] ⊆ ′[ ] for all . This can be interpreted as a dificulty ordering : if ⪯ ′ then each answer of ′ is just a disjunction of Lemma 1. ⊑ ′ if and only if for all ∈ and ∈ , Π [ ] ⊆ Π ′ [ ′ ].
Proof. “if”: Suppose , |= S . Then ∈ Π [ ], so there is ∈ ‖ ‖ such that ∈ Π []. Consequently ∈ Π [ ] ⊆ Π ′ [ ′ ], which means ′ ∈ Π ′ [] ⊆ Π ′ [ ]. Hence ′, |= S . This shows ⊑ ′.
“only if”: Let ∈ Π [ ]. Let be any formula with ‖ ‖ = {}. Then , |= S , so ⊑ ′ gives ′, |= S , i.e. ′ ∈ Π ′ [], so ∈ Π ′ [ ′ ]. Hence Π [ ] ⊆ Π ′ [ ′ ].
Note that Π[] is the set of valuations indistinguishable from the “actual” valuation in case , for source . In light of Lemma 1, we can interpret ⊑ ′ as saying that all sources are more knowledgeable in each case in world than in ′. However, ⊑ ′ does not say anything about the partition cells not containing some .
2. ≈ ′.
3. For all ∈ and ∈ , Π [ ] = Π ′ [ ′ ].
of Lemma 1. To show (
On the other hand, if ≈ ′ then and ′ satisfy exactly the same soundness statements, so it is clear that any sequence is a stream for if it is a stream for ′. we have the following.
by * the question formed by the equivalence relation ≈ . Then * [ ] is the set of ′ with ≈ solvable question can distinguish ≈ -equivalent worlds, ′. Since no Lemma 2. If is solvable then * ⪯ .
Proof. Suppose is a consistent method solving . We show * [ ] ⊆ * [ ]. Then ′ ≈ [ ] for all . Indeed, let ′ ∈
. Taking any stream for , there is such that ( []) ⊆ [ ] for ≥ the other hand is also a stream for ′ by Proposition 3, so there is ′ such that ( []) ⊆ [ ′] for ≥ Setting = max{, ′} and using the fact that is ′. . On consistent, we find ∅ ⊂ and there is no ′ ∈ ∈ snd if
snd ̸= ∅, and ( ) = min⊑ snd if ∈
snd snd with ′ ⊏ ). Note that is consistent since is finite and non-empty. We show that solves * by Proposition 1. Take any world and a stream . First note that, by soundness of , ∈ sn[d] for all ∈ N, so we are always in the first Take ′ ∈/ * [ ]. Then ̸≈ ′. Consider two • Case 1: ̸⊑ ′. By definition, there are , , such that , |= S
but ′, ̸|= S . By completeness of for , there is such that snd = ⟨, , ⟩. Consequently ′ ∈/ [] for all ≥
. Since ( []) ⊆ sn[d], we have ′ ∈/ ( []) as required. for all . ′ can never be ⊑-minimal. Thus ′ ∈/ ( [])
Theorem 1. is solvable if and only if * ⪯ .
ally matters: any other question is either unsolvable or formed by coarsening * . With this in mind, we make the following definition.
Definition 3.
Example 5. We refer back to the questions of Example 4. 1. The question , , for any propositional formula where 1 ⊩ , 2 ⊩
∈ ℒ0, is solvable if and only if either is a tautology or a contradiction. To see the “only if” part, consider the contrapositive. For any contingent formula , take worlds 1, 2 where no source has any expertise (i.e. Π = {}) but ¬ . Then 1 ≈ 2 (e.g. by Proposition 3) but 1 ∈/ , [2].
Similarly, E, is solvable if either is a tautology or contradiction, when |Prop| ≥ 2. 2. The finest question ⊥ is not solvable, since there are always distinct , ′ with ≈ ′. 3. In general, is solvable if ≈ ′ implies ( ) = ( ′), i.e. if takes a unique value on each equivalence class of ≈ . 5.
• Case 2: ⊏ ′. Since ∈ sn[d] for all , valuations is possible. On the other hand if all sources
Solving a question has a global character: we must ifnd the correct answer [ ] starting from any world . As we saw in Example 5, this rules out the possibility of solving many interesting questions due to the presence of “abnormal” worlds (e.g. those in which no sources have any expertise). In this section we take a more fine-grained approach by looking
locally: given some particular world , what can we learn about via truth-tracking methods? Concretely, what properties of are uniquely defined across * [ ]?
Clearly this depends on . If no sources have expertise then source partitions are uniquely defined (since all consistent formulas are sound, and only the trivial partitions have this property), but any combination of have total expertise then valuations are uniquely defined, but there may not be enough cases to uniquely identify the source partitions. Of particular interest is the case where * [ ] contains only ; starting in such a world, truth-tracking methods are able to find the true world exactly.
In what follows, say decides Φ in case if either , |= Φ or , |= ¬Φ. That is, the truth value of Φ in case is unambiguously defined across . If Φ does not depend on the case (e.g. if Φ = E ) we simply say decides Φ. maximally consistent. This example shows how the expertise of multiple sources can be combined to find valuations uniquely, but that this is not necessarily possible in all cases.
Lemma 3. For ≈ ′, ∈ and ∈ ℒ0, , |= ∧ E =⇒ ′, |= . 5.1. Valuations
tional formula in case , i.e. when truth-tracking methods are guaranteed to successfully determine whether 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.
We need a notion of group expertise. For ′ ⊆ and Γ ⊆ ℒ 0, write |= E′ Γ if for each ∈ Γ there is ∈ ′ such that |= E . Then the group ′ have expertise on Γ in a collective sense, even if no single source has expertise on all formulas in Γ. We have that is decided if have group expertise on a set of true formulas Γ ⊆ ℒ 0 such that either Γ ⊩ or Γ ⊩ ¬ . Proof. From , |= we have ∈ ‖ ‖, so Π [ ] ⊆ Π [ ]. But , |= E means Π [ ] = ‖ ‖, so in fact Π [ ] ⊆ ‖ ‖. Now using ≈ ′, we find ′ ∈ Π ′ [ ′ ] = Π [ ] ⊆ ‖ ‖. Hence
* [ ] = ⋂︀ Lemma 4. * [ ] decides all propositional formulas – and thus determines the -valuation exactly – if have group expertise on a maximally consistent set of true formulas.
For ⊆ and ∈ , write = { | ∈ } for the -valuations appearing in . as in we get Π [ ] = Π ′ [ ′ ]. For = , note Π ′ [ ′ ] = Π []. By assumption ∈ Π [ ], so Π [] = Π [ ]. Hence Π ′ [ ′ ] = Π [ ] as required.
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,
* [ ] = {¯} = { }, and * [ ] = {, ¯} ̸= ‖Γ‖ = ⋂︀∈ Π [ ] = * [ ]. Hence there is some
{ }. That is, ’s valuation is uniquely determined ′ ∈ * [ ] such that = ′ . But * [ ] decides
by truth-tracking methods, but its valuation is not: there in case , so ′, |= if , |= . Thus ⊩ if
is some world ′ ≈ whose -valuation difers 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. (
Formally, take Γ = { ∨ , ¬}. Then , |= Γ, and ′ share the same -valuation by (
* [ ]. Then there is ′ ∈ * [ ] such that = ′ . Let ∈ Prop. Since , ′ ∈ * [ ] and * [ ] decides in case , we have ⊩ if ⊩ . Since
(
= ⋃︀ ℒ0, there is a set Γ ⊆ ℒ 0 such that , |
= = E Γ , and either Γ ⊩ or Γ ⊩
¬ . Set ∈ℒ0 sistent – and | Γ . Clearly , |= Γ – so Γ is con
= E Γ. To show Cn0 (Γ) is maxitonicity of classical consequence and Γ ⊆ mally consistent, suppose /∈ Cn0 (Γ). From mono /∈ Cn0 (Γ ). Hence Γ ⊩ ¬ , and Γ ⊩
¬ means Cn0 (Γ) ∪ { } is inconsistent, and we are done.
Γ, we get
too. This
(
∈ ℒ0. Then we may apply to see that * [ ] decides in case .
consistency property ensure either Γ ⊩ or Γ |= ¬ – ∈ 5.2. Source Partitions We now apply the analysis of the previous section to the set of source partitions {Π }∈ . For ⊆ ∈ , write = {Π | ∈ } for the -partitions and appearing in . When = * [ ], these are exactly those partitions which agree with Π at each valuation . Π.
Lemma 5. Π ∈
* [ ] if and only if {Π [ ]}∈ ⊆ Proof. “if”: Suppose {Π [ ]}∈ ⊆ obtained from by setting ’s partition to Π, keeping valuations and other source partitions the same. We Π. Let ′ be claim ′ ≈ . Indeed, take any ∈ and ∈ .
If ̸= then Π ′ = Π ; since valuations are the same we get Π [ ] = Π ′ [ ′ ]. For = , note that since Π [ ]
Π by assumption, and ∈ 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 and bottommost sets. Any such Π consists of these cells together with a partition of the shaded area. Since there are 5 possible partitions of a 3-element set, it follows that | * [ ]| = 5.
Example 7 hints that if the cells containing the valuations cover the whole space of valuations , or just omit a single valuation, then ’s partition is uniquely defined in
* [ ]. That is, truth-tracking methods can determine the full extent of ’s expertise if the “actual” world is . Indeed, we have the following analogue of Theorem 3 for partitions. Γ , Theorem 4. The following are equivalent. 1.
* [ ] = {Π }. 2. * [ ] decides E for all ∈ ℒ0. 3. | ∖ | ≤ 1, where = ⋃︀ ∈
Π [ ].
∈ Note that = ⋃︀
Π [ ] is the set of valuations
this sense, it is easier to find
indistinguishable from the actual state at some case .
Theorem 4 (
Example 8. In Example 7 we have already seen an example of a world for which 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 * [ ] does not contain a truth-tracking methods.
⋃︀
∈ Π ′ [ ].
Lemma 6. Let ∈ and ⊆ . Then ⊆ Π [ ] and ≈
′ implies Π [ ] = Proof. It sufices to show that for all have Π [] = Π ′ [], since by definition ∈
we Π[ ] = Π [], as required, ≈ Π ′ [ ′ ], so Π ′ [] = Π ′ [ ′ ] = Π [ ] = ′, Π [ ] = Π ′ [ ′ ]. This means ∈ By Proposition 3, ′ ≈
. Hence Π ∈ “only if”: This is clear from Proposition 3. * [ ].
∈ ⋃︀ Π [ ], we have Π[ ] = Π [ ]. By construction of ′, this means Π [ ] = Π[ ′ ] = Π ′ [ ′ ]. ∈ Π [ ]. Hence Π [] = Π [ ]. But since ∈ Π[]. Let ∈ . Then there is ∈ such that Lemma 7. * [ ] decides E if and only if, writing = ⋃︀∈ Π [ ], either (i) ‖ ‖ ⊆ ; (ii) ‖¬ ‖ ⊆ ; or (iii) there is some ∈ such that Π [ ] intersects with both ‖ ‖ and ‖¬ ‖.
positive. Suppose there is Π ∈ * [ ] ∖ {Π }. Write ℛ = {Π [ ]}∈ , so that ℛ is a partition of . By Lemma 5, ℛ ⊆ Π. Note that ℛ ⊆ Π too. Since Π ̸= Π , we in fact have ℛ ⊂ Π and ℛ ⊂ Π . Hence Π ∖ ℛ and Π ∖ ℛ are distinct partitions of ∖ . Since a one-element set has a unique partition, ∖ must contain at least two elements.
Proof. “if”: First suppose (i) holds. Take ′ ∈ * [ ].
From ‖ ‖ ⊆ , ≈ ′ and Lemma 6 we get Π [ ] = Π ′ [ ]. Consequently, ′ |= E if |= 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 characteridecides 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 , ∈ Π [ ]. We Corollary 1. * [ ] = { } if and only if claim * [ ] |= ¬E . Indeed, take ′ ∈ * [ ]. 1. There is a collection {Γ}∈ ⊆ ℒ 0 such that for each , (i) , |= Γ; (ii) |= E Γ; (iii) Cn0 (Γ) is maximally consistent; and Then Π [ ] = Π ′ [ ′ ], so , ∈ Π ′ [ ′ ]. In particular, and difer on but are contained in the same cell in Π ′ . Hence ′ |= ¬E .
“only if”: We show the contrapositive. Suppose none of (i), (ii), (iii) hold. Then there is ∈ ‖ ‖ ∖ and ∈ ‖¬ ‖ ∖ . Let us define two worlds 1, 2 from by modifying ’s partition: Π 1 = {Π [ ]}∈ ∪ { ∖ }, Π 2 = {Π [ ]}∈ ∪ {{} | ∈ ∖ }.
2. For each each ∈ , | ∖ ⋃︀∈ Π [ ]| ≤ 1.
extent to which they reveal information about the actual world. We now turn to the methods which solve them.
ods under mild assumptions, before discussing the family of conditioning methods from Singleton and Booth [1].
Then 1, 2 ∈ * [ ] by Lemma 5. We claim that 1 |= ¬E but 2 |= E , which will show * [ ] does not decide E .
First, note that since , ∈/ , we have Π 1 [] = 6.1. A General Characterisation Π 1 [] = ∖ . Since and difer on but share the same partition cell, 1 |= ¬E . For sequences , , write ≡ if is obtained from
To show 2 |= E , take ∈ ‖ ‖. If ∈/ then by replacing each report ⟨, , ⟩ with ⟨, , ⟩, for some Π 2 [] = {} ⊆ ‖ ‖. Otherwise there is ∈ such ≡ . For ∈ N, let denote the -fold repetition of 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 [] = Π [ ] ⊆ ‖ ‖. Equivalence If ≡ then ( ) = ( ). Since ∈ ‖2‖[w]as⊆ ‖arbitr‖a.ryS,iwnceehtahvee srhevoewrnseΠinc2l[us]io=n ⋃︀∈‖ ‖ Π Repetition ( ) = ( ). always holds, this shows 2 |= E , and we are done.
Soundness ( ) ⊆ snd.
Proof of Theorem 4. The implication (
To show (
Let be any propositional formula with ‖ ‖ = {}. For methods satisfying these properties, we have a preWe show by Lemma 7 that * [ ] does not decide E . cise characterisation of truth-tracking, i.e. necessary and Indeed, all three conditions fail: ‖ ‖ ̸⊆ (since ∈/ ), suficient conditions for to solve * . First, some new ‖¬ ‖ ̸⊆ (since ∈ ‖¬ ‖ ∖ ) and no Π [ ] notation is required. Write ⪯ if for each ⟨, , ⟩ ∈ intersects with ‖ ‖ (otherwise ∈ Π [ ] ⊆ ). everything does, up to logical equivalence. Set there is ≡ such that ⟨, , ⟩ ∈ . That is, contains = snd ∖ ⋃︁ {︁ snd | ̸⪯ }︁
⊆ . has ⪯ Then ∈ if is sound for and any sound for
. In this sense contains all soundness statements for – up to equivalence – so can be seen as a finite version of a stream. Let us call a pseudo-stream for whenever ∈ .
etition and Soundness is truth-tracking if and only if it satisfies the following property.
Credulity , ̸|= S
=⇒ ( ), |= ¬S.
Before the proof, we comment on our interpretation of Credulity. It says that whenever ¬S is consistent with – those for which is a pseudo-stream – ( ) should imply ¬S . Since the number of sound statements decreases with increasing expertise, this is a principle of maximal trust: we should believe has the expertise to rule out in case , whenever this is consistent with . That is, some amount of credulity is required to find the truth. Our assumption that learning methods receive complete streams ensures that, if a source in fact lacks this expertise, they will eventually report and this belief can be be retracted. A stronger version of Credulity spells this out explicitly in terms of expertise: ∀, , , : , ̸|= ¬E =⇒ ( ), |= E.
(
Theorem 5 also shows truth-tracking cannot be performed deductively: the method ( ) = does not go beyond the mere information that each resnd, which port is sound, fails Credulity. Some amount of inductive or non-monotonic reasoning, as captured by Credulity, is necessary.
streams. First, pseudo-streams provide a way of accessing * via a finite sequence: is a cell in * whenever it and (ii) = * [ ].
Lemma 8. If ∈ , then (i) ′ ∈ snd if ⊑ ′; S we get ′, |= S .
From ′ ∈ This shows ⊑ ′.
snd and S ≡ ′ ∈ ′ ∈
Now suppose ⊑ ′ and let ⟨, , ⟩ ∈ . Then since ∈ ⊆
snd we have , |= S , and ⊑ ′ gives ′, |= S . Consequently ′ ∈
Now for (ii), first suppose ′ ∈ * [ ]. Then and ′ satisfy exactly the same soundness statements, so snd. also. Conversely, suppose ′ ∈ . Then snd, so (i) gives ′ ∈ and ∈ Hence ≈ ′, i.e. ′ ∈ * [ ].
snd, so (i) again gives ′ ⊑ .
⊑ ′. But we also have
∈ [] for all ≥ .
̂︀ ̂︀
̂︀ Proof. Let · be a function which selects a representative formula for each equivalence class of ℒ0/≡ , so that ≡ and ≡ implies is equal to ̂︀. Note that since and are also finite, there are only finitely many reports of the form completeness of for , we may take suficiently large so that , |= S ̂︀ implies ⟨, , ̂︀⟩ ∈ [], for all , , . Now, take ≥
. We need to show ∈ [].
Clearly ∈ sn[d], since is sound for . Suppose ∈
snd. We need to show ⪯ []. Indeed, take ⟨, , ⟩ ∈ . Then , |= S . Since S ≡ we have , |= S ̂︀. Hence ⟨, , ̂︀⟩ appears in [], and consequently in [] too. Since ≡ , this shows S ,
̂︀ ⟨, , ̂︀⟩. By ̂︀ for such that [ ] ≡ for all ∈ N.
Lemma 10. If ∈ and = | |, there is a stream formulas equivalent to Proof. First note that ∈ implies ̸ = ∅, so > 0. Since ℒ0 is countable, we may index the set of ℒ0 ∈ ℒ0 as { }∈N. Let be obtained from by replacing each report ⟨, , ⟩ with ⟨, , ⟩. Then ≡ obtained as the infinite concatenation 1 ∘ 2 ∘ 3 ∘ · · · . Let be the sequence [ ] = 1 ∘ · · · ∘
, and consequently [ ] ≡ .
of follows from ∈ ⊆ in is equivalent to some report in by construction.
For completeness, suppose , |= S . As in the proof of Lemma 8, considering the singleton sequence = ⟨, , ⟩, we get from ∈ that there is ≡
snd, since every report
= , so ⟨, , ⟩ ∈ , and thus ⟨, , ⟩ ∈ .
(
Theorem 5. We collect some useful properties of pseudo- (this is possible since is of positive finite length). Then quence = ⟨, , ⟩ we have ∈
snd. From ∈
we get ⪯ , i.e. there is ≡ such that ⟨, , ⟩ ∈ .
5We conjecture (
Proof. Suppose ∈ . For (i), first suppose
′ ∈ snd and , |= S . Considering the singleton se- such that ⟨, , ⟩ ∈ . Hence there is ∈ N such that such that , ̸|
= Lemma 8, ( ) ⊆
( ), |= ¬S .
which is less transparent as a postulate for learning methods, but easier to work with. isfies ̸= ∅.
Credulity if and only if ( ) ⊆ for all with Proof. “if”: Suppose , ̸|= S . Then there is ∈
= * [ ]. Thus every world in ( ) agrees with on soundness statements, so “only if”: Suppose there is some Lemma 8, this is equivalent to ≈ take ′ ∈ ( ).
We need to show ′ ∈ ; by ′. First suppose , |= S . Then ∈ implies there is ≡ such that ⟨, , ⟩ ∈ . By Soundness for , we have ′ ∈ ( ) ⊆
snd. Consequently ′, |= S and thus ′, |= S . This shows ⊑ ′. Now suppose , ̸|= S . Then , ̸|= S . By Credulity, ∈ , and ( ), |=
¬S . Hence ′, ̸|= ′ ⊑ . Thus ≈ ′ as required.
Lemma 8, [] = * [ ] for such . In particu. By Credulity and Lemma 11, we get “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 Repetition and Equivalence, ( ) = ( ) = ( [ ]).
large , we obtain ( ) ⊆ as required.
* [ ] = . Hence, going via some 6.2. Conditioning Methods
ods, proposed in [1] and inspired by similar methods in the belief change literature [22]. While our interpretation of input sequences is diferent – we read reporting is possible in case , whereas Singleton and
⟨, , ⟩ as can still be applied in our setting.
Conditioning methods operate by successively restricting a fixed
plausibility total preorder6 to the information 6A total preorder is a reflexive, transitive and total relation. snd ∘ ⊆ within
snd.
Definition 4. that S corresponding to each new report ⟨, , ⟩. In this paper, we take a report ⟨, , ⟩ to correspond to the fact holds in case ; this fits with our assumption throughout that sources only report sound statements.7 Thus, the worlds under consideration given a sequence are exactly those satisfying all soundness statements in , i.e. snd. Note that
snd represents the indefeasible knowledge given by : worlds outside nated and cannot be recovered with further reports, since snd are elimisnd. The plausibility order allows us to represent defeasible beliefs about the most plausible worlds
≤ is consistent. Moreover, ≤ tioning method ≤ is given by ≤ ( ) = min≤ snd.
For a total preorder ≤ on , the condiNote that since snd ̸= ∅ for all 8 and is finite, satisfies
Example 9. We recall two concrete choices of ≤ from 1. Set ≤ ′ if ( ) ≤ ( ′), where ∑︁ ∈ ( ) = −
|{ ∈ Prop | Π [] = ‖‖}|.
The most plausible worlds in this order are those in which source have as much expertise on the propositional variables as possible, on aggregate. We denote the corresponding conditioning method by vbc, standing for variable-based conditioning. 2. Set ≤ ′ if ( ) ≤ ( ′), where ( ) = − ∑︁ |Π |.
∈ This order aims to maximise the number of cells in each source’s partitions, thereby maximising the number of propositions on which they have expertise. Note that the propositional variables play no special role. We denote the corresponding conditioning operator by pbc, for partition-based conditioning.
A straightforward property of ≤ characterises truthtracking for conditioning methods. For a generic total preorder ≤ , let < denote its strict part.
Theorem 6. ≤ is truth-tracking if and only if
⊏ ′ =⇒ ∃ ′′ ≈ such that ′′ < ′. (
c pq ΠW i p¯q¯ pq¯ p¯q vW′ c pq ΠW′ i p¯q¯ pq¯ need to allow a “surrogate” world ′′ ≈ to take the ̸
= ∅.
Proof of Theorem 6. Write = ≤ . Since satisfies
Equivalence, Repetition and Soundness, we may use
Theorem 5. Furthermore, it is suficient by Lemma 11 to
show that (
“only if”: Suppose there is some ∈ , and let ′ ∈ ( ). We need to show ′ ∈ = * [ ], i.e. . ∈ .9
′. Since ′ ∈ ( ) ⊆
snd, Lemma 8 gives
⊑ ′. Suppose for contradiction that ̸≈
Then ⊏ ′. By (
snd: contradiction.
pseudo-stream.
and ′ shown in Fig. 3, where we assume
Prop = {, }, = {} and = {}. Then
⊏ ′ (e.g. by Lemma 1). Note that does not
have expertise on or in both and ′, so
( ) = ( ′) = 0. Moreover, ’s partition is
uniquely determined in * [ ] by Theorem 4, so
if ′′
is no ′′ ≈
≈
then ( ′′) = 0 also. That is, there
such that ′′ < ′. Hence (
Summary. In this paper we studied truth-tracking in the presence of non-expert sources. The model assumes sources report everything true up to their lack of expertise, i.e. all that they consider possible. We obtained precise characterisations of when truth-tracking methods can uniquely find the valuations and partitions of a world . We then gave a postulational characterisation of truth-tracking methods under mild assumptions, before looking specifically at the conditioning methods of
Limitations and future work.
Conceptually, the assumption that streams are complete is very strong. As seen in Example 3, completeness requires sources to give jointly inconsistent reports whenever Π[] contains more than just . Such reports provide informaand ¬
we know ¬E . To provide all sound reports sources must also have negative introspection over their own knowledge, i.e. they know when they do not know 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 reality, non-expert sources may have beliefs about the world, and may prefer to report only that which they believe. A source may even believe a sound report is false, since soundness only says the source does not know ¬ . For example, in Example 1 the doctor D may think it ′. tion about the source’s expertise: if reports both