Research Report AI–1994–09

Defaults in Domain Theory

Guo-Qiang Zhang Department of Computer Science

University of Georgia William C. Rounds

Artificial Intelligence Laboratory University of Michigan

Defaults in Domain Theory

Guo-Qiang Zhang^{1} Department of Computer Science University of Georgia Athens, Georgia 30602 U.S.A. William C. Rounds Artificial Intelligence Laboratory University of Michigan Ann Arbor, Michigan 48109 U.S.A. December 7, 1994

Abstract. This paper uses ideas from artificial intelligence to show how default notions can be defined over Scott domains. We combine these ideas with ideas arising in domain theory to shed some light on the properties of nonmonotonicity in a general model-theoretic setting.

We consider in particular a notion of default nonmonotonic entailment between prime open sets in the Scott topology of a domain. We investigate in what ways this notion obeys the so-called laws of cautious monotony and cautious cut, proposed by Gabbay, Kraus, Lehmann, and Magidor. Our notion of nonmonotonic entailment does not necessarily satisfy cautious monotony, but does satisfy cautious cut. In fact, we show that any reasonable notion of nonmonotonic entailment on prime opens over a Scott domain, satisfying in particular the law of cautious cut, can be concretely represented using our notion of default entailment.

We also give a variety of sufficient conditions for defaults to induce cumulative entailments, those satisfying cautious monotony. In particular, we show that defaults with unique extensions are a representation of cumulative nonmonotonic entailment. Furthermore, a simple characterization is given for those default sets which determine unique extensions in coherent domains. Finally, a characterization is given for Scott domains in which default entailment must be cumulative. This is the class of daisy domains; it is shown to be cartesian closed, a purely domain-theoretic result.

1This research was partially supported by a Faculty Grant from the University of Georgia Research Foundation.

1 Introduction

Why should the topic of domain theory have any connection with default reasoning, as commonly understood in artificial intelligence? Our basic observation is that partial information is a fundamental concept shared by both areas. Essentially, domain theory is about partial information: elements of domains are partial objects, and total objects can be approximated by increasingly better approximations. Nonmonotonic reasoning, on the other hand, is also about partial information, though traditionally in AI it has been represented either disjunctively in theories, or model-theoretically by means of large structures of total models. There is growing awareness in AI of the importance of the idea: see, for example, the book on the topic [6]. Our contribution in this respect is merely a new technical tool. In particular, though, it focuses on the concept of observability as the kind of property from which we can jump to new conclusions.

Domain theory has provided quite a lot of insight into structures of partial information. So, in addition to the ideas from AI which provide some new techniques for the study of general nonmonotonic phenomena in domains, we hope that, eventually, domain-theoretic insights can help resolve some of the anomalies which seem to plague default reasoning in AI. We are, however, not claiming that domain theory can be so applied without much work. Traditionally, domain theory deals mostly with monotonic, continuous functions. The challenges seem to be to find the right interface between nonmonotonic reasoning and domain theory, and to develop a basic theory on a special class of nonmonotonic functions.

1.1 Nonmonotonic reasoning

Your friend’s flight is scheduled to arrive at 12 noon. So you left home around 10:30 am to meet him at the airport. At the airport, you are told that the flight has been delayed and it will be arriving at 1 pm instead.

This is a typical scenario considered in common sense (prototypical) reasoning in Artificial Intelligence. A key property in common sense reasoning is that the conclusions made are only tentative (such as “arriving on time”), and may be defeated in light of new information. Because of this, the reasoning involved is called nonmonotonic. If we let S stand for “scheduled to arrive at noon”, A for “does arrive at noon”, and D for “delayed”, then A follows nonmonotonically from S, but not from S and D. Intuitively, weakening fails.

Developing formal systems that capture this process turns out to be extremely interesting and challenging. In AI there has been more than a decade’s work in this area. Some notable approaches include McCarthy’s circumscription [9], Reiter’s default logic [12], and McDermott and Doyle’s autoepistemic logic [10]. A great deal is now known about these logics, though there are well-known problems with each of the approaches. Take Reiter’s default logic, for example. This is an augmentation of first order logic with extended rules called defaults. Extensions are a basic notion in default logic because these stand for sets of conclusions made using “common sense assumptions” embodied in the default rules. However, the following properties are often considered undesirable:

• There can be multiple extensions.

• Extensions may not exist.

• Even when they do exist, it can be too costly or impossible to find them.

• Default logic does not support the familiar principle of reasoning by cases [2, 8].

• Standard entailment in default logic fails to have the so-called cumulativity property [4].

A possible reason why the current approaches to nonmonotonic reasoning may be that the approaches presume the syntax and the total model theory used in classical first order logic 2. This presents a fundamental mismatch between the theoretical tool on the one hand, and the phenomena we want to describe on the other. The basic view of classical logic is total: every issue is settled as either true or false, and truth values never change. In commonsense reasoning, our conclusions cannot be supported by proofs in the mathematical sense, and we need to take action in situations of partial information. The only place such information resides, in traditional default logic, is in the incompleteness of default theories. But it seems that the lack of information about an airplane’s arrival time is not well captured by several incomplete scientific theories of its particular flight. Instead, we propose to use defaults to complete this particular scenario by adding conjunctive atomic “facts” which are coherent with constraints on any total picture. We then reason about such extended pictures with traditional logics adapted for partial models. So instead of having several default theories (traditional extensions), we will have one default theory of this model: that theory which contains all sentences observably true in the model-theoretic extensions of the incomplete picture.

Default model theory (DMT), as developed in [15, 16, 18, 14, 13], results from a marriage of domain theory with techniques from default logic. We summarize some of its key ideas.

• Reiter’s default rules can be regarded as semantic, not syntactic notions. In default logic, systems of defaults are interpreted proof-theoretically. In default model theory, systems of defaults are used to build partial models.

• We have generalized Scott’s information systems to the setting of default reasoning. The notion of a “base theory” in default logic is replaced by the notion of a “base situation”, or partial world. The notion of “extension” is retained, but now refers not to a collection of theories, but to a collection of situations, each containing more information than the base situation.

• To reason about what happens in a base situation and its extensions, we have introduced several modal logics. All of them involve a modal operator B for belief. Bφ holds in a given situation s iff φ holds in all extensions of s. Since the notion of validity in a model is primitive in our treatment, the modal logics are semantics based.

2Of course, probabilistic tools can and have been used for this purpose. But in many cases, probability distributions and/or statistical information is unavailable.

Here is how DMT gets around, for example, the problem of multiple extensions. When extensions are regarded as partial (possible) worlds,the extension relation is similar to the accessibility relation in Kripke structures A default rule functions here not as an extended proof rule, but as part of a constructive procedure for building an agent’s preferred worlds extending the current one. There can be many different worlds reachable from the current world. So the possibility of multiple extensions becomes a feature, not a bug – Kripke structures would be rather uninteresting if there were only one world accessible from the current one.

When defaults are regarded as a constructive method for building worlds, we can investigate different model building procedures. Reiter’s extension operator, when phrased modeltheoretically, remains one of the key “algorithms” for building preferred worlds. However, extensions may not exist in some reasonable cases. To cope with this, we have introduced the notion of a “dilation”, a robust generalization of the notion of an extension. Dilations exist in all reasonable cases.

Finally, we need to stress the analogy between default systems and programs. In domain theory, the meaning or behavior of a program is interpreted as an element of a domain (traditionally a Scott domain.) Our observation is that one can also interpret a system of defaults in this behavioral way; as being a kind of user-specified “program” whose meaning is not a given domain element, but a nondeterministic and nonmonotonic way of extending such an element.

1.2 Nonmonotonic entailment

The basic notion underlying a standard logic is that of an entailment. Traditionally, we say a (finite) set of formulas Σ entails a formula ψ if every model of Σ is a model of ψ. A basic property of this entailment is monotonicity: if Σ entails ψ and Σ ⊆ Σ′, then Σ′ entails ψ.

