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

44

CHAPTER 2. PREFERENTIAL STRUCTURES

Let a propositional language s be fixed.

Definition 2.1 Z =< X,-<> is a preferential structure iff X is a set of pairs

and -~ is a binary relation on X. We say that Z is transitive, irreflexive etc., iff

-< is.

< y,i

> is called a minimal element of

XrY

in Z iff: 1. <

y,i >E X~Y,

and 2.

there is no <

yt,# >E X[Y

such that <

yl, it

>--<<

y,i >.

Thus, Z defines a function

#z : V -+ V (V

the set-theoretic universe) by

#z(Y)

:= {y : there is i such that <

y,i

> is a minimai element of X[Y}.

(Note that #z is thus a proper class, but this need not bother us.)

Given a set Z,

,az,z

shall denote #z [P(Z).

(A short motivation tor indexing: if there is just one copy of y in .I:', and e.g.

y/--< y, then, for y E Y, y will not be minimal in Y if yl E Y. If we want two

yt, ytl

necessary in Y for y not to be minimal, we need something like

yt ~ < Y, 0 >, yrl

-4 < y, 1 >. So the different <

y,i >, < y,j

> encode conjunction, the different

y/-~ < y, i >, y//-< < y, i > disjunction: in other words, we look at the product.)

If all elements occur at most once, we will sometimes omit indexing.

Z =< A',-<> will be called y-smooth (terminology of [KLM90]) or 32-stoppered

(terminology of [Mak94]) iff for all X E Y and <

y,i >E X[X,

either <

y,i >

is minimal in

X[X,

or there is <

yl,il

>-~<

y,i >, < yt, il

> minimal in

X[X.

In shorthand, all non-minimal elements are "killed" by minimal ones. It is an

immediate and important consequence that then for X E 32, 22 iX r 0 implies

We sometimes further restrict -< by requiring it to be transitive or irreflexive, and

either say so explicitely, or use the abbreviations i/t.

M is called ranked, iff -~ is modular, i.e. iff one of the following three equivalent

properties holds ([LM92J) for any x,y,z: 1. x 7~ y, y 7~ z, z -< x --+ z 4 y, 2.

if x -< y then either z -~ y or x -< z, a. there is a totally ordered set X and

a (ranking) function r : N -~ X such that

:~" -.< y ~ r'(x)

< r(y). (It helps

the intuition to picture a ranked partial order as "layers of pancakes" - where

~he particles within one pancake are incomparable, but everything is comparable

from one pancake to the other.)

The following example shows that there is Z V-smooth, and z E ~o+ 1, such that

there is

X, x C X -#z(X),

but there is no such X minimal by set-inclusion:

Example 2.1 Let Z := < X,-<>, where X := {< a0,i >: i < co} tO {< m,0 >:

m < w}, and < m, 0 > -4 < co, i > iff i _< m. Consider now # := #z, then

co E X - #(X) iff co E X and X contains a cofinal subset of w - but, of course,

there is no minimal such X.

Remark 2.2 Consider Z =< X, -~> .

1) Note that X and Y may be finite, X [Yr ~, and still /Lz(Y) = @: Just look

at Z :=< {< m,0 >,< m,1 >}, < ca,0 > -~ < m, 1 > -< < m,0 > > , and

Y := {m}. Such "suicidal techniques" can be used extensively tbr general -~.

2.1. PREFERENTIAL STRUCTURES 45

2) Note that given any Z and Z, there is a structure

Zf

:=< ,gf,-< I > such

that #z = #z,, and, for all z E Z, there is <

z,i

>E A'!, if we admit cycles.

(Alternatively, one might use infinite descending chains, see Lemma 2.82 below.)

Proof Let Z = < X,-<> be given and Y := {z E Z :there is no < z,i >E

X} r (a. Define Zl :=< X!,-< ! > by A2! := X U {<

z,j

>: x E Y, j E 2}. Let

-4 I agree with -4 on X, and extend by < x, 0 > -4 ! < x, 1 > -< ! < x, 0 > for all

z E I/. Note that the construction preserves transitivity, i.e. if -< was transitive,

then so is -4 !. We show #z = #z,.

Let X be given, z E X. Case 1: x E Y: Then z ~ #z(X), since there is no i su&

that <

z,i

>E ,12. But the only <

x,i

>E A'! are < x,0 > and < x,1 >, and

<z,0>-~l<x,l>-<I<x, 0>,soz~#x,(X). Case 2: zEZ-Y: Note that

"old" and "new" elements are not comparable, so z E #z(X) iff x E #z,(X). []

Definition 2.3 A preferential structure ~l =< A', ~> will be called a classical

preferential model (cpm) for s iff for all < x, i >E X, x E l~iL.

3A will be called definability preserving (dp) iff # :=

#~,a~ : 79(ML) --+ 7)(ML)

is definability preserving.

By the above, 3A defines a logic on s by T ~ := T**, i.e. T ~ := {~ E s q5 holds

in all

rn ~ #(MT)).

A cpm 3// will be called stoppered, iff it is D-stoppered.

A logic = for s is said to be representable by a cpm, iff there is a cpm 3//for Z;,

such that for all T C s T ~4 = T.

For <

rn, i

>E .g, we shall abuse notation and say <

m,i

>~ r iff rn ~ r for

q5 E s We also write sometimes rni for < rn, i > .

Remark 2.4 Our definition is a notational variant of e.g. the definition in

[KLN90]: The function l : X --+ Mc in [KLM90] has the same meaning as our

indices: I need not be injective. Neither need I be onto, and we do not require

for all rn E Mz: some < rn, i >E X.

I- corresponds to our "abuse of notation" just introduced.

Example 2.2 We give two examples for cpm's which are not definability pre-

serving, they will be used later on.

Let v(s := {pi : i E co}, m0, rrz~ E Mc be defined by

rno ~ {pi

:

i E co},

{-,po } u {p, : o < i < co}.

(1) Let M :=< Mcz{0},-<> where only < rng,0 >-<< rno, 0 >, i.e. just two

models are comparable. Let # :=

#M,Mc, T

:= 0, TI := {pi : 0 < i < co}. We

have Mr = Me, #(Mr) = Mc - {m0},

MT,

= {rno, mo},

#(MT,)

= {rno}. So

by the result of Example 1.1, Ad is not dp, and, furthermore, Tr = T,

TI ~ =

{~p0} U {Pl : 0 < i < co}, so -~P0 E (T tO T/) an, but T ~ U

T! = TtO T/ = T-7, so

-~p0 r TT. (Thus, Theorem 2.81 below can fail without the @-condition.)

D.Makinson gives in [Mak94], Section 3.4, below Observation 3.4.8, another exam-

ple of a preferential model violating condition (=4), and definability preservation.

(2) Let M/:= Me- {too}. Consider now 3.4 := < X,-4>, where A" := {< rn, 0 >:

rn G Mr}

U {< rn0, m >: rn E

Mr},

and define -4 by < rn, 0 > -< < m0,rn > for

46 CHAPTER 2. PREFERENTIAL STRUCTURES

all m E MI. Let again # := #z4,~I~, and T := T M. Thus, #(Me) = M/, so JM

is not dp, and #(A) = A for all A r Me. (Note that the only model which can

be eliminated, is rno. But you have to kill all copies < m0, m >, rn E Mr, and

for that you need all m E MI.) Let now T := -~. Then MT = Mz, p,(MT) = M~,

andT = T by the above. If T/ is such that TI =fi ~, then Mr, r Me, and

#(MT,) = MT,, so T-7 = T~. So, for all T C_ s ~ = ~. (Thus condition (=4)

of Theorem 2.81 below is trivially true, and Theorem 2.81 may hold even if the

dp-condition fails.) []

The following is a very simple, but equally important fact on preferential model

structures.

Lemma 2.5 Let A,B C Mc. Then A C_ B ~ fM(B) n A C fM(A).

particular, fM(B) C__ A C B ~ f~4(B) C f~(A).

So, ill

Proof LetmEf.~(B)nA. SomEA, and there is i E f such that < m, i >E N,

and there is no < rn1,# >E N, 'ml E B, < rn/,i/> -< < m,i >. But then there

can be no such < m/, # > with rnf E A, as A C B. Consequently, m C fM(A) .

[]

Consequently, the %enter" of a set cannot be determined by simple preferential

relations: Consider A := {0, l, 2}, B := {-3, 0, 1, 2}. Let the center of X, c(X)

be that element of X, which has the least maximal distance to the others (if

this is well-defined). So c(A) = 1, e(B) = 0. If the center were determined by a

preferential relation, {c(X)} = J;~(X),

]88

= {0} C A C B, but it is not the

case that {0} = f~(B) C f~(A) = {1}. (Of course, this is an unfair example, as

fM does not '*see" the additional information on the distance. Still it illustrates

the problems when trying to find "best fits", or approximations via preferential

structures. See Chapter 4 for a different approach to these questions.)

In this Section 2.1 on preferential models, we first discuss the completness results

for preferential models presented by Kraus, Lehmann~ Magidor, and G~irdenfors,

Makinson.

We investigate in Section 2.1.2 in detail (a slight modification of) an order intro-

duced by Kraus, Lehmann, Magidor. We then compare in Section 2.1.3 in detail

defaults and preferential models, in a continuation of work by Imielinski. The

completeness results by Kraus, Lehmann, Magidor were given for single formulas

on the left hand side, i.e. for inferences of the type o~ I~ ;9, and we show in

Section 2.1.4 by a counterexample (Example 2.3) that their generalization to the

infinite case fails. Section 2.1.5 presents our own representation result for mini-

mal preferential models, for the general infinite case. In Section 2.1.6 we discuss

smoothness. Finally, in Section 2.1.7, we give a restricted completeness result for

limit preferential models.

2.1.2 Orderings on s and completeness results

For rigorous completeness proofs the reader is referred to [KLMg0] and [LM92].

In those proofs, several orderings between formulas are used, which arise more or

2.1. PREFERENTIAL STRUCTURES 47

less naturally from the logi@-, . We now slightly modify one such order (defined in

[LM92]), and examine its properties and connections to other orderings in detail.

For convenience, we use the above soundness and completeness results. We then

reconstruct the completeness proofs, emphasizing the main ideas and the central

role of the orderings. This gives us also an opportunity to incorporate results

by Ggrdenfors and Makinson [GM91], who show that, given a partial order < on

formulas, satisfying EE1-EE3 of the epistemic entrenchment axioms (see Chapter

5), there is a natural way to define a rational entailment relation I~ g, and vice

versa - we will come to this later in a short summary. Ggrdenfors and Makinson

also give a completeness proof directly from <, which we will present in outline

along with the other completeness results.

In this Section, we first motivate, define and examine a natural ordering con-

structible from a logic (2.1.2.1). We then proceed to relate our ordering to others

to be found in the literature (2.1.2.2, 2.1.2.3). In 2.1.2.3, we also take the opportu-

nity to note some marginalia to the results of [GM91]. In 2.1.2.4 we reconstruct

the completeness proofs of [KLMg0], [LM92], [GM91], emphasizing the role of

such orderings as above, focussing on intuition and the main ideas. All three

proofs proceed by showing the existence of a canonical model. Again, the results

presented in [GM91] are slightly augmented. The reader will notice that the com-

pleteness proof for t2 via the [GM91]-technique makes extensive use of rational

montony, which is needed in the [LM92]-approach only at two points. We finish

in 2.1.2.5 by relating our ordering to the rank as defined in [LM92].

So let us define and discuss the promised order.

A natural ordering

We discuss a relation almost identical to (the inverse of) ~.LM, defined at the

beginning of Section 5.3 in [LM92]. So all credit should go to [LM92]. The

systematic investigation as done in Fact 2.7 is, however, our own - though several

results summarized there can be found explicitely or implicitely in the literature.

If we read ~1 ~-, ~ as "most c~'s are/~'s", we can compare sizes: al~ fl says that

c~ and a A ~ have approximately the same size, and c~ A -~ is much smaller -

provided c~ is consistent : if c~ I~ • then any subset of c~ has identical size 0.

So we define

(We use a little logic in the last equivalence, of course, but this will hold in all

systems that interest us.)

Next, we would like to compare any two sets (formulas), not only those where

one is contained in the other. If we use the same approach, there are two extreme

possibilities:

-

c~ >/~ :~-~ truel?~ ~a, but true]~ -~

- o~ >

~' :~,

,~ v 91~ ~9-

Tile first extreme should be rejected for the tbllowing reason: "From the point

of view of God, dwarfs and giants are alike" - the measure is too coarse. So, the

most cautious approach, taking the least set containing both, i.e. c~ V ~, gives the

48 CHAPTER 2. PREFERENTIAL STRUCTURES

finest discrimination.

We make this official now:

Definition 2.6 a

>/3 :~. a V ill'" -7/3 and o~ V/31'/' '.i_

~~/3:~r162 ,--+

(~ v/3i,--, z) or (~V/31r -",~, ,~Vgl'/" -,/3)

To show the last equivalence: "--+": a > fl ~ a ;~ /3 (by Fact 2.7, 2) c) below),

a.-~fl-+ ar ar (a ~/3 A/3r or (ar A/3< a), the first

is equivalent to ct -../3, and from the second, conclude/3 < a.

To make our motivation a little more formal, we can argue a V/3 ]~ -,/3 *-,

v/3 [~ ~ A -/3 ~ ~(~ v/3) ~ ~(~) ~ ~(~ - 9) ~ ~(~) >> ~(/3) (~ a measure).

The systems P

and R

were defined in Section 1.4, Definition 1.17.

Note the following facts:

Fact 2.7 In P holds:

1)

b) ~

>/3 ---+ ,~(,~)

r 0,

2)

