Editing Existential quantification (section)

== Properties ==

=== Negation ===
A quantified propositional function is a statement; thus, like statements, quantified functions can be negated.  The <math>\lnot\ </math> 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:
:<math>\exists{x}{\in}\mathbf{X}\, P(x)</math>

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:
:<math>\lnot\ \exists{x}{\in}\mathbf{X}\, P(x)</math>.

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
:<math>\exists{x}{\in}\mathbf{X}\, P(x)</math>
is logically equivalent to "For any natural number ''x'', ''x'' is not greater than 0 and less than 1", or:
:<math>\forall{x}{\in}\mathbf{X}\, \lnot P(x)</math>

Generally, then, the negation of a [[propositional function]]'s existential quantification is a [[universal quantification]] of that propositional function's negation; symbolically,
:<math>\lnot\ \exists{x}{\in}\mathbf{X}\, P(x) \equiv\ \forall{x}{\in}\mathbf{X}\, \lnot P(x)</math>
(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:
:<math>\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)</math>

Negation is also expressible through a statement of "for no", as opposed to "for some":
:<math>\nexists{x}{\in}\mathbf{X}\, P(x) \equiv \lnot\ \exists{x}{\in}\mathbf{X}\, P(x)</math>

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

<math> \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))</math>

=== Rules of inference ===
{{Transformation rules}}

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 generalization|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,

:<math> P(a) \to\ \exists{x}{\in}\mathbf{X}\, P(x)</math>

[[Existential elimination|Existential instantiation]], 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 [[logical truth|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:

:<math> \exists{x}{\in}\mathbf{X}\, P(x) \to\ ((P(c) \to\ Q) \to\ Q)</math>

<math>P(c) \to\ Q</math> 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 empty set ===
The formula <math>\exists {x}{\in}\varnothing \, P(x)</math> is always false, regardless of ''P''(''x''). This is because <math>\varnothing</math> 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.