\underline{\underline{\underline{7}}} Non-monotonic consequences of

preferential contextual disambiguation

Abstract. Logical consequence between (unambiguous) formulas is extended to ambiguous expressions through disambiguations mapping the latter to the former. A particular system of preferential contextual disambiguation is related to well-known rules for non-monotonic consequence relations |∼. On the one hand, the system provides a representation of |∼ based on an ambiguous expression of the background conditions underlying the entailment. On the other hand, rules for |∼ suggest requirements on disambiguations and on preferences between them.

1. Introduction

A familiar obstacle to applying logic to analyze the meaning of a natural language utterance is that pragmatics is commonly abstracted out of logic. Frustration with logic short on pragmatics might well drive one to the bold alternative slogan

logic is a consequence of pragmatics!

But what could the words “logic” and “consequence” (not to mention “pragmatics”) mean? Notions of logical consequence going back to Tarski and Gentzen have been relaxed in more recent years to provide a minimal criteria for “logic,” admitting, in particular, the possibility of non-monotonicity. A concrete test then of the slogan above is provided by the matter of ambiguity, construed broadly and pragmatically.

1.1. Summary. The present paper relates the theory of non-monotonic consequence relations |∼ (e.g., Gabbay [6]) to “preferential, contextual disambiguation.” An indeterminate background context is ascribed to |∼, and formulated as an “ambiguous” expression c that is then “merged” with the antecedent (to the left of |∼), yielding an ambiguous expression. Ambiguous expressions are “disambiguated” into unambiguous formulas by functions, called disambiguations, that take context into account (hence, the term “contextual disambiguation”). A “preference” relation ≺ on (the set of) disambiguations is assumed that induces an extension |−_{≺} of a classical consequence relation |− (on unambiguous formulas) to possibly ambiguous expressions. The consequence relation |∼ between expressions e and e′ is then characterized by the equivalence

e |∼ e′ iff c^{∧}e |−_{≺} e′ ,

for some binary (merge) operation ^{∧} on expressions, generalizing classical conjunction on unambiguous formulas.

1.2. Aims. Properties postulated for non-monotonic consequence relations (e.g., the cumulative and preferential systems described in Kraus, Lehmann and Magidor [9]) translate into requirements on the set Δ of disambiguations, and on the preference relation ≺ ⊆ Δ × Δ on Δ. Conversely, representation theorems based on Δ and ≺ constitute an alternative to the usual (forms of) preferential semantics (going back to Shoham [14], Makinson [10], etc.). Extensions of |∼ to ambiguous expressions, including (nested) conditionals, are also provided by |−_{≺}.

1.3. Underlying intuitions. The intuition behind preferential semantics is that agents cope with uncertainty about information by preferring certain interpretations over others. The notion of context can be understood either as an object that supports some information or as a piece of information itself. In either case, the partiality of contexts suggests a formalization of contexts as formulas^{1} (or as sets of models), with indeterminate contexts analyzed as ambiguous expressions. What is novel about the present work is that the preference relation ≺ above is defined not on contexts, but on functions that disambiguate contexts; that is, ≺ is a binary relation on the forementioned disambiguations. The idea in linking |∼ to a notion |−_{≺} of logical consequence between possibly ambiguous expressions is to trace deviant features of commonsense reasoning to the step from classical logic (with an unambiguous consequence relation |−) to natural language (interpreted relative to a context that admits no unambiguous formulation). The syntactic nature of this characterization of |∼ is deliberate; the thrust of representation theorems (in terms of Δ and ≺) is not so much to describe model-theoretic systems (derived by replacing formulas with sets of models) relative to which certain proof rules are complete, but rather to explore the scope of a “representationalist” conception of disambiguation that need not appeal to models.

2. Background

A natural operation to perform on two formulas φ and φ′ is to “merge” them into a formula φ^{∧}φ′ that contains the information in φ and in φ′. This operation supports a view of formulas as both contexts φ and “context change potentials” φ′ insofar as

φ^{∧}φ′ ≈ the context returned by asserting φ′ at context φ .

Classical conjunction is an obvious example of such an operation, but, in fact, the term “context change potential” is used in certain formal approaches to natural language discourse (e.g., Kamp and Reyle [8]), where ^{∧} is not commutative (hence the elevation of the symbol ∧, suggesting concatentation). These approaches are motivated in no small measure by the problem of anaphora in natural language, which, very roughly, has to do with the question of what pronouns refer to, as in the piece of discourse

1This point is taken up at length in §4.1 below.

                     Ernest has a brother.
                He would understand this paper.

As illustrated above, a pronoun (occurrence) may well have more than one possible reference, leading to ambiguity.^{2} With this in mind, let us distinguish the set Φ of unambiguous formulas from a larger set E ⊃ Φ of (possibly ambiguous) expressions (regarding say, a formula with an unbound variable as an element of E − Φ). Under this division, a classical notion of logical consequence |− can be assumed for Φ that treats (the restriction to Φ of) ^{∧} as just ordinary conjunction ∧. This point is discussed in §4.2 below. For now, let us take it for granted, and turn our attention to how to extend |− to E.

