On the Semantics of Counterfactuals

1 Introduction

Counterfactuals are conditional statements in which the antecedent is deemed to be false, e.g. 'If Waldo were rich, he'd live in Las Vegas'. Considered as material conditionals, all such statements are trivially true. Thus 'If Waldo were rich, he'd live in Milwaukee' would also be a true statement, if Waldo were not rich. Yet the intention seems to be: 'if things were more or less as they are, except that Waldo were rich, he'd be living in Las Vegas', which rules out living in Milwaukee. It is customary to write a counterfactual conditional of the form 'if 'I' then cp' as ''I' > cp' rather than ''I'::::> cp', in order to preserve this distinction.

Counterfactuals are not truth functional, because they can only be evaluated relative to (i) some theory of what the world is like, and (ii) some notions about what the world might be like if certain things were to change. Informally, we want 'I' > cp to be true if and only if cp is true in all those plausible worlds where 'I' holds which are most similar to the real world. From a formal point of view, the problem is to specify what we mean by 'plausible' and 'similar'.

*This work was supported by the McDonnell Douglas Independent Research and Development program.

Ginsberg's [ 1986] paper was perhaps the first to demonstrate the relevance of counterfactual reasoning to a range of AI applications. Its scope is considerable, including a review of the literature, an account of counterfactual implication, a discussion of implementation issues, and a survey of applications. In this paper, we shall be concerned only with the account of counterfactual implication, which we feel to be flawed in corrigible ways.

Our theses are the following: (i) that the account contains a confusion between proof and model theory; and (ii) that the theory revisions sanctioned are not always minimal.

Our method shall be: (i) to work though the main examples of the original paper, pointing out where difficulties lie; (ii) to present a semantics for counterfactual implication which alleviates these difficulties and compare it with that of Winslett [1988]; and (iii) to show that the model theory satisfies a well-known axiomatization of counterfactuallogic.

2 Critique of Ginsberg's construction

We saw in Section 1 that counterfactual statements are not truth-functional, so we need some kind of construction, consisting of possible worlds other than the current world, which we can inspect in order to decide whether or not a counterfactual holds in the current world.

2.1 Counterfactual implication

Ginsberg's construction for counterfactuals has the following components: an initial set S of sentences; a predicate B on 2s, the power set of S; and a partial order< on 2s which extends set inclusion and respects B. S is a theory of the world, B is a 'bad world' predicate which declares some worlds to be implausible, and < is a comparator of possible worlds along the plausibility dimension. The definition of plausible, similar worlds is as follows.

Definition 1 A possible world for VI in S is any subset T of S such that T l:t: -.\jf, -.B(T), and Tis maximal with respect to <, given these restrictions. The set of such worlds, W(\jf, S), is given by

