Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques

74 CHAPTER 2. PREFERENTIAL STRUCTURES

So Ab ~ A. As W! = 31x.x = ac and Ab ~ A, there is no model of WI+ Ab, thus

• ~- ~ +-+ W, + Ab ~d ~ ~ Wl

F

or, but Con(W'). Contradiction. []

The idea of the next Lemma is, of course, the same as in Lemma 2.76. We fix

the extension of a predicate so it will be rigid under circumscription.

Lemma 2.77 Let P, P, be unary predicates, A := Bx, xl(x 7 ~ x! A Pcc A Pxl),

D := ~, D E MCO*Ab with I:*,II, P~ then P, EII or P, = P~, the minimized

predicate. I.e., to obtain a modular translation, we have to vary every other

unary predicate!

Proof Suppose not.

Let W := Vz(Px +-+ PIx) A 3x, ztVy(y = x V y = xt) A ~xPz. As Con(W, A),

(W,A) [,,, DCr e+ W+A ~ a. Let WI := Vz(Px e-+ Ptx) A Bx, zlVy(y = zVy = xl)

A 31xPx. As -~Con(Wl, A), (Wf, A)],',, D~ +-+ Wl ]- cr. Thus, W

+

Ab ~--< A.

Claim: A is valid in all models of W+Ab. Proof: Suppose there is m E M(W+Ab),

so = {x}. As >

W,

= {x}. Again by Lemma 2.r5 (and

the second condition in W), there is re, y m, 'rel E p(W q- Ab). As PI r II,

and P, 7~ P.~, ~P1~, : {x}. As m, ~ W, [[P~m, : {z} and 'rn, ~ -.d.

Contradiction.

SoW+Ab~A. As~-W,--+WandW+Ab~-A,W,+Ab~A, so there is no

model of W, + Ab (-~Con(Wq A)). Thus • F ~ ~ W, + Ab ~• ~ +-+ W, F- c~, but

Con(W'). Contradiction. []

Corollary 2.78 Let A and D be as in Lemma 2.77. Suppose we can do pairing,

e.g. we have enough set theory. Then we can forget the arity of the predicates

and have to let every predicate PI vary in order to obtain a modular translation[

2.1.4 Supraclassicality + cumulativity § distributivity

does not entail classical representability

S.Kraus, D.Lehmann, and M.Magidor have shown in [KLM90] that for any logic =

for s which is supraclassicat, cumulative, and distributive, there is a D-stoppered

preferential model 34, such that for all finite T C_ s T M = T. (See also [Mak94],

Observation 3.4.7.) Using a Lemma by D.Makinson, we now show that the re-

striction to finite T is necessary, by providing a counterexample for the infinite

case.

Both Lemma 2.79 and our counterexample, Example 2.3 below, have appeared in

[Mak94], Section 3.4 (Lemma 3.4.9, Observation

a.4.10).

The reader less familiar

with transfinite ordinals can find there a more algebraic proof that our coun-

terexample satisfies the logical properties clainaed. Our technique of constructing

a logic inductively by a mixed iteration of suitable length has, however, proved

useful in other situations as well (see [Sch91-2]), moreover, it is very fast and

straightforward: once you have the necessary ingredients, tile machinery will run

almost by itself.

2.1. PREFERENTIAL STRUCTURES 75

Lemma 2.79 (David Makinson, personal communication)

Let a logic = on s be representable by a classical preferential model structure.

Then, for all A C s x E s x r A there is a maximal consistent (under k-) ~ C s

such that A C__ A, x ~ A, and A :/s

We now construct a supraclassical, cumulative~ distributive logic, and show that

the logic so defined fails to satisfy the condition of Lemma 2.79, and is thus not

representable by a cpm.

Example 2.3 Let v(E) contain ~he propositional variables pi : i E a~, r. We shall

violate compactness badly "in both directions" by adding the rules (infinitely

many p~)[~ r and (infinitely many -~p~)I~ r. To account for distributivity, we

shah add for all q5 E /2 (infinitely many pi V r r V r and (infinitely many

-,p~- V r I~ r V r Closing under [~-. and classical logic co~ many times to take

care of the countably infinite rules will give the result.

The details We define the logic = by a mixed iteration: For B C Z: define

I+,r := {i < ~o: piVr E B}, I~,r := {i < co: -~piVr E B}. Define now inductively

Ao := A, for successor ordinals (a a limit or 0, i E co): A~+2i+l := "A~+21, A~+2i+2

"- A~+2i+l U {r V r I + is infinite or I2~+~;+ ~,r is infinite }, for limit A: Aa

'-- Aa+2i+l ,~5

:= I,J{Ai :i < ,~}, A := A~.

Note that = is monotone. Using regularity of wl, it can be shown that the logic

= is as desired.

We use the Lemma to obtain the negative result, as the logic constructed above

does not satisfy the Lemma's condition:

Consider now A := (3. Assume there is ~b such that infinitely many pi V r E A,

thus there is r such that infinitely many pi V r are tautologies. But then r has to

be a tautology, thus r and r V r E A. Likewise for "~pi V r So, the rules (infinitely

many pi V r N r V r etc. give nothing new, and A = A. In particular, r r A.

Assume now A C L: to be maximal consistent. So A decides all pl : i E a~.

Thus either infinitely many pi, or -~p; in A. Thus, r E A. Hence = is not cpm

representable.

Remark 2.80 In the last step, finiteness of r - i.e. all r have size < co - seems

to play a decisive role. So one might be tempted to try to obtain a positive result

with languages admitting infinite formulas. Yet, if the size of all formulas is less

than fl, a similar construction with/3+ pi's, and induction to/3 ++, will give the

same result.

2.1.5 A representation theorem for preferential models

Introduction The main result of this Section is Theorem 2.81, which shows

that "logically nice", i.e. definability preserving classical preferential models

76 CHAPTER 2. PREFERENTIAL STRUCTURES

are essentially characterized by infinite conditionalization, T U Tt C__ ~ U TI, dis-

cussed in [Mak94], Sections 2.2 and 3.4. The latter contains a detailed overview

of results linking preferential models and logical properties, and the reader is

referred there for a wider perspective.

The proof proceeds in two steps. Recall from the introduction that a classical

preferential model for s defines a function f : T'(Mc) -+ "P(Mc). We first char-

acterize such f generated by a preferential structure (Proposition 2.83) and then

characterize the logics corresponding to such f (Proposition 2.84).

We state the main result and then turn to the proofs.

Theorem 2.81 Let = be a logic for s Then there is a definability preserving

classical preferential model ~%4 such that T = T ~ iff

(=I) T=Tt-+T=TI,

(=2) T is classicaUy closed,

(=3) r C T,

(--4)

T u T, c_ T u

for all T, Tr C s

Moreover, given =, 3/l can be chosen transitive and irreflexive.

Remark:

Example 2.2 (1) shows that " --+" of Theorem, 2.81 is false in general without

the definability preservation condition, by failure of (=4), Example 2.2 (2) shows

that there are structures ~4, which are not definability preserving, but whose

logic nonetheless satisfies (=4).

We first show that every preferential structure has an equivalent irreflexive one.

Lemma 2.82 For any preferential structure Z =< X, -<>, there is a preferential

structure Zt :=< Xl,-< I > such that

(1) #z = ~z,,

(2) Z/is irreflexive,

(3) if Z is transitive, then so is Z 1.

[]

Proposition 2.83 Let Z be any set, 3) ~ 7)(Z), f : Y -+ ;D(Z). Then there is a

preferential structure Z =< 2~, --<> such that for all X E 32 f(X) = pz(X) iff

(fl) f(X) C_ X and,

(f2) X C_ Y -~ I(Y) N X c_ f(X)

for all X, Y C 3;.

Moreover, given such f, Z can be chosen transitive and irreflexive.

(Note that, if 3; is closed under finite intersections, then, in the presence of (fl),

(f2) is equivalent to (f2'), where (f2') f(X) n Y c I(X n Y).)

2.1. PREFERENTIAL STRUCTURES

77

Proof of Proposition 2.83 "-+': easy

"+--": Let

Yx := {x ~

y:x ~ x -/(X)}, Fx := IlY=.

(Ify~ =

(a, F~

= {~},

and

the following Claim 1 will be trivially true.) It is important to note that F~ # 0

by the axiom of choice: A product of non-empty sets is non-empty.

Claim 1: Let X E Y.

(1)

If z E

f(X),

then there is gx E Fx with

ran(gx)nX =

(2) 9 ~

f(x) ~ ~ ~ x and ~g ~ F~.(ra'~(g) n X) = 0.

To clarify the main idea, we first define in (A) a simple preferential structure,

which describes f on y, and then turn in (B) to a more complicated structure to

achieve transitivity.

(A)

Let

X

:= {<

x,g

>: x

E

Z A g

E

F~}, and <

xt, gt

>-4< x,g > :*-+ zl

E

ran(g),

let U, :=< X, -<>, and # := #z.

Claim 2 (A): For

X E Y, U(X) = p(X).

(B)

Let I := {<

y,g,i

>: y E Z, g E Y v, i = 0,1}, W :=

ZxI,

and define < x/,<

U, gt, it

>> -~ < x,<

y,g,i

>> iff (a) y =

yt A g = gt

and (bl) x 7 ~ y A x =

zt

or (b2)

x = y A xt E ran(g).

Finally, let Z :=< X,-4>, # :=

#z.

Remarks:

1) Condition (a) makes the construction "local", we only have to consider two

"layers" of Z at a time.

2) Condition (bl) makes every x 7g y non-minimal in Z<y,g,0> U Z<y,~,l> - where

Z<y,g,i>

:= {< z,<

y,g,i

>>: z E Z}.

3) Condition (b2) makes x = y the "center of a star" in Z<u,gd> : any element of

ran(g) prevents x from being minimal.

4) ~ is transitive, as can easily be seen by examining the four possible cases.

As in case (A) we formulate and show

Claim 2 (B):

For

X ~ y, f(X) = #(X).

By Lemma 2.82, there is a transitive, irreflexive cpm Z! =< A't, ~ t > such that

f(X) = #z(X) = #z,(X)

for all X E Y. [] (Proposition 2.83)

Proposition 2.84 Consider for a logic = on 12 the properties

(:1) T=TI-+T=T/,

(=2) T is classically closed,

(=3) r _c T,

(=4)

TU Tt CC TUTt

for all

T, Tt C 12

and for a function f : y --+ T'(ML) with

Dc C 3J C Mc

the properties

(fl)

f(X) C X,

(f2)

f(X) fl Y C f(X M Y),

(f3) f is definability preserving

for all X, Y E Dz:.

The following holds:

(a.1) If f satisfies (fl), then = defined by T := T S satisfies (=1) - (---3).

(a.2) If f satisfies (fl)-(f3), then = defined by T := T ~' satisfies (=1) - (=4).

78

CHAPTER 2. PREFERENTIAL STRUCTURES

(b.1) If = satisfies (=l) - (=3), then there is f : P(ML) 0-~ :P(ML)

such

that

= T I for all T C s and f satisfies (fl) and (f3).

(b.2) If = satisfies (=1) - (=4), then there is f :

P(Mc) --, P(Mc)

such that

= T S for all T _C s and f satisfies (fl)-.(f3).

Recall that, as Dc is closed under finite intersections, in the presence of (fl), (f2)

is equivalent to (f2')

X C Y ~ f(Y) M X C I(X).

Proof of Proposition 2.84 straightforward []

Proof of Theorem 2.81 straightforward with Proposition 2.84. []

2.1.6 General smoothness

Introduction We examine stopperedness in a very general form (2(-

stopperedness), and characterize X-stoppered classical preferential models by

coherent sequences up to a strong form of equivalence (~), in Proposition 2.106.

For that purpose, we examine for each < a,i > the set of < b,j > such that

< b,j

>-~<

a,i

> in detail. The crucial notions are "X-nice" (Definition 2.91)

and

"3,4 -

X-coherent sequences" (Definition 2.98), which are used for the final

characterization.

Definition 2.85 For Y C_ "P(ML), a E 1~/c, let Y[a := {A E Y : a E A}. (The

double use of [ will be unambigous from the context.) Fix ~-t =<

N,I,

<> and

a E Mz, and define A~ := {A C ML: a r f~4(A)}. (Recollect that

fm(A) =

{ m E A: Si E [ (<

m,i

>E N A-~ <

mf, it

>E

N(ml E A A < ml,# > -~

< m, i >) ) }. ) Thus, A~ [a consists of those subsets of Me, which "minimize"

a away.

Let I~ := {i E h < a,i >E N}. Note that I~ r 0, by No = Me. For i E I~, let

K~,~:={mEMc: ~<m,#>EN(<m, ir>-~<a,i>)}.

Let K~ := {K~,~ :

i E h}. For any K C ~(Mc), let A~ := {A C Me: VK E/C.AG K r ~}.

If necessary, we shall index, like A; u etc.

A short motivation, to be made precise in Lemlna 2.87: For a E A to be minimized

away inA, we have to kill

all < a,i

>E N by some <

m,j > -~ < a,i >, m E A,

so all K~,i ~ K, must have non-empty intersectibn with A.

Fact 2.86 For A C M~, a E A: A r Ay[a e-~ a E fM(A),

Proof A~Ayla ~--~ a~AV AgMLV aE f~(A).

Lemma 2.87 For A/t, a E Mz: Aa~a = A~:=~a.

2.1. PREFERENTIAL STRUCTURES 79

Proof A E A~ra ~ a E A A A C_ Mc A a ~_ fz4(A ). If a E A, then a r r

V < a,i >E N.?b( b 9 A A ~#(< b,# >9 N A < b,# > ~ < a,i >) ). bEK~,~

~#( < b,i[ >9 N A < b,i~ > -~ < a,i > ). Thus, ifa 9 A, a r f~(A)

V < a, i >E N.~b( b 9 A A b 9 I(~,~ ) ~ Yi 9 I~(I(~,~ M A ~ 9). Finally, A E A~ [a

a 9 A A A C Mz A a f[f~(A) ~ a E A A m C_Mc A Vi 9 I~(I(~,~nAr ~)

a9 A, A 9 A~co ~ A 9 A~co~a. []

Corollary 2.88 Let 3d, M ~ be given. Then Va 9 Mc ( .A~ [a = A~c~, [a )

f~= f~,.

Proof By Lemma 2.87, Ay~a = A~ [a, likewise for Adz. Now, f:~ = f~,

Aff[a = A~'[a For the converse, note that f~(A) = {a 9 A: A r Aft[a}

Lemma 2.89 Given K-'-7 = {Kt~ : a 9 Mz} such that all K:t~ C 7)(Me), there is

a cpm M :-~ M~7 such that No = Mc and for all a 9 Mc Az,~ [a = A~c~ [a.

Proof We have to construct ~ =< N, I,-~>. Assume without loss of gen-

erality KI~ = {Kl~,i: i < a~}. Let M0 := {a E Mz : a~ = 0} (i.e. ~I~ = 9),

M1 := {a c ~VZc : ~ = 1 A a s K~,o}, M~ := ML - (M0 U M1). For ~ E M~, set

/3~ := a~, for a E/1//0 U M1, set/?~ := 2. Set N := {< a, i >: i </3~, a E Me} and

[ := sup{fl~ : a E Mz;}, so No = Mz;.

ForaEMo, set <m,j > -~ < a,i> for allj<t3~,i</3~,mCaand <a,j >

-.4 < a,i > for all j < /3~, i < 3~, j r i.

ForaEM~,set <m,j>-~ <a,i> for allj<~3,~,i<fl~,mCa, mE Kl~,o

and < a,j > -~ < a,i > tbr all j < A, i < ~ j r i (recollect: a E K/~,o).

For a E M2, set < m,j > -~ < a,i > for all j < fl,~, i < /3a, m r a, m E KI~,i

and < a,j > -~ < a,i > for all j < fl~, i </?~, j r i, if a E Kf~,~ (note that then

~ = c~ > 1, as a E M2).

It is easy to see that -~ is non-reflexive, and that .M is full in the sense of Definition

2.92 below. We have to show that for all a E Mc A~c,, Ia = A~c~ [a.

Case 0, a ~ Mo: A~c,o = Ao = ;c'(ML) and A~c,o [a ~ {A _C Mz : a ~ A}.

For

a E Mo, ICy {K~, "'~

= It,,~} = {Me}. Thus, A~c~ra = {A c_ Mc: a E A A

AnMzCO}={ACMc: aEA}.

Case 1, a 9 M~: K:~ ~t4 = {I(~M0, It'~,a~l} = {I(1~,0} --- K:I~.

Case 2, a 9 M~: Zy = {~r(~,~ : i < Zo = ~} = ~C/o.

Lemma 2.90 Let K, ]Cl C 7)(Mz).

a) A~:, _c A~: ~ VK E ~3KI E K/(Ir _~ K).

b) Arc, r a c A~c [a ~ VI( E ~.(a ~_ [( -+ 3I(I ~ ]Cl([(l C_ ]()).

Proof We show b), the proof of a) is similar.

"-~": Let K E K, a ~_ If. So CK = Mc - l( ~_ A~c [a, so by A~o [a C A~: [a,

CK r M~:,Ia ~ (as a E CK) 3I(] E K](CK n K/= (~), thus K/C K.

"~": Let A E A~:,ra. Thus a E A A Vt(I E K.I(AnKI ~ ~). Let K E/~, we have

to show A n K ~ (~. Case 1: a E K, then A C? K ~ 9, as a E A. Case 2: a r K,

so there is KI such that Kr C K. As K/M A r (~, K n A r (~. []

80 CHAPTER 2. PREFERENTL4L STRUCTURES

Definition 2.91 Let X C P(Mc).

Given Ad, X C_ Me, set g(X) := X - #(X) (remember: #(X) := fM(X)).

K C_ M~ is called X-nice iff for all X E X either K Cl X = ~ or K ~ #(X) r ~.

]C C ~(Mz) is called X-nice iff all K E E are X-nice.

Given K, X, let X~- := {X E X: #(X) M It" = ~}, and K- := If - U{~(X) : X E

x~.} = K- UX~.

Definition 2.92 Call Ad full iff

w ~ K~,~(~ r a --+ Vj e I~(< ~,j > ~ < ~,i >) and ~ = ~ ~ Vj e Z~- {i}(<

"m,j > -4 < a,i >) ) for alia E M~, i E I~.

Note that if 34/ is the full model corresponding to M, (obtained by adding

"redundant" pairs, i.e. ifm r a and < m,j > -< < a,i >, add < re, j! > -~

< a,i > for all jl E I.~ to -~a, and likewise for m = a ), then 3fl ..~ 341, and if

A4 is X-stoppered, then so is A/f I, though not necessarily the other way round!

Lemma 2.93 Let .ad be transitive. If 34 is X-stoppered, then all K;~ are X-

nice. If 3d is fui1, then the converse holds, too.

Proof "--.'": Let a ~ _a/Ic, K ~/C; ~4, X E X. We have to show K M X = (~ or

K nf~a(X) r ~. Such K is of the form K~,~, with < a, i >E N. Let b E K~,~ N X,

so there is < b,j >~ N, < b,j >-<< a,i > . If < b,j > is minimal in Nx, we

are done, as then b E f~a(X). Otherwise, there is < c, k >E fix minimal in Nx,

so c E f~v4(X), and < c,h >-<< b,j > . By transitivity, < c,k >-~< a,i >, and

c E K~,~ M f~a(X).

%--": Let < a,i >E Nx be given. Consider K := K=,i. If KMX = ~, then there

is no < ml, i! >E N, ml E X, < ml,# > -.4 < a,i >. So < a,i > is minimal

in Nx. Otherwise, by X-niceness, there is mr E K M fM(X). Thus, there is #

such that < mr,# > -4 < a,i >o Moreover, there is iH such that there is no

< m+,i + > --4 <mv, ilr >, m + E X, ( Note that < rnl, ill >r a,i >. ) But

then, < ml,ill > is minimal in Nor, and, by fullness, < mf, i//> -4 < a,i >. []

Fact 2.94 Let K* C I~7, Kl ~ K- for some K C Me, then K! is not X - nice.

Proof Let x E Kt-K-. So there is X E X such that #(X) glK = ~, and

z E g(X). But then ~(X) Cl KI = ~, and KrN X # 0. []

Definition 2.95 Define for K C_ Me, X, 3/[ by induction:

K0 := K, K~+I := K2, Ka := f3{K~ : c~ < s for limit ~.

Note that K~ is descending, and if Ks = K~+I, then K 0 will be constant after ct,

so after card(K) + steps, the sequence is constant. Thus define K* := K~d(t~)+.

(To be more precise, one should index 9 by X.)

Lemma 2.96 K* is the largest X-nice set K/C K.

2.1. PREFERENTIAL STRUCTURES

81

Proof Suppose K* is not X-nice. Then there is X E X such that

K*N-g(X) r

(~, K*Nf(X)

= (~. Let a <

card(K) +

be such that K* =

I(~.

Then X ~ XKo, and

/(~+tMg(X) = ~, so by K* C_ K~+t, K*M~(X) = (~, contradiction. Suppose there

is K~ _C K, K~ X-nice, K~ g K*. Take c~ such that

Kt C K~, K~ f[= I(~+t = Kg,

contradicting above Fact 2.94.

Putting Lemmas 2.90 and 2.96 together, we see:

Lemma 2.97 Let/C C

7)(Me), ;~ X, a E Mc

be given.

a. Then there is s X-nice with A~ = A~:, i# (*) VK ~ ~K + E ~.K + C K*.

b. Then there is K/ X-nice with

Ax:[a = A~c,[a

i# (,b) VK E /C(a r K ---,

~K+ ~/C.K + c_ K*).

We then say that < a,/C > satisfy (*b).

Proof We show b., the proof fbr a. is similar.

~ e--" Suppose (*b) holds. Let )~ :=

{K* : a r K,

K E ~}. By Lemma 2.96, all

K* are X-nice. By definition, VK E/d(a r K --~ ~KI E ]~l.Kl _C K). By Lemma

2.90 b),

A~c,[a c ApcIa.

On the other hand, let K/ ff ~, so there is K ~ K,

a ~ K, K/= K*. Bug then, by (.b), ~K + E K;.K + _C K* = K/. Thus, by Lemma

~.~0 b), A~Ia _c .4~,[a.

" --+" Suppose there is such ]C/. Fix K E ~, a r K. By Lemma 2.90 b), there

is K! E /C/, K! _ K, ~hus a r Kr As K/is X-nice, by Lemma 2.96, K/C_ K*.

Again by Lemma 2.90 b), and a r162 there is K + _C K~ _C K*, K + E K. []

Definition 2.98 Let M and X be given.

A sequence E =< c~z :/3 < a >, o- 0 C ML will be called A4 - X-coherent i# it

satisfies:

1. For each/3 < a there are Az C Mc, X~ _C X such that ~Z = AZ U U{#(X) :

X E X~} (where # is #z4) and cr~+l = A~ U U X~,

2. if/ira(A), then ~ra = U{~r~ :/3 < A}.

In addition, we call

-

inductive for !/__ 1P(Mc), i# (to r Y --4 V/3 < c~.c~ ~ Y and

inductive for <

a,Y >, a E Me, Y C_ ~P(Mc)

i# a E ~ro A ~o ~

Y[a --~

v/~< ~.o-,~ CY[a.

We say (+) holds for Y, i# all .M - X-coherent sequences are inductive for Y,

and (+b) holds for < a, Y >, i# all ]M - X-coherent sequences are inductive for

<a,Y>.

Lemma 2.99 Note that for increasing E =< ~z :/3 < c~ >, crp _C M~ a E ~ro A

~o ~ Y[a --* V/3 < o~.~r~ ~

Y[a

is equivalent to a E ao A o-o r Y --+ Vfl < c~.cr~ r Y.

Proof

"---r a E o'o A oo r Y ~ a ~ o'o A O'o r

Y[a -~, Vfl

<

o~.cr 9 ([ Y[a.

As

#o C r a E

~a, soV/3 < ~-~0

~Y"

:'~-": a ~ Oo A ,~o r Y[a ~ a e oo A ~'o r Y ~ V/3 < ~.~'~ r Y ~ V/3 < a.o'~ r

Y[a

82 CHAPTER 2. PREFERENTIAL STRUCTURES

Fact 2.100 A = U{Ai: i e I} -~ f~(A) c U{J~(ai) : i ~ [}

Proof Suppose not, let a ~ f~(A), a f[ O{f34(Ai) : i e [}. As f~(A) C_ A,

there is i such that a ~ A~, a f~ fM(A~), contradicting Lemma 2.5. []

Lemma 2.101 Let E := < crZ : 3 < c~ > be 3A - X-coherent. Then < fm(crz) :

< c~ > is descending.

Proof (by induction) Let era = AZ U U{#(X) : X E X~}, crZ+ 1 = A;~ U U Xz.

Then #(crO+,) C #(Ap) U U{#(X) : X E X~} C crp C Co+, (by Fact 2.100).

aemma 2.5 shows #(r C #(az). Let lira (A), ~rx = U{crz : fl < A}, 81 < A, so

= u U{op : h" < h' <

#(era) C_ #(crZ,) U U{#(~r~) : fit < fl < A}. By induction hypothesis for fl~ < fl <

c so c

Lemma 2.102 All < a, A~ > satisfy (+b) iff all 34 - X-coherent sequences are

constant under #~, i.e. for all jtd - X-coherent sequences E := < cr;~ : fl < c~ >,

Proof Let E Ad - X-coherent be given.

"--*": Let a E #(~o) be given, by Lemma 2.101 it suffices to show a G #(crZ)

for all fll So a G #(~o) C Cro, and by Fact 2.86 ~o ~ .A~ [a, so by prerequisite

c~ r A~ ra. As a G c~0 C c,p, a E #(c~) by Fact 2.86 again.

"~-": Let #(~o) C #(crib) for all fl < c~, assume a C cro A c~0 ~ AX[a, so by Fact

2.86, a E #(cro) C #(cr3) _C or3, and by Fact 2.86 again, ere ~ A~ [a. []

We now get cumulativity for free:

Corollary 2.103 Let D C X, and all < a,A~ > satisfy (+b) tbr Ad, X. Then

3A is cumulative.

Proof Let = := =-~, and T G Tf C__ T, T, Tt C_ s Thus, #(Mr) C_ M 7 C_

Mr~ _C Mr. Consider E := < Cro := Mrs, r := Mr >. E is M - X-coherent:

Mr, = MT, U #(MT), and MT = Mr, U Mr. So #(MT) = #(MT,) by Lemma 2.102

and T = T-I. []

Lemma 2.104 Let E := < cr z : fl < a > be 2M - X coherent. Then K ffl era =

-~ Vfl < a(cr~ n K* = 0).

2.1. PREFERENTIAL STRUCTURES

83

Proof Let K (1 ao = 0. We show V/3 < a(cr;~ ;-1 If~ = 13) by induction, and are

done by

K* C_ I(~

for all/3.

As K0 = K, it holds for 0.

Suppose it holds for ft. o" m = A~ U LJ{#(X) : X E A'm}, and (rm+~ = A m U [.j 2(~.

Assume (rZ+l

(]

IfZ+l r 13. o-~ F1 I( m = (Az F11(z)

U (U{At(X) : X E 2(Z} F1

Ifz)

= 13, so, as

KZ+~ C Ifz, (Am N Kz+a)

U (U{#(X) : X E 2(Z} N Ifz) = 13. On the

other hand,

(A~MK~+~)

U (U2(z cl Kz+I) # 13. Thus, there is X E 2(a _ 2( such

that #(X) F1 I( m = 13, X fl Km+~ .fi 0. As, however,

X E 2(Kz

and

I(~+~ = K'~,

X F1 K0+I = 13, contradiction.

Let now

lim(A),

and assume Y/3 < A(a0 F1 IfZ = 0), but ~r~ fl

Ira # 13.

As ea =

U{a0 : /3 < A}, there is/3 < A such that ~r~ FI

If~ # 13.

As

I(~

= f-I{Kz : fi < A},

~r z M I(-~ # 13 for all 7 < A, contradicting ~ Cl K z = 0. []

Lemma 2.105 a. Given A/ and X, K] C P(Mc), (*) in Lemma 2.97 a. for K]

and (+) for .djc are equivalent.

b. Given .~, 2(, a E ML, ~ C 7)(Mc), (.b) in Lemma 2.97 b. for < a, K: > and

(+b) for < a, ..4~2 > are equivalent.

Proof We show b., the proof of a. is similar. (We use Lemma 2.99.)

(*b) ~ (+b): Let E be 3,t - 2(-coherent. Let a E ~0, Oo ~ .A~:, so there is K E K

such that KFlao--- 13. By Lemma2.104, V/? < c~.c DF1K* = 13. As a E oo and

K F1 ~0 = 13, a ~ K, so by (*b), there is K + E K, K + __C_ K*, so

Vfl < a.~p r .Ajo

(+b) -~ (*b): Let K E K, a r K. Define E =< o-p : fl < a > by o'fi :=

CK m

with

c~ = card(K)++

1. By definition,

CI(.~ = CKmUU{#(X):

X E 2(t,b}. Moreover,

as I(a =

f-l{Ii~

: 3 < A}, cr.x = U{~r~ : /3 < A}, and as I(~+~ =

I(~- U2(K~,

so CI(o+~ =

CKo

O U 2(Ke. So E is coherent, and by (+b) thus inductive for

< a, Ajc

>. As a ~ K = Ko, a E ~ro =

CKo.

Moreover, as K = Ko E K:,

CKo = ~7o r Ajo

So

CK* = ~r~d(;~-)+ r Aic,

thus there is K + C K*, K + E K.

[3

Proposition 2.106 Let 34 be a ~.ransitive cpm, No =

Me.

Then there is M l

with Nl0 = Me such that

1) 34 ~M/,

2) M/is 2(-stoppered

iff

1) all yt4 -2(-coherent sequences are constant under Atz4,

2) #M (X) r 0 for all0r

Proof "-~":

i) Assume there is such 2(-stoppered .hal t. Then all/C~' are 2(-nice (Lemma 2.93),

so all <

al,]C~'

> trivially satisfy (*b) in Lemma 2.97, b., so all < a/,.A~:~, >

satisfy (+b) (Lemma 2.105, b.), but for all a, .A~[a = A~[a = .A~e,[a by

34 ~ A//t (Lemma 2.87, Corollary 2.88). So, as the definition of (+b) looks only

at

Y[a,

in particular all < a, .dam > satisfy (+b), so all 3//-2(-coherent sequences

are constant under #M (Lemma 2.102).

Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques

Подождите немного. Документ загружается.