\documentstyle[11pt]{article}
\oddsidemargin=0in % 1'' left margin.
\textwidth=6.5in % 6.5'' line width.
\topmargin=0in % 1'' top margin.
\headheight=0in % No page head.
\headsep=0in % No space below page head.
\textheight=9in % 9'' page body height.
% \pagestyle{empty} % No page numbers.
\parindent=0.7cm % 0.7cm paragraph indentation.
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\renewcommand{\models}{\mathrel|\mathrel{\mkern-4mu}=}
\newcommand{\intp}[1]{[\![#1]\!]}
\newcommand{\ov}[1]{\overline{#1}}
\newcommand{\dom}{\mbox{{\it dom\/}}}
\newcommand{\Pow}{\mbox{{\sf Pow}}}
\newcommand{\true}{\mbox{{\sf true}}}
\newcommand{\WSP}{\mbox{{\sf WSP}}}
\newcommand{\Oh}{{\cal O}}
\newcommand{\inisig}{\sigma_\circ}
\newcommand{\ima}{\mbox{{\it ima\/}}}
\begin{document}
\title{A logical connective for ambiguity requiring disambiguation}
\author{Tim Fernando\thanks{
My thanks to Hans Kamp, Peter Krause,
Uwe Reyle, Emil Weydert and Ede Zimmermann for helpful discussions.}
\\
{\tt fernando@ims.uni-stuttgart.de}
}
\date{{\small For the 2nd Conference on Information-Theoretic Approaches
to Logic, Language and Computation}}
\maketitle
\section{Introduction: ambiguity and disambiguation}
The idea of analyzing an expression as the (ordinary object level)
disjunction of its disambiguations has been criticized
on the grounds of both computational intractability
and logical untenability
(e.g., Reyle \cite{Rey93}, van Deemter \cite{vDe94}).
Concentrating on the latter,
let us fix a set $\Phi_0$ of formulas,
closed under disjunction $\vee$,
and a semantic interpretation $\intp{\varphi}_M$ of
formulas $\varphi \in \Phi_0$
relative to a first-order model $M$, under which
the disjunction $\varphi \vee \psi$ of two
formulas $\varphi$ and $\psi \in \Phi_0$ is
interpreted by the operation $\cup$ of union,
\begin{eqnarray*}
\intp{\varphi \vee \psi}_M
& = &
\intp{\varphi}_M \cup \intp{\psi}_M \ .
\end{eqnarray*}
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 $\varphi$ and $\psi \in \Phi_0$ and
all models $M$,
$\intp{\varphi \vee \psi}_M = F(\intp{\varphi}_M,\intp{\psi}_M)$.
That is, the interpretations of $\varphi$ and $\psi$
unambiguously determine that of $\varphi \vee psi$,
suggesting that
the disjunction of two unambiguous formulas is also unambiguous.
By contrast, an expression that is ambiguous between (say) two unambiguous
formulas $\varphi$ and $\psi$ should be interpreted
as either $\varphi$ or $\psi$ (but not both\footnote{Without loss
of generality, let us insist that if the expression can
also mean both, then the formula $\varphi \wedge \psi$
should be added to the set of its disambiguations.
The same goes for $\varphi \vee \psi$.})
according to some unspecified information that
must be supplied at the meta-level.
With this in mind, let us introduce a binary connective $\bullet$ that is
interpreted relative % not only to a model $M$, but
also to some item $i$ embodying that information.
More precisely, let $\Phi$ be the closure of $\Phi_0$
under $\bullet$ as well as the connectives in $\Phi_0$,
with each formula in $\Phi$ interpreted
relative to a model $M$ and to an item $i$ that will be described shortly.
Abusing notation, let us write $\intp{\varphi}_{M,i}$
for the interpretation of $\varphi \in \Phi$ relative to $M$ and $i$,
defending the abuse by arranging the interpretation of a formula
in $\Phi_0$ to be independent of $i$,
\begin{eqnarray*}
\intp{\theta}_{M,i}
& = &
\intp{\theta}_{M} \ \hspace{.3in} \mbox{for } \theta \in \Phi_0 \ .
\end{eqnarray*}
(Similarly, for connectives from $\Phi_0$ such as $\vee$,
$\intp{\varphi \vee \psi}_{M,i}
= \intp{\varphi}_{M,i} \cup
\intp{\psi}_{M,i}$,
for all $\varphi$ and $\psi \in \Phi$, and not just in $\Phi_0$.)
It is natural to call a formula in $\Phi_0$ {\em unambiguous\/}
inasmuch as its interpretation does not require
the ``disambiguating'' item $i$.
\subsection{Total disambiguations}
The simplest example of item $i$ considered below
is a linear order $\prec$ on $\Phi$
disambiguating $\varphi \bullet \psi$ as follows:
\begin{eqnarray}
\intp{\varphi \bullet \psi}_{M,\prec}
& = & \left\{ \begin{array}{ll}
\intp{\varphi}_{M,\prec} \ \
& \mbox{ if } \varphi \prec \psi \\
\intp{\psi}_{M,\prec} \ \
& \mbox{ otherwise.}
\end{array}
\right.
\end{eqnarray}
(A similar meta-theoretic ``or'' connective is proposed
in van Deemter \cite{vDe94}, 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.\footnote{
Van Deemter \cite{vDe94} also hints at an approach via modal logic,
suggesting (as others have) that an expression ambiguous between
$\varphi$ and $\psi$ be characterized as
Mean$(\varphi) \vee \mbox{Mean}(\psi)$,
rather than $\varphi \vee \psi$ (or Mean($\varphi \vee \psi$)).
To what extent the present connective can be viewed in modal
terms is taken up briefly in $\S 4.1$.
})
Up to semantic equivalence $\equiv_{M,\prec}$, defined by\begin{eqnarray*}
\varphi \equiv_{M,\prec} \psi
& \mbox{ iff } &
\intp{\varphi}_{M,\prec} = \intp{\psi}_{M,\prec} \ ,
\end{eqnarray*}
the connective $\bullet$ is
symmetric (because $\prec$ is anti-symmetric)
and associative (because $\prec$ is transitive)
\begin{eqnarray*}
\varphi \bullet \psi & \equiv_{M,\prec} & \psi \bullet \varphi \\
\theta \bullet (\varphi \bullet \psi) & \equiv_{M,\prec} & (\theta
\bullet \varphi) \bullet \psi \ .
\end{eqnarray*}
The interpretation (1) of $\bullet$
is particularly natural in case
$\intp{\varphi}_{M,\prec}$ is an element
of some set $\Omega$, a proper subset $\true \subset \Omega$
of which picks out the formulas ``true'' under that interpretation.
Then the theory of
a family ${\cal M}$ of models
relative to a particular order (i.e., disambiguation)
$\prec$ is
\begin{eqnarray*}
Th({\cal M},\prec) & = &
\{\varphi
\ : \
(\forall M \in {\cal M}) \
\intp{\varphi}_{M,\prec} \in \true
\} \ .
\end{eqnarray*}
A basic shortcoming of the interpretation (1) of $\bullet$
is the absence of a notion of context in disambiguating formulas.
\medskip
For a context-dependent notion of disambiguation,
let us fix a binary operation
$^\wedge: \Phi_0 \times \Phi_0 \ra \Phi_0$
{\em merging\/} formulas,
with the intuition that the first argument $\theta$ in
$\theta ^\wedge \varphi$
represents the context in which the second argument
$\varphi$ is asserted.
Now, taking the item $i$ to be a
function $\theta \mapsto \ \prec^{\theta}$
from unambiguous formulas $\theta$ ($\in \Phi_0$) to orders $\prec^{\theta}$
on $\Phi$, extend the operation $^\wedge$
to an operation $^{\wedge_i}: \Phi_0 \times \Phi \ra \Phi_0$
relativized to $i$ as follows
\begin{eqnarray}
\theta ^{\wedge_i} (\varphi\bullet \psi)
& = &
\left\{ \begin{array}{ll}
\theta ^{\wedge_i} \varphi \ \
& \mbox{ if } \varphi \prec^{\theta} \psi \\
\theta ^{\wedge_i} \psi \ \
& \mbox{ otherwise}
\end{array}
\right.
\end{eqnarray}
for $\theta \in \Phi_0$ and $\varphi,\psi \in \Phi$.
Note that the first argument of $^{\wedge_i}$ is unambiguous,
as is the value assigned to $\theta^{\wedge_i}\varphi$.
The present paper concentrates on unambiguous contexts,
touching only very briefly
on ambiguous contexts (in $\S 4.2$).
\subsection{Partial disambiguations}
Ambiguity arises when there are two or more possible items ($i,i',\ldots$)
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 $\prec$ 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 $\varphi$ will be interpreted
relative to a model $M$ and binary relation $R$ on formulas
(in the case of context-independent disambiguation).
\subsection{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 \cite{KR:book}).
\medskip
Henceforth, $M$ will denote a (first-order) model,
$\prec$ a linear order on $\Phi$, referred to simply
as an order, and $R$ a binary relation on $\Phi$.
\section{Context-independent disambiguation}
Throughout this section, we will
assume an interpretation of $\bullet$ given by line (1) above,
with $\intp{\varphi}_{M,R} \in \{0,1\}$,
$\true = \{1\}$, $0 =\emptyset$ and $1=\{0\}$
(so that $\vee$ is given by $\cup$, etc.).
\subsection{Compositionality examined locally}
Call $(M,\prec)$ {\em composite\/} if
$\equiv_{M,\prec}$ is a congruence with respect to $\bullet$
--- or equivalently, there is some function $\hat{\bullet}$ such that for all
$\varphi$ and $\psi \in \Phi$,
\begin{eqnarray*}
\intp{\varphi \bullet \psi}_{M,\prec} & = &
\intp{\varphi}_{M,\prec} \ \hat{\bullet} \ \intp{\psi}_{M,\prec} \ .
\end{eqnarray*}
Dropping subscripts for the sake of simplicity, note that
to say that $\equiv$ is a congruence with respect to
$\bullet$ is to assert the following implication for all
formulas $\varphi, \psi,\varphi'$ and $\psi'$,
\[
\frac{\varphi \prec \psi
\ \ \ \ \varphi \not\equiv \psi
\ \ \ \ \varphi' \equiv \varphi
\ \ \ \ \psi' \equiv \psi}{\varphi' \prec \psi'} \ ,
\]
whence
\medskip
\noindent
{\bf Proposition 1}.
{\sl $(M,\prec)$ is composite iff there is a linear order
$<$ on the equivalence classes
$[\varphi] = \{\psi : \varphi \equiv_{M,\prec} \psi\}$
such that
\begin{eqnarray*}
\prec & = &
\{(\varphi,\psi) \ : \
\varphi \not\equiv_{M,\prec} \psi
\mbox{ and }
[\varphi] < [\psi]\}
\ \ \cup \ \
\{(\varphi,\psi) \ : \
\varphi \equiv_{M,\prec} \psi
\mbox{ and }
\varphi \prec \psi\} \ .
\end{eqnarray*}
\/}
\noindent
Indeed, given a model $M$, the orders $\prec$ that
make $(M,\prec)$ composite can be formed as follows.
For every unambiguous formula $\varphi \in \Phi_0$, let
$|\varphi| = \{\psi \in \Phi_0 : \varphi \equiv_M \psi\}$, and
order $\{|\varphi| : \varphi \in \Phi_0\}$.
Following the inductive generation of formulas,
throw in formulas with occurences of $\bullet$ into
the appropriate equivalence classes $|\varphi|$,
at the end ordering each enlarged equivalence class.
\medskip
Of course, there is no reason to expect that a natural choice of
$(M,\prec)$ should be composite. One may argue that the
compositionality of $\bullet$ is more suitably reconsidered
``globally'' over a collection of pairs $(M,\prec)$.
\subsection{Ambiguity through variation}
Ambiguity arises when considering two or more
disambiguations (i.e., orders).
Relative to a collection ${\cal I}$ of pairs $(M,\prec)$,
the projections of the interpretations of $\varphi$
are defined by
\begin{eqnarray*}
\intp{\varphi}_{{\cal I}}^\exists
& = &
\{M \ : \
\intp{\varphi}_{M,\prec} = 1 \mbox{ for some $\prec$ such that }
(M,\prec) \in {\cal I}
\} \
\\
\intp{\varphi}_{{\cal I}}^\forall
& = &
\{M \ : \
\intp{\varphi}_{M,\prec} = 1 \mbox{ for all $\prec$ such that }
(M,\prec) \in {\cal I}
\} \ ,
\end{eqnarray*}
inducing obvious equivalences $\equiv^\exists_{\cal I}$ and
$\equiv^\forall_{\cal I}$ on formulas.
But first let us compare projections induced by different collections
${\cal I}$ and ${\cal I}'$.
\medskip
\noindent
{\bf Proposition 2}.
{\sl Let $\Oh$ and $\Oh'$ be two collections of orders on formulas,
and let ${\cal M}$ be a family of models. Then
\begin{eqnarray*}
\bigcup \Oh
= \bigcup \Oh'
& \mbox{ implies } &
\intp{\varphi}^\exists_{{\cal M} \times \Oh}
=
\intp{\varphi}^\exists_{{\cal M} \times \Oh'}
\end{eqnarray*}
and
\begin{eqnarray*}
\bigcap \Oh
= \bigcap \Oh'
& \mbox{ implies } &
\intp{\varphi}^\forall_{{\cal M} \times \Oh}
=
\intp{\varphi}^\forall_{{\cal M} \times \Oh'}
\end{eqnarray*}
for every formula $\varphi \in \Phi$.}
\medskip
\noindent
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
${\cal M} \times \Oh$ is replaced by
some complicated subset of it.
Secondly, the converse fails
already for the case of singleton families $\Oh$,
since the ordering between say $\bullet$-free formulas $\varphi$
and $\psi$ that are equivalent
in ${\cal M}$ makes no difference to the interpretation (over ${\cal M}$)
of $\varphi \bullet \psi$.
\medskip
Another useful fact is
\medskip
\noindent
{\bf Proposition 3}.
{\sl For all collections ${\cal I}$ and ${\cal I}'$
(of model-order pairs) such that
${\cal I} \subseteq {\cal I}'$,
\begin{eqnarray*}
\intp{\varphi}^\exists_{{\cal I}}
\ \subseteq \
\intp{\varphi}^\exists_{{\cal I}'}
& \mbox{ and } &
\intp{\varphi}^\forall_{{\cal I}}
\ \supseteq \
\intp{\varphi}^\forall_{{\cal I}'}
\end{eqnarray*}
for every formula $\varphi \in \Phi$.\/}
\medskip
\noindent
Again, the proof is immediate, the crucial point being
(as in Proposition 2) that
$\intp{\varphi}^Q_{\cal I}$
is determined ``distributively'' at each $(M,\prec) \in {\cal I}$.
\subsection{Compositionality reconsidered globally}
A family ${\cal M}$ of models is fixed throughout this section.
For $Q \in \{\exists,\forall\}$,
call a collection $\Oh$ of orders
{\em $Q$-composite\/} (relative to ${\cal M}$)
if $\ \equiv^Q_{{\cal M} \times \Oh}$ is
a congruence with respect to $\bullet$.
$\Oh$ is {\em undecided on\/} a pair $\varphi,\psi$
of formulas if $\Oh$ has orders $\prec$ and
$\prec'$ such that $\varphi \prec \psi$
and $\psi \prec' \varphi$.
$\Oh$ is {\em undecided\/} if
it is undecided on every pair of distinct formulas
(i.e., every pair $(\varphi,\psi)$
of distinct formulas $\varphi$ and $\psi$ is in
$\bigcup \Oh$).
\medskip
\noindent
{\bf Proposition 4}.
{\sl
\begin{itemize}
\item[(i)]
If $\Oh$ is undecided on $\varphi,\psi$, then
\begin{eqnarray*}
\intp{\varphi \bullet \psi}^\exists_{{\cal M} \times {\Oh}}
& = &
\intp{\varphi}^\exists_{{\cal M} \times {\Oh}}
\cup
\intp{\psi}^\exists_{{\cal M} \times {\Oh}}
\\
\intp{\varphi \bullet \psi}^\forall_{{\cal M} \times {\Oh}}
& = &
\intp{\varphi}^\forall_{{\cal M} \times {\Oh}}
\cap
\intp{\psi}^\forall_{{\cal M} \times {\Oh}} \ .
\end{eqnarray*}
\item[(ii)]
If $\Oh$ is undecided, then it is
both $\exists$- and $\forall$-composite, and
(assuming the usual semantics for $\vee$ and $\wedge$)
\begin{eqnarray*}
\varphi \bullet \psi
& \equiv^\exists_{{\cal M} \times {\Oh}} &
\varphi \vee \psi \\
\varphi \bullet \psi
& \equiv^\forall_{{\cal M} \times {\Oh}} &
\varphi \wedge \psi \
\end{eqnarray*}
for all formulas $\varphi$ and $\psi$.
\end{itemize}
}
\medskip
\noindent
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 $\bullet$.
\medskip
For $Q \in \{\exists,\forall\}$, a
singleton set $\{\prec\}$ is typically not
$Q$-composite,
whence Propositions 3 and 4 suggest that if a collection
$\Oh$ of orders is to be made
$Q$-composite, then it is more promising to
add orders to $\Oh$ than to take away orders from it.\footnote{
The existential case is particularly simple, the condition that
$\Oh$ is $\exists$-composite being captured precisely by
the following implication (for all
formulas $\varphi, \psi, \varphi'$ and $\psi'$,
and every $\prec \ \in \Oh$)
\[
\frac{\varphi \prec \psi
\ \ \ \ \varphi \not\equiv^\exists \psi
\ \ \ \ \varphi' \equiv^\exists \varphi
\ \ \ \ \psi' \equiv^\exists \psi}{
(\exists \prec' \ \in \Oh) \
\varphi' \prec' \psi'} \
\]
(suppressing for notational simplicity
the subscript ${\cal M} \times \Oh$
on $\equiv^\exists$).
}
But is there a most economical method?
Given a set $\Oh$ of orders, let
\begin{eqnarray*}
\Oh^Q & = &
\bigcap \{\Oh' \ : \ \Oh' \supseteq \Oh \mbox{ and }
\Oh' \mbox{ is $Q$-composite}\} \ .
\end{eqnarray*}
If $\Oh^Q$ is $Q$-composite, then it would certainly be
the least one containing $\Oh$.
Unfortunately, the assumption may fail because
\begin{itemize}
\item[$(\dagger)$]
two distinct orders can induce the same interpretation
by differing on ${\cal M}$-equivalent $\bullet$-free formulas.
\end{itemize}
\subsection{From orders to normal relations}
In view of Proposition 2 and $(\dagger)$, it is natural to
interpret $\bullet$ relative to an arbitrary binary relation
$R$ on formulas. Proposition 4 suggests two possibilities,
yielding two different connectives $\bullet_\exists$ and
$\bullet_\forall$\footnote{To simplify the notation, we will
reuse $\intp{\cdot}$ for the present modification
to relations, relying on context to determine the sense in which
$\intp{\cdot}$ is used, and appealing implicitly to the smooth
generalization from the connective $\bullet$ to
$\bullet_\exists$ and $\bullet_\forall$.
Also, it goes without saying that henceforth,
the full set $\Phi$ of formulas
refers to the result of closing
the set $\Phi_0$ of unambiguous formulas under
$\bullet_\exists$ and $\bullet_\forall$ (as well as the
connectives from $\Phi_0$).}
\[
\intp{\varphi \bullet_\exists \psi}_{M,R}
\ = \ \left\{ \begin{array}{ll}
\intp{\varphi}_{M,R} \ \
& \mbox{ if } \varphi R \psi
\mbox{ but not } \psi R \varphi \\
\intp{\psi}_{M,R} \ \
& \mbox{ if } \psi R \varphi
\mbox{ but not } \varphi R \psi \\
\intp{\varphi}_{M,R} \cup \intp{\psi}_{M,R} \ \
& \mbox{ otherwise }
\end{array}
\right. \]
\[
\intp{\varphi \bullet_\forall \psi}_{M,R}
\ = \ \left\{ \begin{array}{ll}
\intp{\varphi}_{M,R} \ \
& \mbox{ if } \varphi R \psi
\mbox{ but not } \psi R \varphi \\
\intp{\psi}_{M,R} \ \
& \mbox{ if } \psi R \varphi
\mbox{ but not } \varphi R \psi \\
\intp{\varphi}_{M,R} \cap \intp{\psi}_{M,R} \ \
& \mbox{ otherwise. }
\end{array}
\right. \]
A formula $\varphi$ (built from $\bullet_Q$ rather than $\bullet$)
is interpreted relative to a family ${\cal M}$ of models
and $R$ in the obvious way
\begin{eqnarray*}
\intp{\varphi}_{{\cal M},R}
& = &
\{M \in {\cal M} \ : \ \intp{\varphi}_{M,R} = 1\} \ .
\end{eqnarray*}
\medskip
\noindent
{\bf Proposition 5}.
{\sl Given a non-empty family ${\cal M}$ of models
and a non-empty family $\Oh$ of orders,
\begin{eqnarray*}
\intp{\varphi \bullet \psi}^\exists_{{\cal M} \times {\Oh}}
& = &
\intp{\varphi \bullet_\exists \psi}_{{\cal M},\cup {\Oh}}
\\
\intp{\varphi \bullet \psi}^\forall_{{\cal M} \times {\Oh}}
& = &
\intp{\varphi \bullet_\forall \psi}_{{\cal M},\cap {\Oh}}
\end{eqnarray*}
for all unambiguous
formulas $\varphi$ and $\psi \in \Phi_0$.\/}
\medskip
\noindent
{\bf Proof}.
Straightforward inspection of the cases:
$M \in \intp{\varphi \bullet \psi}^Q_{{\cal M} \times \Oh}$
and $M \not\in \intp{\varphi \bullet \psi}^Q_{{\cal M} \times \Oh}$,
for $Q \in \{\exists,\forall\}$.
$\dashv$
\medskip
\noindent
In the case of $\forall$,
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 ${\cal R}$ of relations
be collapsed to its union $\bigcup {\cal R}$
or its intersection $\bigcap {\cal R}$ to capture
the projections of the interpretations of a formula
relative to a family
${\cal I}$ of pairs $(M,R)$, where $R \in {\cal R}$.
(The essential difference here between orders and relations is
that the latter are closed under unions and intersections.)
Repeating the definition in $\S 2.2$ but this time for
$\varphi$'s built from $\bullet_\exists$ and $\bullet_\forall$
(and $\prec$ weakened to $R$), set
\begin{eqnarray*}
\intp{\varphi}_{{\cal I}}^\exists
& = &
\{M \ : \
\intp{\varphi}_{M,R} = 1 \mbox{ for some $R$ such that }
(M,R) \in {\cal I}
\} \
\\
\intp{\varphi}_{{\cal I}}^\forall
& = &
\{M \ : \
\intp{\varphi}_{M,R} = 1 \mbox{ for all $R$ such that }
(M,R) \in {\cal I}
\} \ ,
\end{eqnarray*}
an immediate consequence of which is
\medskip
\noindent
{\bf Proposition 6}.
{\sl Given a non-empty family ${\cal M}$ of models,
and a non-empty family ${\cal R}$ of relations,
\begin{eqnarray*}
\intp{\varphi}^\exists_{{\cal M} \times {\cal R}}
& = &
\intp{\varphi}_{{\cal M},\cup {\cal R}}
\\
\intp{\varphi}^\forall_{{\cal M} \times {\cal R}}
& = &
\intp{\varphi}_{{\cal M},\cap {\cal R}}
\end{eqnarray*}
for every formula $\varphi \in \Phi$.\/}
\medskip
To get rid of the annoying ``but not $\ldots$'' clauses
in the interpretation of $\bullet_Q$,
let us ``normalize'' a binary
relation $R$ on formulas to
\begin{eqnarray*}
\hat{R} & = & \{(\varphi,\psi) \ : \
\varphi R \psi \mbox{ but not } \psi R
\varphi\} \ ,
\end{eqnarray*}
observing that
$\intp{\varphi}_{M,R}
= \intp{\varphi}_{M,\hat{R}}$
for every formula $\varphi$.
A relation $R$ on $\Phi$
is said to be {\em normal\/} if $R = \hat{R}$.
\subsection{Compositionality one more time}
Given a family ${\cal M}$ of models,
call a binary relation $R$ on formulas {\em $Q$-composite\/}
(relative to ${\cal M}$) if
$\equiv_{{\cal M},R}$ is a congruence relative to $\bullet_Q$.
$R$ is {\em composite\/} if it is both $\exists$- and $\forall$-composite.
Proposition 1 generalizes to
\medskip
\noindent
{\bf Lemma 7}.
{\sl Let ${\cal M}$ be a family of models,
$R$ be a normal relation, and
$\tilde{R}$ be the binary relation $\{(\varphi,\psi) :
\varphi R \psi$ and $\varphi \not\equiv_{{\cal M},R} \psi\}$.
\begin{itemize}
\item[(i)] $R$ is $\exists$-composite (relative to ${\cal M}$)
iff the implications
\[
\frac{
\varphi \tilde{R} \psi \ \ \
\varphi' \equiv_{{\cal M},R} \varphi \ \ \
\psi' \equiv_{{\cal M},R} \psi}{\mbox{not }
\psi' \tilde{R} \varphi'}
\hspace{.3in}
\frac{
\varphi \tilde{R} \psi \ \ \
\varphi' \equiv_{{\cal M},R} \varphi \ \ \
\psi' \equiv_{{\cal M},R} \psi \ \ \
\mbox{not } \varphi' \tilde{R} \psi'}{
\intp{\psi}_{{\cal M},R} \subseteq \intp{\varphi}_{{\cal M},R}
}
\]
hold for all formulas $\varphi, \psi, \varphi'$ and $\psi'$.
\item[(ii)] $R$ is $\forall$-composite
iff the implications
\[
\frac{
\varphi \tilde{R} \psi \ \ \
\varphi' \equiv_{{\cal M},R} \varphi \ \ \
\psi' \equiv_{{\cal M},R} \psi}{\mbox{not }
\psi' \tilde{R} \varphi'}
\hspace{.3in}\frac{
\varphi \tilde{R} \psi \ \ \
\varphi' \equiv_{{\cal M},R} \varphi \ \ \
\psi' \equiv_{{\cal M},R} \psi \ \ \
\mbox{not } \varphi' \tilde{R} \psi'}{
\intp{\varphi}_{{\cal M},R} \subseteq \intp{\psi}_{{\cal M},R}
}
\]
hold for all formulas $\varphi, \psi, \varphi'$ and $\psi'$.
\item[(iii)] $R$ is composite
iff the implication
\[
\frac{
\varphi \tilde{R} \psi \ \ \
\varphi' \equiv_{{\cal M},R} \varphi \ \ \
\psi' \equiv_{{\cal M},R} \psi}{
\varphi' \tilde{R} \psi'}
\]
holds for all formulas $\varphi, \psi, \varphi'$ and $\psi'$.
\end{itemize}
}
\medskip
\noindent
{\bf Proof}.
Under normality, parts (i) and (ii) follow easily from the
definitions, while part (iii) is an immediate consequence
of parts (i) and (ii).
$\dashv$
\medskip
The trivial relation on formulas that contains every pair
of formulas is manifestly composite.
Before passing to that relation, however,
let us define the {\em composite closure of\/} a relation $R$
(given a family ${\cal M}$ of models)
to be the least relation containing $R$ that is composite
(relative to ${\cal M}$).
If it exists, it could only be
\begin{eqnarray*}
R^{\cal M} & = &
\bigcap \{R' \ : \ R' \supseteq R \mbox{ and $R'$ is composite
relative to } {\cal M}\} \ .
\end{eqnarray*}
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$,
$\intp{\varphi \bullet_\exists \psi}_{{\cal M},R}$
increases (or stays the same) whereas
$\intp{\varphi \bullet_\forall \psi}_{{\cal 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
\medskip
\noindent
{\bf Theorem 8}.
{\sl Every normal relation $R$ has a composite closure\/.}
\medskip
\noindent
{\bf Proof}.
Fix a family ${\cal M}$ of models, and a normal relation $R$.
We will construct $R^{\cal M}$ in stages such that
\begin{eqnarray*}
R^{\cal M}
& = &
R \ \cup \
\bigcup_{n<\omega} R_n \ ,
\end{eqnarray*}
where
$R_0 \subseteq R_1 \subseteq R_2 \subseteq
\cdots$.
Let $R_0 = R -\{(\varphi,\psi) \ : \varphi \equiv_{{\cal M},R} \psi\}$,
and for every $n$, form $R_{n+1}$ from
$R_n$ by applying
an operation $\Theta$ that maps
a binary relation $R'$ and a set $\Phi'$ of formulas
to the binary relation
\[
\{(\varphi',\psi') \in \Phi' \times \Phi'
\ : \
(\exists \varphi, \psi) \ \varphi R' \psi , \
\varphi' \equiv_{{\cal M},R'} \varphi , \mbox{ and }
\psi' \equiv_{{\cal M},R'} \psi
\}
\]
derived from part (iii) of Lemma 7.
More specifically, let
\begin{eqnarray*}
R_{n+1} & = & R_n \ \cup \ \Theta(R_n,\Phi_n)
\end{eqnarray*}
where $\Phi_0$ is, as before, the set of unambiguous formulas, and
\begin{eqnarray*}
\Phi_{n+1} & = &
cl(\{\varphi \bullet_\exists \psi \ : \ \varphi,\psi \in \Phi_n\}
\ \cup \
\{\varphi \bullet_\forall \psi \ : \ \varphi,\psi \in \Phi_n\})
\end{eqnarray*}
and $cl(\Phi')$ is the closure of $\Phi'$ under all the logical
connectives except $\bullet_\exists$ and $\bullet_\forall$.
Observe that $\bigcup_{n < \omega} \Phi_n$ includes
all formulas, and that for every $n$ and
all $\varphi$ and $\psi$ in $\Phi_n$,
\begin{eqnarray*}
\varphi \equiv_{{\cal M},R \cup R_n} \psi
& \mbox{ iff } &
(\forall m > n) \
\varphi \equiv_{{\cal M},R \cup R_m} \psi
\end{eqnarray*}
(i.e., $R_{n+1} - R_n$ is disjoint from
$\Phi_n \times \Phi_n$),
whence, writing $R_\omega$ for
$R \cup \bigcup_{n< \omega} R_n$,
\begin{eqnarray*}
R_\omega
& = &
\Theta(R_\omega, \bigcup_{n < \omega} \Phi_n) \ .
\end{eqnarray*}
That is, $R_\omega$ is composite,
by Lemma 7, part (iii).
Moreover, $R_\omega$ is the least extension of $R$ that is
composite because every $R_n$ is disjoint from
$\equiv_{{\cal M},R_\omega}$.
$\dashv$
\medskip
\noindent
The case where $R$ is not normal is left to the abnormal reader.
\section{Context-dependent disambiguation}
Let us now turn to an interpretation of $\bullet$ based on line (2).
This interpretation
builds on a binary operation $^\wedge: \Phi_0 \times \Phi_0 \ra
\Phi_0$ that merges unambiguous formulas, the first argument of which
is regarded as a context in which the second argument is uttered.
\medskip
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 context-independent case in mind,
let us define a {\em context-dependent disambiguation\/}
to be a function $i$ mapping an unambiguous formula
$\theta \in \Phi_0$ to a normal relation $R^\theta$ (on $\Phi$),
generalizing line (2) to
\begin{eqnarray*}
\theta ^{\wedge_i} (\varphi\bullet_\exists \psi)
& = &
\left\{ \begin{array}{ll}
\theta ^{\wedge_i} \varphi \ \
& \mbox{ if } \varphi R^{\theta} \psi \\
\theta ^{\wedge_i} \psi \ \
& \mbox{ if } \psi R^{\theta} \varphi \\
\theta ^{\wedge_i} (\varphi \vee \psi) \ \
& \mbox{ otherwise}
\end{array}
\right.
\\
\theta ^{\wedge_i} (\varphi\bullet_\forall \psi)
& = &
\left\{ \begin{array}{ll}
\theta ^{\wedge_i} \varphi \ \
& \mbox{ if } \varphi R^{\theta} \psi \\
\theta ^{\wedge_i} \psi \ \
& \mbox{ if } \psi R^{\theta} \varphi \\
\theta ^{\wedge_i} (\varphi \wedge \psi) \ \
& \mbox{ otherwise.}
\end{array}
\right.
\end{eqnarray*}
{\em Caution\/}: it is understood above that
$\vee$ is interpreted as union (or,
as an operation on binary relations, non-deterministic choice), and
$\wedge$ as intersection (both of which would require extending
the basic apparatus of Kamp and Reyle \cite{KR:book}).
Assuming (as we will) that $\Phi$ is closed under $\vee$ and $\wedge$,
the equations above extend in a natural way\footnote{
More precisely, for all formulas $\varphi,\psi$ and $\chi \in \Phi$,
assert
\begin{eqnarray*}
\theta ^{\wedge_i} \chi
& = &
\left\{ \begin{array}{ll}
\theta ^{\wedge_i} (\chi[\varphi \bullet_\exists
\psi/\varphi]) \ \
& \mbox{ if } \varphi R^{\theta} \psi \\
\theta ^{\wedge_i} (\chi[\varphi \bullet_\exists
\psi/\psi]) \ \
& \mbox{ if } \psi R^{\theta} \varphi \\
\theta ^{\wedge_i} (\chi[\varphi \bullet_\exists \psi/
\varphi \vee \psi]) \ \
& \mbox{ otherwise}
\end{array}
\right.
\end{eqnarray*}
and similarly for $\bullet_\forall$, where
$\chi[\varphi/\psi]$ is $\chi$ with all occurrences of $\varphi$
replaced by $\psi$.}
to turn $^{\wedge_i}$ into a function from $\Phi_0 \times \Phi$ into $\Phi_0$.
\subsection{Representing context change potentials}
This subsection draws on Fernando \cite{Fer:prag}
to relate the merge $^\wedge: \Phi_0 \times \Phi_0 \ra \Phi_0$
to an interpretation of a formula $\varphi \in \Phi_0$
as a {\em context change potential\/} (CCP)
$P(\varphi) \subseteq \WSP \times \WSP$
on a collection $\WSP$ of {\em world-sequence pairs\/} (wsp's).
To be more precise, fix a family ${\cal M}$ of
first-order models, and let $\WSP$ be the collection
of pairs $(M,f)$ where $M \in {\cal M}$, and
$f$ is a partial function from the set of variables
(from which formulas in $\Phi_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 = {\cal M}$, with
variables occurring freely treated as constants.
Now, the intuition behind a CCP $P(\varphi)$ is that
it specifies the input/output relation of $\varphi$,
extending the interpretation $\intp{\varphi}_M$ of
unambiguous formulas $\varphi \in \Phi_0$
analyzed in the previous section, by returning outputs
precisely on inputs $M \in{\cal M}$ at which
$\varphi$ is true
\begin{eqnarray*}
\intp{\varphi}_M = 1
& \mbox{ iff } &
M \in \dom(P(\varphi)) \ .
\end{eqnarray*}
The merge operation $^\wedge$ is interpreted
(``sequentially'' or ``incrementally'') by $P$
as relational composition $\circ$,
where, by definition, $R \circ R' = \{(a,b) : (\exists c)
\ aRc \mbox{ and } cR'b\}$.
Adding further assumptions on $P$, let us record these together as
\medskip
\noindent
{\bf Assumptions} (in force throughout this section).
{\sl
For all $\varphi$ and $\theta \in \Phi_0$,
\begin{eqnarray*}
({\rm A}1) & & \dom(P(\varphi)) \ = \ \{M \in {\cal M} \ : \ \intp{\varphi}_M =
1\} \\
({\rm A}2) & & P(\theta ^\wedge \varphi) \ = \ P(\theta) \circ P(\varphi) \\
({\rm A}3) & & P(\neg\varphi) \ = \ \{(M,M) \ : \ M \in {\cal M}
- \dom(P(\varphi))\}
\end{eqnarray*}
for some unary connective
$\neg$ under which $\Phi_0$ is assumed to be closed. Furthermore,
\begin{eqnarray*}
({\rm A}0) & &
\mbox{there is a formula } \top \in \Phi_0 \ \mbox{ s.t. }
P(\top) = \{(M,M) \ : \ M \in {\cal M}\} \ .
\end{eqnarray*}
}
Assumption (A1) suggests a definition of
the set $\Phi_{\cal M} \subseteq \Phi_0$
of ${\cal M}$-{\em absurd} formulas as follows
\begin{eqnarray*}
\Phi_{\cal M}
& = &
\{\varphi \in \Phi_0 \ : \
(\forall M \in {\cal M})
\ M \not\in \dom(P(\varphi))\} \ .
\end{eqnarray*}
With (A1) in mind, define the equivalence
$\equiv_{\cal M}$ on $\Phi$ by
\begin{eqnarray*}
\varphi \equiv_{\cal M} \psi
& \mbox{ iff } &
\dom(P(\varphi))
=
\dom(P(\psi)) \ .
\end{eqnarray*}
\medskip
\noindent
{\bf Proposition 9}.
{\sl For
all $\varphi, \psi \in \Phi_0$,
\begin{eqnarray*}
\varphi \equiv_{\cal M} \psi
& \mbox{ iff } &
(\forall \theta \in \Phi_0) \
(\theta ^\wedge \varphi \in \Phi_{\cal M}
\mbox{ iff }
\theta ^\wedge \psi \in \Phi_{\cal M}) \ .
\end{eqnarray*}
}
\noindent
{\bf Proof}.
The forward implication $\Ra$ follows immediately from (A1) and (A2).
For the converse, suppose $\varphi \not\equiv_{\cal M} \psi$,
say, $M \in \dom(P(\varphi)) - \dom(P(\psi))$.
Then, appealing to (A3),
take $\theta$ to be $\neg\psi$.
$\dashv$
\medskip
\noindent
As an equivalence on (unambiguous) formulas,
$\equiv_{\cal M}$ abstracts away the dynamic effects of the CCP's
inasmuch as
\begin{eqnarray*}
\neg\neg \varphi & \equiv_{\cal M} & \varphi
\end{eqnarray*}
for every $\varphi \in \Phi_0$.
Complementing the equivalence $\equiv_{\cal M}$ on $\Phi_0$
is the equivalence $\equiv^{\cal M}$ on $\Phi_0$
testing the other side of $^\wedge$
\begin{eqnarray*}
\theta \equiv^{\cal M} \rho
& \mbox{ iff } &
(\forall \varphi \in \Phi_0) \
(\theta ^\wedge \varphi \in \Phi_{\cal M}
\mbox{ iff }
\rho ^\wedge \varphi \in \Phi_{\cal M}) \ ,
\end{eqnarray*}
which may very well be distinct since
relational composition is typically not
commutative.\footnote{
Defining $\ima(P(\varphi))$ to be
$\{M' \ : \ (\exists M \in {\cal M}) \ M \ P(\varphi) \ M'\}$,
it is immediate that $\ima(P(\theta)) = \ima(P(\rho))$ implies
$\theta \equiv^{\cal M} \rho$.
For the converse, however, it would be helpful to have a
connective dual to $\neg$, or further assumptions such as in,
for example, Fernando \cite{Fer:prag} (concerning which
note that $\ima(P(\varphi))$ is different from
$D[P(\varphi)](\inisig)$, as defined there, since
$\inisig$ corresponds only to a proper subset of
${\cal M}$).
}
Now, how do the equivalences $\equiv_{\cal M}$ and
$\equiv^{\cal M}$ behave relative to the merge $^\wedge$?
It is immediate that
\begin{eqnarray}
\frac{\theta \equiv^{\cal M} \rho
\ \ \ \
\varphi \equiv_{\cal M} \psi
}{
\theta^\wedge \varphi \in \Phi_{\cal M}
\ \mbox{ iff } \
\rho^\wedge \psi \in \Phi_{\cal M}} \ .
\end{eqnarray}
To conclude further, under the same premisses, that
$\theta^\wedge \varphi \equiv_{\cal M} \rho^\wedge \psi$,
it suffices (by (3), (A2) and the associativity of $\circ$)
that for all $\theta'$,
${\theta'}^\wedge \theta \equiv^{\cal M} {\theta'}^\wedge \rho$.
Similarly, to deduce
$\theta^\wedge \varphi \equiv^{\cal M} \rho^\wedge \psi$, it
is enough that
$\varphi^\wedge \varphi' \equiv_{\cal M} \psi^\wedge \varphi'$
for all $\varphi'$.
Now, certainly
\[
\frac{\theta \equiv^{\cal M} \rho}{\theta^\wedge \theta'
\equiv^{\cal M} \rho^\wedge \theta'}
\ \ \ \
\ \ \ \
\ \ \ \
\ \ \ \
\frac{\varphi \equiv_{\cal M} \psi}{{\varphi'}^\wedge \varphi
\equiv_{\cal M} {\varphi'}^\wedge \psi} \
\]
and again the possibility that $^\wedge$ is non-commutative
prevents us from
strengthening the conclusion of (3) to
$\theta^\wedge \varphi \equiv_{\cal M} \rho^\wedge \psi$
and $\theta^\wedge \varphi \equiv^{\cal M} \rho^\wedge \psi$
(which would then mean, by (A0), that
$\equiv^{\cal M}$ is identical with $\equiv_{\cal M}$).
Rather than assuming $^\wedge$ is commutative,
let us instead add
\begin{eqnarray*}
({\rm A}4) & &
\frac{\theta \equiv^{\cal M} \rho
\ \ \ \ \
\theta \equiv_{\cal M} \rho}{
{\theta'}^\wedge \theta
\equiv^{\cal M}
{\theta'}^\wedge \rho}
\ \ \ \ \
\ \ \ \ \
\frac{\varphi \equiv^{\cal M} \psi
\ \ \ \ \
\varphi \equiv_{\cal M} \psi}{
\varphi^\wedge \varphi'
\equiv_{\cal M}
\psi^\wedge \varphi'}
\end{eqnarray*}
to the list of assumptions above.\footnote{
A model for (A0) to (A4) can be built from
Kamp and Reyle \cite{KR:book}, with
\begin{eqnarray*}
\varphi \equiv^{\cal M} \psi
\mbox{ and }
\varphi \equiv_{\cal M} \psi
& \mbox{ iff } &
P(\varphi) = P(\psi) \ ,
\end{eqnarray*}
as explained in Fernando \cite{Fer:prag}.}
The preceding discussion then yields
\medskip
\noindent
{\bf Proposition 10}.
{\sl The equivalence $\equiv_{\cal M} \cap \equiv^{\cal M}$
is a congruence relative to $^\wedge$.
In particular, the implications
\[
\frac{
\theta \equiv^{\cal M} \rho \ \ \
\theta \equiv_{\cal M} \rho \ \ \
\varphi \equiv_{\cal M} \psi}{
\theta ^\wedge \varphi
\equiv_{\cal M}
\rho ^\wedge \psi}
\ \ \ \ \ \ \ \ \
\mbox{ and } \ \ \
\ \ \ \ \ \
\frac{
\theta \equiv^{\cal M} \rho \ \ \
\varphi \equiv^{\cal M}
\psi \ \ \
\varphi \equiv_{\cal M}
\psi}{
\theta ^\wedge \varphi
\equiv^{\cal M}
\rho ^\wedge \psi}
\]
hold for all $\theta,\rho,\varphi$ and $\psi \in \Phi_0$.\/}
\medskip
Next, let us bring into the picture a context-dependent
disambiguation $i$.
Replacing $^\wedge$ by $^{\wedge_i}$,
the equivalence
$\equiv_{\cal M}$ on $\Phi_0$ extends
to an equivalence $\equiv_{{\cal M},i}$
on $\Phi$
\begin{eqnarray*}
\varphi \equiv_{{\cal M},i} \psi
& \mbox{ iff } &
(\forall \theta \in \Phi_0) \
(\theta ^{\wedge_i} \varphi \in \Phi_{\cal M}
\mbox{ iff }
\theta ^{\wedge_i} \psi \in \Phi_{\cal M}) \ .
\end{eqnarray*}
\medskip
\noindent
{\bf Proposition 11}.
{\sl Given a normal relation $R$ on $\Phi$,
let $i^R$ be the context-dependent [sic] disambiguation
that maps every unambiguous formula to $R$.
Then, the equivalence $\equiv_{{\cal M},R}$ (from the previous section)
is identical to the equivalence $\equiv_{{\cal M},i^R}$
---
\begin{eqnarray*}
\varphi \equiv_{{\cal M},i^R} \psi
& \mbox{ iff } &
\varphi \equiv_{{\cal M},R} \psi
\end{eqnarray*}
for all $\varphi$ and $\psi \in \Phi$.\/}
\medskip
\noindent
As for the equivalence $\equiv^{\cal M}$, the point
is to extend the bounded quantification on $\Phi_0$ to
$\Phi$. That is, let
$\equiv^{{\cal M},i}$ be the equivalence on $\Phi_0$ given by
\begin{eqnarray*}
\theta \equiv^{{\cal M},i} \rho
& \mbox{ iff } &
(\forall \varphi \in \Phi) \
(\theta ^{\wedge_i} \varphi \in \Phi_{\cal M}
\mbox{ iff }
\rho ^{\wedge_i} \varphi \in \Phi_{\cal M}) \ .
\end{eqnarray*}
\medskip
\noindent
{\bf Proposition 12}.
{\sl For every
context-dependent disambiguation $i$,
\begin{itemize}
\item[(i)]
$\equiv^{{\cal M},i} \ \subseteq \ \equiv^{{\cal M}}$, and
\item[(ii)]
$\equiv^{{\cal M}} \ \not\subseteq \ \equiv^{{\cal M},i}$
iff for some $\varphi \in \Phi$,
$\equiv^{\cal M}$ is not a congruence with respect
to $^{\wedge_i}\varphi$.
\end{itemize}
}
\medskip
\noindent
The proof is immediate, with (A0) useful for part (ii).
\subsection{Composite disambiguation}
Fix a family ${\cal M}$ of models,
and a context-dependent disambiguation $i:
\theta \mapsto R^\theta$.
Call $i$ ${\cal M}$-{\em composite\/} if
\begin{itemize}
\item[(i)]
$\equiv_{{\cal M},i}$ is a congruence relative to
$\bullet_\exists$ and $\bullet_\forall$,
\item[(ii)] the rule
\[
\frac{
\theta \equiv^{\cal M} \rho \ \ \
\theta \equiv_{{\cal M}} \rho \ \ \
\varphi \equiv_{{\cal M},i} \psi}{
\theta ^{\wedge_i} \varphi
\equiv_{{\cal M},i}
\rho ^{\wedge_i} \psi}
\]
holds for all $\theta$ and $\rho \in \Phi_0$
and all $\varphi$ and $\psi \in \Phi$,
\end{itemize}
and
\begin{itemize}
\item[(iii)] $\equiv^{\cal M}$ identical to
$\equiv^{{\cal M},i}$.\footnote{
We make do with this condition, because of the
problem in extending $\equiv^{\cal M}$ to $\Phi - \Phi_0$,
to formulate the extension,
\[
\frac{
\theta \equiv^{{\cal M}} \rho \ \ \
\varphi \equiv^{\cal M} \psi
\ \ \
\varphi \equiv_{{\cal M},i} \psi
}{
\theta ^{\wedge_i} \varphi
\equiv^{{\cal M}}
\rho ^{\wedge_i} \psi} \ ,
\]
of the second rule in Proposition 10. See $\S 4.2$.
}
\end{itemize}
Two unambiguous formulas $\theta$ and $\rho$ are
$(i,{\cal M})$-{\em similar\/} if
\begin{itemize}
\item[(i)] $\equiv_{{\cal M},R^\theta}$ and $\equiv_{{\cal M},R^\rho}$
are the same,
\end{itemize}
and, calling that equivalence $\equiv$,
\begin{itemize}
\item[(ii)]
the implications
\[
\frac{
\theta^\wedge \varphi \not\equiv \rho^\wedge \psi \ \ \
\varphi R^\theta \psi \ \ \
\varphi' \equiv
\varphi \ \ \
\psi' \equiv
\psi}{
\varphi' R^\rho \psi'}
\ \ \ \ \
\mbox{ and }
\ \ \ \ \
\frac{
\theta^\wedge \varphi \not\equiv \rho^\wedge \psi \ \ \
\varphi R^\rho \psi \ \ \
\varphi' \equiv
\varphi \ \ \
\psi' \equiv
\psi}{
\varphi' R^\theta \psi'}
\]
hold for all
formulas $\varphi, \psi, \varphi'$ and $\psi' \in \Phi$.
\end{itemize}
\medskip
\noindent
{\bf Theorem 13}.
{\sl Given a family ${\cal M}$ of models,
a context-dependent disambiguation $i$
is ${\cal M}$-composite iff
$\equiv^{{\cal M},i}$ is $\equiv^{\cal M}$, and
for all $\theta$ and $\rho \in \Phi_0$, if
$\theta \equiv^{\cal M} \rho$
and $\theta \equiv_{\cal M} \rho$,
then $\theta$ and $\rho$ are $(i,{\cal M})$-similar.\/}
\medskip
\noindent
({\bf Proof}. Long, using Lemma 7 and Propositions 9 to 12.)
\medskip
Partially ordering context-dependent
disambiguations ($i$ and $i'$) pointwise,
\begin{eqnarray*}
i \leq i' & \mbox{ iff } &
(\forall \theta \in \Phi_0) \
i(\theta) \subseteq i'(\theta) \ ,
\end{eqnarray*}
and defining the ${\cal M}$-{\em composite closure of\/} $i$
to be the $\leq$-least ${\cal M}$-composite context-dependent
disambiguation $i'$ such that $i \leq i'$,
Theorem 13 yields
\medskip
\noindent
{\bf Corollary 14}.
{\sl For every family ${\cal M}$ of models,
every context-dependent disambiguation
$i$ has an ${\cal M}$-composite closure.\/}
\medskip
\noindent
>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
$\theta \mapsto R^\theta$ such that
for unambiguous $\varphi,\theta$ and $\psi$,
\begin{eqnarray*}
\varphi R^{\theta} \psi
& \mbox{ iff } &
\theta ^\wedge \varphi
\ \sqsubseteq^{\cal M} \
\theta ^\wedge \psi \ ,
\end{eqnarray*}
where $\sqsubseteq^{\cal M}$ is the pre-order
\begin{eqnarray*}
\theta \sqsubseteq^{\cal M} \rho
& \mbox{ iff } &
(\forall \varphi \in \Phi_0) \
(\theta ^\wedge \varphi \in \Phi_{\cal M}
\mbox{ implies }
\rho ^\wedge \varphi \in \Phi_{\cal M}) \
\end{eqnarray*}
on $\Phi_0$, for which $\equiv^{\cal M}$ can be decomposed
as $\sqsubseteq^{\cal M} \cap \sqsupseteq^{\cal M}$.
Of course, we might be interested more widely
in disambiguations whose $\theta$th relation includes
$R^\theta$ (plus possibly any number of other constraints).
\section{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 $\{\varphi, \psi\}$
semantically with $\{\varphi \vee \psi\}$.
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).
\medskip
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
\begin{center}
In what sense can the constructs $\bullet_\exists$ and
$\bullet_\forall$ be described as logical connectives?
\end{center}
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.
\subsection{Variations on a theme from Kripke}
Insofar as the interpretations of $\bullet_\exists$ and $\bullet_\forall$
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
\begin{eqnarray*}
(\ast) & &
\mbox{axiomatizing $\bullet_\exists$ and $\bullet_\forall$
on the basis of properties imposed on the disambiguations.}
\end{eqnarray*}
For starters, it is easy enough to see that if a normal relation
$R$ is transitive, then the interpretation of
$\bullet_Q$ (relative to $R$) is associative; and
if $R$ is symmetric, then its normalization $\hat{R}$ is empty,
and $\bullet_Q$ becomes either $\vee$ or $\wedge$.\footnote{
A particularly natural property (that vaguely smells of
compositionality) is that $R$ satisfy
the following condition:
\begin{eqnarray*}
\varphi_1 R \psi_1 , \
\ldots
\mbox{ and }
\varphi_n R \psi_n
& \mbox{ imply } &
\alpha(\varphi_1,\ldots,\varphi_n)
\ R \
\alpha(\psi_1,\ldots,\psi_n)
\end{eqnarray*}
for every $n$-ary connective $\alpha$.}
The problem $(\ast)$ can also be posed {\em globally\/},
interpreting $\bullet_Q$ relative to a family ${\cal I}$ of pairs
$(M,R)$ where $R$ has the prescribed properties.
If ${\cal I}$ is a cartesian product ${\cal M} \times {\cal R}$,
then Proposition 6 suggests collapsing ${\cal R}$ to either
$\bigcup {\cal R}$ or $\bigcap {\cal R}$.
But what if ${\cal 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 $\hat{\Phi}$ of formulas,
call $(M,R)$ $\hat{\Phi}$-{\em charitable\/} if
for all $\varphi$ and $\psi \in \hat{\Phi}$,
\begin{eqnarray*}
\intp{\varphi \wedge \neg \psi}_{M,R} = 1
& \mbox{ implies } &
\varphi R \psi \ .
\end{eqnarray*}
Rather than considering $\hat{\Phi}$-charitable pairs,
the notion of charity can also (and arguably more naturally)
be phrased relative to a family ${\cal M}$ of models as follows:
a relation $R$ is {\em $({\cal M},\hat{\Phi})$-charitable\/} if
for all $\varphi$ and $\psi \in \hat{\Phi}$,
\begin{eqnarray*}
\intp{\varphi \wedge \neg \psi}_{{\cal M},R} = {\cal M}
& \mbox{ implies } &
\varphi R \psi \ ,
\end{eqnarray*}
so that $R$ need not depend on a fixed $M \in {\cal M}$ (but rather on
${\cal 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 $\S 3.2$ comes closest
(degenerating to the second notion of charity above,
if the context is frozen).\footnote{
Another constraint on disambiguation mentioned in
van Deemter \cite{vDe94} is ``a tendency towards {\em equal\/}
interpretation of different occurrences of a given expression
throughout a discourse'' ($\S 5.1$) called {\em 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.}
We can go on, but for now
let us just say that the matter of choosing ``interesting''
collections ${\cal I}$ of pairs $(M,i)$ and investigating
the associated theories
\begin{eqnarray*}
Q({\cal I}) & = &
\{\varphi \ : \
(\forall (M,i) \in {\cal I}) \
M \in \intp{\varphi}^Q_{\cal I}
\} \
\end{eqnarray*}
for $Q \in \{\exists,\forall\}$ 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.
\subsection{Further work: ambiguous contexts and some generalizations}
It is curious,
as pointed out to the author by U. Reyle,
that the first argument of $^{\wedge_i}$
should be restricted to unambiguous formulas ($\in \Phi_0$).
The reason is that an assumption of total disambiguation
is built in by the requirement that
every pair $(\theta,\varphi)$ in $\Phi_0 \times \Phi$
be mapped by $^{\wedge_i}$ into an unambiguous formula.
But suppose $\theta^{\wedge_i}\varphi$ can be ambiguous,
delaying its disambiguation until further information is
available.
Then it is only sensible to expand
the domain of $^{\wedge_i}$
from $\Phi_0 \times \Phi$ to $\Phi \times \Phi$.
More precisely, allowing the value
$R^\theta$ of a disambiguation $i$ at $\theta$
to be abnormal, define
\begin{eqnarray*}
\theta ^{\wedge_i} (\varphi\bullet_\exists \psi)
& = &
\left\{ \begin{array}{ll}
\theta ^{\wedge_i} \varphi \ \
& \mbox{ if } \varphi R^{\theta} \psi
\mbox{ but not } \psi R^{\theta} \varphi \\
\theta ^{\wedge_i} \psi \ \
& \mbox{ if } \psi R^{\theta} \varphi
\mbox{ but not } \varphi R^{\theta} \psi \\
\theta ^{\wedge_i} (\varphi \vee \psi) \ \
& \mbox{ if } \psi R^{\theta} \varphi
\mbox{ and } \varphi R^{\theta}
\psi \\
\theta ^{\wedge_i} (\varphi \bullet_\exists \psi) \ \
& \mbox{ otherwise}
\end{array}
\right.
\\
\theta ^{\wedge_i} (\varphi\bullet_\forall \psi)
& = &
\left\{ \begin{array}{ll}
\theta ^{\wedge_i} \varphi \ \
& \mbox{ if } \varphi R^{\theta} \psi
\mbox{ but not } \psi R^{\theta} \varphi \\
\theta ^{\wedge_i} \psi \ \
& \mbox{ if } \psi R^{\theta} \varphi
\mbox{ but not } \varphi R^{\theta} \psi \\
\theta ^{\wedge_i} (\varphi \wedge \psi) \ \
& \mbox{ if } \psi R^{\theta} \varphi
\mbox{ and } \varphi R^{\theta}
\psi \\
\theta ^{\wedge_i} (\varphi \bullet_\forall \psi) \ \
& \mbox{ otherwise}
\end{array}
\right.
\end{eqnarray*}
so that if neither $\varphi R \psi$ nor $\psi R \varphi$, then
the disambiguation of $\varphi \bullet_Q \psi$ is postponed.
Further generalizations are provided by taking $i(\theta)$ to be
a function from $\Phi \times \Phi$ to $\Phi$, allowing
$i(\theta)(\varphi,\psi)$ to be some formula other than
$\varphi$ or $\psi$ that presumably
resolves only part of the ambiguity in $\varphi \bullet_Q \psi$.
In addition to extending the domain of $i$ to
$\Phi$, some mechanism for disambiguating contexts
must also be introduced that complements $i$.
A more general approach to
the interpretation of ambiguity is adopted in Fernando \cite{Fer:aa},
the virtue of the present paper being concreteness and simplicity.
\begin{thebibliography}{1}
\bibitem{vDe94}
Kees~van Deemter.
\newblock Towards a logic of ambiguous expressions.
\newblock Manuscript, 1994.
\newblock To be revised into a paper to appear in a CSLI Lecture
Note.
\bibitem{Fer:prag}
Tim Fernando.
\newblock Are context change potentials functions?
\newblock Manuscript, distributed at a workshop on context dependency in
Prague, 1995.
\bibitem{Fer:aa}
Tim Fernando.
\newblock Ambiguity under changing contexts.
\newblock Manuscript, 1995.
\newblock Presented in
{\sl Mathematics of Language 4\/},
Philadelphia, October 1995.
\bibitem{KR:book}
H.~Kamp and U.~Reyle.
\newblock {\em From Discourse to Logic}.
\newblock Kluwer Academic Publishers, Dordrecht, 1993.
\bibitem{Rey93}
Uwe Reyle.
\newblock Dealing with ambiguities by underspecification: construction,
representation and deduction.
\newblock {\em Journal of Semantics}, 10(2), 1993.
\end{thebibliography}
\end{document}