Quantifiers in Formal Logic
QUANTIFIERS IN FORMAL LOGIC
Familiarity with classical quantification theory is presupposed here. Some proposed amendments are considered, as are several additions.
Alternatives to Classical Quantification Theory
First-order logic can be reformulated so as to avoid quantifiers and variables. This is only partially done in modal logic, which avoids explicit quantification over possible states of the world in favor of operators □ and ♢. However, in principle all quantification is avoidable, if one is willing to admit enough operators and does not worry about their having ordinary-language readings. In practice, however, few have preferred this predicate-functor approach (see Quine 1960, Benthem 1977). Thus, even such dissidents as the intuitionists adopt the classical quantificational language, though the properties they ascribe to the quantifiers are nonclassical. (Thus, while classically ∀ and ¬¬∀ and ∀¬¬ are equivalent, intuitionistically the first is stronger than the second and the second stronger than the third.)
Classical logic allows terms formed from constants and function symbols, subject to the restriction that each term must denote some element of the domain over which the quantifiers range; but terms are eliminable using Bertrand Russell's theory of descriptions. On the classical Tarskian definition of truth in a model, truth of ∀x ϕ(x ) (respectively, ∃x ϕ(x )) is equivalent to the truth of ϕ(t ) for all (respectively, some) terms t only in special cases, as when each element of the domain is the denotation of some term of the language (which is never so if the domain is uncountable and the language countable). By contrast, the so-called substitutional quantifier ∏ (respectively, ∑) is defined by the condition that ∏x ϕ(x ) (respectively, ∑x ϕ(x )) always counts as true if and only if (iff) ϕ(t ) is true for all (respectively, some) terms t. There is no technical obstacle to introducing such operators, but whether there is any philosophical advantage to doing so is controversial. In particular, if one has in mind a specific domain, ∏ (respectively, ∑) will be intuitively equivalent to the ordinary language "for every (respectively, some) element of the domain" only in special cases (see Kripke 1976). Antithetical to substitutional quantification is so-called free logic, which drops the classical restriction that all terms must have denotations and gives up the classical inferences from ∀x ϕ(x ) to ϕ(t ) and from ϕ(t ) to ∀x ϕ(x ) (see Bencivenga 1983).
Extensions of Classical Quantification Theory
In contrast to the various anticlassical logics just mentioned, by far the largest body of work on quantifiers in formal logic concerns certain extraclassical logics, called model-theoretic logics. These accept classical logic and the Tarskian definition of truth in a model, but introduce additional kinds of quantifiers into the language, indicating their intended meaning by adding clauses for them to the Tarskian definition. There are several kinds (see Barwise and Feferman 1985).
cardinality quantifiers
Though there are nineteenth-century and even medieval antecedents, the modern theory of such quantifiers as "most" begins with Andrzej Mostowski (1957). Given a formula ϕ(x ) and a model with domain A, write ϕ[a ] to indicate that a ∈A satisfies ϕ(x ); also write card B for the cardinality of a set B. Then the truth conditions for the most studied Mostowski-style quantifiers are as shown in Table 1.
All these generalized quantifiers count as logical notions according to the definition of Alfred Tarski (1986) (which requires that any sentence involving a purportedly logical operator that is true in a model remains true if the model is replaced by an isomorphic one). Their theory has been worked out in some detail. For example, for first-order logic plus Q0 the Löwenheim-Skolem theorem holds but the compactness theorem fails, while for Q1 the opposite is the case.
plural quantifiers
So-called second-order and higher-order quantifiers are nowadays generally read as first-order quantifiers, but with a different domain from that of the first-order quantifiers. Thus, one writes "∃X (Xy & … )" but reads it as something like "There is a class X such that y is a member of X and …" or "There is a concept X such that y falls under X and …" and similarly
| Quantifier | Truth condition |
| Most X ϕ(X ) | card {a : ϕ[a ]} > card {a : ¬ϕ[a ]} |
| More X [ϕ(X ), ψ(X )] | card {a : ϕ[a ]} > card {a : ψ[a ]} |
| Q 0X ϕ(X ) | card {a : ϕ[a ]} infinite |
| Q 1X ϕ(X ) | card {a : ϕ[a ]} uncountable |
| H X ϕ(X ) | card {a : ϕ[a ]} = card A |
| R XY ϕ(X ) | for some infinite l ⊆ A, ψ[a, b ] for all distinct a, b ∈ l |
for the two-place "∃X (Xyz & … )" and the third-order "∃X (X Y & … )," with relation and class of classes in place of class.
George S. Boolos (1984) suggests a different reading, "There are some things, the x s, such that y is one of them." Such a reading is available only in the second-order, one-place case, but there it seems to offer a way of avoiding overt quantification over classes or concepts. But it is controversial whether such plural quantification is prior to such notions as that of class, or whether the use of the plural involves a covert "ontological commitment" to something like classes. Boolos argues against the reduction of plural to class quantification, on the grounds that "[t]here are some classes such that any class is one of them iff it is not a member of itself" is true, while "[t]here is a class of classes such that any class" is false.
game quantifiers
Any first-order sentence is equivalent to one in prenex form, with all quantifiers out front. Any first-order prenex is equivalent to an existential second-order sentence (quantifying over functions from and to the domain A of the first-order variables), called its Skolem form, as with this equivalent pair (where the alternation of quantifiers may go on for any finite number n of rounds):
(1) ∀x 1∃y 1∀x 2∃y 2 … ϕ(x 1, y 1, x 2, y 2, … )
(2) ∃f 1∃f 2 … ∀x 1∀x 2 … ϕ(x 1, f (x 1), x 2, f (x 1, x 2), … )
Leon Henkin (1961) observes that one can associate to (1) a game for two players: player A chooses some a 1 ∈ A, player E chooses some b 1 ∈ A, A chooses a 2, then E chooses b 2, … , and in the end E wins if ϕ[a 1, b 1, a 2, b 2, …], and A if not. A strategy for a player is a rule telling that player how to play on each move as a function of the opponent's previous moves. A winning strategy is one such that, if the player plays according to it, then the player will win, regardless of how the opponent plays. A strategy for E can be represented as a pair of functions, one giving E's first move as a function of A's first move, the other giving E's second move as a function of A's first two moves. Then, (2) asserts that there is a winning strategy for E.
The game interpretation is especially useful if one wants to consider infinitely long formulas. A sentence like (1) but with an infinite alternation of quantifiers can be thought of as describing an infinite game—one may imagine each move made twice as fast as the one before—and the assertion that there exists a winning strategy for E is expressible as an infinitely long second-order sentence like (2) with infinite blocks of existential second-order and universal first-order quantifiers. There is this difference, that for a finite game one or the other of the players must have a winning strategy, but not for infinite games except in special cases. One such special case is that where ϕ is a conjunction of formulas ϕ1, ϕ2, … , each involving only finitely many of the x 's and y 's. This game quantifier has a tractable theory in this case (see Moschovakis 1972).
branching quantifiers
Henkin (1961) also introduces branching quantifiers and suggests an interpretation in terms of an associated Skolem form, illustrated by the following pair:
(3)
(4) ∃f 1∃f 2ϕ(x 1, f (x 1), x 2, f 2(x 2))
Note the subtle difference between (4) and (2): In the latter, f 2 is a one-place function. The main result about Henkin quantifiers is the Enderton-Walkoe theorem, asserting that not only is every Henkin quantifier sentence equivalent to an existential second-order sentence but also the converse holds. This means that known results about the logic of existential second-order sentences immediately apply to the logic of Henkin quantifier sentences: the Löwenheim-Skolem theorem, the compactness theorem, the definability of truth for sentences of this class by a sentence of the class, and more.
Jaako Hintikka (1996) introduces a nonbranching notation, in which (3) would be written as follows:
(5) ∀x 1∃y 1∀x 2∃y 2/x 1ϕ(x 1, y 1, x 2, y 2)
The "/x 1" is read "independent of x 1." Hintikka, long an advocate of a game interpretation of first-order quantification, also suggests a game interpretation of the new quantifiers, in terms of a game of imperfect information, in which at the time of E's second move, E has available only information about A's second move, not about A's first move—which is most easily imagined if one thinks of E as a team, with different members making different moves and having available different information when doing so. Hintikka calls the logic with these quantifiers independence-friendly (or information-friendly) logic and makes strong and controversial claims about the philosophical significance of theorems about existential second-order sentences when restated for "IF" logic (see Hintikka 1996; compare Tennant 1998; see also Hodges 1997; Burgess 2003).
Which quantifiers considered by logicians have natural-natural language counterparts, and how close those counterparts are, is a much discussed question that cannot be addressed in this entry.
See also Artificial and Natural Languages; First-Order Logic; Intuitionism and Intuitionistic Logic; Quantifiers in Natural Language; Types, Theory of.
Bibliography
Barwise, K. Jon, and Solomon Feferman, eds. Model-Theoretic Logics. Berlin, Germany: Springer-Verlag, 1985.
Bencivenga, Ermanno. "Free Logics." In Handbook of Philosophical Logic. Vol. 3, Alternatives to Classical Logic, edited by Dov M. Gabbay and F. Guenther, 73–426. Dordrecht, Netherlands: D. Reidel, 1983.
Benthem, J. F. A. K. van. "Tense Logic and Standard Logic." Logique et Analyse 80 (1977): 41–83.
Boolos, George S. "To Be Is to Be the Value of a Variable (or to Be Some Values of Some Variables)." Journal of Philosophy 81 (1984): 430–439.
Burgess, John P. "A Remark on Henkin Sentences and Their Contraries." Notre Dame Journal of Formal Logic 44 (2003): 185–188.
Enderton, H. B. "Finite Partially-Ordered Quantifiers." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 16 (1970): 393–397.
Henkin, Leon. "Some Remarks on Infinitely Long Formulas." In Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959, 167–183. Oxford, U.K.: Pergamon, 1961.
Hintikka, Jaako. The Principles of Mathematics Revisited. New York: Cambridge University Press, 1996.
Hodges, Wilfrid. "Compositional Semantics for a Language of Imperfect Information." Logic Journal of the IGPL 5 (1997): 539–563.
Kripke, Saul A. "Is There a Problem about Substitutional Quantification?" In Essays in Semantics, edited by Garteth Evans and John McDowell, 324–419. New York: Oxford University Press, 1976.
Moschovakis, Yannis. "The Game Quantifier." Proceedings of the American Mathematical Society 31 (1972): 245–250.
Mostowski, Andrzej. "On a Generalization of Quantifiers." Fundamenta Mathematicæ 44 (1957): 12–36.
Quine, W. V. O. "Variables Explained Away." Proceedings of the American Philosophical Society 104 (1960): 343–347.
Tarski, Alfred. "What Are Logical Notions?" History and Philosophy of Logic 7 (1986): 143–154.
Tennant, Neil. Review of The Principles of Mathematics Revisited, by Jaako Hintikka. Philosophia Mathematica 6 (1998): 90–115.
Walkoe, W. J. "Finite Partially Ordered Quantification." Journal of Symbolic Logic 35 (1970): 535–550.
John P. Burgess (2005)