## Notes to Generalized Quantifiers

1. The use of “quantifier” (German “Quantor”, French “quantificateur”, etc.) to denote ∀ and ∃ became established in logic toward the end of the 1920s.

2.
As a rule of thumb we use a smaller sans-serif font for quantifier
expressions and italics for the signified quantifiers. In logical
languages, on the other hand, it is convenient to abuse notation
somewhat by using the same symbol for both the expression and the
quantifier, when no confusion results. We sometimes do the same for
predicate symbols, so that the letters *A*,
*B*,…, *R*,… stand for both the symbol and
the set or relation it denotes.

3.
See Parsons (2004) for an illuminating account of the Aristotelian
square of opposition and some modern misunderstandings about it.
Peters and Westerståhl (2006), ch. 1.1.1, has a quick comparison with the ‘modern square’, which differs from the Aristotelian one in that *all* doesn't have existential import but *not
all* does, and, more importantly, that the relations along this sides of the square are different. For a detailed account of these differences, and of squares of opposition generated by various generalized quantifiers, see Westerståhl (2011).

4. See Peters and Westerståhl (2006), ch. 1.4, for a proof that there does not exist a semantics assigning individuals or sets of individuals even to phrases of the two forms all A and some B in a systematic (compositional) way.

5. Some such properties were considered even in the early days of predicate logic, for example, the quantifier ∃! meaning ‘there exists exactly one.’

6. Rather than seeing generalized quantifiers as mappings from universes to second-order relations, Lindström took them to be classes of models of the corresponding type. This is a negligible difference, since we have

Q_{M}(R_{1},…,R_{k}) ⇔ (M,R_{1},…,R_{k}) ∈Q

(see section 6 for the notation on the right-hand side).

7. It is often held that the idea of a totality of everything has been shown to be incoherent by Russell's paradox. Indeed, the paradox proved Frege's original system to be inconsistent, and shows that there cannot be a set containing all sets. For a defense of the notion of ‘everything’, and an argument that this notion is not only coherent but in fact indispensable, see Williamson (2003).

8. These are the modern variants. Aristotle considered all with existential import, i.e.,

(all_{ei})_{M}(A,B) ⇔ ∅ ≠A⊆B

and similarly for not
all, which he took to be the negation of
*all*_{ei}.

9.
We are here interpreting most as ‘more than half of the’ (on
finite universes). Often, most rather seems to mean something like ‘a
large majority of the’. There is probably some vagueness
involved, as well as an ambiguity: the threshold may be
set at different values in different contexts. We are not dealing with
vagueness here, and we assume that a *fixed context assumption*
chooses a suitable meaning. By default, we thus set the
threshold to 1/2.

10. A main source for the mathematics of model-theoretic logics is Barwise and Feferman (1985).

11. Here is a fact which is non-trivial but still relatively easy to prove:

FO(MO) ≡FO(Q_{0},most)

See Peters and Westerståhl (2006), ch. 13.2, for proofs of this and similar facts.

12. Nor does it have the completeness property or the Tarski property, though it does have the Löwenheim property.

13. See Ebbinghaus and Flum (1995) for the mathematics, and Westerståhl (1989) or Peters and Westerståhl (2006), chs. 13-15, for surveys focused on linguistic applications.

14.
Or *Q*_{M}(*A*, *B*) ⇔
*Q*(|*A* - *B*|, |*A* ∩ *B*|)
in the relativized type <1,1> case.

15.
Similarly, an arbitrary monadic quantifier can be coded as a set of
*k*-letter words for suitable *k*.

16. See, for example, Hopcroft and Ullman (1979) for an introduction to automata theory.

17. See van Benthem (1987). ISOM entails that the automata here are permutation-closed, i.e., that if a binary word is accepted, so are all permutations of that word; only the number of 1's and 0's counts.

18.
Here 0 can be defined as the unique *y* in *N* such
that *y* + *y* = *y*. For more results in this area, see Mostowski (1998). Clark (2011a) gives an overview of the automata-theoretic perspective of quantifiers, with applications to learning theory.

19.
This is one way of providing for *recursive definitions* in the
logic. A simpler operator that one can add is the transitive closure
operator. If *R* is a binary relation, the *transitive closure*
of *R*, *TC*(*R*), is the smallest transitive
relation containing *R*. It can also be defined as follows
(cf. the definition of *RECIP* in the list (15)):

aTC(R)b⇔ ∃n≥ 1 ∃x_{0},…,x_{n}[x_{0}=a∧x_{n}=b∧x_{i}Rx_{i+1}fori<n]

Note the quantification over *n*: *TC*(*R*) is not
in general definable in *FO* from *R*. It can also be
defined recursively:

aTC(R)b⇔aRb∨ ∃x[aRx∧xTC(R)b]

To be able to do this inside our logic we can add formulas of the form
*TC*(*x*, *y*,φ)(*u*, *v*)
whenever φ is a formula, and the semantic rule that when
*a*, *b* ∈ *M*, ψ(*x*,
*y*,[*z*]) has the free variables shown, and
[*c*] corresponds to [*z*],

M⊨TC(x,y,ψ(x,y,[c]))(a,b) ⇔ (a,b) ∈TC(ψ(x,y,[c])^{M, x, y})

This gives us the logic *FO*(*TC*); the LFP operator
generalizes this to other forms of recursion. See Ebbinghaus and Flum
(1995) for details about the definitions, and for results about these
logics, including those mentioned in this and the next two paragraphs.

