Stanford Encyclopedia of Philosophy
This is a file in the archives of the Stanford Encyclopedia of Philosophy.

Generalized Quantifiers

First published Mon Dec 5, 2005

Generalized quantifiers are now standard equipment in the toolboxes of both logicians and linguists. The purpose of this entry is to describe these tools: where they come from, how they work, and what they can be used to do. The description is by necessity sketchy, but more comprehensive surveys exist in the literature and will be referred to when needed. To fully appreciate the text below, one will need basic familiarity with elementary set theoretic terminology, and with the language of first-order logic.

1. Preliminaries

The term “generalized quantifier” reflects that these entities were introduced in logic as generalizations of the standard quantifiers of modern logic, ∀ and ∃.[1] In retrospect one may say that ∀ and ∃ have been found to be just two instances of a much more general concept of quantifier, making the term “generalized” superfluous. Today it is also common to use just “quantifier” for the general notion, but “generalized quantifier” is still frequent for historical reasons. This article reflects both uses, with a tendency to insert “generalized” in logical contexts, and drop it in linguistic contexts.

It is useful to distinguish quantifier expressions from what they signify or denote, the (generalized) quantifiers themselves. In logical languages, quantifier expressions are variable-binding operators. Thus, ∃ is the familiar operator such that in a formula ∃xφ, ∃x binds all free occurrences of x in φ. It signifies the quantifier ‘there exists’ — we'll see shortly exactly what this object is. Likewise, the symbol Q0 is often used as a variable-binding operator signifying ‘there exist infinitely many’.

In natural languages a variety of expressions have been seen as quantifier expressions, for example, each of the following English expressions: everything, nothing, three books, the ten professors, John, John and Mary, only John, firemen, every, at least five, most, all but ten, less than half of the, John's, some student's, no _ except Mary, more male than female, usually, never, each other.[2]

What, then, are generalized quantifiers? Before answering that question, a brief historical prelude is enlightening.

2. Aristotle

Aristotle not only invented logic but also introduced the study of quantification as a main part of the discipline. The syllogistics can be seen as a formal study of the meaning of the four basic quantifier expressions all, no, some, not all, and of their properties. For example, the validity, according to Aristotle, of the syllogism

all(A,B)
all(B,C)
some(A,C)

shows that he considered, in contrast with modern logical usage, all to have existential import, so that all A are B entails that A is not an empty term. Likewise, the validity of the syllogism

some(A,B)
all(B,C)
some(A,C)

expresses that some is monotone increasing (as we now put it) in the second argument. Each valid syllogism formalizes part of the meaning of these quantifier expressions, but Aristotle's study of their properties went beyond the syllogistics. He observed, for example, that some and no are convertible or, as we might now say, symmetric, since they satisfy the scheme

Q(A,B)
Q(B,A)

in contrast with all and not all. Further, he studied how various forms of negation combined with quantifier expressions in (what was later called) the square of opposition.[3] The circumstance that the syllogistic format in itself is too weak to express interesting pieces of reasoning, and that generations of philosophers nonetheless mechanically continued to present it as the essence of logic far into the 20th century, should not obscure the fact that Aristotle's logic is a decisive contribution to the study of quantification.

Especially interesting in the present context is the fact that these quantifier expressions take two arguments or terms, and thus can be seen as binary relations, both syntactically (as Aristotle no doubt saw them) and semantically: given that terms signify sets of individuals, the expression some can be taken to signify the relation of overlap, i.e., of having non-empty intersection, between two sets, and all signifies the inclusion relation. Note that these are not relations between individuals but between sets of individuals — second-order relations. Indeed, they are exactly the generalized quantifiers some and all, respectively (on a given universe).

This thread — that quantifier expressions signify second-order relations — was not picked up by any of Aristotle's medieval followers (as far as we know). Instead, they picked up on the fact that the two terms have different status: the first combines with the quantifier expression to form a noun phrase (as we now say), which is the subject of the sentence, whereas the second is a verb phrase constituting the predicate. This led them to focus on what the subject — all men, some dogs, no sailors — signified, which conceptually seems to be a harder question. One might surmise that all men signifies every man (or the set of men), and that some dogs signifies some particular dog, but what about no sailors? In fact, one can show that approaches like these are doomed to failure.[4] The modern solution is that noun phrases signify sets of sets of individuals, so that, for example some dogs signifies the set of sets containing at least one dog — but that appears to require a more abstract and mathematical approach to semantics than the idea, which is at least implicit in Aristotle, that quantifier phrases signify relations between (the denotations of) terms.

3. Frege

The second major historical contribution to the theory of generalized quantifiers came from the ‘inventor’ of modern logic, Gottlob Frege, in the 1870s. In fact, Frege's contribution is twofold. As every philosophy student knows, he introduced the language of predicate logic, with sentential connectives, identity, and the variable-binding operators ∀ and ∃ (in modern notation, not Frege's). These are the quantifiers that logicians during the 1950s began to ‘generalize’. But Frege also explicitly formulated the abstract notion of a quantifier as a second-order relation, or, as he called it, a second level concept (“Begriff zweiter Stufe”). He was well aware that the four Aristotelian quantifiers were prime examples, but he wanted to avoid the focus on subject-predicate form, which he (with much justification) saw as having been a major obstacle to the development of logic after Aristotle. It was therefore an important discovery that these quantifiers could all be defined in terms of ∀ and sentential operators (replacing all(A, B) by ∀x(A(x) → B(x)), some(A, B) by ¬∀x(A(x) → ¬B(x)), etc.).

