Eradication

Eradication is a radical form of contraction that removes not only a sentence but also all of its non-tautological consequences from a belief set. Eradication of a single sentence that was included in the original belief set coincides with full meet contraction, but if the sentence is external to the belief set then the two operations differ. Multiple eradication, i.e. simultaneous eradication of several sentences, differs from full meet contraction even if the sentences to be contracted are all included in the original belief set. Eradication is axiomatically characterized and its properties investigated. It is shown to have close connections with the recovery postulate for multiple contraction. Based on these connections it is proposed that eradication rather than full meet contraction is the appropriate lower limiting case for multiple contraction operators.     

基础生成的多元部分收缩的一个公理化刻画(英文)

这篇论文结合了两种信念收缩的 AGM 框架的推广,分别为:(1)基础生成收缩,其中信念集的变化是从某个信念基的变化生成的;(2)多元收缩,其中几个句子一次过同时被消去。本文引入了一个结合以上两种推广的运算,"基础生成的多元部分收缩",并将其进行了公理化刻画。     

Global and Iterated Contraction and Revision: An Exploration of Uniform and Semi-Uniform Approaches

In order to clarify the problems of iterated (global) belief change it is useful to study simple cases, in particular consecutive contractions by sentences that are both logically and epistemically independent. Models in which the selection mechanism is kept constant are much more plausible in this case than what they are in general. One such model, namely uniform specified meet contraction, has the advantage of being closely connected with the AGM model. Its properties seem fairly adequate for the intended type of contraction. However, the revision operator based on it via the Levi identity collapses into an implausible operation that loses all old information when revising by new information. A weaker version, semi-uniform specified meet contraction, avoids the collapse but has the disadvantage of a remarkably weak logic. It is left as an open issue whether there is an intermediate class of contraction operators that yields a more satisfactory logic.     

Maximal and perimaximal contraction

Generalizations of partial meet contraction are introduced that start out from the observation that only some of the logically closed subsets of the original belief set are at all viable as contraction outcomes. Belief contraction should proceed by selection among these viable options. Several contraction operators that are based on such selection mechanisms are introduced and then axiomatically characterized. These constructions are more general than the belief base approach. It is shown that partial meet contraction is exactly characterized by adding to one of these constructions the condition that all logically closed subsets of the belief set can be obtained as the outcome of a single (multiple) contraction. Examples are provided showing the counter-intuitive consequences of that condition, thus confirming the credibility of the proposed generalization of the AGM framework.     

Bootstrap Contraction

We can often specify how we would contract by a certain sentence by saying that this contraction would coincide with some other contraction that we know how to perform. We can for instance clarify that our contraction by p&q would coincide with our contraction by p, or by q, or by {p, q}. In a framework where the set of potential outcomes is known, some contractions are “self-evident” in the sense that there is only one serious candidate that can be the outcome of such a contraction. Contraction by a specific contractee (sentence or set of sentences to be contracted) is bootstrapped if it is specified by saying that it coincides with some such self-evident contraction. For a wide range of (multiple) contraction operators, contractions by any contractee can be bootstrapped. This means that the selection mechanism (selection function, incision function, etc.) can be replaced by a function called a bootstrapping selector that assigns to each contractee some “self-evident” contractee that yields the same outcome. With bootstrapping we can eliminate traditional extralogical components in contraction (e.g., selection functions) and replace them by bootstrapping selectors that reflect more closely the ways in which we actually reason and argue about belief contraction.     

Specified Meet Contraction

Specified meet contraction is the operation ?\div defined by the identity K ?p = K   ~  f(p)K \div p = K \,{\sim}\, f(p) where ∼ is full meet contraction and f is a sentential selector, a function from sentences to sentences. With suitable conditions on the sentential selector, specified meet contraction coincides with the partial meet contractions that yield a finite-based contraction outcome if the original belief set is finite-based. In terms of cognitive realism, specified meet contraction has an advantage over partial meet contraction in that the selection mechanism operates on sentences rather than on temporary infinite structures (remainders) that are cognitively inaccessible. Specified meet contraction provides a versatile framework in which other types of contraction, such as severe withdrawal and base-generated contraction, can be expressed with suitably chosen properties of the sentential selector.     

How to bereally contraction free

A logic is said to becontraction free if the rule fromA (A B) toA B is not truth preserving. It is well known that a logic has to be contraction free for it to support a non-trivial naïve theory of sets or of truth. What is not so well known is that if there isanother contracting implication expressible in the language, the logic still cannot support such a naïve theory. A logic is said to berobustly contraction free if there is no such operator expressible in its language. We show that a large class of finitely valued logics are each not robustly contraction free, and demonstrate that some other contraction free logics fail to be robustly contraction free. Finally, the sublogics of (with the standard connectives) are shown to be robustly contraction free.     

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.     

Categories and percepts: a bi-directionnal framework for categorization

Categorization is a fundamental process whereby variable perceptual inputs are reduced progressively to a small number of equivalence classes, called 'categories'. How do theorists frame the categorization problem so that variable face, object and scene information is stabilized for higher-level processing? One approach suggests that perception delivers a fixed set of features that are treated as inputs to categorization processes. This paper questions this unidirectionality and argues instead that perceptual organization is linked intimately with the categorization being accomplished. An example is presented where it can be shown that the history of categorization changes the featural analysis and the perception of identical, but unfamiliar, inputs. Flexible percepts are then generalized to real-world scene categorization in the space of multiple spatial scales. This evidence suggests that a bidirectional framework, with direct interactions between concepts and percepts, is a more appropriate framework for categorization.     

Three Approaches to Iterated Belief Contraction

