Definition 1.3.3.1.
The existential quantification of \(P\) , denoted \(\exists x \,P(x)\) is the proposition “There exists an element \(x\) in the domain such that \(P(x)\text{.}\)” The symbol \(\exists\) is the existential quantifier.
Subsection 1.3.3 Existential quantification
Example 1.3.3.2. Existential quantification is true.
Let \(Q(x)\) be “\(x\lt 0\)” with domain the integers. Consider the proposition
\begin{equation*}
\exists x\, Q(x)
\end{equation*}
Because \(Q(-3)=\) “\(-3\lt 0\)” is true and \(-3\) is an integer, we have found an element in the domain for which \(Q(x)\) is true. Thus the proposition \(\exists x\, Q(x)\) is true.
Example 1.3.3.3. Existential quantification is false.
Let \(R(x)=\) “\(x\lt 0\)” with domain the natural numbers. Consider the proposition
\begin{equation*}
\exists x\, R(x)
\end{equation*}
Because all natural numbers are positive there is no natural number \(b\) such that \(b \lt 0\text{.}\) Thus \(\exists x\, R(x)\) is false.
Definition 1.3.3.4.
A witness of \(\exists x \,P(x)\) is an element \(x_0\) in the domain of \(P\) such that \(P(x_0)\text{.}\)
Remark 1.3.3.5.
To prove an existential quantification is true, it suffices to exhibit a single witness.
Proof Technique 1.3.3.6. To show \(\exists x \,P(x)\) is true.
Suppose \(P\) is a propositional function, and we want to prove the existential quantification \(\exists x \,P(x)\) is true.
-
Find a witness. Specifically, find an element \(x_0\) in the domain of \(P\) such that \(P(x_0)\) is true.
-
Conclude \(\exists x \,P(x)\) is true.
Example 1.3.3.7. Witness.
Let \(P(x)\) be “\(x^4=16\)” with domain the integers.
-
\(\exists x\, P(x)\) is true since \(2^4=16\) and \(2\) is in the domain of \(P\text{.}\) We say \(x=2\) is a witness for \(\exists x\, P(x)\text{.}\)
-
\(\forall x\, P(x)\) is false since \(3^4=81\ne 16\) and \(3\) is in the domain of \(P\text{.}\) We say \(x=3\) is a counterexample for \(\forall x\, P(x)\text{.}\)
To show an existential quantification false, we need to show that a witness does not exist. Specifically, to show \(\exists x \,P(x)\) is false, we need to show that \(P(x)\) is false for every \(x\) in the domain of \(P\) .
Proof Technique 1.3.3.8. To show \(\exists x \,P(x)\) is false.
Suppose \(P\) is a propositional function, and we want to prove the existential quantification \(\exists x \,P(x)\) is false.
-
Show \(P(x)\) is false.
-
Conclude \(\exists x \,P(x)\) is false.
Remark 1.3.3.9.
To prove the existential quantification of \(P\) is true, it is enough to exhibit a single witness. To prove the existential quantification of \(P\) is false, we need to show that the universal quantification of \(\lnot P\) is true.
We wrap up this section with a comparison of the proof techniques for universal and existential quantification.
Proposition
|
When true?
|
When false?
|
|---|---|---|
\(\forall x \,P(x)\)
|
||
\(\exists x \,P(x)\)
|
Example 1.3.3.11. MAT 253 students born in NC.
Let \(N(x)\) be the propositional function “\(x\) was born in NC,” with domain the MAT 253 students.
-
\(\displaystyle \forall x \,N(x)\)
-
\(\displaystyle \exists x \,N(x)\)
What are the truth values of the two propositions above? Do you need to discuss this with your classmates to determine the truth values?
-
\(\forall x \,N(x)\) says “Every student in MAT 253 was born in NC.” To prove this statement false, it is enough to produce a counterexample. We need to just find one student in MAT 253 that was not born in NC. To prove this statement true, we need to check that every MAT 253 student was born in NC.
-
\(\exists x \,N(x)\) says “There is a student in MAT 253 that was born in NC.” To prove this statement true, it is enough to produce a witness. We need to find just find one student in MAT 253 that was not born in NC.
Now suppose instead we take the domain of \(N\) to be all people in the US, but we want to have the same propositions about our MAT 253 class. Then we need to introduce a new propositional function \(S(x)\) which is “\(x\) is a MAT 253 student.”
-
We can write “Every student in MAT 253 was born in NC,” as \(\forall x(S(x) \implies N(x))\) .
-
We can write “There is a student in MAT 253 that was born in NC,” as \(\exists x \,(S(x)\land N(x))\)
Note that we have shown that \(p \implies q\) is equivalent to \(\lnot p\lor q\) . That means that \(\forall x \,(\lnot S(x)\lor N(x))\) is a valid (though convoluted) way to write that every student in MAT 253 was born in NC.
https://xkcd.com/1856/). Real analysis is way realer than I expected.