b)~<fl<~c~<~,

d) o~ < fl --+ o~ A 7 </3,

f) o~ < 9, ~/t~ ~ ---, ~ </3,

3)

b) c~ < 9 or fl <c~or

~fl,

c)~<fiorfi<~,

4)

b)~4a,

d)

a

<

fl ~ c~ 5_/3

v q,,

f)~_<~,fll ~~-+~<v,

g) _L < r < true for any r

h) trueSr I -+ _L

<

t~u~,

5)

a) ~<fi,~</3--+ ~vv<fl,

b)~<fl,~<fl-~ ~</3A--,,

6)

2.1. PREFERENTIAL STRUCTURES 49

Not in P, but in R holds:

7)

a) c~ ~/3 ~-r --* a N'r,

b) c~ </3 ~ 7 ---+ c~ < 7,

c) c~ ~/3 < 7 ---~ a < 7,

s)

a) c~ < /3 < 7 ---~ o: < if,

b) a </3 < 2/--+ a < "y,

c) a_< 3_<'~ --+ a <%

9)

a) 7 ,-- c~ < /3 ---+ c~ V 7 < fl,

b)-r ~ ~ </3 ~ ~ </3 A-,-~,

10) < is modular.

Proof We will almost always a.rgue semantically, building on the completeness

