# Comparing exhaustivity operators

Benjamin Spector

► To cite this version:

Benjamin Spector. Comparing exhaustivity operators. Semantics and Pragmatics, 2017, 9 (11), 10.3765/sp.9.11. hal-03877047

HAL Id: hal-03877047

https://hal.science/hal-03877047

Submitted on 29 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

# Comparing exhaustivity operators*

Benjamin Spector

Institut Jean Nicod (ENS - EHESS - CNRS)

Département d'études cognitives,

École normale supérieure - PSL Research University

Submitted 2015-03-06 / First decision 2015-06-10 / Revision received 2015-08-23 / Second decision 2015-09-22 / Revision received 2015-10-22 / Accepted 2016-02-09 / Early access published 2016-04-28 / Published 2017-03-12

**Abstract** In this paper, I investigate the formal relationships between two types of exhaustivity operators that have been discussed in the literature, one based on *minimal worlds/models*, noted $exh_{mw}$ (van Rooij & Schulz 2004, Schulz & van Rooij 2006, Spector 2003, 2006, with roots in Szabolcsi 1983, Groenendijk & Stokhof 1984), and one based on the notion of *innocent exclusion*, noted $exh_{ie}$ (Fox 2007). Among others, I prove that whenever the set of alternatives relative to which exhaustification takes place is semantically closed under conjunction, the two operators are necessarily equivalent. Together with other results, this provides a method to simplify, in some cases, the computation associated with $exh_{ie}$, and, in particular, to drastically reduce the number of alternatives to be considered.

Besides their practical relevance, these results clarify the formal relationships between both types of operators.

**Keywords:** exhaustivity operators, innocent exclusion

<footnote>* I thank Emmanuel Chemla, Philippe Schlenker and Bernhard Schwarz for extremely useful exchanges. In particular, Bernhard Schwarz noticed several mistakes, including an important one, in a previous version of this paper. Fixing this mistake helped me to expand the scope of this paper. Emmanuel Chemla helped me to simplify the proof of Theorem 9. Let me also thank David Beaver, Michael Franke and two anonymous reviewers for extremely useful remarks on previous versions of this paper. The research leading to these results has received funding from the Agence Nationale de la Recherche (grants ANR-10-LABX-0087 IEC and ANR-10-IDEX-0001-02 PSL).</footnote>
# 1 Introduction

In the literature on scalar implicatures and exhaustivity effects, it has proved useful to define so-called *exhaustivity operators*. Such operators take two arguments, a proposition $\varphi$ and a set of propositions ALT (the alternatives of $\varphi$), and return a proposition that entails $\varphi$, which corresponds to the pragmatically strengthened meaning of $\varphi$ (the conjunction of $\varphi$ and its quantity implicatures). A simple (and ultimately inadequate) version of the exhaustivity operator, which is a variation on Krifka's (1993) entry for the word *only*, is the following:

(1) a. $exh_{krifka}(ALT, \varphi) =$
$\lambda w.\varphi(w) = 1 \wedge \forall a((a \in ALT \wedge a(w) = 1) \rightarrow (\varphi \subseteq a))$

b. Equivalently:<fnref n="1" />
$exh_{krifka}(ALT, \varphi) = \varphi \wedge \neg\{a: a \in ALT \wedge \varphi \text{ does not entail } a\}$

c. In words:
$exh_{krifka}(ALT, \varphi)$ states that $\varphi$ is true and that every member of ALT that is true is entailed by $\varphi$, i.e., every non-entailed member of ALT is false.

Now, this operator has been known for quite some time to be inadequate, particularly for disjunctive sentences. For instance, under standard assumptions, a sentence $S$ of the form $p \lor (q \lor r)$ has, among its alternatives, the sentence $\alpha = p \lor (q \land q)$. Because this alternative is not entailed by $S$, applying $exh_{krifka}$ to $S$ and its set of alternatives will result in a meaning that entails the negation of $\alpha$, hence the negation of $p$ — which is clearly a wrong result (cf. Chierchia 2004).

Among the various solutions to this problem, a quite common one consists in a) weakening the definition of the exhaustivity operator so that it is no longer the case that it negates all non-entailed alternatives, and b) ensuring that when a disjunctive phrase $a \lor b$ occurs in a sentence $S$, which can be represented as $S(a \lor b)$, the set of alternatives for $S$ includes $S(a)$ and $S(b)$ (cf. Sauerland 2004, Spector 2003, 2007).

Two more sophisticated exhaustivity operators have been proposed along these lines, both of which improve on $exh_{krifka}$.

<footnote n="1">¹ When $X$ is a set of propositions, $\wedge X$ refers to the grand conjunction of its members, i.e., the proposition that is true in a world $u$ if and only if every member of $X$ is true in $u$, and $\lor X$ refers to the grand disjunction of the members of $X$, i.e., the proposition that is true in a world $u$ if and only if at least one member of $X$ is true in $u$.</footnote>
The older one (van Rooij & Schulz 2004, Schulz & van Rooij 2006, Spector 2003, 2006, 2007, with roots in Szabolcsi 1983, Groenendijk & Stokhof 1984) works informally as follows. It takes two arguments, a set of alternatives ALT (henceforth ‘alternative set’) and a proposition φ, and it returns the proposition that consists of all the φ-worlds that *minimize* the set of true alternatives. That is, the exhaustification of a proposition φ retains the set of φ-worlds in which as few alternatives as possible are true. I will henceforth use the notation *exh*<sub>mw</sub> to refer to this operator. Under a specific formalization of the Gricean reasoning, the output of *exh*<sub>mw</sub> can be proven to be equivalent to the output of Gricean reasoning (van Rooij & Schulz 2004, Schulz & van Rooij 2006, Spector 2003, 2006, 2007).

The second exhaustivity operator was proposed more recently in Fox 2007. Fox's operator also takes a set of alternatives ALT and a proposition φ as arguments, and it returns the conjunction of φ and of the negations of some members of ALT, those that are *innocently excludable*, in a sense made precise. I will use *exh*<sub>ie</sub> to refer to this operator. Fox motivates *exh*<sub>ie</sub> by showing that the free-choice effect triggered by disjunction in the scope of a possibility modal can be predicted to arise when *exh*<sub>ie</sub> is applied twice to the relevant sentences (provided some specific assumptions are made about the nature of alternative sets). As Fox discusses, this account of free-choice effects would not work if one used *exh*<sub>mw</sub> rather than *exh*<sub>ie</sub>.

Before moving on, it is worth noticing that in certain cases, the choice
between $exh_{krifka}$, $exh_{mw}$ and $exh_{ie}$ does not matter. In fact, whenever the
result of $exh_{krifka}$ is non-contradictory, the three operators are equivalent
(Fact 1 below).

Recently, a number of works on scalar implicatures have adopted $exh_{ie}$.
However, in many cases, one could have as well adopted $exh_{mw}$, because
$exh_{ie}$ and $exh_{mw}$, in the relevant cases, deliver the same result, a fact that
sometimes goes unnoticed.<fnref n="2" />

The primary goal of this paper is to characterize the conditions under
which $exh_{ie}$ and $exh_{mw}$ are equivalent. I will, more generally, investigate the
formal relationships between $exh_{ie}$ and $exh_{mw}$. As I will discuss shortly,

<footnote n="2">² In particular, $exh_{ie}$ is sometimes presented as motivated by the need to solve the problem raised by sentences such as $p \lor (q \lor r)$ without any reference to the fact that that $exh_{mw}$, which was introduced more than 20 years before (Groenendijk & Stokhof 1984), is equivalent to $exh_{ie}$ for such cases — Fox (2007), which introduced $exh_{ie}$, does not fail to acknowledge this fact.</footnote>
the formal results I will report have both practical and possibly theoretical relevance. But first let me state some particularly relevant results (which are reported in more formal terms and with some other results in section 3, and proved in section 5):

1. Given a set of alternatives ALT, closing ALT under disjunction, or conjunction, or both, cannot change anything for the output of $exh_{mw}$ (Proposition 3 below).

2. Given a set of alternatives ALT, closing ALT under disjunction cannot change anything for the output of $exh_{ie}$ (Theorem 10 below).

3. Given a proposition $\varphi$ and a set of alternatives ALT, if ALT is closed under conjunction, both operators are equivalent, i.e., $exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi)$ (Theorem 9 below).

4. Given a proposition $\varphi$ and a set of alternatives ALT, if the closure of ALT under disjunction is itself closed under conjunction, then again $exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi)$ (Corollary 11 below).

5. Irrespective of whether ALT is closed under conjunction, given a proposition $\varphi$ and a set of alternatives ALT, an alternative $a$ in ALT is *innocently excludable* (in the technical sense that will be defined below) if and only if $exh_{mw}(ALT, \varphi)$ entails $
eg a$. For this reason, $exh_{ie}(ALT, \varphi)$ can be straightforwardly defined in terms of $exh_{mw}(ALT, \varphi)$, and, furthermore, $exh_{mw}(ALT, \varphi)$ always entails $exh_{ie}(ALT, \varphi)$ (Propositions 6 and 7 and corollary 8).

6. Given a sentence $S$ obtained from a set of elementary sentences $E$ by combining them with disjunction and conjunction, if $S$'s alternatives ALT are determined on the basis of Sauerland's (2004) procedure, then applying $exh_{ie}$ to $S$ relative to ALT is equivalent to applying $exh_{mw}$ to $S$ relative to $E$ (Theorem 12 below).

But why does this matter? First, these results are useful to identify the cases that provide decisive evidence for or against one type of exhaustivity operator. Trivially, when we are dealing with a case where the two operators are known to be equivalent, nothing can be concluded from this case about which operator should be used. Fox's argument for using $exh_{ie}$ is, obviously, based on a case where the two operators deliver different results, precisely because the alternative set he assumes is not closed under conjunction.
Second, these results also have practical (and possibly theoretical) relevance, as I will discuss in section 4. It will appear that computing the output of $exh_{mw}$ is often easier than computing the result of $exh_{ie}$. The reason is the following: given broadly accepted views about the alternatives triggered by disjunction (based on Sauerland 2004), the number of alternatives to consider quickly increases as a sentence's complexity increases (Mascarenhas 2014). Now, it follows from Result 1 above that if one uses $exh_{mw}$, it is often possible to ignore most of the alternatives without any change in the output, because it is sufficient to consider a subset of the alternatives whose closure under disjunction and conjunction is the same as that of the original set. As a result, $exh_{mw}$ is often more tractable than $exh_{ie}$. So even if one's favorite approach is based on $exh_{ie}$, in every case where the two operators are known to yield the same result (e.g., when alternatives are closed under conjunction, or when the closure of alternatives under disjunction is closed under conjunction, cf. Results 3 and 4), it will often be easier to work with $exh_{mw}$. And even in cases where the two operators do not yield the same result, the fact that one can define $exh_{ie}$ in terms of $exh_{mw}$ (Result 5) can help make the innocent-exclusion operator more tractable.

