A logical connective for ambiguity requiring disambiguation

Tim Fernando^{∗}

                       fernando@ims.uni-stuttgart.de

1 Introduction: ambiguity and disambiguation

The idea of analyzing an expression as the (ordinary logical) disjunction of its disambiguations has been criticized on the grounds of both computational intractability (e.g., Reyle [5]) and logical untenability (e.g., van Deemter [1]). Concentrating on the latter, let us fix a set Φ_{0} of formulas, closed under disjunction ∨, and a semantic interpretation [[φ]]_{M} of formulas φ ∈ Φ_{0} relative to a first-order model M, under which the disjunction φ ∨ ψ of two formulas φ and ψ ∈ Φ_{0} is interpreted by the operation ∪ of union,

[[φ ∨ ψ]]_{M} = [[φ]]_{M} ∪ [[ψ]]_{M} .

The use of union above is adopted mainly for the sake of definiteness, the crucial point being that there is a fixed binary function F such that for all φ and ψ ∈ Φ_{0} and all models M, [[φ ∨ ψ]]_{M} = F ([[φ]]_{M}, [[ψ]]_{M}). That is, the interpretation of ∨ is uniform over all models M, suggesting that the disjunction of two unambiguous formulas is also unambiguous. By contrast, an expression that is ambiguous between (say) two unambiguous formulas φ and ψ should be interpreted as either φ or ψ (but not both^{1}) according to some unspecified information that must be supplied at the meta-level. With this in mind, let us introduce a binary connective • that is interpreted relative also to some item i embodying that information. More precisely, let Φ be the closure of Φ_{0} under • as well as the connectives in Φ_{0}, with each formula in Φ interpreted relative to a model M and to an item i that will be described shortly. Abusing notation, let us write [[φ]]_{M,i} for the interpretation of φ ∈ Φ relative to M and i, defending the abuse by arranging the interpretation of a formula in Φ_{0} to be independent of i,

[[θ]]_{M,i} = [[θ]]_{M}  for θ ∈ Φ_{0} .

(Similarly, for connectives from Φ_{0} such as ∨,

[[φ ∨ ψ]]_{M,i} = [[φ]]_{M,i} ∪ [[ψ]]_{M,i}

for all φ and ψ ∈ Φ, and not just in Φ_{0}.) It is natural to call a formula in Φ_{0} unambiguous inasmuch as its interpretation does not require the “disambiguating” item i.

1.1 Total disambiguations

The simplest example of item i considered below is a linear order ≺ on Φ disambiguating φ • ψ as follows:

[[φ • ψ]]_{M,≺} = \{ \begin{matrix}[[φ]]_{M,≺} & if φ ≺ ψ \\ [[ψ]]_{M,≺} & otherwise. \end{matrix}  (1)

(A similar meta-theoretic “or” connective is proposed in van Deemter [1], the additional step taken here being the introduction of the item i supporting its formal interpretation. The necessity of that additional material is the essential intuition behind the present work.^{2}) Up to semantic equivalence ≡_{M,≺}, defined by

∗My thanks to Hans Kamp, Peter Krause, Uwe Reyle, Emil Weydert and Ede Zimmermann for helpful discussions.

1Without loss of generality, let us insist that if the expression can also mean both, then the formula φ ∧ ψ should be added to the set of its disambiguations. The same goes for φ ∨ ψ.

φ ≡_{M,≺} ψ iff [[φ]]_{M,≺} = [[ψ]]_{M,≺} ,

the connective • is symmetric (because ≺ is anti-symmetric) and associative (because ≺ is transitive)

φ • ψ ≡_{M,≺} ψ • φ
θ • (φ • ψ) ≡_{M,≺} (θ • φ) • ψ .

The interpretation (1) of • is particularly natural in case [[φ]]_{M,≺} is an element of some set Ω, a proper subset true ⊂ Ω of which picks out the formulas “true” under that interpretation. Then the theory of a family M of models relative to a particular order (i.e., disambiguation) ≺ is

T h(M, ≺) = {φ : (∀M ∈ M) [[φ]]_{M,≺} ∈ true} .

A basic shortcoming of the interpretation (1) of • is the absence of a notion of context in disambiguating formulas.

For a context-dependent notion of disambiguation, let us fix a binary operation ^{∧} : Φ_{0} × Φ_{0} → Φ_{0} merging formulas, with the intuition that the first argument θ in θ^{∧}φ represents the context in which the second argument φ is asserted. Now, taking the item i to be a function θ ↦ ≺^{θ} from unambiguous formulas θ (∈ Φ_{0}) to orders ≺^{θ} on Φ, extend the operation ^{∧} to an operation ^{∧_{i}} : Φ_{0} × Φ → Φ_{0} relativized to i as follows

θ^{∧_{i}}(φ • ψ) = \{ \begin{matrix}θ^{∧_{i}}φ & if φ ≺^{θ} ψ \\ θ^{∧_{i}}ψ & otherwise \end{matrix}  (2)

for θ ∈ Φ_{0} and φ, ψ ∈ Φ. Note that the first argument of ^{∧_{i}} is unambiguous, as is the value assigned to θ^{∧_{i}}φ. The present paper concentrates on unambiguous contexts, touching only very briefly on ambiguous contexts (in §4.2).

1.2 Partial disambiguations

Ambiguity arises when there are two or more possible items (i, i′, …) to consider, suggesting an interpretation of a formula relative to a family of such items. Assuming an independent pairing of models with items, this step can, in turn, be analyzed by weakening an order ≺ on formulas to a binary relation R on formulas, families of which collapse to their unions or intersections. This assertion will be made precise in Propositions 5 and 6 below. For now, suffice it to say that a formula φ will be interpreted relative to a model M and binary relation R on formulas (in the case of context-independent disambiguation).

1.3 Outline of present paper

The present paper first considers context-independent disambiguation, investigating not only partiality but also the compositionality of the semantics. The paper then turns to the context-dependent theory, which arises from the context-independent case by shifting to a “dynamic” perspective (e.g., Kamp and Reyle [4]).

Henceforth, M will denote a (first-order) model, ≺ a linear order on Φ, referred to simply as an order, and R a binary relation on Φ.

2 Context-independent disambiguation

Throughout this section, we will assume an interpretation of • given by line (1) above, with [[φ]]_{M,R} ∈ {0, 1}, true = {1}, 0 = ∅ and 1 = {0} (so that ∨ is given by ∪, etc.).

2Van Deemter [1] also hints at an approach via modal logic, suggesting (as others have) that an expression ambiguous between φ and ψ be characterized as Mean(φ) ∨ Mean(ψ), rather than φ ∨ ψ (or Mean(φ ∨ ψ)). To what extent the present connective can be viewed in modal terms is taken up briefly in §4.1.

2.1 Compositionality examined locally

Call (M, ≺) composite if ≡_{M,≺} is a congruence with respect to • — or equivalently, there is some function ˆ• such that for all φ and ψ ∈ Φ,

[[φ • ψ]]_{M,≺} = [[φ]]_{M,≺} ˆ• [[ψ]]_{M,≺} .

Dropping subscripts for the sake of simplicity, note that to say that ≡ is a congruence with respect to • is to assert the following implication for all formulas φ, ψ, φ′ and ψ′,

\frac{φ ≺ ψ φ ≢ ψ φ′ ≡ φ ψ′ ≡ ψ}{φ′ ≺ ψ′} ,

whence

Proposition 1. (M, ≺) is composite iff there is a linear order < on the equivalence classes [φ] = {ψ : φ ≡_{M,≺} ψ} such that

≺ = {(φ, ψ) : φ ≢_{M,≺} ψ and [φ] < [ψ]} ∪ {(φ, ψ) : φ ≡_{M,≺} ψ and φ ≺ ψ} .

Indeed, given a model M, the orders ≺ that make (M, ≺) composite can be formed as follows. For every unambiguous formula φ ∈ Φ_{0}, let |φ| = {ψ ∈ Φ_{0} : φ ≡_{M} ψ}, and order {|φ| : φ ∈ Φ_{0}}. Following the inductive generation of formulas, throw in formulas with occurences of • into the appropriate equivalence classes |φ|, at the end ordering each enlarged equivalence class.

Of course, there is no reason to expect that a natural choice of (M, ≺) should be composite. One may argue that the compositionality of • is more suitably reconsidered “globally” over a collection of pairs (M, ≺).

2.2 Ambiguity through variation

Ambiguity arises when considering two or more disambiguations (i.e., orders). Relative to a collection I of pairs (M, ≺), the projections of the interpretations of φ are defined by

[[φ]]_{I}^{∃} = {M : [[φ]]_{M,≺} = 1 for some ≺ such that (M, ≺) ∈ I}
[[φ]]_{I}^{∀} = {M : [[φ]]_{M,≺} = 1 for all ≺ such that (M, ≺) ∈ I} ,

inducing obvious equivalences ≡_{I}^{∃} and ≡_{I}^{∀} on formulas. But first let us compare projections induced by different collections I and I′.

Proposition 2. Let O and O′ be two collections of orders on formulas, and let M be a family of models. Then

⋃ O = ⋃ O′ implies [[φ]]_{M×O}^{∃} = [[φ]]_{M×O′}^{∃}

and

⋂ O = ⋂ O′ implies [[φ]]_{M×O}^{∀} = [[φ]]_{M×O′}^{∀}

for every formula φ ∈ Φ.

The proof is trivial, although the following two points are perhaps worth making. The reference to cartesian products is crucial, as the argument breaks down if M × O is replaced by some complicated subset of it. Secondly, the converse fails already for the case of singleton families O, since the ordering between say •-free formulas φ and ψ that are equivalent in M makes no difference to the interpretation (over M) of φ • ψ.

Another useful fact is

Proposition 3. For all collections I and I′ (of model-order pairs) such that I ⊆ I′,

[[φ]]_{I}^{∃} ⊆ [[φ]]_{I′}^{∃}

and

[[φ]]_{I}^{∀} ⊇ [[φ]]_{I′}^{∀}

for every formula φ ∈ Φ.

Again, the proof is immediate, the crucial point being (as in Proposition 2) that [[φ]]_{I}^{Q} is determined “distributively” at each (M, ≺) ∈ I.

2.3 Compositionality reconsidered globally

A family M of models is fixed throughout this section. For Q ∈ {∃, ∀}, call a collection O of orders Qcomposite (relative to M) if ≡_{M×O}^{Q} is a congruence with respect to •. O is undecided on a pair φ, ψ of formulas if O has orders ≺ and ≺′ such that φ ≺ ψ and ψ ≺′ φ. O is undecided if it is undecided on every pair of distinct formulas (i.e., every pair (φ, ψ) of distinct formulas φ and ψ is in ⋃ O).

Proposition 4.

(i) If O is undecided on φ, ψ, then

[[φ • ψ]]_{M×O}^{∃} = [[φ]]_{M×O}^{∃} ∪ [[ψ]]_{M×O}^{∃}
[[φ • ψ]]_{M×O}^{∀} = [[φ]]_{M×O}^{∀} ∩ [[ψ]]_{M×O}^{∀} .

(ii) If O is undecided, then it is both ∃- and ∀-composite, and (assuming the usual semantics for ∨ and ∧)

φ • ψ ≡_{M×O}^{∃} φ ∨ ψ
φ • ψ ≡_{M×O}^{∀} φ ∧ ψ

for all formulas φ and ψ.

Proposition 4 lends some support to both disjunctive and conjunctive reductions of ambiguity. Of course, it is clear from the proof of Proposition 1 that union and intersection are not the only possible compositional interpretations of •.

For Q ∈ {∃, ∀}, a singleton set {≺} is typically not Q-composite, whence Propositions 3 and 4 suggest that if a collection O of orders is to be made Q-composite, then it is more promising to add orders to O than to take away orders from it.^{3} But is there a most economical method? Given a set O of orders, let

O^{Q} = ⋂{O′ : O′ ⊇ O and O′ is Q-composite} .

If O^{Q} is Q-composite, then it would certainly be the least one containing O. Unfortunately, the assumption may fail because

(†) two distinct orders can induce the same interpretation by differing on M-equivalent •-free formulas.

\frac{φ ≺ ψ φ ≢^{∃} ψ φ′ ≡^{∃} φ ψ′ ≡^{∃} ψ}{(∃ ≺′ ∈ O) φ′ ≺′ ψ′}

3The existential case is particularly simple, the condition that O is ∃-composite being captured precisely by the following implication (for all formulas φ, ψ, φ′ and ψ′, and every ≺ ∈ O)

(suppressing for notational simplicity the subscript M × O on ≡^{∃}).

2.4 From orders to normal relations

In view of Proposition 2 and (†), it is natural to interpret • relative to an arbitrary binary relation R on formulas. Proposition 4 suggests two possibilities, yielding two different connectives •_{∃} and •_{∀}^{4}

[[φ •_{∃} ψ]]_{M,R} = \{ \begin{matrix}[[φ]]_{M,R} & if φRψ but not ψRφ \\ [[ψ]]_{M,R} & if ψRφ but not φRψ \\ [[φ]]_{M,R} ∪ [[ψ]]_{M,R} & otherwise \end{matrix}

[[φ •_{∀} ψ]]_{M,R} = \{ \begin{matrix}[[φ]]_{M,R} & if φRψ but not ψRφ \\ [[ψ]]_{M,R} & if ψRφ but not φRψ \\ [[φ]]_{M,R} ∩ [[ψ]]_{M,R} & otherwise. \end{matrix}

A formula φ (built from •_{Q} rather than •) is interpreted relative to a family M of models and R in the obvious way

[[φ]]_{M,R} = {M ∈ M : [[φ]]_{M,R} = 1} .

Proposition 5. Given a non-empty family M of models and a non-empty family O of orders,

[[φ • ψ]]_{M×O}^{∃} = [[φ •_{∃} ψ]]_{M,∪O}
[[φ • ψ]]_{M×O}^{∀} = [[φ •_{∀} ψ]]_{M,∩O}

for all unambiguous formulas φ and ψ ∈ Φ_{0}.

Proof. Straightforward inspection of the cases: M ∈ [[φ • ψ]]_{M×O}^{Q} and M ∉ [[φ • ψ]]_{M×O}^{Q}, for Q ∈ {∃, ∀}. ⊣

In the case of ∀, Proposition 5 provides a linearization principle, under which a partial order can be reduced to its set of linearizations. But now, not only does Proposition 2 anticipate Proposition 5, it also suggests that a family R of relations be collapsed to its union ⋃ R or its intersection ⋂ R to capture the projections of the interpretations of a formula relative to a family I of pairs (M, R), where R ∈ R. (The essential difference here between orders and relations is that the latter are closed under unions and intersections.) Repeating the definition in §2.2 but this time for φ’s built from •_{∃} and •_{∀} (and ≺ weakened to R), set

[[φ]]_{I}^{∃} = {M : [[φ]]_{M,R} = 1 for some R such that (M, R) ∈ I}
[[φ]]_{I}^{∀} = {M : [[φ]]_{M,R} = 1 for all R such that (M, R) ∈ I} ,

an immediate consequence of which is

Proposition 6. Given a non-empty family M of models, and a non-empty family R of relations,

[[φ]]_{M×R}^{∃} = [[φ]]_{M,∪R}
[[φ]]_{M×R}^{∀} = [[φ]]_{M,∩R}

for every formula φ ∈ Φ.

To get rid of the annoying “but not …” clauses in the interpretation of •_{Q}, let us “normalize” a binary relation R on formulas to

R̂ = {(φ, ψ) : φRψ but not ψRφ} ,

observing that

[[φ]]_{M,R} = [[φ]]_{M,R̂}

for every formula φ. A relation R on Φ is said to be normal if R = R̂.

4To simplify the notation, we will reuse [[·]] for the present modification to relations, relying on context to determine the sense in which [[·]] is used, and appealing implicitly to the smooth generalization from the connective • to •_{∃} and •_{∀}. Also, it goes without saying that henceforth, the full set Φ of formulas refers to the result of closing the set Φ_{0} of unambiguous formulas under •_{∃} and •_{∀} (as well as the connectives from Φ_{0}).

2.5 Compositionality one more time

Given a family M of models, call a binary relation R on formulas Q-composite (relative to M) if ≡_{M,R} is a congruence relative to •_{Q}. R is composite if it is both ∃- and ∀-composite. Proposition 1 generalizes to

Lemma 7. Let M be a family of models, R be a normal relation, and R̃ be the binary relation {(φ, ψ) : φRψ and φ ≢_{M,R} ψ}.

(i) R is ∃-composite (relative to M) iff the implications

\frac{φR̃ψ φ′ ≡_{M,R} φ ψ′ ≡_{M,R} ψ}{not ψ′R̃φ′}

\frac{φR̃ψ φ′ ≡_{M,R} φ ψ′ ≡_{M,R} ψ not φ′R̃ψ′}{[[ψ]]_{M,R} ⊆ [[φ]]_{M,R}}

hold for all formulas φ, ψ, φ′ and ψ′.

(ii) R is ∀-composite iff the implications

\frac{φR̃ψ φ′ ≡_{M,R} φ ψ′ ≡_{M,R} ψ}{not ψ′R̃φ′}

\frac{φR̃ψ φ′ ≡_{M,R} φ ψ′ ≡_{M,R} ψ not φ′R̃ψ′}{[[φ]]_{M,R} ⊆ [[ψ]]_{M,R}}

hold for all formulas φ, ψ, φ′ and ψ′.

(iii) R is composite iff the implication

\frac{φR̃ψ φ′ ≡_{M,R} φ ψ′ ≡_{M,R} ψ}{φ′R̃ψ′}

holds for all formulas φ, ψ, φ′ and ψ′.

Proof. Under normality, parts (i) and (ii) follow easily from the definitions, while part (iii) is an immediate consequence of parts (i) and (ii). ⊣

The trivial relation on formulas that contains every pair of formulas is manifestly composite. Before passing to that relation, however, let us define the composite closure of a relation R (given a family M of models) to be the least relation containing R that is composite (relative to M). If it exists, it could only be

R^{M} = ⋂{R′ : R′ ⊇ R and R′ is composite relative to M} .

Examining the matter more constructively from the point of view of adding to R, it is somewhat disturbing to note that with every addition to R, [[φ •_{∃} ψ]]_{M,R} increases (or stays the same) whereas [[φ •_{∀} ψ]]_{M,R} decreases (or stays the same). By carefully applying, however, part (iii) of Lemma 7 (in accordance with the inductive generation of formulas), we can nevertheless establish

Theorem 8. Every normal relation R has a composite closure.

Proof. Fix a family M of models, and a normal relation R. We will construct R^{M} in stages such that

R^{M} = R ∪ ⋃_{n<ω} R_{n} ,

where

R_{0} ⊆ R_{1} ⊆ R_{2} ⊆ · · · .

Let R_{0} = R − {(φ, ψ) : φ ≡_{M,R} ψ}, and for every n, form R_{n+1} from R_{n} by applying an operation Θ that maps a binary relation R′ and a set Φ′ of formulas to the binary relation

{(φ′, ψ′) ∈ Φ′ × Φ′ : (∃φ, ψ) φR′ψ, φ′ ≡_{M,R′} φ, and ψ′ ≡_{M,R′} ψ}

derived from part (iii) of Lemma 7. More specifically, let

R_{n+1} = R_{n} ∪ Θ(R_{n}, Φ_{n})

where Φ_{0} is, as before, the set of unambiguous formulas, and

Φ_{n+1} = cl({φ •_{∃} ψ : φ, ψ ∈ Φ_{n}} ∪ {φ •_{∀} ψ : φ, ψ ∈ Φ_{n}})

and cl(Φ′) is the closure of Φ′ under all the logical connectives except •_{∃} and •_{∀}. Observe that ⋃_{n<ω} Φ_{n} includes all formulas, and that for every n and all φ and ψ in Φ_{n},

φ ≡_{M,R∪R_{n}} ψ iff (∀m > n) φ ≡_{M,R∪R_{m}} ψ

(i.e., R_{n+1} − R_{n} is disjoint from Φ_{n} × Φ_{n}), whence, writing R_{ω} for R ∪ ⋃_{n<ω} R_{n},

R_{ω} = Θ(R_{ω}, ⋃_{n<ω} Φ_{n}) .

That is, R_{ω} is composite, by Lemma 7, part (iii). Moreover, R_{ω} is the least extension of R that is composite because every R_{n} is disjoint from ≡_{M,R_{ω}}. ⊣

The case where R is not normal is left to the abnormal reader.

3 Context-dependent disambiguation

Let us now turn to an interpretation of • based on line (2). This interpretation builds on a binary operation ∧ : Φ_{0} × Φ_{0} → Φ_{0} that merges unambiguous formulas, the first argument of which is regarded as a context in which the second argument is uttered.

The step from the previous section to the present one can be reversed by freezing the present items i at some fixed context (or restricting to i’s that are constant functions). Keeping lessons from the contextindependent case in mind, let us define a context-dependent disambiguation to be a function i mapping an unambiguous formula θ ∈ Φ_{0} to a normal relation R^{θ} (on Φ), generalizing line (2) to

θ^{∧_{i}}(φ •_{∃} ψ) = \{ \begin{matrix}θ^{∧_{i}}φ & if φR^{θ}ψ \\ θ^{∧_{i}}ψ & if ψR^{θ}φ \\ θ^{∧_{i}}(φ ∨ ψ) & otherwise \end{matrix}

θ^{∧_{i}}(φ •_{∀} ψ) = \{ \begin{matrix}θ^{∧_{i}}φ & if φR^{θ}ψ \\ θ^{∧_{i}}ψ & if ψR^{θ}φ \\ θ^{∧_{i}}(φ ∧ ψ) & otherwise. \end{matrix}

Caution: it is understood above that ∨ is interpreted as union (or, as an operation on binary relations, non-deterministic choice), and ∧ as intersection (both of which would require extending the basic apparatus of Kamp and Reyle [4]). Assuming (as we will) that Φ is closed under ∨ and ∧, the equations above extend in a natural way^{5} to turn ^{∧_{i}} into a function from Φ_{0} × Φ into Φ_{0}.

θ^{∧_{i}}χ = \{ \begin{matrix}θ^{∧_{i}}(χ[φ •_{∃} ψ/φ]) & if φR^{θ}ψ \\ θ^{∧_{i}}(χ[φ •_{∃} ψ/ψ]) & if ψR^{θ}φ \\ θ^{∧_{i}}(χ[φ •_{∃} ψ/φ ∨ ψ]) & otherwise \end{matrix}

5More precisely, for all formulas φ, ψ and χ ∈ Φ, assert and similarly for •_{∀}, where χ[φ/ψ] is χ with all occurrences of φ replaced by ψ.

3.1 Representing context change potentials

This subsection draws on Fernando [2] to relate the merge ^{∧} : Φ_{0} ×Φ_{0} → Φ_{0} to an interpretation of a formula φ ∈ Φ_{0} as a context change potential (CCP) P (φ) ⊆ WSP × WSP on a collection WSP of world-sequence pairs (wsp’s). To be more precise, fix a family M of first-order models, and let WSP be the collection of pairs (M, f) where M ∈ M, and f is a partial function from the set of variables (from which formulas in Φ_{0} are constructed) to the universe of M. To simplify notation, we will regard, in the sequel, a wsp (M, f) as a model over an expanded signature, and assume that WSP = M, with variables occurring freely treated as constants. Now, the intuition behind a CCP P (φ) is that it specifies the input/output relation of φ, extending the interpretation [[φ]]_{M} of unambiguous formulas φ ∈ Φ_{0} analyzed in the previous section, by returning outputs precisely on inputs M ∈ M at which φ is true

[[φ]]_{M} = 1 iff M ∈ dom(P (φ)) .

The merge operation ^{∧} is interpreted (“sequentially” or “incrementally”) by P as relational composition ∘, where, by definition, R ∘ R′ = {(a, b) : (∃c) aRc and cR′b}. Adding further assumptions on P, let us record these together as

Assumptions (in force throughout this section). For all φ and θ ∈ Φ_{0},

(A1)  dom(P (φ)) = {M ∈ M : [[φ]]_{M} = 1}
(A2)  P (θ^{∧}φ) = P (θ) ∘ P (φ)
(A3)  P (¬φ) = {(M, M) : M ∈ M − dom(P (φ))}

for some unary connective ¬ under which Φ_{0} is assumed to be closed. Furthermore,

(A0)  there is a formula ⊤ ∈ Φ_{0} s.t. P (⊤) = {(M, M) : M ∈ M} .

Assumption (A1) suggests a definition of the set Φ_{M} ⊆ Φ_{0} of M-absurd formulas as follows

Φ_{M} = {φ ∈ Φ_{0} : (∀M ∈ M) M ∉ dom(P (φ))} .

With (A1) in mind, define the equivalence ≡_{M} on Φ by

φ ≡_{M} ψ iff dom(P (φ)) = dom(P (ψ)) .

Proposition 9. For all φ, ψ ∈ Φ_{0},

φ ≡_{M} ψ iff (∀θ ∈ Φ_{0}) (θ^{∧}φ ∈ Φ_{M} iff θ^{∧}ψ ∈ Φ_{M}) .

Proof. The forward implication ⇒ follows immediately from (A1) and (A2). For the converse, suppose φ ≢_{M} ψ, say, M ∈ dom(P (φ)) − dom(P (ψ)). Then, appealing to (A3), take θ to be ¬ψ. ⊣

As an equivalence on (unambiguous) formulas, ≡_{M} abstracts away the dynamic effects of the CCP’s inasmuch as

¬¬φ ≡_{M} φ

for every φ ∈ Φ_{0}. Complementing the equivalence ≡_{M} on Φ_{0} is the equivalence ≡^{M} on Φ_{0} testing the other side of ^{∧}

θ ≡^{M} ρ iff (∀φ ∈ Φ_{0}) (θ^{∧}φ ∈ Φ_{M} iff ρ^{∧}φ ∈ Φ_{M}) ,

which may very well be distinct since relational composition is typically not commutative.^{6} Now, how do the equivalences ≡_{M} and ≡^{M} behave relative to the merge ^{∧}? It is immediate that

\frac{θ ≡^{M} ρ φ ≡_{M} ψ}{θ^{∧}φ ∈ Φ_{M} iff ρ^{∧}ψ ∈ Φ_{M}} .  (3)

to a proper subset of M).

6Defining ima(P (φ)) to be {M′ : (∃M ∈ M) M P (φ) M′}, it is immediate that ima(P (θ)) = ima(P (ρ)) implies θ ≡^{M} ρ.

For the converse, however, it would be helpful to have a connective dual to ¬, or further assumptions such as in, for example, Fernando [2] (concerning which note that ima(P (φ)) is different from D[P (φ)](σ_{∘}), as defined there, since σ_{∘} corresponds only

To conclude further, under the same premisses, that θ^{∧}φ ≡_{M} ρ^{∧}ψ, it suffices (by (3), (A2) and the associativity of ∘) that for all θ′, θ′^{∧}θ ≡^{M} θ′^{∧}ρ. Similarly, to deduce θ^{∧}φ ≡^{M} ρ^{∧}ψ, it is enough that φ^{∧}φ′ ≡_{M} ψ^{∧}φ′ for all φ′. Now, certainly

\frac{θ ≡^{M} ρ}{θ^{∧}θ′ ≡^{M} ρ^{∧}θ′}  \frac{φ ≡_{M} ψ}{φ′^{∧}φ ≡_{M} φ′^{∧}ψ}

and again the possibility that ^{∧} is non-commutative prevents us from strengthening the conclusion of (3) to θ^{∧}φ ≡_{M} ρ^{∧}ψ and θ^{∧}φ ≡^{M} ρ^{∧}ψ (which would then mean, by (A0), that ≡^{M} is identical with ≡_{M}). Rather than assuming ^{∧} is commutative, let us instead add

(A4)  \frac{θ ≡^{M} ρ θ ≡_{M} ρ}{θ′^{∧}θ ≡^{M} θ′^{∧}ρ}  \frac{φ ≡^{M} ψ φ ≡_{M} ψ}{φ^{∧}φ′ ≡_{M} ψ^{∧}φ′}

to the list of assumptions above.^{7} The preceding discussion then yields

Proposition 10. The equivalence ≡_{M} ∩ ≡^{M} is a congruence relative to ^{∧}. In particular, the implications

\frac{θ ≡^{M} ρ θ ≡_{M} ρ φ ≡_{M} ψ}{θ^{∧}φ ≡_{M} ρ^{∧}ψ}

and

\frac{θ ≡^{M} ρ φ ≡^{M} ψ φ ≡_{M} ψ}{θ^{∧}φ ≡^{M} ρ^{∧}ψ}

hold for all θ, ρ, φ and ψ ∈ Φ_{0}.

Next, let us bring into the picture a context-dependent disambiguation i. Replacing ^{∧} by ^{∧_{i}}, the equivalence ≡_{M} on Φ_{0} extends to an equivalence ≡_{M,i} on Φ

φ ≡_{M,i} ψ iff (∀θ ∈ Φ_{0}) (θ^{∧_{i}}φ ∈ Φ_{M} iff θ^{∧_{i}}ψ ∈ Φ_{M}) .

Proposition 11. Given a normal relation R on Φ, let i^{R} be the context-dependent [sic] disambiguation that maps every unambiguous formula to R. Then, the equivalence ≡_{M,R} (from the previous section) is identical to the equivalence ≡_{M,i^{R}} —

φ ≡_{M,i^{R}} ψ iff φ ≡_{M,R} ψ

for all φ and ψ ∈ Φ.

As for the equivalence ≡^{M}, the point is to extend the bounded quantification on Φ_{0} to Φ. That is, let ≡^{M,i} be the equivalence on Φ_{0} given by

θ ≡^{M,i} ρ iff (∀φ ∈ Φ) (θ^{∧_{i}}φ ∈ Φ_{M} iff ρ^{∧_{i}}φ ∈ Φ_{M}) .

Proposition 12. For every context-dependent disambiguation i,

(i) ≡^{M,i} ⊆ ≡^{M}, and

(ii) ≡^{M} ⊈ ≡^{M,i} iff for some φ ∈ Φ, ≡^{M} is not a congruence with respect to ^{∧_{i}}φ.

The proof is immediate, with (A0) useful for part (ii).

7A model for (A0) to (A4) can be built from Kamp and Reyle [4], with

φ ≡^{M} ψ and φ ≡_{M} ψ iff P (φ) = P (ψ) , as explained in Fernando [2].

3.2 Composite disambiguation

Fix a family M of models, and a context-dependent disambiguation i : θ ↦ R^{θ}. Call i M-composite if (i) ≡_{M,i} is a congruence relative to •_{∃} and •_{∀}, (ii) the rule

\frac{θ ≡^{M} ρ θ ≡_{M} ρ φ ≡_{M,i} ψ}{θ^{∧_{i}}φ ≡_{M,i} ρ^{∧_{i}}ψ}

holds for all θ and ρ ∈ Φ_{0} and all φ and ψ ∈ Φ, and (iii) ≡^{M} identical to ≡^{M,i}.^{8} Two unambiguous formulas θ and ρ are (i, M)-similar if

(i) ≡_{M,R^{θ}} and ≡_{M,R^{ρ}} are the same, and, calling that equivalence ≡, (ii) the implications

\frac{θ^{∧}φ ≢ ρ^{∧}ψ φR^{θ}ψ φ′ ≡ φ ψ′ ≡ ψ}{φ′R^{ρ}ψ′}

and

\frac{θ^{∧}φ ≢ ρ^{∧}ψ φR^{ρ}ψ φ′ ≡ φ ψ′ ≡ ψ}{φ′R^{θ}ψ′}

hold for all formulas φ, ψ, φ′ and ψ′ ∈ Φ. Theorem 13. Given a family M of models, a context-dependent disambiguation i is M-composite iff ≡^{M,i} is ≡^{M}, and for all θ and ρ ∈ Φ_{0}, if θ ≡^{M} ρ and θ ≡_{M} ρ, then θ and ρ are (i, M)-similar. (Proof. Long, using Lemma 7 and Propositions 9 to 12.)

Partially ordering context-dependent disambiguations (i and i′) pointwise,

i ≤ i′ iff (∀θ ∈ Φ_{0}) i(θ) ⊆ i′(θ) ,

and defining the M-composite closure of i to be the ≤-least M-composite context-dependent disambiguation i′ such that i ≤ i′, Theorem 13 yields Corollary 14. For every family M of models, every context-dependent disambiguation i has an Mcomposite closure. ¿From the construction of a composite closure (see the proof of Theorem 8), it follows that composite i’s are determined at the unambiguous formulas. For example, there is a unique composite disambiguation θ ↦ R^{θ} such that for unambiguous φ, θ and ψ,

φR^{θ}ψ iff θ^{∧}φ ⊑^{M} θ^{∧}ψ ,

where ⊑^{M} is the pre-order

θ ⊑^{M} ρ iff (∀φ ∈ Φ_{0}) (θ^{∧}φ ∈ Φ_{M} implies ρ^{∧}φ ∈ Φ_{M})

on Φ_{0}, for which ≡^{M} can be decomposed as ⊑^{M} ∩ ⊒^{M}. Of course, we might be interested more widely in disambiguations whose θth relation includes R^{θ} (plus possibly any number of other constraints).

\frac{θ ≡^{M} ρ φ ≡^{M} ψ φ ≡_{M,i} ψ}{θ^{∧_{i}}φ ≡^{M} ρ^{∧_{i}}ψ} ,

8We make do with this condition, because of the problem in extending ≡^{M} to Φ − Φ_{0}, to formulate the extension, of the second rule in Proposition 10. See §4.2.

4 Discussion

The present work approaches the problem of ambiguity from a semantic standpoint, freely generating finite sets of unambiguous formulas under the hypothesis that two ambiguous expressions with the same set of unambiguous formulas have the same meaning. This is not to deny that there may well be more to a natural language expression than its set of disambiguated meanings; merely a claim that the “semantic” projection of an expression is determined by that set — stopping short of a disjunctive view of ambiguity that equates say {φ, ψ} semantically with {φ ∨ ψ}. An evaluation of this claim would require an account (completely missing above) of how such sets of unambiguous formulas arise (e.g., through scope ambiguities).

Such an account would presumably build on methods from linguistics beyond the scope of the present work. Concentrating on purer matters of logic, we might (as suggested by P. Krause) ask

In what sense can the constructs •_{∃} and •_{∀} be described as logical connectives?

Interpreting these constructs requires adding (in the simplest case) a binary relation to a model — which is broadly reminiscent of Kripke semantics for modal logic. The basic difference, however, is that in the present case, the binary relation is imposed on formulas, rather than on semantic entities (called worlds). This gives rise to the question as to whether semantic equivalence is a congruence with respect to these connectives — a question to which the bulk of the present work is addressed.

4.1 Variations on a theme from Kripke

Insofar as the interpretations of •_{∃} and •_{∀} depend on a disambiguation in the same way that the existential and universal modalities in modal logic depend on an accessibility relation, it is natural to frame the problem of

(∗)  axiomatizing •_{∃} and •_{∀} on the basis of properties imposed on the disambiguations.

For starters, it is easy enough to see that if a normal relation R is transitive, then the interpretation of •_{Q} (relative to R) is associative; and if R is symmetric, then its normalization R̂ is empty, and •_{Q} becomes either ∨ or ∧.^{9} The problem (∗) can also be posed globally, interpreting •_{Q} relative to a family I of pairs (M, R) where R has the prescribed properties. If I is a cartesian product M×R, then Proposition 6 suggests collapsing R to either ⋃ R or ⋂ R. But what if I does not have such a form? Presumably, the arguments would grow in complexity as M must be varied along with R. For instance, given a collection Φ̂ of formulas, call (M, R) Φ̂-charitable if for all φ and ψ ∈ Φ̂,

[[φ ∧ ¬ψ]]_{M,R} = 1 implies φRψ .

Rather than considering Φ̂-charitable pairs, the notion of charity can also (and arguably more naturally) be phrased relative to a family M of models as follows: a relation R is (M, Φ̂)-charitable if for all φ and ψ ∈ Φ̂,

[[φ ∧ ¬ψ]]_{M,R} = M implies φRψ ,

so that R need not depend on a fixed M ∈ M (but rather on M as a whole). In any case, neither definition of charity captures the importance of context, concerning which, I think the example in the last paragraph of §3.2 comes closest (degenerating to the second notion of charity above, if the context is frozen).^{10} We can go on, but for now let us just say that the matter of choosing “interesting” collections I of pairs (M, i) and investigating the associated theories

Q(I) = {φ : (∀(M, i) ∈ I) M ∈ [[φ]]_{I}^{Q}}

9A particularly natural property (that vaguely smells of compositionality) is that R satisfy the following condition:

φ_{1}Rψ_{1}, … and φ_{n}Rψ_{n} imply α(φ_{1}, …, φ_{n}) R α(ψ_{1}, …, ψ_{n})

for every n-ary connective α.

10Another constraint on disambiguation mentioned in van Deemter [1] is “a tendency towards equal interpretation of different occurrences of a given expression throughout a discourse” (§5.1) called coherence. Under the present approach, coherence suggests a stability during the interpretation of a discourse in either the context or the disambiguations determined by the evolving contexts.

for Q ∈ {∃, ∀} is begging for attention. Just as modal logic can be analyzed in a first-order language (if not a first-order logic), so too might the present systems, the main difference, to repeat, being that the relations are defined on formulas (or, assuming composite interpretations, on particularly simple sets of worlds), rather than on worlds.

4.2 Further work: ambiguous contexts and some generalizations

It is curious, as pointed out to the author by U. Reyle, that the first argument of ^{∧_{i}} should be restricted to unambiguous formulas (∈ Φ_{0}). The reason is that an assumption of total disambiguation is built in by the requirement that every pair (θ, φ) in Φ_{0} × Φ be mapped by ^{∧_{i}} into an unambiguous formula. But suppose θ^{∧_{i}}φ can be ambiguous, delaying its disambiguation until further information is available. Then it is only sensible to expand the domain of ^{∧_{i}} from Φ_{0} × Φ to Φ × Φ. More precisely, allowing the value R^{θ} of a disambiguation i at θ to be abnormal, define

θ^{∧_{i}}(φ •_{∃} ψ) = \{ \begin{matrix}θ^{∧_{i}}φ & if φR^{θ}ψ but not ψR^{θ}φ \\ θ^{∧_{i}}ψ & if ψR^{θ}φ but not φR^{θ}ψ \\ θ^{∧_{i}}(φ ∨ ψ) & if ψR^{θ}φ and φR^{θ}ψ \\ θ^{∧_{i}}(φ •_{∃} ψ) & otherwise \end{matrix}

θ^{∧_{i}}(φ •_{∀} ψ) = \{ \begin{matrix}θ^{∧_{i}}φ & if φR^{θ}ψ but not ψR^{θ}φ \\ θ^{∧_{i}}ψ & if ψR^{θ}φ but not φR^{θ}ψ \\ θ^{∧_{i}}(φ ∧ ψ) & if ψR^{θ}φ and φR^{θ}ψ \\ θ^{∧_{i}}(φ •_{∀} ψ) & otherwise \end{matrix}

so that if neither φRψ nor ψRφ, then the disambiguation of φ•_{Q} ψ is postponed. Further generalizations are provided by taking i(θ) to be a function from Φ × Φ to Φ, allowing i(θ)(φ, ψ) to be some formula other than φ or ψ that presumably resolves only part of the ambiguity in φ •_{Q} ψ. In addition to extending the domain of i to Φ, some mechanism for disambiguating contexts must also be introduced that complements i. Clearly, the present work is at best an initial step towards a formal analysis of the interpretation of ambiguity, a more general approach to which is adopted in Fernando [3].

References

[1] Kees van Deemter. Towards a logic of ambiguous expressions. Manuscript, 1994. To be revised into a paper to appear in a CSLI Lecture Note.

[2] Tim Fernando. Are context change potentials functions? Manuscript, distributed at a workshop on context dependency in Prague, 1995.

[3] Tim Fernando. Ambiguity under changing contexts. Manuscript, 1995. To be presented in Mathematics of Language 4, Philadelphia, October 1995.

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

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