Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques
Подождите немного. Документ загружается.
4 CHAPTER I. INTRODUCTION
rough answer. In an emergency situation, a doctor will try to save the patient's
life, even though he may be unable to make a precise diagnosis.
In the end, researchers and techniciens in artificial intelligence want to build
efficient reasoning systems. These systems will probably be quite different from
logics. What is then the use of doing logic in AI? It seems difficult to imagine to
be able to build an efficient and correct reasoning system without (a) knowing
what it is to reason about, i.e. without having a semantics, (b) having an ideal of
correct reasoning as guideline for its construction, and against which to measure
its performance.
Thus, we see our work as part of the necessary fundamental research upon which
applications can be built.
1.2.2 Basic semantical notions
It is the author's conviction that there are some, perhaps not too many, basic
notions behind the semantics of many non-classical logics, and that the notions
of distance and size are among them.
Let me argue in favour of my position.
The use of distance is perhaps most obvious in the Stalnaker/Lewis semantics
for counterfactual conditionals. An example of a counterfactual conditional is:
"If it were to rain, I would take an umbrella." The Stalnaker/Lewis semantics
consists of a set of possible worlds (as for a Kripke semantics for modal logic),
with a distance relation. Let r >> ~b stand for the counterfactual conditional "if
r were true, then ~b would hold", and let ra be one of the possible worlds. 4) >>
is defined to hold in rn iff in those possible worlds, which are closest to m among
those where (b holds, tb holds, too. The intuition is the following: If my world
changes minimally so that it rains, then I will take an umbrella. There may be
worlds very distant from mine, where there is e.g. always a very strong wind, and
where it makes no sense to take an umbrella. But these distant worlds will not
count.
The basic concept of this semantics is thus one of '?dative closeness", sometimes
called "relative similarity" or conversely ~'relative distance". It is given formal
representation in various equivalent ways, notably by a family of indexed two-
placed relations <~ between worlds, with z -.1~ y read intuitively as '~x is closer
to a than is y."
Nonmonotonic logics speaks and reasons about what normally holds, deontic logic
about what "morMly" holds, i.e. which states of affairs are morally acceptable.
A preferential model Ad for nonmonotonic logics or deontic logic consists of a set
of possible worlds, with a preference relation -~ defined on this set. In the case
of nonmonotonlc logics, this preference relation chooses the more normal worlds,
in the case of deontic logic, the more moral worlds. The semantic consequence
relation r ~ !b with respect to such a structure Ad is then defined to hold iff
in the most normal (moral) worlds, where ~b holds, 'g) holds, too.
With a little bit of abstraction, we can consider this preference relation as an
abstract distance relation too: m -~ ml if[ m is closer to ~n ideal point of maximal
1.2. OUR PHILOSOPHICAL POSITION 5
normality or morality - the paradise of dullness (or saintety).
The notion of size can be seen behind another aspect of nonmonotonic reasoning,
reasoning about the "usual" case. We will then say 4 "usually" implies ~b, iff in
"most" cases, where 4 holds, '~ holds, too. A semantical structure 2t4 will then
be a set of possible worlds, with an (abstract) measure of size defined on it. Then
q~ ~ ~b will be defined to hold, iff the set of worlds, where ~flA~p holds, is large in
the set of worlds where ~ holds. (A semantic of this kind is developped in detail
in Chapter 3.)
In legal reasoning, the concept of size has importance, too. A postulate can only
be considered a law, if in most cases, people obey to it. (This was pointed out to
the author by Otto Pfersmann, Lyon, in personal communication.)
The author sees the work of discovering such basic notions of (intuitive and for-
mal) semantics as one of the aims in research on nonclassical logics. This work
has a philosophical aspect, but also a mathematical side, in making the connec-
tions precise, and examining various abstractions of such notions (e.g. distance
expressed by a binary relation - of different strengths -, by metrics etc.). We thus
strive to reduce one notion, like nonmonotonic reasoning, to another notion, like
distance. Sometimes, such a reductionist approach is criticised, in that it does
not really explain anything, but only transforms one problem into another. Let
us then defend the project.
A justification of the reductionist approach
A reductionist approach does not claim to give absolute explanations, it rather
tries to establish connections. Moreover, it can point out similarities, by reduc-
ing different concepts to the same basic ideas. As pointed out above, the Stal-
naker/Lewis semantics for counterfactual conditionals, preferential semantics for
nonmonotonic and deontic logic reduce to the notion of distance. Consequently,
results from one field can be carried over to other cases. (We have done this in
[Sch96-4] by using the techniques for constructing preferential models to give a
completeness result for counterfactuaI conditionals.)
A reduction of one notion to another can also help clarify intuitive adequacy.
Take for example a logic which is sound and complete for a certain semantics.
As we saw above, it seems to be much easier to judge the intuitive value of a
semantics (i.e. its correspondence to an intuitive abstraction of the situation
considered) than to judge directly the value of a logic.
Finally, in defense of this approach, it may be said that also natural sciences do
not pretend to explain things in an absolute way, but they describe laws governing
the relations between notions, e.g. between mass, speed, and forces. So we are
in a good and fruitful tradition.
Of course, this defense of the reductionist approach is no argument against ex-
plaining some notion by still other means.
6 CHAPTER 1. INTRODUCTION
1.2.3 Abstract semantics
Above, we have described a three-layer picture:
-
First, the natural objects we want to speak and reason about,
-
second, the abstraction thereof into a formal semantics,
- third, a language and logic which correspond to the second by soundness and
completeness.
Sometimes, the picture is more complicated, and we see an intermediary structure,
between the second and the third, a semantics which often evolves in hindsight,
more as an abstraction of the logic and of reasoning than of the objects one
does reasoning about. In the case of nonmonotonic reasoning, we find this in
the semantics via (coherent) systems of (weak) filters (see Chapter 3, and also
elaborated to a number of completeness results in [BB94]), and in the abstract
semantics ~ria partial orders by [FH95]. The latter idea is already inherent in the
completeness proofs in [KLM90] and [LM92], see also Section 2.1.2.
1.2.4 Restricted monotony and irrelevance
Reasoning and logic permit not only to conclude about unobservables - e.g. make
a diagnosis, predictions etc. - but also to transfer information from one situation
to another. For instance, in the case of classical monotonic logic, if we know that
T F r we know that for T/with T C TI, TI ~- 4;, too. We transfer the
conclusion (~ from T to Tf. Obviously, this type of transfer is impossible in the
case of nonmonotonic logics. Thus,
in
other words, with the loss of monotonicity,
we loose a lot of stability of a logic. But a logic, where we cannot transfer
conclusions from one situation to another, is not very comfortable, one always
has to start reasoning fl'om scratch. Moreover, common sense reasoning uses a
lot of such transfer, e.g. by analogical reasoning, generalization, etc., and the aim
of nonmonotonic logics is to stay dose to common sense reasoning. Finally, the
success of common sense reasoning, or reasoning at all, seems to indicate that
the world and reasoning are made in a way that a lot of transfer of reasoning is
possible. Thus, one has looked for other forms of stability than brute monotony,
and re-introduced restricted forms of monotony.
One such form is "cautious monotony". Cautious monotony of a logic IN says,
that if T IN 4; and TIN ~, then T U {4;} t N ~. Cautious monotony together with
its converse, i.e. TIN 4; implies (TI N r iff TU {4;}],'~ ~b) can best be explained
as "normal use of lemmas". If we have already deduced the "lemrna" r then we
neither win nor loose in terms of consequences by adding 4; to our theory (or set
of axioms).
More gen&ally, one can see this as the question of irrelevant information. Given
T and a possible conclusion 4;, what information can be added to or subtracted
from T without changing the fact that T 1,-~ r (or r I'~ 4;)? Less abstractly,
given a (large) database T, and a query ~b, is there a method to single out a
(considerably smaller) subset TI C_ T, such that the information contained in T/
suffices to answer the query 4;? Can we perhaps give a generic procedure, which
for a query of type z singles out an appropriate Tx C T?
1.2. OUR PHILOSOPHICAL POSITION 7
I think it is safe
to
say that research on this question, posed in that generality,
is still at its beginning. The present book treats it only very superficially, and
more as a description than by giving even a preliminary answer (see below in the
introduction, Section 1.3.11.).
The so-called paraconsistent logics try to give an answer to a related problem.
Suppose T is classically inconsistent, so classical logic will deduce anything from
it. Is there a method to single out in a reasonable way a subtheory T! C T, which
answers a query q~, and which is not disturbed by "irrelevant" contradictions?
So, here, we are looking for a "core" of the theory (perhaps relative to the query
4), which is rich enough to give an answer, stable under addition of irrelevant
contradictions.
Considerations of stability of a logic in other forms than in the various kinds of
restricted monotony (as cautious monotony above) have led us (see Chapter 4) to
examine "continuous" logics, which, with a smM1 change of the input (the theory,
or the axiom system) change the output (the set of consequences) only a little,
too. I.e., if T and T! are close to each other, the set of their consequences
C(T)
and C(TI) will be close too. For this to make sense, we have to define a topology
on the set of theories, this is done by defining (almost) a metric on the models,
which carries over to sets of models, and thus to theories.
A more detailed discussion is deferred until Section 1.3.11, when we dispose of
some more material on our treatment of defaults.
1.2.5 Logic and structural information
The reader will find a discussion of reasoning in diagrams in Chapter 6.
Inheritance diagrams allow to inherit properties from supersets to subsets. To
the superficial observer, they seem to be very simple, but present a lot of subtle
problems under cIoser look. In particular, there exists up to now no convincing
semantics for these diagrams (to our knowledge).
These difficulties hide perhaps a deeper difference between logic and structural
information.
Logical properties, e.g. some kind of monotony, are global, they apply every-
where in the language. Structural information, like diagrams, seems to be more
local, describing local construction, influences, or barriers between such influ-
ences. Structural information might be an appropriate way to describe how to
put small theories together, isolate contradictions, inherit or bar inheritance of
properties. So, structural information might be a new primitive, like distance or
size.
One might, of course, import such diagrams into the language of logic by a new
modal operator, whose laws correspond to the laws governing the diagrams. But
this would just be a, possibly unintuitive, re-writing of the structural information.
8 CHAPTER 1. INTRODUCTION
1.2.6 Summary and program
We think that the search for basic semantic concepts is a necessary and fasci-
nating enterprise of philosophical and, by its consequences, mathematical value.
Demonstrations of adequacy between logics and semantics are needed to make
logics philosophically sound and mathematically respectable. The development of
reasoning systems out of logics is perhaps the central open problem. The method
of combining structural reasoning as in inheritance diagrams with logics might
be a promising approach to some problems.
A theory of argumentation - similar to, but more general than the theory of defen-
sible inheritance - might hold some clues~ but will also be plagued by the problems
of inheritance systems, e.g. the problems connected to finding a semantics.
1.3 Introduction to nonmonotonic logics and
its problems
We give in this Section a detailed introduction to some of the problems of non-
monotonic logics, as well as to the subsequent Chapters of the book, without
going far into technical details.
1.3.1 History and an example
Nonmonotonic reasoning (NMR) has its historical origin in attempts to formalise
common sense reasonlng's "jumping to conclusions". Thus, it is often seen as a
strengthening of classical reasoning: Conclusions are drawn which need not hold
;'absolutely", but are quite safe in everyday life.
From a more abstract point of view, it is convenient to consider NMR as drawing
conclusions from (partially) ordered information under (partially) ordered rules.
In this sense, in the above context, classical logic is the strongest inibrmation,
and jumping to conclusions uses weaker rules and assumptions.
"Ordered", "weak", "strong" refer to the treatment of contradictions: If we do
not meet with any contradictions we may use all information indiscriminately. If,
however, some system of ordered axioms and rules is found inconsistent (under
some logic), we use the order to eliminate the weaker information until consistency
is obtained. Thus, if the results of common sense reasoning contradict classical
logic, we will give up some results (and maybe axioms and methods) of common
sense reasoning, but preserve classical logic.
This, as said already above, explains the nonmonotonicity of NMR. Let W be
some set of weak information, and r be deducible from W. If we add some strong
information er to W, it may contradict 4, and, by its strength, prevent the deduc-
tion of r from W U {or}.
Ordered information is all-pervasive in our everyday - and also scientific - reason-
ing: We consider one person, e.g. a witness, more reliable than another, or, in
statistical reasoning, consider the most specific reference class as giving the most
reliable information for the case at hand.
1.3. INTRODUCTION TO NONMONOTONIC LOGICS 9
We may finally encode nonmonotonic logic, the formal counterpart of nonmono-
tonic reasoning - like all of mathematics -, into classical logic + set theory, so:
Why another logic? Such encoding will usually not be natural, not be the right
level of abstraction: We would have to carry with us too much administrative
overhead. Moreover, the devastating effect of contradictions in classical logic -
whose intended semantics is flat: everything is equally important - will cause
drastic revision processes, if such contradictions arise - i.e. if we forgot some
aspect after all.
Before we continue, let me give an example of a nonmonotonic logic. Consider
the propositional language of two variables, p, q, and the structure 3,4 given by
two classical models, 'm ~ p, q, m! ~ ~p, ~q and the relation m! -4 m. M defines
a "preferential" logic ~z4 by 4 ~M ~b iff in all -~ -minimal models (in JM) of
4, ~b holds. Thus,
true ~,~ -~q,
as both m, ml are models of true in 34, but
only rn! is a minimal such. On the other hand, p ~ -~q, but p ~M q, as the
only model of p in did is m. Thus, strengthening the antecedent does not preserve
the consequences, and considering A :=
{true}, B
:=
{true,p}
shows that ~
is nonmonotonic. (The fact that M does not contain all classical models of the
language is not crucial, the property essential for nonmonotonicity is the relation
-< .) The reader will find a thorough discussion of preferential reasoning, and
many more examples in Chapter 2.
1.3.2 Some basic differences
There is one basic split in nonmonotonic reasoning into a more radical and a
more cautious branch: Returning to the above example on reliability, we may
either eliminate the unreliable information - revise our theory - or keep the in-
formation in mind (or database), but don't make the overridden conclusions - as
the more "traditional" nonmonotonic logics do. The latter may have devastating
consequences when the logic is rich enough to permit EFQ (ex falso quodlibet:
anything may be concluded from a contradiction): Assume we have concluded
4 with reliability r, -~4 with reliability rr and ~b totally unrelated with 4, with
reliability s, where r > r! > s. Then we may conclude 4 A -~4, and by EFQ ~'~b
with reliability
rain(r, rl) > s,
destroying the maybe quite acceptable conclusion
~b. If, on the other hand, we had eliminated -'4 completely from our database by
theory revision, the problem would not have arisen.
We turn to the discussion of two other fundamental properties in which non-
monotonic reasoning systems may differ. The first concerns the treatment - if
any - of "irrelevant" information, the second the way conclusions are permitted
to be reached: the liberal way of logics vs. the "totalitarian" way of inference
networks. The first will be discussed in Section 1.3.11, the second, after a short
introduction here, in detail in Section 1.3.10.
Logic has many ways to reach its conclusions. To give a trivial example, if we
can conclude ~b from 4, one can - in most logics - also conclude 4 A 4 from 4,
and then ~b from 4 A 4 - and so on. In contrast, defeasible inheritance systems,
the networks of inference discussed by J.Pearl [Pea88], and Truth Maintenance
10
CHAPTER!. INTRODUCTION
Systems in the sense of J.Doyle [Doy?9] also limit the possible ways conclusions
may be reached. They are thus especially suited to mechanical processing.
The reader will notice that these systems answer the question of irrelevancy to
a large extent, too: Information, which is not "connected" to the problem in
question is trivially irrelevant.
1.3.3 A (simplified) introduction to Reiter's theory of
defaults
Reiter's theory of defaults, see [R.eiS0] was among the first formal systems of
nonmonotonic logics. It has the advantage to show its motivation very clearly.
We therefore give an intuitive definition of this theory, to provide the reader
with some examples. In Reiter's notation, a default has the form ~-~, where
4, ! 5,a are formulas of classical (propositional or first order) logic, q~ is called
the prerequisite, 15 the justification, and ~r the consequence of the default. The
intuitive meaning is, that for objects or situations which have property ~b, if we
can safely (i.e. without contradiction) assume 15, then we also assume or. Shortly
(if 15 = ~r), objects with property ~b normally have property 15, birds normally
fly, bi~:Jzy (In most cases, c~ is the same formula as 9, such defaults are called
.fly "
normal defaults.) The formal meaning is: If we can demonstrate 4, and ~ is
classically consistent, then we believe in a. More precisely, we work on a classical
background theory T, and add ~ to T as believed, if T [- ~, and T U {15} is
consistent. If we have several defaults, we apply this procedure successively to all
defaults. Sometimes, we have to branch into several extensions, e.g. for the set
of defaults { t .... ~ t ..... ~
, ~e j, as we cannot apply both defaults one after the other.
A default of the form ~r is also written :2 and called a default without prereq-
uisites. If ~fi, 15, cr are open first-order formulas, e.g. ~(*):~(~)
~----g(7~, one tries to apply the
default to as many instances as possible. If we have, e.g., a universe of two ele-
ments, one called
Tweety,
the other called a, the default
fly(x),
and the classical
information
-,fIy(Tweety),
we will conclude fIy(~).
A detailed definition of an extension of a default theory is to be found in Section
1.4, Definition 1.19.
1.3.4 Static and dynamic aspects of defaults
Reading a default ~ as ~'normally, ~," reveals a static aspect of the default,
like %n most cases, q~." Defaults in the Reiter formalism have, however, also a
dynamic, %nference-greedy" aspect, they exhibit a certain '~inference pressure",
and are applied as much as possible and not only '~very often". This is perhaps
clear in the case of open defaults. ~ will be applied to as
especially
many
elements of the domain as consistently possible.
One interpretation of the static and the dynamic aspect is that the former reflects
a state of the world, the latter a strategy of the reasoner.
We now take a closer look at these aspects.
1.3. fNTRODUCTION TO NONMONOTONIC LOGICS 1 t
Roughly, the static aspect of a default "normally, birds fly", expresses something
like "most" birds fly, the "interesting" birds do, etc. Reiter's formalism lacks this
static, minimal requirement: If you say that normally birds fly, you have to be
able to show that at least one bird can fly, and even more, the members of a
substantial subset of the set of birds must be able to fly.
To put it differently, reading a default "normally r as gxr and then
taking elements away from {z : r to make the theory consistent seems to
do injustice to the universal quantifier: We write down something we do not
really mean. Starting on the other hand with the empty set trying to put as
many elements into {z: r to translate "normally r seems to violate an
essential, static aspect of "normally": We should not say "normally" when we
are not even shure that there is some x with r Somewhere in between Vzr
and ~zr has to be the (static) meaning of "normally".
If we accept that these are minimal conditions justifying a sentence like "nor-
mally r then we conclude that 'r r and "normally -,4)(x)" are
impossible - on the premise that two such substantial subsets (of one base set)
have non-empty intersection. In our opinion, this minimal condition - r has
to hold for a substantial subset to justify the sentence "normally r - leads
naturally to a formalization of "normally" via "important" or "large" subsets:
"normally r holds if[ there is an important subset A (of the universe, or of
the set of birds etc.) such that for all ~' E A, r holds.
Syntactically, we can then interpret open normal defaults as generalized quanti-
tiers, in strength between the classical existential and universal quantifier. More
precisely, we introduce a new quantifier "almost all" into first-order logic (FOL),
to be interpreted semantically by such "large" subsets. Large subsets are char-
acterized by a weak filter, added to a standard first-order logic model, forming
a more complex structure. A sound and complete axiomatization, extending
classical FOL, for our semantics will be given.
This approach has the advantage to give not only a notion of consistency of
default theories- e.g. { ::~j.), ~} is ruled out as inconsistent- but also to allow
the use of negated and nes[ecl~d~e~aults, and to give such formulas a clear meaning.
Yet, it treats only the minimal, static aspect of defaults, and lacks the dynamic
aspect: Apply the default as much as you can!
Reiter's original approach to open normal defaults via Skolem constants is sensible
~o syntactic reformulations. In [BS93], we have suggested a limit preferential
approach which, by
its
semantical basis, avoids the above problem. It seems
to capture well this "dynamic" or "inference-greedy" aspect of defaults, to make
true as many instances of the defaults as possible. We will return to this dynamic
aspect in Section 1.3.7.
1.3.5 Introduction to preferential structures
Preferential structures in their various forms provide an importailt and relatively
well-studied group of semantics for nonmonotonic logics and other forms of rea-
soning (see [Makg3]). We give here an extended introduction to these structures.
12
CHAPTER 1. !NTROD UCTtON
The intuitive background
The basic idea is to interpret a primitive notion of "importance" or "value",
introduced into a given language and logic, by a function which chooses a subset
of "important" models of a theory or formula of that language.
In other words, we work on a set of "possible worlds", i.e. models of the underlying
base logic, but do not accord the same importance or value to all such models.
Given a theory T of the base language and logic, we determine the semantical
consequences of T in a structure jbt by considering only the set of "important"
models of T : T ~ q~ iff q~ holds in all important models of T in our structure.
More formally, such a structure 2r wilI then consist of a set M of models or
possible worlds for the base logic, and a choice function f on
"P(M) -
the power
set of
M. If M(T)
is the set of all base models of a theory T in 3.4, f singles
out the set
f(M(T)) C_ M(T)
of important models of T in the structure 3,t. We
thus define T V~ ~ iff 4 holds in all m E
I(M(T)).
(We simplify here for the
moment. Later, we shall consider a more general case, where logically equivalent
models may occur several times.)
A refinement of the idea is to work not with one subset of "maximally impor-
tant" models, but with many subsets of important models, perhaps of increasing
importance. We then have several choice functions J~. in the structure Ad, and we
define T ~m r ig there is some .f~ such that r holds in att m E
fi(M(T)).
This
structure captures the intuition that we may not dispose of ideal models, but can
approximate them in the limit: Suppose for simplicity f;(M(T)) __
fi+~(M(T))
for all i E w, with
f;(M(T))
the set of T-models of importance i. Then, even
if each
fi(M(T))
is non-empty, ff~{f~(M(T)) : i E a2} may be empty. In that
case, there are no maximally important models, but we have non-empty sets of
ever-better ones, which approximate the ideal. I shall call this approach the limit
case, and the previous variant, for historical reasons, the minimM case.
Already this very abstract description makes it plausible that representation theo-
rents for the limit case are harder to obtain than for the minimal case. In the limit
case, we have to handle a possibly infinite set of choice functions, and there need
not be a global f such that for all r T ~ ~b iff ~b holds in all m E
f(M(T)).
In
other words, we do not always have a set of "joint witnesses" for all consequences
of a theory.
Logical consequences
It is evident that such consequence relations will be well-behaved with respect to
the base logic - provided the latter is sound and complete for the models we have
chosen as possible worlds. So, if T and Tr are equivalent with respect to the base
logic, they will have the same set of semantic consequences, and, if T ~ cb, and
implies ~5 in the base logic, then also T ~ '~. Moreover, if 6 is a consequence
of T in the base logic, then T ~4 r as the choice functions will choose a subset
of
M(T).
These facts hold in both the limit and the minimal version.
1.3. INTRODUCTION TO NONMONOTONIC LOGICS
!3
Preferential structures
Preferential structures are a special case of the above, the choice is made
locall 9
by a binary relation -< on the set M of base models, where ru -< rut iff m is
considered to be more important than ruz. (m -< .rat instead of rut --< ru for
historical reasons.) They are thus very similar to Kripke structures, but the
relation -4 will be used differently.
In the minimal case, we define f by means of --4 by
f(A)
:= {a E A : -~3b E
A.b -<
a}.
In the limit case, the natural definition is to consider initial segments of A:
8A _C A is called an initial segment of A iff
(61) there is some b E 6A below each a E A: Va E
A~b E 6A(b = a V b -4 a)
(82) 6A is downward closed: Va G_
AVb E 8A(a
-< b ~ a E 6A).
Each
fi
corresponds then to the choice of one such 8A for each A C M.
We thus have in the minimal case T ~z4 r iff r holds in all re E #(T) - the
set of -< -minimal inodels of T in J~/. If, for instance,
M(T)
consists of infinite
descending chains, then #(T) = ~, and T ~4 r for any r J- (=
false)
included.
On the other hand, any m E #(T) will be a "witness" of
all
~M-consequences of
T, in the sense that all q5 with T ~a r will hold in any such .m.
In the limit case, we have T ~aa r iff there is some
8T,r C_ M(T)
which satisfies
(8t) and (82) with respect to
M(T)
and such that r holds in all ru E @,r Thus,
in the limit case, #(T) may be empty, but if
M(T) 5r 0,
we will still not have
T ~M A_, as all @,r are then non-empty. It is easily seen, that if T ~r r
and T ~za
r
and -< is transitive, then also T ~z4 r A
r
if 6T,r and @,r are
suitable, then @,r M
@,#
will be a suitable 8T,r162 Moreover, if T ~ r and
M(T
U {r C M(T 0 _C
M(T), then also T~ ~:~ r
An immediate consequence of the locality of the definition of f is a kind of upward
absoluteness in the minimal case. An element, which is not minimal in A, can't
be minimal in any B with A C B:
(1)
A C B --+ f(B) M A C_C_ f(A).
In contrast, in the general case of arbitrary
f,
the choice may depend on the
"context", there need not be any interdependence between
f(A)
and f(B), even
ifAC_B.
It turns out that (1) is
the
crucial property for minimal preferential structures.
Any choice function which obeys (1) and the trivial property
(0) I(A) C A
can be represented by a preferential structure, i.e. by such a binary relation of
preference (see Proposition 2.83). This is a very general "algebraic" character-
ization, the underlying set M need not consist of models, it may be just any
arbitrary set.
A similar result tbr limit preferential structures seems to be missing up to now,
see [Bou90a],
[Boug0b], [Bou92]
and Section 2.1.7 for restricted cases. Boutilier's
results are restricted in the sense that they treat finitely axiomatisable theories
only, but such theories correspond exactly to clopen (= closed and open) sets
in the standard topology (see Definition 1.13 in Section 1.4). Yet clopen sets