The Proper Treatment of Linguistic Ambiguity in Ordinary Algebra

Abstract

We present a first algebraic approximation to the semantic content of linguistic ambiguity. Starting from the class of ordinary Boolean algebras, we add to it an ambiguity operator $\Vert$ and a small set of axioms which we think are correct for linguistic ambiguity beyond doubt. We then show some important, non-trivial results that follow from this axiomatization, which turn out to be surprising and not fully satisfying from a linguistic point of view. Therefore, we also sketch promising algebraic alternatives.

In the originally published version there is an error in the proof of Lemma 1. The erratum to this chapter is available at https://doi.org/10.1007/978-3-662-53042-9_19

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The term linguistic ambiguity designates cases where expressions, or exponents, of natural language give raise to two or more sharply distinguished meanings.¹ Ambiguity is a truly pervasive phenomenon in natural language, and therefore perhaps also a very heterogeneous one. It affects single-word expressions such as bank (‘financial institute’, ‘strip of land along a river’), multi-word expressions such as kick the bucket (‘kick the bucket’, ‘die’), VPs with varying PP attachment (see the man with the telescope), as well as larger syntactic units up to full clauses, e.g. every boy loves a movie with its two readings of quantifier scopes.

To deal with ambiguity of this kind, say an exponent e with two meanings $m_1, m_2$, two general approaches are at choice. The first approach (aka. syntactic approach) is the following: we have two separate entities $(e,\ m_1)$ and $(e,\ m_2)$ (these are form-meaning pairs, which we henceforth call symbols). These are unrelated, except for the fact that (for whatever reason) they turn out to have the same exponent. If we encounter e, we do not know which of the two entities we have; so we just pick one and proceed. Importantly, in the meaning component itself, there is no ambiguity; it only occurs at the point where we choose one of the two symbols. This process is however non-deterministic, and strictly speaking, there is no function from form to meaning. The second approach (aka. semantic approach) is to assume the existence of one ambiguous symbol $(e,\ m_1\Vert m_2)$, which has a genuinely ambiguous meaning. This comes with a number of technical advantages: there is a function from form to meaning, lexical entries do not multiply, there are no questionable choices, and we always keep track of possible ambiguities during the process of meaning composition.

There is, however, one big question: as in the second approach, ambiguity enters into semantics proper, we have to ask ourselves: what does it actually mean? In this paper, we will approach this question in an algebraic fashion. In doing so, we will see that the answer is far from obvious, and comes with a number of surprising insights.

2 Linguistic Ambiguity

The ambiguity of linguistic exponents is commonly treated by mixing syntactic and semantic approaches – and it is sometimes difficult to sort out which of the two should be preferred given a specific exponent. Still there seem to be cases where there is inherent reason (besides the technical advantages mentioned above) to choose only the semantic approach. One sort of evidence is the concurrent and persistent availability of different meanings of one exponent, such as in (1) taken from [3]:

In (1-a), the modifiers well-muscled and federally-funded refer to different meanings of wing, namely either its literal or idiomatic meaning. This is clearly out of reach for any syntactic approach. The same holds for cases of “conjunctive modification” (Ernst) such as in (1-b). Here, cross-gartered modifies the literal meaning of leg, while pulled leg is interpreted idiomatically. Another sort of evidence in favor of choosing a semantic approach comes from psycholinguistic experiments (e.g. [7, 12]) that suggest that, in the face of ambiguity, processing costs rather emerge in the semantics than in syntax. So even if we don’t claim that all cases of linguistic ambiguity must be treated within a semantic approach, there’s certainly no way around a notion of ambiguity that is genuinely semantic. Therefore, and for the sake of exposition, we want to apply the semantic approach as generously as possible in what follows.

It seems furthermore clear to us that we want to draw inferences from ambiguous statements, even if we cannot disambiguate them. Hence, we do not assume that disambiguation strictly precedes the inferencing step, as does [10]. So given an ambiguous sentence such as in (2), taken from [10], it is clearly possible to infer ‘there is a big car in New York’ without disambiguating the meaning of strikes:

One might think that this is no argument in our favor, because the fact that there is a big car in New York obviously follows from both readings of (2). But the example actually makes a strong point: since we can easily and obviously infer things from ambiguous statements, we have to clarify what the meaning of ambiguity actually is, at least from an inferential point of view.

Usually, there is a quick answer to the question what ambiguity means, namely: ambiguity means the same as disjunction. This is correct in the sense that, if we get an ambiguous meaning $m_1\Vert m_2$, then the only thing we can infer for sure is $m_1\vee m_2$ ($\vee$ being disjunction). However, a quick argument shows that equating $\Vert$ and $\vee$ is inadequate even in simple logical contexts. For example, assume an ambiguous meaning $m_1\Vert m_2$ that is in the scope of a negation. If we treat $\Vert$ as $\vee$, then the meaning of $\lnot (m_1\Vert m_2)$ would be $\lnot m_1\wedge \lnot m_2$ – which is obviously wrong, because intuition clearly tells us that $\lnot (m_1\Vert m_2)=\lnot m_1\Vert \lnot m_2$, for example:

