|
|
|
|
Existential quantification
|
| |
|
| |
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. 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.
Discussion
Ask a question about 'Existential quantification' Start a new discussion about 'Existential quantification' Answer questions from other users |
Encyclopedia
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. 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.
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 is the set of natural numbers, then
-
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: .
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":
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:
.
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 is logically equivalent to "For any natural number x, x is not between 0 and 1", or:
Generally, then, the negation of a propositional function's existential quantification is a universal quantification of that propositional function's negation; symbolically,
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"):
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
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:
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:
The Empty set
By convention, the formula is always false, regardless of the formula P(x); see vacuous truth.
See also
|
| |
|
|