In this paper we investigate three approaches to iterated contraction, namely: the Moderate (or Priority) contraction, the Natural (or Conservative) contraction, and the Lexicographic contraction. We characterise these three contraction functions using certain, arguably plausible, properties of an iterated contraction function. While we provide the characterisation of the first two contraction operations using rationality postulates of the standard variety for iterated contraction, we found doing the same for the Lexicographic contraction more challenging. We provide its characterisation using a variation of Epistemic ranking function instead.     

Blockage Contraction

Blockage contraction is an operation of belief contraction that acts directly on the outcome set, i.e. the set of logically closed subsets of the original belief set K that are potential contraction outcomes. Blocking is represented by a binary relation on the outcome set. If a potential outcome X blocks another potential outcome Y, and X does not imply the sentence p to be contracted, then Y?≠?K ÷ p. The contraction outcome K ÷ p is equal to the (unique) inclusion-maximal unblocked element of the outcome set that does not imply p. Conditions on the blocking relation are specified that ensure the existence of such a unique inclusion-maximal set for all sentences p. Blockage contraction is axiomatically characterized and its relations to AGM-style operations are investigated. In a finite-based framework, every transitively relational partial meet contraction is also a blockage contraction.     

System of Spheres-based Multiple Contractions

We propose a new class of multiple contraction operations — the system of spheres-based multiple contractions — which are a generalization of Grove’s system of spheres-based (singleton) contractions to the case of contractions by (possibly non-singleton) sets of sentences. Furthermore, we show that this new class of functions is a subclass of the class of the partial meet multiple contractions.     

Nested Deontic Modalities: Another View of Parking on Highways

A suggestion is made for representing iterated deontic modalities in stit theory, the “seeing-to-it-that” theory of agency. The formalization is such that normative sentences are represented as agentive sentences and therefore have history dependent truth conditions. In contrast to investigations in alethic modal logic, in the construction of systems of deontic logic little attention has been paid to the iteration... of the deontic modalities. L. Goble (1966, p. 197) N. Belnap and P. Bartha (1995) present a formalization of iterated deontic modalities in stit theory, the “seeing-to-it-that” theory of agency, due to Belnap, Perloff, and Xu (1996). In the present paper a simplification of Belnap and Bartha's approach is suggested. In order to support easy comparison with (1995), I shall take up Belnap and Bartha's discussion of R. Barcan Marcus' (1966) example Parking on highways ought to be forbidden. The simplified account underlines the power of stit theory and represents obligations, prohibitions and permissions as agentive sentences, as required by iteration. Therefore, in particular, the truth of obligations, prohibitions and permissions is it history dependent. This revised version was published online in July 2006 with corrections to the Cover Date.     

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.     

Probabilities on Sentences in an Expressive Logic

Automated reasoning about uncertain knowledge has many applications. One difficulty when developing such systems is the lack of a completely satisfactory integration of logic and probability. We address this problem directly. Expressive languages like higher-order logic are ideally suited for representing and reasoning about structured knowledge. Uncertain knowledge can be modeled by using graded probabilities rather than binary truth values. The main technical problem studied in this paper is the following: Given a set of sentences, each having some probability of being true, what probability should be ascribed to other (query) sentences? A natural wish-list, among others, is that the probability distribution (i) is consistent with the knowledge base, (ii) allows for a consistent inference procedure and in particular (iii) reduces to deductive logic in the limit of probabilities being 0 and 1, (iv) allows (Bayesian) inductive reasoning and (v) learning in the limit and in particular (vi) allows confirmation of universally quantified hypotheses/sentences. We translate this wish-list into technical requirements for a prior probability and show that probabilities satisfying all our criteria exist. We also give explicit constructions and several general characterizations of probabilities that satisfy some or all of the criteria and various (counter)examples. We also derive necessary and sufficient conditions for extending beliefs about finitely many sentences to suitable probabilities over all sentences, and in particular least dogmatic or least biased ones. We conclude with a brief outlook on how the developed theory might be used and approximated in autonomous reasoning agents. Our theory is a step towards a globally consistent and empirically satisfactory unification of probability and logic.     

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.     

Infinite "Backward" Induction Arguments

A large family of paradoxical arguments have been subsumed under the label "backward induction arguments". These include the iterated prisonerÕs dilemma, the centipede game, and the surprise test paradox. They are described as backward because they begin by considering a future hypothetical alternative, rule it out, and then rule out each predecessor. Thus they go backward in time ruling out finitely many alternatives. I present examples that go forward in time and eliminate infinitely many alternatives. These pose problems for solutions that focus on common knowledge assumptions.     

Coherence and Conservatism in the Dynamics of Belief

In this paper I discuss the foundations of a formal theory of coherent and conservative belief change that is (a) suitable to be used as a method for constructing iterated changes of belief, (b) sensitive to the history of earlier belief changes, and (c) independent of any form of dispositional coherence. I review various ways to conceive the relationship between the beliefs actually held by an agent and her belief change strategies (that also deal with potential belief sets), show the problems they suffer from, and suggest that belief states should be represented by unary revision functions that take sequences of inputs. Three concepts of coherence implicit in current theories of belief change are distinguished: synchronic, diachronic and dispositional coherence. Diachronic coherence is essentially identified with what is known as conservatism in epistemology. The present paper elaborates on the philosophical motivation of the general framework; formal details and results are provided in a companion paper.     

The contraction rule and decision problems for logics without structural rules

This paper shows a role of the contraction rule in decision problems for the logics weaker than the intuitionistic logic that are obtained by deleting some or all of structural rules. It is well-known that for such a predicate logic L, if L does not have the contraction rule then it is decidable. In this paper, it will be shown first that the predicate logic FL_ec with the contraction and exchange rules, but without the weakening rule, is undecidable while the propositional fragment of FL_ec is decidable. On the other hand, it will be remarked that logics without the contraction rule are still decidable, if our language contains function symbols.