This sentence is ambiguous between the meanings of there is no financial institute and there is no strip of land along the river, but it surely does not mean that there is neither of the two. The same holds if we have $m_1\Vert m_2$ in the left-hand side of an implication etc.² The semantic treatment of ambiguity also requires a proper behavior in the course of meaning composition, which is definitely not granted by treating it as disjunction. Hence treating ambiguity as disjunction not only runs counter to most basic intuition, but also destroys the parallelism between the two approaches to ambiguity, whereas they should be equivalent (or at least parallel) at some level. Another problem we only briefly mention is the following: we often find ambiguities between meanings $m_1,m_2$ where $m_1$ entails $m_2$ (as in the two readings of every boy loves a movie). In this case however, $m_1\vee m_2$ is obviously equivalent to $m_2$ – so there would be no ambiguity in the first place! This, however, runs counter to any intuition and again destroys the parallelism between the two approaches to ambiguity. To sum up, we think it is completely inadequate to think of ambiguity in terms of disjunction.

Considering all this, it is surprising that until now, there has not been any serious work on the proper meaning of ambiguity. Of course, there are ample works on aspects of linguistic ambiguity in terms of parasemantic underspecification (see, e.g., [1, 2, Chapter 10], [9, 10]), but none of them, to the best of our knowledge, addresses the meaning of ambiguity on the level of object terms. This is what we want to start in this paper. Obviously, this work can be only preliminary; we will start by considering a very particular case, namely what happens when we add an operator $\Vert$, which satisfies laws we consider adequate for ambiguity, to a Boolean algebra. So we consider Boolean algebras with an additional operator and with some additional axioms fixing its properties. As we will see, it is sufficient to provide a very small set of axioms which we think are correct for ambiguity beyond doubt. From these axioms already follow a lot of other properties we think are correct for ambiguity (in fact, all we can think of). On the other side, we can also derive many more strong properties no one would think are generally true for ambiguity. In this sense, the results of this paper are not fully satisfying. However, they leave us with an interesting puzzle and are highly relevant to anyone who thinks that a semantic approach to ambiguity is worth pursuing. Note that all results are algebraic in nature and thus very general, and by no means bound to any particular notion of meaning, except for the assumption that logical operations are Boolean.

The structure of the rest of this paper is as follows: first, we discuss some fundamental properties of $\Vert$ (that is, semantic ambiguity). This provides the theoretical/semantic motivation for our axiomatization of ambiguous algebras, which is presented in the next section. Subsequently, we present the most important results on ambiguous algebras, which are surprisingly strong, and finally, we discuss what it all means and what purpose it might serve.

3 The Semantics of Linguistic Ambiguity

First let us discuss the relation between $\Vert$ and $\vee$. It is not by chance that, in approaches so far, ambiguity is mostly treated as a disjunction. On thing is obvious: $a\Vert b$ entails $a\vee b$, and moreover, $a\vee b$ is the smallest Boolean object generally entailed by $a\Vert b$. That the two are not identical can be seen from the following considerations: by definition, a entails $a\vee b$ and b entails $a\vee b$. However, it is surely not generally true that a entails $a\Vert b$: ‘financial institute’ does not generally entail ‘bank’; in some uses it does, in other it does not. This clearly depends on the question in which sense the speaker intends an expression with meaning $a\Vert b$ – he could for example intend b by it. So, $a\Vert b$ has the following strictly weaker property: either a entails $a\Vert b$, or b entails $a\Vert b$. Which one of the two holds depends on something we might call the speaker’s “intention", but the latter is nothing we can directly observe. The notion of intention of course is very difficult to grasp, and serious philosophers have done major work just in order to clarify this concept (we just mention [4, 13]). This is not the place to dwell on this notion, so we just clarify our point with an example: suppose speaker A utters:

Then no matter which one of the two you bring him, you surely have fulfilled his desire. Conversely, suppose speaker B utters:

If you bring him some pastry, he might say: But I needed some money!; conversely, if you give him money, he might say: But I just needed pastry!. He might of course also be satisfied with either of the two, he might even be satisfied with just a cup of coffee instead, but that is beside the point. The point is: by uttering dough, he is committed to either ‘money’ or ‘pastry’, but just one of the two in particular, and not an arbitrary one of the two.³ The notion of ambiguity has an epistemic flavor which the truth-functional connectives do not have at all. This will correspond with the fact that $\Vert$, contrarily to Boolean operators, cannot be defined in terms of truth-functions (if it could, it would in fact be redundant, as all binary truth functional operators can be defined by $\wedge ,\ \lnot$). Therefore, it is most natural to consider $\Vert$ in an algebraic (rather than a logical) setting, and it seems most natural to us to start with Boolean algebras, because they correspond to classical propositional logic. Though the correspondence of Boolean algebras and classical logic is close, it is important to keep in mind that all formal treatment in this paper will be algebraic, not logical (we therefore use $\sim$ for algebraic complementation, not $\lnot$ as is generally used for logical negation). Nonetheless, the algebraic relation $\le$ ⁴ can be intuitively read as logical entailment, and the algebraic equality $=$ as logical equivalence. Both will help the intuitive understanding and hardly do any harm, and consequently, we will use $a\le b$ and “a entails b" with a parallel meaning, the former being the algebraic counterpart of the latter. To connect the algebras that we are about to introduce properly to intuition, it is important to keep the following in mind: the objects of the algebra are supposed to be meanings; we are completely agnostic to what they actually are and whether they have any internal structure. These meanings are related by the relations $\le$ (corresponding entailment, definable in terms of $\wedge ,\vee$), and can be combined by means of Boolean connectives and $\Vert$.

