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, and Peters and Westerståhl (2005) for a comparison with the ‘modern square’, which differs from the Aristotelian one in that all doesn't have existential import but not all does (for Aristotle and his medieval followers, the reverse held).
4. See Peters and Westerståhl (2005), 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
QM(R1,…, Rk) ⇔ (M, R1,…, Rk) ∈ 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 recent 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.,
(allei)M(A, B) ⇔ ∅ ≠ A ⊆ B
and similarly for not all, which he took to be the negation of allei.
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(Q0, most)
See Peters and Westerståhl (2005) 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 (2005) for surveys focused on linguistic applications.
14. Or QM(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. More results in this area are known; see Mostowski (1998) for a survey.
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 ∃x0,…, xn[x0 = axn = b
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
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],
MTC(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, 1974), 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 (1997), and Peters and Westerståhl (2005).
21. (a) is practically immediate, and for (b) it is easy to verify that Qrel 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 QM(B) ⇔ Q′M(M, B): then (Qrel)M(A, B) ⇔ QA(A ∩ B) (by definition of Qrel) ⇔ Q′A(A, A ∩ B) (by definition of Q′) ⇔ Q′M(A, A ∩ B) (by EXT) ⇔ Q′M(A, B) (by CONSERV), so Q′ = Qrel.
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. For much more on this, and on the treatment of possessive and exceptive determiners in general, see Peters and Westerståhl (2005).
24. We disregard tense here for simplicity, as well as fact that the plural form indicates that John has more than book.
25. See van Benthem (2002) for an informative overview of conditions like ISOM in the context of logicality.
26. See Keenan and Westerståhl (1997) for more examples and discussion.
27. (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 _ thanM(A,B,C) ⇔ |A ∩ C| / |A| > |B ∩ C| / |B|
28. This observation was originally made by Lewis (1975).
29. 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).
30. 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 (1997) have a detailed account of this operation as well as a survey of the properties of iterated quantifiers.
31. 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, 2005, ch. 15).
32. Br(Q1, Q2) is EXT if Q1 and Q2 are, so we assume this and drop the subscript M.
33. 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(Q1, Q2), 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 Q1 and Q2 are right monotone increasing, i.e., Qi(A, B) and B ⊆ B′ entails that Qi(A, B′), i = 1, 2. Note that then
Qi(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).
34. For a proof, see Hella, Väänänen, and Westerståhl (1997).