In fact, the only difference between Frege's notion of a second-level concept and the modern notion of a generalized quantifier is that Frege did not have the idea of an interpretation or model, which we now (since the advent of model theory in the 1950s) see as a universe that the quantifiers range over, plus an assignment of suitable semantic objects to the non-logical symbols. Frege's symbols all had fixed meanings, and the only universe he considered was the totality of everything. But apart from this, one may well say that it was Frege who discovered generalized quantifiers. This aspect of Frege's logic, however, remained in the background for a long time, and model theorists in the 50s and 60s seem not to have been aware of it.

4. Generalizing the universal and existential quantifier

Modern predicate logic fixes the meaning of ∀ and ∃ with the respective clauses in the truth definition, which specifies inductively the conditions under which a formula φ(y1,…,yn) (with at most y1,…,yn free) is satisfied by corresponding elements b1,…,bn in a model M = (M, I) (where M is the universe and I the interpretation function assigning suitable extensions to non-logical symbols): M ⊨ φ(b1,…,bn). The clauses are

  1. M ⊨ ∀xψ(x, b1,…,bn) iff for each a ∈ M, M ⊨ ψ(a, b1,…, bn)
  2. M ⊨ ∃xψ(x, b1,…, bn) iff there is some a ∈ M s.t.
    M ⊨ ψ(a, b1,…, bn)

To introduce other quantifiers, one needs to appreciate what kind of expressions ∀ and ∃ are. Syntactically, they are operators binding one variable in one formula. To see how they work semantically it is useful to rewrite (1) and (2) slightly. First, every formula ψ(x) with one free variable denotes in a model M a subset of M; the set of individuals in M satisfying ψ(x). More generally, if ψ(x, y1,…,yn) = ψ(x,[y]) has at most the free variables shown and [b] = b1,…,bn are elements of M, let

ψ(x,[b])M, x = {a ∈ M : M ⊨ ψ(a,[b])}

be the extension of ψ(x,[y]) in M relative to b1,…, bn. Then we can reformulate (1) and (2) as follows:

  1. M ⊨ ∀xψ(x,[b]) iff ψ(x,[b])M,x = M
  2. M ⊨ ∃xψ(x,[b]) iff ψ(x,[b])M,x ≠ ∅

Thus, the conditions on the right hand side emerge as properties of the sets ψ(x,[b]). In fact, we can think of ∀ and ∃ as denoting these properties, i.e., the property of being identical to the universe, and of being non-empty, respectively. And now it is easy to think of other properties of sets that can also be treated as quantifiers, for example, the property of containing at least 5, or exactly 3, elements, or of being infinite.[5]

Note that these properties depend only on the universe M, not on the rest of the model. Extensionally, they are simply sets of subsets of M. This leads to the following definition. essentially from Mostowski (1957):

Definition: A generalized quantifier Q of type <1> is
  1. syntactically, a variable-binding operator such that whenever φ is a formula so is Qxφ, and Qx binds all free occurrences of x in φ;
  2. semantically, a mapping from arbitrary universes (non-empty sets) M to a set QM of subsets of M, which interprets formulas of the form Qxφ according to the clause
  3. M ⊨ Qxψ(x,[b]) iff ψ(x,[b])M,x ∈ QM

Here we use the same symbol for the quantifier expression and the mapping that it signifies or denotes. Thus, ∀ is now taken to denote the universal quantifier, also written ∀, which is the mapping given by

∀M = {M}

for all M. Similarly, ∃ denotes the mapping defined by

∃M = {A ⊆ M : A ≠ ∅ }

And here are some other generalized quantifiers:

  1. (∃≥ 5)M = {A ⊆ M : |A| ≥ 5} (|X| is the size or cardinality of X)
    (∃=3)M = {A ⊆ M : |A| = 3}
    (Q0)M = {A ⊆ M : A is infinite}
    (QR)M = {A ⊆ M : |A| > |M − A|} (the “Rescher quantifier”)
    (Qeven)M = {A ⊆ M : |A| is even}

We now have a precise notion of a generalized quantifier, of which ∀ and ∃ are instances, along with infinitely many others. Moreover, we see how to extend first-order logic FO to a logic FO(Q), by adding the clause (5) to the formation rules, and the clause (7) to the truth definition. Similarly, if we add more than one generalized quantifier: FO(Q1,…,Qn).

In such a logic one may be a able to say things that are not expressible in FO. For example, it is well-known that in FO the notion of finiteness cannot be expressed. Thus there is no way to say, of an ordering relation <, that each element has only finitely many predecessors, for instance. But this is just the sort of thing one can express in FO(Q0):

  1. ∀x ¬Q0y(y < x)

Likewise, one cannot say in FO that a (finite) set A contains exactly half of the elements of the universe M, but that is expressible in FO(QR):

  1. ¬QRx A(x) ∧ ¬QRx ¬A(x)

(The first conjunct says that |A| ≤ |M − A|, and the second that |M − A| ≤ |A|.)

5. Generalized quantifiers of arbitrary types

Further generalization is possible. First, we can let Q bind one variable in two or more formulas. Second, we can let it simultaneously bind two or more variables in (some of) these formulas. The typing of Q indicates this: Q is of type <n1,…,nk> (where each ni is a natural number ≥ 1) if it applies to k formulas, and binds ni variables in the ith formula. This explains why the quantifiers in the previous section were said to be of type <1>.