At the same time, it is important to highlight the limitations of the results reported in this paper. In particular, Result 6 (more formally stated as Theorem 12 below) does *not* entail that, if we adopt Sauerland's procedure for computing alternatives, the outcome of $exh_{ie}$ with respect to the full set of alternatives is always the same as that of $exh_{mw}$ with respect to some smaller set of alternatives. As stated, the result holds only for sentences whose only alternative-inducing expressions are disjunction and conjunction and where these disjunctions and conjunctions are not embedded under other operators, that is, cases that can be modeled as sentences obtained from atomic sentences by combining them with disjunction and conjunction—I illustrate this point in the last paragraph of section 2.2.2 below. However, there are cases which are not covered by Result 6 (i.e., Theorem 12) but where alternative sets nevertheless happen to be closed under conjunction (or are such that their closure under disjunction is closed under conjunction), so that results 3 and 4 are applicable—which makes it possible to use $exh_{mw}$ in order to compute the outcome of $exh_{ie}$.^3

<footnote n="3">³ I believe that Result 6/Theorem 12 can be extended to some other configurations, but do not attempt such an extension in this paper. For a number of cases which are not covered by Theorem 12 as stated, it is easy, based on the results reported in this paper, to reduce the computation of $exh_{ie}$ to the application of $exh_{mw}$ relative to a small set of alternatives.</footnote>
In the next section, I will provide the necessary background: definitions for both operators, and illustrations based on simple examples, showing that both operators sometimes yield the same result, but not always.

# 2 Background and examples

## 2.1 Definitions

In the context of this paper, the notion of *world* is identical to that of *model*. That is, a world assigns a denotation to every non-logical atomic expression of the language, and, through compositional semantic rules, a truth-value to every sentence in the language. The proposition expressed by a sentence is the set of worlds in which this sentence is true. To mean that a proposition $\varphi$ is true (resp. false) in a world $u$ (or, equivalently, that $u$ makes $\varphi$ true), I write $\varphi(u) = 1$ (resp. $\varphi(u) = 0$), rather than $u \in \varphi$ (resp. $u \notin \varphi$). That is, I sometimes use $\varphi$ to represent the characteristic function of its denotation. However, I also adopt the set-theoretic notation $\varphi \subseteq \psi$ to mean that $\varphi$ entails $\psi$.

When dealing with *propositions* rather than sentences, I use negation, disjunction, conjunction, etc., as standing for their set-theoretic equivalent (e.g., $\neg \varphi$ denotes the set of worlds which do not belong to $\varphi$, disjunction corresponds to union, etc.). To facilitate reading, I will often ignore the first argument of $exh_{ie}$ and $exh_{mw}$ (namely the alternative set), which is then understood to be a certain set ALT, and will thus simply write $exh_{mw}(\varphi)$ and $exh_{ie}(\varphi)$, instead of $exh_{mw}(ALT, \varphi)$ and $exh_{ie}(ALT, \varphi)$.

When I talk about a set of alternatives, I generally mean a set of *propositions*, not sentences. Of course, quite often alternatives are viewed as sentences that are obtained from a given sentence by a number of syntactic operations (such as replacement of a scalar item with another scalar item). However, what counts for $exh$ is the set of propositions that the alternatives express. So when I talk, for instance, about the number of distinct alternatives for a given sentence, under, say, Sauerland's characterization of alternatives, I am referring to the number of *semantically distinct* alternatives. There may be a finite number of semantically distinct alternatives even if there are infinitely many syntactic alternatives.

**Definitions 1.**
1. Given a set of alternatives ALT, $\leq_{ALT}$ is the preorder over possible worlds defined as follows:

$$u \leq_{ALT} v \text{ iff } \{a \in ALT: a(u) = 1\} \subseteq \{a \in ALT: a(v) = 1\}$$

2. Given a set of alternatives ALT, $<_{ALT}$ is the strict preorder over possible worlds corresponding to $\leq_{ALT}$:

$$u <_{ALT} v \text{ iff } u \leq_{ALT} v \wedge \neg(v \leq_{ALT} u).$$

(I.e., the alternatives that $u$ makes true are a proper subset of those that $v$ makes true.)

I will sometimes omit the subscript ALT.

**Definition 2.** Exhaustivity operator based on minimal worlds ($exh_{mw}$).

Given a set of propositions ALT and a proposition $\varphi$,

$$exh_{mw}(ALT, \varphi) = \{u: \varphi(u) = 1 \wedge \neg\exists v(\varphi(v) = 1 \wedge v <_{ALT} u)\}$$

$$\text{Equivalently: } exh_{mw}(ALT, \varphi) = \varphi \cap \{u: \neg\exists v(\varphi(v) = 1 \wedge v <_{ALT} u)\}.$$

Fox's operator is based on the notion of 'innocent exclusion', and its definition is more complex, as it requires a number of intermediate steps. My presentation is slightly different from Fox's, but is fully equivalent. I start with auxiliary definitions:

**Definitions 3.**

1. A set of propositions $X$ is *consistent* if there exists a world $u$ in which every member of $X$ is true.

2. Given a proposition $\varphi$ and a set of alternatives ALT, a set of propositions $E$ is $(ALT, \varphi)$-*compatible* if and only if a) $\varphi \in E$, b) every member of $E$ distinct from $\varphi$ is the negation of a member of ALT, and c) $E$ is consistent.

3. $\text{MC}_{(ALT,\varphi)}$-sets: A set is *maximal* $(ALT, \varphi)$-*compatible* $(\text{MC}_{(ALT,\varphi)}$-set for short) if it is $(ALT, \varphi)$-compatible and is not properly included in any other $(ALT, \varphi)$-compatible set (sometimes the subscript $(ALT,\varphi)$ will be omitted).

4. $\text{IE}_{(ALT,\varphi)} = \{\psi: \psi \text{ belongs to every } \text{MC}_{(ALT,\varphi)}\text{-set}\}^4$

<footnote n="4">4 Note that, somewhat counter-intuitively, the set $\text{IE}_{(ALT,\varphi)}$ is not the set of innocently excludable alternatives, but rather the set that contains $\varphi$ and all the negations of innocently excludable alternatives.</footnote>
5. An alternative a is innocently excludable given ALT and $\varphi$ if and only if $\neg a \in \text{IE}_{(ALT,\varphi)}$.

**Definition 4.** Exhaustivity operator based on innocent exclusion ($exh_{ie}$).

$$exh_{ie}(ALT, \varphi) = \{u: \forall \psi (\psi \in \text{IE}_{(ALT,\varphi)} \rightarrow \psi(u) = 1)\}.$$

Equivalently: $exh_{ie}(ALT, \varphi) = \bigwedge \text{IE}_{(ALT,\varphi)}$

Equivalently: $exh_{ie}(ALT, \varphi) = \varphi \wedge \bigwedge \{\neg a: a \text{ is a member of ALT that is innocently excludable given ALT and } \varphi\}$

## 2.2 Illustrations

### 2.2.1 An elementary case

Let us start with a very simple case where the two operators return the same result: the case where a sentence $\varphi$ has just one alternative, noted $\psi$, which it does not entail.

Let us first see what happens with $exh_{mw}$. We have $u < v$ just in case the set of propositions in $\{\varphi, \psi\}$ that are true in $u$ is a proper subset of the ones that are true in $v$. Now consider all the $\varphi$-worlds. They divide into two classes; worlds of type W1 where $\varphi$ is true and $\psi$ is false, and worlds of type W2 where both $\varphi$ and $\psi$ are true. Clearly, given two $\varphi$-worlds $u$ and $v$, $u < v$ if and only if $u$ is of type W1 and $v$ is of type W2. By definition, $exh_{mw}(\varphi)$ consists of the minimal $\varphi$-worlds relative to $<$, that is, of all the W1 worlds. That is, $exh_{mw}(\varphi) = \varphi \wedge \neg \psi$.

Next, let us see what we get with $exh_{ie}$. We look at all the maximal consistent sets that contain $\varphi$ and the negations of some alternatives. In this simple case, there is just one such set, namely $\{\varphi, \neg \psi\}$. Trivially, $\neg \psi$ thus belongs to every MC-set as defined above, and so $\psi$ is innocently excludable. As a result, we have $exh_{ie}(\varphi) = \varphi \wedge \neg \psi$ — that is, the two operators deliver the same results, unsurprisingly.

### 2.2.2 Disjunction without a conjunctive alternative

We now consider a sentence of the form A or B (with A and B logically independent), and assume that the alternatives for this sentence are just ALT = {A, B}. This is one case where the three operators, $exh_{krifka}$, $exh_{mw}$ and $exh_{ie}$ deliver different results. It is easy to see that $exh_{krifka}$ returns the
contradiction. And while $exh_{mw}$ returns the exclusive reading of *A* or *B*, $exh_{ie}$ turns out to be vacuous.

First let's compute $exh_{mw}(*A* \text{ or } *B*)$ relative to $ALT=\{A, B\}$. The worlds that make *A* or *B* true can be divided into three types: $W1$-worlds where *A* is true and *B* is false, $W2$-worlds where *A* is false and *B* is true, and $W3$-worlds where both *A* and *B* are true. Now, for any worlds $w1$, $w2$, $w3$ of type, respectively, $W1$, $W2$ and $W3$, we have $w1 < w3$, $w2 < w3$, and crucially neither $w1 < w2$ nor $w2 < w1$. So the minimal worlds in $A \lor B$ are the worlds of type $W1$ and $W2$. Therefore, $exh_{mw}(*A* \text{ or } *B*)$ is the union of $W1$-worlds and $W2$-worlds, namely the proposition equivalent to $(A \land \neg B) \lor (\neg A \land B)$ — that is, the exclusive reading.

Let us now compute $exh_{ie}(*A* \text{ or } *B*)$. There are two maximal consistent sets consisting of $A \lor B$ and negations of alternatives: $\{A \lor B, \neg B\}$ and $\{A \lor B, \neg A\}$. These sets are maximal because the set $\{A \lor B, \neg A, \neg B\}$ is not consistent. So there are two MC-sets, and their intersection is just $\{A \lor B\}$. It follows that no alternative is innocently excludable. As a result, nothing gets excluded, and we have $exh_{ie}(*A* \text{ or } *B*) = A \lor B$ (i.e., exhaustification is vacuous).

In fact, most theories of alternatives assume that the alternatives for *A* or *B* also include $A \land B$, in which case, as we discuss in the next section, both $exh_{mw}$ and $exh_{ie}$ return the exclusive reading. A more interesting case, as discussed in Fox 2007, is when a disjunction occurs in the scope of a possibility modal, which we represent with $\diamond(A \lor B)$. If only the disjunction contributes to alternatives and we compute alternatives based on Sauerland's procedure, the alternative set is $\{\diamond A, \diamond B, \diamond(A \lor B), \diamond(A \land B)\}$. Crucially, this set is not closed under conjunction, because none of its members is equivalent to $\diamond A \land \diamond B$. As discussed in Fox 2007, relative to this set of alternatives, $exh_{ie}$ returns the proposition $\diamond(A \lor B) \land \neg\diamond(A \land B)$ (which is compatible with $\diamond A \land \diamond B$), while $exh_{mw}$ returns $\diamond(A \lor B) \land \neg(\diamond A \land \diamond B)$, which is strictly stronger.

