View source for Existential quantification

{{Short description|Mathematical use of "there exists"}}
{{redirect2|∃&nbsp;|∄&nbsp;|the letter turned E|Ǝ|the Japanese katakana ヨ|Yo (kana)|the Ukrainian nightclub also called ∄&nbsp;|K41 (nightclub)}}
{{Infobox mathematical statement
| name = Existential quantification
| type = [[Quantification (logic)|Quantifier]]
| field = [[Mathematical logic]]
| statement = <math>\exists xP(x)</math> is true when <math>P(x)</math> is true for at least one value of <math>x</math>.
| symbolic statement = <math>\exists xP(x)</math>
}}
In [[predicate logic]], an '''existential quantification''' is a type of [[Quantifier (logic)|quantifier]], a [[logical constant]] which is [[interpretation (logic)|interpreted]] as "there exists", "there is at least one", or "for some". It is usually denoted by the [[logical connective|logical operator]] [[Symbol (formal)|symbol]] ∃, which, when used together with a predicate variable, is called an '''existential quantifier''' ("{{math|∃''x''}}" or "{{math|∃(''x'')}}" or "{{math|(∃''x'')"<ref>{{cite book |last1=Bergmann|first1=Merrie |title=The Logic Book |date=2014 |publisher=McGraw Hill|isbn=978-0-07-803841-9 |language=en}}</ref>}}). Existential quantification is distinct from [[universal quantification]] ("for all"), which asserts that the property or relation holds for ''all'' members of the domain.<ref>{{Cite web |title=Predicates and Quantifiers |url=https://www.csm.ornl.gov/~sheldon/ds/sec1.6.html |access-date=2020-09-04 |website=www.csm.ornl.gov}}</ref><ref>{{Cite web |title=1.2 Quantifiers |url=https://www.whitman.edu/mathematics/higher_math_online/section01.02.html |access-date=2020-09-04 |website=www.whitman.edu}}</ref> Some sources use the term '''existentialization''' to refer to existential quantification.<ref>{{cite book |last1=Allen |first1=Colin |url=https://books.google.com/books?id=RSTYAgAAQBAJ&pg=PA77|title=Logic Primer |last2=Hand |first2=Michael |date=2001 |publisher=MIT Press |isbn=0262303965 |language=en}}</ref>

Quantification in general is covered in the article on [[quantification (logic)]]. The existential quantifier is encoded as {{unichar|2203|THERE EXISTS}} in [[Unicode]], and as <code>\exists</code> in [[LaTeX]] and related formula editors.

== Basics ==
Consider the [[formal logic|formal]] sentence

:For some natural number <math>n</math>, <math>n\times n=25</math>.

This is a single statement using existential quantification. It is roughly analogous to the informal sentence "Either <math>0\times 0=25</math>, or <math>1\times 1=25</math>, or <math>2\times 2=25</math>, or... and so on," but more precise, because it doesn't need us to infer the meaning of the phrase "and so on." (In particular, the sentence explicitly specifies its [[domain of discourse]] to be the natural numbers, not, for example, the [[real number]]s.)

This particular example is true, because 5 is a natural number, and when we substitute 5 for ''n'', we produce the true statement <math>5\times 5=25</math>. It does not matter that "<math>n\times n=25</math>" is true only for that single natural number, 5; the existence of a single [[solution (equation)|solution]] is enough to prove this existential quantification to be true.

In contrast, "For some [[even number]] <math>n</math>, <math>n\times n=25</math>" is false, because there are no even solutions. The [[domain of discourse]], which specifies the values the variable ''n'' is allowed to take, is therefore critical to a statement's trueness or falseness. [[Logical conjunction]]s are used to restrict the domain of discourse to fulfill a given predicate. For example, the sentence

:For some positive odd number <math>n</math>, <math>n\times n=25</math>

is [[logically equivalent]] to the sentence

:For some natural number <math>n</math>, <math>n</math> is odd and <math>n\times n=25</math>.

The [[mathematical proof]] of an existential statement about "some" object may be achieved either by a [[constructive proof]], which exhibits an object satisfying the "some" statement, or by a [[nonconstructive proof]], which shows that there must be such an object without concretely exhibiting one.

===Notation===
In [[First-order logic|symbolic logic]], "∃" (a turned letter "[[E]]" in a [[sans-serif]] font, Unicode U+2203) is used to indicate existential quantification. For example, the notation <math>\exists{n}{\in}\mathbb{N}: n\times n=25</math> represents the (true) statement

:There exists some <math>n</math> in the set of [[natural number]]s such that <math>n\times n=25</math>.

The symbol's first usage is thought to be by [[Giuseppe Peano]] in ''[[Formulario mathematico]]'' (1896). Afterwards, [[Bertrand Russell]] popularised its use as the existential quantifier. Through his research in set theory, Peano also introduced the symbols <math>\cap</math> and <math>\cup</math> to respectively denote the intersection and union of sets.<ref name="Webb2018">{{cite book |author=Stephen Webb |title=Clash of Symbols |publisher=Springer Cham |year=2018 |isbn=978-3-319-71349-6 |doi=10.1007/978-3-319-71350-2 |url=http://link.springer.com/10.1007/978-3-319-71350-2|pages=210–211}}</ref>

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

== As adjoint ==
{{main|Universal quantification#As adjoint}}
In [[category theory]] and the theory of [[elementary topos|elementary topoi]], the existential quantifier can be understood as the [[left adjoint]] of a [[functor]] between [[power set]]s, the [[inverse image]] functor of a function between sets; likewise, the [[universal quantifier]] is the [[right adjoint]].<ref>[[Saunders Mac Lane]], Ieke Moerdijk, (1992): ''Sheaves in Geometry and Logic'' Springer-Verlag {{ISBN|0-387-97710-4}}. ''See p. 58''.</ref>

== See also ==
* [[Existential clause]]
* [[Existence theorem]]
* [[First-order logic]]
* [[Lindström quantifier]]
* [[List of logic symbols]] – for the unicode symbol ∃
* [[Quantifier variance]]
* [[Uniqueness quantification]]

== Notes ==
<references/>

== References ==
{{refbegin}}
*{{cite book |author=Hinman, P. |title=Fundamentals of Mathematical Logic |publisher=A K Peters |year=2005 |isbn=1-56881-262-0}}
{{refend}}
{{Authority control}}
{{Common logical symbols}}
{{Mathematical logic}}

[[Category:Logic symbols]]
[[Category:Quantifier (logic)]]