In the general case, one normally chooses distinct variables xi1,…, xini = [xi] for 1 ≤ i ≤ k, so that a formula beginning with Q has the form

  1. Q[x1],…,[xk] (φ1,…,φk)

where all free occurrences of xi1,…,xini in φi become bound. Now Q associates with each universe M a k-ary relation QM between relations over M, where the ith argument is an ni-ary relation between individuals. The corresponding clause in the truth definition becomes

  1. M ⊨ Q[x1],…,[xk] (ψ1([x1],[b]),…,ψk([xk],[b])) iff
    QM(ψ1([x1],[b])M,[x1],…,ψk([xk],[b] )M,[xk])

Here ψi([xi],[y]) is a formula with at most the free variables shown, [b] is a sequence of elements of M corresponding to [y], and ψi([xi],[b])M,[xi] is the extension of ψi([xi],[y]) in M relative to [b] , i.e., the set of ni-tuples [ai] such that M ⊨ ψi([ai],[b]).

This is the official concept of a generalized quantifier in this article. It was introduced by Lindström (1966), and these quantifiers are sometimes called “Lindström quantifiers”.[6] If we fix M to the universe containing ‘everything’, we essentially have Frege's notion of a second-level concept.[7]

Q is monadic if on each universe M it is a relation between subsets of M, i.e., if its type is <1,…,1>; otherwise it is polyadic. For example, the Aristotelian quantifiers mentioned earlier are of type <1,1>:

  1. allM(A, B) ⇔ A ⊆ B
    someM(A, B) ⇔ A ∩ B ≠ ∅
    noM(A, B) ⇔ A ∩ B = ∅
    not allM(A, B) ⇔ A ⊈ B [8]

Here are some more type <1,1> quantifiers:

  1. (at least five)M(A, B) ⇔ |A ∩ B| ≥ 5
    (exactly three)M(A, B) ⇔ |A ∩ B| = 3
    (infinitely many)M(A, B) ⇔ A ∩ B is infinite
    mostM(A, B) ⇔ |A ∩ B| > |A - B|[9]
    (an even number of)M(A, B) ⇔ |A ∩ B| is even
    MOM(A, B) ⇔ |A| > |B|
    IM(A, B) ⇔ |A| = |B| (the “Härtig quantifier”)

With monadic quantifiers it is convenient to use just one variable, and let Q bind that same variable in each of the formulas. Thus, to say that most As are not B, for example, one may write

most x(A(x),¬B(x))

in the corresponding logical language, rather than most x, y(A(x),¬B(y)).

Here are a few polyadic quantifiers:

15.  WM(R) ⇔ R is a well-ordering of M type <2>
(Q0n)M(R) ⇔
    there is an infinite A ⊆ M s.t. An ⊆ R		 type <n>
Resk(most)M(R, S) ⇔ |R ∩ S| > |R − S| type <k,k>
RECIPM(A, R) ⇔
    for all distinct a, b ∈ A there is n ≥ 1 and c0,…,cn
    s.t. c0 = a and cn = b and ciRci+1 for i < n		 type <1,2>

W and Q0n come from logic and set theory. Resk(most) is the resumption of most to k-tuples. Resumption can be applied to any quantifier (in the syntax, this means replacing each individual variable by a corresponding k-tuple of variables); it has logical uses but also, like RECIP, uses in the interpretation of certain sentences in natural languages; see Section 14 below.

6. Topic neutrality

Both Mostowski and Lindström had one additional condition in their definitions of generalized quantifiers: they should not distinguish isomorphic models. Informally, they are topic-neutral: the truth of a statement of the form φ = Qx, yz(A(x), R(y, z)), say, in a model M doesn't depend on the particular individuals M consists of. If the individuals of M are mapped in a one-one fashion onto the individuals of another universe M′, and if A and R are mapped accordingly, one obtains an isomorphic model M′. Isomorphism closure then says that M ⊨ φ iff M′ ⊨ φ .

More formally, if M = (M, I) and M′ = (M′, I′) are models for the same vocabulary V of non-logical symbols, f is an isomorphism from M to M′, iff

M and M′ are isomorphic, in symbols,

M ≅ M′

if there is an isomorphism from one to the other. Now if Q is a generalized quantifier of type <n1,…,nk>, Pi is an ni-ary predicate symbol for 1 ≤ i ≤ k, M = (M, I) is a model for the vocabulary {P1,…,Pk}, and Ri = I(Pi), we also write

M = (M, R1,…, Rk)

Then Q satisfies isomorphism closure, or just ISOM, if the following holds:

  1. If (M, R1,…,Rk) ≅ (M′, R′1,…,R′k), then
    QM(R1,…,Rk) ⇔ QM′(R′1,…, R′k).

One easily checks that all the generalized quantifiers exemplified so far are indeed ISOM. We did not include this requirement in the definition of generalized quantifiers however, since there are natural language quantifiers that do not satisfy it; see below. But logic is supposed to be topic-neutral, so ISOM is almost always imposed. Then two important things follow. First, as indicated above, sentences in logical languages do not distinguish isomorphic models. More precisely, we have the following

FACT
If L = FO(Q1,…,Qn), each Qi is ISOM, φ is an L-sentence, and M ≅ M′, then M ⊨ φ ⇔ M′ ⊨ φ.