Having said this, we can state some intuitively uncontroversial properties: it is obvious that $a\wedge b$ entails $a\Vert b$, and algebraically, $a\wedge b$ is the largest element generally entailing $a\Vert b$. For example, in the particular case where a entails b, this means: a entails $a\Vert b$, and $a\Vert b$ entails b, but $a\Vert b$ does not entail a. This is one important property; the other important property we need is what we call the property of universal distribution. This means that⁵

This property of universal distribution is what makes the semantic approach to ambiguity parallel to the syntactic approach. Logically speaking, this means that $\Vert$ is self-dual. Intuitively, this is clear, because for every ambiguous object, usually one meaning is intended, and this property is preserved over construction of arbitrary Boolean terms. What is very peculiar about $\Vert$ is that it preserves over negative contexts such as negation or the left-hand side of implication.

There are some more properties of $\Vert$ we should mention. One which should be clear is associativity, that is:

This should go without comment, as idempotence:

What is more problematic is commutativity, that is:

One might object that meanings are ordered due to the existence of primary and secondary meanings (cf. the distinction between literal and idiomatic meaning), so commutativity should be rejected. One might alternatively think that in ambiguity, all meanings have the same status, so $\Vert$ should be commutative. We will see, however, that the latter assumption is unwarranted in our algebraic approach, as ambiguous algebras with commutative $\Vert$ are necessarily trivial, that is, they have only one element (so there would be only one meaning).

4 Ambiguous Algebras

4.1 Uniform Usage and Axiomatization

If we want to define $\Vert$ – that is, ambiguity – as an algebraic operation, we have to be aware that in any case, it is a function. This is already a strong commitment, because this implies that for a given linguistic context, in which we use a particular ambiguous algebra,⁶ we have a uniform usage. This can be justified by the hypothesis of uniform usage (UU):

That might seem too strong, but is a prerequisite for any algebraic treatment of ambiguity. Note that this is before all axiomatization, and only concerns the fact that we conceive of $\Vert$ as an operation in an algebra.

A central notion of this paper is the one of a Boolean algebra, which is a structure $\mathbf {B}=(B,\ \wedge ,\ \vee ,\ \sim ,\ 0,\ 1)$. We use the convention that algebras are denoted by boldface letters, whereas their carrier sets are denoted by the same letter without boldface. As Boolean algebras are most well-known, we do not introduce them (the reader interested in background might consider [5, 6], or many other sources). In this paper, we will only use elementary properties of Boolean algebras, these however frequently and without proof or explicit reference. We now provide an axiomatization for ambiguous algebras. An ambiguous algebra is a structure $\mathbf {A}=(A,\ \wedge ,\ \vee ,\ \sim ,\ \Vert ,\ 0,\ 1)$, where $(A,\ \wedge ,\ \vee ,\ \sim ,\ 0,\ 1)$ is a Boolean algebra, and $\Vert$ is a binary operation for which the following holds:

This is sufficient for us: note that this already entails all Eqs. (6)–(10). As is well-known, $\vee$ and $\rightarrow$ are redundant (and the latter will furthermore play no role), and to see that $(a\Vert b)\vee c=(a\vee c)\Vert (b\vee c)$, just consider that

$$\begin{aligned} (a\Vert b)\vee c&\equiv \ \sim (\sim (a\Vert b)\wedge \sim c) \\&=\ \sim ((\sim a\Vert \sim b)\wedge \sim c) \\&=\ \sim ((\sim a\wedge \sim c)\Vert (\sim b\wedge \sim c)) \\&=\,(\sim (\sim a\wedge \sim c))\Vert (\sim (\sim b\wedge \sim c)) \\&\,\equiv (a\vee c)\Vert (b\vee c) \end{aligned}$$

We will see in the structure theory that (ass) and (id) are also derivable from these axioms. As is usual, such an axiomatization comes with a number of questions, to which we shortly provide the following answers (details are to be found in the subsequent sections):

• 1. Do these axioms entail all properties we find intuitively true for ambiguity?

  • As far as we can see, clearly yes.

• 2. Do they imply some properties we find intuitively incorrect for ambiguity in general?

  • Unfortunately, also clearly yes.