In the nonmonotonic case, what kind of entailment is appropriate? A considerable amount of work has been devoted to this basic question since the work of Gabbay [3]. Because there is no widely accepted model theory for nonmonotonic entailment, most other work does not follow the tradition in standard Tarskian logic: postulates about properties of nonmonotonic entailment come first, models next. However, the justification and consequences of the various postulates are not understood to the extent we would like. Another approach, as taken in this paper, is to start from a model theory and let the models guide our way, in the tradition of Tarskian logic. We use the class of default models, which appears in this paper as a class of default domains and extensions.

The usual interpretation of X ⇝ a (where ⇝ stands for the nonmonotonic entailment relation) is that from the information X we can jump to the conclusion a. Many authors, in particular Kraus, Lehmann, and Magidor [7], have considered Gabbay’s axiom of cautious monotony:

X ⇝ a & X ⇝ b ⇒ X, a ⇝ b.

Reasoning with the assumption of this law, together with some other routine axioms, is sometimes called cumulative reasoning. We have found, however, that cumulativity fails given our logical setting. (Examples in the last section.) One cause of this failure is that disjunction can be used in the setting where pieces of information have propositional structure. This may lead us to believe that a similar failure would not occur without disjunctions; but we have found that even this is not true. Much of the paper is concerned with ways to get around this problem.

1.3 Contributions of the paper

We introduce the basic concept of defaults in Scott domains and show some basic properties related to extensions in Section 2. In Section 3, after a detailed discussion of some useful axioms related to abstract nonmonotonic entailment, we show that default domains are a concrete representation of these nonmonotonic entailments. In Section 4 we provide a variety of sufficient conditions for defaults to induce cumulative entailments, those satisfy cautious monotony. In particular, we show that defaults with unique extensions are a representation of cumulative nonmonotonic entailment. Furthermore, we obtain a simple characterization for those default sets which determine unique extensions in coherent domains (they are different from coherent spaces!). In Section 5, we give a characterization of those Scott domains which guarantee cumulativity no matter what default sets are used. We show that those domains can be made into a cartesian closed category. Finally, nonmonotonic entailment is extended to general Scott open sets, and several results for this case are provided.

2 Defaults in domain theory

Originally, default model theory was based on default information structures, augmenting a concrete representation of Scott domains called information systems [17]. In accordance with the cpo-theoretic tradition of domain theory, we present a version of default model theory based directly on Scott domains (note that the use of Scott domains is purely for simplicity; we expect many results presented here to generalize to other classes of domains).

Recall that a Scott domain (D, ⊑) is a complete partial order (cpo) which is consistently complete: every bounded set has a least upper bound. The set of compact elements of a cpo D is written as κ(D).

Definition 2.1 Let (D, ⊑) be a Scott domain. A default set is a subset Λ of κ(D) × κ(D).

We call a pair (a, b) ∈ Λ a default and think of it as a rule \frac{a : b}{b}.

In the rest of the paper, we informally call a triple (D, ⊑, Λ) a default domain. A rule

like \frac{a : b}{b} intuitively means that if a is current and b is compatible, then b can be added to the information state. Of course this is very vague, and indeed there are several different ways to make this intuition precise. However, the general sense is that if Λ is the default set, and x is an element in D, then we can use Λ to get to an element y ⊒ x, containing more information than x. Therefore, from an abstract point of view, a default set in a Scott domain (D, ⊑) serves to generate a certain relation R on D which at least satisfies the property that (x, y) ∈ R implies x ⊑ y. However, at this point default sets are low level objects which do not have internal structure.

Perhaps the most important kind of relation generated from a default set is that of an extension, due to Reiter [12].

Definition 2.2 Let (D, ⊑) be a Scott domain. Let Λ be a default set in D. Write xΥy for x, y ∈ D if

y = ⨆_{i≥0} ϕ(x, y, i),

where ϕ(x, y, 0) = x, and

ϕ(x, y, i + 1) = ϕ(x, y, i) ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ ϕ(x, y, i) & b ↑ y}

for all i ≥ 0. When xΥy, we call y an extension of x.

Here is an example to illustrate the basic idea of the definition.

Example. Consider the scenario of finding out somebody’s last name if we have the partial information that the name starts with ’sm’. Although we only have partial information, it would be a good guess if we say that the last name is ’smith’. Thus, the pair (sm, smith) is a good candidate of a default rule (although smyth would be an exception).

To be more specific, let’s consider the cpo of the complete binary tree, where the elements are labeled by binary strings of finite and infinite length, so that w ⊑ v if and only if w is a prefix of v. Let the default set be

Λ := {(w11, w111) | w is a finite binary string}.

Intuitively, the defaults say that if we see two consecutive 1’s, then mostly likely we will see another 1. The following are the typical pairs in the extension relation:

(1111, 11111), (1101, 1101), (1^{ω}, 1^{ω}).
□

Clearly, if Λ is empty or the identity relation, then the extension relation is the identity relation. Also, for maximal elements m, like 1^{ω} above, we always have m Υ m. This matches our intuition: if we already have perfect information about some object, defaults can tell us nothing more about the object.

Note that although an extension is a certain fixed point, the definition only provides a way to confirm one rather than to find one. An extension seems to build up in stages, but at each step certain consistency with the extension must be checked. This is anomalous: to construct an extension, we must already know it! It is also this phenomenon that makes the extension relation nonmonotonic: if y is an extension of x and x′ ⊒ x, then y need not be an extension of x′.

Do extensions always exist? What kind of properties does the extension relation have? Before answering these questions, we present a characterization of extensions. It generalizes an early result of Reiter’s.

Theorem 2.1 For a Scott domain (D, ⊑) and a subset Λ ⊆ κ(D) × κ(D), we have xΥy if and only if

y = { t | t = x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ t & b ↑ y} }.

This theorem suggests that extensions can be characterized as a nesting of least fixed point and greatest fixed point. For a fixed domain D and default Λ, let

\begin{matrix}ξ(x, u, v) = x ⊔ ⨆\{b | (a, b) ∈ Λ & a ⊑ u & b ↑ v\}, \\ η(x, v) = \{ t | t = ξ(x, t, v) \}. \end{matrix}

It is easy to check that for fixed x and v, ξ(x, u, v) is a continuous function in u (we need to use the fact that the first components of Λ are all compact). Therefore, ξ(x, u, v) has a least fixed point l, such that ξ(x, l, v) = l. However, η(x, v) is the greatest lower bound of all fixed points of ξ(x, u, v) in u. This implies that

ξ(x, η(x, v), v) = η(x, v).

Hence, by the previous theorem, finding an extension is equivalent to finding a fixed point of η(x, v) in v, so that

ξ(x, η(x, v), v) = η(x, v) = v.

Proof. We prove a stronger result: for any y,

⨆_{i≥0} ϕ(x, y, i) = {t | t = x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ t & b ↑ y}}.

We first show that

⨆_{i≥0} ϕ(x, y, i) ⊑ {t | t = x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ t & b ↑ y}}.

This is done by mathematical induction on i, to show that whenever

t = x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ t & b ↑ y},

we have ϕ(x, y, i) ⊑ t for all i. Clearly

ϕ(x, y, 0) ⊑ t.

Suppose

ϕ(x, y, i) ⊑ t.

It is enough to show that

⨆{b | (a, b) ∈ Λ & a ⊑ ϕ(x, y, i) & b ↑ y}
⊑ x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ t & b ↑ y}.

But this is clear from the assumption that ϕ(x, y, i) ⊑ t.

We now show that

⨆_{i≥0} ϕ(x, y, i) ⊒ {t | t = x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ t & b ↑ y}}.

This is done by demonstrating that ⨆_{i≥0} ϕ(x, y, i) is one of the t’s, that is,

⨆_{i≥0} ϕ(x, y, i) = x ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ ⨆_{i≥0} ϕ(x, y, i) & b ↑ y}.