and correctness proofs in [KLM90] and [LM92].

:~-" : trivial.

"--4": Casel: aV/3t~,- _1_: trivial. Case2: aV/3[r Z: Letm r p(aV/3) C m(aVt3)

a>/3-+ (by 1) a) aV/31~ aA-~fl--+ (byaV/315r 2-) m(c~) 5d(~.

2) a) ~ r ~:

Suppose a < a, --+

aim

-~a +

~l~

2. Contradiction.

2) b)a</?<7~a<7:

1. 7 V 0~17 ~ _L: By 7 >/3 and 1) b), m(7 ) r {~ --+ m(7 V o~) # ~ --+ #(ff V ~) r ~.

2. 7Va[" -,a: Let m E #(TVc~). Supposem ~a, thus m ~/3Vo~--~ exists

mt -4 m, m/ ~ /3 A -,a --+ exists mU -~ rot, mZl ~ 7/3 A "7 --4 m r #(7 V oe).

Contradiction. Consider m ~ /3 V c~; mz ~ /3 A -~, mU ~ 7 A -~/3 with mzz

rn/-~ rn.

2) c) ~ < 5 ~ 5 r ~:

Suppose a V/3 IN -,a,-,/3, then a V/3 t~ ~(c~ V/3) -+ o~ V/3 [Z _1_ . Contradiction.

2) d) ~</3~ ~n~ </3:

1. (c~Aff) V/3176 5_: Suppose(c~AT) Vfll~ 2- ~m((c~AT) V/3)={~.But c~<fl

--+ m(/3) r {a. Contradiction.

C.se I: ~ c #(~ v/3)

--+ ,~ p ~ -~

~ p ~ v -~. Ca~e 2: ~ r #(~ V/3)

-~

there exists mt 4 m, mt ~/3 A -~c~ --+ mZE m((c~ A 7) V/3). Contradiction.

2) e) ~ </3 -~ ~ </3V ~:

1. c~ V/3 V 3' 17 L _1_: Suppose c~ V fi V 7 [~" 2_ ---+ m(c~ V/3 V 7) = 13 -+ m(/3) = 13.

Contradiction.

2. c~V (/3V'y)l~ --,c~: Let m E #(c~V/3V7). Suppose ra ~ c~. Then rn 6 rn(c~V/3)

exists mz -< m, m/~ -~c~ A/3 ~ m* E rn(a V/3 V 7). Contradiction.

2) f) ~ </3 A vl~ ~ +v</3:

50

CHAPTER 2. PREFERENTIAL STRUCTURES

2. -7VaIM =-7: Suppose'mEff(-7V/3),m ~"7-+ me #(7) --+ m~ c~--~ exists