• 3. Do non-trivial algebras exist which satisfy these axioms? (That is, for example, algebras with more than one element?)

  • Clearly yes, but if we add commutativity for $\Vert$, then no.

• 4. Are there ambiguous algebras, where $a\Vert b\ne a$ and $a\Vert b\ne b$?

  • No, there are not.

Note, by the way, that ambiguous algebras have a very peculiar axiom, namely $(\Vert 3)$, which is a disjunction. This fact entails that there is no such thing as the free ambiguous algebra over a given set of generators,⁷ and so one of the most important concepts of general algebra is not applicable. Put differently, an algebra (over some set M) in which only the inequations hold which hold in all ambiguous algebras, is not ambiguous algebra! However, we will see later that for every generator set, there are exactly two “free" algebras, that is, ambiguous algebras with a minimal set of equations that hold.

Though this is strange to the algebraist, it nicely models the epistemic component of ambiguity: if we are confronted with a certain algebra, there always hold certain equalities we cannot deduce from general considerations, as in an ambiguous expression, there is always one intended meaning we cannot uniquely construct.

We now show a simple, non-trivial ambiguous algebra. Take the obvious Boolean algebra over the set $\{0, a, b, 1\}$. Put

$a\Vert b=a$;    $b\Vert a=b$;    $0\Vert a=0$;    $1\Vert a=1$;

$a\Vert 1=a$;    $b\Vert 1=b$;    $0\Vert b=0$;    $1\Vert b=1$;

$a\Vert 0=a$;    $b\Vert 0=b$;    $0\Vert 1=0$;    $1\Vert 0=1$;

We can see that $\wedge$-distribution holds: $a=a\Vert b=(a\Vert b)\wedge a=a\Vert 0=a$. $0=0\Vert 1=(0\Vert 1)\wedge a=0\Vert a=0$, and so on, same for $\vee ,\ \sim$. We thus have a proper non-trivial 4-element algebra. The results of the next section will show that this is (up to isomorphism) one of exactly two 4-element ambiguous algebras; in fact, by fixing $a\Vert b=a$, we have fixed the value of $\Vert$ for all arguments.

5 Structure Theory I: Uniformity

We now show the most important results which follow from our axiomatization; in this section we presuppose some familiarity with the elementary theory of Boolean algebras:

Lemma 1

In every ambiguous algebra $\mathbf {A}$ and for all $a,b\in A$, either $a=a \Vert b$ or $b=a\Vert b$.

Proof

Case 1: Assume that $b\not \le a\Vert b$. Then $a\le a\Vert b$, hence ${\sim } a\ge {\sim }(a\Vert b)={\sim } a\Vert {\sim } b$. Now by $(\Vert 3)$, there are two subcases:

Case 1a: ${\sim } a \le {\sim } a\Vert {\sim } b$. Then by another complementation, $a\Vert b\le a$, so $a\Vert b=a$.

Case 1b: ${\sim } b \le {\sim } a\Vert {\sim } b$. Then by iterating complementation, we have $a\Vert b\le b$, hence $a\le a\Vert b\le b$. Hence $(a\Vert b)\vee a=(a\vee a)\Vert (a\vee b)=a\Vert b$ – which by definition of $\le$ means that $a\Vert b\le a$. Hence $a\Vert b= a$.

Case 2: $a \not \le a\Vert b$ – this case is parallel to case 1.

Case 3: Assume that $a, b \le a\Vert b$. Then $a\vee b\le a\Vert b$, and so ${\sim } a\Vert {\sim } b\le {\sim } a,{\sim } b$. By our axioms, we then must have ${\sim } a\Vert {\sim } b={\sim } a$ or ${\sim } a\Vert {\sim } b={\sim } b$; assume the former. Then $a=a\Vert b$ by an iterated complementation. Parallel if we assume the latter.    $\dashv$

It is now easy to see why we cannot reasonably have an axiom for commutativity for $\Vert$: assume we have $a\Vert {\sim } a=a$.⁸ Then ${\sim } a\Vert a=a$ as well; but also ${\sim }({\sim }a\Vert a)={\sim }\sim a\Vert {\sim }a=a\Vert {\sim } a=a$, hence ${\sim } a=a$, which only holds in 1-element algebras. A parallel argument can obviously be applied if $a\Vert {\sim } a={\sim } a$.

Corollary 2

If $\mathbf {A}$ is an ambiguous algebra such that for all $a,b\in A$, $a\Vert b=b\Vert a$, then A has at most one element.

The next result also follows in a straightforward fashion:

Corollary 3

For all ambiguous algebras $\mathbf {A}$, $a,b\in A$, we have

So we have two more desired properties of $\Vert$ which follow from our axiomatization. The next result is more difficult to obtain and is the first one in a series of results which are stronger than our intuition on ambiguity.

Lemma 4

(Monotonicity of $\Vert$). Assume $a'\le a$ and $b'\le b$. Then $a'\Vert b'\le a\Vert b$.

