Main Page | See live article | Alphabetical index In 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. Table of contents 1 The basic idea 2 Domains of discourse 3 Symbolic expression of quantifiers 4 Quantification in natural language 5 Degenerate cases 6 History The basic idea Suppose you wish to say: 0·2 = 0 + 0, and 1·2 = 1 + 1, and 2·2 = 2 + 2, etc. 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: For any natural number n, n·2 = n + n. This is a single statement using universal quantification. On the other hand, suppose you wish to say: 0 is prime, or 1 is prime, or 2 is prime, etc. Logically, this would seem to be a disjunction, because of the repeated use of "or". But the "etc" can't be interpreted as a disjunction in formal logic. Instead, rephrase the statement as: For some natural number n, n is prime. This is a single statement using 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 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". 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 "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: 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.) 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. 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.) 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. Quantification in natural language Several 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). Similarly, several phrasings are used for existential quantification, such as: There is some x such that .... For some natural number x, .... There exists an x such that .... ..., for at least one x. Again, the above variations can be combined, and of course a domain of discourse other than "natural numbers" might appear. Keywords for uniqueness quantification include: The x such that ... is unique. For exactly one natural number x, .... There is only one x such that .... 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 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. History A lot of stuff, on various logic articles, relating to Aristotle would fit here. This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.