Dov M Gabbay
email: dov.gabbay@kcl.ac.uk@www.dcs.kcl.ac.uk

Karl Schlechta
email: karl.schlechta@web.de

A semantics for obligations -Local and global properties of obligations *

We analyze a number of properties obligations have or should have. We will not present a definite answer what an obligation "is", but rather point out the numerous possibilities to consider, as well as some of their interrelations.

1 Introductory remarks

We see some relation of "better" as central for obligations. Obligations determine what is "better" and what is "worse", conversely, given such a relation of "better", we can define obligations. The problems lie, in our opinion, in the fact that an adequate treatment of such a relation is somewhat complicated, and leads to many ramifications. On the other hand, obligations have sufficiently many things in common with facts so we can in a useful way say that an obligation is satisfied in a situation, and one can also define a notion of derivation for obligations.

Our approach is almost exclusively semantical.

Context

The problem with formalisation using logic is that the natural movements in the application area being formalised do not exactly correspond to natural movements in the logic being used as a tool of formalisation. Put differently, we may be able to express statement A of the application area by a formula φ of the logic, but the subtleties of the way A is manipulated in the application area cannot be matched in the formal logic used. This gives rise to paradoxes. To resolve the paradoxes one needs to improve the logic. So the progress in the formalisation program depends on the state of development of logic itself. Recent serious advances in logical tools by the authors of this paper enable us to offer some better formalisations possibilities for the notion of obligation. This is what we offer in this paper. Historically, articles on Deontic Logic include collections of problems, see e.g. [START_REF] Ch | The paradoxes of deontic logic revisited: a computer science perspective[END_REF], semantical approaches, see e.g. [START_REF] Hansson | An analysis of some deontic logics[END_REF], and others, like [START_REF] Carmo | Deontic logic and contrary-to-duties[END_REF]. Our basic idea is to see obligations as tightly connected to some relation of "better". An immediate consequence is that negation, which inverses such a relation, behaves differently in the case of obligations and of classical logic. ( ′′ And ′′ and "or" seem to show analogue behaviour in both logics.) The relation of "better" has to be treated with some caution, however, and we introduce and investigate local and global properties about "better" of obligations. Most of these properties coincide in sufficiently nice situations, in others, they are different. We do not come to a final conclusion which properties obligations should or should not have, perhaps this will be answered in future, perhaps there is no universal answer. We provide a list of ideas which seem reasonable to us. Throughout, we work in a finite (propositional) setting.

Central idea

We see a tight connection between obligations and a relation of "morally" better between situations. Obligations are there to guide us for "better" actions, and, conversely, given some relation of "better", we can define obligations. The problems lie in the fact that a simple approach via quality is not satisfactory. We examine a number of somewhat more subtle ideas, some of them also using a notion of distance.

A common property of facts and obligations

We are fully aware that an obligation has a conceptually different status than a fact. The latter is true or false, an obligation has been set by some instance as a standard for behaviour, or whatever. Still, we will say that an obligation holds in a situation, or that a situation satisfies an obligation. If the letter is in the mail box, the obligation to post it is satisfied, if it is in the trash bin, the obligation is not satisfied. In some set of worlds, the obligation is satisfied, in the complement of this set, it is not satisfied. Thus, obligations behave in this respect like facts, and we put for this aspect all distinctions between facts and obligations aside. Thus, we will treat obligations most of the time as subsets of the set of all models, but also sometimes as formulas. As we work mostly in a finite propositional setting, both are interchangeable. We are not concerned here with actions to fulfill obligations, developments or so, just simply situations which satisfy or not obligations. This is perhaps also the right place to point out that one has to distinguish between facts that hold in "good" situations (they will be closed under arbitrary right weakening), and obligations which describe what should be, they will not be closed under arbitrary right weakening. This article is only about the latter.

Derivations of obligations

Again, we are aware that "deriving" obligations is different from "deriving" facts. Derivation of facts is supposed to conclude from truth to truth, deriving obligations will be about concluding what can also be considered an obligation, given some set of "basic" obligations. The parallel is sufficiently strong to justify the double use of the word "derive". Very roughly, we will say that conjunctions (or intersections) and disjunctions (unions) of obligations lead in a reasonable way to derived obligations, but negations do not. We take the Ross paradox (see below) very seriously, it was, as a matter of fact, our starting point to avoid it in a reasonable notion of derivation. We mention two simple postulates derived obligations should probably satisfy.

(1) Every original obligation should also be a derived obligation, corresponding to α, β ∼ | α.

(2) A derived obligation should not be trivial, i.e. neither empty nor U, the universe we work in.

The last property is not very important from an algebraic point of view, and easily satisfiable, so we will not give it too much attention.

Orderings and obligations

There is, in our opinion, a deep connection between obligations and orderings (and, in addition, distances), which works both ways. First, given a set of obligations, we can say that one situation is "better" than a seond situation, if the first satisfies "more" obligations than the second does. "More" can be measured by the set of obligations satisfied, and then by the subset/superset relation, or by the number of obligations. Both are variants of the Hamming distance. "Distance" between two situations can be measured by the set or number of obligations in which they differ (i.e. one situation satisfies them, the other not). In both cases, we will call the variants the set or the counting variant. This is also the deeper reason why we have to be careful with negation. Negation inverses such orderings, if φ is better than ¬φ, then ¬φ is worse than ¬¬φ = φ. But in some reasonable sense ∧ and ∨ preserve the ordering, thus they are compatibel with obligations. Conversely, given a relation (of quality), we might for instance require that obligations are closed under improvement. More subtle requirements might work with distances. The relations of quality and distance can be given abstractly (as the notion of size used for "soft" obligations), or as above by a starting set of obligations. We will also define important auxiliary concepts on such abstract relations.

Derivation revisited

A set of "basic" obligations generates an ordering and a distance between situations, ordering and distance can be used to define properties obligations should have. It is thus natural to define obligations derived from the basic set as those sets of situations which satisfy the desirable properties of obligations defined via the order and distance generated by the basic set of obligations. Our derivation is thus a two step procedure: first generate the order and distance, which define suitable sets of situations. We will call properties which are defined without using distances global properties (like closure under improving quality), properties involving distance (like being a neighbourhood) local properties.

Relativization

An important problem is relativization. Suppose O is a set of obligations for all possible situations, e.g. O is the obligation to post the letter, and O ′ is the obligation to water the flowers. Ideally, we will do both. Suppose we consider now a subset, where we cannot do both (e.g. for lack of time). What are our obligations in this subset? Are they just the restrictions to the subset? Conversely, if O is an obligation for a subset of all situations, is then some O ′ with O ⊆ O ′ an obligation for the set of all situations? In more complicated requirements, it might be reasonable e.g. to choose the ideal situations still in the big set, even if they are not in the subset to be considered, but use an approximation inside the subset. Thus, relativizations present a non-trivial problem with many possible solutions, and it seems doubtful whether a universally adequate solution can be found.

