universal_quantification

Search for "universal quantification" on Ebay? Click here!

universal quantification

In predicate logic, universal quantification formalizes 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 $\backslash forall$, ?, a turned a) 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.

Basics

Suppose it is given that

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." However, the "etc." cannot be interpreted as a conjunction in formal logic. Instead, the statement must be rephrased:

For all natural numbers n, 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 numbers, 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, 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 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 can take.Further information on using domains of discourse with quantified statements can be found in the Quantification 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, 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, the universal quantifier symbol $\backslash forall$ (a turned "A" in a sans-serif font, Unicode 0x2200) is used to indicate universal quantification. Thus if P(n) is the predicate "2·n > 2 + n" and N is the set of natural numbers, then:

$\backslash forall\; n\backslash !\backslash in\backslash !\backslash mathbb\{N\}\backslash ;\; 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

$\backslash forall\; n\backslash !\backslash in\backslash !\backslash mathbb\{N\}\backslash ;\; \backslash bigl(\; Q(n)\; \backslash rightarrow\; P(n)\; \backslash bigr)$

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 is given:

$(n\{\backslash in\}\backslash mathbb\{N\})\backslash ,\; 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: $\backslash lnot\backslash$.

For example, if P(x) is the propositional function "x is married", then, for a Universe of Discourse X of all living human beings, the universal quantification

Given any living person x, that person is married

is given:

$\backslash forall\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; P(x)$

It can be seen that this irrevocably false. Truthfully, it is stated that

It is not the case that, given any living person x, that person is married

or, symbolically:

$\backslash lnot\backslash \; \backslash forall\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; P(x)$.

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 $\backslash forall\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; P(x)$ is logically equivalent to "There exists a living person x such that he is not married", or:

$\backslash exists\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; \backslash 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,

$\backslash lnot\backslash \; \backslash forall\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; P(x)\; \backslash equiv\backslash \; \backslash exists\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; \backslash lnot\; P(x)$

It is erroneous to state "all persons are not married" (i.e. "there exists no person who is married") when it is meant that "not all persons are married" (i.e. "there exists a person who is not married"):

$\backslash lnot\backslash \; \backslash exists\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; P(x)\; \backslash equiv\backslash \; \backslash forall\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; \backslash lnot\; P(x)\; \backslash not\backslash equiv\backslash \; \backslash lnot\backslash \; \backslash forall\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; P(x)\; \backslash equiv\backslash \; \backslash exists\{x\}\{\backslash in\}\backslash mathbf\{X\}\backslash ,\; \backslash lnot\; P(x)$

Other connectives

The universal (and existential) quantifier moves unchanged across the logical connectives ?, ?, ?, and $\backslash nleftarrow$, as long as the other operand is not affected; that is:

$P(x)\; \backslash land\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash land\; Q(y))$

$P(x)\; \backslash lor\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash lor\; Q(y))$

$P(x)\; \backslash to\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash to\; Q(y))$

$P(x)\; \backslash nleftarrow\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash nleftarrow\; Q(y))$

$P(x)\; \backslash land\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash land\; Q(y))$

$P(x)\; \backslash lor\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash lor\; Q(y))$

$P(x)\; \backslash to\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash to\; Q(y))$

$P(x)\; \backslash nleftarrow\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash nleftarrow\; Q(y))$

Conversely, for the logical connectives ?, ?, $\backslash nrightarrow$, and ?, the quantifiers flip:

$P(x)\; \backslash uparrow\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash uparrow\; Q(y))$

$P(x)\; \backslash downarrow\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash downarrow\; Q(y))$

$P(x)\; \backslash nrightarrow\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash nrightarrow\; Q(y))$

$P(x)\; \backslash gets\; (\backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash gets\; Q(y))$

$P(x)\; \backslash uparrow\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash uparrow\; Q(y))$

$P(x)\; \backslash downarrow\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash downarrow\; Q(y))$

$P(x)\; \backslash nrightarrow\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash nrightarrow\; Q(y))$

$P(x)\; \backslash gets\; (\backslash forall\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; Q(y))\; \backslash equiv\backslash \; \backslash exists\{y\}\{\backslash in\}\backslash mathbf\{Y\}\backslash ,\; (P(x)\; \backslash gets\; Q(y))$

The empty set

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

Universal closure

The universal closure of a formula ? is another formula with no free variables, obtained by adding a universal quantifier for every free variable in ?. For example, the universal closure of

$P(y)\; \backslash land\; \backslash exists\; x\; Q(x,z)$

is

$\backslash forall\; y\; \backslash forall\; z\; (\; P(y)\; \backslash land\; \backslash exists\; x\; Q(x,z))$.

See also

• Redirect Template:Wiktionary

• Existential quantification

• Quantifiers

• First-order logic

Notes

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "universal_quantification". The list of authors you can find on this page.