Allowed Arguments

1 Introduction

The better known accounts of defeasible reasoning are somewhat limited in the expressive power of their object languages. This is apparent for example when it comes to formalizing Raz's [1990] prima facie reasons to act, which underlie the planning and justification of acts. These suggest an analysis in a formalism for expressing defeasible knowledge, such as Reiter's [1980] Default Logic: that p is a prima facie reason to do a can be thought of as a 'normal' default rule with the reason p as its prerequisite and as its consequent a sentence expressing that a ought to be done. Such an analysis runs into a difficulty though. In some cases not discussed by Raz the very fact that there is a reason to act is itself, in turn, a reason to act. Thus Jones' lateness is a reason for his boss to fire him; and this very fact is in turn a reason for Jones to act: it is a reason for him to arrive on time in the future (assuming of course he doesn't want to be fired). This second claim cannot be represented in way I've suggested though, since a default rule which represented it would have, as its prerequisite, a default rule expressing that Jones' lateness is a prima facie reason for him to be fired. Such embedded defaults are not within the scope of Reiter's formalism since its default rules are not a part of its object language. They are metalinguistic rules of inference.

McCarthy's [1980] Circumscription can in principle be used to represent embedded defaults, since it represents defaults in the object language. But in order to represent the

Research supported in part by the NSF and ARL.

notion that an act ought to be done, which prima facie reasons seem to require, this formalism will have to be generalized from classical logic to some more expressive underlying language.

It is unlikely that Default Logic can be extended to cover embedded defaults; Circumscription, on the other hand, can certainly be extended to more expressive languages (Thomason [1990] extends it to Montague's Intensional Logic). But you wonder whether it is not better to start off with a more expressive language, formalizing defaults as ceteris paribus conditionals in modal logic, since modal conditional logic allows unlimited embeddings of conditionals; also, propositional attitudes, deontic contexts, counterfactuals and other constructions are already quite well understood in that setting.

This idea was first persued by Delgrande [1988]. Others including Asher and Morreau [1991] and Boutilier [1992) later took it up, but their results so far have been disappointing. Delgrande had a difficulty which Circumscription and Default Logic do not face with what he called "irrelevant information." Asher & Morreau [1991] solved this particular problem, but their nonmonotonic consequence notion, Commonsense Entailment, is conceptually exotic and technically formidable. Boutilier [1992] treated conditionals expressing defaults as necessarily true, if true at all; this squanders the resources of modal conditional logic for representing nested defaults and embeddings of defaults into belief contexts and counterfactuals. Finally, these approaches have not led to attractive syntactic characterizations of nonmonotonic reasoning. Not even characterizations of the sound-though-incomplete kind which McCarthy [1980] offers.

In this paper I will present an account of nonmonotonic reasoning based in modal conditional logic which does not have these shortcomings. The goal is the same as that of Asher and Morreau [1991]: to provide an underpinning for analyses requiring the resources of possible-worlds theory. In regard to the inferences it allows, the notion of nonmonotonic consequence which I will present here is very similar to their Commonsense Entailment (though section 7 shows how it allows defeasible inferences including strengthening of conditional antecedents and the hypothetical syllogism which have as far as I know not been dealt with before). One important advantage of the present account over Commonsense Entailment is that it is technically and conceptually simpler. For this reason it provides a better foundation for analyses which depend on Commonsense Entailment, such as Lascarides and Asher's [1993] treatment of rhetorical structure in natural language.

I begin in the next section with a weak first-order modal conditional logic with which to represent defaults. I In section 3 I present a syntactic notion of nonmonotonic consequence, Allowed Consequence, and analyze several familiar patterns of nonmonotonic reasoning. In section 4 I present Allowed Entailment which is an analog, in possible-worlds theory, of McCarthy's [1980] Minimal Entailment. In sections 5 and 6 I generalize these to allow a priority order on defaults and show that (prioritized) Allowed Consequence is sound and complete relative to (prioritized) Allowed Entailment.

2 Default Conditionals

Here is a formal language for expressing defaults. Let L be a countable language of first-order logic with no function symbols. Add a binary conditional operator>. The result is L>; where <p and 'If are formulas of L>, so is <p>'lf. Familiar monadic modal operators expressing belief (B), knowledge (K) and obligation (0) can be added too; where cp is a formula of L> so are B<p, K<p, and O<p.

Where <p and 'I' are sentences, <p>'lf is intended to express that normally 'If, if <p. Letting j be an individual constant standing for Jones, for example, Jetting Dyz express that y is a day in month z, Jetting Lxy express that x is late for work on day y and letting Fx express that x is fired, V'y(D(y, december)~L(j,y)) > OFj is intended to express that other things being equal, Jones ought to be fired if he is late every day in december. This formalizes the notion that Jones' being late all december is a prima facie reason for him to be fired.

Where <p and 'If are predicates or relations, \f x( <p>'lf) is intended to express that if something is <p then normally it is a 'I'. For example, Jetting Hxy express that y is an event in which x is thoroughly heated, and Jetting Fxy express that y is an event in which x will catch fire, the monadic predicate Vy(Hxy>Fxy) expresses that x is flammable: it is the sort of thing which in the event that it is thoroughly heated will normally catch fire.

