Universal quantification

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".

Quantification in general is covered in the article on quantification, while this article discusses universal quantification specifically.

Compare this with existential quantification, which says that something is true for at least one thing.

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:: For all natural numbers "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.

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 all natural numbers "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.

On the other hand, "For all composite numbers "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. 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 all composite numbers "n", 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.

In symbolic logic, we use the universal quantifier symbol forall (an upside-down letter "A" in a sans-serif font, Unicode 0x2200) to indicate universal quantification. Thus if "P"("n") is the predicate "2·"n" > 2 + "n" and N is the set of natural numbers, then:: forall n!in!mathbf{N}; P(n)

is the (false) statement:: For all natural numbers "n", 2·"n" > 2 + "n".

Similarly, if "Q"("n") is the predicate "n" is composite", then: forall n!in!mathbf{N}; igl( Q(n) ightarrow P(n) igr)

is the (true) statement:: For all natural numbers "n", if "n" is composite, then 2·"n" > 2 + n,

and since "n" is composite" implies that "n" must already be a natural number, we can shorten this statement to the equivalent:: For all composite numbers "n", 2·"n" > 2 + "n".

Several variations in the notation for quantification (which apply to all forms) can be found in the quantification article. There is a special notation used only for universal quantification, which we also give here:: (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 seconds' 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 forall{x}{in}mathbf{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,: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) otequiv lnot forall{x}{in}mathbf{X}, P(x) equiv exists{x}{in}mathbf{X}, lnot P(x)

Other connectives

The universal (and existential) quantifier moves unchanged across the logical connectives , , , and leftarrow, as long as the other operand is not affected; that is::P(x) land (exists{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) land Q(y)):P(x) lor (exists{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) lor Q(y)):P(x) o (exists{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) o Q(y)):P(x) leftarrow (exists{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) leftarrow Q(y)):P(x) land (forall{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) land Q(y)):P(x) lor (forall{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) lor Q(y)):P(x) o (forall{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) o Q(y)):P(x) leftarrow (forall{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) leftarrow Q(y))Conversely, for the logical connectives , , rightarrow, and , the quantifiers flip::P(x) uparrow (exists{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) uparrow Q(y)):P(x) downarrow (exists{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) downarrow Q(y)):P(x) rightarrow (exists{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) rightarrow Q(y)):P(x) gets (exists{y}{in}mathbf{Y}, Q(y)) equiv forall{y}{in}mathbf{Y}, (P(x) gets Q(y)):P(x) uparrow (forall{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) uparrow Q(y)):P(x) downarrow (forall{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) downarrow Q(y)):P(x) rightarrow (forall{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) rightarrow Q(y)):P(x) gets (forall{y}{in}mathbf{Y}, Q(y)) equiv exists{y}{in}mathbf{Y}, (P(x) gets Q(y))

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{x}{in}mathbf{X}, P(x) o 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",

: P(c) o 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.

The empty set

By convention, the formula forall{x}{in}emptyset , P(x) is always true, regardless of the formula "P"("x"); see vacuous truth.

See also

* Existential quantification
* Quantifiers
* First-order logic

References

*cite book | author = Hinman, P. | title = Fundamentals of Mathematical Logic | publisher = A K Peters | year = 2005 | id = ISBN 1-568-81262-0
*cite book | author = Franklin, J. and Daoud, A. | title = Proof in Mathematics: An Introduction | publisher = Quakers Hill Press | year = 1996 | id = ISBN 1-876192-00-3 (ch. 2)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Quantification — has two distinct meanings.In mathematics and empirical science, it refers to human acts, known as counting and measuring that map human sense observations and experiences into members of some set of numbers. Quantification in this sense is… …   Wikipedia

  • Universal algebra — (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ( models ) of algebraic structures.For instance, rather than take particular groups as the object of study, in universal… …   Wikipedia

  • Universal instantiation — In logic universal instantiation (UI, sometimes confused with Dictum de omni) is an inference from a truth about each member of a class of individuals to the truth about a particular individual of that class. It is generally given as a… …   Wikipedia

  • quantification — See quantifiable. * * * ▪ logic       in logic, the attachment of signs of quantity to the predicate or subject of a proposition. The universal quantifier, symbolized by (∀ ) or ( ), where the blank is filled by a variable, is used to express… …   Universalium

  • Existential quantification — In predicate logic, an existential quantification is the predication [The term predication in grammar means the predicate of a sentence which refers to subject and is an adverb or adjective, or equivalent, that describes an attribute of the… …   Wikipedia

  • Uniqueness quantification — This article is about mathematics. For the electronic group, see Unique (band). In mathematics and logic, the phrase there is one and only one is used to indicate that exactly one object with a certain property exists. In mathematical logic, this …   Wikipedia

  • Singular they — is a popular, non technical expression for uses of the pronoun they (and its inflected forms) when plurality is not required by the context. The Chicago Manual of Style notes: On the one hand, it is unacceptable to a great many reasonable readers …   Wikipedia

  • Dependence logic — is a logical formalism, created by Jouko Väänänen[1], which adds dependence atoms to the language of first order logic. A dependence atom is an expression of the form , where are terms, and corresponds to the statement that the value of is… …   Wikipedia

  • List of philosophy topics (R-Z) — RRaRabad Rabbinic law Rabbinic theology Francois Rabelais François Rabelais race racetrack paradox racism Gustav Radbruch Janet Radcliffe Richards Sarvepalli Radhakrishnan radical Aristotelianism radical behaviourism radical feminism radical… …   Wikipedia

  • SQL — This article is about the database language. For the airport with IATA code SQL, see San Carlos Airport. SQL Paradigm(s) Multi paradigm Appeared in 1974 Designed by Donald D. Chamberlin Raymond F. Boyce Developer …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”