2.1. Eliminating ambiguity. Inasmuch as ambiguous expressions differ from unambiguous formulas in that they require “disambiguation,” it is natural to bring such a notion into the picture. Toward that end, let Δ be a set of disambiguations δ : (Φ × E) → Φ, with the intuition that

δ(φ, e) ≈ a disambiguation of e given context φ .

Observe that an ambiguous expression e is totally disambiguated (relative to an unambiguous context), but that “partial” disambiguation might be modeled as a set of “total” disambiguations. Also, Δ cannot, of course, be the full function space (Φ × E) → Φ. For instance, every δ ∈ Δ must leave unambiguous formulas as is; that is, δ(φ, φ′) = φ′, for all φ and φ′ ∈ Φ. Other requirements should doubtless be imposed, and indeed one of the very points of this paper is to uncover just what those might be. Let us move along then, and notice that a disambiguation δ : (Φ×E) → Φ induces a natural extension of |− ⊆ Φ × Φ to |−^{δ} ⊆ E × E relative to an (implicit) “empty context” ⊤ ∈ Φ (such that, for example, φ |− ⊤ for every φ ∈ Φ) as follows

e |−^{δ} e′ iff δ(⊤, e) |− δ(δ(⊤, e), e′) .

Note that the disambiguation of the succedent e′ is carried out relative to the context δ(⊤, e) created by the antecedent (asserted at the context ⊤).

Next, let us quantify out the choice of δ by asking

is the set {δ ∈ Δ : e |−^{δ} e′} large?

Without saying exactly what “large” means, let us assume some answer given by a family D ⊆ Pow(Δ) of sets of disambiguations (so that a subset D of Δ is “large” iff D ∈ D). Then, it is natural to extend |− ⊆ Φ×Φ to |−^{D} ⊆ E ×E according to

e |−^{D} e′ iff {δ ∈ Δ : e |−^{δ} e′} ∈ D .

Now, returning to D, we may assume the full set Δ is large — i.e., Δ ∈ D —, and that all sets larger than a large set are large — i.e.,

\frac{D ∈ D D ⊆ D′}{D′ ∈ D} .

2As it happens, I have a brother named Ernest. Alas, I doubt he’d understand this paper.

Assuming further that D is closed under intersections,

\frac{D ∈ D D′ ∈ D}{D ∩ D′ ∈ D} ,

turns D into a filter. This third assumption will prove useful for technical reasons, but is certainly more questionable than the other two.

2.2. Non-monotonic consequences of preferential semantics. The “technical reasons” alluded to above concern the fitness of |−^{D} to be a notion of logical consequence. The criteria for such a notion have changed over the years, reflecting the interest in non-monotonicity. A number of rules (or more precisely, closure conditions) for a binary relation |∼ ⊆ L × L on a set L of formulas are presented in Gabbay [6], based on a classical consequence relation |− ⊆ L × L. Typically, |∼ is both stronger and weaker than |−, in that |− ⊆ |∼, but |∼ respects less rules. This is the case for what Kraus, Lehmann and Magidor [9] describe as Gabbay’s base system C of cumulative reasoning, which consists of the rules of reflexivity

(Ref) \overline{e |∼ e} ,

left logical equivalence

(LLE) \frac{e_{1} |∼ e e_{1} |− e_{2} e_{2} |− e_{1}}{e_{2} |∼ e} ,

right weakening

(RW) \frac{e |∼ e_{1} e_{1} |− e_{2}}{e |∼ e_{2}} ,

cut

(Cut) \frac{e_{1} |∼ e_{2} e_{1}^{∧}e_{2} |∼ e}{e_{1} |∼ e} ,

and cautious monotonicity

(CM) \frac{e_{1} |∼ e_{2} e_{1} |∼ e}{e_{1}^{∧}e_{2} |∼ e} .

Observe that all these rules hold for |∼ equal to |−, and that (more generally) the containment |− ⊆ |∼ is an immediate consequence of (Ref) and (RW). As it turns out, the rule (CM) has proved to be somewhat controversial, in no small measure because it fails in Reiter [12]’s default logic (as pointed out in Makinson [10]). A weaker system than C is proposed in Voorbraak [16] to capture default logic. Voorbraak [16] follows Makinson [10] in considering infinitary (Tarski-syle) consequence relations. Following instead Kraus, Lehmann and Magidor [9] in studying finitary (Gentzen-style) consequence relations, let us weaken C to C^{−} by replacing (CM) with

(And)  \frac{e |∼ e_{1}  e |∼ e_{2}}{e |∼ e_{1}^{∧}e_{2}} .

The rule (And) is valid for default logic, and can be derived in C.

A systematic approach to evaluating the soundness of rules for |∼ is, of course, to provide a general semantics for |∼. Proposals based on a preferential relation on contexts go back (at least) to Shoham [14], where contexts are taken to be models, and to Makinson [10], where that identification is loosened. More recent developments are described in Kraus, Lehmann and Magidor [9] and Voorbraak [16]. The present work can be viewed as yet another variation on the theme, the essential novelty being that a distinction between contexts and interpretations is drawn (motivated by the problem of ambiguity), and that it is on the latter that preferences are defined.

