Existential quantification

From Wikipedia, the free encyclopedia

(Redirected from There exists)

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 ("for all"), which asserts that the property or relation holds for any members of the domain.

[edit] Basics

Consider a formula which states that some natural number multiplied by itself is 25. A slow, brute-force way to write this 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, the statement could be rephrased as

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

This is a single statement using existential quantification.

This statement is more precise than the original one, as the phrase "and so on" does not necessarily include all natural numbers, and nothing more. Since the domain was not stated explicitly, the phrase could not 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.^[2] 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 a 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 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) \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] 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.

[edit] Notes

^ 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.
^ This symbol is also known as the existential operator. It is sometimes represented with an alternate symbol V.

[edit] See also

[edit] References

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

[0] 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.

[1] This symbol is also known as the existential operator. It is sometimes represented with an alternate symbol V.

[1]

[2]

Existential quantification

From Wikipedia, the free encyclopedia

Contents

[edit] Basics

[edit] Properties

[edit] Negation

[edit] Rules of Inference

[edit] The Empty set

[edit] Notes

[edit] See also

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages