HOME

TheInfoList



OR:

In
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, a quantifier is an operator that specifies how many individuals in the
domain of discourse In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range. Overview The domain ...
satisfy an
open formula An open formula is a formula that contains at least one free variable. An open formula does not have a truth value assigned to it, in contrast with a closed formula which constitutes a proposition and thus can have a truth value like ''true'' or ' ...
. For instance, the
universal quantifier In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other w ...
\forall in the first order formula \forall x P(x) expresses that everything in the domain satisfies the property denoted by P. On the other hand, the
existential quantifier In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, w ...
\exists in the formula \exists x P(x) expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest
scope Scope or scopes may refer to: People with the surname * Jamie Scope (born 1986), English footballer * John T. Scopes (1900–1970), central figure in the Scopes Trial regarding the teaching of evolution Arts, media, and entertainment * Cinem ...
is called a quantified formula. A quantified formula must contain a
bound variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a Mathematical notation, notation (symbol) that specifies places in an expression (mathematics), expressi ...
and a
subformula In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. A formal language can be ...
specifying a property of the referent of that variable. The mostly commonly used quantifiers are \forall and \exists. These quantifiers are standardly defined as
dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...
s; in
classical logic Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy. Characteristics Each logical system in this class ...
, they are interdefinable using
negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
. They can also be used to define more complex quantifiers, as in the formula \neg \exists x P(x) which expresses that nothing has the property P. Other quantifiers are only definable within
second order logic In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of Propositional calculus, propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-ord ...
or
higher order logic mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and, sometimes, stronger semantics. Higher-order logics with their standard semantics are more express ...
s. Quantifiers have been generalized beginning with the work of Mostowski and Lindström. In a first-order logic statement, quantifications in the same type (either universal quantifications or existential quantifications) can be exchanged without changing the meaning of the statement, while the exchange of quantifications in different types changes the meaning. As an example, the only difference in the definition of
uniform continuity In mathematics, a real function f of real numbers is said to be uniformly continuous if there is a positive real number \delta such that function values over any function domain interval of the size \delta are as close to each other as we want. In ...
and (ordinary) continuity is the order of quantifications. First order quantifiers approximate the meanings of some
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
quantifiers such as "some" and "all". However, many natural language quantifiers can only be analyzed in terms of
generalized quantifier In formal semantics, a generalized quantifier (GQ) is an expression that denotes a set of sets. This is the standard semantics assigned to quantified noun phrases. For example, the generalized quantifier ''every boy'' denotes the set of sets of ...
s.


Relations to logical conjunction and disjunction

For a finite domain of discourse D = \, the universally quantified formula \forall x \in D \; P(x) is equivalent to the
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents this ...
P(a_1) \land ... \land P(a_n). Dually, the existentially quantified formula \exists x \in D \; P(x) is equivalent to the
logical disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
P(a_1) \lor ... \lor P(a_n). For example, if B = \ is the set of
binary digit Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...
s, the formula \forall x \in B \; x = x^2 abbreviates 0 = 0^2 \land 1 = 1^2, which evaluates to ''true''.


Infinite domain of discourse

Consider the following statement (''using dot notation for multiplication''): : 1 · 2 = 1 + 1, and 2 · 2 = 2 + 2, and 3 · 2 = 3 + 3, ..., and 100 · 2 = 100 + 100, and ..., etc. This has the appearance of an ''infinite
conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...
'' of propositions. From the point of view of
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
s, this is immediately a problem, since
syntax In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituency) ...
rules are expected to generate
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...
words. The example above is fortunate in that there is a procedure to generate all the conjuncts. However, if an assertion were to be made about every
irrational number In mathematics, the irrational numbers (from in- prefix assimilated to ir- (negative prefix, privative) + rational) are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two integ ...
, there would be no way to enumerate all the conjuncts, since irrationals cannot be enumerated. A succinct, equivalent formulation which avoids these problems uses ''universal quantification'': : For each
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
''n'', ''n'' · 2 = ''n'' + ''n''. A similar analysis applies to the
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
, : 1 is equal to 5 + 5, or 2 is equal to 5 + 5, or 3 is equal to 5 + 5, ... , or 100 is equal to 5 + 5, or ..., etc. which can be rephrased using ''existential quantification'': : For some
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
''n'', ''n'' is equal to 5+5.


