Namespaces
Variants
Actions

Quantifier

From Encyclopedia of Mathematics
Jump to: navigation, search

The general name for a logical operation that constructs from a predicate $P(x)$ a statement characterizing the domain of validity of $P(x)$. In mathematical logic, the most widely used quantifiers are the universal quantifier $\forall$ and the existential quantifier $\exists$. The statement $\forall x\ P(x)$ means that the domain of validity of $P(x)$ is the same as the domain of values of the variable $x$. The statement $\exists x\ P(x)$ means that the domain of validity of $P(x)$ is non-empty. If one is interested in the behaviour of the predicate $P(x)$ not on the whole domain of values of $x$, but only on the part singled out by a predicate $R(x)$, then one often uses the restricted quantifiers $\forall_{R(x)}$ and $\exists_{R(x)}$. In this case, the statement $\exists_{R(x)} x\ P(x)$ means the same as $\exists x\ R(x) \wedge P(x)$, while $\forall_{R(x)} x\ P(x)$ has the same meaning as $\forall x\ R(x) \rightarrow P(x)$, where $\wedge$ is the conjunction sign and $\rightarrow$ is the implication sign.


Comments

The subject of quantifiers nowadays is far more involved than suggested above, since there are many more quantifiers (e.g. game quantifiers, probability quantifiers) than just the two (or four) discussed above.

More generally, the model-theoretic interpretation of an arbitrary "quantifier" $Q$ (with the same syntactic behaviour as $\forall$ and $\exists$) can (according to A. Mostowski) be given by a mapping associating with each model $(A,\dots)$ a class $\tilde Q$ of subsets of $A$. Then one stipulates as a truth-definition for $Q$ that, e.g., a sentence $Qx\ \Phi(x)$ holds in $(A,\dots)$ if and only if the set $\{a\in A:\Phi(a)\text{ holds in }(A,\dots)\}$ is in $\tilde Q$. Thus, with the existential quantifier $\exists$ is associated the class of non-empty subsets of $A$ and with the universal quantifier $\forall$ is associated the class $\{A\}$. However, there are many more possible quantifiers, e.g. given by $\{B\subset A:B\text{ finite}\}$, $\{B\subset A:B\text{ has the same cardinality as }A\}$ (the Chang quantifier), $\{B\subset A:B\text{ is uncountable}\}$, etc.

This set-up can be generalized to polyadic "quantifiers" binding more than one variable occurring in more than one formula (example: the equi-cardinality quantifier $Q$ binding two variables $x$ and $y$ in two formulas $\Phi(x)$ and $\Psi(y)$, yielding the formula $Qxy(\Phi(x),\Psi(y))$, which is interpreted by $\{(B,C):B\text{ and }C\text{ have the same cardinality}\}$). Even more general is the Lindström quantifier. And each quantifier has its own logic.

References

[a1] J. Barwise (ed.) S. Feferman (ed.) , Model-theoretic logics , Springer (1985)
How to Cite This Entry:
Quantifier. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Quantifier&oldid=43568
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article