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

94

CHAPTER 2. PREFERENTIAL STRUCTURES

2.2.2 Basic definitions

Definition 2.114 Let s be a propositional language for counterfactual condi-

tionals, with primitive connectives -7, A, >>, and let W be a fixed set of "possible

worlds", such that each a E W is associated with a classical model m~ for/2 (not

all models for s need occur, and some may occur more than once).

For each a E W tet a relation -~= over W be given. Then, W :=< W, {-~: a E

W} > defines a

model

for counterfactual conditionals as follows (by simultaneous

induction for a ~vv r [[r

Ur

on the complexity of r For all a E W, r ~ E Z::

a) When r is a propositional variable, a ~v r :~ m~ ~ r (remember: m= is a

classical model),

a

~VV -~r :~-+

a ~w

r

a~wr162 :~-+a ~ Canda~w~,

a ~ r >> ~ :~

U~(a) g

[[r

b) ~r := {a E W: a ~w r

c) U,(a)

:= {~ ~ [[r ~y ~ [[r ~o ~} (thus, U~(a) is the set of C-worlds

closest to a),

d) finally, we define as usual: ),V ~- r ~ r =- W

Strictly speaking, we should index ~.~ and U by l/Y, but this will be done only

when needed for clarity.

We call a model for counterfactuals

modular

iff all of its relations ~ are modular.

Definition 2.115 We recall

that

in a model for counterfactuals a relation -% is

termed

centred

iff for all x E W, a -~= x unless x = a. The model is called centred

iff all its relations are.

Definition 2.116 We say that -~ is determined by a metric d~ on W, iff for

all

x,y E W x ~ y ~ d~(a,x) < d~(a,y).

We say that all -~ for a E W are

determined by a common metric d iff for all

a, x, y E W, x -~ y ~ d(a, x) <

d(a,y).

2.2.3 Results

Fact 2.117 Let ld; :=< W,{-%: a E W} > be any model for counterfactual

conditionals, whose carrier W is countable. Then for every a E W, -~ is both

centred and modular iff it is determined by some metric d~ on W.

Proof One direction is easy.

Conversely, suppose that -~ is centred and modular, so there is a function f~ on

W into a totally ordered set < S,<I. > with x -~ y iff f~(z) <1 .f~(y). Without

loss of generality, we may assume S = f~[W], so since W is countable, so is S.

Define now g~ : S -* (1, 2) C_ N by induction as tbllows: Let S = {si : i E co}. Set

1 Assume

g~(s;)

to be defined up to i = n. Define

g~(sn+~)

as

g~(so)

:= 1 ~.

2 - 2 .... {g.(sd:i_<n) iff sn+l 9 l>si for all { < n,

2

1 + -~i~{g~L~d:~<~}-12 iff 8~+1 <1 *s~ for all i _< n,

2.2. MODELS FOR COUNTERFACTUAL CONDITIONALS 95

erwise.

Set h~ := g~

Define now

i < n, si <1 *s~+l} +

o f=, which will be an order preserving function from W into (1,2).

0 iffx =g

<(x) + ho(y) iff x # Y, x,Y r

<(~'Y) := ha(~) g x r V, V =

By h=(x) > 0 for all x, it is straightforward to see that d= is a metric. It remains

to show x -4= y ~ d=(a, z) < d=(a,y) for all x, y E W: The cases z = y = a,

x = a # y, x # a = y are trivial by centredness. So let x, y 7{ a. Then d=(a, x) <

da(a , y) +-4 ha(x ) < ha(y ) 4--+ x ""~a Y. []

We now present the promised example which shows that there are counterfactual

conditional logics in an uncountable language, generated by modular orderings,

which cannot be represented by a metric. The idea is to define by logical means

an uncountable well-order in the counterfactual structure, which cannot be em-

bedded into the reals, as between any element and its successor there would have

to be a rational, but we have only countably many such.

Example 2.5 Let s := {p{ : i < ~}, where ,c is an uncountable ordinal. Consider

the structure A,l/ :=< Mr,-,< t >, where Mt := {rni : i < ~}, with mi

{pi} U {-'Pi : i 5s j}, and mi -~ tmj iff i < j.

We have:

(1) J/It ~ po --* J- (where _k stands for falsity),

(2) M, b po ~ -.(p~ >> J-) for i < ~,

(3) NI / ~ Po --+ (Pi V/)3. >> p~ A -,pj) for i < j < ~.

We show now that there is no structure which satisfies (1)-(3) and whose distance

relation can be expressed by a metric.

Fact 2.118 Let A-t :=< M, -~>, X :=< X, <>, the latter totally ordered, and

f: M 7-4 X with x -~ y iff f(z) < f(y). Let m E M. Then:

(i) .~ ~ ~(r >> • ~ v,(~) r ~,

(ii) x, y E Uc(m) =~ f(z) : f(y),

(iii) m ~ r V %b >> r A--%b :=> for all x E Uc(m), y E Ur x -,4 y and y r z. []

Fact 2.119 Let again 3,4 :=< M, --<>, X :=< X, <>, the latter totally ordered,

and f: M -~ X with z -~ y iff f(x) < f(y), and:

(1) M g: po -~ •

(2) M ~ po ~ --(p~ > • for i < ~,

(3) A,l~po~(p;Vpj>>p~A~ps)fori<j<n.

Then there is m E M such that

(a) m ~ Po,

(b) Vi < ,~.~,(~) r O,

(c) Vi,j < n Vx E Up~(m) Vy E Uv,(m) (x --~ y ~ i < j).

96

CHAPTER 2. PREFERENTIAL STRUCTURES

Consequently, for that r and m ~ p0, and any choice of

z~ E Up,(rn),

we have

f(x~) < f(xj)

in X iff i < j, so X contains a well-order of type ~. But, if ~ > w~,

X can't be N : Suppose to the contrary, so for i < ~,

f(z~) < f(x~+~),

so there

is some

q~ E Q, qi E

[f(xi),

f(x~+~)),

with

qi r qj

for i :~ j, and the qi form an

uncountable set of rationals, contradiction. [] (Example 2.5)

Theorem 2.120 Let ~/Y =< W, {-<~: a E W} > be a model for counterfactual

conditionals such that each -<= is determined by a metric d= on W. Then there is

a model X =< X, {-4~: x E X} > for counterfactuals and a metric d on X such

that:

(1) W and X validate exactly the same formulae of the language of counterfactual

conditionals, indeed:

For all a E W there is x~ E X such that for all r E s a ~w r iff x~ ~x r and,

for all z E X there is a~ E W such that for all r E 12 x ~x ~ iff a~ ~w 4;;

(2) each ~ is determined by the common metric d.

Remark: X will be modular and centred as all -4~ are determined by a metric.

The construction used to prove Theorem 2.120 is rather complex. For this reason,

we give an outline sketch of it in the next Section 2.2.4, and the formal details in

Section 2.2.5.

2.2.4 Outline of the construction for theorem 2.120

Given a model with set W of worlds and reIations -<~, each of which is determined

by a metric d=, we take the worlds in W and put them ~'very far from each other".

For each world a E W, we make copies of all the other worlds in W, and put those

copies in a cluster relatively close to a, ordered among themselves by the relation

-~. Each such duster is like a galaxy, with the separate galaxies far apart. This

construction is iterated co many times. Thus if b is in the cluster around a, we

make fresh copies of all the other worlds and subcluster them tightly around b,

internally ordered by the relation -% and all very dose to b compared to their

distance from anything outside the subcluster. And so on, w many times.

To give this rough idea precise content, we shall take the elements of the metric

space to be finite sequences of elements from W - for simplicity of construction,

all beginning with some fixed element * ft W (Definition 4). The propositional

properties of such a sequence will be inherited from its last element (see ~'Con-

struction", (d)). The distance between two sequences is measured by "climbing"

from the cornmon intial segment to both ends and adding up the distances encoun-

tered on the way (Definition 4). Those latter distances depend on the position in

the sequence - the later the position, the smaller thedistance - but will preserve

the relative sizes ("Construction", (b)).

More precisely, as we are interested only in the comparison of distances, we define

two metrics to be equivalent, d ,-~ dr, iff the resulting relations are the same

(see Definition 2.121). Lemma 2.122, the proof of which is a straightforward

construction from elementary calculus, says that we can choose the range of a

metric almost ad libitum: For any metric d and any constant c > 0, there is an

2.2. MODELS FOR COUNTERFACTUAL CONDITIONALS

97

3 < d1(z, zl) <_ c

for all z, z/. We

equivalent metric dl such that

d;(x,

xl) = 0 or ~c _

use this result to make distances ever smaller along the sequences - but not too

small - preserving the relative arrangement of worIds.

The main consequences of this construction are:

(1) the set

U(s)

of sequences closest to a sequence s consists of s and its contin-

uations by one further element (Lemma 2.125, (a)), and: (2)

U(s)

is arranged in

the same way as the old universe was, as seen from the last element of s (Lemma

2.125, (b)).

It is then straightforward to show that s (in the new universe) and its last ele-

ment (in the old universe) satisfy exactly the same formulae in the language of

counterfactual conditionals (Lemma 2.125, (c)).

2.2.5 Detailed

proof of theorem 2.120

Definition 2.121 Two metrics d, d! : X x X --+ ~ are called equivalent (d ~ d/)

iff

d(a, b) < d(c, e) e-~ dr(a, b) < dr(c, e)

for all a, b, c, e 9 X.

Lemma 2.122 For each c > 0 and metric d : X x X ~ R, there is d! ~,-

d such that

ran(d1) C_

{0} U [c * 4 a-,c]. (For readability, we use * for ordinary

multiplication.)

Proof: elementary, but tedious, n

Definition 2.123 (a) Let, for any finite sequence s =< So... s~ >,

l(s)

be its

length, and s~o its last element. Let W be any set, and assume without loss of

generality 0 r W (if not, take e.g. If instead of 0).

Consider

X :-- {s: s =< s0...s~ > is a finite sequence in WU {0} such that

1.) 2 _< z(s),

2.) so = 0,

3.) for 0 < i < Z(s) 9 w,

4.) s contains no direct repetitions, i.e. for 0 < i <

l(s) - 1 si r si+l -

but e.g.

si = si+2 is permitted }.

We use the following notation: For s, t 9 X, let the root of s and ~ be the maximal

common initial segment of s and ~, denoted s T t. By condition 2.) above, s T t

will contain at least 0. For s 9 X, a 9 W let < s; a > be the sequence resulting

from appending a to s. For i < I(s), let

s[i

:=< so... s~._l >.

(b) For each s 9 X let a metric de : W x W ~ N, and for s =< 0 > let a metric

ds : (W U {0})x(W U {0}) --~ N be defined. For s 9 X and 0 _< i <

l(s)

- 1 let

i) :--

Si+I).

(Note: As direct repetitions are not allowed, ~(s,i) > 0.)

(c) We define d : X x X -~ N by

0 iffs=t

d(s,t) := E{6(s,i): 1(~ T t)- 1 < i < l(s)- 1} + otherwise

E{5(t,i): l(s T t) - i <_ i < l(t) -

1)

(If s is an initial segment of t, the first sum is 0, etc).

Lemma 2.124 d as just defined in (c) is a metric on X. []

98 CHAPTER 2. PREFERENTIAL STRUCTURES

Construction of the metric space X t Recall that the original structure "~4;

was given by W and a metric d~ for each a E IV.

(a) Define X as in Definition 2.123 (a) from W.

(b) Choose by Lemma 2.122 for each s E X a metric d~. on W such that

3

1. -~ * 2~ <- d~(x,y) < ~ for all x,y E W, x r y,

2. d~ is equivalent to d~.

Moreover, for s =< 0 >, define d<o> : (W U {(~})x(W U {(~}) --* ~ by

0 iffx=y

d<o>(x,y) := 1 otherwise

(c) Define a metric d on X as in Definition 2.123 (c) from the individual metrics

d~ on W (or WU {~}), and let u ~ t :~ d(s,u) < d(s,t). For s ~ X, let

u(~) := {< ~; 9 >: ~ e w} u {~}.

(d) Finallyi construct a model for counterfactnals from X: Set X :=< X, {-~:

s E X} > and define classical validity at s as at soo: s ~x r :~--~ s~ ~w r for

classical r

Lemma 2.125 (a) U(s) contains the elements closest to s, more precisely: for

t e g(~) and ~ e X - U(~), d(~, t) < d(~,

~).

(b) For < s; a >, < s; at >E U(s), we have < s; a >-%< s; a/> ~ a ~ at.

(c) "~ and X are logically equivalent in the language/2 of counterfactuals: for all

Proof (a) Let n := l(s). Note

that for ail t E

U(s) d(s,t) < 1. Let u ~ U(s).

case 1: ~ is an initial segment of~, with l(u) > Z(~)+I: d(n,s) >_ d+(~-l,~0 +

3 3 9

Case 2: u is an initial segment of s: d(u,s) > d(s[n - 1, s) = ds[~_l(sT~_2,,s~_l )

3

Case 3: Neither s nor u is an initial segment of the other: Then d(u,s) > d(s In -

1, s).

(b) < ~;a >-~< ~;~ > :~ d(~,< s;~ >) < d(s,< s;~ >) ~ a~(soo,~) <

d~(~,a~) ~ d~=(~,a) < a~=(~,~) ~ ~ -~o=

a~.

(c) We show by a straightforward simultaneous induction on the complexity of 5:

(1) for all ~ ~ X, r ~ C, we have ~ ~z r ~ ~oo

~ r

(2) If s ~:x ~b, then Ux,c(s) = {< s; a >: a E Uw,~(soo)}.

(1) r is a propositional variable: trivial by prerequisite. The cases ~b = -~b and

= ~b A ~ are straightforward. Consider now ~ = ~b >> or, then s ~x ~b >> e :~

u~,~(~) c [[~]]z and ~ ~w ~ >> ~ :~ Uw,~(~) C_ [[~]]w- Case 1: ~ ~x

~-

Then by induction hypothesis soo ~w ~, and s ~x ~b >> cr iff s ~x cr iff

~

bw ~ if[

~ ~, r >> ~.

Case 2: ~ g:z ~: "~": Let t~ e Uw,,~(~)

-'

(by induction hypothesis) < s; tt >E Ux,e(s) ~ (by prerequisite) < s; tt >~x cr

--* (by induction hypothesis) tt ~w c~. "~": Let t E Ux,e(s) -~ (by induction

hypothesis) t =< s; tt > and tt E Uw,e(soo) ~ (by prerequisite) tt ~w cr --~ (by

induction hypothesis) t ~x or.

(2) Let t E Ux,e(s). We first show t E U(s): Note that < s;t~ >~x r by

(1), and if t (f U(s), then < s;too >~ t by (a). So t =< s;a > for some

2.3. EXTENSION BY FINITE APPROXIMATION FROM BELOW 99

a E W. As t ~x r by (i) a ~w r so a E [[r If a • U~v,r there must

be some a/ -~oo a such that a1 ~w r but then < s;al >~x r by (1), and

< s; al >-~< s; a > by (b). Conversely, let a E Uw,r then < s; a >E U(s),

< s;a >~x r by (1). Suppose now that there is t -~< s;a >, t ~x r then by

(1) and (a), t =< s;a/> for some al E W, and a! ~w r but then al ~ a by

(b), contradiction. [] (Lemma 2.125)

Clearly by construction X is a set and the -~ are modular, centred relations over

X, for all x E X. By Lemma 2.124, d is a metric on X, and by Lemma 2.125, ld;

and 2( validate exactly the same formulae of conditional logic. So Theorem 2.120

is proven. [] (Theorem 2.120)

Theorem

2.126 For any modular and centred model with at most countably

many worlds, there is an equiva!ent model whose relations -~ are all determined

by the same, common metric d via the equivalence displayed in Definition 2.116.

Proof

Immediate from Theorem 2.120 and Fact 2.117. []

2.3

Extension by finite approximation from

below

2.3.1 Introduction

In a joint paper M.Freund, D.Lehmann and D.Makinson [FLM90], see also

[Fre93], have examined the problem of extending nonmonotonic inference rela-

tions that are defined for the finite case (i.e. ibr finite sets of premises) to the

infinite case (i.e. for infinite sets of premises) by approximation from below.

We present here some results related to this problem. The first shows that the

extension does not preserve cautious monotony. This was formulated as a question

in the original version of [FLM90] as presented in a workshop at the Gesellschaft

fSr Mathematik und Datenverarbeitung, Bonn, West Germany. The version as

published cites our result, though without proof. The second result shows that

two versions of distributivity are equivalent. This is of interest to the FLM

problem, for as reported in [FLMg0], distributivity plus cautious monotony is

strong enough to carry cautious monotony through to the extension. The third

result compares two ways of applying the FLM construction to the uncountably

infinite case. The fourth result cautions against one kind of weakening of the basic

construction. Roughly, the weakened approach corresponds to convergent partial

sequences, the original one to totally converging sequences. It is not surprising

that the former can give funny logics. The fifth presents another technique for

constructing still quite well-behaved nonmonotonic logics.

All uses of set theory are standard, and can be found in any such book.

Throughout, we work in propositional languages. In addition to ~ , ~[ and

will denote the closures of a set A of formulas under a (non-classical) inference

relation.

100 CHAPTER 2. PREFERENTIAL STRUCTURES

We now formulate the basic problem and approach of [FLM90]. Suppose we

are given an infinite language and an inference relation = on finite subsets of s

is there a natural way to extend = to some^ which is defined on all subsets of

s For monotonic logics, this is trivial : ~ E A iff there is B C_ A finite such

that r E B. For nonmonotonic logics, this is clearly not sufficient, as B might

overlook some negative (blocking) information contained in A. Let now 7~I(A) be

the set of finite subsets of A. In the author's opinion, a very natural candidate

for extension is that of [FLMg0]: r E A iff there is B E ;at(A) such that for

allB/ E 7~l(A) B C_ Br--+ ~ E B-7. (Why Ainstead of Ais aminor problem

and shortly discussed in [FLM90].) In a sense, r is then a limit of "Pt(A). Our

argument against considering just one B E ~PI(A) collapses, because we look at

all the information, though only in small chunks.

As in [FLM90], we shall suppose that the finitary logic = satisfies supraclassicality

(i.e. A C_ ~) and (finitary) cumulativity (i.e. x E ~ --* A + z = A). So, our first

task in constructing examples will always be to establish these two properties.

A short remark concerning the general ~echniques used in the sequel: We

strengthen classical logic by some new inferences p [~ q. To get well-behaved

systems, we do a mixed iteration of I,-~ and classical closure. As we admit only

finitely many prerequisites in all examples, it suffices to iterate to w. (If we were

to use, say countably many prerequisites, we would do a mixed iteration to

ad 1 ,

and get analogous systems, using regularity of Wl.) So far, we are still monotonic.

Next, we select a suitable subset of the thus constructed A~, and go nonmono-

tonic.

Let us mention very briefly the results of [FLM90] related to our problem :

[FLM90] show that the following properties are preserved by

the

extension pro-

cess: 1. supraclassicality 2. supraclassicality + cut, 3. supraclassicality + cumu-

lativity + distributivity, 4. supraclassicality -I- cumulativity + distributivity +

rational monotony. However, as we shall prove presently, it is not the case that

supraclassicality + cumulativity alone are always preserved.

2.3.2 Cautious monotony does not extend

Idea The idea is, to have positive and negative information, and to glue them

strongly together, such that classical inference cannot separate them, only the

basic entailment relationIN can: pi will be positive information for s,

rl

negative

in the sense that r~ prevents all pj : j < i to be usable for inferring s.

Construction of = Let s be a (propositional) language, consisting of the

propositional variables p~ : i E w,

ri

: / E W, 8.

We define the closure under the rules pi I,-~ ri, pl I ~ s : J~ := A U {r'i :pi E A} U

{s : Pi E A} , and strengthen classical logic by closing under 1,~ and }-. We thus

define inductively

Ao := A,

A~i+ 2 := A2i+1 ,

2.3. EXTENSION BY FINITE APPROXIMATION FROM BELOW 101

A~ := U{Ai : i < w}.

So far, we have a monotonic system. We now select (nonmonotonically) a suitable

subset of A~:

Set I A := {i: r~ E A~), jA := {i: p~ e A~}.

Define I A << jA iff 3j E JAVi E IA.i < j.

Set

= / A~ iff

[A

< jA

A := ~ otherwise

[

We have to show that = is supraclassical and finitary cumulative, i.e.:

1) ACA,

2) x E A--*. A + x = A, where A +x :-- AU {x}. (routine) []

The Extension ^ (as in [FLM90]) Define now x E A iff ex. finite At C A

such that for all finite A/, At _C Ar C A, x E At holds.

To give a counterexample as desired, we show that there is x,A, B such that

xE ~i, AC BCA, x~B.

SetA:= {pi:iCw}.

We show simultaneously s E A and ri E A for all i.

Let A~, := {pi}. Assume now A~, C_ A! C -,4 finite. As pi E A! , ri and s E

AI 2 C AI~, moreover jAr ~ O. As At is finite, the set K d' := {i E w :pl or ri

occurs in some r E A/} is finite, too. Obviously, I AI, jA, C_ K

TM,

so I AI is finite.

But, as A! C --A, ri E AI~ can only be derived from p~- E AI~, so ]A, < jA,. Thus,

A/= At~ and s, ri E AL

Next, we show that there is B, A C B C A, s r

Set B := {p~ : i E w) U {r'~: i C w). Thus A C B _C/[. Assume there is B~ _C B

finite such that for all finite B/B~ C_ Be C_ ~, s E B-W. Let K B' be the finite set of

all p~ occurring in B~, and let k := max(KB~). Consider B/:= B, U {rk+~}. Then

pj ~Bt~forj>k+l, butrk+l EB%,soI s'~JB'and~=B-],andseB-]. []

2.3.3 Weak distributivity entails partial distributivity

Assume in the sequel supraclassicality (S) and cumulativity (C) for = ~,-~ resp.).

Moreover, assume weak distributivity (W), i.e. x I--~ y --* x V y ] ~ y, we show

partial distributivity, i.e. x IN y and :J }- y --+ x V xt 1~ y. As

the

latter is known

to entail full distributivity, i.e. x IN y, xIIN y -* x V xl tN y, we can close the

circle, and all are equivalent.

Fact 2.127 (a) eFeand0FO~ r

(b) I,-~ concatenates with b on the right,

(c) r r162162 r ~ eAet~

Proof (a) {r162162162162162

(b) Assume r ~ ~bF cr. By C, r {q~,~b),by S,c~E {r r a.

(c) r = {r 0, 0/}, '0 A '~bl E ~, "0, V5'I} by C + S. []

102 CHAPTER 2. PREFERENTIAL STRUCTURES

Assume nowat

,-o b, c~ b.

By a ~- aVc and Fact 2.127 (c), a I" bh(aVc), so by W aV(bA(aVc))I~ bA(aVc).

But, aV(bA(aVc)) ~ (aVb)A(aVc) ~ aVc. By Fact 2.127 (a), aVcl~ bA(aVc),

and by Pact 2.127 (b), a V cl,-- b. []

2.3.4 On different infinite extensions of 1

Suppose s is uncountable. Instead of one big step, approximating by finite sets,

one might consider a smoother procedure: inductive approximation through the

cardinals. Are both approaches the same? This Section gives a partial answer:

We prove that if both approaches coincide for all c~ < ~ , and ~ is a regular

cardinal, then they coincide for ~ too. The author does not know whether the

induction carries through singular cardinals.

Assume the axiom of choice throughout. Let I - I denote the cardinality function,

9 ordinal multiplication. ~ will be any infinite cardinal.

Definition

of i,-~ ~ (by induction on cardinals) Let 1~ be a finitary en-

tailment relation for some language s Assume I,,~ ~ to be defined for all infinite

cardinals ~ < ~;. Then define A[,-~ ~r iff

there is A0 C A, [ A0 I< ~, and for allB such that I B I= ~ < ~ and Ao C B C_ A,

B]~', r andBl,-~ ~r

(Thus, I~ ~ is the canonical extension of [FLM90].)

Lemma 2.128 AI~ o,r -~ AI~ ~r

Proof By induction on infinite cardinals.

Lemma 2.129 Assume l A 1= ~, ~ regular, and for all # < ~ and AI C

A1],-o .r ~ A/l~ ~q~. Then A],-~ ~b ~ AI~ ~qS.

Proof To simplify notation and save us another bijection, assume without loss

of generality A = n. By assumption, there is Ao G A, I Ao ]< n, and for all B,

I B ]= ,k < ~, Ao C_ B C_ ~ B IN ~r holds. By induction hypothesis, B [~-- ~r

By regularity of n, there is a < ~ such that Ao C_ a. If n is a limit cardinal, set

I( := {hi < n: n/is a cardinal}, if ~: = n/+, set K := {hi./3: fl < n}. In both

cases, K C_ n is closed unbounded.

Moreover, there is a bijection g : ~ ~ ~<~ ( where X <~ := {y C~ X: I Y I< ~}

), such that for all nl E K, gin1 : nt ~ ~I <~ is a bijection. (To see this, proceed

inductively: If nr is a limit point of K, let g In/:= U{g [nll: nH< nl}. If nl is the

successor of ~;1! in Is use ] ~r -- ~t! I----[ ~r I-)

Let now A := K-o~, so A __ ~ is closed unbounded, and for X E A, t1-,~ ~r Thus,

for each X C A, there is aa C ~ finite and for all ax C b C ~ finite, b I r r Define

h(X) := such an aa (using AC). Thus, for X ~ A, f(X) := 9-~(h(a)) C ,X, so f is

regressiv, and defined on a stationary subset of ~. Using Fodor's Theorem (see

e.g. [Kun80]) by regularity of ~, we see that there is X C_ A, X C_ ~ stationary,

2.3. EXTENSION BY FINITE APPROXIMATION FROM BELOW

103

such that

fiX

is constant. Let f(A) = a for A E X. So, as h = g~ there is

X C_ ~ unbounded, such that h IX is constant, say = a. But now, we are finished:

LetaCbC~finite. As X is unbounded, there is A E X, bCA, and b].-. r

definition of aa = a. []

2.3.5 Extension by unbounded subsets

One might consider the definition of [FLM90] as too cautious: We may think of

arguments and say:

"I

will be prepared to accept r iff I can win any argument

against r formally, r E A iff there is some U, C PI(A) unbounded such that for

all X E Ur r E X, i.e. for each B E Pl(~) there is C E PI(A) such that B C_ C

and r E ~. The problem here is that such unbounded U, U/might have empty or

bounded intersection, giving some very strange results. Comparing some A and

/? needs even stronger properties for reasonable results.

The following example shows that care has to be taken so the logic will not behave

wildly: We show that without such precaution it is possible that r E ,4, r E/I,

but r A r r A. This is not really surprising, but the reader might want to see a

proof, to get familiar with techniques.

Let E := {p,: i E w} U {q,-: i E w} U {r,s}.

Define/~ := B U {r: pl E B} U {s: qi E B} for B C s and

Bo :=B,

B2i+l

:=

B2i z,

J~2i+2

::

J~2i+l,

B,., := U{B~ : i < ~}.

Note that all operations so far are monotonic.

Let I B := {i:p~ E B~}, jB := {i: q~ E B~}. For I, I1_C a; define I < I/iff

Jj E I/Vi E I.i < j,

likewise I < I/iff 3j E

IIVi E I.i < j.

Note, that ifBis finite, so is I s and d B, and either I B < jB or

jB <_ ]B, or

[B = fiB = ~.

Thus, for finite B, the following definition is exhaustive:

_

[ B+s if/B < jB

:= / B+r ifJB_<I B

if

I B = jB =

We have to show for finite B:

1) B C

B (this is trivial),

2) zE B ~ B+z= B

[]

If, however, U M U/(U, U/as in above construction) were unbounded in 79/(-A),

we would have concluded r A s E B unboundedly often (using supraclassical-

ity). So, any weakening of the original extension definition should have the finite

intersection property, i.e. the systems considered should be closed under finite

intersections. Yet, to achieve more results, e.g. to show (under additional as-

sumptions) something like A C B C_ ~ --, ~ = ~, one needs a global system for

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

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