Modeling Belief Change using Counterfactuals

Tom Costello^{∗} Computer Science Department Stanford University Stanford, CA 94305 email: costello@steam.Stanford.EDU

Abstract

We can represent how to change our beliefs in the light of new information by using a conditional “if A is the case, then we should accept B”. We propose that this belief change conditional should be defined as material implication when A is consistent with our current beliefs, and as a suitable counterfactual in the other case. We show that the resulting belief change system obeys the rationality postulates suggested by Alchourrón, Gärdenfors, and Makinson. To get an exact correspondence between systems of belief change thus defined in terms of counterfactuals, and systems based on rationality postulates, it is more intuitive to modify the usual “closest possible world” models of counterfactuals, so that different similarity measures centered at the same world are cotenable, and all worlds are ranked. Once this is done we can achieve a correspondence between finite sequences of belief changes using rationality postulates and models of a counterfactual. The valid counterfactual sentences do not constitute a possible state of belief. They do not decide enough sentences. However, we can specify a state of belief, by adding the additional sentences, that describe the fact that we believe no counterfactuals, save those that we have explicitly been told. This characterizes a “tabula rasa” or blank slate, upon which we can impose any belief change system, by revising it with the sentences that characterize the defaults of that belief change system.

1 Motivations

Changing ones mind is the prerogative of every fallible reasoner. We are constantly told new information that we must assimilate. That information can neatly be split into two parts; new facts that contradict our current beliefs, and facts that we currently have no opinion about.

There is considerable agreement about how to deal with the second case. We should conjoin the new information to our current beliefs. The first case is more problematic however. Clearly conjoining the information will lead to inconsistency. One feels tempted to assent to the new belief, but one does not want to give up all ones old beliefs.

A solution to this quandary might be found in counterfactuals. They are propositions of the form,“if … were the case, then … would be the case.”, where the left hand side is contrary to our current beliefs.

There are several semantics that state what counterfactuals are true based only on which facts about the world are true, and some notion of what other worlds might be most likely. Perhaps the best known of these is the “official logic” for counterfactual conditionals, Lewis’s VC. We intend to use counterfactuals to tell us what facts in our present corpus we should retain. However, we differ from Lewis in that we consider only what worlds are most likely when giving truth conditions to our counterfactual. We do not use what facts are true in the actual world.

Every belief change conditional A > B can be divided into two parts—the material conditional, which is appropriate when we do not believe ¬A, and the counterfactual part, which is appropriate when we believe ¬A. These parts can define the belief change conditional.

If A > B is the belief change conditional, we can relate our counterfactual conditional ≻ to >^{1} by the following identity.

∗ The author thanks Anna Patterson, John Mc-Carthy, Grigori Mints, and Johan van Benthem for helpful discussions.

(Change) Γ ⊧ A > B ≡^{def}

if Γ ⊧ ¬A then Γ ⊧ A ≻ B else Γ ⊧ A → B

This approach to conditionals allows a very simple formalization of how beliefs change in the light of new information. It avoids the problems, exposed by Lewis and Gärdenfors[Lewis, 1976, Lewis, 1991, Gärdenfors, 1986, Gärdenfors, 1988], that arise when belief change conditional is added to the language as an operator.

Adding a new connective to the language also avoids the problems exposed by Lehmann[Lehmann, 1995]. He points out that there are strong arguments against treating belief states, that have exactly the same sentences true in them, identically. He argues the change should also depend on the pedigree of the beliefs. As we represent more information, by having an extra connective ≻, we can have theories with the same ≻- free sentences, that are not identical.

2 Outline of the Paper

We wish to develop a model of belief change, based on the idea that we can use counterfactual conditionals to model how we change our mind when we find we are mistaken. When we find we are under-informed, we intend to conjoin the new information. To carry out this plan we need a model of counterfactuals, and a model of belief change.

We first look at a model of counterfactuals proposed by Lewis. It is based around the idea that a counterfactual A ≻ B is true if the corresponding implication A → B is true at the closest worlds where A is true. As a model of counterfactuals this system is not completely natural as it does not allow us to consider different similarity measures on the same world—each world must have a unique ordering on worlds assigned to it. It is natural to imagine that there are different possible orders of the same set of worlds. Furthermore this model makes the counterfactual A ≻ B agree with the material conditional when A is the case. Thus it gives truth conditions to this conditional, when it is not counterfactual.

The next model we look at seem superficially very similar to Lewis’s. It is Grove’s model [Grove, 1988] of the belief change postulates proposed by Alchourrón, Gärdenfors, and Makinson (AGM) [Alchourrón et al., 1985]. It is intended to deal with incomplete knowledge. Sadly, as shown by Gärdenfors[Gärdenfors, 1986, Gärdenfors, 1988] it cannot represent conditionals in its language, if the conditionals are to represent the notion of belief change itself.

Our solution to this problem is to propose a new model, that allows both nested counterfactual conditionals and incomplete knowledge. It combines some of the features of both models. Its most critical idea is that the underlying propositions that are believed are not objective propositions and the conditionals corresponding to belief change, but rather, objective propositions, and counterfactual conditionals. The belief change conditional is definable from the counterfactual conditional and objective propositions, but is not a “first class” belief. The critical change is that we only preserve the counterfactual conditional and the objective propositions. To stress the importance of this decision we list this as the assumption ≻.

(≻ ≻ ≻) Our language contains ≻ as its only non truth functional connective.

We present a new model of counterfactuals and show that, when (Change) is used to specify belief change in terms of this counterfactual, we get a system that obeys each of AGM’s eight postulates. We thus suggest a new postulate, essentially the counterfactual part of Change that relates belief change to counterfactuals. This postulate completes the rationality postulates, in that it completely determines revision in terms of the logical connectives and ≻. We give theorems relating our postulates to our semantics. Namely, every set of iterated AGM revisions can be captured in our model. Thus we show a correspondence between rational belief change as defined by postulates and using (Change) to define belief change in terms of counterfactuals.