However, the above follows from the fact that a’s are isolated elements and

{ϕ(x, y, i) | i ≥ 0}

is an ω-increasing chain.

□

The following theorem summarizes some important properties of extensions for default domains.

Theorem 2.2 Given a Scott domain D and a default set Λ, we have:

1. Extensions always exist.

2. If xΥy then y ⊒ x.

3. xΥy and yΥz if and only if y = z.

4. If xΥy and xΥy′, then either y = y′ or y ↑̸ y′.

5. If xΥz and y ⊑ z, then (x ⊔ y) Υ z.

Proof. The original proofs for these, in terms of information systems, are given in [15]. Because some results of this paper crucially depend on item 5, we give a proof for it in the order-theoretic setting.

Suppose xΥz, which means that

z = ⨆_{i∈ω} ϕ(x, z, i).

We prove by mathematical induction that

z = ⨆_{i∈ω} ϕ(x ⊔ y, z, i).

⊑: Clearly ϕ(x ⊔ y, z, 0) ⊑ z by the assumption y ⊑ z. Suppose ϕ(x ⊔ y, z, i) ⊑ z. Then

ϕ(x ⊔ y, z, i + 1)
= ϕ(x ⊔ y, z, i) ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ ϕ(x ⊔ y, z, i) & b ↑ z}
⊑ ϕ(x ⊔ y, z, i) ⊔ ⨆{b | (a, b) ∈ Λ & x ⊑ z & b ↑ z}
⊑ z,

where the last step follows from Theorem 2.1. Therefore, ϕ(x ⊔ y, z i) ⊑ z for every i ≥ 0. ⊒: Obviously ϕ(x ⊔ y, z, 0) ⊒ ϕ(x, z, 0). Assume ϕ(x ⊔ y, z, i) ⊒ ϕ(x, z, i). Then

ϕ(x ⊔ y, z, i + 1)
= ϕ(x ⊔ y, z, i) ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ ϕ(x ⊔ y, z, i) & b ↑ z}
⊒ ϕ(x, z, i) ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ ϕ(x, z, i) & b ↑ z}
= ϕ(x, z, i + 1).

Therefore ϕ(x ⊔ y, z, i) ⊒ ϕ(x, z, i) for every i ≥ 0.

□

Remember that a default set in a Scott domain is just a set of pairs of compact elements. However, the basic idea of a default rule is to let an agent to ”jump to a certain conclusion”. This means not all defaults makes sense, and certain forms of defaults may be useless. We are concerned in the remainder of this section about removing ”useless” defaults and establish certain ‘normal forms’ for defaults.

Definition 2.3 Let Λ, Λ′ be default sets in a Scott domain (D, ⊑). We say that Λ and Λ′ are equivalent if they determine the same extension relation.

This first kind of useless defaults are those of the form (a, b), where a is incompatible with b. The fact that we can safely remove them is confirmed in the following theorem, whose easy proof is omitted.

Proposition 2.1 Let (D, ⊑, Λ) be a default domain. Then Λ and Λ′ are equivalent, where

Λ′ := {(a, b) | (a, b) ∈ Λ & a ↑ b}.

The second kind of useless defaults are those (a′, b)s where some (a, b) is already in Λ with a ⊑ a′. These defaults can also be removed.

Proposition 2.2 Let (D, ⊑, Λ) be a default domain and let (D, ⊑) be finitary, i.e., each compact element dominates only finitely many compact elements. Then Λ and Λ′ are equivalent, where

Λ′ := Λ − {(a′, b) | (a′, b) ∈ Λ & (a, b) ∈ Λ for some a below a′}.

The proof is straightforward: we can use (a, b) everywhere (a′, b) is used for constructing an extension. However, note that the finitary condition on D is important here. Otherwise one could potentially remove all the pairs in Λ.

Keeping in mind that the role of a default is to increase (hypothetical) information, we can further require that if (a, b) ∈ Λ, then a ⊑ b.

Proposition 2.3 Let (D, ⊑, Λ) be a default domain. Then Λ is equivalent to some Λ′ with the property that

(a, b) ∈ Λ′ ⇒ a ⊑ b.

To get Λ′, we simply replace each (a, b) in Λ by (a, a ⊔ b) and remove those (a, b)’s where a and b are incompatible. According to the definition of an extension, we can see that Λ′ and Λ are equivalent. In the rest of the paper, we only consider defaults of the form (a, b) with a ⊑ b, although this restriction is not crucial in many cases.

3 Abstract nonmonotonic entailment

The purpose of this section is to introduce an abstract notion of a nonmonotonic entailment in a Scott domain and to show that default domains are representations of such entailments. Our axioms for the abstract nonmonotonic entailment is then justified semantically in the default domains.

Entailments, in general, should work at the level of logical statements. In the domain logic paradigm [1, 19], the correspondence goes from domains to types, open sets to properties, and points to computations. So, strictly speaking, entailments should be at the level of Scott open sets. However, we would like to gain a better understanding of the basic cases before going to a full fledged propositional version. For this reason, we consider nonmonotonic entailment between prime open sets of the form ↑ x first, where x range over compact elements of the domain. As a further reduction of the overhead, we simply work on an entailment between compact elements.

In the study of nonmonotonic consequences, the following axioms are often considered. (By standard practice, X ⇝ Y is an abbreviation for ∀b ∈ Y X ⇝ b.)

Identity: a ∈ X ⇒ X ⇝ a.
Cautious monotony: X ⇝ a & X ⇝ b ⇒ X, a ⇝ b.
Cut: X ⇝ T & T, Y ⇝ b ⇒ X, Y ⇝ b.
Cautious cut: X ⇝ T & T, X ⇝ b ⇒ X ⇝ b.

For these axioms, X and Y range over finite sets of formulas, and a and b are single formulas.

Although Cut and Cautious cut are equivalent with the assumption of monotonicity, Cautious cut is strictly weaker without monotonicity.

In our domain-theoretic setting, we wish to generalize axioms like the above, but now finite sets of formulas will be replaced by compact elements in a Scott domain. To this end we introduce the notion of an abstract nonmonotonic entailment in a Scott domain.

Definition 3.1 Let (D, ⊑) be a Scott domain. We call (D, ⊑, ⇝) an abstract nonmonotonic entailment if ⇝ is a relation on κ(D) which satisfies the following requirements.

• Reflexivity: a ⇝ a for all compact a;

• Right Weakening: if a ⇝ b and c ⊑ b with c compact, then a ⇝ c;

• Consistency: if a ⇝ b then a ↑ b;

• Right Conjunction: If F is a finite subset of κ(D) and a ⇝ b for all b ∈ F then a ⇝ ⨆ F (note that in particular F is consistent);

• Cautious cut: If a ⇝ b and (a ⊔ b) ⇝ c then a ⇝ c.

One special instance, for example, of an abstract nonmonotonic entailment is (D, ⊑, ⊒). As the name suggests, monotonicity, which states that if a ⇝ b and a′ ⊒ a, then a′ ⇝ b, does not hold in general for a nonmonotonic entailment.

Note that Reflexivity and Right Weakening implies what Gärdenfors and Makinson [4] call the axiom of Supraclassicality:

a ⊑ b ⇒ b ⇝ a.

Supraclassicality means that nonmonotonic entailment includes all classical entailment as special instances.

The first four axioms for nonmonotonic entailment are self-explanatory. We explain the axiom of Cautious cut in more detail. In the literature there are at least two additional versions of cut rules, which appear in the following forms under the current context:

• Cut: if a ⇝ b and b ⊔ b′ ⇝ c, then a ⊔ b′ ⇝ c.

• Cut’: if a ⇝ b and b ⇝ c, then a ⇝ c.

Assuming monotonicity, we have the following.

Cut’ ⇒ Cut: If a ⇝ b and b ⊔ b′ ⇝ c, then, by monotonicity, we have a ⊔ b′ ⇝ b ⊔ b′. Now applying Cut’, we have a ⊔ b′ ⇝ c.

