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 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.] of a property or relation to at least one member of the domain. [http://dictionary.reference.com/browse/predication] 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.

Basics

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

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 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)\; otequiv\; 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 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)\; o\; 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 reach 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)\; o\; ((P(c)\; o\; Q)\; o\; 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)\; o\; (exists\{x\}\{in\}mathbf\{X\},\; P(x)\; or\; exists\{x\}\{in\}mathbf\{X\},\; Q(x))$

The Empty set

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

Notes

See also

* 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