Finally we consider what state of belief is most appropriate to choose as an initial state. We show that we can define a set of sentences that capture the idea that initially we should believe as few counterfactuals as possible.

3 Previous Work

3.1 Lewis

Lewis suggested a semantics of conditionals based on a system of spheres. The basic notion is a sphere of accessibility, or alternately a set of possible worlds. To each possible world i he assigned a set of spheres of accessibility 𝕊_{i}^{2}. This assignment is constrained to meet certain formal constraints.

1Throughout the paper, we use > to refer to a belief change conditional, and ≻ to refer to a counterfactual conditional.

• C Centering {i} ∈ S_{i}.

• 1 Nesting: ∀S ∈ S_{i}, T ∈ S_{i}.T ⊂ S ∨ S ⊂ T.

This system of spheres carries the notion of similarity of worlds. Each sphere around a world i contains exactly those worlds that resemble i to a certain degree. We write that a proposition A is true in a world w as w ⊧ A. We can now define Lewis’s counterfactual conditional as:

i ⊧_{Lewis} A ≻ B =^{def}

∀S ∈ S_{i}, w ∈ S.w |̸= A or ∃S ∈ S_{i}, w ∈ S.w ⊧ A and ∀w′ ∈ S.w′ ⊧ A → B

The first alternative gives the vacuous case where there is no world where A is possible, the second states that we judge A ≻ B to be true if in the closest worlds where A is true, B is true.

Thus Lewis suggested that we could judge conditionals by appealing to what is essentially a “well-founded”^{3} total pre-order on worlds. We can see that the system of spheres induces a total pre-order, where w ≤ w′ iff ∃S.w ∈ S ∧ w′ ∉ S.

Thus Lewis’s system is designed to capture that part of our beliefs that will be useful when we commit sins of commission, when we find a new fact that contradicts our old beliefs.

Lewis’s system can be axiomatized in the following way, as he originally proposed,

\frac{A, A → B}{B}

all truth functional tautologies

\frac{C_{1} ∧ … ∧ C_{n} → B}{((A ≻ C_{1}) ∧ … ∧ (A ≻ C_{n})) → (A ≻ B)} for n ≥ 1

A ≻ A (¬A ≻ A) → (B ≻ A) (A ≻ ¬B) ∨ (((A ∧ B) ≻ C) ≡ (A ≻ (B → C)))

\begin{matrix}(A ≻ B) → (A → B) \\ (A ∧ B) → (A ≻ B) \end{matrix}

or in the manner of Gärdenfors[Gärdenfors, 1978], to mirror revision style semantics, or using the notation of non-monotonic consequence relations which we now present.

All valid principles of propositional logic Replacement of Provable Equivalents

A ≻ A  Reflexitivity
\frac{A ≻ B}{A ≻ (B ∨ C)}  Right Monotonicity

\frac{A ≻ B, A ≻ C}{A ≻ (B ∧ C)} Conjunction

\frac{A ≻ B, C ≻ B}{(A ∨ C) ≻ B} Disjunction

\frac{A ≻ B, A ≻ C}{(A ∧ B) ≻ C} Cautious Monotonicity

\frac{A ≻ B, ¬(A ≻ C)}{(A ∧ ¬C) ≻ B} Rationality

\frac{T rue ≻ A}{A}  Centering

These systems are equivalent. The second is equivalent as shown by Burgess[Burgess, 1981]. We give the second axiomatization, as it will bear much similarity to the way in which we axiomatize our conditional, and shows how similar counterfactual reasoning is to work in non-monotonic consequence relations[Kraus et al., 1990].

It is worth noting that although Lewis’s system is designed to deal with counterfactual conditionals, it also gives truth conditions for conditional sentences that are not counterfactual, that is sentences whose premise is not counterfactual. In this case, Lewis gives the conditional the same truth value as the material conditional. This is seen in his axiom, (A ≻ B) → (A → B). This has a consequence, (T rue ≻ A) → A, the assumption of centering.

3.2 Grove

Grove suggested a semantics for the AGM postulates for belief revision. He characterized the conditional “if I revised my beliefs to accommodate A, the I would would believe B”. He also uses a system of spheres, but his system differs from Lewis’s. Rather than define what conditionals are true at a world, he starts by defining what conditionals are true at a set of worlds. We note that he implicitly rejects the idea that one can determine what conditionals are true at a set of worlds by looking at the conditionals true at each world in that set,

2We use A, B, C, D for propositions or sentences. We use w, i, j, k for worlds, which we consider set of propositions. We use K, M, N, Γ, Δ, Θ for sets of sentences. We use L for languages. We use W, R, S for sets of worlds, and calligraphic letters for sets of sets of worlds, S, W, R, S.

We use 𝕊 for rich states of belief. We use P for propositional letters, and P for sets of propositional letters. We use K for sets of sets of sentences.

3The condition is not exactly well-foundedness, but Kraus et al.’s [Kraus et al., 1990] smoothness.

We write [A] for the set of worlds that satisfy a proposition A. His spheres are also sets of possible worlds. There is a system of spheres corresponding not to each world, but to each set of worlds. Thus instead of the system of spheres from a world i we have the system of spheres around a set of worlds [K]. The smallest sphere is the sphere [K], that is the set of worlds itself. Contrast this with Lewis who has a systems of spheres associated with a single world. The largest sphere is all the worlds. For every sentence A, the set of spheres around a set [K] that contain worlds that satisfy A has a minimum, in the sense of set inclusion. We call this minimum S_{A}.

Grove’s interpretation of the conditional is, for a system of spheres, centered on the set [K],

K ⊧_{Grove} A > B =^{def} B ∈ ⋂_{w∈[A]∩S_{A}} w