m/-4 m, m/# ;8 A -~5, . Contradiction.

2) g) ~ </3 A 9I~ -7 --, ~ < ~:

1. ~ v ~ Ir 2_: .~(/3) # e --+ ~(-7) # ~

--, ~(~

v 3,) #

~.

2. c~ V 9']~ -~c~: Suppose m E #(ce V 3,), m > cx -+ exists

ml -4 m, mf >/3 A -~a,

ml E #(a V fl) --+ m! E #(fl) -+ mt ~ "y .

Contradiction.

a) a) 5 < ,8 -~ ~ < 9:

By Definition.

a) b) c~ </3 V 9<5V ~/3:

By Definition.

3) c)~_<5V9_<~:

By Definition.

4) a) 5 ~ ~:

By 2) a).

4) b) a < a:

By 2) a).

4) c) 5 <-5 --+ c~A-7 </3:

Equivalently,/3 r 5 ---+ /3 g a A -7, or /3 < a A 7 --~ /3 < a. But/3 < ce A 3, --+ (by

2) e)/3

<(~Av)v~=5.

4) d) ~ <- f3 + ~ _ 9 v -7:

Equivalently, /3 r c~ ---+ /3 V 3, r c~, or ~ V "7 < a ~ /3 < c~. But/3 V -7 < c~ --~ (by

2)

d) ~

= (/~ v 7) A/3 <

~.

4) e) c~ <- /3 A "71~ c~ ---~ q, </3:

Equivalently, "7 I~ ~ + (~ < ,8 -+ ~, _</3), or "7 1 ~" o~ ~ (/3 < -7 --+/3 < 5), which

holds by 2) g).

4) f) 5 <_/5 A /31~ -7 --+ c~ ! -7:

Equivalently, /51 ~-, "7 --~ (3' < c~ ~ /3 < a), which holds by 2) f).

4) g) _L ! q5 <-

t'rtLe

for any 05:

Suppose 05 < 2-, then 05 = q5 V _1_ i~ "~&, so 05 V _L I~ 2_. Contradiction. 05 _< true:

Suppose

true

< 05, then

true

V 05t ~ ~trtze = 2-. Contradiction.

4) h) true

Ir _t -, 2-

< true:

truels~

J_ -+ true

V J_ 19 ~ _L.

But true

