quantifier

Introduction

A quantifier is a logical symbol which makes an assertion about the set of values which make one or more formulas true. This is an exceedingly general concept; the vast majority of mathematics is done with the two standard quantifiers, $\forall$ (for all) and $\exists$ (there exists).

The universal quantifier $\forall$ takes a variable $x$ and a formula, which may or may not contain $x$, and asserts that the formula holds for any value of $x$ (the value as being taken from some given universe $A$). A typical example would be a sentence like:

$$\forall x[0\le x]$$

which states that no matter what value $x$ takes (from $A$), $0\le x$.

The existential quantifier $\exists$ is the dual; that is the formula $\exists x\varphi (x)$ is equivalent to $\mathrm{\neg }\forall x\mathrm{\neg }\varphi (x)$. It states that there is some $x$ satsifying the formula, as in

$$\exists x[x>0]$$

which states that there is some value of $x$ greater than $0$.

Remark. In practice, for simplicity, one usually writes $\exists x_1,x_2,\mathrm{\dots },x_n\varphi (x_1,\mathrm{\dots },x_n)$ or $\exists 𝒙\varphi (𝒙)$ (where $𝒙=(x_1,\mathrm{\dots },x_n)$), instead of $\exists x_1\exists x_2\mathrm{\cdots }\exists x_n\varphi (x_1,\mathrm{\dots },x_n)$.

Scopes

The scope of a quantifier is the portion of a formula where it binds its variables. Note that previous bindings of a variable are overridden within the scope of a quantifier. In the examples above, the scope of the quantifiers was the entire formula, but that need not be the case. The following is a more complicated use of quantifiers:

$$\forall x\underset{\text{The scope of the universal quantifier.}}{\underbrace{[x=0\vee \exists y\stackrel{\text{The scope of the first existential quantifier.}}{\overbrace{[x=y+1\wedge (y=0\vee \exists x\underset{†}{\underbrace{[y=x+1]}})]}}]}}$$

$†$:The scope of the second existential quantifier. Within this area, all references to $x$ refer to the variable bound by the existential quantifier. It is impossible to refer directly to the one bound by the universal quantifier.

As that example illustrates, it can be very confusing when one quantifier overrides another. Since it does not change the meaning of a sentence to change a bound variable and all bound occurrences of it, it is better form to replace sentences like that with an equivalent but more readable one like:

$$\forall x[x=0\vee \exists y[x=y+1\wedge (y=0\vee \exists z[y=z+1])]]$$

These sentences both assert that every number is either equal to zero, or that there is some number one less than it, and that the number one less than it is also either zero or has a number one less than it. [Note: This is not the most useful of sentences. It would be nice to replace this with a mathematically simple sentence which uses nested quantifiers meaningfully.]

Variations

The quantifiers may not range over all objects. That is, $\forall x\varphi (x)$ may not specify that $x$ can be any object, but rather any object belonging to some class of objects. Similarly $\exists x\varphi (x)$ may specify that there is some $x$ within that class which satisfies $\varphi$. For instance second order logic has two universal quantifiers, ${\forall }^1$ and ${\forall }^2$ (with corresponding existential quantifiers), and variables bound by them only range over the first and second order objects respectively. So ${\forall }^{1}x[0\le x]$ only states that all numbers are greater than or equal to $0$, not that sets of numbers are as well (which would be meaningless).

A particular use of a quantifier is called bounded or restricted if it limits the objects to a smaller range. This is not quite the same as the situation mentioned above; in the situation above, the definition of the quantifier does not include all objects. In this case, quantifiers can range over everything, but in a particular formula it doesn’t. This is expressed in first order logic with formulas like these four:

$\forall x[x\in X\to \varphi (x)]$ $\exists x[x\in X\wedge \varphi (X)]$

The restriction is often incorporated into the quantifier. For instance the first example might be written .

A quantifier is called vacuous if the variable it binds does not appear anywhere in its scope, such as $\forall x\exists y[0\le x]$. While vacuous quantifiers do not change the meaning of a sentence, they are occasionally useful in finding an equivalent formula of a specific form.

While these are the most common quantifiers (in particular, they are the only quantifiers appearing in classical first-order logic), some logics use others. The quantifier

$$\exists !x\varphi (x),$$

which means that there is a unique $x$ satsifying $\varphi (x)$ is equivalent to

$$\exists x[\varphi (x)\wedge \forall y[\varphi (y)\to x=y]].$$

Other quantifiers go beyond the usual two. Examples include interpreting $Qx\varphi (x)$ to mean there are an infinite (or uncountably infinite) number of $x$ satisfying $\varphi (x)$. More elaborate examples include the branching Henkin quantifier, written:

This quantifier is similar to $\forall x\exists y\forall a\exists b\varphi (x,y,a,b)$ except that the choice of $a$ and $b$ cannot depend on the values of $x$ and $y$. This concept can be further generalized to the game-semantic, or independence-friendly, quantifiers. All of these quantifiers are examples of generalized quantifiers.

Title	quantifier
Canonical name	Quantifier
Date of creation	2013-03-22 12:59:09
Last modified on	2013-03-22 12:59:09
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	18
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B15
Classification	msc 03B10
Synonym	restricted quantifier
Related topic	HartigsQuantifier
Related topic	GameTheoreticalQuantifier
Related topic	QuantifierFree
Related topic	GeneralizedQuantifier
Defines	scope
Defines	universal quantifier
Defines	existential quantifier
Defines	bound
Defines	bounded quantifier
Defines	vacuous
Defines	vacuous quantification