Numerous possibilities

Seeing the possibilities presented so far (set or counting order, set or counting distance, various relativizations), we can already guess that there are numerous possible reasonable approaches to what an obligation is or should be. Consequently, it seems quite impossible to pursue all these combinations in detail. Thus, we concentrate mostly on one combination, and leave it to the reader to fill in details for the others, if (s)he is so interested. We will also treat the defeasible case here. Perhaps somewhat surprisingly, this is straightforward, and largely due to the fact that there is one natural definition of "big" sets for the product set, given that "big" sets are defined for the components. So there are no new possibilities to deal with here. The multitude of possibilities is somewhat disappointing. It may, of course, be due to an incapacity of the present authors to find the right notion. But it may also be a genuine problem of ambiguous intuitions, and thus generate conflicting views and misunderstandings on the one side, and loopholes for not quite honest argumentation in practical juridical reasoning on the other hand.

1.9 Notation P(X) will be the powerset of X, A ⊆ B will mean that A is a subset of B, or A = B, A ⊂ B that A is a proper subset of B.

Overview of the article

We will work in a finite propositional setting, so there is a trivial and 1-1 correspondence between formulas and model sets. Thus, we can just work with model sets -which implies, of course, that obligations will be robust under logical reformulation. So we will formulate most results only for sets.

• In Section 2 (page 4) , we give the basic definitions, together with some simple results about those definitions.

• Section 3 (page 10) will present a more philosophical discussion, with more examples, and we will argue that our definitions are relevant for our purpose.

• As said already, there seems to be a multitude of possible and reasonable definitions of what an obligation can or should be, so we limit our formal investigation to a few cases, this is given in Section 4 (page 13).

• In Section 5 (page 16), we give a tentative definition of an obligation.

(The concept of neighbourhood semantics is not new, and was already introduced by D.Scott, [START_REF] Scott | Advice in modal logic[END_REF], and R.Montague, [START_REF] Montague | Universal grammar[END_REF]. Further investigations showed that it was also used by O.Pacheco, [START_REF] Pacheco | Neighbourhood semantics for deontic and agency logics[END_REF], precisely to avoid unwanted weakening for obligations. We came the other way and started with the concept of independent strengthening, see Definition 2.13 (page 9), and introduced the abstract concept of neighbourhood semantics only at the end. This is one of the reasons we also have different descriptions which turned out to be equivalent: we came from elsewhere.)

Basic definitions

We give here all definitions needed for our treatment of obligations. The reader may continue immediately to Section 3 (page 10), and come back to the present section whenever necessary. Intuitively, U is supposed to be the set of models of some propositional language L, but we will stay purely algebraic whenever possible. U ′ ⊆ U is some subset. For ease of writing, we will here and later sometimes work with propositional variables, and also identify models with the formula describing them, still this is just shorthand for arbitrary sets and elements. pq will stand for p ∧ q, etc. If a set O of obligations is given, these will be just arbitrary subsets of the universe U. We will also say that O is over U. Before we deepen the discussion of more conceptual aspects, we give some basic definitions (for which we claim no originality). We will need them quite early, and think it is better to put them together here, not to be read immediately, but so the reader can leaf back and find them easily.

We work here with a notion of size (for the defeasible case), a notion d of distance, and a quality relation . The latter two can be given abstractly, but may also be defined from a set of (basic) obligations.

We use these notions to describe properties obligations should, in our opinion, have. A careful analysis will show later interdependencies between the different properties.

Size

For each U ′ ⊆ U we suppose an abstract notion of size to be given. We may assume this notion to be a filter or an ideal.

Coherence properties between the filters/ideals of different U ′ , U ′′ will be left open, the reader may assume them to be the conditions of the system P of preferential logic, see [START_REF] Gabbay | Size and logic[END_REF].

Given such notions of size on U ′ and U ′′ , we will also need a notion of size on U ′ × U ′′ . We take the evident solution:

Definition 2.1 Let a notion of "big subset" be defined by a principal filter for all X ⊆ U and all X ′ ⊆ U ′ . Thus, for all X ⊆ U there exists a fixed principal filter F (X) ⊆ P(X), and likewise for all X ′ ⊆ U ′ . (This is the situation in the case of preferential structures, where F (X) is generated by µ(X), the set of minimal elements of X.)

Define now F (X × X ′ ) as generated by {A × A ′ : A ∈ F(X), A ′ ∈ F(X ′ )}, i.e. if A is the smallest element of F (X), A ′ the smallest element of F (X ′ ), then F (X × X ′ ) := {B ⊆ X × X ′ : A × A ′ ⊆ B}.
Fact 2.1 If F (X) and F (X ′ ) are generated by preferential structures X , X ′ , then F (X ×X ′ ) is generated by the product structure defined by x, x ′ X×X ′ y, y ′ :⇔ x X y and x ′ X ′ y ′ .

Proof

We will omit the indices of the orderings when this causes no confusion.

Let A ∈ F(X), A ′ ∈ F(X ′ ), i.e. A minimizes X, A ′ minimizes X ′ . Let x, x ′ ∈ X × X ′ , then there are a ∈ A, a ′ ∈ A ′ with a x, a ′ x ′ , so a, a ′ x, x ′ . Conversely, suppose U ⊆ X × X ′ , U minimizes X × X ′ . but there is no A × A ′ ⊆ U s.t. A ∈ F(X), A ′ ∈ F(X ′ ). Assume A = µ(X), A ′ = µ(X ′ ), so there is a, a ′ ∈ µ(X) × µ(X ′ ), a, a ′ ∈ U.
But only a, a ′ a, a ′ , and U does not minimize X × X ′ , contradiction. 2

Note that a natural modification of our definition:

There is A ∈ F(X) s.t. for all a ∈ A there is a (maybe varying) A ′ a ∈ F(X ′ ), and U := { a, a ′ : a ∈ A, a ′ ∈ A ′ a } as generating sets will result in the same definition, as our filters are principal, and thus stable under arbitrary intersections.

Distance

We consider a set of sequences Σ, for x ∈ Σ x : I → S, I a finite index set, S some set. Often, S will be {0, 1}, x(i) = 1 will mean that x ∈ i, when I ⊆ P(U ) and x ∈ U. For abbreviation, we will call this (unsystematically, often context will tell) the ∈ -case. Often, I will be written O, intuitively, O ∈ O is then an obligation, and x(O) = 1 means x ∈ O, or x "satisfies" the obligation O.

Definition 2.2 In the ∈ -case, set O(x) := {O ∈ O : x ∈ O}.
Definition 2.3 Given x, y ∈ Σ, the Hamming distance comes in two flavours:

d s (x, y) := {i ∈ I : x(i) = y(i)}, the set variant, d c (x, y) := card(d s (x, y)), the counting variant. We define d s (x, y) ≤ d s (x ′ , y ′ ) iff d s (x, y) ⊆ d s (x ′ , y ′ ), thus, s-distances are not always comparabel.
Proof (2.1) Suppose U = {x, y}, O = {U }, then O(X) = O(Y ), but x = y. (2.3) If i ∈ d s (x, y) ∪ d s (y, z), then x(i) = y(i) = z(i), so x(i) = z(i) and i ∈ d s (x, z).
The others are trivial. 2 Definition 2.4 (1) We can define for any distance d with some minimal requirements a notion of "between". If the codomain of d has an ordering ≤, but no addition, we define: x, y, z d :⇔ d(x, y) ≤ d(x, z) and d(y, z) ≤ d(x, z).

If the codomain has a commutative addition, we define x, y, z d :⇔ d(x, z) = d(x, y) + d(y, z) -in d s + will be replaced by ∪, i.e.

x, y, z s :⇔ d(x, z) = d(x, y) ∪ d(y, z).

For above two Hamming distances, we will write x, y, z s and x, y, z c .

(2) We further define: [x, z] d := {y ∈ X : x, y, x d } -where X is the set we work in.

We will write [x, z] s and [x, z] c when appropriate.

(3) For

x ∈ U, X ⊆ U set x d X := {x ′ ∈ X : ¬∃x ′′ = x ′ ∈ X.d(x, x ′ ) ≥ d(x, x ′′ )}. Note that, if X = ∅, then x X = ∅.
We omit the index when this does not cause confusion. Again, when adequate, we write s and c .

For problems with characterizing "between" see [START_REF] Schlechta | Coherent Systems[END_REF].

Fact 2.3 (0) x, y, z d ⇔ z, y, x d .
Consider the situation of a set of sequences Σ.

Let A := A σ,σ ′′ := {σ ′ : ∀i ∈ I(σ(i) = σ ′′ (i) → σ ′ (i) = σ(i) = σ ′′ (i))}. Then (1) If σ ′ ∈ A, then d s (σ, σ ′′ ) = d s (σ, σ ′ ) ∪ d s (σ ′ , σ ′′ ), so σ, σ ′ , σ ′′ s .
(2) If σ ′ ∈ A and S consists of 2 elements (as in classical 2-valued logic), then d s (σ, σ ′ ) and d s (σ ′ , σ ′′ ) are disjoint.

(3) [σ, σ ′′ ] s = A.

(4) If, in addition, S consists of 2 elements, then [σ, σ ′′ ] c = A. Proof (0) Trivial.

(1) " ⊆ " follows from Fact 2.2 (page 5), (2.3).

Conversely, if e.g. i ∈ d s (σ, σ ′ ), then by prerequisite i ∈ d s (σ, σ ′′ ).

(2

) Let i ∈ d s (σ, σ ′ ) ∩ d s (σ ′ , σ ′′ ), then σ(i) = σ ′ (i) and σ ′ (i) = σ ′′ (i), but then by card(S) = 2 σ(i) = σ ′′ (i), but σ ′ ∈ A, contradiction.
We turn to (3) and (4):

If σ ′ ∈ A, then there is i ′ s.t. σ(i ′ ) = σ ′′ (i ′ ) = σ ′ (i ′ ). On the other hand, for all i s.t. σ(i) = σ ′′ (i) i ∈ d s (σ, σ ′ ) ∪ d s (σ ′ , σ ′′ ). Thus: (3) By (1) σ ′ ∈ A ⇒ σ, σ ′ , σ ′′ s . Suppose σ ′ ∈ A, so there is i ′ s.t. i ′ ∈ d s (σ, σ ′ ) -d s (σ, σ ′′ ), so < σ, σ ′ , σ ′′ > s cannot be. (4) By (1) and (2) σ ′ ∈ A ⇒ < σ, σ ′ , σ ′′ > c . Conversely, if σ ′ ∈ A, then card(d s (σ, σ ′ ))+card(d s (σ ′ , σ ′′ )) ≥ card(d s (σ, σ ′′ ))+ 2. 2 Definition 2.5
Given a finite propositional laguage L defined by the set v(L) of propositional variables, let L ∧ be the set of all consistent conjunctions of elements from v(L) or their negations. Thus, p ∧ ¬q ∈ L ∧ if p, q ∈ v(L), but p ∨ q, ¬(p ∧ q) ∈ L ∧ . Finally, let L ∨∧ be the set of all (finite) disjunctions of formulas from L ∧ . (As we will later not consider all formulas from L ∧ , this will be a real restriction.)

Quality and closure

Definition 2.6 Given any relation (of quality), we say that X ⊆ U is (downward) closed (with respect to ) iff ∀x ∈ X∀y ∈ U (y x ⇒ y ∈ X).

(Warning, we follow the preferential tradition, "smaller" will mean "better".) We think that being closed is a desirable property for obligations: what is at least as good as one element in the obligation should be "in", too.

Fact 2.5 Let be given.

(1) Let D ⊆ U ′ ⊆ U ′′ , D closed in U ′′ , then D is also closed in U ′ . (2) Let D ⊆ U ′ ⊆ U ′′ , D closed in U ′ , U ′ closed in U ′′ , then D is closed in U ′′ .
(3) Let D i ⊆ U ′ be closed for all i ∈ I, then so are {D i : i ∈ I} and {D i : i ∈ I}.

Proof

(1) Trivial.

(

2) Let x ∈ D ⊆ U ′ , x ′ x, x ′ ∈ U ′′ , then x ′ ∈ U ′ by closure of U ′′ , so x ′ ∈ D by closure of U ′ .
(3) Trivial. 2

We may have an abstract relation of quality on the domain, but we may also define it from the structure of the sequences, as we will do now.

Definition 2.7 Consider the case of sequences. Given a relation (of quality) on the codomain, we extend this to sequences in Σ :

x ∼ y :⇔ ∀i ∈ I(x(i) ∼ y(i))

x y :⇔ ∀i ∈ I(x(i) y(i))

x ≺ y :⇔ ∀i ∈ I(x(i) y(i)) and ∃i ∈ I(x(i) ≺ y(i))

In the ∈ -case, we will consider x ∈ i better than x ∈ i. As we have only two values, true/false, it is easy to count the positive and negative cases (in more complicated situations, we might be able to multiply), so we have an analogue of the two Hamming distances, which we might call the Hamming quality relations. Let O be given now. (Recall that we follow the preferential tradition, "smaller" will mean "better".)