We see that the conditional is defined as B being true in the smallest worlds where A is true. Grove’s system tells us how to add to our knowledge. If A is not the case in [K], but [K] ∩ [A] is non-empty then we find ourselves at the set of worlds [K] ∩ [A]. In the case that [K] ∩ [A] is empty, then we find ourselves in a system very much like Lewis’s. The key insight for us, is that we can represent our partial knowledge of the world by a set of possible worlds, and that we can represent revision by selecting out the subset of these worlds where the new fact is the case, when this subset is non-empty.

It is worth noting that the Grove semantics do not give a semantics to nested conditionals. We might imagine that we could use the set of worlds picked out by S_{A}, to give a new set of worlds from which to further judge the truth of sub-formulas. Grove does not do this because his intent was to capture a set of postulates, proposed by AGM, that render trivial extending the semantics in this way.

3.3 Nesting

There has been some work that considers nested conditionals. Adams [Adams, 1975] has suggested that A > (B > C) might be read as A ∧ B > C, under suitable restrictions.

Lehman[Lehmann, 1995] suggests seven postulates that both strengthen and weaken, in some ways, the AGM postulates, by adding Darwiche and Pearl’s[Darwiche and Pearl, 1994] C1, and a weaker version of their C2, which Freund and Lehmann[Freund and Lehmann, 1994] showed was inconsistent. He weakens the postulates by cropping the implicit assumption that revision is functional on theories. This work has a close connection with non-monotonic consequence relations. In this system revising one’s beliefs by A is equivalent to adding the weakest sentence that non-monotonically implies A if A is consistent with the current beliefs. Note that this is consistent with the current monotonic beliefs, not with the non-monotonic consequences of those beliefs.

4 Rationality Postulates

Alchourrón, Gärdenfors, and Makinson give eight rationality postulates that they claim every belief change system should obey. Before we can speak of these postulates we must first introduce some notation.

Definition: 1 (Language) A language L is identified with a set of sentences. We will consider languages that contain all the truth functional connectives, {∧, ∨, →, ¬, ≡}, a set of propositional atoms P, a conditional connective ≻, and the additional constants ⊥ and T. The rules for constructing sentences are the standard ones. We call this L_{P}^{≻}. We call the language without ≻, L_{P}^{classical}.

Definition: 2 (State of Belief) A state of belief K_{L} over a language L, is a logically closed subset of the sentences of the language L.

We use Cn({A_{1}, …, A_{n}}) to refer to the logical closure of the set of sentence {A_{1}, …, A_{n}}. We use K+A to refer to the logical closure of the set K ∪ {A}.

Definition: 3 (Revision) We define the revision of a state of belief K_{L}, by a sentence A in L, as K_{L} ∗ A. When the language is fixed we drop the subscript L.

K ∗ A represents the state of belief which is the result of minimally changing K to include A.

We can now define a belief revision system.

Definition: 4 (Belief Revision System) A belief revision system, ⟨K, ∗⟩, is a sets of states of beliefs, over a language L, and a function ∗ from pairs of states of belief and sentences, to states of beliefs ∗ : K×L → K.

We can now state the eight postulates proposed by AGM:

(R1) K ∗ A is deductively closed.
(R2) A ∈ K ∗ A.
(R3) K ∗ A ⊆ K + A.
(R4) If ¬A ∉ K then K + A ⊆ K ∗ A.
(R5) K ∗ A = Cn(⊥) if and only if ⊧ ¬A.
(R6) If ⊧ A ≡ B then K ∗ A = K ∗ B.
(R7) K ∗ (A ∧ B) ⊆ (K ∗ A) + B.
(R8) If ¬B ∉ K ∗ A then (K ∗ A) + B ⊆ K ∗ (A ∧ B).

These postulates do not fully constrain belief change. Indeed, we need to add extra information, in the form of a choice of sphere around each set of worlds in Grove’s model, or an entrenchment ordering from Gärdenfors [Gärdenfors, 1988], or a partial meet contraction function [Alchourrón et al., 1985], to characterize a belief change operator exactly. Rather than add one of these ordering principles outside the language, we propose to add a new rationality postulate:

(Counter) If ¬A ∈ K then B ∈ K ∗ A if and only if A ≻ B ∈ K.

This will uniquely give a belief change system. We show this in Theorem 3. However to make sense of this postulate we need a semantics for the counterfactual ≻.

The idea behind (Counter) is that when we believe ¬A, we should change our beliefs as we would when we consider a counterfactual. In any other case, (R3) and (R4) will apply and fully describe the revision.

This approach, of using a conditional to define belief change seems very close to work done by Gärdenfors in [Gärdenfors, 1988]. The major difference is that we only characterize belief change using the conditional when the conditional is truly a counterfactual, i.e. when (R4) does not apply.

5 Expanding Counterfactual Semantics

We wish to define a belief revision conditional in terms of counterfactuals. However when we attempt to do this we see two problems in Lewis’s standard model. The counterfactuals that are true are indexed only by a world. We wish to have our semantics capture states of belief, and thus identify worlds and sets of propositions.

If we take a commonly considered counterfactual:

If Otto had come to the party, it would have been a good party.

Some people may consider this true, and others false. They may differ on their beliefs, not because the objective facts they know about reality differ, but instead because one person considers the world where Otto came and the party was good, closer than the world where Otto came and the party was bad, and the other person does not. They can differ on what they consider the ranking on worlds, without differing on what they believe the current world to be.

Lewis’s model insists that each world have a unique ranking associated with it. He speaks of the system of spheres associated with each world. We can generalize his semantics by allowing the same world to have different system of spheres around it. Once we do this it is clear that the system of spheres should rank pairs of worlds and systems of spheres, not worlds.

Lewis did not include this freedom in his semantics, but it makes very little difference, as the semantics allow arbitrary many copies of worlds that agree on all propositions.