Cut ⇒ Cautious cut: This follows without using monotonicity.

Cautious cut ⇒ Cut’: Suppose a ⇝ b and b ⇝ c. Then a ⊔ b ⇝ c, by monotonicity. So a ⇝ c follows from Cautious cut.

To summarize, the three different versions of cut are equivalent under the assumption of monotonicity. Without monotonicity, however, Cautious cut is strictly weaker than either of the other two cut rules. Here, it is informative to note that Supraclassicality and Cut’ together imply monotonicity. Therefore, for an abstract nonmonotonic entailment, Cut and Cut’ are equivalent, and either of them implies monotonicity.

Also note the interesting connections with the general inference rules for linear logic. The cut rule, which expresses the categorical concept of composition, here is replaced with a natural rule one would expect without weakening. But so far our system bears only a superficial resemblance to linear logic; much more work is needed to determine any precise relations.

We now show that a default domain (D, ⊑, Λ) induces an abstract nonmonotonic entailment relation, via extensions.

Given a default domain, we define a relation ⇝_{Λ} by letting a ⇝_{Λ} b if

∀y [aΥy ⇒ b ⊑ y],

where Υ is the extension relation for Λ.

Theorem 3.1 Let (D, ⊑, Λ) be a default domain. Define the triple (D, ⊑, ⇝_{Λ}), with a ⇝_{Λ} b iff a, b ∈ κ(D) and

∀y [aΥy ⇒ b ⊑ y].

Then (D, ⊑, ⇝_{Λ}) is an abstract nonmonotonic entailment.

Proof. Reflexivity, Right Weakening, Consistency, and Right Conjunction follow routinely from the definitions. For Cautious cut, use item 5 of Theorem 2.2.

□

What is unexpected is that the converse of the above theorem is also true. Every abstract nonmonotonic entailment is faithfully recaptured by some default domain.

Theorem 3.2 Let (D, ⊑, ⇝) be an abstract nonmonotonic entailment. There is a default domain (D′, ⊑′, Λ) with (D, ⊑) a subdomain of (D′, ⊑′), such that

a ⇝ b iff a ⇝_{Λ} b

for a, b ∈ κ(D).

To describe the construction needed in the proof, we introduce an auxiliary notion called the nonmonotonic consequence bound, which is defined as:

ã := ⨆{b | a ⇝ b}.

Nonmonotonic consequence bound always exist because from the axioms of an abstract nonmonotonic entailment, it is easy to check that the set {b | a ⇝ b} is directed.

We now describe the construction. Start with an abstract nonmonotonic entailment (D, ⊑, ⇝). We construct a default domain (D′, ⊑′, Λ), where

• D′ = D ∪ {x̂ | x ∈ D}, with x̂’s the new elements added to D in such a way that x̂ is the unique maximal immediately above x.

• Λ = {(a, ˆ ã) | a ∈ κ(D)}.

Several remarks are in order. First, notice that all the new elements are compact. So, although ã need not be compact, ˆ ã always is, for compact a. This makes the set Λ a legitimate candidate for a default set. Secondly, all the new elements are incompatible with each other, and the only elements in D which are compatible with x̂ are in the set ↓ x. Thirdly, D is clearly a subdomain of D′, in whatever reasonable sense one could make out of the word ‘subdomain’ (retract, embedding projection pairs, etc).

The following picture helps us to visualize this construction. The domain D′ looks like a new domain with lots of “hair” growing out of the old D.

[figure: D; a; ã; â]

The proof that the above construction works for arbitrary default domains is achieved via several lemmas.

Lemma 3.1 Let (D, ⊑, ⇝) be an abstract nonmonotonic entailment. For any element a ∈ κ(D), we have

{b̃ | b ∈ κ(D) & b ⊑ a ⊑ b̃} = ã.

Proof. We clearly have a ⊑ a ⊑ ã. Therefore,

{b̃ | b ∈ κ(D) & b ⊑ a ⊑ b̃} ⊑ ã.

On the other hand, suppose b ⊑ a ⊑ b̃. By Right Conjunction, {x | b ⇝ x} is a directed set whose least upper bound is b̃. Since a ∈ κ(D), we have a ⊑ b_{0} for some b_{0} such that b ⇝ b_{0}. This implies, by Right Weakening, b ⇝ a. For any x ∈ D, if a ⇝ x then a ⊔ b ⇝ x, as b ⊑ a. Therefore, b ⇝ x, by applying Cautious cut. This proves ã ⊑ b̃. Hence,

{b̃ | b ∈ κ(D) & b ⊑ a ⊑ b̃} ⊒ ã.
□

Lemma 3.2 Given a, b ∈ κ(D), suppose that b ⊑ a ⊑ b̃. Then aΥˆb̃ in (D′, ⊑′, Λ).

Proof. This is because (b, ˆ b̃) is a member of Λ, and from the given assumption we have

a ⊑ b̃ ⊑ ˆ b̃.

So, aΥˆb̃ since ˆ b̃ is a maximal element.

□

The previous lemma shows that if b ⊑ a ⊑ b̃, then ˆ b̃ is an extension of a. The next lemma shows that all extensions of a are of this form.

Lemma 3.3 Fix a ∈ κ(D). Every extension of a is of the form ˆ b̃ with

b ∈ κ(D) and b ⊑ a ⊑ b̃.

Proof. Clearly every extension of a must be some ˆ b̃, because of the special kind of pairs of elements in Λ. We have to explain why such bs must have the properties mentioned in the lemma. It is easy to see that we have b ⊑ a; But we must also have a ⊑ b̃, because otherwise a and ˆ b̃ will be incompatible.

□

These lemmas lead to the proof for Theorem 3.2, as follows.

Proof: Let (D, ⊑, ⇝) be an abstract nonmonotonic entailment, and let the default domain (D′, ⊑′, Λ) be the one described earlier.

Suppose a ⇝ b, and suppose y is an extension of a in D′. By the previous lemma, y = ˆ x̃ for some x ∈ κ(D) such that

x ⊑ a ⊑ x̃.

However, by Lemma 3.1, we have ã ⊑ x̃. Hence,

b ⊑ ã ⊑ x̃ ⊏ y,

which shows that a ⇝_{Λ} b.

On the other hand, suppose a ⇝_{Λ} b for a, b ∈ κ(D). By the previous lemmas again, ˆ ã is an extension for a in D′. Therefore, b ⊑ ˆ ã, which in turn implies that b ⊑ ã since b ∈ D. This means a ⇝ b, by Right Weakening, the directedness of {q | a ⇝ q}, as well as the compactness of b.

□

Extensions are a complicated, non-inductive construction, whose computational cost is very high. Theorem 3.2 tells us that with a proper encoding of the defaults, it is possible to greatly simplify the construction of an extension, at least conceptually, while keeping the nonmonotonic entailment relation unchanged. In fact, for the default set used in the proof of Theorem 3.2, only one single ‘application’ of the default rules is sufficient for us to obtain an extension. Moreover, each extension is nothing more than a certain kind of nonmonotonic bound.

However, although Theorem 3.2 is of significant conceptual value, there are at least two potential obstacles that may keep it from being directly applicable in implementation. One is that, in the construction of the default set Λ, we used pairs like (a, ˆ ã), where ã need not be a compact element. So, the construction of D′ may transform a finitary domain D (in the sense that any compact element dominate only finitely many elements) to a non-finitary domain. This means that although ˆ ã is compact, it may be required to code an ‘infinite amount’ of information.

Is there a different construction, which avoids this problem, but still faithfully captures the nonmonotonic entailment? This is, surprisingly, indeed possible, although the construction is slightly more complicated, and we need to iterate the application of defaults twice to get to an extension. We are not going to present that construction here, but only refer the reader to [18].

