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" (with the same syntactic behaviour as and ) can (according to A. Mostowski) be given by a mapping associating with each model a class of subsets of . Then one stipulates as a truth-definition for that, e.g., a sentence holds in if and only if the set is in . Thus, with the existential quantifier is associated the class of non-empty subsets of and with the universal quantifier is associated the class . However, there are many more possible quantifiers, e.g. given by , (the Chang quantifier), , 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 binding two variables and in two formulas and , yielding the formula , which is interpreted by ). 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=35865
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article