We wish to be able to work out, from a “state of belief”, what counterfactuals that reasoner should believe. We thus want to have as our objects states of belief, rather than worlds. Unless the state of belief includes some representation of the similarity measure it uses, we will not be able to calculate what counterfactuals should be accepted. To represent the state of belief that results after being told a previously denied proposition, as a set of conditionals, the the truth conditions of the counterfactual must bring us not to a new world, but to a full state of belief, that is, a world and a new similarity measure on state of belief. For this reason we need the primary index in the satisfaction relation, or the state of belief, to be a set of assignments to objective propositions, and an order on states of belief.

The second difference between our system and Lewis’s is that we do not care what the truth conditions of counterfactuals are when their premises are not contradictory with what we currently believe. This might seem like a minor point, however it allows us to simplify the system somewhat. In particular, we lose the axiom corresponding to centering. This is what allows us to avoid the unnecessary updating of conditionals, when we revise our beliefs by accepting consistent new information.

The third difference between our semantics and Lewis’s is that we wish that the conditional A ≻ ⊥ be true only when A is contradictory. Thus every state of belief smoothly orders all other states of belief.

6 Our Semantics

Our basic unit is a rich state of belief ⟨W, ≤⟩, a set of worlds W, which capture what sentences in the object language we consider possible, and a total order on rich states of belief^{4}. Our total order plays the same role as Lewis spheres. This is the semantical notion that parallels the syntactic states of belief we saw earlier. We note that we use a total order, rather than a total pre-order. This difference will be dealt with in the definition of the satisfaction relation.

Definition: 5 (Rich State of Belief) A rich state of belief, 𝕊 over a set of propositional atoms P, is a pair ⟨W, ≤_{P}⟩, a set of worlds W, identified with subsets of P, and a smooth^{5} total order on rich states of belief over P.

We write the set of all rich states of belief over P as W_{P}.

It should be stressed that our semantics agree with Lewis’s semantics on all conditionals, save that we add that a proposition conditionally implies false only when it is logically equivalent to false as we wish to avoid contradiction for as long as possible.

Definition: 6 (↓_{≤} A) If 𝕊 = ⟨W, ≤⟩, is a rich state of belief, and W′ ⊂ W, W′ ≠ ∅ then we say that ⟨W′, ≤⟩ is a sub-state of 𝕊.

We define ↓_{≤}^{∗} A to be the smallest state under the pre-order ≤, that has a sub-state that models A.

We define ↓_{≤} A to be the sub-state of ↓_{≤}^{∗} A that models A, and whose set of worlds is maximal among the sub-states of ↓_{≤}^{∗} A that model A.

We now define satisfaction or ⊧_{T} a relation between rich states of beliefs and propositions. We now inductively define the satisfaction relation between rich sates of belief and formulas.

Definition: 7 (⟨W, ≤⟩ ⊧_{T} A) We now define the satisfaction relation for our system ⊧_{T}. It is a relation between a rich state of belief in W_{P}, and a sentence in the language L_{P}^{≻}. We define it using structural induction over the language L_{P}^{≻}.

• ⟨W, ≤⟩ ⊧_{T} P if and only if ∀w ∈ W.w ⊧_{T} P.

• ⟨W, ≤⟩ ⊧_{T} ¬A if and only if , ∀w ∈ W.⟨{w}, ≤⟩ |̸=_{T} A.

• ⟨W, ≤⟩ ⊧_{T} A ∧ B if and only if ⟨W, ≤⟩ ⊧_{T} A and ⟨W, ≤⟩ ⊧_{T} B.

• ⟨W, ≤⟩ ⊧_{T} A ≻ B if and only if ∀W′, ≤′ .⟨W′, ≤′⟩ ⊧_{T} ¬A or ↓_{≤} A ⊧_{T} B

This gives us a notion of truth at a rich state of belief.

7 Completeness

We can axiomatize our system, using the axioms of V, that is the axioms of VC less centering, and the axiom that a proposition counterfactually entails false, only when it is itself contradictory. We denote provability in this system as ⊢_{T}. It axioms are the axioms of V, plus,

A ≻ ⊥ → ⊢_{T} ¬A.

We note that this notion of derivation is recursively defined in the sense that its axioms refer to its own notion of derivation. We therefore can have more than one fixed point for the set of theorems. We take the smallest fix-point as our definition, that is, a sentence is only derivable if it is derivable in every fix-point.

We now show the completeness of ⊢_{T} for our semantics. We follow the usual method of making the objects of our model from sets of sentences. The sets of sentences that we associate with rich states of beliefs are those sets Δ, of the form Δ = {A|B ≻ A ∈ Γ}, for some maximally consistent set of sentences Γ, and sentence B. We use Γ to refer to a maximally consistent set of sentences, and Δ to refer to a set of the form {A|B ≻ A ∈ Γ}. We call sets of the form {A|B ≻ A ∈ Γ}, for Γ maximally consistent, premaximal sets.

We associate a rich state of belief S with a pre-maximal set of sentences Δ in the following way. We take the valuations of S to be the worlds that model those conditional free sentences A, such that A ∈ Δ. We note that this differs from the usual method of associating a valuation with state of belief. More normally we would associate the set of letters the state of belief contained as its valuation. The reason we do not do this is because we are interested in having states of belief that have more that one valuation.

4Our semantics of conditional are best explained in terms of non-well-founded sets. As our model of non-well-founded sets we take ZF with urelements, with AAFAA, that is Aczel’s Anti-foundation Axiom with Atoms. This states that there is a set associated with every labeled directed graph. It is the use of non-well-founded sets that allows this recursive definition. Rather than use nonwell founded set theory we could use any of the techniques for constructing models of the untyped lambda calculus[Scott, 1972, Plotkin, 1975]. Our treatment is similar to von Rimsha’s[von Rimscha, 1980] non-well founded model of the untyped lambda calculus.

5We mean smooth in Kraus et al.’s sense, that is that every definable subset has a least element.

The proof goes by a series of lemmas. We first show that there is a unique non-empty set of worlds associated with each pre-maximal set of sentences Δ. We next show that we can make a total order on rich states of belief from the order we read off. Next we show that all the sentences in a pre-maximal Δ are true in some rich state of belief made from Δ. This is the model for Δ.