A counterfactual 'I' > cj> is now true with respect to S iff T u ('I'} I= cj> for all T e W('ljf, S).

Treating 2s as a set of possible worlds confuses syntactic objects, such as sets of sentences, with semantic objects, such as models. In fact, each T e 2s represents a set of worlds in its own right, namely those worlds that satisfy every sentence in T. It can be dangerous to treat arbitrary theories as 'partial possible worlds', because theories are more complex than models. This construction is known as the Possible Worlds Approach (PWA), although the 'worlds' in W('ljf, S) are partial. The basic idea is that if T e W('ljf, S) then T represents a minimum revision to S such that T u ('I'} is consistent, T is not implausible, and no other revision of S is more plausible than T.

In the rest of this paper, a possible world ro will be represented by a set of atomic propositions, ('1'1· ... , '1' 0 }, such that if 'I' is an atom then ro satisfies 'I', written ro I= "''if and only if 'I' e ro, and if 'I'~ ro then ro I= --.'ljf. Such worlds are essentially propositional calculus models as specified in Chang & Keisler [1973, Ch.1]. Satisfaction conditions for a compound statement 'I' follow the normal truth-functional recursion on the complexity of'ljf.

2.2 Semantics of counterfactuals

In this subsection, we review the model theory of Ginsberg's construction, as well as Winslett's reconstruction of the semantics of counterfactual consequence.

2.2.1 PW A and equivalent theories

Ginsberg notes that logically equivalent theories do not have identical counterfactual consequences in PW A.

Example 1 LetS= (p,p ::::> q} and T = (p, q}. -,q >pis a counterfactual consequence ofT but not of S. Neither is it the case in general that a theory and its deductive closure have the same counterfactual consequences.

Ginsberg writes: 'It does not seem to me that this dependence upon representation is inappropriate when investigating counterfactuals, so that we should not be overly concerned over the fact that our construction depends upon more than merely the model-theoretic information contained in the theory S'.

On the contrary, we believe that the counterfactual consequences of a theory should not depend upon the vagaries of its syntactic representation, and construe this dependency as further evidence of a confusion between syntactic and semantic entities. Section 3 presents a semantics in which logically equivalent theories have identical counterfactual consequences.

Example 2 Let t denote 'thunder' and I denote 'lightning'. An agent unaware of the connection between them would describe the world asS= {t, 1}, giving --.t >I.

Ginsberg uses this example to suggest that without the vices of his model theory, it would be impossible for any fact to be irrelevant to any other. This turns out not to be the case. Section 3 presents a model theory without these vices in which irrelevance is possible.

2.2.2 The Possible Models Approach

Winslett's [1988] Possible Models Approach (PMA) attempts to regularize the model theory of counterfactual consequence. Given a set of formulas S and a theory T, PMA computes a set of models Incorporate{S, M) produced by incorporating S into T, where M is a model ofT. The formal definition can be expressed as follows.

Definition 2 Let T be a theory with protected formulas T* c T, let M be a model ofT, and letS be a set of formulas. Incorporate(S, M) is the set of all models M such that

• (i) M' I= Sand M' I= T*; and
• (ii) no other model satisfying (i) differs from M on fewer atoms

where 'fewer' is defined by set inclusion. If Models(T) is the set of all models ofT, then the set of models of the revised theory is given by: UM e Models(f) Incorporate(S, M).

It is easy to verify that logically equivalent theories have identical counterfactual consequences in PMA. However, we shall argue that its results are sometimes counterintuitive, especially when we iterate the conditional operator. We return to Winslett's construction in Section 3.2 (Example 4), and show that its revisions are not always minimal.

3 Situation semantics for counterfactuals

The following account assumes a propositional language L, defined over a finite alphabet A. We can construct 2IA 1 interpretations over this alphabet, and consider each as a possible world. Let this set of interpretations be W. The empty theory, 0, is satisfied by every interpretation, so we label this set of worlds W 0· i.e. the class containing all models of 0. Clearly W 0 = W. A non-empty theory S c L describes a situation, Ws e 2w. Thus Ws c W is the set containing just those possible worlds which satisfy S.

The easiest way to formalize situations is in terms of model-theoretic forcing [Keisler, 1977]. If S is a theory, then a condition for S is a finite set of literals, C, consistent with S, and C II- 'I' denotes that C forces 'ljf, i.e. that S, C 1'1'· G is a generic set for S iff each H !;;::; G is a condition for S and G II- 'I' or G II- --.'ljf for all propositions 'I'·

Definition 3 If Sis a theory, then a situation for S, Wg, is a set of possible worlds constructed as follows. For each generic set G for S, we can construct a world

ro =('I' IS, G 1- 'I'}

where 'If is an atomic proposition. W s is the set of such worlds.

The semantics that we shall give for counterfactuals of the form 'If > cjl with respect to a theory S depends upon a very simple idea. We consider 'I' as a revision function that we can apply to S to return those plausible worlds where 'I' holds which are most similar to some world in w 5 . 'I'> cjl is then a consequence of S just in case cjl holds in each of these worlds.

3.1 Propositions as functions

A proposition 'If can be considered as a function, 'fl: 2 W ~ 2 W, from situations to situations. For example, if S c L is {p => q}, then p(S) denotes p(W 5 ), where p is the function associated with p. We want the value of p(W s) to be the set of worlds most similar to S in which p holds. If A = {p, q} is the alphabet of L, then Ws = {0, {q}, {p, q}}, and the application of p to W s should return { {p, q} } , the only model of {p,p :::> q}.

The above example was rather straightforward. p was consistent with S, and we did not place any restrictions upon the range of p, i.e. all worlds in which p held were deemed to be plausible. As a result, we can consider the computation performed by p as an instance of forcing: {p} was a condition for S that forced q. But we are most interested in the case where p is inconsistent with S, and cannot therefore be a condition for S. What general properties should propositions considered as revision functions possess?

Pl. If S logically implies 'If, then there is no need to change W S· Otherwise, some revision must be effected, else there will be a world in W s which is not a model of 'fl.

P2. If 'If is consistent with S but does not follow from it, then we compute a new situation 'fi(S) = W {'I'} n W s, containing all the possible worlds which satisfy {'I'} uS.

P3. If 'I' is inconsistent with S, then we compute some minimum revision, 'fi(S), of W s such that 'fi(S) !:: W {'If}" This inclusion must hold if 'I' is to be true at every world m 'fi(S). If 'I' is inconsistent with protected propositions in S, then 'fi(S) = 0.

Let us concentrate on P3, since the other three cases are straightforward. 'fi(S) cannot be just any subset of W {'If}' because there may be propositions in S that we wish to protect. If S* c S is the (proper) subset containing the protected propositions, then we require that 'fi(S) ~ (W {'I'} n W s·), i.e. 'fi(S) must contain only plausible worlds.

We can generalize the notion of a revision function as follows. Rather than generating an individual function for each proposition, and composing these functions for compound propositions, we introduce a two-place operation, =:),upon sets of worlds, such that 'fi(S) = (W{'I'} =:) Ws). In so doing, we use the notion of a world lattice: If S c L and B ~A contains those members of the alphabet of L occuring inS, then As= (2B, c) is a world lattice for S.