x ∼ s y :⇔ O(x) = O(y), x s y :⇔ O(y) ⊆ O(x), x ≺ s y :⇔ O(y) ⊂ O(x), x ∼ c y :⇔ card(O(x)) = card(O(y)), x c y :⇔ card(O(y)) ≤ card(O(x)), x ≺ c y :⇔ card(O(y)) < card(O(x)).
The requirement of closure causes a problem for the counting approach: Given e.g. two obligations O, O ′ , then any two elements in just one obligation have the same quality, so if one is in, the other should be, too. But this prevents now any of the original obligations to have the desirable property of closure. In the counting case, we will obtain a ranked structure, where elements satisfy 0, 1, 2, etc. obligations, and we are unable to differentiate inside those layers. Moreover, the set variant seems to be closer to logic, where we do not count the propositional variables which hold in a model, but consider them individually. For these reasons, we will not pursue the counting approach as systematically as the set approach. One should, however, keep in mind that the counting variant gives a ranking relation of quality, as all qualities are comparable, and the set variant does not. A ranking seems to be appreciated sometimes in the literature, though we are not really sure why. Of particular interest is the combination of d s and s (d c and c ) respectively -where by s we also mean ≺ s and ∼ s , etc. We turn to this now.

Fact 2.6

We work in the ∈ -case.

(1)

x s y ⇒ d s (x, y) = O(x) -O(y) Let a ≺ s b ≺ s c. Then (2) d s (a, b) and d s (b, c) are not comparable, (3) d s (a, c) = d s (a, b) ∪ d s (b, c), and thus b ∈ [a, c] s .
This does not hold in the counting variant, as Example 2.1 (page 8) shows.

(4) Let x ≺ s y and x ′ ≺ s y with x, x ′ ≺ s -incomparabel. Then d s (x, y) and d s (x ′ , y) are incomparable.

(This does not hold in the counting variant, as then all distances are comparable.)

(5) If x ≺ s z, then for all y ∈ [x, z] s x s y s z.

Proof

(1) Trivial.

(2) We have O(c) ⊂ O(b) ⊂ O(a), so the results follows from (1).

(3) By definition of d s and (1).

(4) x and x ′ are s -incomparable, so there are

O ∈ O(x) -O(x ′ ), O ′ ∈ O(x ′ ) -O(x). As x, x ′ ≺ s y, O, O ′ ∈ O(y), so O ∈ d s (x, y) -d s (x ′ , y), O ′ ∈ d s (x ′ , y) -d s (x, y). (5) x ≺ s z ⇒ O(z) ⊂ O(x), d s (x, z) = O(x) -O(z). By prerequisite d s (x, z) = d s (x, y) ∪ d s (y, z). Suppose x s y. Then there is i ∈ O(y) -O(x) ⊆ d s (x, y), so i ∈ O(x) -O(z) = d s (x, z), contradiction. Suppose y s z. Then there is i ∈ O(z) -O(y) ⊆ d s (y, z), so i ∈ O(x) -O(z) = d s (x, z), contradiction. 2 Example 2.1
In this and similar examples, we will use the model notation. Some propositional variables p, q, etc. are given, and models are described by p¬qr, etc. Moreover, the propositional variables are the obligations, so in this example we have the obligations p, q, r. Consider x := ¬p¬qr, y := pq¬r, z := ¬p¬q¬r. Then y

≺ c x ≺ c z, d c (x, y) = 3, d c (x, z) = 1, d c (z, y) = 2, so x ∈ [y, z] c . 2 Definition 2.8
Given a quality relation ≺ between elements, and a distance d, we extend the quality relation to sets and define:

(1) x ≺ Y :⇔ ∀y ∈ (x Y ).x ≺ y. (The closest elements -i.e. there are no closer ones -of Y, seen from x, are less good than x.)

analogously X ≺ y :⇔ ∀x ∈ (y X).x ≺ y (2) X ≺ l Y :⇔ ∀x ∈ X.x ≺ Y and ∀y ∈ Y.X ≺ y (X is locally better than Y ).
When necessary, we will write ≺ l,s or ≺ l,c to distinguish the set from the counting variant.

For the next definition, we use the notion of size: ∇φ iff for almost all φ holds i.e. the set of exceptions is small.

(3) X ≪ l Y :⇔ ∇x ∈ X.x ≺ Y and ∇y ∈ Y.X ≺ y. We will likewise write ≪ l,s etc. This definition is supposed to capture quality difference under minimal change, the "ceteris paribus" idea: X ≺ l CX should hold for an obligation X. Minimal change is coded by , and "ceteris paribus" by minimal change.

Fact 2.7 If X ≺ l CX, and x ∈ U an optimal point (there is no better one), then x ∈ X.

Proof

If not, then take x ′ ∈ X closest to x, this must be better than x, contradiction. 2 Fact 2.8 Take the set version. If X ≺ l,s CX, then X is downward ≺ s -closed.

Proof

Suppose X ≺ l,s CX, but X is not downward closed.

Case 1: There are x ∈ X, y ∈ X, y ∼ s x. Then y ∈ x s CX, but x ≺ y, contradiction. Case 2: There are x ∈ X, y ∈ X, y ≺ s x. By X ≺ l,s CX, the elements in X closest to y must be better than y. Thus, there is x ′ ≺ s y, x ′ ∈ X, with minimal distance from y. But then x ′ ≺ s y ≺ s x, so d s (x ′ , y) and d s (y, x) are incomparable by Fact 2.6 (page 7), so x is among those with minimal distance from y, so X ≺ l,s CX does not hold. 2 Example 2.2 We work with the set variant. This example shows that s -closed does not imply X ≺ l,s CX, even if X contains the best elements.

Let O := {p, q, r, s}, U ′ := {x := p¬q¬r¬s, y := ¬pq¬r¬s, x ′ := pqrs}, X := {x, x ′ }. x ′ is the best element of U ′ , so X contains the best elements, and X is downward closed in U ′ , as x and y are not comparable. d s (x, y) = {p, q}, d s (x ′ , y) = {p, r, s}, so the distances from y are not comparable, so x is among the closest elements in X, seen from y, but x ≺ s y. The lack of comparability is essential here, as the following Fact shows. 2

We have, however, for the counting variant: Fact 2.9 Consider the counting variant. Then If X is downward closed, then X ≺ l,c CX.

Proof

Take any x ∈ X, y ∈ X. We have y c x or x ≺ c y, as any two elements are c -comparabel. y c x contradicts closure, so x ≺ c y, and X ≺ l,c CX holds trivially. 2

Neighbourhood

Definition 2.9 Given a distance d, we define:

(1) Let X ⊆ Y ⊆ U ′ , then Y is a neighbourhood of X in U ′ iff ∀y ∈ Y ∀x ∈ X(x is closest to y among all x ′ with x ′ ∈ X ⇒ [x, y] ∩ U ′ ⊆ Y ).
(Closest means that there are no closer ones.) When we also have a quality relation ≺, we define:

(2) Let X ⊆ Y ⊆ U ′ , then Y is an improving neighbourhood of X in U ′ iff ∀y ∈ Y ∀x((x is closest to y among all x ′ with x ′ ∈ X and x ′ y) ⇒ [x, y] ∩ U ′ ⊆ Y ).
When necessary, we will have to say for (3) and (4) which variant, i.e. set or counting, we mean.

Fact 2.10 (1) If X ⊆ X ′ ⊆ Σ, and d(x, y) = 0 ⇒ x = y, then X and X ′ are Hamming neighbourhoods of X in X ′ .

