HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, 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 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 ...
can be satisfied by every
member Member may refer to: * Military jury, referred to as "Members" in military jargon * Element (mathematics), an object that belongs to a mathematical set * In object-oriented programming, a member of a class ** Field (computer science), entries in ...
of a domain of discourse. In other words, it is the predication of a
property Property is a system of rights that gives people legal control of valuable things, and also refers to the valuable things themselves. Depending on the nature of the property, an owner of property may have the right to consume, alter, share, r ...
or relation to every member of the domain. It asserts that a predicate within the
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 * Cinema ...
of a universal quantifier is true of every
value Value or values may refer to: Ethics and social * Value (ethics) wherein said concept may be construed as treating actions themselves as abstract objects, associating value to them ** Values (Western philosophy) expands the notion of value beyo ...
of a predicate variable. It is usually denoted by the turned A (∀) logical operator symbol, which, when used together with a predicate variable, is called a universal quantifier ("", "", or sometimes by "" alone). Universal quantification is distinct from ''existential'' quantification ("there exists"), which only asserts that the property or relation holds for at least one member of the domain. Quantification in general is covered in the article on quantification (logic). The universal quantifier is encoded as in
Unicode Unicode, formally The Unicode Standard,The formal version reference is is an information technology standard for the consistent encoding, representation, and handling of text expressed in most of the world's writing systems. The standard, ...
, and as \forall in LaTeX and related formula editors.


Basics

Suppose it is given that
2·0 = 0 + 0, and 2·1 = 1 + 1, and , etc.
This would seem to be a
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 thi ...
because of the repeated use of "and". However, the "etc." cannot be interpreted as a conjunction in formal logic. Instead, the statement must be rephrased:
For all natural numbers ''n'', one has 2·''n'' = ''n'' + ''n''.
This is a single statement using universal quantification. This statement can be said to be more precise than the original one. While the "etc." informally includes
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 ...
s, and nothing more, this was not rigorously given. In the universal quantification, on the other hand, the natural numbers are mentioned explicitly. This particular example is true, because any natural number could be substituted for ''n'' and the statement "2·''n'' = ''n'' + ''n''" would be true. In contrast,
For all natural numbers ''n'', one has 2·''n'' > 2 + ''n''
is false, because if ''n'' is substituted with, for instance, 1, the statement "2·1 > 2 + 1" is false. It is immaterial that "2·''n'' > 2 + ''n''" is true for ''most'' natural numbers ''n'': even the existence of a single counterexample is enough to prove the universal quantification false. On the other hand, for all
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor In mathematics, a divisor of an integer n, also called a factor ...
s ''n'', one has 2·''n'' > 2 + ''n'' is true, because none of the counterexamples are composite numbers. This indicates the importance of the '' domain of discourse'', which specifies which values ''n'' can take.Further information on using domains of discourse with quantified statements can be found in the Quantification (logic) article. In particular, note that if the domain of discourse is restricted to consist only of those objects that satisfy a certain predicate, then for universal quantification this requires a logical conditional. For example,
For all composite numbers ''n'', one has 2·''n'' > 2 + ''n''
is logically equivalent to
For all natural numbers ''n'', if ''n'' is composite, then 2·''n'' > 2 + ''n''.
Here the "if ... then" construction indicates the logical conditional.


Notation

In
symbolic logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
, the universal quantifier symbol \forall (a turned " A" in a sans-serif font, Unicode U+2200) is used to indicate universal quantification. It was first used in this way by Gerhard Gentzen in 1935, by analogy with Giuseppe Peano's \exists (turned E) notation for
existential quantification 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, ...
and the later use of Peano's notation by
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, a ...
. For example, if ''P''(''n'') is the predicate "2·''n'' > 2 + ''n''" and N is the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of natural numbers, then : \forall n\!\in\!\mathbb\; P(n) is the (false) statement :"for all natural numbers ''n'', one has 2·''n'' > 2 + ''n''". Similarly, if ''Q''(''n'') is the predicate "''n'' is composite", then : \forall n\!\in\!\mathbb\; \bigl( Q(n) \rightarrow P(n) \bigr) is the (true) statement :"for all natural numbers ''n'', if ''n'' is composite, then ". Several variations in the notation for quantification (which apply to all forms) can be found in the '' Quantifier'' article.


