Existential quantification

A quantified propositional function is a statement; thus, like statements, quantified functions can be negated. The ${\displaystyle \lnot \ }$ symbol is used to denote negation.

For example, if P(x) is the predicate "x is greater than 0 and less than 1", then, for a domain of discourse X of all natural numbers, the existential quantification "There exists a natural number x which is greater than 0 and less than 1" can be symbolically stated as:

${\displaystyle \exists {x}{\in }\mathbf {X} \,P(x)}$

This can be demonstrated to be false. Truthfully, it must be said, "It is not the case that there is a natural number x that is greater than 0 and less than 1", or, symbolically:

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

If there is no element of the domain of discourse for which the statement is true, then it must be false for all of those elements. That is, the negation of

${\displaystyle \exists {x}{\in }\mathbf {X} \,P(x)}$

is logically equivalent to "For any natural number x, x is not greater than 0 and less than 1", or:

${\displaystyle \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,

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

(This is a generalization of De Morgan's laws to predicate logic.)

A common error is stating "all persons are not married" (i.e., "there exists no person who is married"), when "not all persons are married" (i.e., "there exists a person who is not married") is intended:

${\displaystyle \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)}$

Negation is also expressible through a statement of "for no", as opposed to "for some":

${\displaystyle \nexists {x}{\in }\mathbf {X} \,P(x)\equiv \lnot \ \exists {x}{\in }\mathbf {X} \,P(x)}$

Unlike the universal quantifier, the existential quantifier distributes over logical disjunctions:

${\displaystyle \exists {x}{\in }\mathbf {X} \,P(x)\lor Q(x)\to \ (\exists {x}{\in }\mathbf {X} \,P(x)\lor \exists {x}{\in }\mathbf {X} \,Q(x))}$

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

Existential introduction (∃I) concludes that, if the propositional function is known to be true for a particular element of the domain of discourse, then it must be true that there exists an element for which the proposition function is true. Symbolically,

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

Existential elimination, when conducted in a Fitch style deduction, proceeds by entering a new sub-derivation while substituting an existentially quantified variable for a subject—which does not appear within any active sub-derivation. If a conclusion can be reached within this sub-derivation in which the substituted subject does not appear, then one can exit that sub-derivation with that conclusion. The reasoning behind existential elimination (∃E) is as follows: If it is given that there exists an element for which the proposition function is true, and if a conclusion can be reached by giving that element an arbitrary name, that conclusion is necessarily 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:

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

${\displaystyle P(c)\to \ Q}$ must be true for all values of c over the same domain X; else, the logic does not follow: If c is not arbitrary, and is instead a specific element of the domain of discourse, then stating P(c) might unjustifiably give more information about that object.

The formula ${\displaystyle \exists {x}{\in }\emptyset \,P(x)}$ is always false, regardless of P(x). This is because ${\displaystyle \emptyset }$ denotes the empty set, and no x of any description – let alone an x fulfilling a given predicate P(x) – exist in the empty set. See also Vacuous truth for more information.