Second, ISOM takes a particularly interesting form for monadic quantifiers. If M = (M, A1,…,Ak), where Ai ⊆ M for each i, then A1,…,Ak partition M into 2k pairwise disjoint subsets (some of which may be empty); let us call them the parts of M . We illustrate with k = 2 and M = (M, A, B):

Figure 1
Figure 1

Now it is not hard to see that only the sizes of the parts determine whether two models of this kind are isomorphic or not:

FACT
(M, A1,…,Ak) ≅ (M′, A′1,…,A′k) iff the cardinalities of the corresponding parts are the same.

This shows that monadic and ISOM generalized quantifiers indeed deal only with quantities, i.e., with sizes of sets rather than the sets themselves. The list (14) of type <1,1> generalized quantifiers clearly illustrates this, but also the Aristotelian quantifiers can be formulated in terms of cardinalities,

allM(A, B) ⇔ |A − B| = 0
someM(A, B) ⇔ |A ∩ B| > 0

etc., and similarly for the type <1> examples we gave.

7. Relativization

Every statement involving a generalized quantifier Q takes place within some universe M. Sometimes it is useful to be able to mirror this relativization to a universe inside M. This means defining a new quantifier with one extra set argument which says that Q behaves on the universe restricted to that argument exactly as it behaves on M. Thus, if Q is of type <n1,…,nk>, we define Qrel of type <1,n1,…,nk> as follows:

  1. (Qrel)M(A, R1,…,Rnk) ⇔def QA(R1restricted toA,…,Rnkrestricted toA)

where Ri ⊆ Mni and Rirestricted toA is the restriction of Ri to A, i.e., the set of ni-tuples in Ri ∩ Ani.

We have in fact already seen several examples of relativization: since one easily verifies (see the lists (8) and (14)) that

  1. all = ∀rel
    some = ∃rel
    at least five = (∃≥5)rel
    exactly three = (∃=3)rel
    infinitely many = (Q0)rel
    most = (QR)rel
    an even number of = (Qeven)rel

8. Expressive power

We described how generalized quantifiers can be added to FO, resulting in more expressive logics. A logic in this sense roughly consist of a set of sentences, a class of models, and a truth relation (or a satisfaction relation) between sentences and models. Such logics are often called model-theoretic logics, since they are defined semantically in terms of models and truth, rather than proof-theoretically in terms of a deductive system for deriving theorems.[10] Here we restrict attention to logics of the form FO(Q1, Q2,…), formed by adding generalized quantifiers to FO, where each quantifier comes with a formation rule and a semantic clause for the truth definition as described in Section 5 above.

There is an obvious way to compare the expressive power of model-theoretic logics. L2 is at least as expressive as L1, in symbols,

L1 ≤ L2

if every L1-sentence φ is logically equivalent to some L2-sentence ψ, i.e., φ and ψ are true in the same models. Also, L1 and L2 have the same expressive power, L1 ≡ L2, if L1 ≤ L2 and L2 ≤ L1, and L2 is stronger than L1, L1 < L2, if L1 ≤ L2 but L2 ≰ L1. Thus, L1 < L2 if everything that can be said in L1 can also be said in L2, but there is some L2-sentence which is not equivalent to any sentence in L1.

How does one establish facts about expressive power? It seems as if in order to show L1 ≤ L2 one has to go through all of the infinitely many sentences in L1 and for each one find an equivalent in L2. But in practice it suffices to show that the generalized quantifiers in L1 are definable in L2. If Q is of type <1, 2> , say, Q is definable in L2 if there is an L2-sentence ψ whose non-logical vocabulary consists exactly of one unary and one binary predicate symbol, such that for all models M = (M, A, R),

QM(A, R) ⇔ (M, A, R) ⊨ ψ

Similarly for other types. For example, the quantifier all is definable in FO, since the following holds:

allM(A, B) ⇔ (M, A, B) ⊨ ∀x(A(x) → B(x))

Likewise, QR is definable in FO(most), since

(QR)M(A) ⇔ (M, A, B) ⊨ most x(x = x, A(x))

(note that all our logics contain the logical apparatus of FO, so they are all extensions of FO). The latter is an instance of the following observation:

  1. For any generalized quantifier Q, Q is definable in FO(Qrel).

Such facts about definability can be easy or hard to establish,[11] but they suffice to establish positive facts about expressivity, since we have the readily verified

FACT
FO(Q1,…,Qn) ≤ L if and only if each Qi is definable in L.

On the other hand, to prove inexpressibility, i.e., that some sentence is not equivalent to any L-sentence, is harder. One way that sometimes works is to establish that L1 has some property that L2 lacks; then one might be able to conclude that L1 ≰ L2. Some properties that are typical of FO, but fail for most stronger logics, are:

For example, FO(Q0) does not have the compactness property.[12] This can be seen by looking at the set of sentences

Φ = {¬Q0x(x = x)} ∪ {θn : n = 1,2,…}

where θn is an FO-sentence saying that there are at least n elements in the universe. If you take any finite subset Φ′ of Φ , and M is a universe whose cardinality is the largest n such that θn belongs to Φ′, then all sentences in Φ′ are true in M. But no universe can make all sentences in Φ true. And this shows that Q0 is not definable in FO, i.e., that FO(Q0) ≰ FO, since otherwise we could replace Φ by an equivalent set of FO-sentences, but FO does have the compactness property, so that it impossible.