The other issue is: what kind of domains are already good enough so we do not need to ‘grow the hair’ out of them, as we did to get D′ from D? This is important because if we go back and forth a couple of times, between ⇝ and Λ, we don’t want the domain to grow arbitrary large. It is necessary to have somewhere to stop: i.e. a fixed point where no further maximal elements need to be added to the domain.

These domains turn out to be just like the ones constructed earlier: they are called hairy domains. Intuitively, a hairy domain is one with enough maximal elements–at least as many maximals as non-maximals.

Definition 3.2 Let (D, ⊑) be a Scott domain. This domain is called hairy, if for each a ∈ D, if a is not a compact maximal element, then there is a compact maximal element m_{a} ∈ D such that

∀x ∈ D [x ⊏ m_{a} ⇒ x ⊑ a].

In other words, a is the element immediately below the maximal element m_{a}.

Note that many familiar domains are hairy: the one-point cpo, the truth value cpo, the integer cpo, and so on. Of course, there exist domains which are not hairy, such as the diamond shaped cpo.

Proposition 3.1 Let (D, ⊑, ⇝) be an abstract nonmonotonic entailment and (D, ⊑) a hairy Scott domain. Then there is a default set Λ such that the nonmonotonic entailment determined by the default domain (D, ⊑, Λ) is the same as ⇝.

We omit the proof similar to that of Theorem 3.2, but indicate the default set needed:

Λ := {(a, ˆ ã) | a ∈ κ(D)},

where x̂ = x if x is a maximal and x̂ = m_{x} if x is a non-maximal. Here, m_{x} is a maximal element immediately above x.

4 Cumulativity

Let (D, ⊑, ⇝) be an abstract nonmonotonic entailment on a Scott domain D. The relation ⇝ is said to be cumulative if it satisfies the axiom of cautious monotony:

a ⇝ b & a ⇝ c ⇒ a ⊔ b ⇝ c.

Intuitively, cautious monotony says that if from a one expects both b and c, then one should still expect c if b becomes current.

Cautious monotony is a nice property to have because it makes the nonmonotonic entailment cumulative: if from a one expects many things, and if nothing unexpected happens, then none of the expected needs to be withdrawn.

Since Gabbay [3], a considerable amount of work has been devoted to the study of cumulativity. As mentioned earlier, our work here differs from other work in the following fundamental way: the other work assumes cautious monotony, and then searches for models having this property. Although models which capture cautious monotony do exist, they appear to be somewhat artificial. Our starting point is, in contrast, the idea of defaults as used in default logic, seemingly unrelated to cautious monotony. Does the nonmonotonic entailment relation ⇝_{Λ} derived from a default domain (D, ⊑, Λ) satisfy cautious monotony? The next example shows that it does not have to.

Example. Consider the default set

{(a, b), (a′, b′)}

on the following Scott domain.

[figure: b′; a′; b; a]

We have a ⇝ b, from which it follows that a ⇝ a′. However, we do not have a ⊔ a′ ⇝ b because a ⊔ a′ = a′, and there are two incompatible extensions for a′, i.e., b and b′.

□

It can also be seen from the above example that cumulativity is fragile for Λ with respect to set inclusion. For example, if we add to Λ a pair (a, b′), or remove from it the pair (a′, b′), the induced relation ⇝ becomes cumulative.

The question now is: what kind of a default set induces a cumulative entailment relation? In the subsections to follow, we provide various useful characterizations for cumulativity.

4.1 Cumulativity and nonmonotonic closure

In ordinary logic, there is a useful notion called deductive closure of a set of formulae, defined as {b | X ⊢ b}. We have, in the nonmonotonic case, also used a certain nonmonotonic closure operator, defined as ã := ⨆{b | a ⇝ b}. For convenience, we still call a closure operator although it need not have the property that ã = ˜ ã.

The next theorem shows that cumulativity amounts to equality between nonmonotonic closures of certain elements.

Theorem 4.1 Let (D, ⊑, ⇝) be a nonmonotonic entailment. Then ⇝ is cumulative if and only if the following condition holds for the nonmonotonic closure:

(a ⊑ b ⊑ ã) ⇒ ã = b̃.

Note that we get b̃ ⊑ ã for free from Lemma 3.1. So the above theorem says that cumulativity is equivalent to

(a ⊑ b ⊑ ã) ⇒ ã ⊑ b̃.

Proof. Only if: Suppose ⇝ satisfies the axiom of cautious monotony, and suppose a ⊑ b ⊑ ã. We know from the condition b ⊑ ã that a ⇝ b. If a ⇝ x, then a ⊔ b ⇝ x, by cautious monotony. However, a ⊔ b = b, so b ⇝ x. This means ã ⊑ b̃.

If: On the other hand, suppose

(a ⊑ b ⊑ ã) ⇒ ã ⊑ b̃

for compact elements a, b ∈ D. If x ⇝ y and x ⇝ z, then

x ⊑ x ⊔ y ⊑ x̃.

Therefore, x̃ ⊑ x̃ ⊔ y by assumption. Now, x ⇝ z implies z ⊑ x̃. Hence x ⊔ y ⇝ z.

□

Note that although this theorem is a characterization of cumulativity, it is not very helpful for deciding cumulativity from a default set directly.

4.2 Deterministic defaults

Let (D, ⊑, Λ) be a default domain. We call Λ a deterministic default set if

• [(a, b), (a′, b′) ∈ Λ & a ⊑ a′ ⊑ b] ⇒ a = a′,

• [(a, b), (a′, b′) ∈ Λ & a ↑ a′ & b ↑ b′] ⇒ [a = a′ & b = b′].

The example given earlier for illustrating non-cumulativity is not a deterministic default set. Our next result shows that deterministic default sets induce a cumulative nonmonotonic entailment relation.

Proposition 4.1 Suppose (D, ⊑, Λ) is a default domain with Λ deterministic. Then the nonmonotonic entailment ⇝_{Λ} is cumulative.

The proof becomes very easy once the conditions for determinacy are digested. They ensure that in the process of building any extension for an element x in D, at most one default is ever applicable; further, the inductive construction terminates at stage 1 at the latest. Now suppose x ⇝ y and x ⇝ z. To show that (x ⊔ y) ⇝ z, note that a default rule is applicable to x if and only if it is applicable to x ⊔ y, because at most one default rule is applicable, and (because x ⇝ y) x ⊑ x ⊔ y ⊑ u for any extension u of x. This means x and x ⊔ y have the same extension sets. Therefore, (x ⊔ y) ⇝ z.

4.3 Precondition-free defaults

There is a simple and yet very useful class of defaults considered in the literature, called precondition-free defaults. For a default domain (D, ⊑, Λ), Λ is called precondition-free if for each (a, b) in Λ, a = ⊥.

The next result is the observation that precondition free structures give rise to a nonmonotonic relation supporting cautious monotony.

Lemma 4.1 Let (D, ⊑, Λ) be a default domain, where Λ is precondition-free. Then y is an extension of x if and only if there is a subset B of π_{2}Λ (where π_{2} is the projection to the second coordinate) which is

• maximal with the property that x is compatible with B, and

• y = x ⊔ ⨆ B.

The proof is straightforward from definition, but Lemma 4.1 is the key to the following theorem.

Theorem 4.2 Suppose (D, ⊑, Λ) is a precondition-free default domain. Define the triple

(D, ⊑, ⇝),

with a ⇝ b if a, b ∈ κ(D) and

∀y.[aΥy ⇒ b ⊑ y].

Then ⇝ is a cumulative entailment on (D, ⊑).

Proof . Let x ⇝ y and x ⇝ z. We want x ⊔ y ⇝ z. Suppose that t is an extension of x ⊔ y. Then by the previous lemma, there is a maximal subset B of π_{2}Λ compatible with x ⊔ y, such that t = x ⊔ y ⊔ ⨆ B. We want to show that z ⊑ u. It suffices to show that x ⊔ ⨆ B is an extension of x. If x ⊔ ⨆ B is not an extension of x, it is because B is not maximal in the sense of Lemma 4.1. That is, there is some maximal C, a proper superset of B, compatible with x, and such that w = x ⊔ ⨆ C is an extension of x. By hypothesis, y ⊑ w, and we already have x ⊑ w. So C is a larger set than B, but compatible with x ⊔ y, violating the maximality of B. This contradiction proves that t is an extension of x. Thus z ⊑ t, as desired.