We define a pre-state of belief to be a set of worlds and a binary relation in pre-state of belief.

Definition: 8 We define the function S(Δ) from premaximal sets of formulas Δ to pre-states of belief as follows. We let S(Δ) = ⟨W, ≤⟩, then

• W is the largest set of worlds such that if W ⊧ B, B conditional free, then B ∈ Δ.

• If A ∨ B ≻ A ∈ Δ, then S{α|A ≻ α ∈ Δ} ≤ S{β|B ≻ β ∈ Δ}.

Lemma: 1 If S(Δ) = ⟨W, ≤⟩, for some consistent pre-maximal set of sentences Δ, then there is a unique maximal W.

Proof: We consider the conditional free, non-refutable sentences B such that B ∈ Γ. It is logically closed, as the logic is closed under substitution by equivalents. Thus it is the theory of a set of worlds. Clearly there is no larger set with this property.□

Lemma: 2 Given a pre-maximal consistent set of sentences Δ, then the relation, A ≤ B as,

A ≤ B iff A ∨ B ≻ A ∈ Δ

is a total order on sets of logically equivalent sentences.

Proof: We need to show this is transitive, comparable and reflexive. Reflexitivity follows from right weakening and left logical equivalence, comparability from cumulativity, Or, and rationality, and transitivity follows from Or, Left Logical Equivalence, Right Weakening and cautious monotonicity. □.

Lemma: 3 The function S can be extended to a function from pre-maximal sets of sentences to rich states of belief.

Proof: We need to show that S(Δ), for a consistent set of sentences Δ, can be extended to a rich state of belief. To do this we note that it is already a set of worlds and a total order on pre-states of belief. We thus need to extend the total order to all rich states of belief. We can do this by choosing a smooth total order on rich states of belief and using this order to order all rich states of beliefs not ordered by S. □

We call this new function to rich state of beliefs S(Γ).

Lemma: 4 For all A ∈ Δ,, Δ pre-maximal, S(Δ) ⊧ A

Proof: We show this by induction on the structure of A.

• A = p. Immediate from definition of S(Γ).

• A = B ∧ C. Immediate from the definition of ⊧, and the induction hypothesis.

• A = B ∨ C.Immediate from the definition of ⊧, and the induction hypothesis.

• A = ¬B. Immediate from the definition of ⊧, and the induction hypothesis.

• A = B ≻ C. We need to show that in the minimal rich state of belief where B is true C is the case. We this need to show that that C is true in ({A|B ≻ A ∈ Δ}). But, by assumption, B ≻ C ∈ Δ, thus from the induction hypothesis, C is true in, S({A|B ≻ A ∈ Δ}), as it is an element of {A|B ≻ A ∈ Δ}.

□

Thus we have completeness. The system can be shown to be sound in the usual manner.

8 Belief Revision from Conditionals

A belief revision system can be defined from a conditional and a satisfaction relation in a simple manner. We can define K ∗ A to be exactly those sentences B such that the conditional A > B is true in the rich state of belief K.

Definition: 9 (Belief Revision based on > and ⊧_{T}) The belief revision system based on a conditional > and a satisfaction relation ⊧_{T}, and a set of belief states K = W_{P}, is the pair consisting of the set of belief states and the function ∗_{>,⊧_{T}}, from belief states to belief states, such that for all K ∈ K and sentences A, B:

(B ∈ K ∗_{>,⊧_{T}} A) ≡ (K ⊧_{T} A > B)

This definition is sometimes referred to as the Ramsey Test. We now define a belief revision system based on the set of belief states in our model of ⊧_{T} and the conditional defined in terms of the material and counterfactual conditional.

Lemma: 5 (>) The belief revision conditional > was defined in terms of ≻ and the material conditional. We note that:

𝕊 ⊧_{T} A > B ≡ if 𝕊 ⊧_{T} ¬A then \begin{matrix}𝕊 ⊧_{T} A ≻ B else \\ 𝕊 ⊧_{T} A → B \end{matrix}

Proof: We expand the definitions of ⊧_{T}. □

Definition: 10 The belief revision system ℭ is defined to be the pair ⟨W_{P}, ∗_{>,⊧_{T}} ⟩.

Theorem: 1 The belief revision system ℭ obeys the AGM postulates.

Proof: We consider each of the AGM postulates in turn.

R1 Immediate as both material and counterfactuals right hand side is closed under implication.

R2 Immediate as ⊧ A → A and ⊧_{T} A ≻ A.

R3 We have two cases. When ¬A ∈ K then K + A = Cn(⊥), which is all sentences. When ¬A ∉ K we have K ∗ A = {B|A → B ∈ K}, which is exactly K + A.

R4 Again when ¬A ∉ K we have K ∗ A = {B|A → B ∈ K}, which is exactly K + A.

R5 We have two cases. Firstly when ¬A ∉ K then we have |̸= ¬A. We know K ∗ A = {B|A → B ∈ K} which is not all sentences, as it does not contain ¬A. Secondly when ¬A ∈ K, if ⊧ ¬A then there is no state of affairs that satisfies it, and thus no minimal state. Therefore all sentences are the case. If all sentences were the case, on the chosen state of affairs, it must be because there was no state that modeled A, and thus ⊧ ¬A.

R6 Immediate by extensionality of all rules.

R7 We again split on the two cases. Firstly ¬(A ∧ B) ∉ K then K ∗ (A ∧ B) = {C|A ∧ B → C ∈ K}. This is K + (A ∧ B), which is a subset of (K ∗ A) + B, as by (R3) K ∗ A ⊂ K + A, and K+A+B = K+(A∧B). Secondly ¬(A∧B) ∈ K, then the K ∗ (A ∧ B) are the sentences true in the state of smallest state of affairs where A ∧ B are the case. Also K ∗ A is the smallest set of affairs where A is the case. Now either ¬B ∈ K ∗ A, in which case (K ∗ A) + B is all sentences, or ¬B ∉ K ∗ A, in which case the smallest state of affairs that does not contradict A ∧ B is the smallest set of affairs that does not contradict A, and we have an equality.