As mentioned in the introduction, one of the results proven in this paper (Result 6 above, more formally stated in Theorem 12 below) is that, in certain cases, applying $exh_{ie}$ relative to Sauerland's alternatives is equivalent to applying $exh_{mw}$ with respect to a more restricted set of alternatives. The case we have just discussed illustrates that this result has a limited scope, as it is simply not relevant to sentences where a disjunction occurs in the scope of some other operator. Note, however, that when a disjunction is embedded under a necessity modal, the resulting alternative set based on, say, Sauerland's procedure, happens to be closed under conjunction, and
so $exh_{mw}$ and $exh_{ie}$ are again equivalent, thanks to Result 3 above (stated as Theorem 9 below). This is so because, under Sauerland's procedure, the alternatives for $\Box(A \lor B)$ are $\{\Box(A \lor B), \Box A, \Box B, \Box(A \land B)\}$, and $\Box(A \land B)$ is equivalent to $\Box A \land \Box B$.

### 2.2.3 Disjunction with a conjunctive alternative

Now let us consider again a disjunctive sentence $A$ or $B$, but with an alternative set $ALT=\{A, B, A \land B\}$. It turns out that the relationship denoted by $<$ is in fact the same as before. In worlds of type $W1$ as defined above, there is just one true alternative, namely $A$. In worlds of type $W2$, $B$ is the only true alternative. And in worlds of type $W3$, all the alternatives are true. So as before, for any worlds $w1$, $w2$, $w3$ of type, respectively, $W1$, $W2$ and $W3$, we have $w1 < w3$, $w2 < w3$, and crucially neither $w1 < w2$ nor $w2 < w1$. So the result of applying $exh_{mw}$ is the same as before, namely it returns the exclusive construal of $A$ or $B$.

However, things change with $exh_{ie}$. Now the MC-sets all include one additional element, namely $
eg(A \land B)$. That is, we still have two MC-sets, but they now are $\{A \lor B, \neg A, \neg(A \land B)\}$ and $\{A \lor B, \neg B, \neg(A \land B)\}$. Since $
eg(A \land B)$ belongs to both, $A \land B$ is innocently excludable, and as a result $exh_{ie}(A \ or \ B) = (A \lor B) \land \neg(A \land B)$. So now both exhaustivity operators return the same results.

## 3 Results to be proven

### 3.1 Note about the notion of closure of a set of propositions under disjunction and/or conjunction

I view propositions as sets of worlds, and so, as noticed in section 2.1, when I talk about negation, conjunction, and disjunction, I mean to talk about the set-theoretic operations of complementation, intersection, and union. I can thus talk of the grand disjunction or grand conjunction of infinitely-many propositions. With this in mind, it is worth noticing that there are two possible notions of 'closure under disjunction/conjunction/disjunction and conjunction'. First there is a finitary notion, where the closure under, say, disjunction, of a set of propositions $E$ is the set of propositions that is obtained by applying disjunction recursively to two propositions. That is, we start with a set $E$, we then expand this set by adding all the disjunctions
of pairs of members of $E$, and we then do the same thing with the resulting
set, which yields a new set, *ad infinitum*. But I will use here a stronger notion
of closure, where, at each step, we add all the propositions that you get
by taking the disjunction of an arbitrary subset of propositions (including
infinite sets). This is necessary in order for some of the results I will report
to be fully general, that is, to hold even in cases where the alternative set is
infinite. Let me make this precise.

**Definition 5.** Closure of a set of propositions under conjunction and disjunction.

Let $E$ be a set of propositions. The closure of $E$ under disjunction and con-
junction, noted $E^{\vee\wedge}$, is defined recursively as follows:

1. First we posit $E_0 = E$.

2. Then we define $E_{n+1} = \{\varphi: \text{ there exists a subset } X \text{ of } E_n \text{ such that} \\ \qquad \varphi = \bigvee X \text{ or } \varphi = \bigwedge X\}.$

3. $E^{\vee\wedge} = \{\varphi: \text{ for some } i, \varphi \in E_i\}$.

The definition of the closure under disjunction alone of a set $E$, noted $E^{\vee}$ (resp. conjunction, noted $E^{\wedge}$), is straightforward. One just needs to replace the second clause with:

$E_{n+1} = \{\varphi: \text{ there exists a subset } X \text{ of } E_n \text{ such that } \varphi = \bigvee X \text{ (resp. } \varphi = \bigwedge X\}\}$.

Note that $E^{\vee\wedge}$ could as well be defined as the smallest set of propositions that contains $E$ and is closed under $\vee$ and $\wedge$, where a set $X$ is closed under $\vee$ (resp. $\wedge$) if, for any subset $Y$ of $X$, $\bigvee Y \in X$.

3.2 The relationship between the three operators $exh_{krifka}$, $exh_{mw}$ and $exh_{ie}$

**Proposition 1.** For any proposition $\varphi$ and any alternative set ALT:

if $exh_{\text{krifka}}(\text{ALT}, \varphi)$ is not the contradiction,
then $exh_{\text{krifka}}(\text{ALT}, \varphi) = exh_{\text{mw}}(\text{ALT}, \varphi) = exh_{\text{ie}}(\text{ALT}, \varphi)$.

**Corollary 2.** For any proposition $\varphi$ and any alternative set ALT:

$exh_{\text{krifka}}(\text{ALT}, \varphi)$ entails both $exh_{\text{mw}}(\text{ALT}, \varphi)$ and $exh_{\text{ie}}(\text{ALT}, \varphi)$.
### 3.3 Some facts about $exh_{mw}$

**Proposition 3.** For any proposition $\varphi$ and any alternative set ALT:

$$exh_{mw}(ALT, \varphi) = exh_{mw}(ALT^{\vee\wedge}, \varphi).$$

In other terms, closing ALT under disjunction and conjunction is vacuous for $exh_{mw}$.

**Corollary 4.** For every $\varphi$ and every ALT,

$$exh_{mw}(ALT^{\vee}, \varphi) = exh_{mw}(ALT^{\wedge}, \varphi) = exh_{mw}(ALT, \varphi).$$

That is, closure under disjunction alone, or conjunction alone, is vacuous for $exh_{mw}$.

**Corollary 5.** For any proposition $\varphi$ and two sets ALT$_1$ and ALT$_2$,

$$\text{if } ALT_1^{\vee\wedge} = ALT_2^{\vee\wedge} \text{ or } ALT_1^{\vee} = ALT_2^{\vee} \text{ or } ALT_1^{\wedge} = ALT_2^{\wedge}, \\ exh_{mw}(ALT_1, \varphi) = exh_{mw}(ALT_2, \varphi).$$

That is, if one can find a set whose closure under conjunction, or disjunction, or both, is the same as that of ALT, one can use this set instead of ALT with no change of output for $exh_{mw}$.

### 3.4 The relationship between $exh_{mw}$ and $exh_{ie}$

**Proposition 6.** For any proposition $\varphi$ with alternatives ALT: $exh_{mw}(ALT, \varphi)$ entails $exh_{ie}(ALT, \varphi)$.

**Proposition 7.** For any ALT, any $a \in ALT$, and any proposition $\varphi$, $a$ is innocently excludable given ALT and $\varphi$ if and only if $exh_{mw}(ALT, \varphi)$ entails $\neg a$.

**Corollary 8.** $exh_{ie}(ALT, \varphi) = \varphi \wedge \neg\{\neg a: a \in ALT \wedge exh_{mw}(ALT, \varphi) \subseteq \neg a\}$

### 3.5 Closure under conjunction of alternatives makes $exh_{mw}$ and $exh_{ie}$ equivalent

The most important result I will report is that two operators deliver the same result when the alternatives are closed under conjunction, where a set ALT
is said to be closed under conjunction if $ALT=ALT^\wedge$ (equivalently: if for any subset $X$ of $ALT$, $\wedge(X) \in ALT$).<fnref n="5" />

**Theorem 9.** For any $\varphi$ and any ALT, if $ALT$ is closed under conjunction, then

$$exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi).$$

## 3.6 Some consequences

While it is not generally true that closing alternatives under disjunction and conjunction is vacuous for $exh_{ie}$ (in contrast with $exh_{mw}$), a weaker result holds for $exh_{ie}$: closing the alternatives under disjunction (but crucially not conjunction) is vacuous for $exh_{ie}$.

**Theorem 10.** For any proposition $\varphi$ and any alternative set ALT,

$$exh_{ie}(ALT, \varphi) = exh_{ie}(ALT^\vee, \varphi).$$

From 9 and 10, the following result follows: if the closure of ALT under disjunction is closed under conjunction, applying $exh_{mw}$ and $exh_{ie}$ give rise to equivalent results.

**Corollary 11.** For any proposition $\varphi$ and any alternative set ALT:

$$\text{if } ALT^\vee = ALT^\vee \wedge, exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi).$$

## 3.7 Sauerland's alternatives

The final result is specifically relevant to Sauerland's (2004) procedure for generating alternatives. In general, the alternatives of a sentence, as defined by this procedure, are not closed under conjunction, and so Theorem 9 is not relevant. Nevertheless, for a significant subset of cases, Theorem 12 ensures that the result of applying $exh_{ie}$ relative to the full set of alternatives is the same as that of $exh_{mw}$ relative to a much smaller set of alternatives. Let us

<footnote n="5">⁵ In this case, there is no similar result if we restrict ourselves to a finitary notion of closure. Let us say that a set ALT is finitely closed under conjunction if for any finite subset $X$ of ALT, $\wedge(X)$ is in ALT. This is not sufficient in general to guarantee that $exh_{ie}(ALT, \varphi)=exh_{mw}(ALT, \varphi)$. Of course, when there are finitely-many alternatives (which is most often the case), this distinction is irrelevant since generalized closure under conjunction and finitary closure are equivalent.</footnote>
first define Sauerland's procedure for generating alternatives and then state
the result.

**Definition 6.** Sauerland's alternatives.<fnref n="6" />

Let *E* be a set of sentences that do not themselves contain alternative-inducing
expressions (we call such sentences *elementary* and treat them as atomic
sentences of a propositional language), and let *S* be a sentence obtained by
combining members of *E* with disjunction and conjunction.

The set of Sauerland-alternatives of S, noted ALT<sup>sauerland</sup>(S), is the set of sentences that can be obtained by all possible substitutions of occurrences of ∨ or ∧ in S with a member in {∨, L, R, ∧}, where L and R are the Boolean operators such that ‘x L y’ is equivalent to x and ‘x R y’ is equivalent to y.<fnref n="7" />

**Theorem 12.** Let *S* be a sentence obtained from a set of elementary sentences *E* by combining them with disjunction and conjunction.

Then $exh_{ie}(ALT^{sauerland}(S), S) = exh_{mw}(E, S).$

Importantly, the theorem is restricted to sentences where disjunctions and
conjunctions are not under the scope of some other operator, and which
contain no other alternative-inducing expression. However, there are cases
which are not covered by Theorem 12 but where it is nevertheless also the
case that the outcome of $exh_{ie}$ relative to the alternatives that result from
Sauerland's procedure is the same as that of $exh_{mw}$ with respect to a smaller
set of alternatives. I simply do not attempt here a full characterization
of the configurations in which this is the case, but one can use the other
results reported here to establish this equivalence on a case-by-case basis. For
instance, as already mentioned in 2.2.2, configurations in which a disjunction
is embedded under a necessity modal give rise to a set of alternatives that is
closed under conjunction, so that Theorem 9 is applicable.

