Belief revision,epistemic conditionals and the Ramsey test

Epistemic conditionals have often been thought to satisfy the Ramsey test (RT): If A, then B is acceptable in a belief state G if and only if B should be accepted upon revising G with A. But as Peter Gärdenfors has shown, RT conflicts with the intuitively plausible condition of Preservation on belief revision. We investigate what happens if (a) RT is retained while Preservation is weakened, or (b) vice versa. We also generalize Gärdenfors' approach by treating belief revision as a relation rather than as a function.In our semantic approach, the same relation is used to model belief revision and to give truth-conditions for conditionals. The approach validates a weak version of the Ramsey Test (WRR) — essentially, a restriction of RT to maximally consistent belief states.We prove that alternatives (a) and (b) are both consistent, but argue that (b) is philosophically more promising. Gärdenfors' belief-revision axioms are compatible with WRR together with RT from left to right: the only direction of the test that is defensible on intuitive grounds.An earlier version of this paper was presented at the conference on the dynamics of knowledge and belief at Lund University, 24–26 August 1989. We wish to thank Sven Danielsson, Peter Gärdenfors, Sören Halldén, David Makinson, Hugh Mellor, Michael Morreau, Nils-Eric Sahlin and Brian Skyrms for their very helpful suggestions and remarks. We are also grateful for thought-provoking criticism and comments from two anonymous referees.     

Belief contraction without recovery

The postulate of recovery is commonly regarded to be the intuitively least compelling of the six basic Gärdenfors postulates for belief contraction. We replace recovery by the seemingly much weaker postulate of core-retainment, which ensures that if x is excluded from K when p is contracted, then x plays some role for the fact that K implies p. Surprisingly enough, core-retainment together with four of the other Gärdenfors postulates implies recovery for logically closed belief sets. Reasonable contraction operators without recovery do not seem to be possible for such sets. Instead, however, they can be obtained for non-closed belief bases. Some results on partial meet contractions on belief bases are given, including an axiomatic characterization and a non-vacuous extension of the AGM closure condition.     

Iterated Belief Change and the Recovery Axiom

The axiom of recovery, while capturing a central intuition regarding belief change, has been the source of much controversy. We argue briefly against putative counterexamples to the axiom—while agreeing that some of their insight deserves to be preserved—and present additional recovery-like axioms in a framework that uses epistemic states, which encode preferences, as the object of revisions. This makes iterated revision possible and renders explicit the connection between iterated belief change and the axiom of recovery. We provide a representation theorem that connects the semantic conditions we impose on iterated revision and our additional syntactical properties. We show interesting similarities between our framework and that of Darwiche–Pearl (Artificial Intelligence 89:1–29 1997). In particular, we show that intuitions underlying the controversial (C2) postulate are captured by the recovery axiom and our recovery-like postulates (the latter can be seen as weakenings of (C2)). We present postulates for contraction, in the same spirit as the Darwiche–Pearl postulates for revision, and provide a theorem that connects our syntactic postulates with a set of semantic conditions. Lastly, we show a connection between the contraction postulates and a generalisation of the recovery axiom. Portions of this paper were originally presented at ECAI 2002.     

Conditional Probability and Defeasible Inference

We offer a probabilistic model of rational consequence relations (Lehmann and Magidor, 1990) by appealing to the extension of the classical Ramsey–Adams test proposed by Vann McGee in (McGee, 1994). Previous and influential models of non-monotonic consequence relations have been produced in terms of the dynamics of expectations (Gärdenfors and Makinson, 1994; Gärdenfors, 1993).Expectation is a term of art in these models, which should not be confused with the notion of expected utility. The expectations of an agent are some form of belief weaker than absolute certainty. Our model offers a modified and extended version of an account of qualitative belief in terms of conditional probability, first presented in (van Fraassen, 1995). We use this model to relate probabilistic and qualitative models of non-monotonic relations in terms of expectations. In doing so we propose a probabilistic model of the notion of expectation. We provide characterization results both for logically finite languages and for logically infinite, but countable, languages. The latter case shows the relevance of the axiom of countable additivity for our probability functions. We show that a rational logic defined over a logically infinite language can only be fully characterized in terms of finitely additive conditional probability. The research of both authors was supported in part by a grant from NSF, and, for Parikh, also by support from the research foundation of CUNY.     

Iterated Belief Revision and Conditional Logic

In this paper we propose a conditional logic called IBC to represent iterated belief revision systems. We propose a set of postulates for iterated revision which are a small variant of Darwiche and Pearl's ones. The conditional logic IBC has a standard semantics in terms of selection function models and provides a natural representation of epistemic states. We establish a correspondence between iterated belief revision systems and IBC-models. Our representation theorem does not entail Gärdenfors' Triviality Result.     