2.3. Disambiguating entailment, abduction and deduction. Let us now merge the two previous subsections by analyzing an entailment e |∼ e′ in terms of an ambiguous expression c ∈ E − Φ that makes the entailment’s background conditions explicit. That is, let us stipulate

(†) e |∼ e′ iff c^{∧}e |−^{D} e′ .

Note that for e, e′ ∈ Φ, it suffices (as far as (†) is concerned) to consider the restriction of disambiguations δ to (Φ×Φ)∪({⊤}×{c^{∧}φ : φ ∈ Φ}). On Φ×Φ, we have already decided that δ should respect the unambiguous character of formulas in Φ — i.e.,

(C1) δ(φ, φ′) = φ′ , for all φ, φ′ ∈ Φ .

As for {⊤}×{c^{∧}φ : φ ∈ Φ}, let us observe that contexts not only disambiguate, but can themselves be disambiguated — i.e.,

(C2) δ(⊤, c^{∧}φ) = c_{φ}^{δ} ∧ φ , for every φ ∈ Φ ,

for certain choices c_{φ}^{δ} ∈ Φ.

Next, let us derive the notion D of a “large” set from some preference relation ≺ ⊆ Δ × Δ on Δ. An obvious candidate is that of a ≺-dense set, where a subset D ⊆ Δ is defined to be ≺-dense if for every δ ∈ Δ, there is a δ′ ∈ D such that δ′ ⪯ δ (writing ⪯ for ≺ ∪ =). Unfortunately, the family of ≺-dense sets is not necessarily closed under intersection.^{3} This defect is easily corrected by requiring that a large set D be stably ≺-dense in that for every δ ∈ Δ, there is a δ′ ⪯ δ such that for every δ′′ ⪯ δ′, δ′′ ∈ D.

Proposition 1 (Folklore). For any transitive relation ≺, the family D_{≺} of stably ≺-dense sets is a filter.

Let us pause for a moment to reflect on where things stand. A characterization of e |∼ e′ is proposed, in which ambiguity is injected through a “rogue” context c ∈ E − Φ that validates the entailment, under a disambiguation from the set {δ ∈ Δ : c^{∧}e |−^{δ} e′}. Although preferences have been defined here not (as in the usual case) on contexts, but rather on disambiguations, note that the restriction of the equivalence (†) above to unambiguous formulas e, e′ ∈ Φ reduces (for all purposes) a disambiguation δ to its value δ(⊤, c^{∧}e) at the antecedent. That is, for φ, φ′ ∈ Φ, the set

3See the pair (Δ, ≺) constructed for the representation theorem in §3.2. Alternatively, closure under intersections might be required only for “definable” sets in D.

C_{φ,φ′} = {c_{φ}^{δ} : δ ∈ Δ and c^{∧}φ |−^{δ} φ′}

can be regarded as the set of possible “explanations” for the entailment φ |∼ φ′. The reader familiar with Peirce [11] and the more recent paper, Hobbs et al [7], might at this point bring in abduction. If explanations are equated with partial disambiguations of c, modeled by sets of total disambiguations of c, then the preference relation for abduction might simply be the superset relation, with the set C_{φ,φ′} as the explanation abduced for the entailment φ |∼ φ′. If, moreover, C_{φ,φ′} (or more precisely, the corresponding set {δ ∈ Δ : c_{φ}^{δ} ∈ C_{φ,φ′}}) is stably ≺-dense, then abduction is deduction! Alternatively, the preference relation for abduction can also be equated with the preference relation ≺ on Δ, in which case the explanation abduced for the entailment φ |∼ φ′ must be drawn from the set {δ ∈ Δ : c_{φ}^{δ} ∈ C_{φ,φ′}}. Just what is entailed by the assumption that optimal explanations exist will be taken up in §4.3.

3. Cumulative consequence relations interpreted ambiguously

The rules for |∼ ⊆ L × L in Kraus, Lehmann and Magidor [9] mention a consequence relation |− ⊆ L × L that is classical on L. For this reason, let us identify L with Φ, and restrict |∼ to Φ, leaving to §3.3 a brief consideration of the possibility of extending the theory to E. Recall, for the record, that the system C of cumulative reasoning is given by

C = {(Ref), (LLE), (RW), (Cut), (CM)} ,

which has a weakened form

C^{−} = {(Ref), (LLE), (RW), (Cut), (And)} .

Let us also write e ≡ e′ to abbreviate the conjunction, e |− e′ and e′ |− e, and observe that ≡ is an equivalence on Φ, but not on E.

3.1. Soundness. The following choices of sufficient conditions are not so ad hoc, in view of the representation theorem from the next section. A pair (Δ, ≺) is C^{−}-sufficient if

