# truthtracking_with_nonexpert_information_sources__f270a9e9.pdf Journal of Artificial Intelligence Research 81 (2024) 619-641 Submitted 07/2023; published 11/2024 Truth-tracking with Non-expert Information Sources Joseph Singleton joesingo@gmail.com Richard Booth boothr2@cardiff.ac.uk Cardiff University, UK We study what can be learned when receiving propositional reports from multiple nonexpert 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 couple of specific classes of methods from the belief change literature. 1. Introduction In this paper we study truth-tracking in the logical framework of Singleton and Booth (2022) for reasoning about multiple non-expert information sources. Broadly speaking, the goal of truth-tracking is to find the true state of the world given some input which describes it. In our case this involves finding the true state of some propositional domain about which the sources give reports, and finding the extent of the expertise of the sources themselves. The general problem of truth-tracking has been studied in various forms across many domains. Perhaps the oldest approach goes back to de Condorcet (1785), whose celebrated Jury Theorem states that a majority vote on a yes/no issue will yield the correct answer with probability approaching 1 as the number of voters tends to infinity, provided that each voter is more reliable than random choice. This result has since been generalised in many directions (e.g., by Grofman, Owen and Field (1983)). More widely, epistemic social choice (Elkind & Slinko, 2016) studies aggregation methods (e.g., voting rules) from the point of finding the correct result with high probability, where individual votes are seen as noisy approximations. Of particular relevance to our work is truth-tracking in judgement aggregation in social choice (Hartmann & Sprenger, 2012; Terzopoulou & Endriss, 2019), which also takes place in a logical framework. Belief merging has close links with judgement aggregation, and generalised jury theorems have been found here too (Everaere, Konieczny, & Marquis, 2010). In crowdsourcing, the problem of truth discovery (Li, Gao, Meng, Li, Su, Zhao, Fan, & Han, 2016) looks at how information from unreliable sources can be aggregated to find 2024 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0. Singleton & Booth the true value of a number of variables, and to find the true reliability level of the sources. This is close to our setting, since incoming information is not always assumed to be reliable, and information about the sources themselves is sought after. Work in this area combines empirical results (e.g., how well methods find the truth on test datasets for which true values are known) and theoretical guarantees, and is typically set in a probabilistic framework. On the other hand, formal learning theory (Jain, Osherson, Royer, & Sharma, 1999) offers a non-probabilistic view on truth-tracking, stemming from the framework of identification in the limit (Gold, 1967). In this paradigm a learner receives an infinite sequence of information step-by-step, such that all true information eventually appears in the sequence. The learner outputs a hypothesis at each step, and aims to stabilise on the correct hypothesis after some finite number of steps. This framework has been combined with belief revision theory (Kelly, Schulte, & Hendricks, 1997; Baltag, Gierasimczuk, & Smets, 2019), ontology learning (Eschenbach & Ozcep, 2010) and dynamic epistemic logic (Gierasimczuk, 2009a, 2009b, 2010; Baltag, Gierasimczuk, Ozg un, Sandoval, & Smets, 2019). See also (Gierasimczuk, 2023) for a recent overview. This is the approach we take, and in particular we adapt the truth-tracking setting of Baltag et al. (2019). We apply this to the logical framework of Singleton and Booth (2022). Briefly, this framework extends finite propositional logic with two new notions: that of a source having expertise on a formula, and a formula being sound for a source to report. Intuitively, expertise on φ means the source has the epistemic capability to distinguish between any pair of φ and φ states: they know whether or not φ holds in any state. A formula is sound for a source if it is true up to their lack of expertise. For example, if a source has expertise on φ but not ψ, then φ ψ is sound whenever φ holds, since we can ignore the ψ part (on which the source has no expertise). The resulting logical language therefore addresses both the ontic facts of the world, through the propositional part, and the epistemic state of the sources, via expertise and soundness. For the most part, formal learning theory supposes that all information received is true, and that all true information is eventually received.1 This is not a tenable assumption with non-expert sources: some sources may simply lack the expertise to know whether φ is true or false. Instead we make a different (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, since both φ and φ will look consistent to a source that lacks expertise to determine whether φ holds. Consequently, the input to our learning methods should be distinguished from the inputs to belief revision and belief merging methods (Alchourr on, G ardenfors, & Makinson, 1985; Konieczny & Pino P erez, 2002) also propositional formulas which represent beliefs of the reporting sources. 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. Example 1. Consider a medical scenario in which patient A is checked for conditions p and q. By examining A, a doctor D has expertise to determine whether A has at least one 1. But see Section 8.1 of Jain et al. (1999), who consider inaccurate data of various kinds, and Baltag et al. (2019), who consider erroneous reports provided that all errors are eventually corrected. Truth-tracking with Non-expert Information Sources of p or q, but cannot tell which one(s) without a blood test. A test is only available for p, however, so that the technician T performing the test has expertise on p but not q. Supposing A in fact suffers from q but not p, D considers each of p q, p q and p q possible, whereas T considers both p q and p q possible. Assuming both sources report all they consider possible, their combined expertise leaves p q as the only possibility. Intuitively, this means we can find the true values of p and q in this case. Now consider a patient B who suffers from both conditions. D cannot distinguish A and B, so will provide the same reports, and T considers both p q and p q possible. In this case T is more knowledgable than D since T considers fewer situations possible but we cannot narrow down the true value of q. Thus truth-tracking is only possible for p. The second patient still provides useful information, though, since together with the reports on A, T s lack of expertise tells us all the (in)distinctions between states they are able to make. Namely, T cannot distinguish between p q and p q. Thus we can find the truth about T s expertise. Contributions. This paper adapts learning-theoretic notions from formal learning theory - and in particular its intersection with belief revision (Baltag et al., 2019) - to handle non-expert information sources. We establish the limits of learning in this setting, and conditions under which one can learn the true facts of the world as well as the true extent of the expertise of the sources. We go on to characterise truth-tracking learning methods in terms of syntactic postulates, and look specifically at some methods previously introduced by Singleton and Booth (2022). Paper outline. In Section 2 we outline the logical framework for reasoning about expertise. Section 3 introduces the key concepts of truth-tracking and solvable questions. We characterise solvable questions in Section 4, and explore what they can reveal about the actual world in Section 5. Section 6 looks at learning methods themselves, and characterises truth-tracking methods. We conclude in Section 7. 2. Preliminaries In this section we recall the logical framework of Singleton and Booth (2022) for reasoning with non-expert sources. Syntax. Let Prop be a finite set of propositional variables, and let L0 denote the propositional language generated from Prop. We use L0 to model the domain underlying the truth-tracking problem; it describes the ontic facts of the world, irrespective of the expertise of the sources. Formulas in L0 will be denoted by lower-case Greek letters (φ, ψ, etc). Let S be a finite set of sources. Here we make an important change to the setup of Singleton and Booth (2022): we do not include a special, completely reliable source. Indeed, having access to a completely reliable source of information would somewhat trivialise the truth-tracking problem, at least as far as learning ontic facts is concerned. The language L extends L0 with expertise and soundness formulas for each source i S, and is defined by the following grammar: Φ ::= φ | Eiφ | Siφ | Φ Φ | Φ, Singleton & Booth Figure 1: Example of a world W, which formalises Example 1. Here Prop = {p, q}, S = {D, T} and C = {A, B}. for φ L0 and i S. Formulas in L will be denoted by upper-case Greek letters (Φ, Ψ etc). Other logical connectives ( , , ) are introduced as abbreviations. We read Eiφ as i has expertise on φ , and Siφ as φ is sound for i . Note that we restrict the expertise and soundness formulas to propositional arguments, and do not consider nested formulas such as Ei Sjφ. Semantics. Let V denote the set of propositional valuations over Prop. We represent the expertise of a source i with a partition Πi of V. Intuitively, this partition represents the distinctions between states the source is able to make: valuations in the same cell in Πi are indistinguishable to i, whereas i is able to tell apart valuations in different cells. We say i has expertise on φ iff i can distinguish all φ states from φ states, and φ is sound for i if the actual state (as defined below) is indistinguishable from some φ state. Let C be a finite set of cases, thought of as independent concrete instances of the domain of interest. For example, the cases in Example 1 are the patients A and B. We consider the expertise of sources to be fixed across all cases. A world is a pair W = {vc}c C, {Πi}i S , where vc V is the actual valuation for case c; Πi 2V is a partition representing the expertise of i. Let W denote the set of worlds. Note that W is finite, since V, C and S are. Note it is possible in a world W to have vc1 = vc2 for c1 = c2. For φ L0, write φ V for the models of φ, and write v φ iff v φ . The consequences of a set Γ L0 is denoted by Cn0 (Γ), and we write Γ φ if φ Cn0 (Γ). For a partition Π, let Π[v] denote the unique cell in Π containing v, and write Π[U] = S v U Π[v] for U V. For brevity, we write Π[φ] instead of Π[ φ ]. We evaluate L formulas with respect to a world W and a case c as follows: W, c |= φ vc φ W, c |= Eiφ Πi[φ] = φ W, c |= Siφ vc Πi[φ], Truth-tracking with Non-expert Information Sources where the clauses for conjunction and negation are as standard. The semantics follows the intuition outlined above: Eiφ holds when Πi separates the φ states from the φ states, and Siφ holds when vc is indistinguishable from some φ state. Thus, Siφ means φ is true up to the expertise of i: if we weaken φ according to i s expertise, the resulting formula (with models Πi[φ]) 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 Πi, we obtain a (multi-agent) S5 Kripke model, and have the correspondences Siφ Ki φ and Eiφ A(φ Kiφ), where Ki denotes knowledge of source i and A is the universal modality (Goranko & Passy, 1992). (Aφ is true at a state iff φ is true at all states.) This gives expertise and soundness precise interpretations in terms of knowledge; we refer the reader to (Singleton & Booth, 2022; Singleton, 2021) for further discussion. Example 2. Take W from Fig. 1, which formalises Example 1. Then W, c |= ED(p q) for all c C, since p q is a cell in ΠD. We also have W, A |= p SDp, i.e., patient A does not suffer from condition p, but it is consistent with D s expertise that they do. We write W, c |= Γ, for a set of formulas Γ L, if W, c |= Φ for all Φ Γ. For a set S W, we write S, c |= Φ iff W, c |= Φ for all W S. Reports. A report is a triple i, c, φ , where i S, c C and φ L0 with φ . In this paper, we interpret such triples as source i reporting that φ is possible in case c. An input sequence σ is a finite sequence of reports. A method L maps each input sequence σ to a set of worlds L(σ) W, called the conjecture of L on σ.2 We say L implies S W on the basis of σ if L(σ) S. L is consistent if L(σ) = for all input sequences σ. 3. Truth-Tracking We adapt the framework for truth-tracking from (Gierasimczuk, 2010; Baltag, Gierasimczuk, & Smets, 2015; Baltag et al., 2019), which finds its roots in formal learning theory. In this framework, a learning method receives increasing initial segments of an infinite sequence called a stream which enumerates all (and only) the true propositions observable at the actual world. Truth-tracking requires the method to eventually find the actual world (or some property thereof), given any stream. As mentioned in the introduction, in our setting we 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, but such false reports only arise due to lack of expertise of the corresponding source.3 Moreover, all sound reports will eventually arise. Since Siφ means φ is possible from the point of view of i s expertise, we can view a stream as each source sharing all that they consider possible for each case c C. In particular, a non-expert source may report both φ and φ for the same case. 2. We depart from the original framework of Singleton and Booth (2022) here by taking a semantic view of belief change operators, with the output a set of worlds instead of formulas. 3. Alternatively, we can consider statements of the form φ is sound for i in case c as a higher-order proposition ; a stream then enumerates all true propositions of this kind. Singleton & Booth Definition 1. An infinite sequence of reports ρ is a stream for W iff for all i, c, φ4: i, c, φ ρ W, c |= Siφ. We refer to the left-to-right implication as soundness of ρ for W, and the right-to-left direction as completeness. Note that every world W has some stream: the set { i, c, φ | W, c |= Siφ} is countable, so can be indexed by N to form a stream. For n N we let ρn denote the n-th report in ρ, and write ρ[n] for the finite initial segment of ρ of length n. Example 3. Consider W from Fig. 1 and case A. From the point of view of D s expertise, the actual valuation could be pq, pq, p q. Consequently, in a stream for W, D will report p, p, q, q, p q, and so on. A report that D will not give is (p q), since D has expertise to know this is false. Note that v A and v B are indistinguishable to D, so the reports of D in any stream will be the same for both cases. In contrast, T can distinguish the two cases, and will report p in case A but not in B, and p in case B but not in A. In line with the notion originally given by Baltag et al. (2015) we define a question Q to be a partition of W. That is, a question is a set of disjoint answers A Q, with each world W appearing in a unique cell Q[W] the correct answer at W. Example 4. We consider some example questions. 1. Any formula Φ L and case c defines a question QΦ,c, whose two cells consist of the worlds satisfying Φ, respectively Φ, in case c. Intuitively, this question asks whether Φ is true or false in case c. 2. The finest question Q = {{W} | W W} asks: what is the actual world? 3. More generally, for any set X and function f : W X, the equivalence relation given by W f W iff f(W) = f(W ) defines a question Qf. In this way any data associated with a world gives rise to a question. For example, if f(W) = {i S | ΠW i [p] = p } we ask for the set of sources with expertise on p; if f(W) = |{c C | W, c |= p}| we ask for the number of cases where p holds, etc. In fact, all questions are of this form: given Q we may define f : W Q by f(W) = Q[W]; then Qf = Q. A method solves Q if it eventually implies the correct answer when given any stream. Definition 2. A method L solves a question Q if for all worlds W and all streams ρ for W, there is n N such that L(ρ[m]) Q[W] for all m n. A question Q is solvable if there is some consistent method L which solves Q. Note that we do not require W L(ρ[m]). Solvability can be also expressed in terms of eliminating incorrect worlds. 4. By abuse of notation, we use set membership for a sequence ρ to mean that the element appears somewhere in the sequence. Truth-tracking with Non-expert Information Sources Proposition 1. A method L solves Q if and only if for all W, all streams ρ for W, and all W / Q[W], there is n W N such that W / L(ρ[m]) for all m n W . Proof. if : Taking n = max{n W | W / Q[W]}, which exists since W is finite, L(ρ[m]) Q[W] for m n. only if : Taking n from the definition of L solving Q, we may simply take n W = n for all W / Q[W]. 4. Characterising Solvable Questions In this section we explore solvability of questions, finding 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. Following Baltag et al. (2015), questions are partially ordered by partition refinement: Q Q iff each A Q can be written as a union of answers from Q. Equivalently, Q[W] Q [W] for all W. This can be interpreted as a difficulty ordering: if Q Q then each answer of Q is just a disjunction of answers of Q, and thus Q is easier than Q. Naturally, if Q is solvable then so too is any easier question. Proposition 2. If Q is solvable and Q Q , then Q is solvable. Proof. The method which solves Q also solves Q . Since question solving is based on streams of sound reports, worlds satisfying the same soundness statements cannot be distinguished by any solvable question. To formalise this, define a preorder on W by W W i, c, φ : (W, c |= Siφ = W , c |= Siφ). Thus, W W iff any report sound for W is also sound for W . We denote by and the strict and symmetric parts of , respectively. Lemma 1. W W if and only if for all i S and c C, ΠW i [v W c ] ΠW i [v W c ]. Proof. if : Suppose W, c |= Siφ. Then v W c ΠW i [φ], so there is u φ such that v W c ΠW i [u]. Consequently u ΠW i [v W c ] ΠW i [v W c ], which means v W c ΠW i [u] ΠW i [φ]. Hence W , c |= Siφ. This shows W W . only if : Let u ΠW i [v W c ]. Let φ be any formula with φ = {u}. Then W, c |= Siφ, so W W gives W , c |= Siφ, i.e., v W c ΠW i [u], so u ΠW i [v W c ]. Hence ΠW i [v W c ] ΠW i [v W c ]. Note that Πi[vc] is the set of valuations indistinguishable from the actual valuation in case c, for source i. In light of Lemma 1, we can interpret W W as saying that all sources are more knowledgeable in each case c in world W than in W . However, W W does not say anything about the partition cells not containing some vc. Proposition 3. The following are equivalent. 1. W and W have exactly the same streams. Singleton & Booth 3. For all i S and c C, ΠW i [v W c ] = ΠW i [v W c ]. Proof. (2) and (3) are easily seen to be equivalent in light of Lemma 1. To show (1) is equivalent to (2), first suppose W and W have the same streams, and suppose W, c |= Siφ. Taking an arbitrary stream ρ for W, completeness gives i, c, φ ρ. But ρ is a stream for W too, and soundness gives W , c |= Siφ. Hence W W . A symmetrical argument shows W W. On the other hand, if W W then W and W satisfy exactly the same soundness statements, so it is clear that any sequence ρ is a stream for W iff it is a stream for W . Since it will play a special role throughout, we denote by Q the question formed by the equivalence relation . Then Q [W] is the set of W with W W . Since no solvable question can distinguish -equivalent worlds, we have the following. Lemma 2. If Q is solvable then Q Q. Proof. Suppose L is a consistent method solving Q. We show Q [W] Q[W] for all W. Indeed, let W Q [W]. Then W W. Taking any stream ρ for W, there is n such that L(ρ[m]) Q[W] for m n. On the other hand ρ is also a stream for W by Proposition 3, so there is n such that L(ρ[m]) Q[W ] for m n . Setting m = max{n, n } and using the fact that L is consistent, we find L(ρ[m]) Q[W] Q[W ]. Since Q is a partition, this means Q[W] = Q[W ], i.e., W Q[W]. So, any solvable question is coarser than Q . Fortunately, Q itself is solvable since we work in a finite framework. For a sequence σ, write X snd σ for the set of worlds W such that W, c |= Siφ for all i, c, φ σ. To solve Q it suffices to conjecture the -minimal worlds in X snd σ . Proposition 4. Q is solvable. Proof. Set L(σ) = min X snd σ if X snd σ = , and L(σ) = W otherwise (where W min X snd σ iff W X snd σ and there is no W X snd σ with W W). Note that L is consistent since W is finite and non-empty. We show that L solves Q by Proposition 1. Take any world W and a stream ρ. First note that, by soundness of ρ, W X snd ρ[n] for all n N, so we are always in the first case in the definition of L. Take W / Q [W]. Then W W . Consider two cases: Case 1: W W . By definition, there are i, c, φ such that W, c |= Siφ but W , c |= Siφ. By completeness of ρ for W, there is n such that ρn = i, c, φ . Consequently W / X snd ρ[m] for all m n. Since L(ρ[m]) X snd ρ[m], we have W / L(ρ[m]) as required. Case 2: W W . Since W X snd ρ[n] for all n, W can never be -minimal. Thus W / L(ρ[n]) for all n. Note that these cases are exhaustive since W W . This completes the proof. Putting Propositions 2 and 4 and Lemma 2 together we obtain a characterisation of solvable questions. Truth-tracking with Non-expert Information Sources Theorem 1. Q is solvable if and only if Q Q. Given this result, Q is the only question that really matters: any other question is either unsolvable or formed by coarsening Q . With this in mind, we make the following definition. Definition 3. A method is truth-tracking if it solves Q . Example 5. We refer back to the questions of Example 4. 1. The question Qφ,c, for any propositional formula φ L0, 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 W1, W2 where no source has any expertise (i.e., ΠWk i = {V} for k {1, 2}) but where v W1 c φ, v W2 c φ. Then W1 W2 (e.g., by Proposition 3) but W1 / Qφ,c[W2]. Similarly, QEiφ,c is solvable iff either φ is a tautology or contradiction, when |Prop| 2. 2. The finest question Q is not solvable, since there are always distinct W, W with W W . 3. In general, Qf is solvable iff W W implies f(W) = f(W ), i.e., iff f takes a unique value on each equivalence class of . 5. What Information can be Learned? Solving a question Q has a global character: we must find the correct answer Q[W] starting from any world W. 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 W, what can we learn about W via truthtracking methods? Concretely, what properties of W are uniquely defined across Q [W]? For instance, in Example 1 we took this local perspective and argued that in the particular world W modelling the medical scenario, it is possible to find the true value of q for patient A but not for B. The results and examples of this section will formalise this informal argument. There are two components of a world that need to be identified: the cases (i.e., the valuations) and the expertises (i.e., the partitions). The former will be addressed in Section 5.1, the latter in Section 5.2. The two will be combined in Section 5.3. In general, the extent to which one can learn depends on W. 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 valuations is possible, since if ΠW i = {V} for all i S then W W for every other W such that ΠW i = {V} for all i S. On the other hand if all sources 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 Q [W] contains only W; starting in such a world, truth-tracking methods are able to find the true world exactly. In what follows, say S W decides Φ in case c iff either S, c |= Φ or S, c |= Φ. That is, the truth value of Φ in case c is unambiguously defined across the worlds in S. If Φ does not depend on the case (e.g., if Φ = Eiφ) we simply say S decides Φ. Singleton & Booth 5.1 Valuations We start by considering when Q [W] decides a propositional formula φ in case c, i.e., when truth-tracking methods are guaranteed to successfully determine whether or not φ holds in the actual world. This leads to a precise characterisation of when Q [W] contains a unique valuation in case c, so that v W c can be found exactly. We need a notion of group expertise. For S S and Γ L0, write W |= ES Γ if for each ψ Γ there is i S such that W |= Eiψ. Then the group S has expertise on Γ in a collective sense, even if no single source has expertise on all formulas in Γ. We have that φ is decided if S have group expertise on a set of true formulas Γ L0 such that either Γ φ or Γ φ. Theorem 2. Q [W] decides φ L0 in case c if and only if there is Γ L0 such that (i) W, c |= Γ; (ii) W |= ESΓ; and (iii) either Γ φ or Γ φ. Q [W] decides all propositional formulas and thus determines the c-valuation v W c exactly iff S have group expertise on a maximally consistent set of true formulas. For S W and c C, write VS c = {v W c | W S} for the c-valuations appearing in S. Theorem 3. The following are equivalent. 1. VQ [W] c = {v W c }. 2. Q [W] decides φ in case c, for all φ L0. 3. There is Γ L0 such that (i) W, c |= Γ; (ii) W |= ESΓ; and (iii) Cn0 (Γ) is a maximally consistent set. We illustrate Theorem 3 with an example. Example 6. Consider W from Fig. 1. Then one can show VQ [W] A = { pq} = {v W A }, and VQ [W] B = {pq, p q} = {v W B }. That is, W s A valuation is uniquely determined by truthtracking methods, but its B valuation is not: there is some world W W whose B-valuation differs from W s. This matches the informal reasoning in Example 1, in which patient A could be successfully diagnosed on both p and q but B could not. Formally, take Γ = {p q, p}. Then W, A |= Γ, W |= ESΓ (since D has expertise on p q and T has expertise on p), and Cn0 (Γ) = Cn0 ( p q), which is 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. The remainder of this section proves Theorems 2 and 3. Lemma 3. For W W , i S and φ L0, W, c |= φ Eiφ = W , c |= φ. Proof. From W, c |= φ we have v W c φ , so ΠW i [v W c ] ΠW i [φ]. But W, c |= Eiφ means ΠW i [φ] = φ , so in fact ΠW i [v W c ] φ . Now using W W , we find v W c ΠW i [v W c ] = ΠW i [v W c ] φ . Hence W , c |= φ. Truth-tracking with Non-expert Information Sources Lemma 4. VQ [W] c = T i S ΠW i [v W c ]. Proof. : Suppose u VQ [W] c . Then there is W W such that u = v W c . Let i S. Then u ΠW i [v W c ] = ΠW i [v W c ] by Proposition 3, as required. : Suppose u T i S ΠW i [v W c ]. Let W be the world obtained from W by setting the c-valuation to u, keeping partitions and other valuations the same. We need to show W W. We do so via Proposition 3, by showing condition (3). Take any i S and d C. If d = c then v W d = v W d ; since partitions are the same in W as in W we get ΠW i [v W d ] = ΠW i [v W d ]. For c = d, note ΠW i [v W c ] = ΠW i [u]. By assumption u ΠW i [v W c ], so ΠW i [u] = ΠW i [v W c ]. Hence ΠW i [v W c ] = ΠW i [v W c ] as required. Proof of Theorem 2. if : Take W Q [W]. Note that since W, c |= Γ and W, c |= ESΓ, we may apply Lemma 3 to each formula in Γ in turn to find W , c |= Γ. Now, if W, c |= φ then we must have Γ φ, so W , c |= φ too. Otherwise W, c |= φ, so we must have Γ φ and W , c |= φ. This shows W , c |= φ if and only if W, c |= φ. Since W Q [W] was arbitrary, Q [W] decides φ in case c. only if : Suppose Q [W] decides φ in case c. For each i S, take some ψi L0 such that ψi = ΠW i [v W c ]. Then W |= Eiψi. Set Γ = {ψi}i S. Clearly W, c |= Γ and W |= ESΓ. Now, take any u Γ . By Lemma 4, Γ = T i S ΠW i [v W c ] = VQ [W] c . Hence there is some W Q [W] such that u = v W c . But Q [W] decides φ in case c, so W , c |= φ iff W, c |= φ. Thus u φ iff W, c |= φ. Since u Γ was arbitrary, we have Γ φ if W, c |= φ, and Γ φ otherwise. Proof of Theorem 3. (1) implies (2): If W Q [W] then W and W share the same cvaluation by (1), so clearly W, c |= φ iff W , c |= φ, for any φ. Hence Q [W] decides φ in case c. (2) implies (1): Clearly v W c VQ [W] c . Suppose u VQ [W] c . Then there is W Q [W] such that u = v W c . Let p Prop. Since W, W Q [W] and Q [W] decides p in case c, we have u p iff v W c p. Since p was arbitrary, u = v W c . (2) implies (3): Applying Theorem 2 to each φ L0, there is a set Γφ L0 such that W, c |= Γφ, W |= ESΓφ, and either Γφ φ or Γφ φ. Set Γ = S φ L0 Γφ. Clearly W, c |= Γ so Γ is consistent and W |= ESΓ. To show Cn0 (Γ) is maximally consistent, suppose φ / Cn0 (Γ). From monotonicity of classical consequence and Γφ Γ, we get φ / Cn0 (Γφ). Hence Γφ φ, and Γ φ too. This means Cn0 (Γ) {φ} is inconsistent, and we are done. (3) implies (2): Take φ L0. Then we may apply Theorem 2 with Γ from (3) noting that the maximal consistency property ensure either Γ φ or Γ |= φ to see that Q [W] decides φ in case c. 5.2 Source Partitions We now consider when Q [W] decides an expertise formula Eiφ, i.e., when truth-tracking methods are guaranteed to successfully determine the expertise of source i. This leads to a precise characterisation of when Q [W] contains a unique partition for source i. We apply the analysis of the previous section to the set of source partitions {ΠW i }i S. For S W and i S, write PS i = {ΠW i | W S} for the i-partitions appearing in S. When S = Q [W], Singleton & Booth Figure 2: World W from Example 7. Note that for brevity we do not label the valuations. these are exactly those partitions which agree with ΠW i at each valuation v W c . In other words: Lemma 5. Π PQ [W] i if and only if {ΠW i [v W c ]}c C Π. Proof. if : Suppose {ΠW i [v W c ]}c C Π. Let W be obtained from W by setting i s partition to Π, keeping valuations and other source partitions the same. We claim W W. Indeed, take any j S and c C. If j = i then ΠW j = ΠW i ; since valuations are the same we get ΠW j [v W c ] = ΠW j [v W c ]. For j = i, note that since ΠW i [v W c ] Π by assumption, and v W c ΠW i [v W c ], we have Π[v W c ] = ΠW i [v W c ]. By construction of W , this means ΠW i [v W c ] = Π[v W c ] = ΠW i [v W c ]. By Proposition 3, W W. Hence Π PQ [W] i . only if : This is clear from Proposition 3. Example 7. Suppose |Prop| = 3, C = {c1, c2} and i S. Consider a world W whose ipartition is shown in Fig. 2. By Lemma 5, a partition Π appears as ΠW i for some W W 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 |PQ [W] i | = 5. Example 7 hints that if the cells containing the valuations v W c cover the whole space of valuations V, or just omit a single valuation, then i s partition is uniquely defined in Q [W]. That is, truth-tracking methods can determine the full extent of i s expertise if the actual world is W. Indeed, we have the following analogue of Theorem 3 for partitions. Theorem 4. The following are equivalent. 1. PQ [W] i = {ΠW i }. 2. Q [W] decides Eiφ for all φ L0. 3. |V \ R| 1, where R = S c C ΠW i [v W c ]. Note that R = S c C ΠW i [v W c ] is the set of valuations indistinguishable from the actual state at some case c. Clause 3 of Theorem 4 says this set needs to essentially cover the whole space V, omitting at most a single point. In this sense, it is easier to find ΠW i uniquely Truth-tracking with Non-expert Information Sources when i has less expertise, since the cells ΠW i [v W c ] will be larger. In the extreme case where i has total expertise, i.e., ΠW i = {{v} | v V}, we need at least 2|Prop| 1 cases with distinct valuations in order to find ΠW i exactly. Example 8. In Example 7 we have already seen a world W for which PQ [W] i does not contain a unique partition. For a positive example, consider the world W from Fig. 1. Then V \ RD = { p q} and V \ RT = , so both the partitions of D and T can be found uniquely by truth-tracking methods. The remainder of this section proves Theorem 4. Lemma 6. Let i S and U V. Then U S c C ΠW i [v W c ] and W W implies ΠW i [U] = ΠW i [U]. Proof. It suffices to show that for all u U we have ΠW i [u] = ΠW i [u], since by definition Π[U] = S u U Π[u]. Let u U. Then there is c C such that u ΠW i [v W c ]. Hence ΠW i [u] = ΠW i [v W c ]. But since W W , ΠW i [v W c ] = ΠW i [v W c ]. This means u ΠW i [v W c ], so ΠW i [u] = ΠW i [v W c ] = ΠW i [v W c ] = ΠW i [u], as required, Lemma 7. Q [W] decides Eiφ if and only if, writing R = S c C ΠW i [v W c ], either (i) φ R; (ii) φ R; or (iii) there is some c C such that ΠW i [v W c ] intersects with both φ and φ . Proof. if : First suppose (i) holds. Take W Q [W]. From φ R, W W and Lemma 6 we get ΠW i [φ] = ΠW i [φ]. Consequently, W |= Eiφ iff W |= Eiφ. Since W was arbitrary, either all worlds in Q [W] satisfy Eiφ, or all do not. Hence Q [W] decides Eiφ. If (ii) holds, a similar argument shows that Q [W] decides Ei φ. But it is easily checked that Eiφ Ei φ, so Q [W] also decides Eiφ. Finally, suppose (iii) holds. Then there is c C and u φ , v φ such that u, v ΠW i [v W c ]. We claim Q [W] |= Eiφ. Indeed, take W Q [W]. Then ΠW i [v W c ] = ΠW i [v W c ], so u, v ΠW i [v W c ]. In particular, u and v differ on φ but are contained in the same cell in ΠW i . Hence W |= Eiφ. only if : We show the contrapositive. Suppose none of (i), (ii), (iii) hold. Then there is u φ \ R and v φ \ R. Let us define two worlds W1, W2 from W by modifying i s partition: ΠW1 i = {ΠW i [v W c ]}c C {V \ R}, ΠW2 i = {ΠW i [v W c ]}c C {{w} | w V \ R}. Then W1, W2 Q [W] by Lemma 5. We claim that W1 |= Eiφ but W2 |= Eiφ, which will show Q [W] does not decide Eiφ. First, note that since u, v / R, we have ΠW1 i [u] = ΠW1 i [v] = V \ R. Since u and v differ on φ but share the same partition cell, W1 |= Eiφ. To show W2 |= Eiφ, take w φ . If w / R then ΠW2 i [w] = {w} φ . Otherwise there is c C such that w ΠW i [v W c ]. Thus ΠW i [v W c ] intersects with φ . Since (iii) does not hold, this in fact implies ΠW i [v W c ] φ , and consequently ΠW2 i [w] = ΠW i [v W c ] φ . Since w φ was arbitrary, we have shown ΠW2 i [φ] = S w φ ΠW2 i [w] φ . Since the reverse inclusion always holds, this shows W2 |= Eiφ, and we are done. Singleton & Booth Proof of Theorem 4. The implication (1) to (2) is clear since if W Q [W] then ΠW i = ΠW i by (1), so W |= Eiφ iff W |= Eiφ, and thus Q [W] decides Eiφ. To show (2) implies (3) we show the contrapositive. Suppose |V \ R| > 1. Then there are distinct u, v V \ R. Let φ be any propositional formula with φ = {u}. We show by Lemma 7 that Q [W] does not decide Eiφ. Indeed, all three conditions fail: φ R (since u / R), φ R (since v φ \ R) and no ΠW i [v W c ] intersects with φ (otherwise u ΠW i [v W c ] R). Finally, for (3) implies (1) we also show the contrapositive. Suppose there is Π PQ [W] i \ {ΠW i }. Write R = {ΠW i [v W c ]}c C, so that R is a partition of R. By Lemma 5, R Π. Note that R ΠW i too. Since Π = ΠW i , we in fact have R Π and R ΠW i . Hence Π \ R and ΠW i \ R are distinct partitions of V \ R. Since a one-element set has a unique partition, V \ R must contain at least two elements. 5.3 Learning the Actual World Exactly Putting Theorems 3 and 4 together we obtain a precise characterisation of when W can be found exactly by truth-tracking methods, i.e when Q [W] = {W}. Corollary 1. Q [W] = {W} if and only if 1. There is a collection {Γc}c C LC 0 such that for each c, (i) W, c |= Γc; (ii) W |= ESΓc; (iii) Cn0 (Γc) is maximally consistent; and 2. For each each i S, |V \ S c C ΠW i [v W c ]| 1. 6. Truth-Tracking Methods So far we have focussed on solvable questions, and the extent to which they reveal information about the actual world. We now turn to the methods which solve them. We give a general characterisation of truth-tracking methods under mild assumptions, before discussing the families of conditioning and score-based methods from Singleton and Booth (2022). 6.1 A General Characterisation For sequences σ, δ, write σ δ iff δ is obtained from σ by replacing each report i, c, φ with i, c, ψ , for some ψ φ. For k N, let σk denote the k-fold repetition of σ. Consider the following properties which may hold of a learning method L. Equivalence If σ δ then L(σ) = L(δ). Repetition L(σk) = L(σ). Soundness L(σ) X snd σ . Equivalence says that L should not care about the syntactic form of the input. Repetition says that the output from L should not change if each source repeats their reports k times. Note this is a weaker requirement than saying that L should be invariant under duplication of some reports in σ. In that case the number of times a source i repeats a particular report Truth-tracking with Non-expert Information Sources could, conceivably, be taken as an indicator of the confidence that i has in that report, and so the duplication represents extra context that we may want L to take into account. Soundness says that all reports in σ are conjectured to be sound.5 For methods satisfying these properties, we have a precise characterisation of truthtracking, i.e., necessary and sufficient conditions for L to solve Q . First, some new notation is required. Write δ σ iff for each i, c, φ δ there is ψ φ such that i, c, ψ σ. That is, σ contains everything δ does, up to logical equivalence. Set Tσ = X snd σ \ [ n X snd δ | δ σ o Then W Tσ iff σ is sound for W and any δ sound for W has δ σ. In this sense σ contains all soundness statements for W up to equivalence so can be seen as a finite version of a stream. Let us call σ a pseudo-stream for W whenever W Tσ. Theorem 5. A method L satisfying Equivalence, Repetition and Soundness is truthtracking if and only if it satisfies the following property. Credulity If Tσ, c |= Siφ then L(σ), c |= Siφ. Before the proof, we comment on our interpretation of Credulity. It says that whenever Siφ is consistent with Tσ those W for which σ is a pseudo-stream L(σ) should imply Siφ. Since the number of sound statements decreases with increasing expertise, this is a principle of maximal trust: we should believe i has the expertise to rule out φ in case c, whenever this is consistent with Tσ. 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: If Tσ, c |= Eiφ then L(σ), c |= Eiφ. (1) The above property (1) implies Credulity in the presence of Soundness, and is thus a sufficient condition for truth-tracking (when also taken with Equivalence and Repetition).6 Theorem 5 also shows truth-tracking cannot be performed deductively: the method L(σ) = X snd σ , which does not go beyond the mere information that each report is sound, fails Credulity. Some amount of inductive or non-monotonic reasoning, as captured by Credulity, is necessary. Example 9. For a simple example of Credulity assume Prop = {p}, S = {i} and C = {c}. In this case V contains just two possible valuations vp and v p according to whether p is true or false, respectively. There are also just two possible partitions for i, namely ΠE = {{vp}, {v p}} and Π E = {V} according to whether i is able to distinguish between the two possible valuations or not. Thus W contains four possible worlds W1 = vp, ΠE , W2 = vp, Π E , W3 = v p, ΠE and W4 = v p, Π E . There are just three distinct reports, 5. Note that we are using the term soundness in three different, but related, ways in this paper. This usage refers to a property of learning methods, in contrast to our earlier usages as (i) a property of a formula being sound for a source to report, and (ii) a stream ρ being sound for a world W. 6. We conjecture (1) is strictly stronger than Credulity. Singleton & Booth up to logical equivalence, that i can possibly give about c, namely p, p and the tautological p p. Let s assume i reports the first and the third of these, i.e., σ = ( i, c, p , i, c, p p ). We have X snd σ = {W1, W2, W4}. The missing report i, c, p is sound for W2 and W4 but not for W1. Thus Tσ = {W1} and so Tσ, c |= Si p. Therefore Credulity says we should have L(σ), c |= Si p, which means that, on the basis of just σ, we should assume i is expert on p. The rest of this section works towards the proof of Theorem 5. We collect some useful properties of pseudo-streams. First, pseudo-streams provide a way of accessing Q via a finite sequence: Tσ is a cell in Q whenever it is non-empty. Lemma 8. If W Tσ, then (i) W X snd σ iff W W ; and (ii) Tσ = Q [W]. Proof. Suppose W Tσ. For (i), first suppose W X snd σ and W, c |= Siφ. Considering the singleton sequence δ = i, c, φ we have W X snd δ . From W Tσ we get δ σ, i.e., there is ψ φ such that i, c, ψ σ. From W X snd σ and Siφ Siψ we get W , c |= Siφ. This shows W W . Now suppose W W and let i, c, φ σ. Then since W Tσ X snd σ we have W, c |= Siφ, and W W gives W , c |= Siφ. Consequently W X snd σ . Now for (ii), first suppose W Q [W]. Then W and W satisfy exactly the same soundness statements, so W Tσ also. Conversely, suppose W Tσ. Then W X snd σ , so (i) gives W W . But we also have W Tσ and W X snd σ , so (i) again gives W W. Hence W W , i.e., W Q [W]. We can now show that property (1) implies Credulity together with Soundness. Proposition 5. Suppose L satisfies Soundness and property (1). Then L satisfies Credulity. Proof. Suppose Tσ, c |= Siφ. By assumption, there is some W Tσ such that W, c |= Siφ. Take some W L(σ). We need to show that W , c |= Siφ. Now, from W, c |= Siφ we get ΠW i [v W c ] φ = . Taking ψ such that ψ = ΠW i [v W c ], we have ψ φ = and W, c |= Eiψ. Thus Tσ, c |= Eiψ, so property (1) gives L(σ), c |= Eiψ. Since W L(σ), we get W , c |= Eiψ, i.e., ΠW i [ψ] = ψ . On the other hand, from Soundness we have L(σ) X snd σ , so W X snd σ . Since W Tσ, Lemma 8 gives W W , and so ψ = ΠW i [v W c ] ΠW i [v W c ] by Lemma 1. Now since ψ is a subset of the cell ΠW i [v W c ], its expansion under ΠW i is equal to this cell, i.e., ΠW i [ψ] = ΠW i [v W c ]. But we showed above that ΠW i [ψ] = ψ . Hence ΠW i [v W c ] = ψ . In particular, ΠW i [v W c ] φ = , and W , c |= Siφ as required. The next two results show that initial segments of streams are (eventually) pseudostreams, and that any pseudo-stream gives rise to a stream. Lemma 9. If ρ is a stream for W, there is n such that W Tρ[m] for all m n. Proof. Let b be a function which selects a representative formula for each equivalence class of L0/ , so that φ bφ and φ ψ implies bφ is equal to bψ. Note that since Prop is finite, and since S and C are also finite, there are only finitely many reports of the form i, c, bφ . By completeness of ρ for W, we may take n sufficiently large so that W, c |= Si bφ implies Truth-tracking with Non-expert Information Sources i, c, bφ ρ[n], for all i, c, φ. Now, take m n. We need to show W Tρ[m]. Clearly W X snd ρ[m], since ρ is sound for W. Suppose W X snd δ . We need to show δ ρ[m]. Indeed, take i, c, φ δ. Then W, c |= Siφ. Since Siφ Si bφ, we have W, c |= Si bφ. Hence i, c, bφ appears in ρ[n], and consequently in ρ[m] too. Since φ bφ, this shows δ ρ[m]. Lemma 10. If W Tσ and N = |σ|, there is a stream ρ for W such that ρ[Nk] σk for all k N. Proof. First note that W Tσ implies σ = , so N > 0. Since L0 is countable, we may index the set of L0 formulas equivalent to φ L0 as {φn}n N. Let σn be obtained from σ by replacing each report i, c, φ with i, c, φn . Then σ σn. Let ρ be the sequence obtained as the infinite concatenation σ1 σ2 σ3 (this is possible since σ is of positive finite length). Then ρ[Nk] = σ1 σk, and consequently ρ[Nk] σk. It remains to show ρ is a stream for W. Soundness of ρ follows from W Tσ X snd σ , since every report in ρ is equivalent to some report in σ by construction. For completeness, suppose W, c |= Siφ. As in the proof of Lemma 8, considering the singleton sequence δ = i, c, φ , we get from W Tσ that there is ψ φ such that i, c, ψ σ. Hence there is n N such that φ = ψn, so i, c, φ σn, and thus i, c, φ ρ. Next we obtain an equivalent formulation of Credulity which is less transparent as a postulate for learning methods, but easier to work with. Lemma 11. Suppose L satisfies Soundness. Then L satisfies Credulity if and only if L(σ) Tσ for all σ with Tσ = . Proof. if : Suppose Tσ, c |= Siφ. Then there is W Tσ such that W, c |= Siφ. By our assumption and Lemma 8, L(σ) Tσ = Q [W]. Thus every world in L(σ) agrees with W on soundness statements, so L(σ), c |= Siφ. only if : Suppose there is some W Tσ, and take W L(σ). We need to show W Tσ; by Lemma 8, this is equivalent to W W . First suppose W, c |= Siφ. Then W Tσ implies there is ψ φ such that i, c, ψ σ. By Soundness for L, we have W L(σ) X snd σ . Consequently W , c |= Siψ and thus W , c |= Siφ. This shows W W . Now suppose W, c |= Siφ. Then Tσ, c |= Siφ. By Credulity, L(σ), c |= Siφ. Hence W , c |= Siφ. This shows W W. Thus W W as required. Finally, we prove the characterisation of truth-tracking. Proof of Theorem 5. Suppose L satisfies Equivalence, Repetition and Soundness. if : Suppose Credulity holds. We show L solves Q . Take any world W and stream ρ for W. By Lemma 9, there is n such that W Tρ[m] for all m n. By Lemma 8, Tρ[m] = Q [W] for such m. In particular, Tρ[m] = . By Credulity and Lemma 11, we get L(ρ[m]) Tρ[m] = Q [W]. only if : Suppose L solves Q . We show Credulity via Lemma 11. Suppose there is some W Tσ, and write N = |σ| > 0. By Lemma 10, there is a stream ρ for W such that ρ[Nk] σk for all k N. By Repetition and Equivalence, L(σ) = L(σk) = L(ρ[Nk]). But L solves Q , so for k sufficiently large we have L(ρ[Nk]) Q [W] = Tσ. Hence, going via some large k, we obtain L(σ) Tσ as required. Singleton & Booth 6.2 Conditioning Methods In this section we turn to the family of conditioning methods, proposed by Singleton and Booth (2022) and inspired by similar methods in the belief change literature (Spohn, 1988), which have also been studied in the framework of learning of Gierasimczuk (2010) and Baltag et al. (2019). While our interpretation of input sequences is different we read i, c, φ as i reporting φ is possible in case c, whereas Singleton and Booth (2022) read this as i believes φ this class of methods can still be applied in our setting. Conditioning methods operate by successively restricting a fixed plausibility total preorder7 to the information corresponding to each new report i, c, φ . In this paper, we take a report i, c, φ to correspond to the fact that Siφ holds in case c; this fits with our assumption throughout that sources only report sound statements.8 Thus, the worlds under consideration given a sequence σ are exactly those satisfying all soundness statements in σ, i.e., X snd σ . Note that X snd σ represents the indefeasible knowledge given by σ: worlds outside X snd σ are eliminated and cannot be recovered with further reports, since for any sequence δ, X snd σ δ X snd σ . The plausibility order allows us to represent defeasible beliefs about the most plausible worlds within X snd σ . Definition 4. For a total preorder on W, the conditioning method L is given by L (σ) = min X snd σ . Note that X snd σ = for all σ. For example, if ΠW i = {V} for all i then W X snd σ . From this and the fact that W is finite, we know L is consistent. Moreover, L satisfies Equivalence, Repetition and Soundness. Example 10. We recall two concrete choices of given by Singleton and Booth (2022). 1. Set W vbc W iff rvbc(W) rvbc(W ), where rvbc(W) = X i S |{p Prop | ΠW i [p] = p }|. The most plausible worlds in this order are those in which sources have as much expertise on the propositional variables as possible, on aggregate. The subscript vbc here stands for variable-based conditioning, and we denote the corresponding conditioning method by Lvbc. 2. Set W pbc W iff rpbc(W) rpbc(W ), where rpbc(W) = X i S |ΠW i |. 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. The subscript pbc here stands for partition-based conditioning, and we denote the corresponding conditioning operator by Lpbc. 7. A total preorder is a reflexive, transitive and total relation. 8. Singleton and Booth (2022) consider more general conditioning methods in which this choice is not fixed. Truth-tracking with Non-expert Information Sources Figure 3: Worlds which demonstrate Lvbc is not truth-tracking. A straightforward property of characterises truth-tracking for conditioning methods. For a generic total preorder , let < denote its strict part. Theorem 6. L is truth-tracking if and only if W W = W W such that W < W . (2) Like Credulity, (2) is a principle of maximising trust in sources. Recall from Lemma 1 that W W means all sources are more knowledgeable in each case in W than in W , and there is at least one source and case for which this holds strictly. If we aim to trust sources as much as possible, we might impose W < W here; then W is strictly less plausible and will be ruled out in favour of W. This yields a sufficient condition for truth-tracking, but to obtain a necessary condition we need to allow a surrogate world W W to take the place of W. Proof of Theorem 6. Write L = L . Since L satisfies Equivalence, Repetition and Soundness, we may use Theorem 5. Furthermore, it is sufficient by Lemma 11 to show that (2) holds if and only if L(σ) Tσ, whenever Tσ = . if : Suppose W W . Let σ be some pseudo-stream for W, so that W Tσ.9 Note that since W Tσ X snd σ and W W , we have W X snd σ also. By assumption, L(σ) Tσ = Q [W]. Since W W , this means W X snd σ \ L(σ). That is, W lies in X snd σ but is not -minimal. Consequently there is W X snd σ such that W < W . Since L is consistent, we may assume without loss of generality that W L(σ). Hence W Q [W], so W W. only if : Suppose there is some W Tσ, and let W L(σ). We need to show W Tσ = Q [W], i.e., W W . Since W L(σ) X snd σ , Lemma 8 gives W W . Suppose for contradiction that W W . Then W W . By (2), there is W W such that W < W . But W is -minimal in X snd σ , so this must mean W / X snd σ . On the other hand, W Q [W] = Tσ X snd σ : contradiction. Example 11. We revisit the methods of Example 10. 9. For example, pick some stream ρ and apply Lemma 9 to obtain a pseudo-stream. Singleton & Booth 1. The variable-based conditioning method Lvbc is not truth-tracking. Indeed, consider the worlds W and W shown in Fig. 3, where we assume Prop = {p, q}, S = {i} and C = {c}. Then W W (e.g., by Lemma 1). Note that i does not have expertise on p or q in both W and W , so rvbc(W) = rvbc(W ) = 0. Moreover, i s partition is uniquely determined in Q [W] by Theorem 4, so if W W then rvbc(W ) = 0 also. That is, there is no W W such that W 0 = dexm(W , i, c, ψ ), which gives rσ d(W ) < rσ d(W ) as required. 7. Conclusion Summary. In this paper we studied truth-tracking in the presence of non-expert sources. To start with, 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 truthtracking methods can uniquely find the actual valuations of a world W, and in doing so showed how sources may combine their expertise to track the truth. Similar results were presented for finding the actual partitions of a world W, i.e., finding the true extent of each source s expertise. We then presented the Credulity postulate, which characterises truth-tracking methods under mild assumptions. Roughly speaking, this postulate says that one needs to trust sources to be experts wherever possible. Purely deductive reasoning in which one does not conjecture beyond the fact that each received report is sound fails to be credulous enough in this sense, and thus some amount of non-monotonic reasoning is required for truth-tracking. Next, we reconsidered the belief and expertise operators of Singleton and Booth (2022) in the context of truth-tracking. Interestingly, it was seen that the variable-based conditioning method Lvbc is not truth-tracking, but the partition-based conditioning method Lpbc and score-based method Lexm are. The success of the latter two methods showed that truth-tracking is compatible with rational belief change as expressed by the postulates of (Singleton & Booth, 2022) (which are satisfied by all three methods). 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 Πi[vc] contains more than just vc. Such reports provide information about the source s expertise: if i reports both φ and φ we know Eiφ. To provide all sound reports sources must also have negative introspection over their own knowledge, i.e., Singleton & Booth they know when they do not know something. Indeed, our use of partitions makes expertise closely related to S5 knowledge (Singleton & Booth, 2022; Singleton, 2021), 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 is more likely that A suffers from p than q, but we cannot express this in our framework. On the technical side, our results on solvability of Q and the characterisation of Theorem 5 rely on the fact that we only consider finitely many worlds. In a sense this trivialises the problem of induction as studied by Kelly et al. (1997) and Baltag et al. (2015), among others. In future work it would be interesting to see which results can be carried over to the case where Prop is infinite. Acknowledgements Thanks are due to the reviewers, both of this journal and of NMR 2022, for some highly useful comments that helped to improve the paper. Alchourr on, C. E., G ardenfors, P., & Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 510 530. Baltag, A., Gierasimczuk, N., Ozg un, A., Sandoval, A. L. V., & Smets, S. (2019). A dynamic logic for learning theory. Journal of Logical and Algebraic Methods in Programming, 109, 100485. Baltag, A., Gierasimczuk, N., & Smets, S. (2015). On the solvability of inductive problems: A study in epistemic topology. In Ramanujam, R. (Ed.), Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge, TARK, 2015, Vol. 215 of EPTCS, pp. 81 98. Baltag, A., Gierasimczuk, N., & Smets, S. (2019). Truth-Tracking by Belief Revision. Studia Logica, 107(5), 917 947. de Condorcet, N. (1785). Essai sur l application de l analyse a la probabilit e des d ecisions rendues a la pluralit e des voix. Paris: L Imprimerie Royale. Elkind, E., & Slinko, A. (2016). Rationalizations of voting rules. In Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.), Handbook of Computational Social Choice, pp. 169 196. Cambridge University Press. Eschenbach, C., & Ozcep, O. L. (2010). Ontology-revision operators based on reinterpretation. Logic Journal of the IGPL, 18(4), 579 616. Everaere, P., Konieczny, S., & Marquis, P. (2010). The epistemic view of belief merging: Can we track the truth?. In Proceedings Nineteenth European Conference on Artificial Intelligence (ECAI), pp. 621 626. Gierasimczuk, N. (2009a). Bridging learning theory and dynamic epistemic logic. Synthese, 169(2), 371 384. Truth-tracking with Non-expert Information Sources Gierasimczuk, N. (2009b). Learning by erasing in dynamic epistemic logic. In International Conference on Language and Automata Theory and Applications, pp. 362 373. Springer. Gierasimczuk, N. (2010). Knowing One s Limits: Logical Analysis of Inductive Inference. Ph.D. thesis, ILLC. Gierasimczuk, N. (2023). Inductive inference and epistemic modal logic. In Klin, B., & Pimentel, E. (Eds.), 31st EACSL Annual Conference on Computer Science Logic, CSL 2023, February 13-16, 2023, Warsaw, Poland, Vol. 252 of LIPIcs, pp. 2:1 2:16. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Gold, E. M. (1967). Language identification in the limit. Information and Control, 10(5), 447 474. Goranko, V., & Passy, S. (1992). Using the universal modality: Gains and questions. Journal of Logic and Computation, 2(1), 5 30. Hartmann, S., & Sprenger, J. (2012). Judgment aggregation and the problem of tracking the truth. Synthese, 187(1), 209 221. Jain, S., Osherson, D., Royer, J. S., & Sharma, A. (1999). Systems that Learn: An Introduction to Learning Theory. MIT. Kelly, K., Schulte, O., & Hendricks, V. (1997). Reliable belief revision. In Chiara, M. L., Doets, K., Mundici, D., & van Benthem, J. (Eds.), Logic and Scientific Methods, pp. 383 398. Springer. Konieczny, S., & Pino P erez, R. (2002). Merging information under constraints: A logical framework. Journal of Logic and Computation, 12(5), 773 808. Li, Y., Gao, J., Meng, C., Li, Q., Su, L., Zhao, B., Fan, W., & Han, J. (2016). A Survey on Truth Discovery. SIGKDD Explor. Newsl., 17(2), 1 16. Singleton, J. (2021). A logic of expertise. ESSLLI 2021 Student Session. https://arxiv.org/abs/2107.10832. Singleton, J., & Booth, R. (2022). Who s the Expert? On Multi-source Belief Change. In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, pp. 331 340. Spohn, W. (1988). Ordinal conditional functions: A dynamic theory of epistemic states. In Harper, W. L., & Skyrms, B. (Eds.), Causation in Decision, Belief Change, and Statistics, pp. 105 134. Springer. Terzopoulou, Z., & Endriss, U. (2019). Optimal truth-tracking rules for the aggregation of incomplete judgments. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT-2019).