Stanford Encyclopedia of Philosophy
This is a file in the archives of the Stanford Encyclopedia of Philosophy.

Logic of Belief Revision

First published Fri Apr 21, 2006

In the logic of belief revision, a belief state (or database) is represented by a set of sentences. The major operations of change are those consisting in the introduction or removal of a belief-representing sentence. In both cases, changes affecting other sentences may be needed (for instance in order to retain consistency). Rationality postulates for such operations have been proposed, and representation theorems have been obtained that characterize specific types of operations in terms of these postulates.

In the dominant belief revision theory, the so-called AGM model, the set representing the belief state is assumed to be a logically closed set of sentences (a belief set). In an alternative approach, the corresponding set is not logically closed (a belief base). One of most debated topics in belief revision theory is the recovery postulate, according to which the all original beliefs are regained if one of them is first removed and then reinserted. The recovery postulate holds in the AGM model but not in closely related models employing belief bases. Another much discussed topic is how repeated changes can be adequately represented.

Introduction

1.1 History

Belief revision (belief change, belief dynamics) is a young field of research that has been recognized as a subject of its own since the middle of the 1980's. The new subject grew out of two converging research traditions.

One of these emerged in computer science. Since the beginning of computing, programmers have developed procedures by which databases can be updated. The development of Artificial Intelligence inspired computer scientists to construct more sophisticated models of database updating. The truth maintenance systems developed by Jon Doyle (1979) were important in this development. One of the most significant theoretical contributions was a 1983 paper by Ronald Fagin, Jeffrey Ullman and Moshe Verdi, in which they introduced the notion of database priorities.

The second of these two research traditions is philosophical. In a wide sense, belief change has been a subject of philosophical reflection since antiquity. In the twentieth century, philosophers have discussed the mechanisms by which scientific theories develop, and they have proposed criteria of rationality for revisions of probability assignments. Beginning in the 1970's a more focused discussion has taken place of the requirements of rational belief change. Two milestones can be pointed out. The first was a series of studies conducted by Isaac Levi in the 1970's. (Levi 1977, 1980) Levi posed many of the problems that have since then been the major concerns of this field of research. He also provided much of the basic formal framework. William Harper's (1977) work from the same period has also had a lasting influence.

The next milestone was the AGM model, so called after its three originators, Carlos Alchourrón, Peter Gärdenfors, and David Makinson. Alchourrón and Makinson had previously cooperated in studies of changes in legal codes. (Alchourrón and Makinson 1981, 1982) Gärdenfors's early work was concerned with the connections between belief change and conditional sentences. (Gärdenfors 1978, 1981) With combined forces the three wrote a paper that provided a new, much more general and versatile formal framework for studies of belief change. Since the paper was published in the Journal of Symbolic Logic in 1985, its major concepts and constructions have been the subject of significant elaboration and development. The AGM model and developments that have grown out of it still form the core of belief revision theory.

1.2 The representation of beliefs and changes

In the AGM model and most other models of belief change, beliefs are represented by sentences in some formal language. Sentences do not capture all aspects of belief, but they are the best general-purpose representation that is presently available.

The beliefs held by an agent are represented by a set of such belief-representing sentences. It is usually assumed that this set is closed under logical consequence, i.e. every sentence that follows logically from this set is already in the set. This is clearly an unrealistic idealization, since it means that the agent is taken to be “logically omniscient.” However, it is a useful idealization since it simplifies the logical treatment; indeed, it seems difficult to obtain an interesting formal treatment without it. In logic, logically closed sets are called “theories”. In formal epistemology they are also called “corpora”, “knowledge sets”, or (more commonly) “belief sets”.

Isaac Levi (1991) has clarified the nature of this idealization by pointing out that a belief set consists of the sentences that someone is committed to believe, not those that she actually believes in. According to Levi, we are doxastically committed to believe in all the logical consequences of our beliefs, but typically our performance does not fulfil this commitment. The belief set represents your commitments.

In the AGM framework, there are three types of belief change. In contraction, a specified sentence p is removed, i.e. a belief set K is superseded by another belief set K÷p that is a subset of K not containing p. In expansion a sentence p is added to K, and nothing is removed, i.e. K is replaced by a set K+p that is the smallest logically closed set that contains both K and p. In revision a sentence p is added to K, and at the same time other sentences are removed if this is needed to ensure that the resulting belief set K*p is consistent.

It is important to note the specific character of these models. They are input-assimilating. This means that the object of change, the belief set, is exposed to an input, and is changed as a result of this. No explicit representation of time is included. Instead, the characteristic mathematical constituent is a function that, to each pair of a belief set and an input, assigns a new belief set.

1.3 Formal preliminaries

The belief-representing sentences form a language. (As is usual in logic, the language is identified with the set of all sentences it contains.) Sentences, i.e. elements of this language, will be represented by lowercase letters (p, q…) and sets of sentences by capital letters. This language contains the usual truth-functional connectives: negation (¬), conjunction (&), disjunction (∨), implication (→), and equivalence (↔). ⊥ denotes an arbitrary contradiction (“falsum”), and ⊤ an arbitrary tautology.

To express the logic, a Tarskian consequence operator will be used. Intuitively speaking, for any set A of sentences, Cn(A) is the set of logical consequences of A. More formally, a consequence operation on a given language is a function Cn from sets of sentences to sets of sentences. It satisfies the following three conditions:

Inclusion: A⊆Cn(A)

Monotony: If A⊆B, then Cn(A) ⊆ Cn(B)

Iteration: Cn(A) = Cn(Cn(A))