However, this way of proving inexpressibility only works for logics with properties like those above. Moreover, they only work if infinite universes are allowed, but interesting inexpressibility facts hold also for finite models, for example, the fact that QR and Qeven are not definable in FO, or that most = (QR)rel is not definable in FO(QR). Logicians have developed much more direct and efficient methods of showing undefinability results that work also for finite models.[13]

The above properties in fact characterize FO, in the sense that no proper extension of FO can have (certain combinations of) them. This is the content of a celebrated theorem about model-theoretic logics, Lindström's Theorem, a version of which is given below. For an accessible proof see, for example, Ebbinghaus, Flum, and Thomas (1994). We say that a logic L = FO(Q1,…,Qn) relativizes if the ‘converse’ of (19) holds for each Qi, i.e., if each (Qi)rel is definable in L.

THEOREM (Lindström)
If L is compact and has the Löwenheim property, then L ≡ FO. Also, provided L relativizes, if L is complete and has the Löwenheim property, or if L has both the Löwenheim and the Tarski properties, then L ≡ FO.

9. Generalized quantifiers and computation

In addition to the truth conditions associated with generalized quantifiers, one may study the computations required to establish the truth of a quantified statement in a model. Indeed, generalized quantifiers turn up in various places in the part of computer science that studies computational complexity. We sketch two examples.

Restrict attention to finite universes, assume ISOM throughout, and consider first type <1> quantifiers, or type <1,1> quantifiers that are relativizations (Section 7) of these; we'll see in Section 12 that these types are highly relevant in natural language contexts. Such quantifiers can be seen as binary relations between natural numbers: using the same symbol we have QM(A) ⇔ Q(|M - A|, |A|).[14] These relations can in turn be coded as sets of words, for example by letting a binary word w1… wm correspond to a model (M, A) where |M| = m, A ⊆ M, and a 1 means ‘belonging to A’, and 0 means ‘not belonging to A’. Thus |A| is the number of 1's; note that by ISOM, the order in the string doesn't matter. So Q is coded as a set WQ of such words (one for each m ≥ 1).[15] One may then ask what it takes to recognize that a word belongs to WQ. The abstract notion of an automaton can be used to give one kind of answer; automata are machines that accept or reject words, and they are classified according to the complexity of the operations they perform.[16]

A finite automaton has a finite number of states including one start state and at least one accepting state. It starts scanning a word at the leftmost symbol in the start state, and at each step it moves one symbol to the right and enters a (possibly) new state, according to a given transition function. If it can move along the whole word ending in an accepting state, the word is accepted. It accepts a set W of words if it accepts all the words in W but no others from the same alphabet. It is easy to construct a finite automaton accepting ∀ (or ∀rel = all), i.e., checking that w consists only of 1's: just remain in the start state = accepting state as long as 1's are encountered, but go to a rejecting state as soon as a 0 is scanned, and remain there whatever is encountered afterwards. A slightly more complex automaton accepts Qeven: again there are two states, a start state = the accepting state and a rejecting state, and this time remain in the same state when 0's are scanned, but go to the other state when a 1 is scanned. To end in the accepting state it is then necessary and sufficient that there be an even number of 1's. This machine essentially uses cycles of length 2, whereas the first example had only 1-cycles. Call an automaton of the latter kind acyclic. Van Benthem showed that the FO-definable quantifiers are exactly the ones accepted by finite automata that are acyclic and permutation closed.[17]

A slightly more complex automaton, the pushdown automaton, has rudimentary memory resources in the form a of stack of symbols that can be pushed or popped from the top, enabling it to keep track to some extent of what went on at earlier steps. Another result by van Benthem is that the type <1> quantifiers accepted by pushdown automata are precisely those for which the corresponding binary relation between numbers is definable (with first-order means) in additive arithmetic, i.e., in the model (N, +), where N = {0, 1, 2,…}. An example is QR (or its relativization most): we have QR(m, n) ⇔ m < n, and the right hand side is definable in (N, +) by ∃x(x ≠ 0 ∧ m + x = n).[18]

Thus, an algorithmic characterization is matched with a logical one. This has been one prominent direction in the study of algorithmic complexity. Consider now the most general abstract automaton or computational device, i.e., Turing machines. One (of many) interesting complexity classes is PTIME: A set W of words is PTIME if there is a polynomial p(x) (with natural number coefficients) and a Turing machine accepting W such that whenever w ∈ W has length n, the accepting computation takes at most p(n) steps. PTIME computations are ‘feasible’, in contrast with EXPTIME ones, where the number of steps required may grow exponentially. An early result by Immerman and Vardi is that the PTIME sets of (words coding) finite models are precisely those describable by single sentences in FO(LFP), which is FO logic with an added mechanism for forming least fixed-points.[19] However, now one needs to represent not just monadic models but arbitrary ones. For example, a binary relation on the universe {1,…,m} can be represented by a word w11 … w1m#…#wm1 … wmm, where the relation holds of (i, j) iff wij = 1. But this time the order does seem to matter, and in fact the Immerman and Vardi result just mentioned only holds for models with a given linear order and a binary predicate symbol standing for that order.

Logics like FO(LFP) can be recast as logics of the form FO(Q1, Q2,…). Here infinitely many quantifiers may be required, but in some cases a single one suffices. As to FO(LFP), it suffices to add all the resumptions (see the end of Section 5 above) of a single quantifier. More generally, let FO*(Q1, Q2,…) be like FO(Q1, Q2,…) but with mechanisms for making relativizations (Section 7) and for resuming each Qi to k-tuples for each k. Then there is a single quantifier Q such that FO(LFP) = FO*(Q).

