|
In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. A quantification imposes a limitation on the variables of a proposition. A language element which generates a quantification is called a quantifier. The resulting statement is a quantified statement, and we say we have quantified over the predicate. Quantification is used in both natural languages and formal languages. Examples of quantifiers in a natural language are: for all, for some, many, few, a lot, and no. In formal languages, quantification is a formula constructor that produces new formulas from old ones. The semantics of the language specifies how the constructor is interpreted as an extent of validity. Quantification is an example of a variable-binding operation. The two fundamental kinds of quantification in predicate logic 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 traditional symbol for the universal quantifier "all" is "∀", an inverted letter "A", and for the existential quantifier "exists" is "∃", a rotated letter "E". Quantification in natural language All known human languages make use of quantification, even languages without a fully fledged number system (Wiese 2004). For example, in English: There exists no simple way of reformulating any one of these expressions as a conjunction or disjunction of sentences, each a simple predicate of an individual such as That wine glass was chipped. These examples also suggest that the construction of quantified expressions in natural language can be syntactically very complicated. Fortunately, for mathematical assertions, the quantification process is syntactically more straightforward. The study of quantification in natural languages is much more difficult than the corresponding problem for formal languages. This comes in part from the fact that the grammatical structure of natural language sentences may conceal the logical structure. Moreover, mathematical conventions strictly specify the range of validity for formal language quantifiers; for natural language, specifying the range of validity requires dealing with non-trivial semantic problems. Montague grammar gives a novel formal semantics of natural languages. Its proponents argue that it provides a much more natural formal rendering of natural language than the traditional treatments of Frege, Russell and Quine. Need for quantifiers in mathematical assertions We will begin by discussing quantification in informal mathematical discourse. Consider the following statement 1·2 = 1 + 1, and 2·2 = 2 + 2, and 3 · 2 = 3 + 3, ...., and n · 2 = n + n, etc. This has the appearance of an infinite conjunction of propositions. From the point of view of formal languages this is immediately a problem, since we expect syntax rules to generate finite objects. Putting aside this objection, also note that in this example we were lucky in that there is a procedure to generate all the conjuncts. However, if we wanted to assert something about every irrational number, we would have no way enumerating all the conjuncts since irrationals cannot be enumerated. A succinct formulation which avoids these problems uses universal quantification: For any natural number n, n·2 = n + n. A similar analysis applies to the disjunction, 1 is prime, or 2 is prime, or 3 is prime, etc. which can be rephrased using existential quantification: For some natural number n, n is prime. Nesting of quantifiers Consider the following statement: For any natural number n, there is a natural number s such that s = n × n. This is clearly true; it just asserts that every number has a square. The meaning of the assertion in which the quantifiers are turned around is quite different: There is a natural number s such that for any natural number n, s = n × n. This is clearly false; it asserts that there is a single natural number s that is at once the square of every natural number. This illustrates a fundamentally important point when quantifiers are nested: The order of alternation of quantifiers is of absolute importance. A less trivial example is the important concept of uniform continuity from analysis, which differs from the more familiar concept of pointwise continuity only by an exchange in the positions of two quantifiers. To illustrate this, let f be a real-valued function on R. interchanging the universal quantifiers over the braces, this is the same as This differs from by interchanging the existential and universal quantifiers over the braces in A'. Range of quantification Every quantification involves one specific variable and a domain of discourse or range of quantification of that variable. The range of quantification specifies the set of values that the variable takes. In the examples above, the range of quantification is the set of natural numbers. Specification of the range of quantification allows us to express the difference between, asserting that a predicate holds for some natural number or for some real number. Expository conventions often reserve some variable names such as "n" for natural numbers and "x" for real numbers, although relying exclusively on naming conventions cannot work in general since ranges of variables can change in the course of a mathematical argument. A more natural way to restrict the domain of discourse uses guarded quantification. For example, the guarded quantification For some natural number n, n is even and n is prime means For some even number n, n is prime. In some mathematical theories one assumes a single domain of discourse fixed in advance. For example, in Zermelo Fraenkel set theory, variables range over all sets. In this case, guarded quantifiers can be used to mimic a smaller range of quantification. Thus in the example above to express For any natural number n, n·2 = n + n in Zermelo-Fraenkel set theory, one can say For any n, if n belongs to N, then n·2 = n + n, where N is the set of all natural numbers. Notation for quantifiers The traditional symbol for the universal quantifier is "∀", an inverted letter "A", which stands for the word "all". The corresponding symbol for the existential quantifier is "∃", a rotated letter "E", which stands for the word "exists". Correspondingly, quantified expressions are constructed as follows, where "P" denotes a formula. Many variant notations are used, such as All of these variations also apply to universal quantification. Other variations for the universal quantifier are Early 20th century documents do not use the ∀ symbol. The typical notation was (x)P to express "for all x, P", and "(∃x)P" for "there exists x such that P". The ∃ symbol was coined by Giuseppe Peano around 1890. Later, around 1930, Gerhard Gentzen introduced the ∀ symbol to represent universal quantification. Frege's Begriffsschrift used an entirely different notation, which did not include an existential quantifier at all; ∃x P was always represented instead with the Begriffsschrift equivalent of ¬∀x ¬P. Note that some versions of the notation explicitly mention the range of quantification. The range of quantification must always be specified, but for a given mathematical theory, this can be done in several ways: Also note that one can use any variable as a quantified variable in place of any other, under certain restrictions, that is in which variable capture does not occur. Even if the notation uses typed variables, one can still use any variable of that type. The issue of variable capture is exceedingly important, and we discuss that in the formal semantics below. 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. Note that mathematical formulas mix symbolic expressions for quantifiers, with natural language quantifiers such as For any natural number x, .... There exists an x such that .... For at least one x. Keywords for uniqueness quantification include: For exactly one natural number x, .... There is one and only one x such that .... One might even avoid variable names such as x using a pronoun. For example, For any natural number, its product with 2 equals to its sum with itself Some natural number is prime. Formal semantics
Paucal, multal and other degree quantifiers So far we have only considered universal, existential and uniqueness quantification as used in mathematics. None of this applies to a quantification such as Though we will not consider semantics of natural language in this article, we will attempt to provide a semantics for assertions in a formal language of the type One possible interpretation mechanism can obtained as follows: Suppose that in addition to a semantic domain X, we have given a probability measure P defined on X and cutoff numbers 0 < a ≤ b ≤ 1. If A is a formula with free variables x1,...,xn whose interpretation is the function F of variables v1,...,vn then the interpretation of is the function of v1,...,vn-1 which is T if and only if and F otherwise. Similarly, the interpretation of is the function of v1,...,vn-1 which is F if and only if and T otherwise. We have completely avoided discussion of technical issues regarding measurability of the interpretation functions; some of these are technical questions that require Fubini's theorem. We also caution the reader that the corresponding logic for such a semantics is exceedingly complicated. History of formalization Term logic treats quantification in a manner that is closer to natural language, and also less suited to formal analysis. Aristotelian logic treated All, Some and No in the 1st century BC, in an account also touching on the alethic modalities. The first variable-based treatment of quantification was Gottlob Frege's 1879 Begriffsschrift. To universally quantify a variable, Frege would make a dimple in an otherwise straight line appearing in his diagrammatic formulas, then write the quantified variable over the dimple. Frege did not have a specific notation for existential quantification, instead using the equivalent of . Frege's treatment of quantification went largely unremarked until Bertrand Russell's 1903 Principles of Mathematics. Meanwhile, Charles Sanders Peirce and his student O. H. Mitchell independently invented the existential as well as the universal quantifier, in work culminating in Peirce (1885). Peirce and Mitchell wrote Πx and Σx where we now write ∀x and ∃x. This notation can be found in the writings of Ernst Schroder, Leopold Loewenheim, Thoralf Skolem, and Polish logicians into the 1950s. It is the notation of Kurt Goedel's landmark 1930 paper on the completeness of first order logic, and 1931 paper on the incompleteness of Peano arithmetic. Peirce's later existential graphs can be seen as featuring tacit variables whose quantification is determined by the shallowest instance. Peirce's approach to quantification influenced Ernst Schroder, William Ernest Johnson, and all of Europe via Giuseppe Peano. Pierce's logic has attracted fair attention in recent decades by those interested in heterogeneous reasoning and diagrammatic inference. Peano notated the universal quantifier as (x). Hence "(x)φ" indicated that the formula φ was true for all values of x. He was the first to employ, in 1897, the notation (∃x) for existential quantification. The Principia Mathematica of Whitehead and Russell employed Peano's notation, as did Quine and Alonzo Church throughout their careers. Gentzen introduced the ∀ symbol 1935 by analogy with Peano's ∃ symbol. ∀ did not become canonical until the 1950s. | |||||||||
|
| ||||||||||
 |
|
| |