Existential quantification

From Wikipedia, the free encyclopedia

In predicate logic, an existential quantification is the predication[1] of a property or relation to at least one member of the domain.[1] In laymen's terms, it simply refers to something. It is denoted by the logical operator symbol ∃ (pronounced "there exists" or "for some"), which is called the existential quantifier. Existential quantification is distinct from universal quantification (pronounced "for all"), which asserts that the property or relation holds for any members of the domain.

Contents

[edit] Basics

 The tone or style of this article or section may not be appropriate for Wikipedia.
Specific concerns may be found on the talk page. See Wikipedia's guide to writing better articles for suggestions.(December 2007)

Suppose you wish to write a formula which is true if and only if some natural number multiplied by itself is 25. A slow, brute-force approach you might try is the following:

0·0 = 25, or 1·1 = 25, or 2·2 = 25, or 3·3 = 25, and so on.

This would seem to be a logical disjunction because of the repeated use of "or". However, the "and so on" makes this impossible to integrate and to interpret as a disjunction in formal logic. Instead, we rephrase the statement as

For some natural number n, n·n = 25.

This is a single statement using existential quantification.

Notice that this statement is really more precise than the original one. It may seem obvious that the phrase "and so on" 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 quantified statement, on the other hand, the natural numbers are mentioned explicitly.

This particular example is true, because 5 is a natural number, and when we substitute 5 for n, we produce "5·5 = 25", which is true. It does not matter that "n·n = 25" is false for most natural numbers n, in fact false for all of them except 5; even the existence of a single solution is enough to prove the existential quantification true. (Of course, multiple solutions can only help!) In contrast, "For some even number n, n·n = 25" is false, because there are no even solutions.

On the other hand, "For some odd number n, n·n = 25" is true, because the solution 5 is odd. This demonstrates the importance of the domain of discourse, which specifies which values the variable 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 existential quantification, you do this with a logical conjunction. For example, "For some odd number n, n·n = 25" is logically equivalent to "For some natural number n, n is odd and n·n = 25". Here the "and" construction indicates the logical conjunction.

In symbolic logic, we use the existential quantifier "∃" (a backwards letter "E" in a sans-serif font) to indicate existential quantification. Thus if P(a, b, c) is the predicate "a·b = c" and \mathbb{N} is the set of natural numbers, then

\exists{n}{\in}\mathbb{N}\, P(n,n,25)

is the (true) statement

For some natural number n, n·n = 25.

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

\exists{n}{\in}\mathbb{N}\, \big(Q(n)\;\!\;\! {\wedge}\;\!\;\! P(n,n,25)\big)

is the (false) statement

For some even number n, n·n = 25.

Several variations in the notation for quantification (which apply to all forms) can be found in the quantification article.

[edit] Properties

[edit] 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 between 0 and 1"; then, for a Universe of Discourse X of all natural numbers, consider the existential quantification "There exists a natural number x which is between 0 and 1":

\exists{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 there is a natural number x, that is between 0 and 1", or, symbolically:

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

Take a moment and consider what, exactly, negating the existential quantifier means: if the there is no element of the Universe of Discourse for which the statement is true, then it must be false for all of those elements. That is, the negation of \exists{x}{\in}\mathbf{X}\, P(x) is logically equivalent to "For any natural number x, x is not between 0 and 1", or:

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

Generally, then, the negation of a propositional function's existential quantification is an universal quantification of that propositional function's negation; symbolically,

\lnot\ \exists{x}{\in}\mathbf{X}\, P(x) \equiv\ \forall{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) \not\equiv\ \lnot\ \forall{x}{\in}\mathbf{X}\, P(x) \equiv\ \exists{x}{\in}\mathbf{X}\, \lnot P(x)

[edit] 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 existential

Existential introduction concludes that, if the propositional function is known to be true for a particular element of the universe of discourse, then it must be true that there exists an element for which the proposition function is true. Symbolically, this is represented as

P(a) \to\ \exists{x}{\in}\mathbf{X}\, P(x)


Existential elimination is a fairly complicated rule. The reasoning behind it is as follows: If we know that there exists an element for which the proposition function is true, then if we can each a conclusion by giving that object an arbitrary name, we know that conclusion to be true, as long as it does not contain the name. Symbolically, for an arbitrary c and for a proposition Q in which c does not appear:

\exists{x}{\in}\mathbf{X}\, P(x) \to\ ((P(c) \to\ Q) \to\ Q)

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 stating P(c) might unjustifiably give us more information about that object.


Finally, unlike the universal quantifier, the existential quantifier distributes over logical disjunctions:

\exists{x}{\in}\mathbf{X}\, P(x) \or Q(x) \to\ (\exists{x}{\in}\mathbf{X}\, P(x) \or \exists{x}{\in}\mathbf{X}\, Q(x))

[edit] Notes

  1. ^ 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 subject. In logic, "predication" is a declaration (or assertion) that is claimed to be self-evident and can be assumed as the basis for argument.

[edit] See also

[edit] References

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