<footnote n="6">⁶ Alternatives are now defined as *sentences* of a propositional language, rather than propositions. However, when I use a symbol standing for a set of alternatives as one of the arguments of *exh*<sub>*ie*</sub> or *exh*<sub>*mw*</sub>, this symbol is then meant to denote the set of propositions that the alternatives express.</footnote>

<footnote n="7">⁷ These substitutions do not have to be uniform: a given occurrence of ∨ can be replaced with, say, *L*, while some other occurrence of ∨ is replaced with, say, ∧, and of course a given occurrence can also be left unchanged, that is, ‘replaced’ with itself — so that any sentence is an alternative of itself.</footnote>
# 4 Practical relevance: some examples

In this section, I will often omit the ALT argument of $exh_{ie}$ and $exh_{mw}$.

## 4.1 Cases involving disjunction and conjunction

Consider again the case of a disjunctive sentence $S$ of the form *A or B or C*. If we follow Spector (2003, 2006), the alternatives for this sentence consist of the closure under disjunction and conjunction of {$A, B, C$}, that is, include 18 semantically distinct alternatives.<fnref n="8" /> If we apply Sauerland's 2004 scale for disjunction and conjunction, we have 16 syntactically distinct alternative, and 13 semantically distinct alternatives.<fnref n="9" /> In the first case, since the set of alternatives is closed under conjunction, we can conclude from Theorem 9 that applying $exh_{ie}$ is equivalent to applying $exh_{mw}$, and then from Proposition 3 that applying $exh_{mw}$ relative to the full set of alternatives, is equivalent to applying $exh_{mw}$ relative to just {$A, B, C$}.<fnref n="10" /> As a result of these two equivalences, we know that applying $exh_{ie}$ relative to the full set of alternatives is equivalent to applying $exh_{mw}$ relative to just three alternatives. The same result holds if we use Sauerland's scale, given Theorem 12.

It follows that to compute the result of $exh_{ie}$, it is sufficient to apply $exh_{mw}$ relative to alternatives {$A, B, C$}. One can straightforwardly see that the minimal worlds that make $S$ true are those in which only one member of {$A, B, C$} is true, i.e., that the exhausted meaning is equivalent to $(A \wedge (\neg B \wedge \neg C)) \vee (B \wedge (\neg A \wedge \neg C)) \vee (C \wedge (\neg A \wedge \neg B))$. In contrast with this, if one wants to directly compute the result of $exh_{ie}$, one has to consider all alternatives and construct all the MC-sets, on the basis of 16 or 18 alternatives, which is significantly more time- and ink-consuming.

<footnote n="8">⁸ As noted in Mascarenhas (2014), the closure under disjunction and conjunction of *n* independent propositions contains $D(n) - 2$ propositions, where $D(n)$ is the *n*th so-called *Dedekind's number* (Wikipedia 2016).</footnote>

<footnote n="9">⁹ If a sentence contains *n* connectives and no other alternative-inducing expression, the number of syntactically distinct alternatives on the basis of Sauerland's scale is $4^n$, where *n* is the number of connectives occurring in the sentence. Furthermore, if each atom occurs only once in such a sentence, the number of *semantically distinct alternatives* based on Sauerland's scale is equal to $\frac{3^{n+1}-1}{2}$ (see the Appendix for a proof).</footnote>

<footnote n="10">¹⁰ Importantly, the counterpart of Proposition 3 for $exh_{ie}$ is false, as we have already seen: for *A or B*, $exh_{ie}$ is vacuous relative to alternatives {$A \lor B, A, B$}, but not relative to {$A \lor B, A, B, A \land B$}. And in the case of *A or B or C*, relative to the alternative set {$A, B, C$}, $exh_{ie}$ is vacuous as well.</footnote>
Let me consider another example. Mascarenhas (2014) discusses sentences such as *Either Mary came, or both Peter and Sue did*, which I will schematize as $m \lor (p \land s)$. Mascarenhas adopts Katzir's (2007) theory of alternatives, and observes that if one applies something close to Sauerland's (2004) pragmatic procedure on the basis of these alternatives, the predicted pragmatically strengthened meaning is $(m \land \neg p \land \neg s) \lor (p \land s \land \neg m)$ — as already discussed in Spector 2003. Proving this result directly, though not difficult, is not completely straightforward either, because the alternative set is big and so there are complex logical relationships between the various alternatives and the sentence whose strengthened meaning is computed. And applying $exh_{ie}$ directly to such a sentence (instead of running the neo-Gricean procedure as formalized by Sauerland) is not straightforward either, because again the high number of alternatives, and their complex logical relationships, make the computation of innocent exclusion far from trivial. Now, if one uses Sauerland's alternatives, we know thanks to Theorem 12 that the result of $exh_{ie}$ will be the same as that of $exh_{mw}$ relative to just $\{m, p, s\}$. It is easy to see that the worlds that make the sentence true and at the same time minimize the set of true alternatives in $\{m, p, s\}$ are those in which only $m$ is true and those in which $p$ and $s$ are true and $m$ is false. So it is now straightforward to see that the strengthened meaning of the sentence is $(m \land \neg p \land \neg s) \lor (p \land s \land \neg m)$. A similar simplification is available on the basis of Katzir's theory of alternatives (which is the one adopted by Mascarenhas). Mascarenhas shows that the alternatives as defined by Katzir for the relevant sentence (henceforth the *Katzir-alternatives*, ALT$^{katzir}$) are all the members of the closure under disjunction and conjunction of $\{m, p, s\}$ except $(m \land p) \lor (p \land s) \lor (m \land s)$. But this missing alternative itself belongs to the closure of the Katzir-alternatives under disjunction. That is, we have: (ALT$^{katzir}$)$^\vee = \{m, p, s\}^{\vee\wedge}$. Now, by Theorem 10, applying $exh_{ie}$ relative to ALT$^{katzir}$ is the same as applying it relative to (ALT$^{katzir}$)$^\vee$, hence relative to $\{m, p, s\}^{\vee\wedge}$. By Theorem 9, applying $exh_{ie}$ relative to $\{m, p, s\}^{\vee\wedge}$ is the same as applying $exh_{mw}$ relative to $\{m, p, s\}^{\vee\wedge}$. By Proposition 3, this is in turn equivalent to applying $exh_{mw}$ relative to just $\{m, p, s\}$.

If we now consider a more complex sentence, such as, say, *Mary or Sue came, or both Peter and Jane did*, which we can schematize as $(m \lor s) \lor (p \land j)$, the number of syntactically distinct alternatives based on Sauerland's scale is 64, corresponding to 40 semantically distinct alternatives, and the computation of innocent exclusion becomes intractable unless one finds a
way of simplifying the problem.<fnref n="11" /> The results mentioned in this note provide
such a tool. Thanks to Theorem 12, we know that applying $exh_{ie}$ relative to
the full set of alternatives is equivalent to applying $exh_{mw}$ relative to just
$\{m, s, p, j\}$. Using $exh_{mw}$, it is easy to see that the result is ($m \wedge \neg s \wedge \neg p \wedge \neg j) \vee (s \wedge \neg m \wedge \neg p \wedge \neg j) \vee (p \wedge j \wedge \neg m \wedge \neg s)$.

For an even more complex sentence, based on five elementary disjuncts
or conjuncts, the number of syntactically distinct alternatives based on
Sauerland's scale becomes 256, corresponding to 121 semantically distinct
alternatives.<fnref n="12" /> But again, we can be sure that applying $exh_{ie}$ relative to the
full set of alternatives is equivalent to applying $exh_{mw}$ relative to just five
alternatives.<fnref n="13" />

Let us sum up these observations in a somewhat more abstract form.
In the cases we have just discussed, ALT contained a much smaller subset
ALT* such that $exh_{ie}(ALT, \varphi) = exh_{mw}(ALT*, \varphi)$. This is what allowed us to
compute the output of $exh_{ie}$ by considering only a small set of alternatives. It
is important to note that we did not generally have $exh_{ie}(ALT, \varphi) = exh_{ie}(ALT*, \varphi)$.
So, even if we adopt a theory based on $exh_{ie}$, it turns out that in a number
of cases the fastest way to compute the outcome of the operator is to use
$exh_{mw}$ as a shortcut, thanks to which the set of alternatives that need to be
considered can be drastically shrunk.

<footnote n="11">11 This is even more so if, following Spector 2003, we assume that the alternatives are the closure under disjunction and conjunction of {m, s, p, j}, which contains 166 semantically distinct members.</footnote>

<footnote n="12">12 On the view that alternatives are obtained by closing the set of atomic sentences occurring in the sentence under disjunction and conjunction, the number of alternatives is $D(5) - 2 = 7579$. With 6 propositions serving as disjuncts or conjuncts, the number of alternatives is truly enormous: $D(6) - 2 = 7828352$.</footnote>

<footnote>On the basis of Sauerland's alternatives, with 6 propositions serving as disjuncts or conjuncts (and occurring only once), there are 1024 syntactically distinct alternatives (4⁵, 5 being the number of connectives in the sentence), corresponding to 364 semantically distinct alternatives (3⁵+1-1/2). Yet again, whatever choice we make, we can work with just 6 alternatives.</footnote>

<footnote n="13">13 All this remains true if instead of using Sauerland's procedure for computing alternatives, we take as our set of alternatives the closure under disjunction and conjunction of the elementary propositions the relevant sentence is made of, as in Spector 2003. Given Theorem 9, we know that applying $exh_{ie}$ to the sentence relative to this set of alternatives (which is closed under conjunction) is equivalent to applying $exh_{mw}$, and then Proposition 3 tells us that we will get the same outcome by applying $exh_{mw}$ relative to a set of alternatives that contains only the elementary propositions.</footnote>
## 4.2 A case with infinitely-many alternatives

Irrespective of whether alternatives are closed under conjunction, it is always true that $exh_{mw}(\varphi)$ entails $exh_{ie}(\varphi)$. So, suppose we can show that $exh_{mw}(\varphi) = \varphi$. It then follows that $\varphi$ entails $exh_{ie}(\varphi)$. But since $exh_{ie}(\varphi)$ entails $\varphi$ (by definition), we get $exh_{ie}(\varphi) = \varphi$. In other words, if $exh_{mw}$ is vacuous, so is $exh_{ie}$. This can be useful when proving that $exh_{mw}$ is vacuous is easier than proving directly that $exh_{ie}$ is.

Now, in recent works about the semantics of expressions such as *at least* $n$, it is shown that the ‘ignorance inference’ triggered by a sentence such as *there are at least 1037 stars*, that is, the inference that the speaker is uncertain about the exact number of stars, follows if the alternatives for such a sentence are all the sentences of the form *there are at least n stars* and *there are exactly n stars* (Büring 2008, Schwarz 2013, 2016 — see also Spector 2006, which discusses a similar account for modified numerals of the form *more than n*, and Mayr 2011 for a related proposal).

