Chapter 5 Approaching the Truth via Belief Change in Propositional Languages Gustavo Cevolani and Francesco Calandra Starting from the 1960s of the past century, scientific change has become a main concern of philosophy of science. In particular, a great deal of attention has been devoted to theory change.1 Two of the best known formal accounts of theory change are the post-Popperian theories of verisimilitude (for short: PPV)2 and the AGM theory of belief change (for short: AGM).3 In this paper, we will investigate the conceptual relations between PPV and AGM and, in particular, we will ask whether the AGM rules for theory change are effective means for approaching the truth, i.e., for achieving the cognitive aim of science pointed out by PPV. PPV and AGM are characterized by strongly different assumptions concerning the aims of science. In fact, while all versions of PPV share the view that verisimilitude is the main cognitive aim of science, the only aims explicitly suggested by G. Cevolani () Department of Philosophy, University of Bologna, via Zamboni 38, 40126 Bologna (Italy) e-mail: g.cevolani@gmail.com F. Calandra University of Trieste, Italy e-mail: filocalandra@libero.it  Although we are separately responsible for particular sections (Gustavo Cevolani: Sections 5.1.2, 5.2 and 5.3; Francesco Calandra: Section 5.1.1), we have each benefited from regular discussions and the rereading of each other's contributions, which produced a unified exposition of all the subjects dealt with in the paper. 1 For a discussion of the problem of rational theory change and its relations with the aims of science, see Cevolani and Festa (2009). 2 In the present paper, the terms "verisimilitude" and "truth approximation" are used as synonymous. The first full-fledged account of verisimilitude was provided by Karl Popper (1963, 1972). Later, David Miller (1974) and Pavel Tichý (1974) showed that Popper's account was untenable, thus opening the way to the post-Popperian theories of verisimilitude, emerged since 1975. An excellent survey of the modern history of verisimilitude is provided by Niiniluoto (1998). 3 In the literature, the terms "belief dynamics", "belief change", and "belief revision" are used as synonymous. AGM, which is named after Alchourrón, Gärdenfors, and Makinson (1985), was developed, starting from the 1970s, by researchers in philosophy of science, logic and Artificial Intelligence. The first monograph devoted to AGM was written by Gärdenfors (1988), and the first textbook presentation by Hansson (1999). M. Suárez et al. (eds.), EPSA Epistemology and Methodology of Science: Launch of the European Philosophy of Science Association, DOI 10.1007/978-90-481-3263-8 5, c Springer Science+Business Media B.V. 2010 47 48 G. Cevolani and F. Calandra AGM are consistency and informative content. In fact, truth and truth approximation play no role at all in AGM, as the following telling quote by Gärdenfors (1988, p. 20) clearly reveals: OE: : : the concepts of truth and falsity are irrelevant for the analysis of belief systems. These concepts deal with the relation between belief systems and the external world, which I claim is not essential for an analysis of epistemic dynamics. OE: : : My negligence of truth may strike traditional epistemologists as heretical. However, one of my aims is to show that many epistemological problems can be attacked without using the notions of truth and falsity.4 In spite of this, one may ask whether the AGM rules for belief change are effective means for approaching the truth (Niiniluoto 1999). In Sections 5.1 and 5.2, the key ideas of PPV and AGM and their application to so called "propositional theories" will be illustrated. In Section 5.3 we will prove that, as far as propositional theories are concerned, AGM belief change is an effective tool for approaching the truth. 5.1 Post-Popperian Verisimilitude for Propositional Theories 5.1.1 Post-Popperian Theories of Verisimilitude The intuitive idea underlying the concept of verisimilitude is that: a theory is highly verisimilar if it says many things about the domain under investigation and many of those things are true, or almost exactly true. One of the best known accounts of verisimilitude has been provided by Ilkka Niiniluoto (1987). Niiniluoto's approach can be applied to theories stated in many kinds of language, including propositional and first-order languages. In this paper, however, we will only be concerned with theories stated within a propositional language L with n atomic propositions p1; p2; : : : ; pn. Given an atomic proposition pm we will say that pm and :pm are the basic propositions – or b-propositions – associated to pm. The b-propositions of L form a set B D fp1; :p1; p2; :p2; : : : ; pn; :png including 2n members. The most informative propositions of L are called constituents. A constituent Ci is the most complete description of a possible world made by means of the expressive resources of L. In fact, for any atomic proposition pm; Ci tells whether pm is true or not. Hence, Ci can be written in the following form:   p1 ^  p2 ^ : : : ^  pn; (5.1) 4 Quite recently, however, some AGM theorists have criticized the lack of any concern for truth in AGM. For instance, Hans Rott argues that AGM "should worry more about truth" considered as one of the basic aims of scientific inquiry (see Rott 2000, pp 513, 518 and ff., and in particular note 38). 5 Approaching the Truth via Belief Change in Propositional Languages 49 where " " is either empty or the negation symbol ":". Any b-proposition occurring in Eq. 5.1 will be called a basic claim – or b-claim – of Ci . Moreover, we will say that each b-claim  pm of Ci is true in (the possible world described by) Ci . The constituents of L form a set C D fC1; C2; : : : ; Cqg including q D 2n members. Moreover, one can check that: (i) C1; C2; : : : ; Cq are mutually exclusive and jointly exhaustive; (ii) there is an unique true constituent, which will be denoted by "C "; (iii) any sentence T of L can be expressed in its normal disjunctive form as follows: T  _ j 2T Cj (5.2) where T is the index set of the constituents entailing T . The so called "similarity approach" to verisimilitude is based on the idea that an appropriate measure of verisimilitude Vs.T / should express the similarity between T and "the truth" C  or, equivalently, the closeness of T to C . The basic intuition underlying Niiniluoto's version of the similarity approach is that the verisimilitude Vs.T / of a theory T  _ j 2T Cj can be defined as a function of the distances between the disjuncts Cj of T and C . The versions of the similarity approach based on this intuition may be called disjunctive versions (or d-versions). In Niiniluoto's d-version of the similarity approach, Vs.T / is defined as follows. First, a distance function  is defined on the ordered couples .Ci ; Cj / of constituents of C by identifying ij  .Ci ; Cj / with the number of the differences in the  -signs between Ci and Cj , divided by n; i.e., with the number of the b-claims on which Ci and Cj disagree, divided by the total number of atomic propositions. This implies that 0  ij  1 and ij D 0 iff i D j . Second, an extended distance function .T; Ci/ is defined on all the couples .T; Ci /, where the distance .T; Ci / of T from Ci is a function of the distances ij between the disjuncts Cj of T and Ci . Niiniluoto's favourite extended distance function .T; Ci / is the so called min-sum distance function:  0 ms .T; Ci /  min.T; Ci/ C  0sum.T; Ci /; (5.3) with 0 < "; "0  1.5 Since  0ms is normalized, the similarity s.T; Ci / of T to Ci can be simply defined as: s 0 ms .T; Ci /  1   0 ms .T; Ci/: (5.4) 5 Distance  0 ms is a weighted sum of two simpler (extended) distances, the minimum distance min.T; Ci / and the normalized sum distance sum.T; Ci /. The minimum distance of T from Ci is the distance from Ci of the closest constituent entailing T , defined as: min.T; Ci / D minj2T ij. The normalized sum distance of T from Ci is the sum of the distances from Ci of all the constituents entailing T normalized with respect to the sum of the distances of all the elements of C from Ci W sum.T; Ci / D Pj2T ij .P Cj 2C ij. 50 G. Cevolani and F. Calandra Finally, the degree of verisimilitude Vs 0 ms .T / of T can be defined as the similarity between T and "the truth" C : Vs 0 ms .T /  s 0 ms .T; C /  1   0ms .T; C /: (5.5) One can prove that Vs 0 ms satisfies a number of plausible principles. Among them, the following are especially important6: (Vs.1) Among true statements, verisimilitude covaries with information. (Vs.2) Among false statements, verisimilitude does not covary with information. (Vs.3) Some false statements may be more verisimilar than some true statements. 5.1.2 Applying PPV to Propositional Theories According to the d-version of the similarity approach, the verisimilitude Vs.T / of a sentence T depends only on the distances between the states of affairs allowed by T – represented by the constituents Ci which entail T – and the true state of affairs C . On the other hand, according to a recently proposed version of this approach – which may be called the conjunctive version (or c-version) – Vs.T / depends only on what T says about the "basic features" of the actual world C , where such features are expressed by the b-claims  pm which are true in C .7 The key concept of the c-version of the similarity approach is the notion of conjunctive proposition – or c-proposition. C-propositions are possibly the simplest kind of "propositional theories", i.e., of theories stated within a propositional language L.8 While a constituent Ci specifies a complete list of the allegedly true b-propositions of L, a c-proposition T specifies a (possibly) incomplete list of such b-propositions. A c-proposition can be expressed in the following form:   p1T ^  p2T ^ : : : ^  pkT ; (5.6) where kT  n. Constituents are nothing but a special kind of c-proposition with kT D n; moreover, a tautology T can be seen as the c-proposition with kT D 0. Any b-proposition  pm occurring in Eq. 5.6 will be called a b-claim of T . The set T C of all the b-claims of a c-proposition T will be referred to as the basic content – or b-content – of T . Given a constituent Ci ; T C can be partitioned into two subsets: (1) the subset t.T; Ci / of the b-claims of T which are true in Ci , and 6 There are good reasons to think that any plausible measure of verisimilitude should respect (Vs.1– Vs.3) (see Niiniluoto 1987, pp 232–233). 7 The c-version of the similarity approach presented here has been developed by Festa (2007a,b,c), Cevolani and Festa (2009), and Cevolani et al. (2009) with respect to first-order and propositional languages. 8 C-propositions are essentially identical to "descriptive statements" or "D-statements" (Kuipers 1982, pp 348–349) and to "quasi-constituents" (Oddie 1986, p 86). 5 Approaching the Truth via Belief Change in Propositional Languages 51 (2) the subset f .T; Ci / of the b-claims of T which are false in Ci. We may say that t.T; Ci / is the true b-content of T w.r.t. Ci , while f .T; Ci / is the false b-content of T w.r.t. Ci . Given a non-tautological c-proposition T , we will say that T is true in the case where t.T; C / D T C (and f .T; C / D ¿/ and that T is completely false in the case where t.T; C / D ¿ (and f .T; C / D T C/. T is false if some of its b-claims are false. The c-proposition QT , given by the conjunction of the negations of all T 's b-claims, will be called the specular of T. It is easy to see that if T is true then QT is completely false and viceversa, whereas if T is false then QT too is false. Starting from the qualitative notions of true and false b-content of T w.r.t. Ci , the corresponding quantitative notions of degree of true b-content contt .T; Ci / and degree of false b-content contf (T; Ci) of T w.r.t. Ci can be introduced as follows: contt .T; Ci/ D t.T; Ci / n and contf .T; Ci / D f .T; Ci / n (5.7) The similarity s£.T; Ci / of T to Ci can then be defined as a weighted average of contt .T; Ci / and contf .T; Ci/, where contt .T; Ci/ is construed as the prize attributed to the true b-content of T w.r.t. Ci and contf .T; Ci / as the penalty attributed to the false b-content of T w.r.t. Ci : s .T; Ci / D contt .T; Ci / C .1  /.contf .T; Ci // D contt .T; Ci /  .1  /contf .T; Ci/ (5.8) where 0 < £  1=2. The verisimilitude of T; Vs£.T /, is then identified with the similarity between T and the true constituent C : Vs .T / D s .T; C /: (5.9) In order to state some interesting features of Vs£, it is useful to introduce the notions of verisimilar sentences and of sentences which are distant from the truth-or t-distant sentences.9 To this purpose, we shall say that a c-proposition T is verisimilar in the case where Vs£.T / > 0 and that T is t-distant in the case where Vs£.T / < 0. Some relevant consequences of Eqs. 5.8 and 5.9 can now be proved: Theorem 1. Given a c-proposition T of the form  p1T ^  p2T ^ : : : ^  pkT : 1. .£  1/  Vs£.T /  £. 2. If T is tautological, then Vs£.T / D 0. 3. If T is true, then T is verisimilar. 9 A similar definition can be given with respect to any verisimilitude measure Vs, by selecting a suitable threshold value ¢ and calling "verisimilar" and "t-distant" those sentences whose verisimilitude is greater or lower than ¢ , respectively. 52 G. Cevolani and F. Calandra 4. If T is completely false, then T is t-distant. 5. Vs .T / D Ppm2T C Vs .pm/. 6. Vs£ satisfies principles (Vs.1–Vs.3). 7. Vs .T / <=D=> Vs . QT / iff contt .T; C / <=D=> contf .T; C /. 5.2 AGM Belief Change for Propositional Theories 5.2.1 The AGM Theory of Belief Change Within the AGM theory of belief change, the epistemic state of an ideal agent X is represented by a belief set or theory, i.e., by a deductively closed set of sentences. More precisely, given a language L, an operation of logical consequence Cn defined on L, and a set K of sentences within L, the notion of belief set is defined as follows: K is a belief set if and only if Cn.K/ D K: (5.10) Although the notion of belief set in Eq. 5.10 includes also inconsistent belief sets, AGM theorists adopt the following principle of consistency: (C) The belief set K of an ideal agent X should be consistent. Suppose that the epistemic state of X is represented by a consistent belief set K . Then X can have one of the following epistemic attitudes towards a sentence A of L: i X accepts A in the case where A 2 K; ii X rejects A in the case where :A 2 K; iii X suspends the judgment on A – or, equivalently, A is undetermined for X – in the case where both A ... K and :A ... K . The basic purpose of AGM is to provide a plausible account of how an ideal agent X should update his belief set K in response to certain epistemic inputs coming from some information source. Given a sentence A, two kinds of epistemic input concerning A are considered within AGM: (a) Additive inputs, which can be expressed as orders of the form "Add A to your belief set!". (b) Eliminative inputs, which can be expressed as orders of the form "Remove A from your belief set!". Below, the additive input "Add A to your belief set!" and the eliminative input "Remove A from your belief set!" will also be denoted by the shorter expressions "additive input A" and "eliminative input A", respectively. 5 Approaching the Truth via Belief Change in Propositional Languages 53 Suppose that X receives the additive input "Add A to your belief set!". Of course, if A already belongs to K – i.e., if X already accepts A – then X 's appropriate response is keeping K unchanged. However, there are two more interesting cases where A ... K: Expansion. A is compatible with K , i.e., :A ... K . In this case, the epistemic operation by which X should update K by the addition of A is called expansion, and the expanded belief set is denoted by "KCA ". Revision. A is incompatible with K , i.e., :A 2 K . In this case, the epistemic operation by which X should update K by the addition of A is called revision, and the revised belief set is denoted by "KA". Below, we will call "addition" the generic operation of updating K by an additive input A. Hence, the addition of A to K will be either the expansion of K by A, in the case where A is compatible with K , or the revision of K by A, in the case where A is incompatible with K . Now suppose that X receives the eliminative input "Remove A from your belief set!". If A does not belong to K – i.e., X rejects, or suspends the judgment on, A–X's appropriate response consists is keeping K unchanged. However, the more interesting case where A 2 K may occur: Contraction. If A 2 K , the epistemic operation by which X should update K by the removal of A is called contraction, and the contracted belief set is denoted by "KA". AGM theorists have made systematic efforts aiming to show how, given a belief set K and a sentence A, an ideal agent X could specify the updated belief sets KCA ; KA and KA . A basic intuition underlying the AGM approach is expressed by the following general principle of rationality, known as the principle of minimal change: (MC) When the belief set K of an ideal agent X is updated in response to a given epistemic input, a minimal change of K should be accomplished. This means that X should continue to believe as many of the old beliefs as possible and start to believe as few new beliefs as possible. There are many alternative ways of defining KCA ; KA and KA in accordance with the general principles of consistency and minimal change. For this reason, Gärdenfors (1988) has proposed a number of adequacy conditions – the so called Gärdenfors postulates – that any appropriate definition of KCA ; KA and KA should satisfy. For instance, the "Success" postulate for revision says that A 2 KA. However, it should be noted that the Gärdenfors postulates alone cannot fully determine the result of any belief change. Suppose, for example, that an agent X receives the additive input A. If X 's theory K includes :A, then X has to revise K by A. This means that :A must be removed from K , in order to guarantee both that A 2 KA – as required by the Success postulate – and that KA is consistent – in agreement with (C). Moreover, X has to remove from K not only :A but – due to the definition (Eq. 5.10) of belief set – also any set of sentences entailing :A. Since there are normally many alternative ways to fulfill this task, the choice of one of them will 54 G. Cevolani and F. Calandra depend on the relative "importance" that X attaches to the sentences in K . In this connection, one may assume that the elements of K are ordered with respect to their so called epistemic entrenchment (Gärdenfors and Makinson 1988). When X has to remove some sentences from K , he will choose the less entrenched in agreement with appropriate selection rules. A well known method for defining the operations of expansion, revision and contraction in accordance with the Gärdenfors postulates and with entrenchment-based selection rules has been provided by Grove (1988). For the sake of brevity, below we will outline Grove's method only with reference to expansion and revision.10 Grove shows that, given a propositional language L, any belief set K in L is identical to the set of all the logical consequences of some sentence T of L – i.e., is identical to the so called consequence class Cn.T /. Hence, a generic belief set or "theory" may be identified with the corresponding sentence T of L, expressed in its normal disjunctive form as T  _ j 2T Cj . An epistemic entrenchment relation can be defined on the sentences of L by ordering the constituents of C with respect to their relative closeness or similarity to the elements of T. Niiniluoto (1999) shows that such an ordering is easily obtained in the case where a suitable distance function  is defined on the constituents of L (see Section 5.1.1). In fact, the distance i .T / of a constituent Ci from a theory T may be defined as i .T / D minj 2T ij D min.Ci ; T /. Moreover, given an epistemic input A, the set CT .A/ of the closest constituents to T entailing A is defined as: CT .A/ D   i 2 A W i .T /  j .T /  for all j 2 A. By using these notions, Niiniluoto proves the following identities concerning expansion and revision11: Theorem 2. If the additive input A is compatible with T , in the sense that :A ... Cn.T /, then T CA is simply given by the conjunction of T and A: T CA D T ^ A D _ i2T\A Ci : Theorem 3. If the additive input A is incompatible with T , in the sense that :A 2 Cn.T /, then T A is given by T A D _ i2CT .A/ Ci : 5.2.2 Applying AGM to Propositional Theories Now we will show how the basic principles of AGM can be applied to the definition of T CA and T  A in the case where both T and A are c-propositions. To this purpose, we have to introduce some preliminary notions concerning T and its logical relations with A. 10 See Cevolani et al. (forthcoming) for a discussion of contraction. 11 See Niiniluoto (1999), pp 7–9. 5 Approaching the Truth via Belief Change in Propositional Languages 55 First of all, recall that T C is the set of all b-claims of T , i.e., the set of all b-propositions occurring in T . The set of the negations of the elements of T C will be denoted by "T ", whereas the set of the b-propositions which occur neither in T C nor in T  will be denoted by "T ‹".12 Note that the sets T C; T  and T ‹ form a partition of the set B of the 2n b-propositions of L. Suppose that the agent X receives the additive input A. In order to understand how X should update his belief set T in response to A, one should note that the logical relations between T and A depend on how AC overlaps the partition fT C; T ; T ‹g. For this reason, it is useful to introduce the notions of the "redundant", "conflicting" and "extra" part of A with respect to T , as follows. Given two c-propositions T and A, the following related c-propositions are defined: 1. ArT , the conjunction of the elements of AC \ T C, will be called the redundant part of A w.r.t. T. 2. AcT , the conjunction of the elements of AC \ T , will be called the conflicting part of A w.r.t. T. 3. AxT , the conjunction of the elements of AC \ T ‹, will be called the extra part of A w.r.t. T. Below, the conflicting and the extra parts of A w.r.t. T will be also referred to as the "non-redundant parts" of A w.r.t. T . Note that the three sets AC \ T C; AC \ T  and AC \ T ‹ form a partition of AC. Hence, A can be written as ArT ^ AcT ^ AxT and, in the same way, T can be written as TrA ^ TcA ^ TxA. The following properties of the c-propositions ArT ; AcT and AxT defined above are worth noting. First, ArT is identical to TrA, by definition. Moreover, it is easy to see that AcT D QTcA and TcA DQAcT – i.e., that the conflicting part of A w.r.t. T is the specular of the conflicting part of T w.r.t. A, and vice versa. Finally, AxT and TxA share by definition no common conjuncts. The above notions can be used to prove the following theorems concerning expansion and revision13: Theorem 4. If the additive input A is compatible with T , in the sense that AC \ T  D ¿, then T CA D T ^ A. Theorem 5. If the additive input A is incompatible with T , in the sense that AC \ T  ¤ ¿, then T A D A ^ TxA. A consequence of Theorem 4 is worth noting here. First, recalling that ArT D TrA, one can see that the information ArT is already conveyed by T . Second, since A is compatible with T by hypothesis, the conflicting part of A w.r.t. T is empty – i.e., AC \ T  D ¿ and AcT D TcA D T. From these two facts, it follows that the conjunction of T with A is identical to the conjunction of T with the extra part of A w.r.t. T . Hence, Theorem 4 implies that T CA D T ^ AxT . 12 If T is the theory of an agent X , then T C; T , and T ‹ can be seen as the set of the b-propositions which X accepts, rejects, and on which suspends the judgment, respectively. 13 These theorems are proved in Cevolani et al. (forthcoming) together with a number of results about contraction. 56 G. Cevolani and F. Calandra 5.3 Is AGM Belief Change a Road to Verisimilitude? We can now come back to the question considered at the beginning of the paper, i.e., the question whether the AGM rules for belief change are effective means for approaching the truth. This question may be now rephrased as follows: are AGM expansion and revision effective means for approaching the truth?14 Niiniluoto (1999) investigates this problem with respect to his favored verisimilitude measure Vs 0 ms , introduced in Section 5.1.1. In particular, Niiniluoto asks in which cases expansion and revision lead our theories closer to the truth or, in other words, in which cases, given a theory T and an additive input A; T CA and T A are more verisimilar than T . In this connection, Niiniluoto can immediately prove the following result15: Theorem 6. Suppose that both T and A are true. Then Vs 0 ms  T CA   Vs 0ms .T /. It is not difficult to show that this result doesn't hold only for Vs 0 ms but also for most of the existing verisimilitude measures. Indeed Theorem 3 holds for any verisimilitude measure satisfying the principle (Vs.1) according to which, among true statements, verisimilitude covaries with information.16 Unfortunately, Niiniluoto shows that Theorem 3 cannot be extended to more general cases. In particular, Niiniluoto proves that, even in the case where A is true, T CA and T A may be less verisimilar than T 17: Theorem 7. Suppose that A is true. Then: 1. If T is false, T CA may be less verisimilar than T . 2. T A may be less verisimilar than T. Niiniluoto's results above concern the expansion and the revision of theories expressed in propositional and first-order languages. Theorem 3 shows that the simple addition of true epistemic inputs to such theories doesn't necessarily lead them closer to the truth. In this regard, one can say that expansion and revision are not effective means for approaching the truth, at least as far Vs 0 ms is concerned. However, a different conclusion can be reached if we restrict our attention to a special kind of propositional theories, i.e., c-propositions. In this case, we can specify various cases where expansion and revision are effective means for approaching the truth. Accordingly, from now on we will assume that both the theory T and the epistemic input A are c-propositions. The following theorems state the conditions under which expansion and revision increase the verisimilitude of a theory T with respect to the verisimilitude measure Vs£ introduced in Section 5.1.2. 14 The problem of the effectiveness of contraction for approaching the truth is considered in Cevolani et al. (forthcoming). 15 See Niiniluoto (1999), Eq. 5.10. 16 One of the few verisimilitude measures violating (Vs.1) has been proposed by Graham Oddie (1986). 17 See Niiniluoto (1999), pp. 10–13, in particular equations 10, 17 and 20. 5 Approaching the Truth via Belief Change in Propositional Languages 57 Theorem 8. Given a theory T , suppose that A is compatible with T and AC 6 T C.18 Then: Vs  T CA  > Vs .T / iff AxT is verisimilar: Theorem 9. Given a theory T , suppose that A is incompatible with T . Then: Vs  T A  > Vs .T / iff Vs .AxT / > Vs . QAcT /  Vs .AcT /: In order to grasp the intuitive meaning of Theorem 9, recall that, by hypothesis, A is incompatible with T , i.e., that the conflicting part of T w.r.t. A is not empty. According to Theorem 5, the revision of T by A replaces such conflicting part TcA DQAcT with AcT and adds AxT to T . Now suppose that Vs .AcT/ < Vs . QAcT/. Then the difference Vs . QAcT/  Vs .AcT/ can be construed as the loss of verisimilitude due to the addition of the conflicting part of A to T . However, if the extra part of A outweighs this loss – i.e., if Vs .AxT/ > Vs . QAcT/  Vs .AcT/ – then the revised theory T A will still be more verisimilar than T . Recalling that, according to Theorem 1, if A is true then A is verisimilar, whereas if A is completely false then A is t-distant, one can now prove some interesting consequences of Theorems 8 and 9. First, the addition of true inputs to (false) theories always increases their verisimilitude: Theorem 10. Suppose that A is true. Then: 1. Vs  T CA  > Vs .T /. 2. Vs  T A  > Vs .T /. Second, if the non-redundant parts of A w.r.t. T are verisimilar, then the addition of A to T leads T closer to the truth: Theorem 11. Suppose that AcT and AxT are verisimilar. Then: 1. Vs  T CA  > Vs .T /. 2. Vs  T A  > Vs .T /. To sum up, expansion and revision are effective means for approaching the truth, as far as c-propositions and the verisimilitude measure Vs£ are concerned, in the following sense. First, the addition of true inputs to (false) theories leads to more verisimilar theories. Second, the addition of inputs whose non-redundant parts are verisimilar also increases the verisimilitude of the original theory. Finally, one may consider another aspect of AGM's effectiveness for approaching the truth which is not discussed by Niiniluoto (1999). In fact, Theorems 10 and 11 concern the expansion and the revision of T by true inputs or by inputs whose nonredundant parts are verisimilar. However, one might ask what happens in the case where T is expanded or revised by inputs which are completely false or whose nonredundant parts are t-distant. In such cases, it seems plausible to expect that the 18 The proviso is needed in order to exclude the trivial case where A is already contained in T , i.e., the case where AxT D T and T CA D T . 58 G. Cevolani and F. Calandra expansion and the revision of T by A leads to theories which are less verisimilar than T . An answer to this question is provided by the following theorems. First, one can prove that the addition of completely false inputs to T leads to a less verisimilar theory, as the following result (which is the counterpart of Theorem 3) states: Theorem 12. Suppose that A is completely false. Then: 1. Vs  T CA  < Vs .T /. 2. Vs  T A  < Vs .T /. Moreover, if the non-redundant parts of A are t-distant, the expansion of T by A is less verisimilar than T : Theorem 13. Suppose that AcT and AxT are t-distant. Then, Vs  T CA  < Vs .T /. Interestingly, however, this doesn't hold for revision; in fact: Theorem 14. T A may be more verisimilar than T , even if both AcT and AxT are t-distant. The results illustrated in this paper suggest two further questions. The first is whether similar results may be obtained for the contraction of c-propositions by different kind of eliminative inputs. This problem is analyzed in Cevolani et al. (forthcoming). The second question is whether Theorems 10–14 can be extended to verisimilitude measures different from Vs£. In this connection, we advance the admittedly bold guess that the results proved in Theorems 10–14 hold for any plausible verisimilitude measure defined on propositional languages. Acknowledgments The authors wish to express their gratitude to Roberto Festa and Theo A. F. Kuipers for commenting on an early draft of the paper. Proofs. Proof of Theorem 1. 1. The most verisimilar c-proposition T of L is the true constituent itself, i.e., C . If T D C , then contt .T; C / D 1, whereas contf .T; C / D 0. Then Vs£.T / D £contt .T; C / D £ is the verisimilitude of the most verisimilar c-proposition of L. On the other hand, the less verisimilar c-proposition T is the completely false constituent, i.e., the specular QC  of C . If T D QC , then contt .T; C / D 0, whereas and contf .T; C / D 1. Then Vs£.T / D  .1  £/contf .T; C / D £  1 is the verisimilitude of the less verisimilar c-proposition of L. 2. Recall that T is tautological iff kT D 0, i.e., T C D ¿. Then, contt .T; C / D contf .T; C / D 0 and Vs£.T / D 0. 3. If T is true (and non-tautological), then t.T; C /DT C¤¿ and contt .T; C / > 0, whereas f .T; C / D ¿ and contf .T; C / D 0. Consequently, since £ > 0; Vs£.T / D £contt .T; C / > 0. 5 Approaching the Truth via Belief Change in Propositional Languages 59 4. If T is completely false, then t.T; C / D ¿ and contt .T; C / D 0, whereas f .T; C / D T C ¤ ¿ and contf .T; C / > 0. Since .1  £/ > 0; Vs£.T / D .1  £/contf .T; C / < 0. Note that a b-proposition pm is also a c-proposition, whose unique b-claim is pm. If pm is true, then t.pm; C / D fpmg and contt .pm; C / D 1=n, whereas f .pm; C / D ¿ and contf .pm; C / D 0; moreover Vs£.pm/ D £=n. Conversely, if pm is false, then f .pm; C / D fpmg and contf .pm; C / D 1=n, whereas t.pm; C / D ¿ and contt .pm; C / D 0; moreover Vs£.pm/ D  .1  £/=n. It is now easy to see that, for any T; contt .T; C / D P pi 2t.T;C / contt .pi ; C / and contf .T; C / D P pj 2f .T;C / contf .pj ; C /. Hence, Vs .T / D   P pi 2t.T;C / contt .pi ; C /  .1  /  P pj 2f .T;C / contf .pj ; C /, i.e., since t.T; C /[f .T; C / D T C; Vs .T / D P pi 2t.T;C / Vs .pi / C P pj 2f .T;C / Vs .pj / D P pm2T C Vs .pm/. 5. Consider two c-propositions A and B such that A is logically stronger than B , i.e., such that A ` B but B / A. This means that BC  AC, i.e., that A contains all B's claims and at least one additional b-proposition  pm. First, suppose that A and B are both true; it follows that  pm is true and Vs£. pm/ D £=n by the lemma above. By the same lemma, Vs£.A/ D Vs£.B/ C Vs£. pm/; moreover, since pm is true, Vs£. pm/ > 0. Thus, Vs£.A/ > Vs£.B/. Consequently, (Vs1) is satisfied: if A is logically stronger than B and both are true, A is more verisimilar than B . Suppose now that A and B are both false. If  pm is true, then A will be more verisimilar than B; however, if  pm is false, then A will be less verisimilar (but logically stronger) than B . Thus, (Vs2) is satisfied, since verisimilitude doesn't covary, among false c-propositions, with logical strength. Finally, to see that (Vs3) is satisfied, consider the measure Vs£ with £ D 1=2, defined on the language L with three atomic propositions p, q and r . Suppose that p, q and r are true and consider the two c-propositions A  p and B  p ^ q ^ :r . Although A is true and B is false, Vs£.A/ D £=n D 1=6, whereas Vs£.B/ D £2=n  .1  £/1=n D 1=3. Thus, the false c-proposition B is more verisimilar than the true c-proposition A. 6. By definition, contt .A; C / D contf . QA; C / and contf .A; C / D contt . QA; C /. Consequently, Vs£.A/ < = D = > Vs£. QA/ iff, by definition (9), £contt .A; C /  .1£/contf .A; C / <=D=> £contf .A; C / .1£/contt .A; C /, i.e., since £ > 0, iff contf .A; C / >=D=< contt .A; C /. Proof of Theorem 8. Let us prove the following result: Vs  T CA  >=D=< Vs .T / iff Vs .AxT/ >=D=< 0. The expansion of T by A is T CA D T ^ A by Theorem 4. As observed at the end of Section 5.2.2, since AxT D TxA and TcA D AcT D T by hypothesis (since A is compatible with T ), T CA can be written as T ^ AxT . Consequently, Vs  T CA  > = D = < Vs .T / iff Vs .T ^ A/ > = D = < Vs .T /. 60 G. Cevolani and F. Calandra By Theorem 1, Vs£.T ^ A/ D Vs£.T / C Vs£.AxT/. Hence, Vs  T CA  > = D = < Vs .T / iff Vs .AxT/ >=D=< 0. Proof of Theorem 9. Let us prove the following result: Vs  T A  >=D=< Vs .T / iff Vs .AxT/ >=D=< Vs . QAcT/Vs .AcT/. The revision of T by A is T A D ÂTxA by Theorem 5. Recalling from Section 5.2.2 that A D ArT ^ AcT ^ AxT , we have that T A D ArT ^ AcT ^ AxT ^ TxA. Since A is incompatible with T by hypothesis, i.e., AcT is not empty, T may be expressed as ArT ^ QAcT ^ TxA. Thus, Vs  T A  > =D=< Vs .T / iff Vs .ArT ^ AcT ^ AxT ^ TxA/ >=D=< Vs .ArT ^ QAcT ^ TxA/ iff (by Theorem 1) Vs .AcT/CVs .AxT/ >=D=< Vs . QAcT/, i.e., iff Vs .AxT/ >=D= < Vs . QAcT/  Vs .AcT/. Proof of Theorem 10. 1. If A is true, AxT is also true (a fortiori) and Vs£.AxT/ is verisimilar by Theorem 1. Thus, Vs  T CA  > Vs .T / by Theorem 8. 2. If A is true, both AcT and AxT are true (a fortiori). Thus, Vs£.AxT/ > 0 and Vs£.AcT/ > 0 by Theorem 1. We want to prove, according to Theorem 8, that Vs .AxT/ > Vs . QAcT/  Vs .AcT/; to this purpose, it is then sufficient to prove that Vs . QAcT/  Vs .AcT/  0, i.e., Vs . QAcT/  Vs .AcT/. By Theorem 1.7, this holds iff contt .AcT ; C /  contf .AcT ; C /. To see that this is in fact the case, note that, since AcT is true, contt .A; C / > 0 and contf .A; C / D 0. Consequently, by Theorem 8, Vs  T A  > Vs .T /. Proof of Theorem 11. 1. Note that since A is compatible with T by hypothesis, the only non-redundant part of A w.r.t. T is AxT . If AxT is verisimilar, then Vs£.AxT/ > 0 by definition and Vs  T CA  > Vs .T / by Theorem 8. 2. If AcT and AxT are verisimilar, then Vs£.AcT/ > 0 by definition. In order to prove that Vs .AxT/ > Vs . QAcT/  Vs .AcT/, it is then sufficient to prove (see the proof of Theorem 10) that contt .AcT ; C /  contf .AcT ; C /. To see that this is in fact the case, note that, since Vs£.AcT/ > 0; £contt .AcT ; C /  .1  £/contf .AcT ; C / > 0. Consequently, contt .AcT ; C / > .1  £/= £contf .AcT ; C /. Since .1  £/=£  1, it follows that contt .AcT ; C /  contf .AcT ; C /. It follows from this that Vs .AcT/  Vs . QAcT/, i.e., Vs . QAcT/  Vs .AcT/  0, and thus that Vs .AxT/ > Vs . QAcT/  Vs .AcT/. Consequently, by Theorem 8, Vs  T A  > Vs .T /. Proof of Theorem 12. 1. If A is completely false, AxT is also completely false (a fortiori) and Vs£.AxT/ < 0 by Theorem 1. Thus, Vs  T CA  < Vs .T / by the proof of Theorem 8. 2. If A is completely false, both AcT and AxT are completely false (a fortiori). Thus, Vs£.AxT/ < 0 and Vs£.AcT/ < 0 by Theorem 1. As observed above (see the proof of Theorem 8), to prove that Vs .AxT/ < Vs . QAcT/  Vs .AcT/ it is sufficient to prove that contt .AcT ; C /  contf .AcT ; C /. To see that this is in fact the case, note that, since AcT is completely false, contt .AcT ; C / D 0 and contf .AcT ; C / > 0. Consequently, by the proof of Theorem 8, Vs  T A  < Vs .T /. 5 Approaching the Truth via Belief Change in Propositional Languages 61 Proof of Theorem 13. Note that since A is compatible with T by hypothesis, the only non-redundant part of A w.r.t. T is AxT . If AxT is t-distant, then Vs£.AxT/ < 0 by definition and Vs  T CA  < Vs .T / by Theorem 8. Proof of Theorem 14. Consider the following counterexample to the claim that if AcT and AxT are t-distant, then Vs  T A  < Vs .T /. Let p1; : : : ; p6 be true atomic propositions of L and let be T  :p1 ^ :p2 ^ :p3 ^ p4 ^ p5 a false theory. Let consider the (false) additive input A  p1 ^ p2 ^ p3 ^ :p4 ^ :p5 ^ :p6; the conflicting part of A w.r.t. T is AcT D p1 ^ p2 ^ p3 ^ :p4 ^ :p5 and the extra part of A w.r.t. T is AxT D :p6. The revision of T by A will be, by Theorem 5, T A D p1 ^p2 ^p3 ^:p4 ^:p5 ^:p6. Now consider a verisimilitude measure Vs£ defined on L with £ D 1=3. It is easy to calculate that Vs£.T / D 4=3n. Moreover, Vs£.AcT/ D 1=3n and Vs£.AxT/ D 2=3n, i.e., both AcT and AxT are t-distant. This notwithstanding, since Vs  T A  D 1=n; T A is more verisimilar than T . References Alchourrón C, Gärdenfors P, Makinson D (1985) On the logic of theory change: partial meet contraction and revision functions. J Symbol Logic 50:510–530 Cevolani G, Festa R (2009) Scientific change, belief dynamics and truth approximation. La Nuova Critica 51–52:27–59 Cevolani G, Crupi V, Festa R (2009) The whole truth about Linda: probability, verisimilitude and a paradox of conjunction. In: D'Agostino M, Sinigaglia C (eds) Selected papers from the SILFS07 Conference, College Publications, London, forthcoming Cevolani G, Crupi V, Festa R (forthcoming) Verisimilitude and belief change for conjunctive theories Festa R (2007a) The qualitative and statistical verisimilitude of qualitative theories. La Nuova Critica 47–48:91–114 Festa R (2007b) Verisimilitude, cross classification, and prediction logic. Approaching the statistical truth by falsified qualitative theories. Mind Soc 6:37–62 Festa R (2007c) Verisimilitude, qualitative theories, and statistical inferences. In: Pihlström S, Sintonen M, Raatikainen P (eds) Approaching truth: essays in honour of Ilkka Niiniluoto. College Publications, London, pp 143–177 Gärdenfors P (1988) Knowledge in flux: modeling the dynamics of epistemic states. MIT Press/Bradford Book, Cambridge, MA Gärdenfors P, Makinson D (1988) Revisions of knowledge systems using epistemic entrenchment. In: Vardi MY (ed) Proceedings of the second conference on theoretical aspects of reasoning about knowledge. Morgan Kaufmann, Los Altos, CA, pp 83–95 Grove A (1988) Two modelling for theory change. J Philos Logic 17:157–170 Hansson SO (1999) A textbook of belief dynamics: theory change and database updating. Kluwer, Dordrecht Kuipers TAF (1982) Approaching descriptive and theoretical truth. Erkenntnis 18:343–378 Miller D (1974) Popper's qualitative theory of verisimilitude. Br J Philos Sci 25:166–177 Niiniluoto I (1987) Truthlikeness. Reidel, Dordrecht Niiniluoto I (1998) Verisimilitude: the third period. Br J Philos Sci 49:1–29 Niiniluoto I (1999) Belief revision and truth likeness. In: Hansson B, Halldén S, Sahlin N-E, Rabinowicz W (eds) Internet Festschrift for Peter Gärdenfors. URL http://www.lucs.lu.se/ spinning/ 62 G. Cevolani and F. Calandra Oddie G (1986) Likeness to truth. Reidel, Dordrecht Popper KR (1963) Conjectures and refutations: the growth of scientific knowledge. Routledge & Kegan Paul, London Popper KR (1972) Objective knowledge. Clarendon, Oxford Rott H (2000) Two dogmas of belief revision. J Philos 97:503–522 Tichý P (1974) On Popper's definitions of verisimilitude. Br J Philos Sci 25:155–