(i) the family D_{≺} of stably ≺-dense sets is a filter (e.g., ≺ is transitive), (ii) for all δ ∈ Δ, and φ, φ′ ∈ Φ, and e ∈ E,

(C3) \frac{φ ≡ φ′}{δ(φ, e) |− δ(φ′, e)}

and (iii) for all φ, φ′ ∈ Φ,

\frac{\{δ ∈ Δ : c^{∧}φ |−^{δ} φ′\} ∈ D_{≺} (i.e., φ |∼ φ′)}{\{δ ∈ Δ : δ(⊤, c^{∧}φ) |− δ(⊤, c^{∧}(φ ∧ φ′))\} ∈ D_{≺}} .

Weakening the premiss in (C3) to φ |− φ′, would strengthen (LLE) as in (RW), leading to monotonicity. Condition (iii) is unreletingly ugly, but can be made prettier if we pass from C^{−} to a preferential version of it, described in §3.3. In the meantime, call (Δ, ≺) C-sufficient if it is C^{−}-sufficient, and (iii) is strengthened into

\frac{\{δ ∈ Δ : c^{∧}φ |−^{δ} φ′\} ∈ D_{≺}}{\{δ ∈ Δ : δ(⊤, c^{∧}(φ ∧ φ′)) ≡ δ(⊤, c^{∧}φ)\} ∈ D_{≺}}

for all φ, φ′ ∈ Φ.

Proposition 2 (Soundness). If (Δ, ≺) is C^{−}-sufficient, then the relation {(φ, φ′) ∈ Φ × Φ : c^{∧}φ |−_{≺} φ′} verifies C^{−}. Similarly, for the full system C.

Proof. Given the conditions (C1) and (C2) from §2.3, use (a) Δ ∈ D_{≺} for (Ref),

(b) D_{≺} is upward closed for (RW),

(c) D_{≺} is closed under intersections for (And),

(d) condition (C3) for (LLE), and

(e) part (iii), as well as the closure properties of D_{≺}, for (Cut). (CM) follows as in part (e) from the additional condition for C-sufficiency. ⊣

3.2. Completeness [sic]. Fix a relation |∼ ⊆ Φ×Φ validating say, C^{−}, with the idea of defining a suitable pair (Δ, ≺), from which |∼ can be reconstructed. A first attempt might be to disambiguate c uniformly as {ψ : ⊤ |∼ ψ}. However, even if we set aside the problem that {ψ : ⊤ |∼ ψ} is infinite, there remains the question of establishing the equivalence

(‡) φ |∼ φ′ iff {ψ : ⊤ |∼ ψ}, φ |− φ′ .

(As usual, |− can be extended to Pow(Φ) × Φ by

Γ |− φ iff (∃ finite Γ_{0} ⊆ Γ) ⋀ Γ_{0} |− φ ,

with Γ, φ |− φ′ written instead of Γ ∪ {φ} |− φ′.) It suffices for the forward direction ⇒ of (‡) that

φ |∼ φ′ implies ⊤ |∼ φ ⊃ φ′ ,

which is a special case of the “hard half of the deduction theorem” called rule (S) in Kraus, Lehmann and Magidor [9] (page 191). Avoiding this rule altogether, let us disambiguate c instead as {ψ ⊃ ψ′ : ψ |∼ ψ′}. But there is still the backward direction ⇐ of (‡), for which the relativization c_{φ}^{δ} of the disambiguation of c to φ, given by (C2), is useful. In particular, let us trim down the disambiguation further by setting our sights on the theory

Γ_{φ} = {φ ⊃ φ′ : φ |∼ φ′} ,

which enjoys the following property.

Lemma 3.^{4} Assuming |∼ verifies C^{−},

φ |∼ φ′ iff Γ_{φ}, φ |− φ′

for all φ, φ′ ∈ Φ.

Proof. Suppose φ |∼ φ′. Then by the definition of Γ_{φ}, Γ_{φ} |− φ ⊃ φ′, and we are done by the deduction theorem for |−. The converse requires a bit more work. Assume Γ_{φ}, φ |− φ′. That is, there are φ_{1}, …, φ_{n} such that

(∗) φ |∼ φ_{i} for every i ∈ {1, …, n} ,

and

(∗∗) ⋀_{i=1}^{n} (φ ⊃ φ_{i}) ∧ φ |− φ′ .

Now, (∗∗) implies

(⋀_{i=1}^{n} φ_{i}) ∧ φ |− φ′ ,

whence (since |− is contained in |∼)

(⋀_{i=1}^{n} φ_{i}) ∧ φ |∼ φ′ .

Also, by the rule (And), it follows from (∗) that

φ |∼ ⋀_{i=1}^{n} φ_{i} .

Thus, (Cut) yields φ |∼ φ′, as required. ⊣

Next, let us attend to the problem that the set Γ_{φ} is infinite. This is where Δ and ≺ come to play. Assuming Φ is countable, fix an enumeration {ψ_{0}, ψ_{1}, … } of Φ, and build a set Δ = {δ_{0}, δ_{1}, … } of disambiguations, where (for every φ ∈ Φ) δ_{i} approximates Γ_{φ} up to {ψ_{0}, …, ψ_{i}} in the sense that