Properties


Negation

The negation of a universally quantified function is obtained by changing the universal quantifier into an existential quantifier and negating the quantified formula. That is, :\lnot \forall x\; P(x)\quad\text \quad \exists x\;\lnot P(x) where \lnot denotes negation. For example, if is the propositional function " is married", then, for the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of all living human beings, the universal quantification
Given any living person , that person is married
is written :\forall x \in X\, P(x) This statement is false. Truthfully, it is stated that
It is not the case that, given any living person , that person is married
or, symbolically: :\lnot\ \forall x \in X\, P(x). If the function is not true for ''every'' element of , then there must be at least one element for which the statement is false. That is, the negation of \forall x \in X\, P(x) is logically equivalent to "There exists a living person who is not married", or: :\exists x \in X\, \lnot P(x) It is erroneous to confuse "all persons are not married" (i.e. "there exists no person who is married") with "not all persons are married" (i.e. "there exists a person who is not married"): :\lnot\ \exists x \in X\, P(x) \equiv\ \forall x \in X\, \lnot P(x) \not\equiv\ \lnot\ \forall x\in X\, P(x) \equiv\ \exists x \in X\, \lnot P(x)


Other connectives

The universal (and existential) quantifier moves unchanged across the
logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
s , , , and , as long as the other operand is not affected; that is: :\begin P(x) \land (\exists\mathbf\, Q(y)) &\equiv\ \exists\mathbf\, (P(x) \land Q(y)) \\ P(x) \lor (\exists\mathbf\, Q(y)) &\equiv\ \exists\mathbf\, (P(x) \lor Q(y)),& \text \mathbf\neq \emptyset \\ P(x) \to (\exists\mathbf\, Q(y)) &\equiv\ \exists\mathbf\, (P(x) \to Q(y)),& \text \mathbf\neq \emptyset \\ P(x) \nleftarrow (\exists\mathbf\, Q(y)) &\equiv\ \exists\mathbf\, (P(x) \nleftarrow Q(y)) \\ P(x) \land (\forall\mathbf\, Q(y)) &\equiv\ \forall\mathbf\, (P(x) \land Q(y)),& \text \mathbf\neq \emptyset \\ P(x) \lor (\forall\mathbf\, Q(y)) &\equiv\ \forall\mathbf\, (P(x) \lor Q(y)) \\ P(x) \to (\forall\mathbf\, Q(y)) &\equiv\ \forall\mathbf\, (P(x) \to Q(y)) \\ P(x) \nleftarrow (\forall\mathbf\, Q(y)) &\equiv\ \forall\mathbf\, (P(x) \nleftarrow Q(y)),& \text \mathbf\neq \emptyset \end Conversely, for the logical connectives , , , and , the quantifiers flip: :\begin P(x) \uparrow (\exists\mathbf\, Q(y)) & \equiv\ \forall\mathbf\, (P(x) \uparrow Q(y)) \\ P(x) \downarrow (\exists\mathbf\, Q(y)) & \equiv\ \forall\mathbf\, (P(x) \downarrow Q(y)),& \text \mathbf\neq \emptyset \\ P(x) \nrightarrow (\exists\mathbf\, Q(y)) & \equiv\ \forall\mathbf\, (P(x) \nrightarrow Q(y)),& \text \mathbf\neq \emptyset \\ P(x) \gets (\exists\mathbf\, Q(y)) & \equiv\ \forall\mathbf\, (P(x) \gets Q(y)) \\ P(x) \uparrow (\forall\mathbf\, Q(y)) & \equiv\ \exists\mathbf\, (P(x) \uparrow Q(y)),& \text \mathbf\neq \emptyset \\ P(x) \downarrow (\forall\mathbf\, Q(y)) & \equiv\ \exists\mathbf\, (P(x) \downarrow Q(y)) \\ P(x) \nrightarrow (\forall\mathbf\, Q(y)) & \equiv\ \exists\mathbf\, (P(x) \nrightarrow Q(y)) \\ P(x) \gets (\forall\mathbf\, Q(y)) & \equiv\ \exists\mathbf\, (P(x) \gets Q(y)),& \text \mathbf\neq \emptyset \\ \end