So generalized quantifiers remain a simple and versatile way of adding expressive power to FO. One natural question was if the logical characterization of PTIME mentioned above could be improved using generalized quantifiers, in particular if one could remove the restriction to ordered structures in this way. The answer, however, turned out to be negative, since Hella proved that the PTIME computable properties of arbitrary finite structures cannot be characterized by adding a finite number of generalized quantifiers to FO, or even to FO(LFP). The question of whether PTIME can be characterized by a logic of the form FO*(Q) remains open, however (indeed, solving it would be a major breakthrough in complexity theory).

10. Generalized quantifiers and natural language

Around 1980 a number of linguists began to realize that generalized quantifiers of type <1> and <1,1> readily lend themselves to the interpretation of noun phrases (NP), which are ubiquitous syntactic units in many languages.[20] This is immediately clear if one looks at the structure of a typical English sentence whose subject is a quantified NP:


  1. most students smoke

The (subject) NP consists of a determiner and a noun (N). Both the noun and the verb phrase (VP) have sets as extensions, and so the determiner is naturally taken to denote a binary relation between sets, i.e., a type <1,1> quantifier. An utterance of (20) has a (discourse) universe in the background (say, the set of people at a particular university), but the meaning of most, every, at least five and similar expressions is not tied to particular universes. For example, the meaning of all in

    1. All cats like milk.
    2. All electrons have negative charge.
    3. All natural numbers have a successor.
    4. All twins like each other.
    5. All compact subsets of Hausdorff spaces are closed.

has nothing to do with cats or electrons or numbers or twins or Hausdorff spaces, nor with the discourse universes that may be associated with the above examples. It simply stands for the inclusion relation, regardless of what we happen to be talking about. Therefore, the generalized quantifier all, which with each universe M associates the inclusion relation over M, is eminently suitable to interpret all, and similarly for other determiners.

However, it is characteristic of sentences of the form (20) that the noun argument and the VP argument are not on a par. The noun combines with the determiner to form the NP, a separate constituent, and this constituent can also be taken to signify a generalized quantifier, this time of type <1> . Thus, at least five students denotes the set of subsets of the universe which contain at least five students. This quantifier results from freezing the first argument of the type <1,1> five to the set of students; we write this fivestudent. In general, if A is a fixed set and Q a type <1,1> quantifier, one may define the type <1> quantifier QA by

  1. (QA)M(B) ⇔def QM ∪ A(A, B)

for any M and any B ⊆ M. In a compositional semantics it is natural to take each constituent part of a sentence to have a separate signification or meaning, and the default significations of noun phrases are type <1> quantifiers.

This holds also for some NPs that lack determiners, such as proper names. While John is assigned some individual j by an interpretation, the NP John can be taken to denote the quantifier Ij, defined, for any M, by

(Ij)M = {B ⊆ M : j ∈ B}

This is in fact motivated, not only because the interpretation of NPs becomes more uniform, but also because John can combine with quantified NPs; cf.

  1. John and three professors came to the meeting.

Here it is convenient if John and three professors have the same semantic category. Note that generalized quantifiers have a clear Boolean structure; define (here in the type <1> case, but similarly for any other type)

(Q1 ∧ Q2)M(A) ⇔ (Q1)M(A) and (Q2)M(A)
(¬Q)M(A) ⇔ not QM(A)

Then we can take the complex determiner in (23) to denote Ij ∧ threeprofessor. Similarly, the complex NP in

  1. John and Mary came to the meeting.

signifies Ij ∧ Im.

The first argument (coming from the noun) of a type <1,1> determiner denotation is often called its restriction, and the second its scope. The difference in syntactic status between these two arguments turns out to have a clear semantic counterpart.

11. Conservativity

It was observed early on that type <1, 1> quantifiers denoted by determiners in natural languages have the following property:

  1. Conservativity (CONSERV):
    For all M and all A, B ⊆ M, QM(A, B) ⇔ QM(A, A ∩ B).

This can be seen from sentence pairs such as the following, where it is clear that the second sentence is just an awkward way of expressing the first:

    1. Most students smoke.
    2. Most students are students who smoke.

    1. At least five professors were absent.
    2. At least five professors were absent professors.

    1. More than one third of the graduate students are foreigners.
    2. More than one third of the graduate students are foreign graduate students.

CONSERV says that only the part of B which is common to A matters for the truth of QM(A, B). That is, the part B - A in Figure 1 doesn't matter. This appears to hold for all determiner denotations, but it fails for perfectly natural logical quantifiers, such as MO and I from the list (14) above. The reason is that it is characteristic of determiner denotations that the restriction argument restricts the domain of quantification to that argument.

12. Extension

Actually, the idea of domain restriction has one further ingredient. To restrict the domain of quantification to a subset A of M means not only that B - A is irrelevant but the whole part of M that lies outside A, and hence also the part M - (A ∪ B) in Figure 1. This in turn is an instance of a more general property, applicable to arbitrary generalized quantifiers:

  1. Extension (EXT):
    If Q is of type <n1,…,nk>, Ri ⊆ Mni for 1 ≤ i ≤ k, and M ⊆ M′, then
    QM(R1,…, Rk) ⇔ QM′(R1,…, Rk).