Algebraic approaches to quantification

It is possible to devise
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
s whose
models A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
include
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
s with quantification, but progress has been slow and interest in such algebra has been limited. Three approaches have been devised to date: *
Relation algebra In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2''X''² of all binary relations ...
, invented by Augustus De Morgan, and developed by
Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
, Ernst Schröder,
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
, and Tarski's students. Relation algebra cannot represent any formula with quantifiers nested more than three deep. Surprisingly, the models of relation algebra include the
axiomatic set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
ZFC and
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
; *
Cylindric algebra In mathematics, the notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Cylindric algebra ...
, devised by
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
,
Leon Henkin Leon Albert Henkin (April 19, 1921, Brooklyn, New York - November 1, 2006, Oakland, California) was an American logician, whose works played a strong role in the development of logic, particularly in the theory of types. He was an active scholar ...
, and others; * The
polyadic algebra Polyadic algebras (more recently called Halmos algebras) are algebraic structures introduced by Paul Halmos. They are related to first-order logic analogous to the relationship between Boolean algebras and propositional logic (see Lindenbaum–Tar ...
of
Paul Halmos Paul Richard Halmos ( hu, Halmos Pál; March 3, 1916 – October 2, 2006) was a Hungarian-born American mathematician and statistician who made fundamental advances in the areas of mathematical logic, probability theory, statistics, operator ...
.


Notation

The two most common quantifiers are the universal quantifier and the existential quantifier. The traditional symbol for the universal quantifier is "
∀ A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula. ...
", a rotated letter " A", which stands for "for all" or "all". The corresponding symbol for the existential quantifier is " ∃", a rotated letter " E", which stands for "there exists" or "exists". An example of translating a quantified statement in a natural language such as English would be as follows. Given the statement, "Each of Peter's friends either likes to dance or likes to go to the beach (or both)", key aspects can be identified and rewritten using symbols including quantifiers. So, let ''X'' be the set of all Peter's friends, ''P''(''x'') the
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
"''x'' likes to dance", and ''Q''(''x'') the predicate "''x'' likes to go to the beach". Then the above sentence can be written in formal notation as \forallX, (P(x) \lor Q(x)) , which is read, "for every ''x'' that is a member of ''X'', ''P'' applies to ''x'' or ''Q'' applies to ''x''". Some other quantified expressions are constructed as follows, : \exists\, P     \forall\, P for a formula ''P''. These two expressions (using the definitions above) are read as "there exists a friend of Peter who likes to dance" and "all friends of Peter like to dance", respectively. Variant notations include, for set ''X'' and set members ''x'': : \bigvee_ P     (\exists) P     (\exists x \ . \ P)     \exists x \ \cdot \ P     (\exists x : P)     \exists(P)     \exists_\, P     \exists\, P     \existsX \, P     \exists\, xX \, P All of these variations also apply to universal quantification. Other variations for the universal quantifier are : \bigwedge_ P     \bigwedge x P     (x) \, P Some versions of the notation explicitly mention the range of quantification. The range of quantification must always be specified; 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 In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as ...
, * 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
statically typed In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
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). One can use any variable as a quantified variable in place of any other, under certain restrictions in which ''variable capture'' does not occur. Even if the notation uses typed variables, variables of that type may be used. Informally or in natural language, the "∀''x''" or "∃''x''" might appear after or in the middle of ''P''(''x''). Formally, however, the phrase that introduces the dummy variable is placed in front. Mathematical formulas mix symbolic expressions for quantifiers with natural language quantifiers such as, : For every natural number ''x'', ... : There exists an ''x'' such that ... : For at least one ''x, ....'' Keywords for
uniqueness quantification In mathematics and logic, the term "uniqueness" refers to the property of being the one and only object satisfying a certain condition. This sort of quantification is known as uniqueness quantification or unique existential quantification, and ...
include: : For exactly one natural number ''x'', ... : There is one and only one ''x'' such that .... Further, ''x'' may be replaced by a
pronoun In linguistics and grammar, a pronoun (abbreviated ) is a word or a group of words that one may substitute for a noun or noun phrase. Pronouns have traditionally been regarded as one of the parts of speech, but some modern theorists would not co ...
. For example, :For every natural number, its product with 2 equals to its sum with itself. :Some natural number is prime.