Iterated belief change based on epistemic entrenchment

In this paper it is argued that, in order to solve the problem of iterated belief change, both the belief state and its input should be represented as epistemic entrenchment (EE) relations. A belief revision operation is constructed that updates a given EE relation to a new one in light of an evidential EE relation. It is shown that the operation in question satisfies generalized versions of the Gärdenfors revision postulates. The account offered is motivated by Spohn's ordinal conditionalization functions, and can be seen as the Jeffrization of a proposal considered by Rott.I am indebted John G. Bennett and Henry E. Kyburg. jr. for their insightful comments on an earlier draft of this paper. I thank the referees forErkenntnis who, apart from giving extended comments and suggestions, provided me with some hard-to-find relevant material. I also thank Prashanta Bandyopadhyay, Norman Foo, Maurice Pagnucco, Hans Rott and Mary-Anne Williams for their suggestions. The errors that remain are, of course, mine.     

Systematic Withdrawal

Although AGM theory contraction (Alchourrón et al., 1985; Alchourrón and Makinson, 1985) occupies a central position in the literature on belief change, there is one aspect about it that has created a fair amount of controversy. It involves the inclusion of the postulate known as Recovery. As a result, a number of alternatives to AGM theory contraction have been proposed that do not always satisfy the Recovery postulate (Levi, 1991, 1998; Hansson and Olsson, 1995; Fermé, 1998; Fermé and Rodriguez, 1998; Rott and Pagnucco, 1999). In this paper we present a new addition, systematic withdrawal, to the family of withdrawal operations, as they have become known. We define systematic withdrawal semantically, in terms of a set of preorders, and show that it can be characterised by a set of postulates. In a comparison of withdrawal operations we show that AGM contraction, systematic withdrawal and the severe withdrawal of Rott and Pagnucco (1999) are intimately connected by virtue of their definition in terms of sets of preorders. In a future paper it will be shown that this connection can be extended to include the epistemic entrenchment orderings of Gärdenfors (1988) and Gärdenfors and Makinson (1988) and the refined entrenchment orderings of Meyer et al. (2000).     

Contraction: On the Decision-Theoretical Origins of Minimal Change and Entrenchment

We present a decision-theoretically motivated notion of contraction which, we claim, encodes the principles of minimal change and entrenchment. Contraction is seen as an operation whose goal is to minimize loses of informational value. The operation is also compatible with the principle that in contracting A one should preserve the sentences better entrenched than A (when the belief set contains A). Even when the principle of minimal change and the latter motivation for entrenchment figure prominently among the basic intuitions in the works of, among others, Quine and Ullian (1978), Levi (1980, 1991), Harman (1988) and Gärdenfors (1988), formal accounts of belief change (AGM, KM – see Gärdenfors (1988); Katsuno and Mendelzon (1991)) have abandoned both principles (see Rott (2000)). We argue for the principles and we show how to construct a contraction operation, which obeys both. An axiom system is proposed. We also prove that the decision-theoretic notion of contraction can be completely characterized in terms of the given axioms. Proving this type of completeness result is a well-known open problem in the field, whose solution requires employing both decision-theoretical techniques and logical methods recently used in belief change.     

A Sequent Formulation of Conditional Logic Based on Belief Change Operations

Peter Gärdenfors has developed a semantics for conditional logic, based on the operations of expansion and revision applied to states of information. The account amounts to a formalisation of the Ramsey test for conditionals. A conditional A > B is declared accepted in a state of information K if B is accepted in the state of information which is the result of revising K with respect to A. While Gärdenfors's account takes the truth-functional part of the logic as given, the present paper proposes a semantics entirely based on epistemic states and operations on these states. The semantics is accompanied by a syntactic treatment of conditional logic which is formally similar to Gentzen's sequent formulation of natural deduction rules. Three of David Lewis's systems of conditional logic are represented. The formulations are attractive by virtue of their transparency and simplicity.     

Belief Change in Branching Time: AGM-consistency and Iterated Revision

We study belief change in the branching-time structures introduced in Bonanno (Artif Intell 171:144–160, 2007). First, we identify a property of branching-time frames that is equivalent (when the set of states is finite) to AGM-consistency, which is defined as follows. A frame is AGM-consistent if the partial belief revision function associated with an arbitrary state-instant pair and an arbitrary model based on that frame can be extended to a full belief revision function that satisfies the AGM postulates. Second, we provide a set of modal axioms that characterize the class of AGM-consistent frames within the modal logic introduced in Bonanno (Artif Intell 171:144–160, 2007). Third, we introduce a generalization of AGM belief revision functions that allows a clear statement of principles of iterated belief revision and discuss iterated revision both semantically and syntactically.     

