home | alphabetical index | |||||||

## QuantificationIn predicate logic,quantification is a method of turning a predicate (or open sentence), into a proposition (or closed sentence).
This is done by specifying how often the predicate holds.
The resulting statement is a quantified statement, and we have quantified over the predicate.
In symbolic logic, a quantifier is the symbol used to denote quantification.The two fundamental kinds of quantification are universal quantification and existential quantification. These concepts are covered in detail in their individual articles; here we discuss features of quantification that apply in both cases. Other kinds of quantification include uniqueness quantification.
## The basic ideaLogically, this would seem to be a conjunction, because of the repeated use of "and". But the "etc" can't be interpreted as a conjunction in formal logic. Instead, rephrase the statement as:- For any natural number
*n*,*n*·2 =*n*+*n*.
universal quantification.On the other hand, suppose you wish to say: - 0 is prime, or 1 is prime, or 2 is prime, etc.
- For some natural number
*n*,*n*is prime.
existential quantification.Notice that the quantified statements are really more precise than the original forms. It may seem obvious that the phrase "and so on" is meant to include all natural numbers, and nothing more, but this wasn't explicitly stated, which is essentially the reason that the phrase couldn't be interpreted formally. In the quantified statements, on the other hand, the natural numbers are mentioned explicitly. ## Domains of discourse
In the examples above, the natural numbers for the
You can also restrict the domain of discourse using
In some applications of predicate logic, one assumes a single universe of discourse fixed in advance.
For example, in the standard Zermelo-Fraenkel axioms of axiomatic set theory, the domain of discourse always consists of all sets.
In this case, guarded quantifiers can be used to mimic smaller domains of discourse.
Thus in the example that began this article, to say "For any natural number ## Symbolic expression of 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 "∃", and upsided-down letter "E", which stands for the word "exists".
If we use the notation " n) P(n)" is sometimes used for universal quantification.
(And of course, symbolic logic provides a variety of notations for the predicate P(n), each of which could be combined with the variety of notations for the quantifiers.)You may have noticed that some versions of the notation explicitly mention the domain of discourse (in this case, the natural numbers), while others don't. The domain of discourse must always be specified, but there are still several ways that this can be done, some of them rather implicit: - One way is to assume, throughout a specific application of predicate logic, that a single domain of discourse is always meant. For example, this is done in the standard Zermelo-Fraenkel axioms of set theory, where it's assumed that the domain of discourse always consists of all sets.
- Alternatively, you can fix several domains of discourse in advance but declare that certain variables are to be used only for certain domains. So in the examples above, the variable
*n*would refer only to natural numbers. This is analogous to the practice in strongly-typed computer programming languages, where variables must always be declared in advance to have a certain data type. - Finally, you can mention the domain of discourse explicitly, perhaps using a symbol for the set of all objects in that domain (if you're using set theory) or the type of the objects in that domain (if you're using type theory). Above, the symbol "
**N**" refers to the set of all natural numbers, and the symbol "`uint` " refers to the type of the natural numbers.
P(n), or if the entire quantified statement is embedded inside a larger expression that already uses the new variable freely.
(This exception, of course, is simply a general restriction on the use of dummy variables.)
Informally, the "∀ ## Quantification in natural languageSeveral phrasings are used for universal quantification, such as: - For any natural number
*x*, .... - For all natural numbers
*x*, .... - For every
*x*, .... - ... for each
*x*. - ... (
*x*is a natural number).
- There is some
*x*such that .... - For some natural number
*x*, .... - There exists an
*x*such that .... - ..., for at least one
*x*.
Keywords for uniqueness quantification include: - The
*x*such that ... is unique. - For exactly one natural number
*x*, .... - There is only one
*x*such that ....
x entirely in favour of a pronoun.
For example, we could say "For any natural number, its product with 2 equals to its sum with itself" or "For some natural number, it is prime"; here, "it" takes the place of the dummy variable.
Even less formally, "Some natural number is prime".## Degenerate cases
In a quantified statement, there's no reason that the predicate involved must actually involve the variable that's being quantified over.
That is, the predicate might simply be a proposition.
For example, we could say "For any natural number
If the proposition
In many formalisations of predicate logic, it's assumed that the domain of discourse is ## History
| |||||||

copyright © 2004 FactsAbout.com |