FACTOID # 18: Alaska spends more money per capita on elementary and secondary education than any other state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Universal quantification

In predicate logic, universal quantification is an attempt to formalize the notion that something (a logical predicate) is true for everything, or every relevant thing. The resulting statement is a universally quantified statement, and we have universally quantified over the predicate. In symbolic logic, the universal quantifier (typically "∀") is the symbol used to denote universal quantification, and is often informally read as "given any" or "for all". ... In the jargon of the new mathematics of the 1960s, an open sentence is a sentence in which there are specific numbers which, when used to replace the variables, will allow the resulting expression to evaluate to true. ... Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ...


Quantification in general is covered in the article on quantification, while this article discusses universal quantification specifically. 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. ...


Compare this with existential quantification, which says that something is true for at least one thing. In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. ...

Contents

Basics

Suppose you wish to say

2·0 = 0 + 0, and 2·1 = 1 + 1, and 2·2 = 2 + 2, etc.

This would seem to be a logical conjunction because of the repeated use of "and." But the "etc" can't be interpreted as a conjunction in formal logic. Instead, rephrase the statement as AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ... Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ...

For any natural number n, 2·n = n + n.

This is a single statement using universal quantification.


Notice that this statement is really more precise than the original one. It may seem obvious that the phrase "etc" is meant to include all natural numbers, and nothing more, but this wasn't explicitly stated, which is essentially the reason that the phrase couldn't be interpreted formally. In the universal quantification, on the other hand, the natural numbers are mentioned explicitly. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...


This particular example is true, because you could put any natural number in for n and the statement "2·n = n + n" would be true. In contrast, "For any natural number n, 2·n > 2 + n" is false, because if you replace n with, say, 1 you get the false statement "2·1 > 2 + 1". It doesn't matter 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. Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ... Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ... In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule, i. ...


On the other hand, "For any composite number n, 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 is allowed to take. Further information on using domains of discourse with quantified statements can be found in the Quantification article. But in particular, note that if you wish to restrict the domain of discourse to consist only of those objects that satisfy a certain predicate, then for universal quantification, you do this with a logical conditional. For example, "For any composite number n, 2·n > 2 + n" is logically equivalent to "For any natural number n, if n is composite, then 2·n > 2 + n". Here the "if ... then" construction indicates the logical conditional. A composite number is a positive integer which has a positive divisor other than one or itself. ... The domain of discourse, sometimes called the universe of discourse, is an analytic tool used in deductive logic, especially predicate logic. ... 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. ... In propositional calculus, or logical calculus in mathematics, the logical conditional is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ... In logic, statements p and q are logically equivalent if they have the same logical content. ...


In symbolic logic, we use the universal quantifier "∀" (an upside-down letter "A" in a sans-serif font) to indicate universal quantification. Thus if P(n) is the predicate "2·n > 2 + n" and N is the set of natural numbers, then Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... Look up A, a in Wiktionary, the free dictionary. ... In typography, serifs are the small features at the end of strokes within letters. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...

forall{n}{in}mathbf{N}, P(n)

is the (false) statement

For any natural number n, 2·n > 2 + n.

Similarly, if Q(n) is the predicate "n is composite", then

forall{n}{in}mathbf{N}, Q(n);!;! {rightarrow};!;! P(n)

is the (true) statement

For any composite number n, 2·n > 2 + n.

Several variations in the notation for quantification (which apply to all forms) can be found in the quantification article. But there is a special notation used only for universal quantification, which we also give here: 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. ...

(n{in}mathbf{N}), P(n)

The parentheses indicate universal quantification by default.


Properties

Negation

Note that a quantified propositional function is a statement; thus, like statements, quantified functions can be negated. The notation mathematicians and logicians utilize to denote negation is: lnot.


For example, let P(x) be the propositional function "x is married"; then, for a Universe of Discourse X of all living human beings, consider the universal quantification "Given any living person x, that person is married":

forall{x}{in}mathbf{X}, P(x)

A few second's thought demonstrates this as irrevocably false; then, truthfully, we may say, "It is not the case that, given any living person x, that person is married", or, symbolically:

lnot forall{x}{in}mathbf{X}, P(x).

Take a moment and consider what, exactly, negating the universal quantifier means: if the statement is not true for every element of the Universe of Discourse, then there must be at least one element for which the statement is false. That is, the negation of ∀x P(x) is logically equivalent to "There exists a living person x such that he is not married", or:

exists{x}{in}mathbf{X}, lnot P(x)

Generally, then, the negation of a propositional function's universal quantification is an existential quantification of that propositional function's negation; symbolically, In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. ...

lnot forall{x}{in}mathbf{X}, P(x) equiv exists{x}{in}mathbf{X}, lnot P(x)

A common error is writing "all persons are not married" (i.e. "there exists no person who is married") when one means "not all persons are married" (i.e. "there exists a person who is not married"):

lnot exists{x}{in}mathbf{X}, P(X) equiv forall{x}{in}mathbf{X}, lnot P(x) notequiv lnot forall{x}{in}mathbf{X}, P(x) equiv exists{x}{in}mathbf{X}, lnot P(x)

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. In logic, especially in mathematical logic, a rule of inference is a scheme for constructing valid inferences. ...


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 In logic Universal instantiation (UI) is an inference from a truth about each member of a class of individuals to the truth about a particular individual of that class. ...

forall{x}{in}mathbf{X}, P(x) to P(c)

where c is a completely arbitrary element of the Universe of Discourse.


Universal generalization 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, Generalization is an inference rule of Predicate Calculus which states that: If is true (valid) then so is . ...

P(c) to forall{x}{in}mathbf{X}, P(x)

It is especially important to note 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.


See also

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. ... First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ...

Reference

  • Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0. 

  Results from FactBites:
 
Universal quantification (1057 words)
In predicate logic and technical fields that depend on it, universal quantification is an attempt to formalise the notion of something being true for all things, or all things of a certain type.
In our example, the universe of discourse was originally the set of natural numbers; later we changed it to the set of even prime numbers.
It's not necessary for the universe of discourse to be a set in terms of formal set theory, and universal quantification can be used in logical theories that don't make any reference to sets.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m