c_{φ}^{δ_{i}} = ⋀{φ ⊃ φ′ : φ |∼ φ′ and φ′ ∈ {ψ_{0}, ψ_{1}, …, ψ_{i}}} .

Arrange

δ_{i}(φ, φ′) = φ′

for every i and for all φ, φ′ ∈ Φ. Then define ≺ by

δ_{i} ≺ δ_{j} iff i > j .

Let |−_{≺} be |−^{D_{≺}}, where D_{≺} is the family of stably ≺-dense sets.

4This is the key lemma, corresponding to Lemma 3.18 in Kraus, Lehmann and Magidor [9]. It seems that (LLE) is unnecessary, unless, as suggested in §3.3, (Cut) is replaced by the preferential rule (Or) described there.

Theorem 4 (Representation). Let Φ be countable, and |∼ ⊆ Φ × Φ verify C^{−}. Then for Δ and ≺ constructed as above,

φ |∼ φ′ iff c^{∧}φ |−_{≺} φ′

for all φ, φ′ ∈ Φ. Furthermore, (Δ, ≺) is C^{−}-sufficient. Similarly, for C.

Proof. For the equivalence, it suffices by Lemma 3 to establish that

Γ_{φ}, φ |− φ′ iff c^{∧}φ |−_{≺} φ′ ,

which is easy because ≺ is a linear order, and whenever δ ≺ δ′, c_{φ}^{δ} |− c_{φ}^{δ′}.

Turning to C/C^{−}-sufficiency, use Proposition 1 and the definition of c_{φ}^{δ} for parts (i) and (ii)^{5} respectively of C^{−}-sufficiency. Part (iii) and the additional condition for C-sufficiency are proved by reversing the argument for soundness. In particular, observe that

\frac{\{δ ∈ Δ : c_{φ}^{δ} ∧ φ |− φ′\} ∈ D_{≺}}{\{δ ∈ Δ : c_{φ}^{δ} ∧ φ |− c_{φ∧φ′}^{δ}\} ∈ D_{≺}}

follows from (Ref), (Cut), (And) and the definition of c_{φ}^{δ}, while

\frac{\{δ ∈ Δ : c_{φ}^{δ} ∧ φ |− φ′\} ∈ D_{≺}}{\{δ ∈ Δ : c_{φ∧φ′}^{δ} ∧ (φ^{∧}φ′) |− c_{φ}^{δ}\} ∈ D_{≺}}

is a consequence of (Ref), (CM), (And) and the definition of c_{φ}^{δ}. ⊣

3.3. Extensions. Insofar as neither Δ nor ≺ need mention models, it is perhaps unsuitable to call Theorem 4 a “completeness theorem.” Moreover, §3.2 is hardly “complete” in that there are at least two obvious directions in which to extend the analysis. Further rules might be added to C^{−}, and the set Φ might be expanded to cover more of E. Let us take these up briefly, in turn.

The equivalence stated in Theorem 4 can be maintained for any extension of C^{−} by rules (over the same set Φ). If necessary, the rules can be translated mechanically into conditions on Δ and ≺. Take, for instance, what Kraus, Lehmann and Magidor [9] call preferential reasoning, which is characterized by adding to C the rule

(Or) \frac{e_{1} |∼ e e_{2} |∼ e}{e_{1} ∨ e_{2} |∼ e} .

Put in terms of (Δ, ≺), this rule becomes simply

(OR) \frac{\{δ ∈ Δ : c^{∧}e_{1} |−^{δ} e\} ∈ D_{≺} \{δ ∈ Δ : c^{∧}e_{2} |−^{δ} e\} ∈ D_{≺}}{\{δ ∈ Δ : c^{∧}(e_{1} ∨ e_{2}) |−^{δ} e\} ∈ D_{≺}}

and if we are content with such a “syntactic” requirement on (Δ, ≺), we need work no further for a representation of P. (A parallel here might be drawn with the manner in which the completeness theorem for first-order logic applies to different first-order theories.) Of course, a little labor is always good, and a simple restatement of (OR) might be illuminating. Or perhaps with a bit more effort, we might even strengthen (OR) by a sufficient condition met by the model constructed in the proof of Theorem 4, adapted to P.^{6} Following a suggestion of D. Lehmann’s (made in a conversation with me) that (Or) be regarded as a basic rule, consider the system P^{−} obtained from P by replacing (CM) by (And). As proved in page 191 of Kraus, Lehmann and Magidor [9], P^{−} enjoys cut-elimination — which is to say that P^{−} can be redefined as C^{−} with (Cut) replaced by (Or)

5Observe that the reversal of (LLE) would not have been possible had c_{φ}^{δ_{i}} been defined instead as ⋀(Γ_{φ} ∩ {ψ_{0}, …, ψ_{i}}).

P^{−} = {(Ref), (LLE), (RW), (And), (Or)} .

Now, improving on condition (iii) of C^{−}-sufficiency, define a pair (Δ, ≺) to be P^{−}-sufficient if