□

4.4 Unique extensions and cumulativity

It turns out that cumulativity is closely related to the uniqueness of extensions. In fact, uniqueness of extensions characterize cumulativity: If there exists only one extension for every x ∈ D, then the induced entailment from extension is cumulative, and moreover, each cumulative entailment is determined by a default set which produces unique extensions. This is stated precisely in the following representation result.

Theorem 4.3 Suppose (D, ⊑, Λ) is a default domain for which extensions are unique. Then the induced nonmonotonic entailment ⇝ is cumulative. If, on the other hand, (D, ⊑, ⇝) is a cumulative entailment, then there exists a default domain which induces ⇝ in the sense of Theorem 4.4; moreover, extensions are unique in this default domain.

Proof. The first statement follows from item 5 of Theorem 2.2 and the unique extension property.

The second statement follows from the proof of the representation theorem– Theorem 3.2, and Theorem 4.1.

□

To check that the induced nonmonotonic entailment for a default domain (D, ⊑, Λ) is cumulative, it is sufficient to show that extensions are unique. However, it is clear that we need an effective procedure for determining when a default set determines unique extensions, because the definition for extensions is not helpful. In the rest of this section we present a characterization result for this purpose.

In [18] an effective, sufficient condition is given for unique extensions. However, that condition is not necessary. We now give a very simple condition which is both sufficient and necessary for unique extensions on coherent Scott domains (an effective characterization of unique extensions on general Scott domains remains unsolved). Recall that a Scott domain (D, ⊑) is coherent if for every subset X of D, the compatibility of every pair of elements in X implies the compatibility of the whole set X. Note that in the following theorem we assume that if (a, b) is a pair in a default set Λ, then a ⊑ b.

Theorem 4.4 Let Λ be an abstract default set in a coherent Scott domain D. Then extensions are unique for Λ if and only if for every pair (a, b), (a′, b′) in Λ, if a, a′ is compatible (denoted as a ↑ a′), then

[(a ⊔ a′) ↑ b & (a ⊔ a′) ↑ b′] ⇒ b ↑ b′.

To better understand the theorem, we explain why it does not hold for non-coherent Scott domains, and why the condition cannot be replace by a more familiar one, such as

a ↑ a′ ⇒ b ↑ b′.

Answers to both questions can be found in the two examples below.

Example. Consider this typical non-coherent Scott domain.

[figure: x; b_{2}; b_{1}; ⊥]

The default set {(⊥, b_{1}), (⊥, b_{2})} clearly satisfies the condition in the theorem. However, there are two extensions for x.

□

Example. Consider the next Scott domain, which is coherent.

[figure: b_{2}; b_{1}; a_{2}; a_{1}; ⊥]

The default set {(a_{1}, b_{1}), (a_{2}, b_{2})} generates unique extensions in this domain. However, the condition

a ↑ a′ ⇒ b ↑ b′

does not hold.

□

We now go back to the proof of Theorem 4.4. It involves a canonical way for building an extension. Given a default domain (D, ⊑, Λ), extensions can be constructed in the following way for a given element x in D.

Let x_{0} = x. For each i > 0, let x_{i} ∈ D be such that

x_{i} = x_{i−1} ⊔ ⨆{b | (a, b) ∈ Λ & a ⊑ x_{i−1} & b ↑ x_{i}}.

There may exist more than one such x_{i}’s to make the above equality hold. But we only have to make sure that such x_{i} indeed exist. All we need to do is to pick up the least upper bound b of a maximal compatible subset B of

{b | (a, b) ∈ Λ & a ⊑ x_{i−1}}

such that B ↑ {x_{i−1}}, and take x_{i} = x_{i−1} ⊔ b. The existence of such a set B is guaranteed by Zorn’s lemma applied not to the ordering ⊑ but to the inclusion order on subsets having the above properties. It is easy to see that {x_{i} | i ≥ 0} is an increasing chain. Let m := ⨆_{i∈ω} x_{i}. We can show, by mathematical induction, that

m = ⨆_{i∈ω} ϕ(x, m, i),

which means m is an extension of x.

The above procedure tells us that certain extensions can be built up as the least upper bound of an increasing chain of fixed points of some operators. The difficult direction of the proof of the theorem shows that if the domain D is coherent, then every extension, and consequently the only extension, of an element must be built in this way.

Proof of Theorem 4.4. If: We prove that for any x in D, there is a maximum among the subsets B of

{b | (a, b) ∈ Λ & a ⊑ x}

such that {x} ∪ B is compatible. Consider the set

M := {b | (a, b) ∈ Λ & a ⊑ x & x ↑ b}.

For any b_{1}, b_{2} in this set, there are a_{1}, a_{2}, both below x, such that (a_{1}, b_{1}), (a_{2}, b_{2}) are in Λ. Moreover, (a_{1} ⊔ a_{2}) ↑ b_{1}, and (a_{1} ⊔ a_{2}) ↑ b_{2}. Therefore, by the condition given in Theorem 4.4, we have b_{1} ↑ b_{2}. This means, by coherence of D, that M is the largest set among the subsets B of

{b | (a, b) ∈ Λ & a ⊑ x}

such that {x} ∪ B is compatible.

Now we can complete the proof of the If direction. For each d ∈ D let M(d) be the maximal set M constructed in the previous paragraph; this notation just makes clear the dependence of M on d. We want to show that each x has a unique extension. Fix x, and define a sequence m_{0}, m_{1}, … as follows. Put m_{0} = x, and

m_{i+1} = m_{i} ⊔ ⨆ M(m_{i}).

This gives an increasing sequence, and as in the remarks before the proof, the least upper bound m of this sequence is an extension of x. But now let e be any other extension of x; then

e = ⨆ ϕ(i, x, e)

by the definition of extension. By induction, it is straightforward that for each i

ϕ(i, x, e) ⊑ m_{i}.

Therefore e ⊑ m, and it follows by Theorem 2.2(4) that e = m.

Only If: On the other hand, suppose for some (a_{1}, b_{1}), (a_{2}, b_{2}) in Λ such that a_{1} ↑ a_{2} we have (a_{1} ⊔ a_{2}) ↑ b_{1}, and (a_{1} ⊔ a_{2}) ↑ b_{2}. We must have b_{1} ↑ b_{2} for otherwise there are clearly at least two extensions for a_{1} ⊔ a_{2}.

□

5 Daisy domains

In the previous section we have studied various sufficient conditions for a default set to induce a cumulative nonmonotonic entailment. In this section we study cumulativity along a different dimension: the underlying domain.

What kind of Scott domains (D, ⊑) guarantee that when they are coupled with default sets the induced nonmonotonic entailments are always cumulative?

Of course, we must rule out the domain structure presented in the counterexample to cumulativity in the previous section. Luckily enough, that also turns out to be sufficient.

Definition 5.1 A Scott domain (D, ⊑) is daisy if for each x, y ∈ D, we have

x ↑̸ y ⇒ x ⊓ y = ⊥.

As the name suggests, a daisy domain is one which branches out only at the root. Equivalently, a Scott domain is daisy if it is a collection of lattices smashed together at the bottoms. From an aerial perspective the domain looks like a daisy. Clearly, all lattices are daisy domains.

The main theorem of this section is the following.

Theorem 5.1 A Scott domain (D, ⊑) is daisy if and only if for each default set Λ in D, the induced nonmonotonic entailment is cumulative.

The following lemma, whose easy proof is omitted, is used in our proof. This lemma says that if y is an extension of x, and the only extension of t, strictly in between x and y, is y, then the nonmonotonic entailment determined by Υ is cumulative.