Definition 4 LetS* c S cL, 'I' eLand W{'l'} n Ws = 0. Then 'fi(S) = W {'I'} =:) W s contains just those worlds roe (W {'I'} n W s ·) that satisfy the following condition:

There is a world u e W s such that

• (i) ro is a glb or lub of u in As; or
• (ii) there is a world me W {'I'} such that
• (a) m is a glb or lub of u in As and
• (b) m fE Ws· and
• (c) ro is the smallest superset or largest subset of min (W {'I'} n W s·)

where glb denotes the greatest lower bound and lub denotes the least upper bound.

Thus each world in W {'I'}=:) W sis a world from W {'!'}" For each world ro in W {'!'}' ro is in the revision if and only if: either (i) ro satisfies the protected propositions and is a maximal subset or minimal superset of a world in Ws; or (ii) there is an implausible world m in W {'If} which is a maximal subset or minimal superset of a world in W S· and ro is a maximal subset or minimal superset of m with respect to the plausible worlds. Hence the worlds most similar to worlds in W s are those plausible worlds which are closest to such worlds in the lattice.

Each proposition is therefore a function of the following kind.

Definition 5 If 'If is a proposition and S a theory, then

The reader can verify that the definition satisfies each of the properties Pl-P3.

Definition 6 'I' > cjl is a counterfactual consequence of S iff ro I= cjl for all ro e 'fi(S).

This completes our semantic account of counterfactual consequence; we now return to the examples introduced in Section 2.2.1. The recomputation of the set of plausible, similar worlds for each case will illustrate the model theory, as well as demonstrating its advantages. Let us agree to call the logic of Definitions 3-6 'Belief Revision Logic', or BERYL for short.

3.2 The examples revisited

In this subsection, we show that the problems noted in Section 2 do not arise in BERYL.

Example 1 revisited If S = {p, p :::> q}, T = {p, q} and there are no protected propositions in either theory, then

