Namespaces
Variants
Actions

Difference between revisions of "Quantifier"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
The general name for a logical operation that constructs from a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762601.png" /> a statement characterizing the domain of validity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762602.png" />. In mathematical logic, the most widely used quantifiers are the universal quantifier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762603.png" /> and the existential quantifier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762604.png" />. The statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762605.png" /> means that the domain of validity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762606.png" /> is the same as the domain of values of the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762607.png" />. The statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762608.png" /> means that the domain of validity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q0762609.png" /> is non-empty. If one is interested in the behaviour of the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626010.png" /> not on the whole domain of values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626011.png" />, but only on the part singled out by a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626012.png" />, then one often uses the restricted quantifiers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626014.png" />. In this case, the statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626015.png" /> means the same as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626016.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626017.png" /> has the same meaning as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626018.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626019.png" /> is the [[Conjunction|conjunction]] sign and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626020.png" /> is the [[Implication|implication]] sign.
+
{{TEX|done}}
 +
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.
  
  
Line 6: Line 7:
 
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.
 
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"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626021.png" /> (with the same syntactic behaviour as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626023.png" />) can (according to A. Mostowski) be given by a mapping associating with each model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626024.png" /> a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626025.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626026.png" />. Then one stipulates as a truth-definition for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626027.png" /> that, e.g., a sentence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626028.png" /> holds in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626029.png" /> if and only if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626030.png" /> is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626031.png" />. Thus, with the existential quantifier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626032.png" /> is associated the class of non-empty subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626033.png" /> and with the universal quantifier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626034.png" /> is associated the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626035.png" />. However, there are many more possible quantifiers, e.g. given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626037.png" /> (the Chang quantifier), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626038.png" />, etc. This set-up can be generalized to  "quantifiers"  binding more than one variable occurring in more than one formula (example: the equi-cardinality quantifier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626039.png" /> binding two variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626041.png" /> in two formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626043.png" />, yielding the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626044.png" />, which is interpreted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076260/q07626045.png" />). Even more general is the Lindström quantifier. And each quantifier has its own logic.
+
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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Barwise (ed.)  S. Feferman (ed.) , ''Model-theoretic logics'' , Springer  (1985)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Barwise (ed.)  S. Feferman (ed.) , ''Model-theoretic logics'' , Springer  (1985)</TD></TR></table>

Latest revision as of 11:33, 30 December 2018

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://encyclopediaofmath.org/index.php?title=Quantifier&oldid=14021
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article