R8 Following the previous analysis we have the equality, or if ¬(A ∧ B) ∉ K, then we the equality by K + (A ∧ B) = (K ∗ A) + B.

□

Theorem: 2 The belief revision system ℭ obeys the postulate Counter.

Proof: We note that if ¬A ∈ K then A > B is defined to be A ≻ B. □

Theorem: 3 The postulate Counter and AGM postulates uniquely specify a revision.

Proof: We assume that we are revising a belief state K with a sentence A. We have two cases. Either ¬A ∈ K, in which case the new state of belief is exactly {B|A ≻ B ∈ K}, or ¬A ∉ K in which case K = K+A. □

Theorem: 4 The AGM postulates are derivable from Change, the axioms of V, and consistency preservation.

Proof: We consider the other 6 postulates in turn.

• R1: This follows from Conjunction and the replacement of logical equivalents.

• R2: This follows from A > A, and A → A.

• R3: This follows from Change, and the fact that if ¬A ∈ K, then K + A is all sentences.

• R4:, This is the forward direction of the first conjunct of Change.

• R5: This follows from consistency preservation, as if ⊥ ∈ K then A ∈ K, so we use Counter to revise, and Counter is a consequence of Change.

• R6: This follows from the replacement of logical equivalents.

• R7: If A∧B is consistent with K then this follows from Change. Otherwise, if A is consistent with K, then K ∗ A = K + A. Now if B is inconsistent with K +A, then (K ∗A)+B is all sentences, and thus R7 is true. If B is consistent with K+A, then (K ∗ A) + B is K + A + B, which is K + (A ∧ B), but this is K ∗ (A ∧ B), thus R7 is established in this case. This leaves the possibility that A is inconsistent with K. In this case we have two sub-cases, either K ∗ A is inconsistent with B, in which case, (K∗A)+B = Cn(⊥), establishing R7, or K ∗ A is consistent with B. Thus (K ∗ A) + B is {C|A ≻ B → C ∈ K}. We also know that, by the fact that A ∧ B is inconsistent with K if A is, that K ∗ (A ∧ B) is {C|A ∧ B ≻ C ∈ K}. Thus we need to show that A ∧ B ≻ C ∈ K and ¬(A ≻ ¬B) ∈ K implies that A ≻ B → C ∈ K. But this is derivable from Or, Cautious monotonicity, and Rationality.

• R8: We have two cases, either ¬A is in K, in which case, K ∗ A = {C|A ≻ C ∈ K}, thus (K ∗ A) + B = {C|A ≻ B → C ∈ K}. But as we know ¬B ∈ K ∗ A, we need to show that A ≻ (B → C) ∧ ¬(A ≻ ¬B) → (A ∧ B ≻ C). But by rationality we have, A ≻ D ∧ ¬(A ≻ ¬B) → (A ∧ B ≻ D), so choosing B → C for D, and using Conjunction and replacement interderivables we have the required inclusion. The other case is when ¬A ∉ K, in which case both sides are equivalent to K + A + B.

Theorem: 5 Let L_{P}^{classical} be a language, then every set of finite sequences of AGM revisions H of a given belief state K ⊂ L_{P}^{classical} is captured by a model of ℭ, in the sense that there is a rich state of belief S(H) such that,

\begin{matrix}If B ∈ (… ((((K ∗_{1} A_{1}) ∗_{2} …) ∗_{n} A_{n} ∈ H then \\ S(H) ⊧_{T} (A_{1} > (A_{2} > … > (A_{n} > B))))) …) \end{matrix}

Proof: We construct a rich state of belief that models the set of sequences of AGM revisions H. We do this by using the Grove models for each of the revision operators.

We construct the rich state of belief by induction on the depth of nesting of revisions that are not conjunctions in H.

If there are no revisions that are not modeled by conjoining the sentences, then we model H by the set of worlds that model K, and an arbitrary order on rich state of belief.

If the nesting in H of revisions that are not modeled by conjoining the sentences is n, then construct a rich state of belief from the Grove model, in the following ways. We take the minimal worlds in the Grove model of the first revision as our set of worlds. We replace his total-pre-order on worlds, by the rich states of belief, with those sets of worlds, that correspond to the sub-sequences of revisions that have a nesting of n − 1 revisions that are not modeled by conjoining the sentences.

As Grove’s model is a model of any set of sequences of revisions, where each sequence contains at most one revision K′ ∗ A, such that ¬A ∈ K′, and that revision, if it exists, is the last revision in the sequence, we know that this rich state of correctly captures the first counterfactual revision. However, as the result of revising the rich state of belief, is another rich state of belief, that correctly captures the next sequence of revisions of this type, we correctly model all finite sets of sequences of revisions□.

It is worthwhile noting that if we did not specify that each revision operator was different, the set of revisions would be more constrained, as belief states that agreed on all conditional free sentences would necessarily revise in the same manner due the functional nature of ∗. As we have noted before this does not apply in our system has the conditional sentences allow multiple belief states that agree on all objective, or conditional free, beliefs.

9 Is ≻ a counterfactual?

We have called ≻ a counterfactual up until now, and indeed we have axiomatized it as a counterfactual following Lewis. However, it does not exactly correspond to the counterfactual sentences that we would normally affirm. There are many examples of times when we will affirm a counterfactual, but upon learning the antecedent deny the consequent. A classic example is the counterfactual,

If Hitler had tried to invade Britain he would have won World War II.

If someone who believed this was to learn that Hitler did indeed try to invade Britain, he would not then change his mind on who the victor of World War II was.