Order of quantifiers (nesting)

The order of quantifiers is critical to meaning, as is illustrated by the following two propositions: :For every natural number ''n'', there exists a natural number ''s'' such that ''s'' = ''n''2. This is clearly true; it just asserts that every natural number has a square. The meaning of the assertion in which the order of quantifiers is inversed is different: :There exists a natural number ''s'' such that for every natural number ''n'', ''s'' = ''n''2. This is clearly false; it asserts that there is a single natural number ''s'' that is the square of ''every'' natural number. This is because the syntax directs that any variable cannot be a function of subsequently introduced variables. A less trivial example from
mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series (m ...
are the concepts of
uniform A uniform is a variety of clothing worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, se ...
and
pointwise In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined ...
continuity, whose definitions differ only by an exchange in the positions of two quantifiers. A function ''f'' from R to R is called * Pointwise continuous if \forall \varepsilon > 0 \; \forall x \in \R \; \exists \delta > 0 \; \forall h \in \R \; (, h, < \delta \, \Rightarrow \, , f(x) - f(x + h), < \varepsilon ) * Uniformly continuous if \forall \varepsilon > 0 \; \exists \delta > 0 \; \forall x \in \R \; \forall h \in \R \; (, h, < \delta \, \Rightarrow \, , f(x) - f(x + h), < \varepsilon ) In the former case, the particular value chosen for ''δ'' can be a function of both ''ε'' and ''x'', the variables that precede it. In the latter case, ''δ'' can be a function only of ''ε'' (i.e., it has to be chosen independent of ''x''). For example, ''f''(''x'') = ''x''2 satisfies pointwise, but not uniform continuity (its slope is unbound). In contrast, interchanging the two initial universal quantifiers in the definition of pointwise continuity does not change the meaning. As a general rule, swapping two adjacent universal quantifiers with the same
scope Scope or scopes may refer to: People with the surname * Jamie Scope (born 1986), English footballer * John T. Scopes (1900–1970), central figure in the Scopes Trial regarding the teaching of evolution Arts, media, and entertainment * Cinem ...
(or swapping two adjacent existential quantifiers with the same scope) doesn't change the meaning of the formula (see Example here), but swapping an existential quantifier and an adjacent universal quantifier may change its meaning. The maximum depth of nesting of quantifiers in a formula is called its "
quantifier rank In mathematical logic, the quantifier rank of a formula is the depth of nesting of its quantifiers. It plays an essential role in model theory. Notice that the quantifier rank is a property of the formula itself (i.e. the expression in a langu ...
".


Equivalent expressions

If ''D'' is a domain of ''x'' and ''P''(''x'') is a predicate dependent on object variable ''x'', then the universal proposition can be expressed as :\forall x\!\in\!D\; P(x). This notation is known as restricted or relativized or
bounded quantification In type theory, bounded quantification (also bounded polymorphism or constrained genericity) refers to universal or existential quantifiers which are restricted ("bounded") to range only over the subtypes of a particular type. Bounded quantificati ...
. Equivalently one can write, :\forall x\;(x\!\in\!D \to P(x)). The existential proposition can be expressed with bounded quantification as :\exists x\!\in\!D\; P(x), or equivalently :\exists x\;(x\!\in\!\!D \land P(x)). Together with negation, only one of either the universal or existential quantifier is needed to perform both tasks: :\neg (\forall x\!\in\!D\; P(x)) \equiv \exists x\!\in\!D\; \neg P(x), which shows that to disprove a "for all ''x''" proposition, one needs no more than to find an ''x'' for which the predicate is false. Similarly, :\neg (\exists x\!\in\!D\; P(x)) \equiv \forall x\!\in\!D\; \neg P(x), to disprove a "there exists an ''x''" proposition, one needs to show that the predicate is false for all ''x''. In
classical logic Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy. Characteristics Each logical system in this class ...
, every formula is
logically equivalent Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
to a formula in
prenex normal form A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propos ...
, that is, a string of quantifiers and bound variables followed by a quantifier-free formula.


Range of quantification

Every quantification involves one specific variable and a
domain of discourse In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range. Overview The domain ...
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, say, asserting that a predicate holds for some natural number or for some
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
. 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 universally quantified formula over an empty range (like \forall x\!\in\!\varnothing\; x \neq x) is always
vacuously true In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "she ...
. Conversely, an existentially quantified formula over an empty range (like \exists x\!\in\!\varnothing\; x = x) is always false. 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 In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...
''n'', ''n'' is prime. In some mathematical theories, a single domain of discourse fixed in advance is assumed. For example, in
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as ...
, 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 every natural number ''n'', ''n''·2 = ''n'' + ''n'' in Zermelo–Fraenkel set theory, one would write :For every ''n'', if ''n'' belongs to N, then ''n''·2 = ''n'' + ''n'', where N is the set of all natural numbers.


Formal semantics

Mathematical semantics is the application of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
to study the meaning of expressions in a formal language. It has three elements: a mathematical specification of a class of objects via
syntax In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituency) ...
, a mathematical specification of various
semantic domain A semantic domain is a specific place that shares a set of meanings, or a language that holds its meaning, within the given context of the place. Harriet Ottenheimer (2006), a writer in Linguistic Anthropology, defines a semantic domain as a “spe ...
s and the relation between the two, which is usually expressed as a function from syntactic objects to semantic ones. This article only addresses the issue of how quantifier elements are interpreted. The syntax of a formula can be given by a syntax tree. A quantifier has a
scope Scope or scopes may refer to: People with the surname * Jamie Scope (born 1986), English footballer * John T. Scopes (1900–1970), central figure in the Scopes Trial regarding the teaching of evolution Arts, media, and entertainment * Cinem ...
, and an occurrence of a variable ''x'' is
free Free may refer to: Concept * Freedom, having the ability to do something, without having to obey anyone/anything * Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism * Emancipate, to procur ...
if it is not within the scope of a quantification for that variable. Thus in : \forall x (\exists y B(x,y)) \vee C(y,x) the occurrence of both ''x'' and ''y'' in ''C''(''y'', ''x'') is free, while the occurrence of ''x'' and ''y'' in ''B''(''y'', ''x'') is bound (i.e. non-free). An interpretation for
first-order predicate calculus First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
assumes as given a domain of individuals ''X''. A formula ''A'' whose free variables are ''x''1, ..., ''x''n is interpreted as a boolean-valued function ''F''(''v''1, ..., ''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 : \forall x_n A(x_1, \ldots , x_n) is the function ''G'' of ''n''-1 arguments such that ''G''(''v''1, ..., ''v''''n''-1) = T if and only if ''F''(''v''1, ..., ''v''''n''-1, ''w'') = T for every ''w'' in ''X''. If ''F''(''v''1, ..., ''v''''n''-1, ''w'') = F for at least one value of ''w'', then ''G''(''v''1, ..., ''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''1, ..., ''v''''n''-1) = T if and only if ''F''(''v''1, ..., ''v''''n''-1, ''w'') = T for at least one ''w'' and ''H''(''v''1, ..., ''v''''n''-1) = F otherwise. The semantics for
uniqueness quantification In mathematics and logic, the term "uniqueness" refers to the property of being the one and only object satisfying a certain condition. This sort of quantification is known as uniqueness quantification or unique existential quantification, and ...
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) : \forall y,z \big( A(x_1, \ldots ,x_, y) \wedge A(x_1, \ldots ,x_, z) \implies y = z \big). Each kind of quantification defines a corresponding
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are dete ...
on the set of formulas, by adding, for each free variable ''x'', a quantifier to bind ''x''. For example, the ''existential closure'' of the
open formula An open formula is a formula that contains at least one free variable. An open formula does not have a truth value assigned to it, in contrast with a closed formula which constitutes a proposition and thus can have a truth value like ''true'' or ' ...
''n''>2 ∧ ''x''''n''+''y''''n''=''z''''n'' is the closed formula ∃''n'' ∃''x'' ∃''y'' ∃''z'' (''n''>2 ∧ ''x''''n''+''y''''n''=''z''''n''); the latter formula, when interpreted over the natural numbers, is known to be false by
Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been k ...
. As another example, equational axioms, like ''x''+''y''=''y''+''x'', are usually meant to denote their ''universal closure'', like ∀''x'' ∀''y'' (''x''+''y''=''y''+''x'') to express
commutativity In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
.


Paucal, multal and other degree quantifiers

None of the quantifiers previously discussed apply to a quantification such as :There are many integers ''n'' < 100, such that ''n'' is divisible by 2 or 3 or 5. One possible interpretation mechanism can be obtained as follows: Suppose that in addition to a semantic domain ''X'', we have given a
probability measure In mathematics, a probability measure is a real-valued function defined on a set of events in a probability space that satisfies measure properties such as ''countable additivity''. The difference between a probability measure and the more gener ...
P defined on ''X'' and cutoff numbers 0 < ''a'' ≤ ''b'' ≤ 1. If ''A'' is a formula with free variables ''x''1,...,''x''''n'' whose interpretation is the function ''F'' of variables ''v''1,...,''v''''n'' then the interpretation of : \exists^ x_n A(x_1, \ldots, x_, x_n) is the function of ''v''1,...,''v''''n''-1 which is T if and only if : \operatorname \ \geq b and F otherwise. Similarly, the interpretation of : \exists^ x_n A(x_1, \ldots, x_, x_n) is the function of ''v''1,...,''v''''n''-1 which is F if and only if : 0< \operatorname \ \leq a and T otherwise.


Other quantifiers

A few other quantifiers have been proposed over time. In particular, the solution quantifier, noted § (
section sign The section sign, §, is a typographical character for referencing individually numbered sections of a document; it is frequently used when citing sections of a legal code. It is also known as the section symbol, section mark, double-s, or silc ...
) and read "those". For example, : \left \S n \in \mathbb \quad n^2 \leq 4 \right= \ is read "those ''n'' in N such that ''n''2 ≤ 4 are in ." The same construct is expressible in
set-builder notation In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy. Defining ...
as :\ = \. Contrary to the other quantifiers, § yields a set rather than a formula. Some other quantifiers sometimes used in mathematics include: *There are infinitely many elements such that... *For all but finitely many elements... (sometimes expressed as "for
almost all In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
elements..."). *There are uncountably many elements such that... *For all but countably many elements... *For all elements in a set of positive measure... *For all elements except those in a set of measure zero...


History

Term logic In philosophy, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further in ancient history mostly by his followers, th ...
, also called Aristotelian logic, treats quantification in a manner that is closer to natural language, and also less suited to formal analysis. Term logic treated ''All'', ''Some'' and ''No'' in the 4th century BC, in an account also touching on the
alethic modalities Alethic modality (from Greek ἀλήθεια = truth) is a linguistic modality that indicates modalities of truth, in particular the modalities of logical necessity, contingency, possibility and impossibility. Alethic modality is often associated ...
. In 1827,
George Bentham George Bentham (22 September 1800 – 10 September 1884) was an English botanist, described by the weed botanist Duane Isely as "the premier systematic botanist of the nineteenth century". Born into a distinguished family, he initially studi ...
published his ''Outline of a new system of logic, with a critical examination of Dr Whately's Elements of Logic'', describing the principle of the quantifier, but the book was not widely circulated. William Hamilton claimed to have coined the terms "quantify" and "quantification", most likely in his Edinburgh lectures c. 1840. Augustus De Morgan confirmed this in 1847, but modern usage began with De Morgan in 1862 where he makes statements such as "We are to take in both ''all'' and ''some-not-all'' as quantifiers".
Gottlob Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic phil ...
, in his 1879 ''
Begriffsschrift ''Begriffsschrift'' (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book. ''Begriffsschrift'' is usually translated as ''concept writing'' or ''concept notatio ...
'', was the first to employ a quantifier to bind a variable ranging over a
domain of discourse In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range. Overview The domain ...
and appearing in
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
s. He would universally quantify a variable (or relation) by writing the variable over a dimple in an otherwise straight line appearing in his diagrammatic formulas. Frege did not devise an explicit notation for existential quantification, instead employing his equivalent of ~∀''x''~, or
contraposition In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as Proof by contrapositive, proof by contraposition. The cont ...
. Frege's treatment of quantification went largely unremarked until
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...
's 1903 ''Principles of Mathematics''. In work that culminated in Peirce (1885),
Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
and his student
Oscar Howard Mitchell Oscar, OSCAR, or The Oscar may refer to: People * Oscar (given name), an Irish- and English-language name also used in other languages; the article includes the names Oskar, Oskari, Oszkár, Óscar, and other forms. * Oscar (Irish mythology) ...
independently invented universal and existential quantifiers, and
bound variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a Mathematical notation, notation (symbol) that specifies places in an expression (mathematics), expressi ...
s. Peirce and Mitchell wrote Πx and Σx where we now write ∀''x'' and ∃''x''. Peirce's notation can be found in the writings of Ernst Schröder,
Leopold Loewenheim Leopold may refer to: People * Leopold (given name) * Leopold (surname) Arts, entertainment, and media Fictional characters * Leopold (''The Simpsons''), Superintendent Chalmers' assistant on ''The Simpsons'' * Leopold Bloom, the protagonist o ...
,
Thoralf Skolem Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory. Life Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skolem ...
, and Polish logicians into the 1950s. Most notably, it is the notation of
Kurt Gödel Kurt Friedrich Gödel ( , ; April 28, 1906 â€“ January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
's landmark 1930 paper on the completeness of
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
, and 1931 paper on the incompleteness of
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
. Peirce's approach to quantification also influenced
William Ernest Johnson William Ernest Johnson, FBA (23 June 1858 – 14 January 1931), usually cited as W. E. Johnson, was a British philosopher, logician and economic theorist.Zabell, S.L. (2008"Johnson, William Ernest (1858–1931)"In: Durlauf S.N., Blume L.E. (e ...
and
Giuseppe Peano Giuseppe Peano (; ; 27 August 1858 – 20 April 1932) was an Italian mathematician and glottologist. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The stand ...
, who invented yet another notation, namely (''x'') for the universal quantification of ''x'' and (in 1897) ∃''x'' for the existential quantification of ''x''. Hence for decades, the canonical notation in philosophy and mathematical logic was (''x'')''P'' to express "all individuals in the domain of discourse have the property ''P''," and "(∃''x'')''P''" for "there exists at least one individual in the domain of discourse having the property ''P''." Peano, who was much better known than Peirce, in effect diffused the latter's thinking throughout Europe. Peano's notation was adopted by the ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'' of Whitehead and Russell, Quine, and
Alonzo Church Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scienc ...
. In 1935,
Gentzen Gerhard Karl Erich Gentzen (24 November 1909 – 4 August 1945) was a German mathematician and logician. He made major contributions to the foundations of mathematics, proof theory, especially on natural deduction and sequent calculus. He died o ...
introduced the ∀ symbol, by analogy with Peano's ∃ symbol. ∀ did not become canonical until the 1960s. Around 1895, Peirce began developing his
existential graph An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on logical graph, graphical logic as early as 1882,Peirce, C. S., " n Junctures and Fractures in Logic (ed ...
s, whose variables can be seen as tacitly quantified. Whether the shallowest instance of a variable is even or odd determines whether that variable's quantification is universal or existential. (Shallowness is the contrary of depth, which is determined by the nesting of negations.) Peirce's graphical logic has attracted some attention in recent years by those researching
heterogeneous reasoning Homogeneity and heterogeneity are concepts often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, siz ...
and diagrammatic inference.


See also

*
Absolute generality In philosophical logic, metaphysics, and the philosophy of language, the problem of absolute generality is the problem of referring to absolutely everything. Historically, philosophers have assumed that some of their statements are absolutely gener ...
*
Almost all In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
*
Branching quantifier In logic a branching quantifier, also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering :\langle Qx_1\dots Qx_n\rangle of quantifiers for ''Q'' âˆˆ . It is a special case ...
*
Conditional quantifier In logic, a conditional quantifier is a kind of Lindström quantifier (or generalized quantifier) ''Q'A'' that, relative to a classical model ''A'', satisfies some or all of the following conditions ("''X''" and "''Y''" range over arbitrary formu ...
*
Counting quantification A counting quantifier is a mathematical term for a quantifier of the form "there exists at least ''k'' elements that satisfy property ''X''". In first-order logic with equality, counting quantifiers can be defined in terms of ordinary quantifiers, ...
*
Eventually (mathematics) In the mathematical areas of number theory and analysis, an infinite sequence or a function is said to eventually have a certain property, if it doesn't have the said property across all its ordered instances, but will after some instances have pas ...
*
Generalized quantifier In formal semantics, a generalized quantifier (GQ) is an expression that denotes a set of sets. This is the standard semantics assigned to quantified noun phrases. For example, the generalized quantifier ''every boy'' denotes the set of sets of ...
— a higher-order property used as standard semantics of quantified
noun phrases In linguistics, a noun phrase, or nominal (phrase), is a phrase that has a noun or pronoun as its head or performs the same grammatical function as a noun. Noun phrases are very common cross-linguistically, and they may be the most frequently occ ...
*
Lindström quantifier In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier. Lindström quantifiers generalize first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers. They were ...
— a generalized polyadic quantifier *
Quantifier elimination Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that \ldots" can be viewed as a question "When is there an x such t ...
*
Quantifier shift A quantifier shift is a logical fallacy in which the quantifiers of a statement are erroneously transposed during the rewriting process. The change in the logical nature of the statement may not be obvious when it is stated in a natural language ...


References


Bibliography

* Barwise, Jon; and Etchemendy, John, 2000. ''Language Proof and Logic''. CSLI (University of Chicago Press) and New York: Seven Bridges Press. A gentle introduction to
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
by two first-rate logicians. * Frege, Gottlob, 1879. ''
Begriffsschrift ''Begriffsschrift'' (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book. ''Begriffsschrift'' is usually translated as ''concept writing'' or ''concept notatio ...
''. Translated in
Jean van Heijenoort Jean Louis Maxime van Heijenoort (; July 23, 1912 – March 29, 1986) was a historian of mathematical logic. He was also a personal secretary to Leon Trotsky from 1932 to 1939, and an American Trotskyist until 1947. Life Van Heijenoort was born ...
, 1967. ''From Frege to Gödel: A Source Book on Mathematical Logic, 1879-1931''. Harvard University Press. The first appearance of quantification. * Hilbert, David; and Ackermann, Wilhelm, 1950 (1928). '' Principles of Mathematical Logic''. Chelsea. Translation of ''Grundzüge der theoretischen Logik''. Springer-Verlag. The 1928 first edition is the first time quantification was consciously employed in the now-standard manner, namely as binding variables ranging over some fixed domain of discourse. This is the defining aspect of
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
. * Peirce, C. S., 1885, "On the Algebra of Logic: A Contribution to the Philosophy of Notation, ''American Journal of Mathematics'', Vol. 7, pp. 180–202. Reprinted in Kloesel, N. ''et al.'', eds., 1993. ''Writings of C. S. Peirce, Vol. 5''. Indiana University Press. The first appearance of quantification in anything like its present form. * Reichenbach, Hans, 1975 (1947). ''Elements of Symbolic Logic'', Dover Publications. The quantifiers are discussed in chapters §18 "Binding of variables" through §30 "Derivations from Synthetic Premises". * Westerståhl, Dag, 2001, "Quantifiers," in Goble, Lou, ed., ''The Blackwell Guide to Philosophical Logic''. Blackwell. * Wiese, Heike, 2003. ''Numbers, language, and the human mind''. Cambridge University Press. .


External links

* * . From College of Natural Sciences,
University of Hawaii at Manoa A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United States, t ...
. *
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by Stanford University. Eac ...
: ** Shapiro, Stewart (2000)
"Classical Logic"
(Covers syntax, model theory, and metatheory for first order logic in the natural deduction style.) ** Westerståhl, Dag (2005)
"Generalized quantifiers"
* Peters, Stanley; Westerståhl, Dag (2002)
"Quantifiers"
{{Authority control Logic Predicate logic Quantifier (logic) Philosophical logic Semantics