Cn is assumed to be supraclassical, i.e. if p can be derived from A by classical truth-functional logic, then p ∈ Cn(A). A is a belief set if and only if A = Cn(A). In what follows, K will denote a belief set. X ⊢ p is an alternative notation for p ∈ Cn(X), and X ⊬ p for p ∉ Cn(X). Cn(∅) is the set of tautologies.

The expansion of K by a sentence p, i.e. the operation that just adds p and removes nothing, is denoted K+p and defined as follows: K+p = Cn(K∪{p}).

2. Contraction

2.1 Partial meet contraction

The outcome of contracting K by p should be a subset of K that does not imply p, but from which no elements of K have been unnecessarily removed. Therefore, it is of interest to consider the inclusion-maximal subsets of K that do not imply p.

For any set A and sentence p the remainder set A⊥p (“A remainder p”) is the set of inclusion-maximal subsets of A that do not imply p. In other words, a set B is an element of A⊥p if and only if it it is a subset of A that does not imply p, and there is no set B′ not implying p such that B⊂ B′⊆A. The elements of A⊥p are called “remainders”.

If the operation of contraction uncompromisingly minimizes information loss, then K÷p will be one of the remainders. However, this construction can be shown to have implausible properties. A more reasonable recipe for contraction is to let K÷p be the intersection of some of the remainders. This is partial meet contraction, the major innovation in the classic 1985 paper by Carlos Alchourrón, Peter Gärdenfors and David Makinson. An operator of partial meet contraction employs a selection function that selects the “best” elements of K⊥p. More precisely, a selection function for K is a function γ such that if K⊥p is non-empty, then γ(K⊥p) is a non-empty subset of K⊥p. In the limiting case when K⊥p is empty, then γ(K⊥p) is defined to be equal to {K}.

The outcome of the partial meet contraction is equal to the intersection of the set of selected elements of K⊥p, i.e. K÷p = ∩γ(K⊥p).

The special case when for all sentences p, γ(K⊥p) has exactly one element is called maxichoice contraction. The special case when γ(K⊥p) = K⊥p whenever K⊥p is non-empty is called full meet contraction.

Partial meet contraction of a belief set satisfies six postulates that are called the basic Gärdenfors postulates (or basic AGM postulates). To begin with, when a belief set K is contracted by a sentence p, the outcome should be logically closed.

Closure: K÷p = Cn(K÷p)

Contraction should be successful, i.e., K÷p should not imply p (or not contain p, which is the same thing if Closure is satisfied). However, it would be too much to require that p ∉ Cn(K÷p) for all sentences p, since it cannot hold if p is a tautology. The success postulate has to be conditional on p not being logically true.

Success: If p ∉ Cn(∅), then p ∉ Cn(K÷p).

The contracted set should be a subset of the original one:

Inclusion: K÷p ⊆ K

If the sentence to be contracted is not included in the original belief set, then contraction by that sentence involves no change at all. Such contractions are idle (vacuous) operations, and they should leave the original set unchanged.

Vacuity: If p ∉ Cn(K), then K÷p = K.

Logically equivalent sentences should be treated alike in contraction:

Extensionality: If p↔q ∈ Cn(∅), then K÷p = K÷q.

Extensionality guarantees that the logic of contraction is extensional in the sense of allowing logically equivalent sentences to be freely substituted for each other.

Belief contraction should not only be successful, it should also be minimal in the sense of leading to the loss of as few previous beliefs as possible. The epistemic agent should give up beliefs only when forced to do so, and should then give up as few of them as possible. This is ensured by the following postulate:

Recovery: K ⊆ (K÷p)+p

According to Recovery, so much is retained after p has been removed that everything can be recovered by reinclusion (through expansion) of p.

One of the central results of the AGM model is a representation theorem for partial meet contraction. According to this theorem, an operator ÷ is an operator of partial meet contraction for a belief set K if and only if it satisfies the six above-mentioned postulates, namely Closure, Success, Inclusion, Vacuity, Extensionality, and Recovery.

A selection function for a belief set K should, for all sentences p, select those elements of K⊥p that are “best”, or most worth retaining. However, the definition of a selection function is very general, and allows for quite disorderly selection patterns. An orderly selection function should always choose the best element(s) of the remainder set according to some well-behaved preference relation. A selection function γ for a belief set K is relational if and only if there is a binary relation R such that for all sentences p, if K⊥p is non-empty, then γ(K⊥p) = {B ∈ K⊥p | CRB for all C ∈ K⊥p}. Furthermore, if R is transitive (i.e. it satisfies: If ARB and BRC, then ARC), then γ and the partial meet contraction that it gives rise to are transitively relational.

In order to characterize transitively relational partial meet contraction postulates are needed that refer to contraction by conjunctions.

In order to give up a conjunction p&q, the agent must relinquish either her belief in p or her belief in q (or both). Suppose that contracting by p&q leads to loss of the belief in p, i.e., that p ∉ K÷(p&q). It can be expected that in this case contraction by p&q should lead to the loss of all beliefs that would have been lost in order to contract by p. Another way to express this is that everything that is retained in K÷(p&q) is also retained in K÷p:

Conjunctive inclusion: If p ∉ K÷(p&q), then K÷(p&q) ⊆ K÷p.

Another fairly reasonable principle for contraction by conjunctions is that whatever can withstand both contraction by p and contraction by q can also withstand contraction by p&q. In other words, whatever is an element of both K÷p and K÷q is also an element of K÷(p&q).

Conjunctive overlap: (K÷p) ∩ (K÷q) ⊆ K÷(p&q)

Conjunctive overlap and Conjunctive inclusion are commonly called Gärdenfors's supplementary postulates for belief contraction. An operation ÷ for K is a transitively relational partial meet contraction if and only if it satisfies the six basic postulates and in addition both Conjunctive overlap and Conjunctive inclusion.

2.2 Entrenchment-based contraction