(i) ≺ is transitive, (ii) for all φ, φ′ ∈ Φ, δ ∈ Δ and e ∈ E,

\frac{φ ≡ φ′}{δ(φ, e) ≡ δ(φ′, e)}

and (iii) for all φ_{1}, φ_{2}, ∈ Φ, and δ ∈ Δ,

δ(⊤, c^{∧}(φ_{1} ∨ φ_{2})) |− δ(⊤, c^{∧}φ_{1}) ∨ δ(⊤, c^{∧}φ_{2}) .

The arguments in §§ 3.1 and 3.2 can be modified easily to prove

Theorem 5. For every P^{−}-sufficient pair (Δ, ≺), the relation {(φ, φ′) ∈ Φ × Φ : c^{∧}φ |−_{≺} φ′} verifies P^{−}. Conversely, if Φ is countable, then for every |∼ ⊆ Φ × Φ verifying P^{−}, there is a P^{−}-sufficient pair (Δ, ≺) such that

φ |∼ φ′ iff c^{∧}φ |−_{≺} φ′

for all φ, φ′ ∈ Φ.

A second direction in which to push the present analysis of |∼ is to enlarge the set of formulas to E. This is, in my mind, no mean enterprise, requiring as it does some fundamental reflection on the nature of ambiguity, and on the plausibility that |−^{D} should be “logical” (in any recognizable sense). Two assumptions made in the present paper, for instance, deserve more careful consideration: (i) the claim that the “partial” character of (the “actual” process of) disambiguation can be modeled through sets of total disambiguations, and (ii) the assumption that D is closed under intersections. In confining its attention to the disambiguation of a rogue context c, the present paper takes the tiniest bite at the monster that is ambiguity; the reader with an appetite for more is referred to Fernando [4].

6Notice, for instance, that condition (C3) (in the definition of C^{−}-sufficiency) is stronger than the mechanical translation of (LLE), but that we have taken pains to construct, in the proof of Theorem 4, an interpretation (Δ, ≺) satisfying (C3).

4. Discussion

The basic hypothesis about non-monotonicity explored above is, very briefly, that non-monotonicity arises from the non-persistent interpretation (— identified here with disambiguation —) of implicit (background) conditions. To help us digest that point, let us try to put things in their proper context.

4.1. Contexts: between models and formulas. Few would dispute the claim that contexts are partial, but just what the consequences of this claim are varies widely from researcher to researcher. For the approach developed above, it is crucial that this partiality not be confused with uncertainty about contexts, as such a distinction is necessary in formulating the following principle of persistence

\frac{φ |− φ′}{δ(φ, e) |− δ(φ′, e)} .

The failure (above) of persistence gives rise to the essential asymmetry between the rules (LLE) and (RW) of Kraus, Lehmann and Magidor [9] (— an asymmetry that all other rules can be viewed as being devised to diminish). In fact, whereas the rule (RW) is, in the present work, an immediate consequence of the innocuous assumption that only “large” sets can contain “large” sets, the rule (LLE) must, weak as it is, be introduced through condition (C3). (C3) can be restated (as in the definition of P^{−}-sufficiency) as

\frac{φ ≡ φ′}{δ(φ, e) ≡ δ(φ′, e)} ,

asserting that, so far as disambiguation is concerned, an unambiguous formula matters only up to its set of models. That is, a perfectly finitary formula can be replaced by an infinite set (if not proper class) of its possibly infinite models. Of course, only the most rabid semanticist could (shamelessly) describe such a move as a “reduction.” On the other hand, there is no denying the widespread bias for models over formulas, manifested, for instance, by the fact that preferences were initially defined on models (rather than on formulas). We may well expect preferences on infinite sets of formulas (corresponding to theories of models) to be reducible to preferences on (single) formulas (corresponding to basic open sets of models), if only because compactness has become so familiar.^{7} But defining preferences between states “labeling” the same sets of formulas (as in the preferential models constructed in §5.3 of Kraus, Lehmann and Magidor [9]) is a different matter altogether, requiring a shift in perspective. Staying with our interpretation of |∼ in terms of Δ and ≺, it perhaps bears repeating that in view of the dispensability of models to that interpretation, it is more appropriate to describe Theorem 4 as a “representation theorem,” rather than a “completeness theorem.” Indeed, I conceived Theorem 4 originally to serve a certain representationalist end, establishing the eliminability of models (poorly suited, as they are, for mechanization).

7Passing to effectively presented sets, there is also Kleene’s theorem stating that a recursively enumerable first-order theory is equivalent to a first-order sentence, allowing an expansion in vocabulary.

4.2. Discourse representation. Although a model-theoretic interpretation of a notion |− ⊆ Φ × Φ of consequence allows formulas (in Φ) to be replaced by models, it need not imply that |− is classical. In the case of Discourse Representation Theory (DRT, Kamp and Reyle [8]), for instance, an equivalence between model-theoretic and syntactic accounts of Φ was more or less obvious before a classical consequence relation |− was isolated. The simple reason was that the model-theoretic interpretation commonly associated with the DRT merge ^{∧} is not commutative. More precisely, a certain first-order fragment Φ of DRT can be supplied a semantics [[·]], under which