That is, nothing happens when the universe is extended, or shrunk, as long as the arguments are not changed. Now recall that for type <1> quantifiers we already provided a logical mechanism for restricting the quantification domain to a subuniverse, in terms of relativization (Section 7). We can now see (in (b) below) that the combination of CONSERV and EXT amounts to exactly the same thing:

FACT
  1. For any quantifier Q, Qrel satisfies EXT.
  2. A type <1, 1> quantifier is CONSERV and EXT if and only if it is the relativization of a type <1> quantifier.[21]

Again, all determiner denotations appear to satisfy EXT. At first sight, nothing in principle would seem to prevent a language from containing a determiner, say evso, which meant every on universes with less than 10 elements and some on larger universes. But not only is there in fact no such determiner in any language — there couldn't be, if the noun (restriction) argument of a determiner is to restrict the domain of quantification to the denotation of that noun.

A quantifier such as evso is intuitively not constant, in the sense that it doesn't mean the same, or is not interpreted by the same rule, on every universe. EXT can be seen as a strong requirement of constancy: the rule interpreting Q doesn't even mention the universe. Indeed, many quantifiers from language and logic are EXT. As we saw, all relativized quantifiers are EXT, and all the other quantifiers in the lists (13) – (15) as well, except W.[22] In fact, it seems that all quantifiers taking more than one argument that show up in natural language contexts are EXT. And many type <1> quantifiers are EXT too, for example, ∃, Ij, QA (see (22) above), and all in the list (8) except QR.

But ∀ and QR are not EXT. Yet one is inclined to say for them too that they mean the same on every universe, so it seems that EXT is a sufficient conditions for constancy, but not necessary. The case of ∀ is particularly interesting since one might argue that it interprets NPs like everything or every thing. The crux here is thing. If this expression is seen as a logical constant that always denotes the universe, then these NPs do denote ∀: for all M and all B ⊆ M,

(everything)M(B) ⇔ everyM(M, B) ⇔ M ⊆ B ⇔ M = B ⇔ ∀M(B)

When EXT holds, we can usually drop the subscript M and write, for example,

Q(A, B)

rather than QM(A, B). That is, a suitable universe can be presupposed but left in the background. We often follow this convention below when dealing with EXT quantifiers.

13. Determiners that are not ISOM

Consider

  1. John's books were stolen.
  2. Some student's books have not been returned.
  3. No professor except Mary came to the meeting.
  4. All beach goers except a few enthusiastic swimmers were fully clothed.
  5. More male than female students smoke.

The expressions John's, some student's, no _ except Mary, all _ except a few enthusiastic swimmers, more male than female are quite naturally seen as determiners: when combined with nouns they form phrases that behave like ordinary NPs. Also, the type <1,1> quantifiers they signify are CONSERV and EXT. For example, the sentences in the following pair are trivially equivalent:

    1. John's books were stolen.
    2. John's books are books that were stolen.

But in contrast with the previous examples, they are not ISOM, since they involve some fixed individual or property: if John's books were stolen, and the number of stolen books is the same as the number of red pencils (in some discourse universe), and the number of books that weren't stolen is the same as the number of pencils that aren't red, it does not follow that John's pencils are red, as ISOM would have it.

However, just as the non-ISOM quantifier threestudent results by freezing the restriction argument of the EXT quantifier three, the non-ISOM quantifiers above result by freezing arguments in more abstract relations, which are ISOM. We illustrate this with the possessive determiner John's.[23]

Given that John denotes an individual j, the determiner John's can be defined, for all M and all A, B ⊆ M, by[24]

  1. John'sM(A, B) ⇔ ∅ ≠ {x ∈ A : R0(j, x)} ⊆ B

Here R0 is some ‘possessor’ relation; it is well-known that this relation varies a lot with the circumstances — one could be talking about the books that John owns, or has written, or borrowed, or bought as a present to Mary, etc. Suppose R0 is ownership. Then (30) says that John owns at least one book, and that all of the books he owns were stolen. Now consider the more general ‘quantifier’ defined, for a ∈ M, R ⊆ M2, and A, B ⊆ M, by

PM(a, R, A, B) ⇔ ∅ ≠ {x ∈ A : R(a, x)} ⊆ B

We could say that this is a generalized quantifier of type <0,2,1,1>, letting 0 stand for individuals. P is ISOM (extending definition (16) in the obvious way to quantifiers of this type), and John's results by freezing the first two arguments to suitable values.

Similar constructions work for other cases of quantifier expressions in natural languages that denote non-ISOM quantifiers. For example, the determiner no _ except Mary denotes (given that Mary refers to m)

(no _ except Mary)M(A, B) ⇔ A ∩ B = {m}

That is, (32) says that Mary is a professor, that she came to the meeting, and that no other professor did. Again, a corresponding ISOM quantifier of type <0,1,1> is readily defined. In conclusion, ISOM remains a fundamental property in the semantics of quantifier expressions, and not only in logical languages.

Digression: ISOM, i.e., topic-neutrality, is standardly seen as a mark of logicality.[25] It is possible to distinguish this property from constancy, in the earlier mentioned sense of meaning the same over different universes. One might therefore consider ISOM + EXT as an attempt to capture the idea of a logical constant. This doesn't quite work since ISOM appears to be a necessary (but perhaps not sufficient) condition for logicality, and EXT a sufficient (but not necessary) condition of constancy. As noted, ∀ is not EXT (but perhaps one could live with that, since ∃ (and negation) is EXT so the usual logical constants are at least definable from ISOM + EXT ones). In any case, this combination of properties has an even more succinct formulation, which is just like ISOM except that one allows arbitrary injections of the universe. Suppose Q is of type <n1,…,nk> :

  1. Injection (INJ):
    If Ri ⊆ Mni for 1 ≤ i ≤ k, and f is an injection (a one-one function) from M into M′, then QM(R1,…,Rk) ⇔ QM′(f(R1),…,f(Rk))