One aspect of this type account is that the exhaustification of such a sentence relative to such alternatives is vacuous. This is not necessarily straightforward to prove with $exh_{ie}$—Schwarz’s (2013) proof takes about one page, and Mayr needs about two pages to work out the output of $exh_{ie}$ relative to a different set of alternatives. But note that, even if our official theory is based on $exh_{ie}$, it is sufficient to prove that $exh_{mw}(\varphi) = \varphi$, which turns out to be quite easy. One just needs to show that every world that makes $\varphi$ true is minimal relative to $<_{ALT}$. That is, for any two $\varphi$-worlds $u$ and $v$, we have neither $u <_{ALT} v$ nor $v <_{ALT} u$.

Let us schematize the set of alternatives as ALT = {$= n: n$ is an integer} $\cup$ {$\ge n: n$ is an integer}, where $= n$ stands for *there are exactly n stars* and $\ge n$ for *there are at least n stars*. Note that this set of alternatives is not closed under conjunction. This is so because $\wedge(\{\ge n: n \text{ is an integer}\})$ is the proposition stating that there are infinitely-many stars, which is not already included in ALT, and there is no reason not to consider worlds/models in which this proposition is true.<fnref n="14" /> So we don’t know in advance that $exh_{mw}$ and

<footnote n="14">¹⁴ If we assume that there is no world with infinitely-many stars, the set of alternatives becomes closed under conjunction *if one adds to it the contradictory proposition*. Now, adding the contradiction to a set of alternatives is always a vacuous move, for both $exh_{ie}$ and $exh_{mw}$. The contradiction is always trivially innocently excludable. Adding the contradiction has no effect either on $<_{ALT}$, since the contradiction is false in every world. Given Theorem 9, then, if we only consider worlds with finitely many stars, $exh_{ie}$ and $exh_{mw}$ deliver the same outcome for the sentence under discussion.</footnote>
$exh_{ie}$ are equivalent in this case. Now, every world making the sentence true is either a world in which there are exactly $n$ stars, for some $n \ge 1037$, or a world in which there are infinitely-many stars. Consider two worlds $u_n$ and $u_m$ in which, respectively, there are exactly $n$ stars and there are exactly $m$ stars, with $n \ne m$, $n \ge 1037$ and $m \ge 1037$. It is clear that we don't have $u_n < u_m$: the alternative = $n$ is true in $u_n$ but not in $u_m$. Symmetrically, it is not the case that $u_m < u_n$. Now let $w$ be a world in which there are infinitely-many stars. Again, neither $u_n < w$ nor $w < u_n$. The alternative = $n$ is true in $u_n$ but not in $w$. And the alternative $\ge$ $(n+1)$ is true in $w$ but not in $u_n$. Finally, for any two worlds $u$, $v$ such that either the number of stars is the same in both or there are infinitely-many stars in both, $u$ and $v$ make true exactly the same alternatives, and so we have neither $u < v$ nor $v < u$. So for any two worlds $u$, $v$ that make $\varphi$ true, we have neither $u < v$ nor $v < u$. Therefore all $\varphi$-worlds are minimal and $exh_{mw}(\varphi) = \varphi$, from which it follows that $exh_{ie}(\varphi) = \varphi$.

# 5 Proofs

## 5.1 The relationship between three operators $exh_{krifka}$, $exh_{mw}$ and $exh_{ie}$.

**Proposition 1.** For any proposition $\varphi$ and any alternative set ALT:

if $exh_{krifka}(ALT, \varphi)$ is not the contradiction,

$$ \text{then } exh_{krifka}(ALT, \varphi) = exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi). $$

*Proof.* Assume that $exh_{krifka}(ALT, \varphi)$ is not the contradiction.

1. Let us prove that $exh_{krifka}(ALT, \varphi)=exh_{ie}(ALT, \varphi)$. Since $exh_{krifka}(ALT, \varphi)$ is not the contradiction, the set $X = \{\varphi\} \cup \{\neg a: a \in ALT \wedge \varphi\}$ does not entail $a$ is consistent, that is, is (ALT, $\varphi$)-compatible. Furthermore, any (ALT, $\varphi$)-compatible set is a subset of $X$, and therefore $X$ is the only maximal (ALT, $\varphi$)-compatible set, and so we have $IE_{ALT,\varphi} = X$. We then have:

$$ exh_{ie}(ALT, \varphi) = \bigwedge IE_{ALT,\varphi} = \bigwedge X = exh_{krifka}(ALT, \varphi). $$

2. Let us now show that $exh_{krifka}(ALT, \varphi)=exh_{mw}(ALT, \varphi)$. For any world $u$, let us define $FA(u) = \{a: a \in ALT \wedge a(u) = 0\}$. Note that for any two $\varphi$-worlds $u$ and $v$, i) $u \le_{ALT} v$ if and only if $FA(v) \subseteq FA(u)$ and ii) $u <_{ALT} v$ if and only if $FA(v) \supsetneq FA(u)$. Now, since $exh_{krifka}(ALT, \varphi)$ is consistent, there are worlds $u$ that make
it true, and we have, for every such world $u$, $\mathrm{FA}(u) = \{a: a \in \mathrm{ALT} \wedge \varphi$ does not entail $a\}$. For any $\varphi$-world $v$, the members of $\mathrm{ALT}$ that $v$ makes false cannot be entailed by $\varphi$. In other words, for any $\varphi$-world $v$, $\mathrm{FA}(v) \subseteq \mathrm{FA}(u)$, i.e., $u \le v$. So $v$ can be a minimal $\varphi$-world relative to $<_{\mathrm{ALT}}$ if and only if it makes true the same alternatives as $u$ (so that we don't have $u <_{\mathrm{ALT}} v$), i.e., iff $\mathrm{exh}_{\mathrm{krifka}}(\mathrm{ALT}, \varphi)(v) = 1$. Therefore, $\mathrm{exh}_{\mathrm{krifka}}(\mathrm{ALT}, \varphi) = \mathrm{exh}_{\mathrm{mw}}(\mathrm{ALT}, \varphi)$. $\square$

**Corollary 2.** For any proposition $\varphi$ and any alternative set ALT:

$\mathrm{exh}_{\mathrm{krifka}}(\mathrm{ALT}, \varphi)$ entails both $\mathrm{exh}_{\mathrm{mw}}(\mathrm{ALT}, \varphi)$ and $\mathrm{exh}_{\mathrm{ie}}(\mathrm{ALT}, \varphi)$

*Proof.* If $\mathrm{exh}_{\mathrm{krifka}}(\mathrm{ALT}, \varphi)$ is contradictory, it entails every proposition, hence entails $\mathrm{exh}_{\mathrm{mw}}(\mathrm{ALT}, \varphi)$ and $\mathrm{exh}_{\mathrm{ie}}(\mathrm{ALT}, \varphi)$. If not, then by Proposition 1, $\mathrm{exh}_{\mathrm{krifka}}(\mathrm{ALT}, \varphi)$, $\mathrm{exh}_{\mathrm{mw}}(\mathrm{ALT}, \varphi)$ and $\mathrm{exh}_{\mathrm{ie}}(\mathrm{ALT}, \varphi)$ are equivalent. $\square$

## 5.2 Some facts about $\mathrm{exh}_{\mathrm{mw}}$

**Proposition 3.** For any proposition $\varphi$ and any alternative set ALT:

$$ \mathrm{exh}_{\mathrm{mw}}(\mathrm{ALT}, \varphi) = \mathrm{exh}_{\mathrm{mw}}(\mathrm{ALT}^{\vee\wedge}, \varphi). $$

In other terms, closing ALT under disjunction and conjunction is vacuous for $\mathrm{exh}_{\mathrm{mw}}$.

*Proof.* Given the definition of $\mathrm{exh}_{\mathrm{mw}}$, it is sufficient to show that the two strict preorders $<_{\mathrm{ALT}}$ and $<_{\mathrm{ALT}^{\vee\wedge}}$ are identical, i.e., that their corresponding non-strict preorders $\leq_{\mathrm{ALT}}$ and $\leq_{\mathrm{ALT}^{\vee\wedge}}$ are identical. The right-to-left direction is trivial: if $u \leq_{\mathrm{ALT}^{\vee\wedge}} v$, then since $\mathrm{ALT} \subseteq \mathrm{ALT}^{\vee\wedge}$, $u \leq_{\mathrm{ALT}} v$.

The left-to-right direction requires an inductive proof. Consider the following property $P$ of propositions, defined as follows:

$$ P(\varphi) \Leftrightarrow \text{ for any two worlds } u \text{ and } v \text{ such that } u \leq_{\mathrm{ALT}} v, \text{ if } \varphi(u) = 1, \\ \text{then } \varphi(v) = 1. $$

We will prove by induction that $P$ holds of every member of $\mathrm{ALT}^{\vee\wedge}$.

1. Base case: $P$ holds of every member of $\mathrm{ALT}$ by definition of $\leq_{\mathrm{ALT}}$.

2. Induction hypothesis: $P$ holds of every member of $\mathrm{ALT}_n$.

3. Inductive step: Let $\varphi$ be a member of $\mathrm{ALT}_{n+1}$. Then there exists $X \subseteq \mathrm{ALT}_n$ such that $\varphi = \bigvee X$ or $\varphi = \bigwedge X$. Suppose that $u \leq_{\mathrm{ALT}} v$ and
that $\varphi(u) = 1$. If $\varphi = \bigvee X$ with $X \subseteq \text{ALT}_n$ there is a member $x$ of $X$ such that $x(u) = 1$. Since P holds of $x$ (induction hypothesis), $x(v) = 1$, and therefore $(\bigvee X)(v) = 1$, i.e., $\varphi(v) = 1$. If $\varphi = \bigwedge X$ with $X \subseteq \text{ALT}_n$, every member $x$ in $X$ is such that $x(u) = 1$, and by the induction hypothesis every $x$ in $X$ is such that $x(v) = 1$. Therefore $(\bigwedge X)(v) = 1$, i.e., $\varphi(v) = 1$. So property P holds of $\varphi$.

4. Conclusion: for every $n$, P holds of every member of $\text{ALT}_n$.

5. Furthermore, any member of $\text{ALT}^{\vee\wedge}$ is a member of $\text{ALT}_i$, for some $i$, and therefore P holds of every member of $\text{ALT}^{\vee\wedge}$.

So, whenever $u \leq_{\text{ALT}} v$, every member of $\text{ALT}^{\vee\wedge}$ which is true in $u$ is true in $v$, i.e., $u \leq_{\text{ALT}^{\vee\wedge}} v$. That is, $u \leq_{\text{ALT}} v$ entails $u \leq_{\text{ALT}^{\vee\wedge}} v$. $\square$

**Corollary 4.** For every $\varphi$ and every ALT,

$$exh_{mw}(\text{ALT}^{\vee}, \varphi) = exh_{mw}(\text{ALT}^{\wedge}, \varphi) = exh_{mw}(\text{ALT}, \varphi).$$

(That is, closure under disjunction alone, or conjunction alone, is vacuous for $exh_{mw}$)

*Proof.* Straightforward from Proposition 3 and the fact that $\text{ALT}^{\vee\wedge} = \text{ALT}^{\vee\wedge}$ and $\text{ALT}^{\wedge\wedge} = \text{ALT}^{\wedge\wedge}$. $\square$

Corollary 5 follows straightforwardly from Proposition 3 and Corollary 4.

**Corollary 5.** For any proposition $\varphi$ and two sets $\text{ALT}_1$ and $\text{ALT}_2$,

$$\text{ALT}_1^{\vee\wedge} = \text{ALT}_2^{\vee\wedge} \text{ or } \text{ALT}_1^{\vee} = \text{ALT}_2^{\vee} \text{ or } \text{ALT}_1^{\wedge} = \text{ALT}_2^{\wedge}, \\ exh_{mw}(\text{ALT}_1, \varphi) = exh_{mw}(\text{ALT}_2, \varphi).$$

## 5.3 The relationship between $exh_{mw}$ and $exh_{ie}$

Despite the fact that the definitions of the two operators look very different, they are in fact closely related. The key point, expressed in Lemma 2, is that minimality in terms of $<_{\text{ALT}}$ is closely related to the notion of $\text{MC}_{\text{ALT},\varphi}$-set. First let me remind the reader of some standard terminological points.

## Definitions 7.

1. A world $u$ satisfies a set of propositions $X$ if and only if $u$ makes every member of $X$ true.
2. A proposition $\varphi$ is *consistent* with a set of propositions $X$ if and only if there is a world that satisfies $X \cup \{\varphi\}$.

3. A proposition $\varphi$ is *entailed* by a set of propositions $X$ if and only if every world that satisfies $X$ makes $\varphi$ true.

Before proving the core lemma (Lemma 2), we first prove the following lemma.

**Lemma 1.**

1. Definition.

Given a proposition $\varphi$, a world $u$ that $\varphi$ makes true, and a set of alternatives ALT, we define: $X_{ALT,\varphi}(u) = \{\varphi\} \cup \{\neg a: a \in ALT \wedge a(u) = 0\}$. In what follows, I will omit the subscripts ALT and $\varphi$ and will simply write $X(u)$.

2. Fact.

For any world $u$:

$u$ is a minimal $\varphi$-world relative to $<_{ALT} \Leftrightarrow X(u)$ is an $MC_{(ALT,\varphi)}$-set.

*Proof.* First, note the following equivalence.

For any two $\varphi$-worlds $u$ and $v$: $u <_{ALT} v \Leftrightarrow X(v) \not\subseteq X(u)$.

1. Left-to-right: $u$ is a minimal $\varphi$-world relative to $<_{ALT} \Rightarrow X(u)$ is an $MC_{(ALT,\varphi)}$-set.

Let $u$ be a minimal $\varphi$-world relative to $<_{ALT}$. $X(u)$ is consistent (it is satisfied by $u$) and is therefore (ALT, $\varphi$)-compatible. Suppose $X(u)$ were not a maximal (ALT, $\varphi$)-compatible set. Then there would be a member of ALT, call it $a$, such that a) $\neg a \notin X(u)$ and b) $X(u) \cup \{\neg a\}$ is consistent. So there would be a world $w$ satisfying $X(u) \cup \{\neg a\}$. This world $w$ would be a $\varphi$-world. Furthermore, since $X(w)$ includes $\varphi$ and all the negations of alternatives that $w$ makes false, we would have $X(u) \cup \{\neg a\} \subseteq X(w)$, hence $X(u) \not\subseteq X(w)$. Given the above equivalence, we would have $w <_{ALT} u$, which contradicts the assumption that $u$ is a minimal $\varphi$-world relative to $<_{ALT}$.