When forced to give up previous beliefs, the epistemic agent should give up beliefs that have as little explanatory power and overall informational value as possible. As an example of this, in the choice between giving up beliefs in natural laws and beliefs in single factual statements, beliefs in the natural laws, that have much higher explanatory power, should in general be retained. This was the basic idea behind Peter Gärdenfors's proposal that contraction of beliefs should be ruled by a binary relation, epistemic entrenchment. (Gärdenfors 1988, Gärdenfors and Makinson 1988) To say of two elements p and q of the belief set that “q is more entrenched than p” means that q is more useful in inquiry or deliberation, or has more “epistemic value” than p. In belief contraction, the beliefs with the lowest entrenchment should be the ones that are most readily given up.

The following symbols will be used for epistemic entrenchment:

p≤q : p is at most as entrenched as q.

p<q : p is less entrenched than q ((p≤q)&¬(q≤p))).

p≡q : p and q are equally entrenched ((p≤q)&(q≤p)).

Gärdenfors has proposed the following five postulates for epistemic entrenchment, that are often referred to as the standard postulates for entrenchment:

Transitivity: If p≤q and q≤r, then p≤r.

Dominance: If p ⊢ q, then p≤q.

Conjunctiveness: Either p≤(p&q) or q≤(p&q).

Minimality: If the belief set K is consistent, then p ∉ K if and only if p≤q for all q.

Maximality: If q≤p for all q, then p ∈ Cn(∅).

It follows from the first three of these postulates that an entrenchment relation satisfies connectivity, i.e. it holds for all p and q that either p≤q or q≤p.

An entrenchment relation ≤ gives rise to an operator ÷ of entrenchment-based contraction according to the following definition:

q ∈ K÷p if and only if q ∈ K and either p < (p ∨ q) or p ∈ Cn(∅).

Entrenchment-based contraction has been shown to coincide exactly with transitively relational partial meet contraction.

2.3 Recovery and its avoidance

Recovery is the most debated postulate of belief change. It is easy to find examples that seem to validate Recovery. A person who first loses and then regains her belief that she has a dollar in her pocket seems to return to her previous state of belief. However, other examples can also be presented, in which Recovery yields implausible results. The following are two of the examples that have been offered to show that Recovery does not hold in general:

1. I have read in a book about Cleopatra that she had both a son and a daughter. My set of beliefs therefore contains both p and q, where p denotes that Cleopatra had a son and q that she had a daughter. I then learn from a knowledgeable friend that the book is in fact a historical novel. After that I contract p∨q from my set of beliefs, i.e., I do not any longer believe that Cleopatra had a child. Soon after that, however, I learn from a reliable source that Cleopatra had a child. It seems perfectly reasonable for me to then add p∨q to my set of beliefs without also reintroducing either p or q. This contradicts Recovery.

2. I previously entertained the two beliefs “George is a criminal” (p) and “George is a mass murderer” (q). When I received information that induced me to give up the first of these beliefs (p), the second (q) had to go as well (since p would otherwise follow from q).

I then I received new information that made me accept the belief “George is a shoplifter” (r). The resulting new belief set is the expansion of K÷p by r, (K÷p)+r . Since p follows from r, (K÷p)+p is a subset of (K÷p)+r. By recovery, (K÷p)+p includes q, from which follows that (K÷p)+r includes q.

Thus, since I previously believed George to be a mass murderer, it follows from Recovery that I cannot any longer believe him to be a shoplifter without believing him to be a mass murderer.

Due to the problematic nature of this postulate, it should be interesting to find intuitively less controversial postulates that ensure that not too much is lost in contraction. The following is an attempt to do that:

Core-retainment: If q ∈ K and q ∉ K÷p, then there is a belief set K′ such that K′ ⊆ K and that p ∉ K′ but p ∈ K′+q.

Core-retainment requires of an excluded sentence q that it in some way contributes to the fact that K implies p. It gives the impression of being weaker and more plausible than Recovery. However, it has been shown that if an operator ÷ for a belief set K satisfies Core-retainment, then it satisfies Recovery.

Attempts have been made to construct operations of contraction on belief sets that do not satisfy Recovery. Arguably the most plausible of these constructions is the operation of severe withdrawal that has been thoroughly investigated by Hans Rott and Maurice Pagnucco (2000). It can be constructed from an operation of epistemic entrenchment by modifying the definition as follows:

q ∈ K÷p if and only if q ∈ K and either p < q or p ∈ Cn(∅).

Severe withdrawal has interesting features, but it also has the following property:

Expulsiveness: If p ∉Cn(∅) and q ∉Cn(∅) then either p ∉K÷q or q ∉K÷p.

This is a highly implausible property of belief contraction, since it does not allow unrelated beliefs to be undisturbed by each other's contraction. Consider a scholar who believes that her car is parked in front of the house. She also believes that Shakespeare wrote the Tempest. It should be possible for her to give up the first of these beliefs while retaining the second. She should also be able to give up the second without giving up the first. Expulsiveness does not allow this. The construction of a plausible operation of contraction for belief sets that does not satisfy Recovery is still an open issue.

3. Revision

The two major tasks of a revision operator * are (1) to add the new belief p to the belief set K, and (2) to ensure that the resulting belief set K*p is consistent (unless p is inconsistent). The first task can be accomplished by expansion by p. The second can be accomplished by prior contraction by its negation ¬p. If a belief set does not imply ¬p, then p can be added to it without loss of consistency. This composition of suboperations gives rise to the following definition of a revision operator (Gärdenfors 1981, Levi 1977):

Levi identity: K*p = (K÷¬p)+p.

If ÷ is partial meet contraction, then the operator * that is defined in this way is partial meet revision. It is the standard operation of revision in the AGM model.