(where f (Ri) = {(f(a1),…, f(ani)) : (a1,…,ani) ∈ Ri}). Then it is easy to verify the following

FACT
ISOM + EXT = INJ

There has been some discussion about whether quantifiers like most or two-thirds of the are logical constants. It is not clear that this is a well-defined question since the notion of a logical constant is notoriously hard to pin-point. But that these quantifiers satisfy INJ is certain. End of digression.

14. Other quantifier expressions in natural language

Generalized quantifiers of other types than <1> and <1,1> have also been used to account for natural language quantification. Without going into detail about the often complex issues of interpretation arising here, we illustrate with a few examples.[26]

  1. More women than men smoke.

If more women than men is an NP, which seems to be the case, then the determiner more _ than takes two restriction arguments and one scope argument, and thus denotes the type <1,1,1> generalized quantifier

more _ than(A, B, C) ⇔ |A ∩ C| > |B ∩ C|

Keenan and Moss (1984) provide a thorough account of similar constructions requiring monadic quantifiers with more than two arguments.[27] More _ than is ISOM and EXT. It is also conservative in an extended sense, for type <1,1,1> quantifiers Q where the first two arguments are restrictions:

  1. QM(A, B, C) ⇔ QM(A, B, (A ∪ B) ∩ C)

Next, consider

    1. People usually are grateful to firemen who rescue them.
    2. Men seldom make passes at girls who wear glasses. (Dorothy Parker)

Adverbs like usually, seldom, always, never can be taken to denote generalized quantifiers.[28] For example, Dogs never meow is roughly synonymous with No dogs meow. But for (40), it can be argued that there is a reading where the quantifier applies to pairs: among the pairs consisting of a person and a fireman who rescues that person, a majority are such that the person is grateful. This is just the resumption of most to pairs, that we defined in (15):

Res2(most)(R, S) ⇔ |R ∩ S| > |R − S|

So in (40a), R(a, b) iff a ∈ person and b ∈ fireman and a rescued b, and S(a, b) iff a is grateful to b. It can be shown that for many quantifiers, in particular most, Resn(Q) is not definable in FO(Q). In fact, Res2(most) is not definable from any finite number of monadic quantifiers, so it is an example of an irreducibly polyadic quantifier.[29]

On the other hand, sentences with nested ordinary NPs, such as

  1. Most films were reviewed by two critics.

can also be construed with a polyadic quantifier Q, this time of type <1,1,2>, whose truth conditions may be given by the following logical sentence,

Qx, y, zu(A(x), B(y), R(z, x)) ↔ most x(A(x), two y(B(y), R(x, y)))

but as this sentence shows, Q is definable from most and two.[30]

Next:

  1. Five Boston pitchers sat alongside each other.

This can have the truth conditions

∃ X ⊆ Boston pitcher[|X| = 5 & RECIP(X, sat alongside)]

where RECIP is the type <1,2> quantifier defined in (15). That is, there is a set of five Boston pitchers such that if you take any two of those, either they sit next to each other, or there is one pitcher, or two, or at most three (all in the chosen set), between them. This is just one of several polyadic quantifiers that occur in reciprocal sentences.[31]

Finally, consider the sentence

  1. Most boys in your class and most girls in my class have all dated each other.

This has been put forward as an example of branching quantification, which can be written in a two-dimensional logical format as


  1. most x A(x)

    most y B(y)    		 > R(x,y)

where the intended reading is that there is a subset X of A containing most of the elements of A, and a similarly large subset Y of B, such that each pair (a, b) where a ∈ X and b ∈ Y belongs to the relation R. More generally, we have a polyadic quantifier of type <1,1,2> defined for any Q1, Q2 of type <1,1> by

  1. Br(Q1, Q2)(A, B, R) ⇔
        ∃X ⊆ A ∃Y ⊆ B [Q1(A, X) & Q2(B, Y) & X×Y ⊆ R][32]

Quite plausibly, this gives a reading of (43). Note that x and y here are independent of each other. If one instead would use any one of the linear sentences

most x(A(x), most y(B(y), R(x, y)))
most y(B(y), most x(A(x), R(x, y)))

either y depends on x or vice versa. For example, it is not hard to see that the first of these sentences has the truth condition

∃X ⊆ A [most(A, X) &
    ∀a ∈ X ∃Y ⊆ B [most(B, Y) & Y ⊆ {b : R(a, b)}]]

which clearly shows that the sets Y depend on X, in contrast with the situation in (45). The point of the two-dimensional partially ordered structure in (44) is that this semantic independence is also reflected in the syntax.[33]

It can be shown that Br(most, most) is not expressible in FO(most) alone; indeed not with any finite number of monadic quantifiers.[34]

Many other constructions in natural languages can be taken to involve generalized quantifiers, but the above sentences at least indicate some of the relevant examples.

Bibliography

Other Internet Resources

[Please contact the author with suggestions.]

Related Entries

Aristotle, General Topics: logic | Frege, Gottlob | logic: classical | model theory | square of opposition