New Foundations for a Relational Theory of Theory-revision

AGM-theory, named after its founders Carlos Alchourrón, Peter Gärdenfors and David Makinson, is the leading contemporary paradigm in the theory of belief-revision. The theory is reformulated here so as to deal with the central relational notions ‘J is a contraction of K with respect to A’ and ‘J is a revision of K with respect to A’. The new theory is based on a principal-case analysis of the domains of definition of the three main kinds of theory-change (expansion, contraction and revision). The new theory is stated by means of introduction and elimination rules for the relational notions. In this new setting one can re-examine the relationship between contraction and revision, using the appropriate versions of the so-called Levi and Harper identities. Among the positive results are the following. One can derive the extensionality of contraction and revision, rather than merely postulating it. Moreover, one can demonstrate the existence of revision-functions satisfying a principle of monotonicity. The full set of AGM-postulates for revision-functions allow for completely bizarre revisions. This motivates a Principle of Minimal Bloating, which needs to be stated as a separate postulate for revision. Moreover, contractions obtained in the usual way from the bizarre revisions, by using the Harper identity, satisfy Recovery. This provides a new reason (in addition to several others already adduced in the literature) for thinking that the contraction postulate of Recovery fails to capture the Principle of Minimal Mutilation. So the search is still on for a proper explication of the notion of minimal mutilation, to do service in both the theory of contraction and the theory of revision. The new relational formulation of AGM-theory, based on principal-case analysis, shares with the original, functional form of AGM-theory the idealizing assumption that the belief-sets of rational agents are to be modelled as consistent, logically closed sets of sentences. The upshot of the results presented here is that the new relational theory does a better job of making important matters clear than does the original functional theory. A new setting has been provided within which one can profitably address two pressing questions for AGM-theory: (1) how is the notion of minimal mutilation (by both contractions and revisions) best analyzed? and (2) how is one to rule out unnecessary bloating by revisions?     

Towards a “Sophisticated” Model of Belief Dynamics. Part II: Belief Revision.

In the companion paper (Towards a “sophisticated” model of belief dynamics. Part I), a general framework for realistic modelling of instantaneous states of belief and of the operations involving them was presented and motivated. In this paper, the framework is applied to the case of belief revision. A model of belief revision shall be obtained which, firstly, recovers the Gärdenfors postulates in a well-specified, natural yet simple class of particular circumstances; secondly, can accommodate iterated revisions, recovering several proposed revision operators for iterated revision as special cases; and finally, offers an analysis of Rott’s recent counterexample to several Gärdenfors postulates [32], elucidating in what sense it fails to be one of the special cases to which these postulates apply.     

Preference-based belief revision for rule-based agents

Agents which perform inferences on the basis of unreliable information need an ability to revise their beliefs if they discover an inconsistency. Such a belief revision algorithm ideally should be rational, should respect any preference ordering over the agent’s beliefs (removing less preferred beliefs where possible) and should be fast. However, while standard approaches to rational belief revision for classical reasoners allow preferences to be taken into account, they typically have quite high complexity. In this paper, we consider belief revision for agents which reason in a simpler logic than full first-order logic, namely rule-based reasoners. We show that it is possible to define a contraction operation for rule-based reasoners, which we call McAllester contraction, which satisfies all the basic Alchourrón, Gärdenfors and Makinson (AGM) postulates for contraction (apart from the recovery postulate) and at the same time can be computed in polynomial time. We prove a representation theorem for McAllester contraction with respect to the basic AGM postulates (minus recovery), and two additional postulates. We then show that our contraction operation removes a set of beliefs which is least preferred, with respect to a natural interpretation of preference. Finally, we show how McAllester contraction can be used to define a revision operation which is also polynomial time, and prove a representation theorem for the revision operation.     

On the logic of theory change: Safe contraction

This paper is concerned with formal aspects of the logic of theory change, and in particular with the process of shrinking or contracting a theory to eliminate a proposition. It continues work in the area by the authors and Peter Gärdenfors. The paper defines a notion of safe contraction of a set of propositions, shows that it satisfies the Gärdenfors postulates for contraction and thus can be represented as a partial meet contraction, and studies its properties both in general and under various natural constraints.     

Non-monotonic Probability Theory and Photon Polarization