Rules of inference

A rule of inference is a rule justifying a logical step from hypothesis to conclusion. There are several rules of inference which utilize the universal quantifier. '' Universal instantiation'' concludes that, if the propositional function is known to be universally true, then it must be true for any arbitrary element of the universe of discourse. Symbolically, this is represented as : \forall\mathbf\, P(x) \to P(c) where ''c'' is a completely arbitrary element of the universe of discourse. ''
Universal generalization In predicate logic, generalization (also universal generalization or universal introduction,Moore and Parker GEN) is a valid inference rule. It states that if \vdash \!P(x) has been derived, then \vdash \!\forall x \, P(x) can be derived. Gener ...
'' concludes the propositional function must be universally true if it is true for any arbitrary element of the universe of discourse. Symbolically, for an arbitrary ''c'', : P(c) \to\ \forall\mathbf\, P(x). The element ''c'' must be completely arbitrary; else, the logic does not follow: if ''c'' is not arbitrary, and is instead a specific element of the universe of discourse, then P(''c'') only implies an existential quantification of the propositional function.


The empty set

By convention, the formula \forall\emptyset \, P(x) is always true, regardless of the formula ''P''(''x''); see vacuous truth.


Universal closure

The universal closure of a formula φ is the formula with no free variables obtained by adding a universal quantifier for every free variable in φ. For example, the universal closure of :P(y) \land \exists x Q(x,z) is :\forall y \forall z ( P(y) \land \exists x Q(x,z)).


As adjoint

In category theory and the theory of elementary topoi, the universal quantifier can be understood as the right adjoint of a functor between power sets, the inverse image functor of a function between sets; likewise, the existential quantifier is the left adjoint. Saunders Mac Lane, Ieke Moerdijk, (1992) ''Sheaves in Geometry and Logic'' Springer-Verlag. ''See page 58'' For a set X, let \mathcalX denote its powerset. For any function f:X\to Y between sets X and Y, there is an inverse image functor f^*:\mathcalY\to \mathcalX between powersets, that takes subsets of the codomain of ''f'' back to subsets of its domain. The left adjoint of this functor is the existential quantifier \exists_f and the right adjoint is the universal quantifier \forall_f. That is, \exists_f\colon \mathcalX\to \mathcalY is a functor that, for each subset S \subset X, gives the subset \exists_f S \subset Y given by :\exists_f S =\, those y in the image of S under f. Similarly, the universal quantifier \forall_f\colon \mathcalX\to \mathcalY is a functor that, for each subset S \subset X, gives the subset \forall_f S \subset Y given by :\forall_f S =\, those y whose preimage under f is contained in S. The more familiar form of the quantifiers as used in first-order logic is obtained by taking the function ''f'' to be the unique function !:X \to 1 so that \mathcal(1) = \ is the two-element set holding the values true and false, a subset ''S'' is that subset for which 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 ...
S(x) holds, and :\begin\mathcal(!)\colon \mathcal(1) & \to \mathcal(X)\\ T &\mapsto X \\ F &\mapsto \\end :\exists_! S = \exists x. S(x), which is true if S is not empty, and :\forall_! S = \forall x. S(x), which is false if S is not X. The universal and existential quantifiers given above generalize to the presheaf category.


See also

*
Existential quantification 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, ...
* First-order logic * List of logic symbols—for the Unicode symbol ∀


Notes


References

* * (ch. 2)


External links

* {{Mathematical logic Logic symbols Logical expressions Quantifier (logic)