(2) If X ⊆ Y j ⊆ X ′ ⊆ Σ for j ∈ J, and all Y j are Hamming Neighbourhoods of X in X ′ , then so are {Y j : j ∈ J} and {Y j : j ∈ J}.

Proof

(1) is trivial (we need here that d(x, y) = 0 ⇒ x = y).

(2) Trivial. 2

Unions of intersections and other definitions

Definition 2.10 Let O over U be given. X ⊆ U ′ is (ui) (for union of intersections) iff there is a family

O i ⊆ O, i ∈ I s.t. X = ( { O i : i ∈ I}) ∩ U ′ .
Unfortunately, this definition is not very useful for simple relativization.

Definition 2.11

Let O be over U.

Let O ′ ⊆ O. Define for m ∈ U and δ : O ′ → 2 = {0, 1} m |= δ :⇔ ∀O ∈ O ′ (m ∈ O ⇔ δ(O) = 1) Definition 2.12 Let O be over U. O is independent iff ∀δ : O → 2.∃m ∈ U.m |= δ.
Obviously, independence does not inherit downward to subsets of U.

Definition 2.13

This definition is only intended for the set variant.

Let O be over U.

D(O) := {X ⊆ U ′ : ∀O ′ ⊆ O ∀δ : O ′ → 2 ((∃m, m ′ ∈ U, m, m ′ |= δ, m ∈ X, m ′ ∈ X) ⇒ (∃m ′′ ∈ X.m ′′ |= δ ∧ m ′′ ≺ s m ′ ))}
This property expresses that we can satisfy obligations independently: If we respect O, we can, in addition, respect O ′ , and if we are hopeless kleptomaniacs, we may still not be a murderer. If X ∈ D(O), we can go from U -X into X by improving on all O ∈ O, which we have not fixed by δ, if δ is not too rigid.

Philosophical discussion of obligations

We take now a closer look at obligations, in particular at the ramifications of the treatment of the relation "better". Some aspects of obligations will also need a notion of distance, we call them local properties of obligations.

A fundamental difference between facts and obligations: asymmetry and negation

There is an important difference between facts and obligations. A situation which satisfies an obligation is in some sense "good", a situation which does not, is in some sense "bad". This is not true of facts. Being "round" is a priori not better than "having corners" or vice versa. But given the obligation to post the letter, the letter in the mail box is "good", the letter in he trash bin is "bad". Consequently, negation has to play different role for obligations and for facts. This is a fundamental property, which can also be found in orders, planning (we move towards the goal or not), reasoning with utility (is φ or ¬φ more useful?), and probably others, like perhaps the Black Raven paradox.

We also think that the Ross paradox (see below) is a true paradox, and should be avoided. A closer look shows that this paradox involves arbitrary weakening, in particular by the "negation" of an obligation. This was a starting point of our analysis. "Good" and "bad" cannot mean that any situation satisfying obligation O is better than any situation not satisfying O, as the following example shows.

Example 3.1 If we have three independent and equally strong obligations, O, O ′ , O ′′ , then a situation satisfying O but neither O ′ nor O ′′ will not be better than one satisfying O ′ and O ′′ , but not O.

We have to introduce some kind of "ceteris paribus". All other things being equal, a situation satisfying O is better than a situation not satisfying O, see Section 3.3 (page 11).

Example 3.2

The original version of the Ross paradox reads: If we have the obligation to post the letter, then we have the obligation to post or burn the letter. Implicit here is the background knowledge that burning the letter implies not to post it, and is even worse than not posting it. We prefer a modified version, which works with two independent obligations: We have the obligation to post the letter, and we have the obligation to water the plants. We conclude by unrestricted weakening that we have the obligation to post the letter or not to water the plants. This is obvious nonsense. It is not the "or" itself which is the problem. For instance, in case of an accident, to call an ambulance or to help the victims by giving first aid is a perfectly reasonable obligation. It is the negation of the obligation to water the plants which is the problem. More generally, it must not be that the system of suitable sets is closed under arbitrary supersets, otherwise we have closure under arbitrary right weakening, and thus the Ross paradox. Notions like "big subset" or "small exception sets" from the semantics of nonmonotonic logics are closed under supersets, so they are not suitable.

3.2 "And" and "or" for obligations "Not" behaves differently for facts and for obligations. If O and O ′ are obligations, can O ∧ O ′ be considered an obligation? We think, yes. "Ceteris paribus", satisfying O and O ′ together is better than not to do so. If is the obligation to post the letter, O ′ to water the plants, then doing both is good, and better than doing none, or only one. Is O ∨ O ′ an obligation? Again, we think, yes. Satisfying one (or even both, a non-exclusive or) is better than doing nothing. We might not have enough time to do both, so we do our best, and water the plants or post the letter. Thus, if α and β are obligations, then so will be α ∧ β and α ∨ β, but not anything involving ¬α or ¬β. (In a non-trivial manner, leaving aside tautologies and contradictions which have to be considered separately.) To summarize: "and" and "or" preserve the asymmetry, "not" does not, therefore we can combine obligations using "and" and "or", but not "not". Thus, a reasonable notion of derivation of obligations will work with ∧ and ∨, but not with ¬.

We should not close under inverse ∧, i.e. if φ ∧ φ ′ is an obligation, we should not conclude that φ and φ ′ separately are obligations, as the following example shows. Example 3.3 Let p stand for: post letter, w : water plants, s : strangle grandmother. Consider now φ ∧ φ ′ , where φ = p ∨ (¬p ∧ ¬w), φ ′ = p ∨ (¬p ∧ w ∧ s). φ ∧ φ ′ is equivalent to p -though it is perhaps a bizarre way to express the obligation to post the letter. φ leaves us the possibility not to water the plants, and φ ′ to strangle the grandmother, and neither seem good obligations. 2 Remark 3.1 This is particularly important in the case of soft obligations, as we see now, when we try to apply the rules of preferential reasoning to obligations. One of the rules of preferential reasoning is the (OR) rule:

φ ∼ | ψ, φ ′ ∼ | ψ ⇒ φ ∨ φ ′ ∼ | ψ.
Suppose we have φ ∼ | ψ ′ ∧ ψ ′′ , and φ ′ ∼ | ψ ′ . We might be tempted to split ψ ′ ∧ ψ ′′ -as ψ ′ is a "legal" obligation, and argue:

φ ∼ | ψ ′ ∧ ψ ′′ , so φ ∼ | ψ ′ , moreover φ ′ ∼ | ψ ′ , so φ ∨ φ ′ ∼ | ψ ′ .
The following example shows that this is not always justified.

Then above "ceteris paribus" criterion is satisfied, as y ′ and x do not "see" each other, so X ≺ l,c CX.

But X is not downward closed, below x ∈ X is a better element y ′ ∈ X. This seems an argument against X being an obligation. The set version:

We still have x ′ ≺ s y ′ ≺ s x ≺ s y. As shown in Fact 2.6 (page 7), d s (x, y) (and also d s (x ′ , y ′ )) and d s (x, y ′ ) are not comparable, so our argument collapses. As a matter of fact, we have the result that the "ceteris paribus" criterion entails downward closure in the set variant, see Fact 2.8 (page 8). 2

Note that a sufficiently rich domain (put elements between y ′ and x) will make this local condition (for ≺) a global one, so we have here a domain problem. Domain problems are discussed e.g. in [START_REF] Schlechta | Coherent Systems[END_REF] and [START_REF] Gabbay | Cumulativity without closure of the domain under finite unions[END_REF].

(2) Best states It seems also reasonable to postulate that obligations contain all best states. In particular, obligations have then to be consistent -under the condition that best states exist. We are aware that this point can be debated, there is, of course, an easy technical way out: we take, when necessary, unions of obligations to cover the set of ideal cases. So obligations will be certain "neighbourhoods" of the "best" situations. We think, that some such notion of neighbourhood is a good candidate for a semantics:

• A system of neighbourhoods is not necessarily closed under supersets.

• Obligations express something like an approximation to the ideal case where all obligations (if possible, or, as many as possible) are satisfied, so we try to be close to the ideal. If we satisfy an obligation, we are (relatively) close, and stay so as long as the obligation is satisfied. • The notion of neighbourhood expresses the idea of being close, and containing everything which is sufficiently close. Behind "containing everything which is sufficiently close" is the idea of being in some sense convex. Thus, "convex" or "between" is another basic notion to be investigated. See here also the discussion of "between" in [START_REF] Schlechta | Coherent Systems[END_REF].

Soft obligations

"Soft" obligations are obligations which have exceptions. Normally, one is obliged to do O, but there are cases where one is not obliged. This is like soft rules, as "Birds fly" (but penguins do not), where exceptions are not explicitly mentioned. The semantic notions of size are very useful here, too. We will content ourselves that soft obligations satisfy the postulates of usual obligations everywhere except on a small set of cases. For instance, a soft obligation O should be downward closed "almost" everywhere, i.e. for a small subset of pairs a, b in U × U we accept that a ≺ b, b ∈ O, a ∈ O. We transplanted a suitable and cautious notion of size from the components to the product in Definition 2.1 (page 4).

When we look at the requirement to contain the best cases, we might have to soften this, too. We will admit that a small set of the ideal cases might be excluded. Small can be relative to all cases, or only to all ideal cases. Soft obligations generate an ordering which takes care of exceptions, like the normality ordering of birds will take care of penguins: within the set of pengins, non-flying animals are the normal ones. Based on this ordering, we define "derived soft obligations", they may have (a small set of) exceptions with respect to this ordering.

Overview of different types of obligations

(1) Hard obligations. They hold without exceptions, as in the Ten Commandments. You should not kill.

(1.1) In the simplest case, they apply everywhere and can be combined arbitrarily, i.e. for any O ′ ⊆ O there is a model where all O ∈ O ′ hold, and no O ′ ∈ O -O ′ . (1.2) In a more complicated case, not all combinations are possible. This is the same as considering just an arbitrary subset of U with the same set O of obligations. This case is very similar to the case of conditional obligations (which might not be defined outside a subset of U ), and we treat them together.

A good example is the Considerate Assassin:

Example 3.7 Normally, one should not offer a cigarette to someone, out of respect for his health. But the considerate assassin might do so nonetheless, on the cynical reasoning that the victim's health is going to suffer anyway:

(1) One should not kill, ¬k.

(2) One should not offer cigarettes, ¬o.

(3) The assassin should offer his victim a cigarette before killing him, if k, then o.

Here, globally, ¬k and ¬o is best, but among k-worlds, o is better than ¬o. The model ranking is ¬k ∧ ¬o ≺ ¬k ∧ o ≺ k ∧ o ≺ k ∧ ¬o.

Recall that an obligation for the whole set need not be an obligation for a subset any more, as it need not contain all best states. In this case, we may have to take a union with other obligations.

(2) Soft obligations. Many obligations have exceptions. Consider the following example:

(1.2) It is closed under increasing quality, Definition 2.6 (page 6)

(1.

3) It is an improving neighbourhood of the ideal cases (this also implies (1.1)), Definition 2.9 (page 9) We are less committed to:

(1.4) It is ceteris paribus improving, Definition 2.8 (page 8) An obligation O is a derived obligation of a system O of obligations iff it is a hard obligation based on the set variant of the order and distance generated by O.

(2) Soft obligations A set is a soft obligation iff it satisfies the soft versions of above postulates. The notion of size has to be given, and is transferred to products as described in Definition 2.1 (page 4). More precisely, strict universal quantifiers are transformed into their soft variant "almost all", and the other operators are left as they are. Of course, one might also want to use a mixture of soft and hard conditions, e.g. we might want to have all ideal cases, but renounce on closure for a small set of pairs x, x ′ . An obligation O is derived from O iff it is a soft obligation based on the set variant of the order and distance generated by the translation of O into their hard versions. (I.e. exceptions will be made explicit.) Example 5.1 The Ross paradox is not a derived obligation.

Proof

Suppose we have the alphabet p, q and the obligations {p, q}, let R := p∨¬q. This is not not closed, as ¬p∧q ≺ ¬p∧¬q ∈ R. 2

Conclusion

Obligations differ from facts in the behaviour of negation, but not of conjunction and disjunction. The Ross paradox originates, in our opinion, from the differences in negation. Central to the treatment of obligations seems to be a relation of "better", which can generate obligations, but also be generated by obligations. The connection between obligations and this relation of "better" seems to be somewhat complicated and leads to a number of ramifications. A tentative definition of a derivation of obligations is given.

  4.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.2 The not necessarily independent case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1.3 The independent case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Remarks on the counting case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Fact 2.2 (1) In the ∈ -case, we have d s (x, y) = O(x)△O(y), where △ is the symmetric set difference. (2) d c has the normal addition, set union takes the role of addition for d s , ∅ takes the role of 0 for d s , both are distances in the following sense: (2.1) d(x, y) = 0 if x = y, but not conversely, (2.2) d(x, y) = d(y, x), (2.3) the triangle inequality holds, for the set variant in the form d s (x, z) ⊆ d s (x, y) ∪ d s (y, z). (If d(x, y) = 0 ⇒ x = y poses a problem, one can always consider equivalence classes.)

  Given a set of models M for a finite language L, define φ M := {p ∈ v(L) : ∀m ∈ M.m(p) = v} ∧ {¬p : p ∈ v(L), ∀m ∈ M.m(p) = f } ∈ L ∧ . (If there are no such p, set φ M := T RU E.) This is the strongest φ ∈ L ∧ which holds in M.Fact 2.4 If x, y are models, then [x, y] = M (φ {x,y} ). 2 Proof m ∈ [x, y] ⇔ ∀p(x |= p, y |= p ⇒ m |= p and x |= p, y |= p ⇒ m |= p), m |= φ {x,y} ⇔ m |= {p : x(p) = y(p) = v} ∧ {¬p : x(p) = y(p) = f }.

