Quantification
In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. A language element which generates a quantification is called a quantifier. The resulting statement is a quantified statement, and we say we have quantified over the predicate. Quantification is used in both natural languages and formal languages. In natural language, examples of quantifiers are for all, for some; many, few, a lot are also quantifiers. In formal languages, quantification is a formula constructor that produces new formulas from old ones. The semantics of the language specifies how the constructor is interpreted as an extent of validity. Quantification is an example of a variable-binding operation.The two fundamental kinds of quantification in predicate logic are universal quantification and existential quantification. These concepts are covered in detail in their individual articles; here we discuss features of quantification that apply in both cases. Other kinds of quantification include uniqueness quantification.
Need for quantification in natural language
Quantification is an essential part of natural language:
- Every glass in my recent order was chipped.
- Some of the people standing across the river have white armbands.
- Most of the people I talked to didn't have a clue who the candidates were.
- Everyone in the waiting room had at least one complaint against Dr. Ballyhoo.
- There was somebody in his class that was able to correctly answer every one of the questions I submitted.
- A lot of people are idiots.
- There were a shitload of problems with that new software we bought.
The study of quantification in natural languages is much more difficult than the corresponding problem for formal languages. This is in part due to the fact that the grammatical structure of natural language sentences may conceal the logical structure. Moreover, the specification of the range of validity for formal language quantifiers is essentially a mathematical problem; for natural language, specifying the range of validity requires dealing with non-trivial semantic problems.
Richard Montague's Montague grammars made significant contributions to the formal semantics of quantifiers in natural language.
Need for quantifiers in mathematical assertions
This has the appearance of an infinite conjunction of propositions. From the point of view of formal languages this is immediately a problem, since we expect syntax rules to generate finite objects. Putting aside this objection, also note that in this example we were lucky in that there is a procedure to generate all the conjuncts. However, if we wanted to assert something about every irrational number, we would have no way enumerating all the conjuncts since irrationals cannot be enumerated. A succinct formulation which avoids these problems uses universal quantification:- For any natural number n, n÷2 = n + n.
- 1 is prime, or 2 is prime, or 3 is prime, etc.
- For some natural number n, n is prime.
Nesting of quantifiers
Consider the following statement, often referred to as Bertrand's postulate:
- For any natural number n, there is a prime number p such that n < p ≤ 2 n.
- There is a prime number p such that for any natural number n, n < p ≤ 2 n.
This illustrates a fundamentally important point when quantifiers are nested: The order of alternation of quantifiers is of absolute importance.
Range of quantification
Every quantification involves one specific variable and a domain of discourse or range of quantification of that variable. The range of quantification specifies the set of values that variable takes. In the examples above, the range of quantification is the set of natural numbers. Specification of the range of quantification allows us to express the difference between, asserting that a predicate holds for some natural number or for some real number. Expository conventions often reserve some variable names such as "n" for natural numbers and "x" for real numbers, although relying exclusively on naming conventions cannot work in general since ranges of variables can change in the course of a mathematical argument.
A more natural way to restrict the domain of discourse uses guarded quantification. For example, the guarded quantification
- For some natural number n, n is even and n is prime
- For some even number n, n is prime.
- For any natural number n, n÷2 = n + n
- For any n, if n belongs to N, then n÷2 = n + n,
Notation for quantifiers
The traditional symbol for the universal quantifier is "∀", an upside-down letter "A", which stands for the word "all". The corresponding symbol for the existential quantifier is "∃", a back-to-front letter "E", which stands for the word "exists". Correspondingly, quantified expressions are constructed as follows,Note that some versions of the notation explicitly mention the range of quantification. The range of quantification must always be specified, but for a given mathematical theory, this can be done in several ways:
- Assume a fixed domain of discourse for every quantification, as is done in Zermelo Fraenkel set theory,
- Fix several domains of discourse in advance and require that each variable have a declared domain, which is the type of that variable. This is analogous to the situation in strongly-typed computer programming languages, where variables have declared types.
- Mention explicitly the range of quantification, perhaps using a symbol for the set of all objects in that domain or the type of the objects in that domain.
Informally, the "∀x" or "∃x" might well appear after P(x), or even in the middle if P(x) is a long phrase. Formally, however, the phrase that introduces the dummy variable is standardly placed in front.
Note that mathematical formulas mix symbolic expressions for quantifiers, with natural language quantifiers such as
- For any natural number x, ....
- There exists an x such that ....
- For at least one x.
- For exactly one natural number x, ....
- There is one and only one x such that ....
- For any natural number, its product with 2 equals to its sum with itself
- Some natural number is prime.
Formal semantics
Mathematical semantics is the application of mathematics to study the meaning of expressions in a formal that is mathematically specified language. It has three elements: A mathematical specification of a class of objects via syntax, a mathematical specification of various semantic domains and the relation between the two, which is usually expressed as a function from syntactic objects to semantic ones. In this article, we only address the issue of how quantifier elements are interpreted.
In this section we only consider first order predicate calculus with function symbols. We refer the reader to the article on model theory for more information on the interpretation of formulas within this logical framework. The syntax of a formula can be give by by a syntax tree. Quantifiers have scope and a variable x is free if it is not within the scope of a quantification for that variable. Thus in
Syntactic tree illustrating scope and variable capture
The semantics for uniqueness quantification requires first order predicate calculus with equality. This means there is given a distinguished two-placed predicate "="; the semantics is also modified accordingly so that "=" is always interpreted as the two-place equality relation on X. The interpretation of
Paucal, multal and other degree quantifiers
So far we have only considered universal, existential and uniqueness quantification as used in mathematics. None of this applies to a quantification such as
- There were many dancers out on the dance floor this evening.
- There are many integers n < 100, such that n is divisible by 2 or 3 or 5.
We also caution the reader that the corresponding logic for such a semantics is exceedingly complicated.
History
The first treatment of quantification in formal logic is due to Gottlob Frege. His notation however, was quite different from that we in current use.