Partial meet revision has been axiomatically characterized. An operator * is an operator of partial meet revision if and only if it satisfies the following six postulates:

Closure: K*p = Cn(K*p)

Success: p ∈ K*p

Inclusion: K*p ⊆ K+p

Vacuity: If ¬p ∉ K, then K*p = K+p.

Consistency: K*p is consistent if p is consistent.

Extensionality: If (p ↔ q) ∈ Cn(∅), then K*p = K*q.

These six postulates are commonly called the basic Gärdenfors postulates for revision. In addition, two supplementary postulates are part of the standard repertoire:

Superexpansion: K*(p&q) ⊆ (K*p)+q

Subexpansion: If ¬q ∉ Cn(K*p), then (K*p)+q ⊆ K*(p&q).

These postulates are closely related to the supplementary postulates for contraction. Let * be the partial meet revision defined from the partial meet contraction ÷ via the Levi identity. Then * satisfies superexpansion if and only if ÷ satisfies conjunctive overlap. Furthermore, * satisfies subexpansion if and only if ÷ satisfies conjunctive inclusion.

4. Possible world modelling

Alternative models of belief states can be constructed out of sets of possible worlds (Grove 1988). In logical parlance, by a possible world is meant a maximal consistent subset of the language. By a proposition is meant a set of possible worlds. There is a one-to-one correspondence between propositions and belief sets. Each belief set can be represented by the proposition (set of possible worlds) that consists of those possible worlds that contain the belief set in question.

For any set A of sentences, let [A] denote the set of possible worlds that contain A as a subset, and similarly for any sentencep let [p] be the set of possible worlds that contain p as an element. If A is inconsistent, then [A] = ∅. Otherwise, [A] is a non-empty set of possible worlds. (It is assumed that ∩∅ is equal to the whole language.) If K is a belief set, then ∩[K] = K.

The propositional account provides an intuitively clear picture of some aspects of belief change. It is convenient to use a geometrical surface to represent the set of possible worlds. In Diagram 1, every point on the rectangle's surface represents a possible world. The circle marked [K] represents those possible worlds in which all sentences in K are true, i.e., the set [K] of possible worlds. The area marked [p] represents those possible worlds in which the sentence p is true.

Diagram 1
Diagram 1. Revision of K by p.

In Diagram 1, [K] and [p] have a non-empty intersection, which means that K is compatible with p. The revision of K by p is therefore not belief-contravening. Its outcome is obtained by giving up those elements of [K] that are incompatible with p. In other words, the result of revising [K] by [p] should be equal to [K]∩[ p].

If [K] and [p] do not intersect, then the outcome of the revision must be sought outside of [K], but it should nevertheless be a subset of [p]. In general:

The outcome of revising [K] by [p] is a subset of [p] that is

(1) non-empty if [p] is non-empty

(2) equal to [K]∩[p] if [K]∩[p] is non-empty

This simple rule for revision can be shown to correspond exactly to partial meet revision.