V _L [ `-o

true =

-~2-.

,5) a) c~ </3 A -7 < ,~ --. c~v-7 </3:

1. ~ V/3 V -715r 2-: a V/3 V 3, [~ • --+ c~ V/3 I~ _L. Contradiction.

2. c~V/3V'),l~ -~(5V7): Suppose m E #(5 V /3 V -7), m > c~ V-7. Case 1: m ~ c~,

so exists

.ral -e, ra, ml ~ ~oe A/3.

Contradiction.

Consider rn ~ c~, m! ~ ~c, A/3 with .ml -4 'm.

Case 2: m ~ % but then consider m ~ -7, m/~ -"7 A/3 with ml -4 m.

5) b) ~ </3 A -7.</3 -, 5 </3 A-V:

i. c~V(/3A-~-7)l?~ J-: "7 </3 + /3V-71 ~

-,')'Aft ~

(by/3V-719 z' /) m(/3A-~-7)r 0.

2. ~ v (/3 n -.-7)I~ --~: S,,ppose ,, s ~(~ v (/3 a -.-7)), ,~ h ~. Then there exists

,v C ff(5V/3), m~ 4 m, ,~r ~/3n~. The,, there exists m, ~ #(7V/3),

,~" _~ ~;,

mu ~ /5

A

~7 9 Contradiction.

Consider m ~ a, ml ~/3 A -~cz, mu ~/3 A --3 with 'm;; -4 'rw -4 'ca.

6) a) c, ~ ,8 -~ c~

v/3 ~

c~:

2.1. PREFERENTIAL STRUCTURES

51

Case 1 (of a ,-, fl): a V fll ,-~ 3-: trivial.

Case2:aV/317 ~ ~a,-~fl and aV/3tT~ _L: Then aV/3t7 ~ -~a, and aV/317 L ~(aV/3)

by ~v131r

3-.

6)

b) cr

< /3 -~ /5' A -~ ,-~

/3:

By4b and4cflA-~a <fl. WeshowflA~a • flbyprovingfl= flV(flA-~a) 17 ~

-~(flA ~cr). Suppose fllN -~flVa. As cr </3, m(fl) r 0. Let rn E #(fl). So m ~ -nil

or rn ~ a. ra ~ ~fl is impossible. By a < /3 there is m/ -4 rn, ml ~ /3A-,a.

Contradiction.

7) a) a,-, # ~ 3' ---+ ~Nv:

Examination by cases of .-~

.

Case 1: aV/31~ X,/3 V'rb s --' m(aV/3) = m(/3V3') = 0 --+ -~(aV/3V3') = 0

-~ m(~ v 3,) :

0 -~

~ v3,1~ _h.

Case 2:

~v/31~

_L,/3v3'I~ ~/3,~3':/3v3'Ir

--3 -*

~(/3) # 0 --, ~(~v/3) r

~.

Contradiction.

CaseS: ~v/31r ~,~/3,/3v3,1~ • ~v/31r ~fl + m(/3) r 0 -+ ~(/3v3,) # 0.

Contradiction.

Case 4: a V/317 ~ 3-,/3 V 3,17 L _L, thus a V/31r ~a, ~/3,/3 V 71r 'fl, -'3'. Then

aV 3,1,-, 3_ can't be. We have to show aVT19g -~a,-~%

This does not work in P, as the example shows:

Consider m0 ~ a, fl, 3', m~ ~ -~a,/3, 7, m2 ~ a,-~/3, ~7, ma ~ -,a,-~/3, 7 with

m~ -~ too, ma < m2. Here, a v/3 I"~ -,c~, -~/3, fl V 3' lr -7/3, ~3,, so a ~/3 -.~ % But

aV3,19 ~

• and oeV3,]~ -,a, soaT~7.

For this example, and the others, v.ote that all finite, transitive, irreflexive cpm's

are smooth.

We now argue in R:

By

aV flj7 ~ -~c~,-7/3,

there are m0

~ a, ml ~ t3, 'm~

E

#(aV/3). By/3V3,17/o

~/3,-~7,

there are rn2 ~/3, ma ~ 3', rai E ff(fl V 7). As m0, rn~ E #(o~ V/3), m0_l-rnl (i.e.

incomparable in Ad). Likewise m~2_raa. But

mlZm2,

as both

rrh,'m~ ~/3,

and

both are minimal in m(a V/3)/m(fl V 7). By rankedness now, all m~• We show

that too, ma E #(a V 3'), and are done. Suppose rrq ~ m0,

m4

~ a V 3" Case 1:

m4 ~ a, then

ra4

E m(a V 13), contradicting minimality of too. Case 2:m4

~ 3".

By rankedness, m4 --R ma. Contradiction. Suppose m4 --d rna, m 4 ~ ct V 3'.

Case 1:m4 ~ 3'. Contradiction. Case 2:rn4 ~ a. By rankedness,

m4 -~ m0.

Contradiction.

?)b)a</3~7~ce<'r:

We first show it does not hold in P:

Consider mo D a,/3, 7, m~ ~ -,a,/3, ~7, m2 D -~a, 13, 3' with rrh ~ too. Then

aV/3[r

Z, c~V/3}~ -,a, thus a </3./3V'3,19 ~ --/3,-"'7, so/3 ~-. 7- But aV3,19~ -~a.

We now argue in R:

*.

~v-rlr

z:

~ </3--+ ~(5)r ~v/31r -L--, (byv ~#) ~v/31r ~3'--+

there exists m ~ 3, ~ c~ V 717 ~ _L.

2. aV3,[,-~ -~cr: Suppose mff #(aV7), m ~ a. By aVfl]~-, -~a there exists

m/-4 m, m/~ ~c~ A/3. If ml ~ 3'. Contradiction. So rnl ~ -~a,/3, -17. Moreover

(see in 1.) there is

rnu E

ff(TVfl),

mu

b 3'- ml -~

m,

can't be, as rat b /3,

52

CHAPTER 2. PREFERENTIAL STRUCTURES

and rn/f is minimal. So by rankedness, rn/1 -4 rn, but ca/i ~ -7, ca E #(5 V 3')

Contradiction.

Consider rn ~ a, rnl ~ -~a, fl,--'7 with ca~ -4 rn.

Then rn E #(c, V 7), cat E #(5 V/3).

7) c) a

~fl <-~ -+

a <3`:

We first show it does not hold in P:

Consider mo > 5, fl,7, ca* ~ -~c~,-~fl,7, ca2 > a, ~fl, 7 with ca1 -4 cao. Then

c~ V fl r~r -~a, -,/3,/3 v 3,1r J-,/3 v -7 I~ -,/3, but a V -7 [r -~c~.

We now argue in R:

1.5 v -7 Ir _L: 5 < 3, -~ ca(3,) r

2. 5V-71~ -~a: Case 1: a ~/3 by 5V/?l~ 2_: Then m(c~) = (~, thus aV-vi~ -~5.

Case 2: aV/3{Vt _L, c,V/3[9 t -~a,-7/3. Let ca E #(eV-7), ca ~ 5. There is

cao E #(c~ V/3), rno ~/3, so cao ~/3 V 7. Thus, there is ca~ ~ cao, ca~ ~ 7 A -,/3.

rnt --4 ca is impossible, as ca1 ~ 3`. By rankedness, ca -4 rno. Contradiction.

Consider rno ~ fl, m~ ~ 3' A -~fl with ca~ -4 cao.

s) a) 5<9<_3,-~

a<-~:

The counterexample of 7) b) shows it does not hold for P. In R: If/3 < 3', it is 2)

b), if/3 ~ 3', it is 7) b).

8) b) c, _</3 < 3, + e<-7:

The counterexample for P is in 7) c). In R: If ~ </3: 2) b), if c~ --~/3: 7) c).

S) c) c~ < ~ <-7 --, ~ <_3`:

The countere• for P:

Consider rno ~ -~a, fl,7, ca1 ~ 5,-n/3, ~7, ca2 ~ ct,/3,-"3' with

'm~ -4 rno.

Then

~v/31r -~/~, 3,v/31r -,-7, ~ v-rl~ -,3`, 5 v-71r _L. So/3 r ~, v r -7 < ~, ar, d

thus a < ~ < 3,, but a 2; -7-

In

R: The cases follow from 2) h), 7) a)-c).

9) a) -r,,~ ~ < ~ -~ c~ v-r </3:

The counterexample fbr P is in 7) c): There 5 ~-,/3 < "7, but

aV/VVV,

1r -~(c~VIV) =

-~a A-~3, so c~v/3 r -7.

In tg: a ~"7 --+ (by 6) a) c~V"7 ~ a. 5 </3, c~V"7 ~ 5 --* (by 7) c) c~V3` </3.

9) b) ~ ~ a <

,~' --,

a </3 A -'3`:

A Counterexample for P:

ca0 ~ a,/3,"7, ml ~- -~,/3, 3,, m2 ~ e,/3,"7, m3 ~ -~a,/3, -~3, with ml -4 To,

,~ -<

~. Then ~v/31r Z,

5v/31~

-~,

5v"71r

~,-,,r.

But 5V(/VA-,"7)tr -~.

In

R:

c~ </3, 5 ~'7 -+ "7 < 3 by 7) c). By 6) b) then/3 A-,3` ~-, /3, so 5 < /5 A-~'y by 7)

b).

10) < is modular:

< is not necessarily modular in P:

Consider cao ~ ~,fl,"7, 'rnl ~ 5,-,/3,-~-y, can ~ 5,-~fl, "7 with ,rq -< cao. Then

/3 < ~: 5 V/3 }~ ~/3. But neither/3 < ~ nor "7 < a: /3 V "71r -~/3, "7 V a 1r -,'~.