Thus -,q > p is a counterfactual consequence of both theories. It is easy to see that if S and T are any pair of equivalent theories, then they will have identical counterfactual consequences, so long as S* and T* are equivalent (This result also holds for Winslett's PMA.)

Theorem 1 If S and T are equivalent propositional theories and S* and T* are equivalent. then for all propositions 'I' and <!>, 'I' > <1> is a consequence of S iff 'I' > <1> is a consequence of T.

Proof Follows straightforwardly from Definitions 3-6. If the antecedent holds, then 'lf(S) = 'lf(T). Thus c.o I= <I> for all c.o e 'lf(S) iff c.o I= <1> for all c.o e 'lf(T).

Example 2 revisited If S = (t, I} and S* = 0, then

so -.t > I, and t is irrelevant to I. But if T = {1, -.t } and T* = 0, then

and t and I are now dependent. and will remain so as long as t = I is protected. But if t = I is not protected, then it will be retracted in the face of -.t or --.1. Note also that. if t = I is not protected, we have (t = 1)(--.t (S)) "1:- -.t ((t = l)(S)), even though -.t and t = I are consistent

It follows that -.t > ((t = /) > I) is a counterfactual consequence of S, but not (t = /) > (-.t > 1). The order in which we entertain the two hypotheses makes a difference.

The point is that the outcomes in Example 2 are identical to those that would be derived by PW A. Thus the fact that equivalent theories have identical counterfactual consequences in BERYL has no bearing on the issue of irrelevance. Nor does it prevent counterfactual consequence from being sensitive to either the order in which we entertain hypotheses or the protection of certain propositions in the face of hypotheses. (The same results hold for PMA.)

The next example highlights an essential difference between PW A and BERYL.

In PW A, there is a single revision of S in the light of p: we retract -.p. But there are two alternative revisions ofT: we can retract -.q or we can retract p :::> q. The possible worlds associated with the revised theories S' and T' are { {p, q}} and { {p}, {p, q}} respectively. By contrast. in BERYL:

Thus p > q is a counterfactual consequence of S in Ginsberg's method but not in BERYL, while p > -.q is a consequence ofT in BERYL but not in Ginsberg's method. This conflict is worth examining in more detail. The reader is invited to consult the world lattices of Figure 1, where dark shading signifies the models of the theory in question, light shading signifies models of the counterfactual premise.

With respect to S, the minimal change is to retract -,p and p :::> q. From a semantic point of view, {p} is the most similar world to 0 and {p, q} is the most similar world to { q}. {p, q} is not the most similar world to 0, and so moving from 0 to {p, q} is not a minimal change. This much is clear from Fip;ure Ia.

BERYL's judgement is also justifiable from a syntactic point of view, so long as that view is purely syntactic. In the propositional calculus, p :::> q is just another way of writing the disjunction -,p v q. Relinquishing -,p v q must involve a smaller change to S than retaining it and admitting q, since q 1- -,p v q.

A similar argument holds with respect to the revision of T. Figure lb shows that {p} is the world closest to 0. The minimal change is to reliquish p :::> q before admitting q.

Figure 1 World lattices for Example 3, (a) representing p(S) and (b) representing p(T).

If we protect p :::> q in both theories, then BERYL and PWA get the same results. But in so doing we have implicitly gone beyond the syntax (and semantics) of the propositional calculus. p :::> q then signifies something closer to L(p :::> q) in a system of modal logic (where Lis the necessity operator), since we insist that p :::> q hold in every possible world. (PMA agrees with BERYL, not PWA.)

The final example, also taken from Ginsberg's paper, serves to differentiate BERYL from both PW A and PMA.

Example 4 LetS = {-.v, b, s} with S* = 0, where v denotes that Verdi is French, b denotes that Bizet is French, and s denotes that Satie is French.

What are the counterfactual consequences of v = b, i.e. the consequences of Verdi and Bizet being compatriots? PW A, PMA and BERYL agree about this. PW A would derive the two alternative theories s 1 = ( v' b' s} and s2 = {-,v, -.b, s}, while, in BERYL's notation:

Thus (v =b)> s, which seems intuitively right: Satie remains French in both worlds. This result can be read off from Figure 2a, where dark shading distinguishes models of S, light shading distinguishes models of the counterfactual premise, and models of the revised theory are heavily outlined.

But what of the additional premise -,v = s? What are the counterfactual consequences of Verdi and Satie not being compatriots while Verdi and Bizet are compatriots?

PW A and PMA agree on the set of worlds { {s), { v, b)). In PW A, we can retract the Frenchness of Bizet to obtain the world { s) , or we can retract the Frenchness of Satie to obtain the world { v, b). In PMA, the models { s) and { v, b) each satisfy (-,v = s)" (v =b) and differ minimally from {b, s), the only model of S. Neither of these worlds is preferred to the other, according to Definition 2. BERYL's answer is ((-,v = s)" (v = b))(S), which evaluates to