Lemma 5.1 Let (D, ⊑, Λ) be a default domain. Then ⇝_{Λ} is cumulative if for each x, y, t, u in D,

[xΥy & (x ⊏ t ⊏ y) & tΥu] ⇒ u = y.

Proof of Theorem 5.1. If: Suppose (D, ⊑) is a Scott domain such that any default set in it induces a cumulative nonmonotonic entailment. Given an incompatible pair of elements x, y in D, clearly x ⊓ y is strictly below both x and y. Let a be any fixed compact element with a ⊑ x ⊓ y. We can find compact elements x_{0}, y_{0} such that x_{0} ⊑ x, y_{0} ⊑ y, x_{0} ↑̸ y_{0}, and, moreover, a ⊑ x_{0} ⊓ y_{0}. Now consider the default set {(⊥, x_{0}), (a, y_{0})}. We know that for this set to induce a cumulative nonmonotonic entailment, a must be the bottom. This shows that any compact element below x ⊓ y is the bottom. Therefore, x ⊓ y itself must be the bottom.

Only if: Consider a default domain (D, ⊑, Λ), where (D, ⊑) is daisy. If y is an extension of x, and x ⊏ t ⊑ y, then the only extension of t is y, since (D, ⊑) is daisy. Here we also need to use the basic fact about extensions mentioned in Theorem 2.2: different extensions for the same element are incompatible. By Lemma 5.1, ⇝_{Λ} is cumulative.

□

Unlike hairy Scott domains, daisy domains have better structural properties: they can be made cartesian closed. We spend the rest of the section showing this result.

To show cartesian closure, we must first be precise about the category we are concerned with. The objects of the category are, of course, daisy domains. The morphisms of the category are super-strict continuous functions.

Definition 5.2 Let D, E be daisy domains. A continuous function f : D → E is called super-strict if

f(x) = ⊥_{E} ⇔ x = ⊥_{D},

unless f itself is the bottom, i.e., it maps everything to the bottom.

It is routine to check that indeed we have a category: super-strict functions compose, and the identities are super-strict.

Finite products and function space can be introduced for daisy domains. Let D, E be daisy domains. For convenience, we use D^{−} to denote the resulting set by removing the bottom from D. The smash product of D and E is the cpo D ×_{⊥} E, whose set of elements is

(D^{−} × E^{−}) ∪ {⊥},

with ⊥ the least element, under the componentwise ordering: (x, y) ⊑ (x′, y′) if and only if x ⊑ x′ and y ⊑ y′.

The super-strict function space of D and E is the cpo D →^{⊥} E, whose set of elements is

[D^{−} → E^{−}] ∪ {λx. ⊥},

where

• D^{−} → E^{−} stands for the collection of continuous functions from D^{−} to E^{−}, but each such function can be regarded as one from D to E, by sending ⊥_{D} to ⊥_{E},

• the ordering is given by f ⊑ g ⇔ ∀x ∈ D.f(x) ⊑ g(x).

Perhaps we should say a word about the notation →^{⊥}. Usually, →_{⊥} is a notation for the strict function space. Our notation clearly makes it ‘super-strict’.

The following result shows that smash product and super-strict function space preserve daisy domains.

Proposition 5.1 If D and E are daisy domains, then so are D ×_{⊥} E and D →^{⊥} E.

Proof. Clearly D ×_{⊥} E and D →^{⊥} E are Scott domains. We need to show that the glb of incompatible elements is the bottom.

For the smash product, let (x, y), (x′, y′) be incompatible elements. Then either x, x′ are incompatible, or y, y′ are incompatible. Since D and E are daisy, either x ⊓ x′ = ⊥_{D}, or y ⊓ y′ = ⊥_{E}. This means the glb of (x, y) and (x′, y′) cannot be any element of the form (a, b), where a and b are non-bottom. So the only possibility for the glb of (x, y) and (x′, y′) is ⊥.

For the super-strict function space, let f, g be incompatible functions. Then there is some non-bottom element x in D, such that f(x) and g(x) are incompatible. As the ordering is pointwise, and lower bound l for f and g must satisfy l(x) ⊑ f(x) ⊓ g(x). Since E is daisy, l(x) = ⊥_{E}. So f ⊓ g = ⊥.

□

Moreover, one can show that D ×_{⊥} E is the product, and the one point domain is the initial object in our category.

Theorem 5.2 (Cartesian closure) For daisy domains D, E and F, we have

Hom(D ×_{⊥} E, F) ≅ Hom(D, [E →^{⊥} F]).

Proof (Sketch). It is enough to show that there is a one-one correspondence between the non-bottom elements of D ×_{⊥} E →^{⊥} F and D →^{⊥} [E →^{⊥} F].

For each non-bottom element f in D ×_{⊥} E →^{⊥} F, we get a continuous function f^{−} in D^{−} × E^{−} → F^{−}, where × and → are standard product and function space constructions. Clearly, f^{−} correspond to a function in D^{−} → [E^{−} → F^{−}] (note that [E →^{⊥} F]^{−} ≅ E^{−} → F^{−}) by the standard currying operation. One can check that this induces a one-one correspondence.

□

Two remarks are in order. One is that although cartesian closure is an important idea in programming semantics, its relevance to default reasoning is unclear. The other remark is that our proof above is apparently related to bottomless cpos. It may be better to work in the framework of bottomless cpos directly and then obtain our result as a corollary; but we have not looked at this.

6 Nonmonotonic entailment on open sets

We now turn to an investigation on extending nonmonotonic entailment to open sets, considered as properties in general, as in the setting of domain logics.

Given two open sets α, β in a Scott domain (D, ⊑), when can we say that α nonmonotonically entails β with respect to a default set Λ? There is a general consensus among researchers in nonmonotonic reasoning that a notion of ‘only knowing’ is needed. One jumps to the conclusion that Tweety flies from the information that Tweety is a bird. However, this reasoning is not valid if the reasoner knows that, in fact, Tweety is a penguin, an additional piece of information he puts aside. Our interpretation of ‘only knowing’ is naturally ‘only having information’ with respect to the background informational ordering of the Scott domain. Only knowing the property α, therefore, translates into the information captured by the minimal points of α, written as μα.

It should be pointed out that the notion of ‘only knowing’ should be a local concept. To be realistic, one always has other knowledge, or information, or even other believes. Nevertheless, one can still conclude that Tweety flies with the additional information that Spot is a puppy. A more precise notion of only knowing should also deal with the notion of ‘independence’, the idea that two pieces of information are not related. This has been discussed in the probabilistic literature (e.g., [11]), but not extensively in the logical literature. All of this may be better treated in a version of first order logic. The present paper, however, takes the simple minded view of ‘only knowing’.

Definition 6.1 Let (D, ⊑, Λ) be a default domain, and let α, β be Scott open sets in (D, ⊑). We say that α nonmonotonically entails β in this default domain if for every minimal point x in α (x ∈ μα), every extension of x is in β.

As pointed out in the introduction, cautious monotony fails for nonmonotonic entailment which involves disjunctive information. For the sake of completeness, we restate the example in pure order-theoretic terms.

Consider the domain

[figure: f; \overline{f}; p; ⊥]

Intuitively we want p to stand for “being a penguin”, and f for “fly”. Choose for a default set

{(⊥, f)}.

Then we have true ⇝ f and true ⇝ f ∨ p, but f ∨ p does not ⇝ f. (For simplicity, we misused notation here.) This example points to a general pattern of reasoning where cautious monotony should intuitively fail.

The next example shows that cautious cut can fail as well. First, add a new atom w to the domain above, and new elements showing that w is consistent both with f and \overline{f}. Let φ be w ∨ \overline{f}, α = w ∨ f, and β = f. Take for default set

{(⊥, f), (⊥, w)}.

