There exists

From CS2800 wiki


If [math]P [/math] is a predicate depending only on [math]x [/math], then "there exists [math]x [/math] such that P" (written [math]\exists x, P [/math] or [math]\exists x~\href{/cs2800/wiki/index.php?title=S.t.&action=edit&redlink=1}{s.t.}~P [/math]) is a proposition. It is true if there is some value [math]x [/math] that makes [math]P [/math] evaluate to true.

[math]\href{/cs2800/wiki/index.php/%5Cexists}{\exists} [/math] is sometimes called the existential quantifier.

  • To prove that there exists an [math]x [/math] such that [math]P(x) [/math] holds, it suffices to give a specific [math]x [/math] and then prove that [math]P [/math] is true for that [math]x [/math]. Such a proof usually starts "let [math]x:= \cdots [/math]", and then goes on to prove that [math]P(x) [/math] holds for the given [math]x [/math]. [math]x [/math] is sometimes referred to as a witness for [math]P(x) [/math].
  • If you know there exists some [math]x [/math] satisfying [math]P [/math], you can use it in a proof by treating [math]x [/math] as an arbitrary value. [math]x [/math] is arbitrary because the only thing you know about [math]x [/math] is that it exists, not what its value is.
  • To disprove that there exists an [math]x [/math] satisfying [math]P [/math], you must disprove [math]P [/math] for an arbitrary [math]x [/math]. Put another way, the logical negation of "there exists an [math]x [/math] such that [math]P [/math]" is "for all x, not P".


When trying to prove an existential statement [math]\href{/cs2800/wiki/index.php/%E2%88%83}{∃x}, \href{/cs2800/wiki/index.php/Predicate}{P}(x) [/math], you need to give a specific value of [math]x [/math] (a witness).

Often, in a proof, it is not immediately obvious what the witness should be. Finding one often involves solving some equations or combining some known values.

One nice technique for finding a witness is to simply leave a blank space for the value of [math]x [/math] and continue on with your proof of [math]P(x) [/math]. As you go, you may need [math]x [/math] to satisfy certain properties (for example, maybe you need [math]x \gt 17 [/math] at one point, and later you need [math]x \lt 85 [/math]). You can make a "wishlist" on the side of your proof, reminding you of all the properties you want [math]x [/math] to satisfy. Once you've completed your proof, you can go back and find a specific value of [math]x [/math] (say, [math]50 [/math]) that satisfies all of your wishes.