The revised belief state should not differ more from the original belief state [K] than what is motivated by [p]. This can be achieved by requiring that the outcome of revising [K] by [p] consists of those elements of [p] that are as close as possible to [K]. For that purpose, [K] can be thought of as surrounded by a system of concentric spheres (just as in David Lewis's account of counterfactual conditionals). Each sphere represents a degree of closeness or similarity to [K].

In this model, the outcome of revising [K] by [p] should be the intersection of [p] with the narrowest sphere around [K] that has a non-empty intersection with [p], as in Diagram 2. This construction was invented by Adam Grove (1988), who also proved that such sphere-based revision corresponds exactly to transitively relational partial meet revision. It follows of course that it corresponds exactly to entrenchment-based revision.

Diagram 2
Diagram 2. Sphere-based revision of K by p.

Possible world models can also be used for contraction. In contraction, a restriction on what worlds are “possible” (compatible with the agent's beliefs) is removed. Thus, the set of possibilities is enlarged, so that the contraction of [K] by [p] will result in a superset of [K]. Furthermore, the new possibilities should be worlds in which p does not hold, i.e., they should be worlds in which ¬p holds. In the limiting case when [K] and [¬p] have a non-empty intersection, no enlargement of [K] is necessary to make ¬p possible, and the original belief state will therefore be unchanged. In summary, contraction should be performed according to the following rule:

The outcome of contracting [K] by [p] is the union of [K] and a subset of [¬p] that is

(1) non-empty if [¬p] is non-empty

(2) equal to [K]∩[¬p] if [K]∩[¬p] is non-empty

Belief-contravening contraction is illustrated in Diagram 3. Contraction performed according to this rule can be shown to correspond exactly to partial meet contraction. Furthermore, the special case when the whole of [¬p] is added to [K] corresponds exactly to full meet contraction. The other extreme case, when only one element of [¬p] (a “point” on the surface) is added to [K] corresponds exactly to maxichoice contraction. Thus, in maxichoice contraction by p only one possible way in which p can be false (¬p can be true) is added.

Diagram 3
Diagram 3. Contraction of K by p.

Grove's sphere systems can also be used for contraction. In sphere-based contraction, those elements of [¬p] are added that belong to the closest sphere around [K] that has a non-empty intersection with [¬p]. The procedure is shown in Diagram 4. Sphere-based contraction corresponds exactly to transitively relational partial meet contraction.

Diagram 4
Diagram 4. Sphere-based contraction of K by p.

5. Belief bases

5.1 Increased expressive power

In the approaches discussed above, all beliefs in the belief set are treated equally in the sense that they are all taken seriously as beliefs in their own right. However, due to logical closure the belief set contains many elements that are not really worth to be taken seriously. Hence, suppose that the belief set contains the sentence p, “Shakespeare wrote Hamlet”. Due to logical closure it then also contains the sentence p ∨ q, “Either Shakespeare wrote Hamlet or Charles Dickens wrote Hamlet”. The latter sentence is a “mere logical consequence” that should have no standing of its own.

Belief bases have been introduced to capture this feature of the structure of human beliefs. A belief base is a set of sentences that is not (except as a limiting case) closed under logical consequence. Its elements represent beliefs that are held independently of any other belief or set of beliefs. Those elements of the belief set that are not in the belief base are “merely derived”, i.e., they have no independent standing.

Changes are performed on the belief base. The underlying intuition is that the merely derived beliefs are not worth retaining for their own sake. If one of them loses the support that it had in basic beliefs, then it will be automatically discarded.

For every belief base A, there is a belief set Cn(A) that represents the beliefs held according to A. On the other hand, one and the same belief set can be represented by different belief bases. In this sense, belief bases have more expressive power than belief sets. As an example, the two belief bases {p, q} and {p, p ↔ q} have the same logical closure. They are therefore statically equivalent, in the sense of representing the same beliefs. On the other hand, the following example shows that they are not dynamically equivalent in the sense of behaving in the same way under operations of change. They can be taken to represent different ways of holding the same beliefs.

Let p denote that the Liberal Party will support the proposal to subsidize the steel industry, and let q denote that Ms. Smith, who is a liberal MP, will vote in favour of that proposal.

Abe has the basic beliefs p and q, whereas Bob has the basic beliefs p and p ↔ q. Thus, their beliefs (on the belief set level) with respect to p and q are the same.

Both Abe and Bob receive and accept the information that p is wrong, and they both revise their belief states to include the new belief that ¬p. After that, Abe has the basic beliefs ¬p and q, whereas Bob has the basic beliefs ¬p and p ↔ q. Now, their belief sets are no longer the same. Abe believes that q whereas Bob believes that ¬q.

(In belief set models, cases like these are taken care of by assuming that although Abe's and Bob's belief states are represented by the same belief set, this belief set is associated with different selection mechanisms in the two cases. Abe has a selection mechanism that gives priority to q over p ↔ q, whereas Bob's selection mechanism has the opposite priorities.)

There is only one inconsistent belief set (logically closed inconsistent set), namely the whole language. On the other hand there are, in any non-trivial logic, many different inconsistent belief bases. Therefore, belief bases make it possible to distinguish between different inconsistent belief states.

In belief revision theory it has mostly been taken for granted that belief sets correspond to a coherentist epistemology, whereas belief bases represent foundationalism. However, the logical relationships among the elements of a logically closed set do not adequately represent epistemic coherence. Although coherentists typically claim that all beliefs contribute to the justification of other beliefs, they hardly mean this to apply to merely derived beliefs such as “either Paris or Rome is the capital of France”, that one believes only because one believes Paris to be the capital of France. Therefore, the distinction between operations on belief bases and operations on belief sets should not be equated with that between foundationalism and coherentism.

5.2 Belief base contraction

Partial meet contraction, as defined in Section 2.1, is equally applicable to belief bases. Note that A⊥p is the set of maximal subsets of A that do not imply p, it is not sufficient that they do not contain p. Hence {p ∨ q, p ↔ q} ⊥p = {{p ∨ q}, {p ↔ q}}.

Most of the basic postulates for partial meet contraction on belief sets hold for belief bases as well. However, Recovery does not hold for partial meet contraction of belief bases. This can be seen from the following example (that is adopted from Isaac Levi (2004) who used it for other purposes:

Let the belief set K include both a belief that the coin was tossed (c) and a belief that it landed heads (h). The epistemic agent wishes to consider whether on the supposition that the coin had been tossed, it would have landed heads. In order to do that, it would seem reasonable to remove c from the belief set and then reinsert it, i.e. to perform the series of operations K÷c+c.

(1) If partial meet contraction is performed directly on the belief set, then it follows from Recovery that h ∈ K÷c+c, i.e. h comes back with c. This is contrary to reasonable intuitions.

(2) If partial meet contraction is instead performed on a belief base for K, then recovery can be avoided. Let the belief base be {p1,…pn, c, h}, where the background beliefs p1,…pn are unrelated to c and h, whereas h logically implies c. Then K = Cn({p1,…pn, c, h}). Since h implies c, it will have to go when c is removed, so that K÷c = Cn({p1,…pn}). When c is reinserted, the outcome is (K÷c)+c = Cn({p1,…pn, c}) that does not contain h, as desired.

The following representation theorem has been obtained for partial meet contraction on belief bases (Hansson 1999). An operator ÷ is an operator of partial meet contraction for a set A if and only if it satisfies the following four postulates:

Success: If p ∉ Cn(∅), then p ∉ Cn(A÷ p).

Inclusion: A÷p ⊆ A

Relevance: If q ∈ A and q ∉ A÷p, then there is a set A′ such that A÷p ⊆ A′ ⊆ A and that p ∉ Cn(A′) but p ∈ Cn(A′∪{ q }).

Uniformity: If it holds for all subsets A′ of A that p ∈ Cn(A′) if and only if q ∈ Cn(A′), then A÷p = A÷q.

The Relevance postulate has much the same function as Recovery has for belief sets, namely to prevent unnecessary losses of beliefs.

An alternative approach to contraction of belief bases has been proposed under the name kernel contraction. For any sentence p, a p-kernel is a minimal p-implying set, i.e. a set that implies p but has no proper subset that implies p. A contraction operation ÷ can be based on the simple principle that no p-kernel should be included in A÷p. This can be obtained with an incision function, a function that selects at least one element from each p-kernel for removal. An operation that removes exactly those elements that are selected for removal by an incision function is called an operation of kernel contraction. It turns out that all partial meet contractions on belief bases are kernel contractions, but the converse relationship does not hold, i.e. there are kernel contractions that are not partial meet contractions. In other words, kernel contraction is a generalization of partial meet contraction.

5.3 Belief base revision

The expansion operator for belief sets, K+p = Cn(K∪{p}), was constructed to ensure that the outcome is logically closed. This is not desirable for belief bases, and therefore expansion on belief bases must be different from expansion on belief sets. For any belief base A and sentence p, A +′ p, the (non-closing) expansion of A by p is the set A∪{p}.

Just like the corresponding operators for belief sets, revision operators for belief bases can be constructed out of two suboperations: expansion by p and contraction by ¬p. According to the Levi identity (A*p = (A÷ ¬p)+′ p), the contractive suboperation should take place first. Alternatively, the two suboperations may take place in reverse order, A*p = (A+′p) ÷ ¬p. This latter possibility does not exist for belief sets. If K∪{p} is inconsistent, then K+p is always the same (namely identical to the whole language) independently of the identity of K and of p, so that all distinctions are lost. For belief bases, this limitation is not present, and thus there are two distinct ways to base revision on contraction and expansion:

Internal revision: A*p = (A ÷ ¬p) +′ p

External revision: A*p = (A +′ p) ÷ ¬p

Intuitively, external revision by p is revision with an intermediate inconsistent state in which both p and ¬p are believed, whereas internal revision has an intermediate non-committed state in which neither p nor ¬p is believed. External and internal revision differ in their logical properties, and neither of them can be subsumed under the other.

5.4 Connections between belief bases and belief sets

An operator of contraction on a belief base gives rise to an operator of contraction on its corresponding belief set. Let A be a belief base and K = Cn(A) its corresponding belief set. Furthermore, let − be an operator of contraction on A. It gives rise to an operator ÷ of base-generated contraction on K, such that for all sentences p: K÷p = Cn(A−p). Base-generated contraction has been axiomatically characterized. An operator ÷ on a consistent belief set K is generated by an operator of partial meet contraction for some finite base for K if and only if it satisfies the following eight postulates:

Closure: K÷p = Cn(K÷p)

Success: If p ∉ Cn(∅), then p ∉ Cn(K÷p).

Inclusion: K÷p ⊆ K

Vacuity: If p ∉ Cn(K), then K÷p = K.

Extensionality: If p↔q ∈ Cn(∅), then K÷p = K÷q.

Finitude: There is a finite set X such that for every sentence p, K÷p = Cn(X′) for some X′ ⊆ X.

Symmetry: If it holds for all r that K÷r ⊢ p if and only if K÷r ⊢ q, then K÷p = K÷q.

Conservativity: If K÷q is not a subset of K÷p, then there is some r such that K÷p ⊆ K÷r ⊬p and K÷r ∪ K÷q ⊢ p.

Operators of revision on a belief set can be base-generated in the same sense as operators of contraction.

6. Other operations

The AGM framework has been extended in many ways. Some of these extensions have taken the form of the introducing of new types of operators in addition to the three standard types in AGM, namely contraction, expansion, and revision.

6.1 Update

There are two types of reasons why the epistemic agent may wish to add new information to the belief set. One is that she has received new information about the world, the other that the world has changed. It is common to reserve the term “revision” for the first of these types, and use the term “updating” for the second. The logic of updating differs from that of revision. This can be seen from the following example:

To begin with, the agent knows that there is either a book on the table (p) or a magazine on the table (q), but not both.

Case 1: The agent is told that there is a book on the table. She concludes that there is no magazine on the table. This is revision.

Case 2: The agent is told that after the first information was given, a book has been put on the table. In this case she should not conclude that there is no magazine on the table. This is updating.

One useful approach to updating is to assign time indices to the sentences, as proposed by Katsuno and Mendelzon (1992). Then the belief set will not consist of sentences p but of pairs <p,t1> of a sentence p and a point in time t1, signifying that p holds at t1. In the book-and-magazine example, let t1 denote the point in time that the first statement refers to, and t2 the moment when the second information was given in Case 2. The original belief set contained the pair <¬(p↔ q),t1>. (¬(p↔ q) is the exclusive disjunction of p and q.) Revision by p can be represented by the incorporation of <p,t1>, and updating by p by the incorporation of < p,t2> into the belief set. It follows quite naturally that <¬q,t1> is implied by the revised belief set but not by the updated belief set.

6.2 Consolidation

If a belief base is inconsistent, then it can be made consistent by removing enough of its more dispensable elements. This operation is called consolidation. The consolidation of a belief base A is denoted A!. A plausible way to perform consolidation is to contract by falsum (contradiction), i.e. A! = A÷⊥.

Unfortunately, this recipe for consolidation of inconsistent belief bases does not have a plausible counterpart for inconsistent belief sets. The reason is that since belief revision operates within classical logic, there is only one inconsistent belief set. Once an inconsistent belief set has been obtained, all distinctions have been lost, and consolidation cannot restore them.

6.3 Semi-revision

By non-prioritized belief change is meant a process in which new information is received, and weighed against old information, with no special priority assigned to the new information due to its novelty. A (modified) revision operator that operates in this way is called a semi-revision operator. Semi-revision of K by a sentence p can be denoted K?p. A sentence p that contradicts previous beliefs is accepted only if it has more epistemic value than the original beliefs that contradict it. In that case, enough of the previous sentences are deleted to make the resulting set consistent. Otherwise, the input is itself rejected.

One way to construct semi-revision on a belief base A is to let it consist of two suboperations:

(1) Expand A by p.

(2) Restore consistency by giving up either p or some original belief(s)

This amounts to defining semi-revision in terms of expansion and consolidation:

A?p = (A +′ p)!

This identity cannot be used for belief sets. Since all inconsistent belief sets are identical, an operator ? such that K?p = (K+p)! will have the extremely implausible property that if ¬p1 ∈ K1 and ¬p2 ∈ K2, then K1?p1 = K2?p2. However, other ways to perform semirevision on belief sets have been proposed, in particular, the following two-step process:

(1) Decide whether the input p should be accepted or rejected.

(2) If p was accepted, revise by p.

A simple way to apply this recipe is David Makinson's (1997) screened revision, in which there is a set X of potential core beliefs that are immune to revision. The belief set K should be revised by the input sentence p if p is consistent with the set X∩K of actual core beliefs, otherwise not. The second step of screened revision is a revision of K by p, but with the restriction that no element of X∩K is allowed to be removed.

Another variant of the same recipe is called credibility-limited revision. It is based on the assumption that some inputs are accepted, others not. Those that are accepted form the set C of credible sentences. If p ∈ C, then K?p = K*p. Otherwise, K?p = K. This construction can be further specified by choosing a revision operator and assigning properties to the set C. A variety of such constructions have been investigated. (Hansson et al 2001)

6.4 Selective revision

Selective revision is a generalization of semi-revision. In semi-revision, the input information is either rejected or fully accepted. In selective revision, it is possible for only a part of the input information to be accepted. An operator o of selective revision can be constructed from a standard revision operator * and a transformation function f from and to sentences:

K circ p = K*f(p)

In the intended cases, f(p) does not contain any information that is not contained in p. This is ensured if f(p) is a logical consequence of p. By adding further conditions on f, various additional properties can be obtained for the operator of selective revision.

6.5 Shielded contraction

In shielded contraction, the success postulate of contraction is not universally satisfied. This postulate requires that all non-tautological beliefs are retractable. This is not a fully realistic requirement, since actual agents are known to have beliefs of a non-logical nature that nothing can bring them to give up. In shielded contraction, some non-tautological beliefs cannot be given up; they are shielded from contraction. Shielded contraction can be based on an ordinary contraction operator ÷ and a set R of retractable sentences, so that if p ∈ R, then K−p = K÷p. Otherwise, K−p = K.

This construction can be further specified by adding various requirements on the structure of R. Close connections have been shown to hold between shielded contraction and semi-revision. (Fermé and Hansson 2001)

6.6 Replacement

By replacement is meant an operation that replaces one sentence by another in a belief set. It is an operation with two variables, such that [p/q] replaces p by q. Hence, K[p/q] is a belief set that contains q but not p.

Replacement aims both at the removal of a sentence p and the addition of a sentence q. This amounts to two success conditions, p∉K[p/q] and q∈K[p/q]. However, these two conditions cannot both be satisfied without exception. First, just as for belief contraction, an exception must be made from the first of them in the case when p is a tautology and so cannot be removed. Secondly, the two conditions are not compatible in cases when q logically implies p. This can be dealt with by extending the exception that is provided for in the success postulate for contraction from cases when p ∈ Cn(∅) to cases when p ∈Cn({q}). This gives rise to the following two success conditions:

Contractive success: If p ∉ Cn({q}), then p ∉ Cn(K[p/q]).

Revision success: q ∈ K[p/q]

A replacement operation can be constructed by combining contraction and expansion. The outcome K[p/q] of replacing p by q should be a consistent set that contains q but not p. Thus a subset of K needs to be found, to which q can be added without p being reintroduced. This is equivalent to requiring that this subset of K does not imply q→p. Such a subset can be obtained by contracting by q→p:

K[p/q] = K ÷ (q→p)+q

Replacement can also be used as a kind of “Sheffer stroke” for belief revision, i.e. as an operator in terms of which the other operations can be defined. Contraction by p can be defined as K[p/⊤] and revision by p as K[⊥/p], where ⊥ is falsum and ⊤ is tautology. Provided that the unperformable suboperation of removing the tautology ⊤ is treated as an empty suboperation, expansion by p can be defined as K[⊤/p].

In both positions of the replacement operator, tautology gives rise to an empty suboperation. (Removal of ⊤ is empty since ⊤ cannot be removed. Addition of ⊤ is empty since ⊤ is already in the belief set.) Therefore, it may be instructive to omit ⊤ in the operator. Then [p/ ] denotes contraction, [ /q] expansion, and [⊥/q] revision.

6.7 Multiple contraction and revision

By multiple contraction is meant the simultaneous contraction of more than one sentence. Similarly, multiple revision is revision by more than one sentence.

There are two major types of multiple contraction. In package contraction, all elements of the input set are retracted: they have to go in a package. In choice contraction it suffices to remove at least one of them. Hence, the success conditions for the two types of multiple contraction are as follows:

Package success: If B∩Cn(∅) = ∅ then B∩Cn(A÷B) = ∅

Choice success: If B is not a subset of Cn(∅), then B is not either a subset of Cn(A÷B).

Partial meet contraction and kernel contraction can both be generalized fairly straight-forwardly to both package and choice variants of multiple contraction.

The construction of package revision gives rise to an interesting extension of the notion of negation. The reason why contraction by ¬p is performed as a suboperation of revision by p is that p can be consistently added to a set if and only if it does not imply ¬p. It turns out that (in a logic satisfying compactness) a set B can be consistently added to another set if and only if this other set does not contain any element of the set ¬B, that is defined as follows:

Negation of a set: p ∈ ¬B if and only if p is either a negation of an element of B∪{⊤} or a disjunction of negations of elements of B∪{⊤}.

Therefore multiple revision can be defined from (package) multiple contraction and expansion via a generalized Levi identity:

K*B = (K÷¬B)+B

6.8 Indeterministic belief change

Most models of belief change are deterministic in the sense that given a belief set and an input, the resulting belief set is well-determined. There is no scope for chance in selecting the new belief set. Clearly, this is not a realistic feature, but it makes the models much simpler and easier to handle, not least from a computational point of view. In indeterministic belief change, the subjection of a specified belief set to a specified input has more than one admissible outcome.

Indeterministic operations can be constructed as sets of deterministic operations. Hence, given three revision operators *, *′ and *′′ the set {*, *′, *′′} can be used as an indeterministic operator. The success condition is simply:

K{*, *′, *′′}p ∈{K*p, K*′p, K*′′p}

6.9 Operations for an extended language

Belief revision theory has been almost exclusively developed within the framework of classical sentential (truth-functional) logic. The inclusion of non-truthfunctional expressions into the language has interesting and indeed drastic effects. In particular, this applies to conditional sentences.

Many types of conditional sentences, such as counterfactual conditionals, cannot be adequately expressed with truth-functional implication (material implication). Several formal interpretations of conditional sentences have been proposed. One of them, namely the Ramsey test, is particularly well suited to the formal framework of belief revision. It is based on a suggestion by F. P. Ramsey that has been further developed by Robert Stalnaker and others (Stalnaker 1968). The basic idea is that “if p then q” is taken to be believed if and only if q would be believed after revising the present belief state by p. Let p⇒q denote “if p then q”, or more precisely: “if p were the case, then q would be the case”. In order to treat conditional statements on par with statements about actual facts, they will have to be included in the belief set, thus:

The Ramsey test: (p⇒q)∈K if and only if q∈K*p.

However, inclusion in the belief set of conditionals that satisfy the Ramsey test will require radical changes in the logic of belief change. As one example of this, contraction cannot then satisfy the inclusion postulate (K÷p ⊆ K). The reason for this is that contraction typically provides support for conditional sentences that were not supported by the original belief state. This can be seen from the following example:

If I give up my belief that John is mentally retarded, then I gain support for the conditional sentence “If John has lived 30 years in London, then John understands the English language.”

A famous impossibility theorem by Peter Gärdenfors (1986, 1987) shows that the Ramsey test is incompatible with a set of plausible postulates for revision. (Philosophical Review 95:81-93, 1986) Although several interesting proposals are available, it is fair to say that operations of belief change have not yet been constructed that can deal adequately with conditional or other non-truthfunctional sentences.

7. Repeated change

The preceding sections have only dealt with changes of one and the same belief set or belief base. This is clearly a severe limitation. A realistic model of belief change should allow for repeated (iterated) changes, such as K÷p÷q*r*s÷ t… In other words, operators are needed that can contract or revise any belief set (belief base) by any sentence. Such operators are called global, in contrast to local operators that are defined only for a single specified set.

An obvious way to obtain a global operator of partial meet contraction would be to use the same selection function for all sets to be contracted. However, this is not possible, due to the way selection functions treat the empty set. The way selection functions have been defined, if A⊥p = ∅, then γ(A⊥p ) = {A}. As a consequence of this, if γ is a selection function for A, and A ≠ B, then γ is not a selection function for B. For let A⊥p = B⊥p = ∅. For γ to be a function it must be the case that γ(A⊥p) = γ(B⊥p ). For γ to be a selection function for A it must be case that γ(A⊥p) = {A}, and in order for it to be a selection function for B it must be the case that γ(B⊥p) = {B}. Since A ≠ B, this is impossible.

Therefore, a global operator of partial meet contraction must apply different selection functions to different belief sets (belief bases). A convenient way to achieve this is to introduce two-place selection functions. A two-place selection function γ has two argument places, one for the belief set (belief base) and one for the remainder set. γ(A, A⊥p) is a subset of A⊥p if the latter is non-empty, otherwise it is equal to A. Some formal results on global operations based on two-place selections functions have been obtained.

Epistemic entrenchment has an advantage that makes it one of the more promising approaches to repeated belief change, namely what may be called the self-sufficiency of entrenchment orderings. Given an entrenchment ordering ≤ for a belief set K, K can be “recovered” from ≤ via the simple identity:

K = {q | r<q for some r}

Contractions and revisions can therefore be performed on entrenchment orderings rather than on belief sets. Thus, given a belief set K and an entrenchment ordering ≤ for K, when contracting by a sentence p the outcome should be a new entrenchment ordering ≤′. It automatically provides a new belief set, namely the set {q | r<′q for some r}. If the operation has been successful, then this new belief set should not contain p.

It has turned out to be quite difficult to construct a satisfactory method to contract or revise an entrenchment ordering. The most interesting proposals involve a rather radical departure from the traditional AGM framework in which epistemic entrenchment is usually discussed. Hence, Abhaya Nayak (1994) has proposed that not only the belief states but also the inputs should be binary relations (that satisfy the standard entrenchment postulates except Minimality). Inputs of this type may be seen as “fragments” of belief states, to be incorporated into the previous belief state. In the same vein, Eduardo Fermé and Hans Rott (2004) have investigated belief revision with inputs of the more general form: “accept q with a degree of plausibility that at least equals that of p”. They call this revision by comparison. Belief states are represented by entrenchment orderings. Hence, from an entrenchment ordering ≤ and such a generalized input a new entrenchment ordering ≤′ is obtained that contains the information needed to construct the new belief set.

As this example illustrates, many of the more recent developments in belief change show a need to go beyond the expressive power of the AGM model, but that model is still the standard model to which all other models of belief change are compared.

Bibliography

Citations annotated in gray refer to books or articles that are recommended for further introductory reading.

Other Internet Resources

Related Entries

logic: conditionals | logic: non-monotonic | reasoning: defeasible