We now work in R:

Let/3 < c,,/3 ;~ 7, we show 3` < c~. Case 1: 3' < fl, then -7 < c~ by 2) b), Case 2:

q,r so/3~3,. So "7<c~by7) c). []

2.1. PREFERENTIAL STRUCTURES

53

Next, we compare our order with other relations in the literature: _< in [KLM90],

< and R in [LM92], <_ in [GMgl].

Comparison to orders in the articles by Kraus, Lehmann, Magidor

Definition 2.8 ([KLM90]) a <~<LM fl :~ a V fll~ a

Fact 2.9 (in P)

a V fl ].-, • --~ a <--I(LM /~, ~ <_KLM c~, /3 A -~a r a

b) conversely,

a <_KLM fl <KLM a ~ a I~ /~, /~ [" a

c)

fl]~ a ~ a <KLM fl,

but not vice versa

d) ~ _<K~M r ~ ~ = a V

Proof a) b-aV/3~aV(flA-~a). Moreover, aVfll-v

a ~aV/31..~

-~/3Va:

"-~" is trivial. "~--": Let ,~ c ~(~ V Z), ,~ ~ ~9 V ~. as ~ ~ '~4~ V Z), ~ ~ ~.

So~VZp ~ ~ ~V(/~A~)I~ ~(gA~).

_L. 2. ~ v/~1~ ~ --, ~ v (/~ A ~)p --(/~ A --~) " ~-" i~ trivial by the above.

b) ~v/~l~ ,~,r ---, ~1 ~ ~,/~t ~ ~: ~1 ~ /3: Let ~ ~ ff(,~). ~f,~ r ~(~ V ~'), the,,

there is

ml 4 m,

ml ~ a,/~ .

Contradiction. So m p ft. Likewise for/31~ ~.

c) " 4" is trivial, the following structure 3,4 shows the failure of the converse:

m ~ fl,-,a, m~ ~ a,-,/3, rn~ -< m. Then a

V/~l

~ ~a, but/3[r ~a.

d) trivial, by cumulativity. []

Definition 2.10 ([LM92])

<L. 9 :~ ~ v ~ I~ "~,

Fact 2.11 (in P)

a) ~ v/~ Ir _L

-~ (~

<c~ ~ ~ ~ > ;~), ~ V 91 ~ _L ~ ~ <L~

~,/~ <~,~ ~,

~ r

~,

~r

b) conversely,

a <LM /~ <LM Ct ----> O~

V

• I N _L,

d) ~ <LM /~ ~ ~ _<I~LM /?,

e) ~1~ ~ --' ~ <CM a A -'9-

Proof a), b), e) are triviaI.

C)~<LMfl~/~r247 ~r

d) ~v/~l~ -~ ~ ,~v/~l~ -~/~/~ ~, ~ ~v/31~ ~. []

Remark 2.12 Set

a <LMt ~ :ee ct ~LM fl,

then:

For ~,/~ Ir

~ we have

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

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