2. Right-to-left: $X(u)$ is an $MC_{(ALT,\varphi)}$-set $\Rightarrow u$ is a minimal $\varphi$-world relative to $<_{ALT}$.

Let $u$ be such that $X(u)$ is an $MC_{(ALT,\varphi)}$-set. Suppose $u$ were not
a minimal $\varphi$-world relative to $<_{ALT}$. Then for some $\varphi$-world $w$,
we would have $w <_{ALT} u$, i.e., given the above equivalence, $X(u) \not\subseteq
X(w)$. But since $X(w)$ is consistent ($w$ satisfies $X(w)$), $X(w)$ would
be (ALT, $\varphi$)-compatible and therefore $X(u)$ itself would not be a
maximal (ALT, $\varphi$)-compatible set, contrary to the assumption that
$X(u)$ is an $\mathrm{MC}_{(ALT,\varphi)}$-set.
$\square$

It is now straightforward to prove the following core lemma.

**Lemma 2.** For every proposition $\varphi$, every set of alternatives ALT, and every world $u$, $exh_{mw}(ALT, \varphi)(u) = 1$ if and only if there is an $\mathrm{MC}_{(ALT,\varphi)}$-set $X$ that $u$ satisfies.

Equivalently: $u$ is a minimal $\varphi$-world relative to $<_{ALT}$ if and only if there is an $\mathrm{MC}_{(ALT,\varphi)}$-set $X$ that $u$ satisfies.

Proof.

1. From left to right.

Let $u$ be a minimal $\varphi$-world relative to $<_{ALT}$. By Lemma 1, $X(u)$ is an $\mathrm{MC}_{(ALT,\varphi)}$-set $X$ that $u$ satisfies.

2. From right to left.

Let $u$ be a world that satisfies a certain $\mathrm{MC}_{(ALT,\varphi)}$-set $X$. By definition, $X(u)$ is the maximal $(ALT, \varphi)$-compatible set that $u$ satisfies. It follows that $X \subseteq X(u)$. But since $X$ is itself a maximal $(ALT, \varphi)$-compatible set, necessarily we have $X = X(u)$. So $X(u)$ is an $\mathrm{MC}_{(ALT,\varphi)}$-set, and so by Lemma 1, $u$ is a minimal $\varphi$-world relative to $<_{ALT}$.
$\square$

The core lemma can itself be reformulated as follows:

**Lemma 3.** For every proposition $\varphi$ and every set of alternatives ALT,

$$exh_{mw}(ALT, \varphi) = \{u: u \text{ satisfies at least one } \mathrm{MC}_{(ALT,\varphi)}\text{-set}\}.$$

Equivalently:

$$exh_{mw}(ALT, \varphi) = \bigvee \{\wedge X: X \text{ is an } \mathrm{MC}_{(ALT,\varphi)}\text{-set}\}$$

A number of facts straightforwardly follow, such as Propositions 6 and 7.

**Proposition 6.** For any proposition $\varphi$ with alternatives ALT: $exh_{mw}(\varphi)$ entails $exh_{ie}(ALT, \varphi)$.
*Proof.* Let $u$ be a world that makes $exh_{mw}(ALT, \varphi)$ true. By Lemma 3, $u$ satisfies some $MC_{(ALT,\varphi)}$-set, hence $u$ satisfies the intersection of all the $MC_{(ALT,\varphi)}$-sets, and therefore entails the negation of all innocently excludable alternatives. $\square$

**Proposition 7.** For any ALT, any $a \in ALT$, and any proposition $\varphi$, $a$ is innocently excludable given ALT and $\varphi$ if and only if $exh_{mw}(ALT, \varphi)$ entails $\neg a$..

*Proof.* Let ALT be a set of propositions, $a$ a member of ALT and $\varphi$ proposition.

1. Left to right. Assume $a$ is innocently excludable given ALT and $\varphi$. Then $\neg a$ belongs to every $MC_{(ALT,\varphi)}$-set (by definition). Given Lemma 2, every world $u$ that makes $exh_{mw}(ALT, \varphi)$ true satisfies one $MC_{(ALT,\varphi)}$-set, hence makes $\neg a$ true.

2. Right to left. Assume that $exh_{mw}(ALT, \varphi)$ entails $\neg a$. Given Lemma 3, $exh_{mw}(ALT, \varphi)$ is the set of worlds that satisfy at least one $MC_{(ALT,\varphi)}$-set. So for every $MC_{(ALT,\varphi)}$-set $X$, every world that satisfies $X$ belongs to $exh_{mw}(ALT, \varphi)$ and thus makes $\neg a$ true. But then $\neg a$ has to be consistent with every $MC_{(ALT,\varphi)}$-set. Since $MC_{(ALT,\varphi)}$-sets are maximal (ALT, $\varphi$)-compatible sets and $a$ belongs to ALT, $\neg a$ belongs to every $MC_{(ALT,\varphi)}$-set. So $\neg a \in \text{IE}_{(ALT,\varphi)}$. $\square$

**Corollary 8.** $exh_{ie}(ALT, \varphi) = \varphi \wedge \neg \{\neg a: a \in ALT \wedge exh_{mw}(ALT, \varphi) \subseteq \neg a\}$

Note that the reason why $exh_{mw}(ALT, \varphi)$ may be strictly stronger than $exh_{ie}(ALT, \varphi)$ is that $exh_{mw}(ALT, \varphi)$ sometimes does more than excluding some alternatives (while what $exh_{ie}$ does is enriching the proposition it applies to with the negation of some alternatives). Thus take $A \lor B$, relative to ALT=$\{A, B\}$. We have $exh_{ie}(ALT, A \lor B) = A \lor B$, but $exh_{mw}(ALT, A \lor B) = (A \lor B) \wedge \neg(A \land B)$. The point here is that even though $A \land B$ is not an alternative, it is ‘excluded’ when we apply $exh_{mw}$, but not when we apply $exh_{ie}$.

## 5.4 Closure under conjunction of alternatives makes $exh_{mw}$ and $exh_{ie}$ equivalent

The central result of this paper is the following. It relies on the Lemma 2.
**Theorem 9.** For any $\varphi$ and any ALT, if ALT is closed under conjunction, then

$$exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi).$$

*Proof.* Let ALT be a set of propositions closed under conjunction and $\varphi$ be a proposition. Since $exh_{mw}(ALT, \varphi)$ always entails $exh_{ie}(ALT, \varphi)$ (by Proposition 6), it is sufficient to prove the following:

$$exh_{ie}(ALT, \varphi) \text{ entails } exh_{mw}(ALT, \varphi)$$

Equivalently:

$$\text{For every world } u, \text{ if } exh_{mw}(ALT, \varphi) = 0, \text{ then } exh_{ie}(ALT, \varphi)(u) = 0.$$

Assume that for some world $u$, $exh_{mw}(\varphi)(u) = 0$. We need to prove: $exh_{ie}(\varphi)(u) = 0$. Now, either $\varphi(u) = 0$ or $\varphi(u) = 1$. If $\varphi(u) = 0$, it is trivial that we also have $exh_{ie}(ALT, \varphi)(u) = 0$. So we can restrict our attention to the case where $\varphi(u) = 1$.

