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.
| Table of contents |
|
2 Domains of discourse 3 Symbolic expression of quantifiers 4 Quantification in natural language 5 Degenerate cases 6 History |
Suppose you wish to say:
The basic idea
Logically, 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:
On the other hand, suppose you wish to say:
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.
In the examples above, the natural numbers for the domain or universe of discourse for the quantification.
This specifies what values the variable (n above) is allowed to take.
This allows us to capture the difference between, for example, "For some natural number n, n2 = 2" and "For some real number x, x2 = 2".
After all, the first statement is false, but the second statement is true.
Now, convention suggests using "n" for natural numbers and "x" for real numbers, and this might get across the meaning.
But even then, the domain of discourse is being implicitly specified by the letter chosen for the variable.
Without a given domain of discourse, quantification has no meaning.
(Of course, if you're only looking at syntax in formal logic, then this may be OK; but the domain of discourse comes in at the level of semantics.)
You can also restrict the domain of discourse using guarded quantification.
For example, the statement "For some natural number n, n is even and n is prime" is just a long-winded way to say "For some even number n, n is prime".
Thus the existential quantification has been guarded by the predicate "n is even" using a conjunction (the "and").
A statement that applied to all natural numbers has been restricted to only even numbers.
Similarly, the statement "For any natural number n, if n is perfect, then n is even" is just a long-winded way to say "For any perfect number n, n is even".
Here, the universal quantification has been guarded by the predicate "n is perfect" using a conditional (the "if ... then").
A statement that applied to all natural numbers has been restricted to only perfect numbers.
(By the way, nobody knows whether this last example is a true statement!)
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 n, n·2 = n + n" in Zermelo-Fraenkel set theory, you can say "For any n, if n belongs to N, then n·2 = n + n", where N is the set of all natural numbers.
This works because belonging to sets is a fundamental concept of set theory.
(Of course, you also have to express the operations of arithmetic in terms of set theory, for example by treating the natural numbers as certain Von Neumann ordinals.)
More generally, you can limit the domain of discourse to only those objects satisfying a given predicate Q(x) by guarding the quantifier with that predicate.
The above example is just a special case with Q(n) = "n belongs to N".
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 "P(n)" to stand for the predicate that's being quantified over (in our examples, P(n) is "n·2 = n + n" or "n is prime"), then a wide variety of notations may be used to indicate quantification in symbolic logic, including:
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:
Informally, the "∀x" or "∃x" might well appear after P(x), or even in the middle if P(x) is a long phrase.
Formally, however, the phrase that introduces the dummy variable is standardly placed in front.
Several phrasings are used for universal quantification, such as:
Keywords for uniqueness quantification include:
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 n, Jacques Chirac is president of France", or "For some prime number p, Helmut Kohl is Bundeskanzler of Germany".
These examples are degenerate, but a complete understanding of quantification requires understanding this as well.
If the proposition P being quantified is false, then this is easy; the quantified statement is also false.
If P is true, then the universal quantification ∀x P is also true, but other quantified statements will depend on the nature of the domain of discourse.
For example, the existential quantification "There exists x such that 1 + 1 = 2" is true if some x exists at all -- in other words, if the domain of discourse is not empty.
And the uniqueness quantification "There exists a unique x such that 1 + 1 = 2" is true if there exists a unique x, period -- in other words, if the domain of discourse has precisely one object in it.
In many formalisations of predicate logic, it's assumed that the domain of discourse is not empty.
In that case, "∃x P" has the same truth value as the proposition P.
A lot of stuff, on various logic articles, relating to Aristotle would fit here.
Domains of discourse
Symbolic expression of quantifiers
and combinations of the above.
All of these variations apply to universal quantification as well as to existential quantification, of course.
Additionally, the expression "(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.)
Also note that you can use (almost) any variable in the notation, because this is a dummy variable (that is, not a free variable).
Even if your notation restricts certain variables to certain domains of discourse, still you can use any variable that applies to that domain.
The exception is if the new choice of variable already appears somewhere else in the expression 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.)uint" refers to the type of the natural numbers.Quantification in natural language
Similarly, several phrasings are used for existential quantification, such as:
Again, the above variations can be combined, and of course a domain of discourse other than "natural numbers" might appear.
In a less formal context, we might avoid the variable 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
History