There is something implausible about understanding flammability as a universally quantified conditional: that a piece of wood is flammable wrongly entails that it normally will catch fire in the event that it is thoroughly heated while, say, immersed in water. (Imagine boiling it for hours on end.) There are alternative ways of understanding flammability : that a given piece of wood w is flammable clearly has something to do with events in which w is thoroughly heated. But instead of supposing this claim to quantify over events of this kind it could, say, be taken to express that two properties - the property of being an event in which w is heated, and that of being an event in which w catches fire - stand in an appropriate relation to one another. The generic dogs bark would on this view express that the property of being a dog and being a barking thing stand in this same relation, and so on.

I It is neither new nor is it unique to this analysis of non­ monotonic reasoning; Delgrande, Asher & Morreau and Boutilier all rely on some such underlying conditional logic.

Such a relational account of defaults can be developed on the basis of a suitable theory of properties. And once developed it will be possible to extend to it the account of nonmonotonic reasoning of sections 3 and 4. But that is for another time.

Unlimited nesting of > is allowed. Letting Ax express that x attempts to arrive at work on time (more of the resources of modal logic could be used to analyze A further but that would be a distraction here), the following nested sentence expresses that the fact that Jones' lateness is a reason to fire him is itself a prima facie reason for him to try to arrive on time:

(Vy(D(y,december)~L(j,y)) > OFj) > OAj.

For another example of nesting, letting Rx express that x ought to be kept well away from radiators we can write Vx(Vy(Hxy>Fxy) > Rx) to express that flammable things normally ought to be kept well away from radiators.

What is the meaning of > and what is its logic? As Delgrande, Asher & Morreau and Boutilier all point out, in keeping with the intended interpretation of <p>'lf there is a standard axiom scheme of conditional logic which is not valid: modus ponens, or <p>'lf ~ <p~'lf. It can happen that normally 'If if <p, that <p holds, and yet that 'If does not hold. These authors helped themselves to interpretations of conditional logic within possible-worlds semantics, as pioneered by Stalnaker and Thomason [1970] and Lewis [1973], making suitable adjustments so as to keep modus ponens from being valid. I will do the same.

I begin by interpreting L> in possible-worlds models (which are presented in Chellas [1980]). The basic notion is that of a possible-worlds frame, which is a triple < '71/,1'!., *> consisting of a nonempty set U'of possible worlds, a set!'!. of individuals over which the quantifiers of L> range, and a worlds-selection function *: 'Wx ,f.J('Hl) ~ .f.J( 'W). This latter component, which is used to interpret >, maps each world and proposition onto a proposition. (Proposition is the technical term for a subset of 'W; a proposition p holds in a possible world w just in case wE p.) Thus * (w,p) is a set of worlds; informally speaking, they are the worlds where things are as they normally are if p holds. Just which set this is der 1s on w, since how things normally are if p can vary fron · .. me to time and place to place. Additional structure can added to modal frames in order to interpret B, K, 0 :1 l other modal constructions like counterfactuals; what is 1 :eded is quite well known however and I will not discus it here. See Chellas [1980] for details.

In keeping with its intended purpose * is subject to a very basic constraint of conditional logic:

FACTICITY: A frame <W,I'!.,*> satisfies facticity if

for all wE 'Wand p ~ W, *(w,p) ~ p. Another familiar constraint is however quite inappropriate in this connection. Say that wE 'Wis centered in a frame <'W,*> if for all p ~ 'W, if wE p then wE *(w,p). Then we have:

CENTERING: A frame <W,Ll, *> is centered if each of its possible worlds is centered.

We cannot require that all frames be centered since that w is a p·world in no way guarantees that w is a world where everything is as things normally are if p. Along with Delgrande, Asher and Morreau and Boutilier I therefore do not require that modal frames satisfy this constraint. The following examples of frames will be used in later examples:

EXAMPLE 1: The following singleton structure satisfies facticity and is centered: · u

where *(u, {}) = {}; *(u,{ u}) = { u}.

u

v

EXAMPLE 2: The following structure satisfies facticity and is not centered: · ·

where for each x E { u, v}, *(x, { }) = {}; *(x, { u}) = { u}; *(x, { u,v}) = *(x, { v}) = { v}.

Together with any given domain of quantification, each of these structures forms a modal frame.

A modal frame becomes a model < U',Ll, *,I> for L> on adding an interpretation function I, which in any given possible world assigns elements of Ll to individual constants, and which assigns appropriate intensions to the atomic predicates of L>. The conditions of truth of formulas of L> in possible worlds wE 'W of a model !M = < 11/,Ll, *,I> are stated relative to assignments a of L>­ variables to Ll. The clauses of the truth definition which deal with atomic formulas, sentential connectives apart from > and the quantifiers are all quite familiar; I have not included them here. The clause for> is the standard one in modal conditional logic:

!M,w p<p>'lf [a] if and only if *(w,l<pla) s;;; I 'VIa·

In this expression I <!>Ia, the proposition expressed by <p in !M relative to a, is just { v E 'W: !M, v f= <p [a]}. What is required for a sentence <p>'lf to be true, then, is that 'If holds in any world where things are as they normally are if <p.

EXAMPLE 3: Choosing Ll = {e,w}, let !Mbe obtained by adding, to the singleton structure of EXAMPLE 1, any interpretation function /such that Iu(e) = e; Iu(w) = w, and Iu(H) = Iu(F) = {(w,e)}. It is straightforward to verify that !M,u f= Vy(Hwy>Fwy).

OBSERVATION 4: Let u be centered in !M (as it is in the previous example). Then for any <p and 'If, !M, u f= <p>'lf ~ <p~'lf. This follows directly from the truth­ conditions for>.

These models generate a notion of logical entailment in the standard way. Where r is a set of formulas, r F <p means that for any model !M, for any possible world w of !M and for any appropriate variable assignment a, if !M,w f=r[a] then !M,w p<p[a]. The following example concerns a model showing that modus ponens is not valid. That is to say, It <p>'lf ~ <p~'lf:

• EXAMPLE 5: Choosing Ll = {e,w}, let 9{be obtained by adding, to the structure of EXAMPLE 2, any interpretation function !such that Iu(e) = Jv(e) = e; Iu(w) = Iv(w) = w,

Iu(F) ={}and Iu(H) = Iv(H) = IJF) = {(w,e)}. It is straightforward to verify that 'J{,u f=Vy(Hwy>Fwy), that 'J{,u f=Hwe, and that 'J{,u f=-.Fwe.

Logical entailment can be given a sound and complete syntactic characterization. I start with a notion of derivability without premises. Let f- <p mean that <p can be derived using the following axioms and rules:

Al. All truth-functional tautologies of L>

A2. Vx<p ~ (t/x)<p where tis any individual term of L>

A3. Vx<p H -.3x-.<p

A4. Vx(<p~'lf) ~ (3x<p~'lf) where x is not a free variable of 'I'

A5. Vx(<p>'lf) ~ (<p>V'x'lf) where x is not a free variable of <p

A6. Vx(<p><p)

R 1. If f-<p and f- <p~ 'If then f-'If.

R2. If f- ('lfJA'I'2···"'1'n)~'l'

then f-(<p>'lfl A <p>'lf2···" <p>'lfn)~<p>'lf

R3. If f- <p~(c/x)'lf then f- <p~Vx'lf provided the constant c occurs neither in <p nor in 'If

R4. If f- <p then f- (t/x)<p

• provided the individual term t does not occur in <p

R5. If f- <pH'If then f-(<p/'lf)X H X where (<p/'lf)X is the result of replacing within X an occurrence of 'If by an occurrence of <p.

r f- <p, or <p is derivable from premises r, can be defined in terms of the above notion. It means that for some finite r*s;;; r' f- Ar* ~<p. (This is not the standard definition but it has the advantage that compactness and the deduction theorem involving ~ are obvious.) The following completeness theorem can be proven using a standard, Henkin-style construction of a canonical model:

THEOREM 6: r f- <p if and only if r F <p.

Proof A variation on a result in Chellas [1980].

3 Allowed Consequence ...

In this section the logic of weak conditionals will be extended to a nonmonotonic syntactic consequence notion, written f-lt· Informally speaking, the idea is to add modus ponens wherever possible, thus allowing the consequents of conditionals to be detached. Technically this is done by adding to the premises of an argument as many instances of the axiom scheme <p>'lf ~ <p~'lf as are consistent with them. Let MP be the set of all instances of this scheme.

DEFINITION 7: .Q is maximal T-consistent within MP iff

• (i) .Qs;;; MP, arl (li) IU1 r+-1.. while for every .Q*, if Q s;;; .Q*s;;; MP and RJ.Q* r.fl., then .0= .n*.

Such sets play a role in the notion of allowed consequence which is analogous to that of extensions in Reiter's Default Logic.

DEFINITION 8: r ht <p iff for every maximal r-consistent set .Owithin MP, IU1 f-<p.

Where r ht <p I will say that r allows the consequence <p to be drawn. The following two examples show that interesting instances of modus ponens across > are allowed. First, that e is an event in which w is thoroughly heated, together with the fact that w is flammable, allows the consequence w will catch fire to be drawn:

EXAMPLE 9: Hwe, Vy(Hwy>Fwy) t----p_ Fwe.

Proof" Let the set of the premises Hwe, Vy(Hwy>Fwy) be called r . From EXAMPLE 3 and OBSERVATION 4 it follows that r is satisfiable together with all of MP, so (with THEOREM 6) there is just a single maximal r­ consistent subset of MP, and that is MP itself. Now r, MP f-Fwe. ·

The next example is similar but concerns the part of the language in which > is nested. Intuitively speaking, from the facts that w is flammable and that flammable things normally ought to be kept well away from radiators follows that w ought to be kept well away from radiators: EXAMPLE 10:

V'y(Hwy>Fwy), Vx(Vy(Hxy>Fxy) > Rx) t----p_ Rw. Proof· Let the set of the premises Vy(Hwy>Fwy), Vx(Vy(Hxy>Fxy) > Rx) be called r. Adapt EXAMPLE 3, requiring in addition of !that I u(R) = { w} . It is a matter of routine to show that r is satisfied in the resulting model. From OBSERVATION 4 it again follows that r is satisfiable together with all of MP. Now r, MP f- Rw. ·

From the above demonstrations, which require only that the premises are satisfiable in the frame of EXAMPLE 1, it will be plain that "irrelevant" additional information can be added to the premises without losing these conclusions. For example, the previous examples can be repeated on adding, say, an extra premise Pw expressing that w is a piece of pine. Other analyses of such reasoning which depart from weak conditional logics, such as the previously cited suggestions of Delgrande and Boutilier, have had to go to great lengths to allow such irrelevant additional premises to be added.

EXAMPLE 11: Hwe, --,Fwe,Vy(Hwy>Fwy) ~ Fwe.

Proof: Let the set of the premises be called r . EXAMPLE 5 shows that r is satisfiable. It follows with the deduction theorem for ~ and the compactness of f- that there is a maximal r -consistent subset - call it Q - of MP. Now r , Q b-f Fwe. ·

The following example is similar to the well-worn Nixon Diamond, which could have been analyzed in its place. Let Wx express that x is wet, so that VxVy(Wx>-.Fxy) expresses that wet things normally don't burn. The following example shows that neither the inference that w will catch fire in e, nor that w will not catch fire, is allowed from premises expressing that w is flammable, that e is an event in which w is thoroughly heated, that w is wet, and that wet things normally do not catch fire.

EXAMPLE 12: Let r be {Hwe, Ww, Vy(Hwy>Fwy),

VxVy(Wx>-.Fxy)} Then (i) r ~ Fwe and

(ii) r ~ -.Fwe

Proof" (i) With a model construction based on the frame of EXAMPLE 2 it is straightforward to show that r is satisfiable together with (Ww>-.Fwe) ~ (Ww~--,Fwe). It follows that there is a maximal r -consistent Q ~ M P such that (Ww > -.Fwe) ~ (Ww ~ -.Fwe) E u Now r, Q ~Fwe.

(ii) Analogous

·

4 ... and Allowed Entailment

In this section I will generalize the syntactic notion of Allowed Consequence of the previous section. I will then define the nonmonotonic semantic notion of Allowed Entailment. Later I will prove that Allowed Consequence is sound and complete relative to Allowed Entailment.

Let .'Jbe any set of sentences called the reasoner's focus of attention. (For the meantime .'Jwili always be some or other subset of MP.) Now redefine Allowed Consequence relative to .'J, by substituting .'Jfor MP i.n definition 6. The resulting notion f--:r of Allowed Consequence relative to a focus of attention clearly is a generalization of ~ . Trivially, choosing .'J as MP, f--:r and ~ coincide. To go to the other extreme, choosing .'Jas the empty set, f--:r reduces to logical consequence. Intuitively speaking the focus of attention is a parameter in nonmonotonic reasoning which reflects some of the reasoner's relative concerns: to include a conditional q>>'lf ~ q>~'lf in .'Tis in a sense to let it matter that normally 'If if q> . It is a crude way of dividing defaults into two priority classes: defaults appearing in .'J are alike in having top priority; defaults excluded from .'fare alike in having no effect whatsoever on the nonmonotonic consequences of a theory. This part played by the parameter of focus will be greatly extended in the next section, where it will be filled by a vector of sets of defaults. The following notion is central in defining a preference relation on possible worlds which can be used to characterize Allowed Consequence:

DEFINITION 14: L,v ~!! :M,w means

'Ifi(Lv) n .'J ~ 'Ifi(:M,w).

Here 'Ifi(:M,w)is the theory {q>: :M,w f= q>} of win 'M. One world lies underneath another in the sense of this relation if it "gets more of .'Fright". With .'Jchosen within MP, though, more can be said about ~!!· Consider any given sentence q>>'lf ~ q>~'lf in .'J. We can say that w is irregular in regard to q>>'lf in 5\1 if 'M,w f= q> and 'M,w f= q>>\jl, but 'M, w j;t 'If. Equivalently, of course, w is irregular in regard to q>>'lf iff 'M,w j;t q>>'lf ~ q>~'lf. So L,v ~!! 'M, w just means that vis no more irregular than is w; not, at least, as far as the defaults we are focusing on are concerned.2

2 Notice that I allow possible worlds of different models L and 'M to be compared by '5.![, not just possible worlds of one and the same model. This has raised the eyebrows of some who are used to seeing worlds compared - say in regard to their similarity to a third world - but only within models. In standard developments of modal conditional logic, such as Lewis [ 1973], such similarity relations are of course what make conditionals true or false, as the case may be. I don't know why my comparing the worlds of different models is thought odd; maybe people confuse the metalinguistic task of defining a nonmonotonic consequence notion, which is what concerns me here, with the task of giving the truth conditions of an object­ language conditional. Indeed one of the differences between defaults and other conditionals on the one hand and consequence notions on the other, namely that whereas the former can be embedded the latter cannot, has been hid from view by the

This relation will be used to define a semantic notion of nonmonotonic consequence analogous to John McCarthy's [1980] notion of Minimal Entailment. First there is the notion of a set of premises r being minimally satisfied, relative to :F. at a possible world wof a model 'Jv{; DEFINITION 15: M,w f=.r rjust in case:

• (i) !M,w f=r and

(ii) if L,v pfand Lv~_rM,w, then M,w~.r L,v. Second, a sentence <p is an Allowed Entailment of premises r relative to :r (in symbols, r F=.r<t>) if <p holds in every world where ris minimally satisfied relative to :F: DEFINITION 16: r f=.r <p just in case for every !Mand w,

if M,w F=.r r then M,w F= <t>·

Now I can state the completeness theorem for Allowed Consequence relative to Allowed Entailment:

COMPLE1ENESS THEOREM 17: f f---:Pj> <=> f f=.r<p

This theorem provides Allowed Consequence with a semantic underpinning: the consequences which it is allowed to draw from a given set of premises are just the things which you can be sure are true in all least irregular worlds where the premises are true. It is a special case of the corresponding completeness of Prioritized Allowed Consequence with respect to Prioritized Allowed Entailment, which I will prove in section VI, so the proof will have to wait until then.

One consequence of either theorem which it is interesting to note at this point is that if r is consistent, so are its allowed consequences and entailments. This follows from THEOREM 17 together with DEFINITION 7 since, with the deduction theorem for ~ and the compactness of f-, for any consistent theory rthere is at least one set Q which is maximal r -consistent within :f. As Davis [ 1980] points out the corresponding thing does not hold in general for Circumscription: there are examples of theories which are classically consistent but from which contradictions follow using Circumscription.

5 Prioritized Allowed Consequence ...

Nonmonotonic reasoning needs to be sensitive to the fact that some defaults take precedence over others. Thus, to take the threadbare example, when it comes to drawing conclusions about the ability or otherwise of any given penguin to fly, the default that penguins normally cannot fly takes precedence over the default that birds normally can fly. Laws, interpreted following Raz [1990] as prima facie reasons to act, provide a less familiar example. The example is of added interest in that in the case of defaults which express prima facie reasons to act which derive from laws, precedence orders do not simply mirror the taxonomic order of the kinds which the defaults are about (as it does in the case of the birds, where the default about the subkind penguin takes precedence over the default about the kind, birds). Instead, precedence orders are in the legal case often simply declared in legal codes. So, for example, in virtue of the Jaw which requires this, the fact that a traffic light

practice of concentrating on unnested defaults. For more on the differences between consequence notions and conditionals see for example Quine [1950].

shows red is a prima facie reason to stop at an intersection. Additionally, however, the Jaw requires drivers to follow the directions of traffic officers, so the fact that an officer directing traffic is waving you on is a reason to pass through an intersection. And supposing you are waved on through a red light? The traffic code determines explicitly that the directions of traffic officers take precedence over traffic signs, which include lights, so in that case you ought to ignore the light and follow the directions

In this section I wilJ generalize the notion of Allowed Consequence to take into account priority orders between default conditionals. In the next section the notion of Allowed Entailment will be similarly generalized, and I wilJ prove the completeness theorem according to which these two notions coincide. The first step is to generalize the notion of a focus of attention from a single set of defaults to a linearly ordered (finite) set of such sets, or a focal vector.

DEFINITION 18: £i= <yt. (}2, ... ~>is a focal vector just in case each Yi is a focus of attention in the earlier sense.

The idea is that defaults in 91 will take precedence in conflicts with any defaults from qz, 93, ... ; defaults in 92 will take precedence in conflicts with any defaults from (jj, Y4···· and so on. Letting {i. = <yt. (}2, ... ~>be a focal vector and Jlbe a set of sentences, £iiJ{ is a useful notation for the focal vector <yr, (}2, ... ~, J-f>. Using this notation definitions and proofs can proceed by induction on the length of focal vectors. For a trivial start, £i_ can be "flattened" into a set U{i. of sentences as follows: -v<> = {}; and u {i.IJ{ = u£iu J{. The following notion generalizes to the case of focal vectors the earlier notion of maximal f­ consistency within :r:

• DEFINITION 19: Q is maximal f-consistent within .![is defined by induction on the length of 'I

Base step: {} is maximal f -consistent within <>; Induction step: Q is maximal f-consistent within £ii:J{ if (i) n s;;; u £iiJ{;

(ii) Q n U£i is maximal f -consistent within £i; and

• (iii) run f-f-_1_ And if Q s;;; Q * s;;; uqiJ{ and ILQ* f+l.., then n = Q*.
• OBSERVATION 20: Let 'M,w f= f\....0, where Q is maximal f -consi~cent within![. Then %i._!M,w)n u.1 = Q. This follows directly from (iii) in the induction step
• ofDEFINITION 19.

EXAMPLE 21: Let it be agreed that in reasoning about the properties of different kinds of birds, precedence orders on defaults must parallel the taxonomic order of the kinds which they are about. Thus where K 1 is a subkind of K2, any defaults about members of K 1 which are in focus must have higher priority than any defaults about members of K2 which are in focus. And let "<p>'lf ~ <p~'l'" be abbreviated "<p >J~ 'I'". Finally, let an open formula in a focal vector stand for the set of its ground instantiations. Then for example the focal vector

< PENGUIN(x) >/~-,FLIES(x), BIRD(x) >j~ FLIES(x)> will be acceptable, but

<BIRD(x) >1~ FLIES(x), PENGUIN(x) >1~ -,FLIES(x)>

will not. Call the first of these vectors !E And let our premises rinclude just

Vx(BIRD(x)>FLIES(x)) Vx(PENGUIN(x)>--.FLIES(x)),

BIRD(tweety), PENGUIN(tweety).

Using the frame of EXAMPLE 2 it is not hard to show that fis satisfiable along with Vx(PENGUIN(x) ~ -.FLIES(x)). So r is satisfiable along with all of _r1, which is just the set of all sentences of the form PENGUIN(c) >1~ -.FLIES( c). So there is a unique maximal f -consistent set · within <.1"1>, and that is _r1 itself. _r2 contains only sentences of the form BIRD( c) >1~ FLIES( c), none of which are consistent together with fv.'lj. It follows from DEFINITION 19 that 1j is the unique maximal f-consistent set within ![.

DEFINITION 22: (Prioritized Allowed Consequence): f f--y <p iff for every Q which is maximal f-consistent within :£, r,n f-<p.

CONTINUATIONOFEXAMPLE21: With fand ![as above, f f-y -.FLIES(tweety) but (since fu.1"1 is consistent) f ff:r FLIES(tweety).

It is not hard to see that here as in the previous examples a range of "irrelevant" background premises can be added to r without changing this outcome. Also, once this example has been understood it will be clear how others involving prioritization of defaults can be analyzed, such as the traffic-law case discussed informally above.

In the following section I go on to provide Prioritized Allowed Consequence with its semantic counterpart, Prioritized Allowed Entailment. All that needs to be done is to generalize DEFINITION 14 to an order $;.:ron possible worlds relative to a focal vector![. Substitution of ![for .1" in the earlier definitions then results in the right notions. I also prove that Prioritized Allowed Consequence is sound and complete with respect to Prioritized Allowed Entailment.

6 ... and Prioritized Allowed Entailment

Intuitively it is clear what needs to be done in order to define $;p for any given focal vector :I= <.'Ji, :J2, ... .'Jk>. It is necessary to combine the different orders :5;.1"1, :5;.1"2, ... $;1k appropriately, allowing :5;.1" 1 to order worlds first, then allowing :5;12 to further discriminate between worlds which as far as :5;.1" 1 is concerned are not discriminable, and so on. Such combinations of partial orders are the subject of the following definition, in which vis a finite vector of partial linear orders, each defined on the same domain, 'D:

DEFINITION 23: The alphabetic composition $;v of vis defined by induction on the length of v:

base step: $;<> = 'lf2;

induction step: $;tA$; = {(di,c£2): al$;~2 and if ar"'vc£2, then di $;a2}.

A straightforward induction on the length of v shows that $;vis a partial linear order on 'D. The familiar alphabetic order of words in a dictionary can be construed as such an alphabetic composition.

OBSERVATION 24: Let V= <$;p:5;2 .Sk>· For all a1,a2E 'D, ar"' ~2 just in case for each i:5;k, ar"'i c£2.

This observation follows with a simple induction on the length of v. It and the following observations will be needed later:

OBSERVATION 25: If ('11i(:M;w)n u:£) ~ rrfti..L,v}, then L,v $;:£ M,w. This can be seen with a simple induction on the length of![. The base clause is trivial: :5; <>is the universal relation on possible worlds of different models. For the inductive step, if (rrfti..M,w)n u §I~~ rrfti..L,v), then ('In(M,w) n u~ ~ 'In(L,v} and ('In(M,w) n ~ ~ 'In(L,v}. By induction hypothesis L,v :5;{i!M,w. By definition 14 also L,v$;:J{!M;w, so L,v$;fil:J{!M,w.

OBSERVATION 26: L,v ""f :M;w if and only if ('11i(L,v}n u![) = ('11i(:M;w)n u![).

This is a direct consequence of DEFINITION 14, OBSERVATION 24 and OBSERVATION 25.

Now the following notions of minimal satisfaction and Prioritized Allowed Entailment are completely analogous to the earlier definitions relative to a simple focus:

DEFINITION 27: Let ![be a focal vector. Then

• (a) :M;w f=.:rr means:
• (i) :M;w f:f; and
• (ii) for all L,v, if L,v f= rand L,v:5;.:r:Ni;w,

then L,vz.:r:M:w.

• (b) r Ff <p means that for every :M;w f=.:rr, :M,w f= <p. Now we have:

THEOREM 28: r f--y <p just in case r Ff <p.

Putting the focal vector as <.1">, THEOREM 17 is a special case of this theorem. THEOREM 28 follows immediately from the following lemma, which characterizes the possible worlds in which any given set of premises is minimally satisfied:

LEMMA 29: :M;w f=.:rr just in case for some Q which is f-consistent within :E M,w F r,n.

The proof of this lemma makes use of the following: FACT 30: M,w ffil:J{ r just in case

• Ci) :M:w F!i r, and
• (ii) for any Q*, if ('11i(:M;w)n u §I~~ Q*~ u §IJi and

n.n* ~ l.., then ('11i(:M;w}n u §1.1{) = Q*.

Proof of FACT 30 => Suppose M,w ffii:J{r.

Then (i) By definition of ffi.J:J{, M,w Fr. Now let L,v F rand L,v:5;!i:M;w, and suppose for the contradiction that not L,v""!i :M;w. Then L,v$;fil:J{ :M;wso

L,V""fil:J{!M,w. From this follows by OBSERVATION 24 that L,V""fi:M;w.

Also (ii) Suppose ('11i(:M;w}n u §IJ-{) ~ Q*~ u §IJi and L,v F n.A1*. Then Q * ~ ('In(L,v} n u §1~. so by OBSERVATION 25, L,v$;fil;;{M,w. Now by assumption :M,w ffi.J:J{r. Since L,v f=r, it follows that L,v ""fil#,w. By OBSERVATION 26 then ('11i(:M;w}n U§l~ = ('11i(L,v}n U§IJ{), so ('11i(%,w)n U§IJ{) = Q*.

<== Assume (i) and (ii). Clearly '.M,w f= r; now suppose L,v F rand L,v:5.£j,IJ{ '.M,w. Then (by definition of :;;,f.j.lid L,v :5..a '.M,w so (by i.) L/l~""f.j.'.M, w. By OBSERVATION 26, ('Ifr{'.M,w) n u.(i) k 'Tfi(L,v), and (by definition of :5.£j.lid L,v:5,J(M,w, so (by DEFINITION 14) also ('Ifr{'.M,w) n :J{) k 'Ifr{L,v). Thus ('Ifr{'.M,w)n u {ji:H) k ('Tfi(L,v} n u {ji:J{) k u §IJ£. By ii. then ('Tn('.M,w) n u §IJ£) = ('Tfi(L,v} n U{ji:J{). Now by OBSERVATION 26, L,rr-.a1J!M,w. This completes the proof of fact 30. ·

Proof of LEMMA 29 The proof is by induction on the length of:£. :I=<>: Trivial, since :5.<> is universal and {} is the only maximal r-consistent set within <>. So let :£=§11£ For convenience write I: instead of 'Ifr{'.M,w)n u

{i!J£. (So, very trivially, I: k u §IJ£ and I: ttl..) We have the following equivalencies: '.M,w f=.zT ¢::)FACT 30 '.M,w f=.a r, and if I: k Q* k u §IJ£ and run* tt J., then I: = Q* <=:)INDUCTION HYPOTHESIS, OBSERVATION 20 L n U{jis maximal r -consistent within £i, and if I: k Q* k U§IJ£ and run* ttl, then I:= Q* <=:)DEFINITION 19 I: is maximal r-consistent within §IJ£ <=:)OBSERVATION 20 For some n which is maximal r -consistent within !L

'.M,w F r, n. This completes the proof of lemma 29 .·

7 Strengthening Conditional Antecedents

Allowed Consequence and Entailment solve a problem about reasoning with conditionals which I will now very briefly sketch.

If Shoemaker-Levy 9 had hit Earth then there would have been an explosion equivalent to at least 500 megatons of TNT. It seems reasonable to infer that there would have been an explosion of this magnitude if Shoemaker-Levy 9 had hit Earth right after the world-cup final, but the logic of conditionals does not support this inference; Lewis [1973] argues convincingly that the logic of counterfactuals cannot validate the strengthening of conditional antecedents.

There is also the hypothetical syllogism, or transitivity. If Shoemaker-Levy 9 had hit Earth, then there would have been a 500 megaton explosion. And if there had been a 500 megaton explosion, then life as we know it would have come to an end. So, you might think, if Shoemaker­ Levy 9 had hit Earth, then life as we know it would have come to an end. But again the logic of counterfactual conditionals offers no support. It cannot do since, as can easily be shown, under minimal assumptions validity of transitivity entails that counterfactual antecedents can always be strengthened.

Let TR be the axiom scheme (q»\j/ " '!'>X) ~ q»x. The logic of counterfactuals cannot be allowed to validate TR, but the notion of allowed consequence suggests another way to account for the plausibility of inferences like the examples just mentioned. Just as in this paper the logic of defeasible conditionals was augmented by adding to any given premises as many instances of MP as one consistently can, the logic of counterfactual or for that matter any other conditionals can be augmented by adding instances of TR. This is achieved by including instances of TR in ![_. Then the defeasible notion of allowed consequence can account for reasonable examples of strengthening of the antecedent and the hypothetical syllogism, while unreasonable examples, such as inferring the coffee would have tasted good if there had been sugar and diesel oil in it from the coffee would have tasted good if there had been sugar in it, are "blocked" by background knowledge. Working through this and other examples in detail is something for another time.