(i) every φ ∈ Φ is interpreted as a binary relation [[φ]] ⊆ S × S on a certain fixed set S of states (constructed from models), with the intuition that

s[[φ]]s′ iff given an initial context s,

φ can return the context s′

for all s, s′ ∈ S,

and (ii) ^{∧} is relational composition

[[φ^{∧}φ′]] = {(s, s′) ∈ S : (∃s′′) s[[φ]]s′′ and s′′[[φ′]]s′} ,

for all φ, φ′ ∈ Φ. Nevertheless, it turns out that the relational semantics [[·]] is determined by ∧ and a set Φ_{⊥} ⊆ Φ of “absurd” formulas (Fernando [2]). The situation is completely analogous to the way conjunction and negation determine Boolean connectives. Hence, it is perhaps not terribly surprising that, for this case, relational semantics can be reconciled with Boolean-valued semantics (Fernando [3]). That is to say, a classical notion |− of consequence can be defined for an unambiguous fragment Φ of DRT.

Far more interesting, however, are parts of DRT that go beyond Φ. Two examples are Segmented DRT (SDRT, Asher [1]) and treatments of plurals. In SDRT, a non-monotonic entailment relation |∼_{KB} relative to some knowledge base KB lies at the heart of the discourse interpretation process (involving socalled discourse relations). The idea is to put in the lefthand side of |∼_{KB} not only the natural language utterance to be interpreted, but also the “common ground” — that is, the discourse context. Now, it is natural to hypothesize that “conversational leaps” in the common ground give rise to the rogue context c (above). In particular, the presupposition associated with the utterance of a sentence φ at context K might be expressed as c so that

K, φ |∼_{KB} K′ iff K, c, φ |−_{KB} K′

for all (candidate consequences) K′. As for plural statements, ambiguity is a notorious problem, motivating, for example, the work of Reyle [13]. And whether or not the difficulty is labeled to be one of “ambiguity,” interpretation does not become any easier where there is no explicit quantification, as in the case of

                           Birds fly.

In contrast to the case of |∼_{KB}, it would seem useful to formulate such “bare plurals” as conditional expressions, rather than as judgments about |∼. In any event, a closer investigation of |∼, including its relation with conditionals, is clearly called for.

4.3. Smoothness, optimal disambiguations and generics. The assumption in abduction that there is a most preferred explanation, the limit assumption in Stalnaker [15], and the “smoothness condition” in Kraus, Lehmann and Magidor [9] correspond in the present approach to the following notion. A pair (Δ, ≺) is said to be smooth at (φ, e) ∈ Φ × E if

(∀δ ∈ Δ)(∃δ′ ⪯ δ)(∀δ′′ ⪯ δ′) δ′(φ, e) ≡ δ′′(φ, e) .

That is, there is a set Ψ_{φ,e} ⊆ Φ such that {δ ∈ Δ : (∃ψ ∈ Ψ_{φ,e})(∀δ′ ⪯ δ) δ′(φ, e) ≡ ψ} is stably ≺-dense. (Note that the particular pair (Δ, ≺ ) constructed in §3.2 is smooth at (φ, c) iff Γ_{φ} is equivalent to a formula.) Specializing to the case e = c relevant to our analysis of |∼ ⊆ Φ × Φ, call a pair (Δ, ≺) c-smooth if it is smooth at (φ, c), for every φ ∈ Φ.

Proposition 6. If (Δ, ≺) is c-smooth, then for every φ ∈ Φ, there is a set Ψ_{φ} ⊆ Φ of unambiguous formulas such that

c^{∧}φ |−_{≺} φ′ iff (∀ψ ∈ Ψ_{φ}) ψ |− φ ⊃ φ′ ,

for every φ′ ∈ Φ.

Proposition 6 not only reduces |∼ to material implication, but also characterizes the background condition as a disjunction ⋁ Ψ_{φ} (which can be formalized, assuming the disjunction can be formed; e.g., if Ψ_{φ} is finite). Observe that the background condition is defined relative to the antecedent φ, and that the more general case where antecedents and/or succedents might be ambiguous requires a notion of an “optimal disambiguation” that checks every ambiguous expression (not just c). Whether or not optimal choices at every pair (φ, e) (for all e ∈ E as well as φ ∈ Φ) can be assembled in a disambiguation presumably depends on the application at hand.

Returning to the simple case of c, the following example is instructive, particularly for a comparison with Kraus, Lehmann and Magidor [9].

Example. Let Φ be the set of propositions generated by a countable set {p_{0}, p_{1}, … } of propositional variables, and let L be the first-order language induced by a countable set {U_{0}, U_{1}, … } of unary relation symbols. Fix a constant symbol a, and define the translation ·^{a} from Φ to L(a) as follows

