Quantification

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 .

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:

''Every glass in my recent order was chipped''.

''Some of the people standing across the river have white armbands''.

''Most of the people I talked to didn't have a clue who the candidates were''.

''Everyone in the waiting room had at least one complaint against Dr. Ballyhoo''.

''There was somebody in his class that was able to correctly answer every one of the questions I submitted''.

''A lot of people are smart''.

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 Language s 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.

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 Set s. 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,
:

\exists{n}\, P  \quad orall{n}\, P

where "''P''" denotes a formula. Many variant notations are used, such as
:

\exists{n}\, P \quad (\exists{n}) P \quad \exists{n}(P) \quad \exists_{n}\, P \quad \exists{n}{,}\, P \quad \exists{n}{:}\, P \quad \exists{n}{\in}\mathbb{N}\, P \quad \exists\, n \in \mathbb{N}{,}\, P \quad \exists{n}{:}\mathrm{uint}\, P

All of these variations apply to universal quantification as well as to existential quantification.

Early 20th century documents do not use the ∀ symbol. The typical notation is (''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:

Assume a fixed domain of discourse for every quantification, as is done in Zermelo Fraenkel set theory,

Fix several domains of discourse in advance and require that each variable have a declared domain, which is the ''type'' of that variable. This is analogous to the situation in strongly-typed Computer Programming languages, where variables have declared types.

Mention explicitly the range of quantification, perhaps using a symbol for the Set of all objects in that domain or the Type of the objects in that domain.

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

, a mathematical specification of various Semantic Domains and the relation between the two, which is usually expressed as a function from syntactic objects to semantic ones. In this article, we only address the issue of how quantifier elements are interpreted.

In this section we only consider First Order Logic with function symbols. We refer the reader to the article on Model Theory for more information on the interpretation of formulas within this logical framework. The syntax of a formula can be given by a syntax tree. Quantifiers have scope and a variable ''x'' is free if it is not within the scope of a quantification for that variable. Thus in
:

orall x (\exists y  B(x,y)) ee C(y,x)

the occurrence of both ''x'' and ''y'' in ''C''(''y'',''x'') is free.

An interpretation for first order predicate calculus assumes as given
a domain of individuals ''X''. A formula ''A'' whose free variables
are ''x''₁, ..., ''x''_n is interpreted as a
Boolean -valued function ''F''(''v''₁, ...,
''v''_''n'') of ''n'' arguments, where each argument ranges
over the domain ''X''. Boolean-valued means that the function assumes one of the values T (interpreted as truth) or '''F''' (interpreted as falsehood) . The interpretation of the formula
:

orall x_n A(x_1, \ldots , x_n)

is the function ''G'' of ''n''-1 arguments such that ''G''(''v''₁, ...,''v''_''n''-1) = T iff ''F''(''v''₁, ..., ''v''_''n''-1, ''w'') = T for every ''w'' in ''X''. If ''F''(''v''₁, ..., ''v''_''n''-1, ''w'') = '''F''' for at least one value of ''w'', then ''G''(''v''₁, ...,''v''_''n''-1) = '''F'''. Similarly the interpretation of the formula
:

\exists x_n A(x_1, \ldots , x_n)

is the function ''H'' of ''n''-1 arguments such that ''H''(''v''₁, ...,''v''_''n''-1) = T iff ''F''(''v''₁, ...,''v''_''n''-1, ''w'') = T for at least one ''w'' and ''H''(''v''₁, ..., ''v''_''n''-1) = '''F''' otherwise.

The semantics for Uniqueness Quantification requires first order predicate calculus with equality. This means there is given a distinguished two-placed predicate "="; the semantics is also modified accordingly so that "=" is always interpreted as the two-place equality relation on ''X''. The interpretation of
:

\exists !   x_n A(x_1, \ldots , x_n)

then is the function of ''n''-1 arguments, which is the logical ''and'' of the interpretations of
:

\exists  x_n A(x_1, \ldots , x_n)

orall y,z \left\{  A(x_1, \ldots ,x_{n-1}, y) \wedge  A(x_1, \ldots ,x_{n-1}, z) \implies y = z 
ight\}

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

There were many dancers out on the dance floor this evening.

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

There are many integers ''n'' < 100, such that ''n'' is divisible by 2 or 3 or 5.

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 ''x''₁,...,''x''_''n'' whose interpretation is
the function ''F'' of variables ''v''₁,...,''v''_''n''
then the interpretation of
:

\exists^{\mathrm{many}} x_n A(x_1, \ldots, x_{n-1}, x_n)

is the function of ''v''₁,...,''v''_''n''-1 which is T iff
:

\operatorname{P} \{w: F(v_1, \ldots, v_{n-1}, w) = \mathbf{T} \} \geq b

and F otherwise. Similarly, the interpretation of
:

\exists^{\mathrm{few}}  x_n  A(x_1, \ldots, x_{n-1}, x_n)

is the function of ''v''₁,...,''v''_''n''-1 which is F iff
:

0< \operatorname{P} \{w: F(v_1, \ldots, v_{n-1}, w) = \mathbf{T}\} \leq a

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 FORMALISATION

The first variable-based treatments of quantification in Formal Logic did not appear until the 19th Century , although Term Logic treats quantification in a manner that is closer to how quantifiers appear in natural language, and is less suited to formal analysis. Aristotelian Logic gave an account of the ''All''', ''Some'' and ''No'' quantifiers in the 1st Century BC in an account that also treated the Alethic Modalities .

The first variable-based treatment of logic was that of Gottlob Frege 's Begriffsschrift , but was closely followed by C. S. Pierce 's independent formulation of Existential Graphs . Frege's account proved the more influential, due to its adoption by Giuseppe Peano , although Pierce's logic has recently been attracting greater interest by logicians interested in Heterogenous Reasoning and Diagrammatic Inference .

The first rigorous notation for quantification appeared in Gottlob Frege 's '' Begriffsschrift ''. Frege used a curved line underneath a variable name to indicate that the variable was universally quantified in the formula that followed. Frege did not have a special notation for existential quantification, instead using the equivalent of

\simorall x:\sim\ldots

.

In Whitehead and Russell 's '' Principia Mathematica '', Frege's notation was simplified. The formula "

(x)\phi

" was used to indicate that the formula φ was true for all values of ''x''. Existential quantification was written "

(\exists x)\phi

"; the ∃ symbol itself was first used by Peano in 1897 .

The ∀ symbol was a later invention, introduced by Gentzen in 1935 by analogy with Peano's ∃ symbol.

REFERENCES

(Frege 1879) Begriffsschrift

(Hilbert and Ackermann 1928) ''Grundzüge der theoretischen Logik'' (''Principles of Theoretical Logic''). Springer-Verlag, ISBN 0-8218-2024-9.

(Wiese 2003) ''Numbers, language, and the human mind''. Cambridge University Press, ISBN 0-521-83182-2.

( Hans Reichenbach 1947), ''Elements of Symbolic Logic'', Dover Publications, New York, reprinted 1975, ISBN 0-486-24004-5. Quite readable, suitable for all who are interested in mathematical logic. Cf Reichenbach extensively defines and treats the quantifiers in chapters §18 "Binding of variables" through §30 "Derivations from Synthetic Premises".

EXTERNAL LINKS

http://www.stanford.edu/group/nasslli/courses/peters-wes/PWbookdraft2-3.pdf

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT QUANTIFICATION

	logic

	quantification

	philosophical logic

	semanticslogic

	quantification

	philosophical logic

	semantics

	semantics

	mathematical logic

Information About

Quantification