Consider the set $A = \{a: a \in ALT \wedge a(u) = 1\}$. Since $exh_{mw}(\varphi)(u) = 0$, by Lemma 2, $u$ doesn't satisfy any $MC_{(ALT,\varphi)}$-set. Therefore, every $MC_{(ALT,\varphi)}$-set contains a member $m$ such that $m(u) = 0$, and since $\varphi(u) = 1$, $m$ is of the form $\neg a$, where $a \in ALT$ and $a(u) = 1$, i.e., $a \in A$. So every $MC_{(ALT,\varphi)}$-set has a member whose negation is in $A$. Consider now $\wedge A$, the grand conjunction of $A$. By definition, $(\wedge A)(u) = 1$. Furthermore, since every $MC_{(ALT,\varphi)}$-set contains a member which is a negation of a member of $A$, $\wedge A$ is necessarily false in every world that satisfies an $MC_{(ALT,\varphi)}$-set. That is $\neg (\wedge A)$ is true in every world that satisfies an $MC_{(ALT,\varphi)}$-set, hence is consistent with every $MC_{(ALT,\varphi)}$-set. Since $MC_{(ALT,\varphi)}$-sets are maximal $(ALT, \varphi)$-compatible sets and $\wedge A$ is an alternative (because ALT is closed under conjunction), $\neg (\wedge A)$ belongs to every $MC_{(ALT,\varphi)}$-set. So $\wedge A$ is innocently excludable. Since $(\wedge A)(u) = 1$, there is an innocently excludable alternative, namely $\wedge A$, which $u$ makes true, i.e., fails to exclude, and therefore $exh_{ie}(\varphi)$ is false in $u$.<fnref n="15" /> □

## 5.5 Some consequences

We can now prove a second interesting result: closure of alternatives under disjunction is vacuous even for $exh_{ie}$.

<footnote n="15">15 My original proof was very similar but slightly more complex, and it relied on the axiom of choice. Thanks to Emmanuel Chemla for suggesting a more simple version.</footnote>
**Theorem 10.** For any proposition $\varphi$ and any alternative set ALT,

$$exh_{ie}(ALT, \varphi) = exh_{ie}(ALT^{\vee}, \varphi).$$

*Proof.* We will say that a proposition $\varphi$ excludes a proposition $a$ if $\varphi$ entails $\neg a$.

1. $exh_{mw}(ALT^{\vee}, \varphi) = exh_{mw}(ALT, \varphi)$ (by Corollary 4).

2. Let $a$ be a member of $ALT^{\vee}$. Then $exh_{ie}(ALT^{\vee}, \varphi)$ excludes $a$ if and only if $exh_{mw}(ALT^{\vee}, \varphi)$ does (by Proposition 7).

3. From steps 1 and 2, it follows that $exh_{ie}(ALT^{\vee}, \varphi)$ excludes $a$ if and only if $exh_{mw}(ALT, \varphi)$ does.

4. Now either $a$ belongs to ALT, or $a$ does not. Let us assume that $a$ belongs to ALT. We know by Proposition 7 that $exh_{mw}(ALT, \varphi)$ excludes $a$ if and only if $exh_{ie}(ALT, \varphi)$ does. Given the point we have just made in step 3, it follows that $exh_{ie}(ALT^{\vee}, \varphi)$ excludes $a$ if and only if $exh_{ie}(ALT, \varphi)$ does.

5. So the only way in which $exh_{ie}(ALT^{\vee}, \varphi)$ could be distinct from $exh_{ie}(ALT, \varphi)$ is by excluding a member $a$ of $ALT^{\vee}$ that does not belong to ALT, and such that $\neg a$ is not already entailed by $exh_{ie}(ALT, \varphi)$.

6. Suppose $exh_{ie}(ALT^{\vee}, \varphi)$ excludes some proposition $a$ that is in $ALT^{\vee}$ but not in ALT. Note that $a$ is necessarily the disjunction of a subset of ALT. Call this subset $A$. Since $exh_{ie}(ALT^{\vee}, \varphi)$ entails $\neg a$, it entails the negation of every member of $A$, that is, excludes every member of $A$. Since every member of $A$ belongs to ALT, it follows from step 4 above that every member of $A$ is also excluded by $exh_{ie}(ALT, \varphi)$. Since the negations of all the members of $A$ jointly entail $\neg a$, it follows that $exh_{ie}(ALT, \varphi)$ entails $\neg a$. Therefore every member of $ALT^{\vee}$ that $exh_{ie}(ALT^{\vee}, \varphi)$ excludes is already excluded by $exh_{ie}(ALT, \varphi)$, even if this member is not a member of ALT.

7. Therefore, $exh_{ie}(ALT^{\vee}, \varphi)$ excludes a certain member of $ALT^{\vee}$ if and only if $exh_{ie}(ALT, \varphi)$ does, from which it follows that $exh_{ie}(ALT^{\vee}, \varphi) = exh_{ie}(ALT, \varphi)$. $\square$

The following corollary straightforwardly follows from from 9 and 10:
**Corollary 11.** For any proposition $\varphi$ and any alternative set ALT:

$$ \text{if } ALT^{\vee} = ALT^{\vee\wedge}, \ exh_{mw}(ALT, \varphi) = exh_{ie}(ALT, \varphi). $$

## 5.6 Sauerland's alternatives

Now, what remains to be proven is that if we use Sauerland's alternatives and apply $exh_{ie}$ to a sentence obtained by combining elementary propositions (i.e., propositions that do not themselves include alternative-inducing expressions) with disjunction and conjunction, the result is equivalent to what we get by applying $exh_{mw}$ with respect to an alternative set that contains just the elementary propositions (Theorem 12). If in such cases Sauerland's alternatives were closed under conjunction, this would directly follow from Theorem 9. But Sauerland's alternatives for such sentences are not in fact always closed under conjunction, an important observation that I owe to Bernhard Schwarz (p.c.).<fnref n="16" /> Consider for instance $m \wedge (p \vee s)$. Sentences equivalent, respectively, to $s$ and $m \vee p$, are alternatives by Sauerland's procedure, but no sentence equivalent to $s \wedge (m \vee p)$ is an alternative by Sauerland's procedure. The gist of the proof is the following: even though Sauerland's alternatives for such sentences are not closed under conjunction, their closure under disjunction is closed under conjunction. By Theorem 10, we know that closing the alternatives under disjunction is vacuous for $exh_{ie}$. And since the result of this is itself closed under disjunction and conjunction, we can use Theorem 9 and Proposition 3 to show that exhaustifying with $exh_{ie}$ is equivalent to exhaustifying with $exh_{mw}$ with respect to a much smaller set of alternatives.

Because Sauerland's alternatives are defined syntactically, I now talk about sentences of a propositional language, rather than about the propositions they express. But I also use a sentence name or a variable over sentences to stand for the proposition that the corresponding sentence expresses. When I write as if sentences were the arguments of $exh_{ie}$ or $exh_{mw}$ operators, I intend to refer to the propositions they express. Likewise, alternative sets can be viewed as sets of sentences, but when alternative sets are used as arguments of $exh_{ie}$ or $exh_{mw}$, they stand for the set of propositions that their members express. That is, I freely go back and forth between 'sentence'- talk

<footnote n="16">¹⁶ In a previous version of this paper, I had incorrectly stated that Sauerland's alternatives for sentences with unembedded disjunctions and conjunctions are generally closed under conjunction. Many thanks to Bernhard Schwarz for detecting this mistake.</footnote>
and 'proposition'- talk, and the context should make clear what is meant. Note that because alternative sets as constructed by Sauerland are finite, closure under disjunction/conjunction as defined above is equivalent to *finitary* closure under disjunction/conjunction.

**Fact 1.** Every sentence which belongs to the closure under disjunction and conjunction of a finite set $A$ of atomic sentences is equivalent to a sentence of the form $(p_1 \wedge p_2 \wedge \dots \wedge p_k) \vee (p_m \wedge \dots \wedge p_n) \vee \dots \vee (p_r \wedge \dots \wedge p_s)$, where all the $p_i$s belong to $A$ — let us call sentences of this form *positive disjunctive normal forms based on* $A$, positive DNFs for short.

*Proof*. A standard proof of the Disjunctive Normal Form theorem shows how any sentence of propositional logic can be turned into a disjunctive normal form (DNF) by repeated applications of De Morgan's laws and of the distributivity laws for disjunction and conjunction. If one applies this procedure to a formula in which disjunction and conjunction are the only occurring logical expressions, De Morgan's laws are not needed, and the end-result is a positive DNF. $\square$

**Fact 2.** Let $S$ be a sentence obtained from a set of atomic sentences $E$ by combining them with disjunction and conjunction. Then every conjunction of elements of $E$ (i.e., every formula of the form $e_1 \wedge \dots \wedge e_n$, with $\{e_1, \dots, e_n\} \subseteq E$) is equivalent to a sentence that belongs to $\text{ALT}^{\text{sauerland}}(S)$.

*Proof.* Let $S$ be a sentence obtained from a set of atomic sentences $E$ by combining them with disjunction and conjunction (where each member of $E$ occurs in $S$). Consider a sentence $C = e_1 \wedge \dots \wedge e_n$, with $\{e_1, \dots, e_n\} \subseteq E$. Starting from $S$, we can obtain a sentence equivalent to $C$ by replacing some connectives in $S$ with one of $\{L, R, \wedge\}$, in the following manner. For any subconstituent $\Sigma$ of $S$ of the form $x c A$, where $x$ is a member of $E$ that does not occur in $C$ and $c$ is $\vee$ or $\wedge$, we replace $c$ with the connective $R$. For any subconstituent of $\Sigma$ of the form $A c x$, where $x$ is a member of $E$ that does not occur in $C$ and $c$ is $\vee$ or $\wedge$, we replace $c$ with the connective $L$. Finally, we replace all other connectives in $S$ with $\wedge$. The resulting sentence $S'$ is equivalent to $C$, and belongs to $\text{ALT}^{\text{sauerland}}(S)$ by construction. $\square$

**Fact 3.** Let $S$ be a sentence obtained from a finite set of atomic sentences $E$ by combining them with disjunction and conjunction. Then $(\text{ALT}^{\text{sauerland}}(S))^\vee = E^{\vee\wedge}$.
That is, the closure under disjunction of ALT<sup>sauerland</sup>(S) is the closure under disjunction and conjunction of E.

*Proof.* Let S be a sentence obtained from a finite set of atomic sentences E by combining them with disjunction and conjunction. Let us call B the set of all formulae that can be obtained by combining some members E with conjunction. By Fact 2, $B \subseteq \text{ALT}^{\text{sauerland}}(S)$. Now, the closure of B under disjunction, $B^{\vee}$, contains all the propositions that can be expressed by a positive DNF based on E (i.e., a DNF with no negation whose atomic propositions are all in E). By Fact 1, we then know that every member of $E^{\vee\wedge}$ is equivalent to a member of $B^{\vee}$. Therefore, at the semantic level (i.e., identifying now our sets of sentences with the sets of the propositions they express), we have $E^{\vee\wedge} \subseteq B^{\vee}$, and since $B \subseteq \text{ALT}^{\text{sauerland}}(S)$, we also have $E^{\vee\wedge} \subseteq (\text{ALT}^{\text{sauerland}}(S))^{\vee}$. But obviously (still at the semantic level), $(\text{ALT}^{\text{sauerland}}(S))^{\vee} \subseteq E^{\vee\wedge}$. Therefore, $(\text{ALT}^{\text{sauerland}}(S))^{\vee} = E^{\vee\wedge}$. $\square$