Thus ((-,v = s)" (v =b))> s, and we conserve Satie's Frenchness (see Figure 2b). The minimal change to S is to let Satie stay French in the world where Bizet is Italian, since one of Bizet and Verdi must change nationality anyway. The inclusion of { v, b) by PW A and PMA seems counterintuitive. { v, b) differs from { b, s) on atoms v and s, while {s) only differs on b, so {s) conserves more of S, and therefore seems more similar to {b, s) than does { v, b).

In any event, we have a clash of intuitions, and BERYL's result is perfectly arguable. The difference betwen BERYL and PMA is a direct consequence of Definition 4, which ensu.res that 'IJI(S) con.ta.ins worlds in W {'I'} which are max1mal subsets or m1mmal supersets of worlds in w5, rather than worlds which differ minimally on atoms from worlds in w5, as in PMA.

We can use this example to further distinguish between BERYL and PMA. The most illuminating exercise is to compute (-,v = s)((v = b)(S)), i.e. to compute the worlds in which -,v = s holds which are most similar to the worlds most similar to S where v = b holds. BERYL's answer is identical to ((-,v = s)" (v = b))(S):

whether or not v = b is protected, because -,v = s is consistent with (v = b)(S), and so the revision is given by W (-.v = s} n (v = b)(S), courtesy of Definition 5. Hence (v =b) > ((-,v = s) > s), and we conserve Satie's Frenchness again.

If v = b is unprotected, PMA's answer is

If v = b is protected, then PMA's answer is { { v, b), {s)) . Yet the monotonic revisionl {s) to (v = b)(S) seems preferable to either of the nonmonotonic revisions { v, b) and {b, s), whether v = b is protected or not. It is hard to see how a nonmonotonic revision can be as small as a monotonic revision, whatever one's intuitions. Remember that all three systems agree on (v = b )(S). In fact, PW A agrees with BERYL here.

4 Summary and related work

We have presented a semantics for counterfactual implication which uses nothing more than set inclusion to compute the set of plausible, similar worlds in which a counterfactual premise holds. The function that computes this set, for a given theory S with protected propositions S*, corresponds to the premise itself. Thus if 'IJ1 is a counterfactual premise inconsistent with S, then 'IJ1 can be understood as the function (AX)(W {'I'} => W x). whose argument is S. The idea of using propositions as functions from one epistemic state to another is entirely due to Glirdenfors (1988, Ch.6). Our use differs only in that such functions can be nonmonotonic.

The most interesting comparison is that between BERYL and Glirdenfors' (op cit, Ch.7) axiomatization of Lewis' (1973) counterfactuallogic, VC. .

Theorem 2 The construction of Definitions 3-6 satisfies the ten axioms and two derivation rules of Glirdenfors' axiomatization of VC.

Proof Let 'IJI, ~and X be any propositions, and letS c L be any consistent theory.

A 1. All truth functional tautologies. 1- 'I'::)~ iff W {IJI} !::: W {ell} as usual. A2.('1J1 >~)A ('IJI >X)::) ('IJI >(~A X)). If (1) I=~ and (1) I= X for all (1) E 'IJI(S), then (1) I==(~ 1\ x). A3. 'IJ1 > T. If 1- ~. then w I=~ for all wE 'lji(S). A4. 'IJ1 > 'IJI. w I= 'IJ1 for all w E 'lji(S). AS.('IJI > ~)::) ('IJI::) ~).

If w I=~ for all wE 'IJI(S), then~ follows from S and 'I'·

1 The model {s) represents a monotonic revision because it only requires that we discard models from W 5; thus the process is analogous to theory extension. By contrast, the revisions {v, b} and {b, s) each require that we introduce new models, and are therefore nonmonotonic.