p_{n}^{a} = U_{n}(a)
(φ ∧ ψ)^{a} = φ^{a} ∧ ψ^{a}
(¬φ)^{a} = ¬(φ^{a}) .

Next, let M be the L-model with universe ω (= {0, 1, … }) that interprets U_{n} as {m ∈ ω : m ≥ n}, for every n < ω. Form the L(a)-theory T by adding to the L-theory of M the L(a)-sentences U_{n}(a), for every n < ω:

T = {χ ∈ L : M ⊧ χ} ∪ {U_{0}(a), U_{1}(a), … }

(which is consistent, by compactness). Define

φ |∼ ψ iff T |−_{L(a)} φ^{a} ⊃ ψ^{a} ,

for all φ, ψ ∈ Φ, and observe that |∼ satisfies C (including (CM)), but cannot be captured by a c-smooth pair (Δ, ≺), since T is not satisfiable in M (but only finitely satisfiable there). [End of Example]

By contrast, note that in Kraus, Lehmann and Magidor [9], a similar “smoothness condition is necessary to ensure the validity of Cautious Monotonicity” (page 182). A notion central to the representation arguments there is that of a normal model of φ, by which is meant a model of {φ′ : φ |∼ φ′}. This leads to so-called strongly cumulative models (the essential property of which is that every antecedent φ has a minimum state), because normal models contain infinite information, whereas disambiguations only encode single formulas (in values assigned to pairs (φ, e) ∈ Φ × E). As it turns out, it is fruitful to introduce types (as they are known in model theory) to express more information than can be packaged in single first-order formulas. The question is, however, what are these types of ? As has already been mentioned, preferences in Kraus, Lehmann and Magidor [9] can be defined between states labeling the same sets of formulas. (This, at least, is the case for the preferential models in §5.3, though not, as noted in Voorbraak [16], for the cumulative models in §3.5.) In conceptual terms, what do such states reflect? Toward an answer, Fernando [5] treats these states as objects in a first-order model, explores a notion of generic object (or better: type) that reduces defeasibility to material implication, and presents a proposal relating entailment |∼ to a connective producing conditional expressions. (At the risk of sounding obscure, suffice it to say that what is gained by introducing a preferential relation is the possibility of omitting the type.)

Acknowledgments

My thanks to Nicholas Asher, Hans Kamp, Emil Weydert and Daniel Lehmann (who suggested P^{−} in §3.3, among other things) for helpful discussions.

References

[1] Nicholas Asher. Reference to Abstract Objects in Discourse. Kluwer Academic Publishers, Dordrecht, 1993.

[2] Tim Fernando. What is a DRS? In R. Cooper and J. Groenendijk, editors, Integrating Semantic Theories II. Dyana deliverable R2.1.B, 1994. Presented in a Computational Semantics workshop at Tilburg (December 1994).

[3] Tim Fernando. A persistent notion of truth in dynamic semantics. In D. Westerståhl and J. Seligman, editors, Language, Logic and Computation: The 1994 Moraga Proceedings. CSLI, Stanford, To appear.

[4] Tim Fernando. Ambiguity under changing contexts. Manuscript, 1995. Presented in Mathematics of Language 4, Philadelphia, October 1995.

[5] Tim Fernando. Defeasible generic types. Manuscript, 1995.^{8}

[6] Dov M. Gabbay. Theoretical foundations for non-monotonic reasoning in expert systems. In K.R. Apt, editor, Proc. NATO Advanced Study Institute on Logics and Models of Concurrent Systems. Springer Verlag, Berlin, 1985.

[7] J. Hobbs, M. Stickel, D. Appelt, and P. Martin. Interpretation as abduction. Artificial Intelligence, 63, 1993.

[8] H. Kamp and U. Reyle. From Discourse to Logic. Kluwer Academic Publishers, Dordrecht, 1993.

[9] S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44, 1990.

[10] David Makinson. General theory of cumulative inference. In M. Reinfrank, J. de Kleer, M.L. Ginsberg, and E. Sandewall, editors, Proc. Second International Workshop on Non-monotonic Reasoning, Lecture Notes in Computer Science. Springer Verlag, Berlin, 1989.

[11] Charles Sanders Peirce. Abduction and induction. In J. Buchler, editor, Philosophical Writings of Peirce. Dover Books, New York, 1955.

[12] Raymond Reiter. A logic for default reasoning. Artificial Intelligence, 13, 1980.

[13] Uwe Reyle. Dealing with ambiguities by underspecification: construction, representation and deduction. Journal of Semantics, 10(2), 1993.

[14] Yoav Shoham. Reasoning about Change. MIT Press, Cambridge, MA, 1988.

[15] Robert Stalnaker. A theory of conditionals. In American Philosophical Quarterly Monograph Series 2. Blackwell, Oxford, 1968.

[16] Frans Voorbraak. Preference-based semantics for non-monotonic logics. In Proc. 13th IJCAI. Morgan Kaufmann, San Mateo, CA, 1993.

8Added, February 1997 . This manuscript has since been superseded by “In conjunction with qualitative probability.”

136 Tim Fernando