We are now in a position to prove Theorem 12:

**Theorem 12.** Let S be a sentence obtained from a finite set of atomic sentences E by combining them with disjunction and conjunction.

Then $exh_{ie}(\text{ALT}^{\text{sauerland}}(S), S) = exh_{mw}(E, S)$.

*Proof.* Let S be a sentence obtained from a finite set of atomic sentences E by combining them with disjunction and conjunction.

1. By Theorem 10, we have:
   $exh_{ie}(\text{ALT}^{\text{sauerland}}(S), S) = exh_{ie}((\text{ALT}^{\text{sauerland}}(S))^{\vee}, S)$.
   By Fact 3, $(\text{ALT}^{\text{sauerland}}(S))^{\vee} = E^{\vee\wedge}$.
   Therefore, $exh_{ie}(\text{ALT}^{\text{sauerland}}(S), S) = exh_{ie}(E^{\vee\wedge}, S)$.

2. By Theorem 9, $exh_{ie}(E^{\vee\wedge}, S) = exh_{mw}(E^{\vee\wedge}, S)$, and therefore by step 1 just above, $exh_{ie}(\text{ALT}^{\text{sauerland}}(S), S) = exh_{mw}(E^{\vee\wedge}, S)$.

3. By Proposition 3, $exh_{mw}(E^{\vee\wedge}, S) = exh_{mw}(E, S)$, and therefore given step 2 just above, $exh_{ie}(\text{ALT}^{\text{sauerland}}(S), S) = exh_{mw}(E, S)$. $\square$

# 6 Conclusion

In this note, I have proven a number of results thanks to which the outcome of both $exh_{ie}$ and $exh_{mw}$ can be systematically compared. The results reported
here provide the means to reduce, in a number of cases, the set of alternatives
that need to be considered in order to compute the result of exhaustification,
sometimes in a dramatic way. At the very least, these results a) can help
us determine the kind of facts that can allow us to adjudicate between the
two types of exhaustivity operators, and b) are useful from a practical point
of view, since in many cases they allow us to use $exh_{mw}$ as a shortcut for
computing the outcome of $exh_{ie}$.

Now, as discussed in Mascarenhas 2014, the fact that under many theories
sets of alternatives can be huge even for relatively simple sentences raises
an issue of cognitive plausibility. It is tempting to speculate that the results
reported here may help alleviate this issue. The speculation would be that in
many cases, speakers compute exhaustivity effects by considering a small
number of alternatives and apply $exh_{mw}$, as a way to compute the effect of
$exh_{ie}$ relative to a larger set of alternatives. Needless to say, this can be no
more than speculation at this point. Whether or not these speculations are
on the right track, these results are useful in their own right, as they clarify
the logical relationships between two broadly used exhaustivity operators.

# Appendix: Counting the number of semantically distinct alternatives given Sauerland's definition of alternatives

**Fact:** Let $S$ be a sentence obtained by combining some atomic sentences with disjunction and conjunction. If $S$ contains $n$ connectives and if each atomic sentence occurs only once in $S$, then the number of semantically distinct alternatives given Sauerland's procedure is $\frac{3^{n+1}-1}{2}$.

*Proof.* In what follows, an ‘alternative of $S$’ is defined as a member of ALT<sup>sauerland</sup>($S$) (cf. Definition 6). Let us note $\alpha(S)$ the number of semantically distinct alternatives of $S$, that is, the number of propositions that are expressed by one or several alternatives.
The proof is by induction.

1. Base case: if $S$ contains no connective, the number of alternatives is just 1, which is equal to $\frac{3^{0+1}-1}{2}$.

2. Induction Hypothesis: suppose that for a certain $n$ the claim is true for every $k$ such that $k \le n$.

3. Let $S$ be a sentence containing $n + 1$ connectives and at most one occurrence of each atomic sentence. There exist $S_1$ and $S_2$ such that $S$
is $S_1 c S_2$ where $c = \lor$ or $c = \land$. Now, let us consider all the alternatives in which $c$ has been replaced with $L$ (and possibly some other replacements have been performed). Clearly, they are all equivalent to an alternative of $S_1$ (whatever replacement was done in $S_2$ has no semantic effect), and each alternative of $S_1$ is equivalent to one of them. So the number of semantically distinct alternatives they express is $\alpha(S_1)$. Likewise, the alternatives in which $c$ has been replaced with $R$ express exactly the same propositions as the alternatives of $S_2$, and therefore the number of semantically distinct alternatives they express is $\alpha(S_2)$. Finally, the alternatives in which $c$ has been kept as is or has been replaced by $\lor$ or $\land$ are all of the form $T_1 c T_2$, where $T_1$ is an alternative of $S_1$ and $T_2$ is an alternative of $S_2$. These alternatives are all semantically distinct since each atomic sentence in them occurs only once. The number of alternatives of this sort is $\alpha(S_1) \times \alpha(S_2) \times 2$. So we have $\alpha(S) = \alpha(S_1) + \alpha(S_2) + 2 \times \alpha(S_1) \times \alpha(S_2)$. Now let $k_1$ be the number of connectives in $S_1$, and let $k_2$ be the number of connectives in $S_2$. The number of connectives in $S$ is $k_1 + k_2 + 1$, i.e., we have $n + 1 = k_1 + k_2 + 1$, i.e., $n = k_1 + k_2$. We also have $k_1 \le n$ and $k_2 \le n$. Therefore, by the induction hypothesis, we know that $\alpha(S_1) = \frac{3^{k_1+1}-1}{2}$ and $\alpha(S_2) = \frac{3^{k_2+1}-1}{2}$. Therefore,

$$ 
\begin{aligned}
\alpha(S) &= \alpha(S_1) + \alpha(S_2) + 2\alpha(S_1)\alpha(S_2) \\
&= \frac{3^{k_1+1}-1}{2} + \frac{3^{k_2+1}-1}{2} + \frac{2(3^{k_1+1}-1)(3^{k_2+1}-1)}{4} \\
&= \frac{3^{k_1+1}-1+3^{k_2+1}-1+3^{k_1+k_2+2}-3^{k_1+1}-3^{k_2+1}+1}{2} \\
&= \frac{3^{k_1+k_2+2}-1}{2} \\
&= \frac{3^{(n+1)+1}-1}{2}
\end{aligned}
$$

The claim thus also holds not only for every $k \le n$ (induction hypothesis), but for $n + 1$ as well, i.e., for every $k \le n + 1$. $\square$

## References

Büring, Daniel. 2008. The least *at least* can do. In Charles B. Chang & Hannah J. Haynie (eds.), *West Coast Conference on Formal Linguistics (WCCFL) 26, 114-120*. Somerville, MA: Cascadilla Proceedings Project. http://www.lingref.com/cpp/wccfl/26/paper1662.pdf.

Chierchia, Gennaro. 2004. Scalar implicatures, polarity phenomena, and the syntax/pragmatics interface. In Adriana Belletti (ed.), *Structures and beyond, vol. 3, 39-103*. Oxford University Press.
Fox, Danny. 2007. Free choice and the theory of scalar implicatures. In Uli Sauerland & Penka Stateva (eds.), *Presupposition and implicature in compositional semantics*, 537–586. New York: Palgrave Macmillan. http://dx.doi.org/10.1057/9780230210752_4.

Groenendijk, Jeroen & Martin Stokhof. 1984. *Studies on the semantics of questions and the pragmatics of answers*. University of Amsterdam dis- sertation. http://hdl.handle.net/11245/1.392528.

Katzir, Roni. 2007. Structurally-defined alternatives. *Linguistics and Philosophy* 30(6). 669–690. http://dx.doi.org/10.1007/s10988-008-9029-y.

Krifka, Manfred. 1993. Focus and presupposition in dynamic interpretation. *Journal of Semantics* 10(4). 269–300. http://dx.doi.org/10.1093/jos/10.4.269.

Mascarenhas, Salvador. 2014. *Formal semantics and the psychology of reasoning*. NYU dissertation. http://semanticsarchive.net/Archive/TdiNTBhM/mascarenhas-2014-dissertation.pdf.

Mayr, Clemens. 2011. Implicatures of modified numerals. In Ivano Caponigro & Carlo Cecchetto (eds.), *From grammar to meaning: The spontaneous logicality of language*, chap. 6, 139–171. Cambridge University Press. http://dx.doi.org/10.1017/CBO9781139519328.009.

van Rooij, Robert & Katrin Schulz. 2004. Exhaustive interpretation of complex sentences. *Journal of Logic, Language and Information* 13(4). 491–519. http://dx.doi.org/10.1007/s10849-004-2118-6.

Sauerland, Uli. 2004. Scalar implicatures in complex sentences. *Linguistics and Philosophy* 27(3). 367–391. http://dx.doi.org/10.1023/b:ling.0000023378.71748.db.

Schulz, Katrin & Robert van Rooij. 2006. Pragmatic meaning and non-mono- tonic reasoning: The case of exhaustive interpretation. *Linguistics and Philosophy* 29. 205–250. http://dx.doi.org/10.1007/s10988-005-3760-4.

Schwarz, Bernhard. 2013. *At least* and quantity implicature: Choices and consequences. In *Amsterdam Colloquium*, vol. 19, 187–194. http://maloni.humanities.uva.nl/AC2013/AC_proceedings.pdf.

Schwarz, Bernhard. 2016. Consistency preservation in Quantity implicature: The case of *at least*. *Semantics and Pragmatics* 9(1). 1–47. http://dx.doi.org/10.3765/sp.9.1.

Spector, Benjamin. 2003. Scalar implicatures: Exhaustivity and Gricean reason- ing. In Balder ten Cate (ed.), *European Summer School in Logic, Language and Information (ESSLLI), student session*, vol. 8, 277–288. Revised version in Spector 2007. Vienna, Austria.
Spector, Benjamin. 2006. *Aspects de la pragmatique des opérateurs logiques*. Université Paris 7 dissertation. http://lumiere.ens.fr/~bspector/THESE\_SPECTOR/THESE\_SPECTOR\_AVEC\_ANNEXE2.pdf.

Spector, Benjamin. 2007. Scalar implicatures: Exhaustivity and Gricean reasoning. In Maria Aloni, Paul Dekker & Alastair Butler (eds.), *Questions in dynamic semantics*, vol. 17 (Current Research in the Semantics/Pragmatics Interface), 225-249. Brill. http://dx.doi.org/10.1163/9780080470993_011.

Szabolcsi, Anna. 1983. Focussing properties, or the trap of first order. *Theoretical Linguistics* 10(1-3). 125-146. http://dx.doi.org/10.1515/thli.1983.10.1-3.125.

Wikipedia. 2016. *Dedekind number* - Wikipedia, The Free Encyclopedia. Online; accessed 2016-12-15. https://en.wikipedia.org/wiki/Dedekind_number.

Benjamin Spector

École Normale Supérieure

Institut Jean Nicod

29 rue d'Ulm

75005 Paris, France

Pavillon Jardin

benjamin.spector@ens.fr