The difference here is that when judging counterfactuals we compare worlds based on similarity, after having chosen to modify certain aspects. Thus when we order worlds in counterfactual similarity orderings we order what worlds we imagine were possible, if things had been different. In the similarity ordering we used for belief revision, it seems that we compare worlds, without discounting any of the differences between that world and reality. Thus we order the worlds that we consider possible without assuming that things are different.

It is superficially surprising that the same rules apply to how we change our beliefs, when we are forced to assimilate new information, and when we imagine how things could be different. However, as both are naturally modeled by orders on possible states of affairs, it is not strange that the differences can be concentrated into which particular order is considered appropriate. This is essentially the same approach as Stalnaker[Stalnaker, 1968, Stalnaker, 1985] has used in differentiating between indicative and subjunctive conditionals.

10 Tabula Rasa

Giving the set of valid sentences that a reasoner will always believe is not the most useful set of sentences to describe. A much more useful set would be the set of sentences a reasoner should believe when told nothing. We could then calculate the sentences a reasoner should believe after being told a sequence of sentences, by applying the rule Change.

We now describe one possibility for a reasoner that has been given no information, but which is willing to take information without any biases.

We suggest that when we are told a sentence A with a depth of left nesting of conditionals n we should hold onto all sentences with a higher left nesting of conditionals. It is worth noting that in our system, no consistent set of sentences, each of which has a particular left nesting of conditionals entails any non-valid sentence with an essentially higher left nesting of conditionals. Thus we can treat each set of sentences of a particular nesting independently. We first define left nesting, and then prove this fact.

Definition: 11 The nestings of a sentence containing conditionals are finite binary trees. The nesting of a letter is a leaf, the nestings of a conjunction A ∧ B is the union of the nestings of A and B, the nesting of ¬A is the nesting of A, while the nestings of A ≻ B are the trees whose left subtree is a nesting of A and whose right subtree is a nesting of B.

The left nesting of A is the depth of the longest left branching path in the nestings of A.

Lemma: 6 If we have a set of sentences Γ, all of whose elements have left nestings of conditionals less than n, then ⊬_{T} Γ → A, if A is a sentence whose left nesting of conditionals is greater than n, and A is not equivalent to a sentence whose left nesting of conditionals is less than or equal to n , and ⊬_{T} A.

Proof:

We consider a model of the sentences of Γ. When we write out the truth conditions of Γ, from a rich state of belief S, we say that a occurrence of a rich state of belief S′ is nested once, if it the state of belief selected by a ↓ A, from the state S, and we say that an occurrence of a rich state of belief S′′ is nested n + 1 times, if it the state of belief selected by a ↓ A, from the state S′′′ that is nested n times.

Clearly, none of the sentences of Γ depend on what rich states of the world are ordered under n nestings. But, by assumption, A is not equivalent to a sentence whose right nesting of conditionals is less than or equal to n, therefore, it depends on some feature of the model, that is nested at least n deep. Thus we can modify any model of Γ, so that it is not a model of A, as required.□

We now define the formulas that we should believe in out initial state of belief.

Definition: 12 For a given sentence A_{n} = A_{n}^{l1} ≻ (… A_{n}^{li} ≻ (… (A_{n}^{lm} ≻ A_{n}^{r}) …) …), of left nesting n, where A_{n}^{r} has no conditional in the scope of a negation, we write A_{n−1} for the set of A_{n}^{li}’s, of right nesting n−1. A_{n−1} can be ordered with the sub-formulas that occur further to the right being higher. We write A_{n−1}^{∗} for the largest upwards closed consistent subset of A_{n−1}. We write A_{n−1}^{+}, for the subset of A_{n−1}^{∗}, which has no conditional in the scope of an odd number of negations.

We take as formulas of our initial state,

{A_{n}|A_{n−1}^{+} ⊢_{T} A_{n}^{r}}
{¬(A_{n})|A_{n−1}^{+} ⊬_{T} A_{n}^{r}}

That is the formulas, whose largest upwards closed consistent positive subset of A_{n−1} entail their right hand side.

We now show that all sentences are decided by these sentences, and that this is a consistent state of belief.

Theorem: 6 Every sentence A is decided by the sentences of our initial state.

Proof:

We prove this by structural induction. Let the set of sentences of our initial state be Θ

• A = p. Take n = 0, and m = 0 and A_{0}^{r} = p, then ⊬_{T} A_{0}^{r}, and thus Θ ⊢_{T} ¬p.

• A = B ∧ C. By the induction hypothesis B and C are decided, thus B ∧ C is decided.

• A = B_{1} ≻ (… ≻ (B_{n} ≻ C) …). Let the nesting depth of C be f. We reduce the value of f by the following construction. If the top-level connective of C is ∧, C = C_{1} ∧ C_{2}, then the truth of A is reducible to the truth of B_{1} ≻ (… ≻ (B_{n} ≻ C_{1}) …) and B_{1} ≻ (… ≻ (B_{n} ≻ C_{2}) …). Thus we may assume that the top level connective is not ∧. If the top level connective is ¬, C = ¬C_{1}, then the truth of A is reducible to the falsity of B_{1} ≻ (… ≻ (B_{n} ≻ C_{1}) …).