Fact 5. 1

 1 Let O ∈ O, then O ∼ | O in the independent set case.ProofWe check (1.1) -(1.3) of Definition 5.1 (page 16).(1.1) holds by independence.(1.2) If x ∈ O, x ′ ∈ O, then x ′ s x. (1.3) By Fact 4.1 (page 14) (6).Note that (1.4) will also hold by Fact 4.3 (page 15) (2). 2 Corollary 5.2 Every derived obligation is a classical consequence of the original set of obligations in the independent set case.ProofThis follows from Fact 4.3 (page 15) (3) and Fact 5.1 (page 17).

Acknowledgements

We thank A.Herzig, Toulouse, and L.v.d.Torre, Luxembourg, for very helpful discussions.

Example 3.4 Consider the following obligations for a physician: Let φ ′ imply that the patient has no heart disease, and if φ ′ holds, we should give drug A or (not drug A, but drug B), abbreviated A ∨ (¬A ∧ B). (B is considered dangerous for people with heart problems.) Let φ imply that the patient has heart problems. Here, the obligation is (A ∨ (¬A ∧ B)) ∧ (A ∨ (¬A ∧ ¬B)), equivalent to A. The false conclusion would then be φ ′ ∼ | A ∨ (¬A ∧ B), and φ ∼ | A ∨ (¬A ∧ B), so φ ∨ φ ′ ∼ | A ∨ (¬A ∧ B), so in both situation we should either give A or B, but B is dangerous in "one half" of the situations. 2

We captured this idea about "and" and "or" in Definition 2.10 (page 9).

Ceteris paribus -a local poperty

Basically, the set of points "in" an obligation has to be better than the set of "exterior" points. As above Example 3.1 (page 10) with three obligations shows, demanding that any element inside is better than any element outside, is too strong. We use instead the "ceteris paribus" idea. "All other things being equal" seems to play a crucial role in understanding obligations. Before we try to analyse it, we look for other concepts which have something to do with it. The Stalnaker/Lewis semantics for counterfactual conditionals also works with some kind of "ceteris paribus". "If it were to rain, I would use an umbrella" means something like: "If it were to rain, and there were not a very strong wind" (there is no such wind now), "if I had an umbrella" (I have one now), etc., i.e. if things were mostly as they are now, with the exception that now it does not rain, and in the situation I speak about it rains, then I will use an umbrella. But also theory revision in the AGM sense contains -at least as objective -this idea: Change things as little as possible to incorporate some new information in a consistent way. When looking at the "ceteris paribus" in obligations, a natural interpretation is to read it as "all other obligations being unchanged" (i.e. satisfied or not as before). This is then just a Hamming distance considering the obligations (but not other information).

Then, in particular, if O is a family of obligations, and if x and x ′ are in the same subset O ′ ⊆ O of obligations, then an obligation derived from O should not separate them. More precisely, if

Example 3.5

If the only obligation is not to kill, then it should not be derivable not to kill and to eat spaghetti.

Often, this is impossible, as obligations are not independent. In this case, but also in other situations, we can push "ceteris paribus" into an abstract distance d (as in the Stalnaker/Lewis semantics), which we postulate as given, and say that satisfying an obligation makes things better when going from "outside" the obligation to the d-closest situation "inside". Conversely, whatever the analysis of "ceteris paribus", and given a quality order on the situations, we can now define an obligation as a formula which (perhaps among other criteria) "ceteris paribus" improves the situation when we go from "outside" the formula "inside". A simpler way to capture "ceteris paribus" is to connect it directly to obligations, see Definition 2.13 (page 9). This is probably too much tied to independence (see below), and thus too rigid.

Hamming neighbourhoods

A combination concept is a Hamming neighbourhood: X is called a Hamming neighbourhood of the best cases iff for any x ∈ X and y a best case with minimal distance from x, all elements between x and y are in X. For this, we need a notion of distance (also to define "between" ). This was made precise in Definition 2.3 (page 5) and Definition 2.9 (page 9).

Global and mixed global/local properties of obligations

We look now at some global properties (or mixtures of global and local) which seem desirable for obligations:

(1) Downward closure Consider the following example:

Example 3.6 Let U ′ := {x, x ′ , y, y ′ } with x ′ := pqrs, y ′ := pqr¬s, x := ¬p¬qr¬s, y := ¬p¬q¬r¬s.

The counting version: Then x ′ has quality 4 (the best), y ′ has quality 3, x has 1, y has 0.

Example 3.8 You are in a library. Of course, you should not pour water on a book. But if the book has caught fire, you should pour water on it to prevent worse damage. In stenographic style these obligations read: "Do not pour water on books". "If a book is on fire, do pour water on it." It is like "birds fly", but "penguins do not fly", "soft" or nonmonotonic obligations, which have exceptions, which are not formulated in the original obligation, but added as exceptions.

We could have formulated the library obligation also without exceptions: "When you are in a library, and the book is not on fire, do not pour water on it." "When you are in a library, and the book is on fire, pour water on it." This formulation avoids exceptions. Conditional obligations behave like restricted quantifiers: they apply in a subset of all possible cases. We treat now the considerate assassin case as an obligation (not to offer) with exceptions. Consider the full set U, and consider the obligation ¬o. This is not downward closed, as k ∧ o is better than k ∧ ¬o. Downward closure will only hold for "most" cases, but not for all.

(3) Contrary-to-duty obligations. Contrary-to-duty obligations are about different degrees of fulfillment. If you should ideally not have any fence, but are not willing or able to fulfill this obligation (e.g. you have a dog which might stray), then you should at least paint it white to make it less conspicuous. This is also a conditional obligation. Conditional, as it specifies what has to be done if there is a fence. The new aspect in contrary-to-duty obligations is the different degree of fulfillment.

We will not treat contrary-to-duty obligations here, as they do not seem to have any import on our basic ideas and solutions.

(4) A still more complicated case is when the language of obligations is not uniform, i.e. there are subsets V ⊆ U where obligations are defined, which are not defined in U -V.

We will not pursue this case here.

Summary of the philosophical remarks

(1) It seems justifiable to say that an obligation is satisfied or holds in a certain situation.

(2) Obligations are fundamentally asymmetrical, thus negation has to be treated with care. "Or" and "and" behave as for facts.

(3) Satisfying obligations improves the situation with respect to some given grading -ceteris paribus.

(4) "Ceteris paribus" can be defined by minimal change with respect to other obligations, or by an abstract distance.

(5) Conversely, given a grading and some distance, we can define an obligation locally as describing an improvement with respect to this grading when going from "outside" to the closest point "inside" the obligation.

