3 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.

This could be explained using a challenge-response framework as follows: For any n that you give me, I will give a prime p_n such that n < p_n ≤ 2 n. The meaning of the assertion in which the quantifiers are turned around

There is a prime number p such that for any natural number n, n < p ≤ 2 n.

is quite different and is actually false. In the challenge-response framework it would mean that I could select the prime p once and for all at the beginning. This of course is not possible.

This illustrates a fundamentally important point when quantifiers are nested: The order of alternation of quantifiers is of absolute importance.

4 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

means

For some even number n, n is prime.

In some mathematical theories one assumes a single domain of discourse fixed in advance. For example, in Zermelo Fraenkel set theory, variables range over all sets. In this case, guarded quantifiers can be used to mimic a smaller range of quantification. Thus in the example above to express

For any natural number n, n·2 = n + n

in Zermelo-Fraenkel set theory, one can say

For any n, if n belongs to N, then n·2 = n + n,

where N is the set of all natural numbers.

5 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,

where "P" denotes a formula. Many variant notations are used, such as

All of these variations apply to universal quantification as well as to existential quantification. Additionally, the expression "(n) P" is sometimes used for universal quantification.

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.

Also note that one can use any variable as a quantified variable in place of any other, under certain restrictions, that is in which variable capture does not ocur. Even if the notation uses typed variables, one can still use any variable of that type. The issue of variable capture is exceedingly important, and we discuss that in the formal semantics below.

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.

Keywords for uniqueness quantification include:

For exactly one natural number x, ....

There is one and only one x such that ....

One might even avoid variable names such as x using a pronoun. For example,

For any natural number, its product with 2 equals to its sum with itself

Some natural number is prime.

6 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

the occurrence of y in C(y,x) is free.

An interpretation for first order predicate calculus assumes as given a domain of individuals X. A formula A whose free variables are x₁, ..., x_n is interpreted as a

boolean-valued function F(v₁, ...,

v_n) of n arguments, where each argument ranges over the domain X. Boolean-valued means that the function assumes one of the values T (interpreted as truth) or F(interpreted as falsehood) . The interpretation of the formula

is the function G of n-1 arguments such that G(v₁, ...,v_n-1) = T iff F(v₁, ..., v_n-1, w) = T for every w in X. If F(v₁, ..., v_n-1, w) = F for at least one value of w, then G(v₁, ...,v_n-1) = F. Similarly the interpretation of the formula

is the function H of n-1 arguments such that H(v₁, ...,v_n-1) = T iff F(v₁, ...,v_n-1, w) = T for at least one w and H(v₁, ..., v_n-1) = F otherwise.

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

then is the function of n-1 arguments, which is the logical and of the interpretations of

7 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.

Though we will not consider semantics of natural language in this article, we will attempt to provide a semantics for assertions in a formal language of the type

• There are many integers n < 100, such that n is divisible by 2 or 3 or 5.

One possible interpretation mechanism can obtained as follows: Suppose that in addition to a semantic domain X, we have given a probability measure P defined on X and cutoff numbers 0 < a ≤ b ≤ 1. If A is a formula with free variables x₁,...,x_n whose interpretation is the function F of variables v₁,...,v_n then the interpretation of

is the function of v₁,...,v_n-1 which is T iff

and F otherwise. Similarly, the interpretation of

is the function of v₁,...,v_n-1 which is F iff

and T otherwise. We have completely avoided discussion of technical issues regarding measurability of the interpretation functions; some of these are technical questions that require Fubini's theorem.

We also caution the reader that the corresponding logic for such a semantics is exceedingly complicated.

8 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.

<Hide>