Thus the top level connective may be taken to be ≻, C = C_{1} ≻ C_{2}, and thus is of the form B_{1} ≻ (… ≻ (B_{n} ≻ (B_{n+1} ≻ C_{2}) …). Thus by this method we may reduce the complexity of C.

Finally the induction base, A = B_{1} ≻ (… ≻ (B_{n} ≻ p) …), is established as, p is either derivable from the largest upwards closed consistent positive subset of the B’s or it is not.

□

Theorem: 7 The sentences of the initial state, Θ, are consistent.

Proof: We prove this noticing that any finite subset of the sentences of our initial state can be rewritten into m sentences of the form, B_{1} ≻ (… B_{n} ≻ C) where each of the m sequences of B’s elements are logically distinct. However, the truth conditions of these sentences are all independent. Thus it suffices to show that each sentence is consistent. We note that C will be equivalent to ⊥ if and only if ¬B_{n} is valid, by construction. Thus, each of these sentences are consistent, as any sentence of this form is consistent, just so long as C ≡ ⊥ only when ⊢_{T} ¬B_{n}. □

Thus we have generated a consistent set of sentences, that uniquely picks out a particular rich state of belief. This state of belief has the property that it revises its belief in a simple bias free way. It captures the natural idea that we only believe the propositions for which we have evidence. Here evidence can be thought of as being told a set of consistent sentences that entail the proposition, or being told defaults that lead us to revise our beliefs so that we accept the proposition.

This model has the natural property that we never believe a conditional sentence with left nesting n, unless it is valid, or we have been told sentences with left nesting greater or equal to n. Thus we never believe a general principle for revising belief, that is one that is not the result of a more general default, unless it is valid, or we have been told it explicitly.

This system of belief revision has the property that is is rational in the sense of Kraus et al. It could be modified so that it was preferential for objective propositions, however it would still be rational for conditionals, as every belief state decides all conditionals, and thus it is never the case that (A ≻ B), ¬(A ≻ ¬(C ≻ D)), and ¬(A ≻ (C ≻ D)). Thus, when (A ≻ B), and ¬(A ≻ ¬(C ≻ D)), we have (A ≻ (C ≻ D)), and by cumulativity we can derive, (A ∧ (C ≻ D)) ≻ B.

11 Conclusion

We have developed a model of belief revision that models the AGM postulates. We propose a new postulate that completes the AGM postulates, in that it uniquely specifies a revision. Our model of revision captures all finite sequences of AGM revisions. This should be compared with previous models that only captured one revision. Our model is based on the idea that belief revision can be split into two parts, one that deals with what to do when we are told something consistent with out beliefs, and the other that deals with inconsistencies. We propose the use of counterfactual semantics when we are told an inconsistency. We modify Lewis’s semantics for counterfactuals by allowing many possible similarity measures based around the same world, and removing the assumption that counterfactual conditionals has the truth value of the material conditional, when their antecedent is true. Our semantics are based around states of belief, rather than possible worlds, We note that this change in the semantics does not substantially change the axiomatization of Lewis system. We show that our system can represent all sequences of AGM style revisions, and show that it exactly captures the AGM postulates.

We then propose one possible state of belief as the reasonable starting point for a reasoner. This state of belief has the property that the reasoner updates their beliefs by conjoining consistent information, by applying the rules that they have been previously told when they are told inconsistent information, and by believing only what they have been told when they have been given no advice.

This initial state of belief, and the model of belief revision we give fully specify how a reasoner should change their beliefs over time. It specifies a reasoner that can be told arbitrarily nested conditionals, and can thus model defaults about defaults, in contrast to other non-monotonic and conditional systems where defaults only apply to objective sentences.

Acknowledgments

This research has been partly supported by DARPA contract no. ONR 621915

References

[Adams, 1975] Adams, E. (1975). The Logic of Conditionals. D. Reidel, Dordrecht, Netherlands.

[Alchourrón et al., 1985] Alchourrón,  C.  E.,

Gärdenfors, P., and Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50:510–530.

[Burgess, 1981] Burgess, J. (1981). Quick completeness proofs for some logics of conditionals. Notre Dame Journal of Formal Logic, 22(1):76–84.

[Darwiche and Pearl, 1994] Darwiche, A. and Pearl, J. (1994). On the logic of iterated belief revision. In Fagin, R., editor, Proceedings of the fifth Conference on Theoretical Aspects of Reasoning about Knowledge, pages 5–23. Morgan Kaufmann.

[Freund and Lehmann, 1994] Freund, M. and Lehmann, D. (1994). Belief revision and rational inference. Technical Report TR 94-16, The Leibniz center for research in computer science.

[Gärdenfors, 1978] Gärdenfors, P. (1978). Conditionals and changes of belief. Acta Philos. Fennica, 30:381–404.

[Gärdenfors, 1986] Gärdenfors, P. (1986). Belief revision and the Ramsey test for conditionals. Philosophical Review, 91:81–93.

[Gärdenfors, 1988] Gärdenfors, P. (1988). Knowledge in Flux. Cambridge University Press, Cambridge, UK.

[Grove, 1988] Grove, A. J. (1988). Two modellings for theory change. Journal of Philosophical Logic, 17:157–170.

[Kraus et al., 1990] Kraus, S., Lehmann, D., and Magidor, M. (1990). Nonmonotonic Reasoning, Preferential Models and Cumulative Logics. Artificial Intelligence, 44(1):167–207.

[Lehmann, 1995] Lehmann, D. (1995). Belief revision, revised. In Mellish, C., editor, Proceedings of IJCAI 95, pages 1534–1540. Morgan Kaufmann.

[Lewis, 1976] Lewis, D. K. (1976). Probabilities of conditionals and conditional probabilities. Philosophical Review, 85(1):297–315.

[Lewis, 1991] Lewis, D. K. (1991). Conditionals, chapter Probabilities of Conditionals and Conditional Probabilities, pages 76–110. Oxford University Press, New York.

[Plotkin, 1975] Plotkin, G. (1975). Call-by-name, callby-value and the lambda calculus. Theoretical Computer Science, 1:125–159.

[Scott, 1972] Scott, D. (1972). Continuous lattices. In Proc. 1971 Dalhousie Conference: LNM 274, pages 97–136. Springer-Verlag.

[Stalnaker, 1968] Stalnaker, R. (1968). A Theory of Conditionals, volume 2 of American Philosophical Quarterly Monograph Series (Nicholas Rescher, ed., pages 98–112. Blackwell, Oxford.

[Stalnaker, 1985] Stalnaker, R. (1985). Inquiry. MIT Press, Cambridge, MA.

[von Rimscha, 1980] von Rimscha, M. (1980). Mengentheoretische modelle des λk kalkuls. Arch Math Logik Grundlag, 20(1-2):65–73.