(6) Obligations should also have global properties: they should be downward (i.e. under increasing quality) closed, and cover the set of ideal cases.

(7) The properties of "soft" obligations, i.e. with exceptions, have to be modified appropriately. Soft obligations generate an ordering, which in turn may generate other obligations, where exceptions to the ordering are permitted.

(8) Quality and distance can be defined from an existing set of obligations in the set or the counting variant. Their behaviour is quite different.

(9) We distinguished various cases of obligations, soft and hard, with and without all possibilities, etc.

Finally, we should emphasize that the notions of distance, quality, and size are in principle independent, even if they may be based on a common substructure.

Examination of the various cases

We will concentrate here on the set version of hard obligations.

Hard obligations for the set approach

Introduction

We work here in the set version, the ∈ -case, and examine mostly the set version only. We will assume a set O of obligations to be given. We define the relation ≺:=≺ O as described in Definition 2.3 (page 5), and the distance d is the Hamming distance based on O.

4.1.2

The not necessarily independent case Example 4.1 Work in the set variant. We show that X s -closed does not necessarily imply that X contains all s -best elements.

Let O := {p, q}, U ′ := {p¬q, ¬pq}, then all elements of U ′ have best quality in U ′ , X := {p¬q} is closed, but does not contain all best elements. 2

Example 4.2 Work in the set variant. We show that X s -closed does not necessarily imply that X is a neighbourhood of the best elements, even if X contains them. Consider x := pq¬rstu, x ′ := ¬pqrs¬t¬u, x ′′ := p¬qr¬s¬t¬u, y := p¬q¬r¬s¬t¬u, z := pq¬r¬s¬t¬u. U := {x, x ′ , x ′′ , y, z}, the ≺ s -best elements are x, x ′ , x ′′ , they are contained in X := {x, x ′ , x ′′ , z}. d s (z, x) = {s, t, u}, d s (z, x ′ ) = {p, r, s}, d s (z, x ′′ ) = {q, r}, so x ′′ is one of the best elements closest to z. d(z, y) = {q}, d(y, x ′′ ) = {r}, so [z, x ′′ ] = {z, y, x ′′ }, y ∈ X, but X is downward closed. 2

Fact 4.1 Work in the set variant. Let X = ∅, X s -closed. Then (1) X does not necessarily contain all best elements. Assume now that X contains, in addition, all best elements. Then (2) X ≺ l,s CX does not necessarily hold.

(3) X is (ui).

(4) X ∈ D(O) does not necessarily hold.

(5) X is not necessarily a neighbourhood of the best elements.

(6) X is an improving neighbourhood of the best elements.

(4) Consider Example 2.2 (page 8), let dom(δ) = {r, s}, δ(r) = δ(s) = 0. Then x, y |= δ, but x ′ |= δ and x ∈ X, y ∈ X, but there is no z ∈ X, z |= δ and z ≺ y, so X ∈ D(O).

(5) See Example 4.2 (page 14).

(6) By Fact 2.6 (page 7), (5).

(2.2) X is (ui) does not necessarily imply that X contains all s -best elements.

(3.1)

implies that X contains all s -best elements.

(4.1) X is an improving neighbourhood of the s -best elements ⇒ X is s -closed.

(4.2) X is an improving neighbourhood of the best elements ⇒ X contains all best elements.

Proof

(1.1) By Fact 2.8 (page 8).

(1.2) By Fact 2.7 (page 8).

(2.1) Let O ∈ O, then O is downward closed (no y ∈ O can be better than x ∈ O). The rest follows from Fact 2.5 (page 6) (3).

(2.2) Consider Example 4.1 (page 14), p is (ui) (formed in U !), but p ∩ X does not contain ¬pq.

But then there is no m ′′ |= δ, m ′′ ≺ s m ′ , as m ′ is already optimal among the n with n |= δ.

(3.2) Suppose X ∈ D(O), x ′ ∈ U -X is a best element, take δ := ∅, x ∈ X. Then there must be x ′′ ≺ x ′ , x ′′ ∈ X, but this is impossible as x ′ was best. (4.1) By Fact 2.6 (page 7) , (4) all minimal elements have incomparabel distance. But if z y, y ∈ X, then either z is minimal or it is above a minimal element, with minimal distance from y, so z ∈ X by Fact 2.6 (page 7) (3). The independent case Assume now the system to be independent, i.e. all combinations of O are present. Note that there is now only one minimal element, and the notions of Hamming neighbourhood of the best elements and improving Hamming neighbourhood of the best elements coincide.

Fact 4.3 Work in the set variant. Let X = ∅, X s -closed. Then (1) X contains the best element.

(2) X ≺ l,s CX

(3) X is (ui).

(4) X ∈ D(O)

(5) X is a (improving) Hamming neighbourhood of the best elements.

Proof

(1) Trivial.

(2) Fix x ∈ X, let y be closest to x, y ∈ X.

(5) Trivial by (1), the remark preceding this Fact, and Fact 4.1 (page 14) (6).

4) X is a (improving) neighbourhood of the best elements ⇒ X is s -closed.

Proof

(1) Suppose there are x ∈ X, y ∈ U -X, y ≺ x. Choose them with minimal distance. If card(d s (x, y)) > 1, then there is z, y ≺ s z ≺ s x, z ∈ X or z ∈ U -X, contradicting minimality. So card(d s (x, y)) = 1. So y is among the closest elements of U -X seen from x, but then by prerequisite x ≺ y, contradiction.

(2) By Fact 4.2 (page 14) (2.1).

(3) By Fact 4.2 (page 14) (3.1).

(4) There is just one best element z, so if x ∈ X, then [x, z] contains all y y ≺ x by Fact 2.6 (page 7) (3). 2

The D(O) condition seems to be adequate only for the independent situation, so we stop considering it now. Fact 4.5 Let X i ⊆ U, i ∈ I a family of sets, we note the following about closure under unions and intersections:

(1) If the X i are downward closed, then so are their unions and intersections.

(2) If the X i are (ui), then so are their unions and intersections.

Proof

Trivial. 2

We do not know whether ≺ l,s is preserved under unions and intersections, it does not seem an easy problem.

Fact 4.6 (1) Being downward closed is preserved while going to subsets.

(2) Containing the best elements is not preserved (and thus neither the neighbourhood property).

(3) The D(O) property is not preserved.

(4) l,s is not preserved.

Proof

(4) Consider Example 3.6 (page 11), and eliminate y from U ′ , then the closest to x not in X is y ′ , which is better. 2 We measure distances by counting. X ≺ l,c CX does not necessarily imply that X is an improving Hamming neighbourhood of the best elements.

Remarks on the counting case

Proof Consider Example 3.6 (page 11). There X ≺ l,c CX. x ′ is the best element, and y ′ ∈ [x ′ , x], but y ′ ∈ X. 2 5 What is an obligation?

The reader will probably not expect a final definition. All we can do is to give a tentative definition, which, in all probability, will not be satisfactory in all cases.