A non-monotonic theory of probability is put forward and shown to have applicability in the quantum domain. It is obtained simply by replacing Kolmogorov’s positivity axiom, which places the lower bound for probabilities at zero, with an axiom that reduces that lower bound to minus one. Kolmogorov’s theory of probability is monotonic, meaning that the probability of A is less then or equal to that of B whenever A entails B. The new theory violates monotonicity, as its name suggests; yet, many standard theorems are also theorems of the new theory since Kolmogorov’s other axioms are retained. What is of particular interest is that the new theory can accommodate quantum phenomena (photon polarization experiments) while preserving Boolean operations, unlike Kolmogorov’s theory. Although non-standard notions of probability have been discussed extensively in the physics literature, they have received very little attention in the philosophical literature. One likely explanation for that difference is that their applicability is typically demonstrated in esoteric settings that involve technical complications. That barrier is effectively removed for non-monotonic probability theory by providing it with a homely setting in the quantum domain. Although the initial steps taken in this paper are quite substantial, there is much else to be done, such as demonstrating the applicability of non-monotonic probability theory to other quantum systems and elaborating the interpretive framework that is provisionally put forward here. Such matters will be developed in other works.     

Two notions of epistemic validity

How to accept a conditional? F. P. Ramsey proposed the following test in (Ramsey 1990). (RT) ‘If A, then B’ must be accepted with respect to the current epistemic state iff the minimal hypothetical change of it needed to accept A also requires accepting B. In this article we propose a formulation of (RT), which unlike some of its predecessors, is compatible with our best theory of belief revision, the so-called AGM theory (see (Gärdenfors 1988), chapters 1–5 for a survey). The new test, which, we claim, encodes some of the crucial insights defended by F. P. Ramsey in (Ramsey 1990), is used to study the conditionals epistemically validated by the AGM postulates. Our notion of validity (PV) is compared with the notion of negative validity (NV) used by Gärdenfors in (Gärdenfors 1988). It is observed that the notions of PV and NV will in general differ and that when these differences arise it is the notion of PV that is preferable. Finally we compare our formulation of the Ramsey test with a previous formulation offered by Gärdenfors (GRT). We show that any attempt to interpret (GRT) as delivering acceptance conditions for Ramsey's conditionals is doomed to failure.     

The Simplest Axiom System for Plane Hyperbolic Geometry

We provide a quantifier-free axiom system for plane hyperbolic geometry in a language containing only absolute geometrically meaningful ternary operations (in the sense that they have the same interpretation in Euclidean geometry as well). Each axiom contains at most 4 variables. It is known that there is no axiom system for plane hyperbolic consisting of only prenex 3-variable axioms. Changing one of the axioms, one obtains an axiom system for plane Euclidean geometry, expressed in the same language, all of whose axioms are also at most 4-variable universal sentences. We also provide an axiom system for plane hyperbolic geometry in Tarski's language L _B which might be the simplest possible one in that language.     

Non-Prioritized Ranked Belief Change

Traditional accounts of belief change have been criticized for placing undue emphasis on the new belief provided as input. A recent proposal to address such issues is a framework for non-prioritized belief change based on default theories (Ghose and Goebel, 1998). A novel feature of this approach is the introduction of disbeliefs alongside beliefs which allows for a view of belief contraction as independently useful, instead of just being seen as an intermediate step in the process of belief revision. This approach is, however, restrictive in assuming a linear ordering of reliability on the received inputs. In this paper, we replace the linear ordering with a preference ranking on inputs from which a total preorder on inputs can be induced. This extension brings along with it the problem of dealing with inputs of equal rank. We provide a semantic solution to this problem which contains, as a special case, AGM belief change on closed theories.     

Interrogative Belief Revision in Modal Logic

The well known AGM framework for belief revision has recently been extended to include a model of the research agenda of the agent, i.e. a set of questions to which the agent wishes to find answers (Olsson & Westlund in Erkenntnis, 65, 165–183, 2006). The resulting model has later come to be called interrogative belief revision. While belief revision has been studied extensively from the point of view of modal logic, so far interrogative belief revision has only been dealt with in the metalanguage approach in which AGM was originally presented. In this paper, I show how to model interrogative belief revision in a modal object language using a class of operators for questions. In particular, the solution I propose will be shown to capture the notion of K-truncation, a method for agenda update in the case of expansion constructed by Olsson & Westlund. Two case studies are conducted: first, an interrogative extension of Krister Segerberg’s system DDL, and then a similar extension of Giacomo Bonanno’s modal logic for belief revision. Sound and complete axioms will be provided for both of the resulting logics.