20. Barwise and Cooper (1981), Keenan and Stavi (1986), Higginbotham and May (1981). But the starting-point was Richard Montague's work in the late 1960's; notably his paper “The Proper Treatment of Quantification in Ordinary English” (Montague 1973), where noun phrases, including proper names, were treated as quantifiers. The papers in van Benthem (1986) provided further logical and linguistic development of these ideas. Surveys of the whole area are Westerståhl (1989), Keenan and Westerståhl (2011), and Peters and Westerståhl (2006).

21.
(a) is practically immediate, and for (b) it is easy to verify that
*Q*^{rel} always satisfies CONSERV
and EXT when
*Q* is of type <1>. In the other direction, any
CONSERV and EXT
*Q*′ has a type <1> ‘counterpart’
*Q* defined by *Q*_{M}(*B*) ⇔
*Q*′_{M}(*M*, *B*): then
(*Q*^{rel})_{M}(*A*, *B*) ⇔
*Q*_{A}(*A* ∩ *B*) (by definition of
*Q*^{rel}) ⇔
*Q*′_{A}(*A*, *A* ∩ *B*)
(by definition of *Q*′) ⇔
*Q*′_{M}(*A*, *A* ∩ *B*)
(by EXT) ⇔
*Q*′_{M}(*A*, *B*) (by CONSERV), so *Q*′ =
*Q*^{rel}.

22.
But there again it is often natural to consider the EXT quantifier *W*^{ rel}, where
(*W*^{ rel})_{M}(*A*, *R*)
says that *R* is a well-ordering of *A*.

23.
Indeed, the intersective quantifiers mentioned so far have the
stronger property of being *cardinal*; i.e. only the
cardinality of *A* ∩ *B* matters. An example of an
intersective but non-cardinal quantifier
is *no _ except Mary*, defined in the next
section.

24. See Keenan and Westerståhl (2011), sect. 19.2, for discussion.

25. For detailed discussion and further references, see Peters and Westerståhl (2006): ch. 6.3 for existential there sentences, and ch. 5 for much more on monotonicity, including the connection with polarity items.

26. For much more on this, and on the treatment of possessive and exceptive determiners in general, see Peters and Westerståhl (2006), chs. 7 and 8.

27. We disregard tense here for simplicity, as well as fact that the plural form indicates that John has more than one book.

28. See van Benthem (2002) for an informative overview of conditions like ISOM in the context of logicality. For recent contributions in this area, see Bonnay (2008) and Feferman (2010).

29. See Keenan and Westerståhl (2011) for more examples and discussion.

30.
(38) may also have a *proportional* reading, saying that the
proportion of smokers among women is greater than the proportion of
smokers among men, i.e.,

propmore _ than_{M}(A,B,C) ⇔ |A∩C| / |A| > |B∩C| / |B|

31. This observation was originally made by Lewis (1975).

32. The last mentioned result is proved by Luosto (2000); the proof is quite difficult. More general results on the undefinability of resumption can be found in Hella, Väänänen, and Westerståhl (1997). Some discussion of the linguistic aspects appears in Peters and Westerståhl (2002).

33.
This is one of the readings of (41); the other one is
*two y*(*B*(*y*), *most x*(*A*(*x*),
*R*(*x*, *y*))). These quantifiers can be
described as *iterations* of *most* and *two*;
Keenan and Westerståhl (2011) have a detailed account of this
operation as well as a survey of the properties of iterated
quantifiers.

34.
See Dalrymple et al. (1998) for an extended discussion. RECIP is not
definable in *FO*; indeed it is not definable using monadic
quantifiers at all (Peters and Westerståhl, 2006, ch. 15).

35.
*Br*(*Q*_{1}, *Q*_{2}) is EXT if *Q*_{1} and
*Q*_{2} are, so we assume this and drop the subscript
*M*.

36.
Branching or partially ordered quantifiers is another way of
generalizing (prefixes of) ∀ and ∃; it appeared in logic
with Henkin (1961), and Hintikka (1973) argued that partially ordered
prefixes with ∀ and ∃ occur essentially in English
too. The debate that followed Hintikka's proposal was re-analyzed by
Barwise (1978), who also suggested that (45) is a clearer example of
branching in English than Hintikka's original examples. Semantically,
branching quantifiers are already subsumed under our notion of a
generalized quantifier, since they can all be seen as polyadic
quantifiers, like *Br*(*Q*_{1},
*Q*_{2}), although the special syntax is then lost.

But it should also be noted that the construction in (45) only works
in certain cases, namely, when *Q*_{1} and
*Q*_{2} are *right monotone increasing*, i.e.,
*Q*_{i}(*A*, *B*) and *B*
⊆ *B*′ entails that
*Q*_{i}(*A*, *B*′), *i* = 1,
2. Note that then

Q_{i}(A,B) ⇔ ∃X[Q(A,X) &X⊆B]

and one sees that (45) is a generalization of this. There has been some discussion about if and how (45) can be reformulated for other quantifiers; apart from Barwise (1978), see Westerståhl (1987) and Sher (1997).

37. For a proof, see Hella, Väänänen, and Westerståhl (1997).

38.
The ubiquity of this property, also called *smoothness*, is
discussed in Peters and Westerståhl (2006), ch. 5.

39. Oddly enough, Barwise and Cooper's suggestions 25 years earlier are not mentioned in that paper.

40. More exactly, it is NP-complete. Further, Mostowski and Wojtyniak (2004) proved that the branching construction in Hintikka's famous villagers sentence is also NP-complete:

Some relative of each villager and some relative of each townsman hate each other.