The minimal points of φ are w and \overline{f}. For φ ∧ α the unique minimal point is w. This has the unique extension w ⊔ f, so φ ∧ α ⇝ β. Also, the extensions of the minimal points of φ are w ⊔ f and w ⊔ \overline{f}, respectively. In both of these w holds, so that φ ⇝ α. But φ does not ⇝ β, since we have the extension w ⊔ \overline{f}.

The problem here is that by moving to a minimal point of φ ∧ α we are forgetting the information in w ⊔ f and w ⊔ \overline{f} which we had when we were figuring out the conjunction. The second of these models would block the extension w ⊔ f.

Is this counterexample a realistically valid one? Imagine that w stands for a property that the typical bird has, like “wingspan less than 6 feet”; and f stands for the property of flying. Using a new atom b for “bird”, we could reason as follows: Suppose that birds normally fly, and birds normally have wingspans less than 6 feet. Using intuitive reasoning, it seems that from b ∧ (w ∨ \overline{f}) we could jump to the conclusion b ∧ w. It also seems reasonable to accept b ∧ w ⇝ f. But from b ∧ (w ∨ \overline{f}) ⇝ b ∧ w we get by weakening b ∧ (w ∨ \overline{f}) ⇝ (b ∧ w) ∨ (b ∧ f). Let α be the formula (b ∧ w) ∨ (b ∧ f), ϕ be the formula b ∧ (w ∨ \overline{f}), and β be f. Then ϕ ∧ α is equivalent to b ∧ w, from which we conclude f. But from (b ∧ w) ∨ (b ∧ \overline{f}) it does not seem reasonable to conclude f because of the case b ∧ \overline{f}.

The previous examples indicate that nonmonotonic entailment on open sets do not satisfy cautious monotony, neither cautious cut. We now want to say something affirmative about the nonmonotonic entailment on stable neighborhoods (Scott open sets whose minimal points are pairwise incompatible; see [19]) by assuming the property of unique extensions.

The following is a collection of laws that hold in this case. Note that stable neighborhoods are disjoint, so that whenever we write p ∨ q, we implicitly also mean that p ∧ q = false. Note that ≤ stands for strict entailment, and = is the derived equivalence. When we write p ≤ q, we mean p is a subset of q (the smaller the open set, the more information we have). As usual, &, ⇒, and ⇔ are reserved for our meta-language.

Theorem 6.1 Let p, q, r range over stable neighborhoods in a default domain with unique extensions. Then the following results hold.

• Supraclassicality: p ≤ q ⇒ p ⇝ q.

• Left Logical Equivalence: (p = q) & (p ⇝ r) ⇒ q ⇝ r.

• Right Weakening: (p ⇝ q) & (q ≤ r) ⇒ p ⇝ r.

• Cautious Cut: (p ⇝ q)&(p ∧ q ⇝ r) ⇒ p ⇝ r.

• Cautious Monotony: (p ⇝ q) & (p ⇝ r) ⇒ p ∧ q ⇝ r, where q is disjunction-free.

• Right And: (p ⇝ q) & (p ⇝ r) ⇒ (p ⇝ q ∧ r).

• Left Or: (p ∨ q) ⇝ r ⇔ (p ⇝ r) ∧ q ⇝ r.

• Right Or: p ⇝ (q ∨ r) ⇒ (p ⇝ q) ∨ (p ⇝ r).

Proof: We verify Cautious Monotony and Cautious Cut.

Cautious Monotony. Suppose p ⇝ q, p ⇝ r in a default domain (D, ⊑, Λ), where p, q, r are stable neighborhoods, with q disjunction-free, and extensions are unique. Since stable neighborhoods are preserved under binary intersection, p ∧ q remains a stable neighborhood. Let x be a minimal point of p ∧ q, and let y be the extension for x. Clearly any minimal point of p ∧ q is of the form a ⊔ b, where a ∈ μp and b is the unique minimal point of q. We know that the extension of a, say e, is in q, and hence,

e ⊒ a ⊔ b.

So a ⊑ a ⊔ b ⊑ e. By the unique extension property (see Section 4.4), the only extension of x must be e. From the assumption p ⇝ r we have e ∈ r. Therefore, any extension of a minimal element of p ∧ q belongs to r, which was what we wanted.

Note that q being disjunction-free (hence having a unique minimal element) is crucial for cautious monotony. One can easily construct examples where cautious monotony fails when q is not disjunction-free, as we have seen earlier. In [14], we proved that cautious monotony holds for precondition-free defaults, again assuming that q is disjunction-free.

Cautious Cut. As before, let m be a minimal element of p, and e the extension of m. Since p ⇝ q, e ⊒ n for some n ∈ q and so

m ⊑ m ⊔ n ⊑ e.

Again by the unique extension property, e is an extension of m ⊔ n as well. Therefore, e ∈ r. This means p ⇝ r.

In fact, cautious cut follows from either the property of unique extension or the property of disjointness of stable neighborhoods individually. The above verification did not use disjointness of stable neighborhoods. A proof that cautious cut follows from disjointness of stable neighborhoods can be found in [14].

Finally, note that Right Or only holds when extensions are unique.

□

References

[1] S. Abramsky. Domain theory in logical form. Annals of Pure and Applied Logic 51, 1991.

[2] F. Baader and B. Hollunder. Embedding Defaults into Terminological Knowledge Representation Formalisms, In Proceedings of Third Annual Conference on Knowledge Representation, Morgan Kaufmann, 1992.

[3] D. Gabbay. Theoretical foundations for nonmonotonic reasoning in expert systems. Proceedings of NATO Advanced Study Institute on Logics and Models of Concurrent Systems, 439-457, Springer Verlag, 1985.

[4] P. Gärdenfors and D. Makinson. Nonmonotonic inference based on expectations. Artificial Intelligence 65, 197-245, 1994.

[5] J. Halpern and M. Vardi. Model checking vs. theorem proving – a manifesto. In Proceedings of Second Annual Conference on Knowledge Representation, pages 118–127. Morgan Kaufmann, 1991.

[6] W. van der Hoek, J.-J. Ch. Meyer, Y.H. Tan and C. Witteveen, editors. Non-Monotonic Reasoning and Partial Semantics, Ellis Horwood, 1992

[7] S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models, and cumulative logics. Artificial Intelligence, 44:167–207, 1990.

[8] V. Lifschitz. On open defaults. In Proceedings of the Symposium on Computational Logics, Brussels, 1990.

[9] J. McCarthy. Circumscription-a form of nonmonotonic reasoning. Artificial Intelligence, 13:27-39, 1980.

[10] D. McDermott and J. Doyle. Non-Monotonic Logic I. Artificial Intelligence, 13:41-72, 1980.

[11] J. Pearl. From Adams’ conditionals to default expressions, causal conditionals, and counterfactuals. In Festschrift for Ernest Adams. Cambridge University Press, 1993. To appear.

[12] R. Reiter. A logic for default reasoning. Artificial Intelligence, 13:81-132, 1980.

[13] W. Rounds and G.-Q. Zhang. Constraints in nonmonotonic reasoning. First Workshop on Principles and Practice of Constraint Programming, Rhode Island, 1993.

[14] W. Rounds and G.-Q. Zhang. Logical considerations on default semantics. Proc. 3rd Int’l Symp. on Artificial Intelligence and Mathematics, 1994. To appear.

[15] W. Rounds and G.-Q. Zhang. Domain theory meets default logic. Logic and Computation, 1992. To appear.

[16] W. Rounds and G.-Q. Zhang. Modal logics for default domains, 1992. Submitted.

[17] Dana S. Scott. Domains for denotational semantics. In Lecture Notes in Computer Science 140, 1982.

[18] G.-Q. Zhang and W. Rounds. Nonmonotonic consequences in default model theory. The Third Bar-Ilan Symposium on the Foundations of Artificial Intelligence, Bar-Ilan University, Israel, July 1993. Revised version to appear.

[19] G.-Q. Zhang Logic of Domains. Birkhauser, Boston, 1991.