A6. ('I' " cj>) ::::> ('f' > cj>). This follows immediately from Definition 5. A 7. ('I' > ...,'I') ::::> ( cj> > ...,'f'). c.o 1= ...,'I' for all c.o e 'f'(S) iff 'f'(S) = 0. Thus c.o I= ...,'I' for all c.o e cj>(S) and any cj>, since S* 1- ...,'f'. (If S* = 0, then 1...,'f'.) AS. (('I'> cj>) " (cj> > '!')) => (('I'> X) => (cj> >X)). If 'I'= cj>, then W {'If} = W {ell }· so 'f'(S) = cj>(S). A9 . (('I'> X) "(cj> >X))=> (('I' v cl>) >X). ('I' v cj>)(S) {.;;; W {X} if'f'(S) ~ W {X} and cj>(S) ~ W {x}· AlO. (('I'> cj>) " -,('1' >...,X)) => (('I' "X) > cj>). ('I' " X)(S) ~ 'f'(S) if c.o l:;t ...,X for any c.o e 'f'(S). DRl. 1- ('I' " ('I'::::> cj>)) ::::> cj>. (W {'I'} n W {"'If=> ell})~ W { cp} as usual. DR2. If 1- cj> ::::> x. then 1- ('I'> cj>) ::::>('I'> X). W {ell}~ W {X} so 'f'(S) ~ W {X} if'f'(S) ~ W {ell}·

Ginsberg's construction satisfies AlO only if the partial order is modular, i.e. for any worlds c.o and m such that neither c.o < m nor m < c.o, if u < c.o then u < m. Partial orders based solely on set inclusion do not have this property, although orders based on cardinality, for example, do. Nevertheless, BERYL satisfies A10 without modularity, so this suggests that the requirement is a property of PW A, not counterfactuallogic.

Gardenfors identifies a number of criteria for the classification of belief revision functions, two of which are the preservation criterion (K*P) and the monotonicity criterion (K*M). The former states that if cj> follows from S and 'I' is consistent with S, then cj> will still follow from the revision of S by 'I'. The latter states that if S 1 and s2 are theories and s2 contains S 1, then the revision of s2 will contain the revision of S 1. We can show that the revisions sanctioned by BERYL are always preservative but not always monotonic. (K*P and K*M are translated into the present notation in the following theorems.)

Theorem 3 BERYL satisfies the preservation criterion, K*P: If S l:;t ...,'1' and S I= cj>, then 'I'> cj>.

ProofS l:;t...,'l' and S I= cj> by hypothesis, so W{'l'} n Ws :;t 0 and Ws ~ W {ell}· But then W{'l'} n Ws ~ W {ell}· So c.o I= cj> for all c.o e 'f'(S), and 'I'> cj>.

It is easy to show that PW A satisfies K*P.

Theorem 4 PMA does not satisfy the preservation criterion.

Proof By counterexample. In Example 4, (v =b)> s with respect to the theory S = {-,v, b, s}, but it is not the case that (-,v = s) > s with respect to the theory S' = { v = b, s}, which is just S revised by v =b. Yet S' l:;t -,(-,v = s).

These theorems are important if one wishes to extend either system in the direction of a probabilistic model, since Bayes' Theorem endorses the preservation criterion. Thus the revision functions of BERYL and PW A are amenable to a Bayesian extension, while that of PMA is not as it stands.

Theorem 5 BERYL does not satisfy the monotonicity criterion, K*M: If S1 ~ S2, then 'f'(S2)!:: 'f'(Sl) .

Proof By counterexample. Let S1 = {p = q} and S2 = {p = q,p}. -,q(S1)= {0} while-,q(S2)= {{p}} . HenceS1 ~S2, but not 'f'(Sv {.;;; 'f'(S 1).

Not surprisingly, BERYL is a nonmonotonic logic. Note that we render the consequent of K*M by 'f'(S2) ~ 'f'(S 1) and not 'f'(S 1) ~ 'f'(S2), since there is an inverse relation between the specificity of a theory and the number of models that satisfy it.

In conclusion, we feel that nothing in this paper detracts from Ginsberg's argument that counterfactual reasoning is important for artificial intelligence. We criticize his construction because (i) logically equivalent theories can differ in their counterfactual consequences, and (ii) it does not always compute the smallest revision necessary to admit a proposition to a theory. Winslett's PMA avoids the confusion of proof theory and model theory found in PW A. Like BERYL, PMA uses no order on models other than set inclusion to compute similarity, and logically equivalent theories have identical counterfactual consequences. Yet Example 4 shows that the definition of 'Incorporate' (given here as Definition 2) is not equivalent to Definitions 4 and 5, as it does not always prefer monotonic revisions to nonmonotonic ones.