Proof

There are four possibilities for the values of $a\Vert b$ and $a'\Vert b'$. Two of them trivially entail the claim, and the other two are parallel. So assume without loss of generality that $a\Vert b=a$ whereas $a'\Vert b'=b'$. We then have

Conversely, we have

and consequently

So we have (by (11) and (13)) $a=a\Vert (a\vee b')=a\vee b'$, which by definition means that $b'\le a$, hence $a'\Vert b'=b'\le a= a\Vert b$.    $\dashv$

This result is seemingly strong, but it is only an intermediate step in the proof of the still stronger uniformity lemma. However, it already has the following immediate consequence: it means that ambiguity roughly behaves in a logical way, respecting logical entailment. In fact, if it where wrong, then there would be hardly any way to think of $\Vert$ as a (non-classical) logical connective, because it would not necessarily respect any consequence relation. Secondly, the result has an intuitive semantic meaning: it means that if we assume the weak hypothesis of uniform usage (UU), then this already entails a very strong uniform usage, namely if we use an ambiguous term s with meaning $a\Vert b$ in the sense of a, then we must use all terms with a meaning which is related by implication in a way which is consistent with this usage. This is a strong surprising feature which comes for free, given UU. In the following, we will strengthen this. First, take the following list of results:

Lemma 5

Let $\mathbf {A}$ be an ambiguous algebra, $a\in A$. If $a\Vert {\sim } a=a$, then

Proof

1. follows by negation distribution; 2. is because $({\sim } a\Vert a)\vee a=1\Vert a={\sim } a\vee a=1$. Results 3.–9. follow in a similar fashion from the distributive laws. To see why 10. holds, assume conversely that $0\Vert 1=1$. Then we have

– a contradiction to 3. 11. follows by distribution of ${\sim }$.    $\dashv$

Obviously, this lemma has a dual where $a\Vert {\sim } a={\sim } a$, and where all results are parallel.

Lemma 6

Let $\mathbf {A}$ be an ambiguous algebra. If for an arbitrary $a\in A$, we have $a\Vert {\sim } a=a$, then for all $b, c\in A$ we have $b\Vert c=b$; conversely, if we have $a\Vert {\sim } a={\sim } a$, then for all $b, c\in A$ we have $b\Vert c=c$.

Proof

We only prove the first part, the second one is dual.

Assume $a\Vert {\sim } a=a$, and assume $b\Vert c=c$. By the previous lemma, we know that $0\Vert 1=0$. We then have $b\Vert 1=(0\Vert 1)\vee b=0\vee b=b$. Now assume $c\not \le b$. Then $b\Vert c\not \le b\Vert 1$ – contradiction to monotonicity (Lemma 4). Hence $c\le b$.

By the previous lemma, also $1\Vert 0=1$. So we have $1\Vert c=(1\Vert 0)\vee c=1$. As $c\le b$, $c\wedge b=c$, so we have

Conversely,

Hence by (*), (+) $b\Vert c=b$, so by assumption $b=c$ and the claim follows.    $\dashv$

Now we can prove the strongest result on $\Vert$, the uniformity lemma.

Lemma 7

(Uniformity lemma). Assume we have an ambiguous algebra $\mathbf {A}$ $a,b\in A$ such that $a\ne b$.

• 1. If $a\Vert b=a$, then for all $c,c'\in A$, we have $c\Vert c'=c$;

• 2. if $a\Vert b=b$, then for all $c,c'\in A$, we have $c\Vert c'=c'$.

Proof

We only prove 1., as 2. is completely parallel. Assume there are $a,b\in A$, $a\ne b$ and $a\Vert b=a$. Assume furthermore there are $c,c'\in A$ such that $c\Vert c'\ne c$. There are two cases:

(i) there is such a pair $c,\,c'$ such that $c'={\sim } c$. Then the dual result of the previous lemma leads us to a contradiction, because we then have $c\Vert {\sim } c={\sim } c$, and consequently $a\Vert b=b$, which is wrong by assumption – contradiction.

(ii) there are no such pair $c,c'$. Then however we necessarily have (among other) $a\Vert {\sim } a=a$, and by the previous lemma, this entails $c\Vert c'=c$ – contradiction.    $\dashv$

Put differently:

Corollary 8

If $\mathbf {A}$ is an ambiguous algebra, $a,b\in \mathbf {A}$, then either for all $a,b\in A$, we have $a\Vert b=a$, or for all $a,b\in A$, we have $a\Vert b=b$.

We therefore can say an ambiguous algebra $\mathbf {A}$ is left-sided, if for all $a,b\in A$, $a\Vert b=a$; it is right-sided if for all $a,b\in A$, $a\Vert b=b$. The uniformity lemma says that every ambiguous algebra is either right-sided or left-sided, and only the trivial one-element algebra is both. Needless to say, it is hard to intuitively make sense of this result, as it is much stronger property than any of our intuitions on the meaning of ambiguity would suggest. Still it is very important as a negative result for the semantic treatment of ambiguity in the context of Boolean algebras.

One might consider this a triviality result, and in some sense it is. However, it does not imply triviality for the equations which hold in all ambiguous algebras, which is the really crucial notion for inference from ambiguous meanings. Let us consider the following examples:

holds in all ambiguous algebras. This can be shown as follows: we have

Now in every left-sided ambiguous algebra, we have $((a\rightarrow a)\Vert (a\rightarrow b))=1$; in every right-sided ambiguous algebra we have $((b\rightarrow a)\Vert (b\rightarrow b))=1$, and as every ambiguous algebra is either right-sided or left-sided, the claim follows. Conversely,

holds in some, but not all ambiguous algebras, as can be easily seen in case where $a\Vert b=b,b\Vert a=a$. Another equation which holds in all ambiguous algebras is the following:

This is to say $\Vert$ distributes “over itself”. The next is also easy to show:

Lemma 9

In all ambiguous algebras, we have $(a\Vert b)\Vert c= a\Vert c=a\Vert (b\Vert c)$.

Proof

Every algebra is either left sided, and then $(a\Vert b)\Vert c=a=a\Vert c$, or right-sided, then $(a\Vert b)\Vert c=c=a\Vert c$.    $\dashv$

So the associativity of $\Vert$ follows from $(\Vert 1)$–$(\Vert 3)$. Moreover, every multiple ambiguity can be reduced to an ambiguity of only two terms. This is a very interesting result for decidability,⁹ though it runs counter to our intuitions on ambiguity: linguistically it would mean that any ambiguity between an arbitrary number of meanings is equivalent to an ambiguity between two meanings.

6 The Meaning of Uniformity

The uniformity lemma is obviously a very strong result. Whereas its algebraic meaning should be clear, it is not so clear how it relates to our intuitions on ambiguity, from which we have started after all. To clarify this, it is preferable to first consider the monotonicity Lemma 4, which is a weaker result. This lemma states that if $a\le a'$, $b\le b'$, then $a\Vert b\le a'\Vert b'$. This roughly means: ambiguity respects logical entailment. Let us illustrate this with an example; take the lexically ambiguous word bank; and assume that it has the meaning $a\Vert b$, a being ‘strip of land along a river’, b being ‘financial institute’. Next consider the (complex) expression bank or restaurant. Say restaurant has meaning c, hence the expression has the meaning $(a\Vert b)\vee c=(a\vee c)\Vert (b\vee c)= a'\Vert b'$. Now as $\le$ corresponds to entailment, this means that if monotonicity were wrong, then bank would not (generally) entail bank or restaurant, simply because in the one expression it could mean one thing, in the other expression the other. This however obviously contradicts the hypothesis of uniform usage.¹⁰ Now monotonicity can be read as a strengthening of this hypothesis: even if there was a single word kank with the same meaning as bank or restaurant, using bank in one sense would constrain us to using kank in the related sense. Hence monotonicity is like uniform usage for expressions which are connected by the relation of entailment. In this sense we say that ambiguity respects entailment.

Now the underlying reason for uniformity is that in ambiguous algebras, all elements are strongly connected, in particular because there are elements such as $0\Vert 1$, $1\Vert 0$ (which surely do not have any linguistic counterpart). Thereby, we can establish that if we use one ambiguous expression in the left/right sense (whatever that means), we have to use all expressions in the same sense. This is surely completely unintuitive, and a consequence of two things:

• 1. the strong axioms of Boolean algebras, in particular the equality ${\sim }{\sim } a=a$ we repeatedly use, and

• 2. the fact that $\Vert$ is a total operator, that is, for all a, b, we have an object $a\Vert b$.

So there are two ways to remedy the situation: 1. Consider algebras with weaker axioms than Boolean algebras. In particular, if we add the ambiguity operator and axioms $(\Vert 1)$–$(\Vert 3)$ to Heyting algebras (corresponding to intuitionistic logic), many of the results presented so far do no longer seem to hold. 2. to assume that $\Vert$ is a partial operator, or put differently, that a Boolean algebra only contains certain ambiguous elements. To us, both roads seem to be promising, in particular the one of partially ambiguous algebras. In these, we can investigate which ambiguous elements are independent and which not (in the sense that $\Vert$ has to be uniform for them). However, both topics deserve and need a treatment on their own, so for the rest of the paper, we rather complete the theory of ambiguous Boolean algebras by showing some results on their existence and construction, from which it is easy to derive results on decidability (however we do not present the latter for reasons of space).

7 Structure Theory II: Completions

We have given an example of one non-trivial ambiguous algebra. The previous section has provided us with restrictions on possible algebras. In this part, we will show that nonetheless every Boolean algebra can be completed to an ambiguous algebra. From the uniformity lemma, it easily follows that there are at most two such completions; we now prove there are exactly two. It also easily follows that every ambiguous algebra is the completion of a Boolean algebra.

Definition 10

Let $\mathbf {B}=(B,\wedge ,\vee ,{\sim },0,1)$ be a Boolean algebra. We define the left ambiguous completion of $\mathbf {B}$ to be the ambiguous algebra $C_l(\mathbf {B}):=(B,\wedge ,\vee ,{\sim },\Vert ,0,1)$, where for all $a,b\in B$, we have $a\Vert b=a$; the right ambiguous completion $C_r(\mathbf {B})$ is defined in the parallel fashion, where $a\Vert b=b$.

We mostly say only right/left completion, as there is no source of confusion.

Lemma 11

If $\mathbf {B}$ is a Boolean algebra, then both $C_l(\mathbf {B})$ and $C_r(\mathbf {B})$ are ambiguous algebras.

Proof

We simply check whether it satisfies the axioms. $(\Vert 3)$ is clear by definition. We check the distributivity axioms (for simplicity, we only consider left-completions; the right case is completely parallel):

${\sim }$-distributivity: we have $a\Vert b=a$, so ${\sim } (a\Vert b)={\sim } a={\sim } a\Vert {\sim } b$.

$\wedge$-distributivity: we have $(a\Vert b)\wedge c=a\wedge c=(a\wedge c)\Vert (b\wedge c)$.    $\dashv$

The following is also quite simple:

Lemma 12

Every ambiguous algebra $\mathbf {A}$ is isomorphic either to $C_l(\mathbf {B})$ or $C_r(\mathbf {B})$ for some Boolean algebra $\mathbf {B}$.

Proof

Straightforward consequence of the uniformity lemma.    $\dashv$

We now formally prove the existence of non-trivial algebras, more concretely: for every Boolean algebra $\mathbf {B}$, the Boolean algebra reduct of both $C_l(\mathbf {B})$ and $C_r(\mathbf {B})$ is identical to $\mathbf {B}$; this means that the ambiguous algebra axioms do not collapse any two elements. This has a number of consequences, among other for decidability.

Let t be a term of an ambiguous algebra. We define the map $\pi _l$ as follows:

The right projection $\pi _r$ is defined in the same way, with 5. changed to $\pi _r(t\Vert t')=\pi _r(t')$. An easy induction yields the following:

Lemma 13

Let $\mathbf {A}$ be a left- (right-)sided ambiguous algebra, s, t terms over $\mathbf {A}$. Then $s=t$ holds in $\mathbf {A}$ iff $\pi _l(s)=\pi _l(t)$ ($\pi _r(s)=\pi _r(t)$) holds in $\mathbf {A}$.

Proof

Easy induction over complexity of s, t.    $\dashv$

In order to prove the crucial result of this section, we need to introduce a class of structures which we call $AA'$-algebras. These have the same signature as ambiguous algebras, but a different set of axioms:

Definition 14

A structure $\mathbf {A}=(A,\,\wedge ,\,\vee ,\,{\sim },\,\Vert ,\,0,\,1)$ is a left $AA'$-algebra, if $(A,\wedge ,\vee ,{\sim },0,1)$ is a Boolean algebra, and for all $a,b\in A$, we have $a\Vert b=a$. $\mathbf {A}$ is a right $AA'$-algebra, if $(A,\wedge ,\vee ,{\sim },0,1)$ is a Boolean algebra, and for all $a,b\in A$, we have $a\Vert b=b$.

So $AA'$-algebras are less restrictive in the sense that they do not satisfy the additional axioms $(\Vert 1)$–$(\Vert 3)$. For us, they are useful because they allow to establish the following lemma. By $\mathsf {id}_M$, we generally denote functions which compute the identity on some domain M.

Lemma 15

Every Boolean algebra $\mathbf {B}=(B,\wedge ,\vee ,{\sim },0,1)$ can be completed to a left/right $AA'$-algebra $\mathbf A' =(B,\wedge ,\vee ,{\sim },\Vert ,0,1)$ such that the map $\mathsf {id}:\mathbf A' \rightarrow \mathbf {B}$ is a Boolean algebra isomorphism.

Proof

The completion is obvious, and a straightforward induction on its Boolean terms shows that $\mathsf {id}:\mathbf A' \rightarrow \mathbf {B}$ is a Boolean algebra isomorphism.    $\dashv$

The completions are unique, so we call this the left/right $AA'$-completion, and denote it by $C'_l(\mathbf {B})$, $C'_r(\mathbf {B})$. Let $\cong$ denote the relation of isomorphy, which says that there is a bijection between two structures which preserves the results of all operations.

Lemma 16

For all Boolean algebras $\mathbf {B}$, we have $C'_l(\mathbf {B})\cong C_l(\mathbf {B})$ and $C'_r(\mathbf {B})\cong C_r(\mathbf {B})$.

Proof

We only consider the left case. $C_l(\mathbf {B})$ is the algebra which satisfies (1) all equations of $\mathbf {B}$, (2) $a\Vert b=a$, and (3) all of $(\Vert 1)$–$(\Vert 3)$. To prove the lemma, we only need to show that the same holds for $C'_l(\mathbf {B})$. For (1) and (2), this is straightforward. So we only prove that $C'_l(\mathbf {B})$ satisfies $(\Vert 1)$–$(\Vert 3)$.

$(\Vert 1)$ ${\sim }(a\Vert b)={\sim } a={\sim } a\Vert {\sim } b$

$(\Vert 2)$ $a\wedge (b\Vert c)=a\wedge b=(a\wedge b)\Vert (a\wedge c)$.

$(\Vert 3)$ By definition, $a\le a\Vert b$.    $\dashv$

The next result is really a central lemma, in particular our subsequent decidability results rely on it. In particular it shows the existence of infinitely many non-isomorphic ambiguous algebras.

Lemma 17

(Completion lemma). Every Boolean algebra $\mathbf {B}=(B,\wedge ,\vee ,{\sim },0,1)$ can be completed to an ambiguous algebra $\mathbf {A}=(B,\wedge ,\vee ,{\sim },\Vert ,0,1)$ such that the map $\mathsf {id}:\mathbf {A}\rightarrow \mathbf {B}$ is a Boolean algebra isomorphism.

Proof

By Lemma 15, we know the claim holds for $C'_l(\mathbf {B})$, $C'_r(\mathbf {B})$. By Lemma 16, $C'_l(\mathbf {B})\cong C_l(\mathbf {B})$ etc., and as the composition of two isomorphisms is still an isomorphism, the claim follows.    $\dashv$

Corollary 18

Let $\mathbf {B}=(B,\wedge ,\vee ,{\sim },0,1)$ be a Boolean algebra, and assume $a,b\in B$. Then $a=_\mathbf {B}b$ iff $a=_{C_l(\mathbf {B})}b$ iff $a=_{C_r(\mathbf {B})}b$.

This states that we cannot derive new equalities between objects which are distinct in $\mathbf {B}$, which follows from Lemma 17 (because otherwise $\mathsf {id}$ would not be a bijection). We can formulate this result in another, more general fashion:

Corollary 19

For every Boolean algebra $\mathbf {B}$ there are (up to isomorphism) exactly two ambiguous algebras $\mathbf {A}$ such that there is a bijection $i:\mathbf {B}\rightarrow \mathbf {A}$ which is a Boolean algebra isomorphism.

The existence of two algebras is witnessed by $C_l(\mathbf {B})$, $C_r(\mathbf {B})$; the fact that up to isomorphism there are at most two such algebras follows from the uniformity lemma.

8 Conclusion and Further Work

Our treatment of ambiguous Boolean algebras seems to be complete in the sense that every interesting result on them seems to be either stated explicitly or easily derivable from the results stated here. This is not as much due to excessive treatment as to the fact that ambiguous Boolean algebras are very similar to Boolean algebras (which are excessively treated in many places), maybe too similar to be really interesting. In particular the uniformity lemma and the completion lemma show that there is little of interest to say about ambiguous algebras which does not already hold for Boolean algebras. Still we consider it important to have established these results, which are really obvious or trivial.

Furthermore, our algebraic results are surely not fully compatible with linguistic intuition. The uniformity lemma suggests that all ambiguous terms are either right- or left-ambiguous. Even if there is some flexibility in choosing an algebra depending on the context, this would have to be fixed in advance and ironically contravenes any possibility to establish an order of operands in terms of literal and idiomatic meaning. The weaker monotonicity result, by contrast, which states that words in entailment relations are used consistently meaning-wise, seems much more intuitive and preferable. Nevertheless, the presented work is a first necessary approximation relying on an obvious choice, namely Boolean algebras, corresponding to classical propositional logic. Note that our negative results also have a positive side: it entails that for establishing a semantic notion of ambiguity, we either need to reject the Boolean axioms, or the idea that ambiguity is possible between arbitrary meanings. So if we start to take semantic ambiguity seriously, it can help us gain genuine insights into semantic structure.

The further investigation of the algebraic treatment of ambiguity seems to be very interesting and promising. As we have already mentioned, there are two main directions to pursue: One approach would be the following: instead considering $\Vert$ and $(\Vert 1)$–$(\Vert 3)$ in the context of Boolean algebras, we can consider it in other, more general classes of algebras which are important for reasoning purposes, such as (distributive, modular) lattices, residuated lattices, Heyting algebras and many more. The proof of the uniformity lemma (and many other results) rely on the law of excluded middle ($a\,\vee {\sim } a=1$), which does not hold in all these algebras, so enriching them with an operator $\Vert$ and axioms $(\Vert 1)$–$(\Vert 3)$ might result in a much richer structure theory. What can still be derived in more general cases is the monotonicity for $\Vert$, which is not nearly as strong as uniformity. The second approach would be to investigate Boolean algebras in which $\Vert$ is partial, that is, there are some ambiguous elements, but ambiguity is not a total operator for arbitrary objects. We plan to further pursue both lines in further research.