Section 6.10 Existence and uniqueness
In mathematics we often want to know whether an object with specific desirable properties actually exists. In symbolic language, this is just \((\exists x)A(x)\text{.}\) Conceptually, this is easy to do: just find an example! (In practice, this can often be quite difficult.)
Worked Example 6.10.1.
Prove that \(851\) is not prime.
Solution.
We want to prove the quantified statement
\begin{equation*}
(\exists n)\bbrac{ (n \ne 1) \lgcand (n \ne 851) \lgcand (n \text{ divides } 851)} \text{,}
\end{equation*}
with domain the positive, whole numbers. Testing each number, one by one, starting at \(n = 2\text{,}\) we find that using \(n=23\) fits the bill.
Once we have found an example for an existential statement, we also often want to know whether there are more examples, or whether the one we have found is unique. Suppose \(x_0\) is our concrete example proving \((\exists x)A(x)\text{.}\) To show that \(x_0\) is unique, we should prove the universal statement: \((\forall y)\bbrac{ A(y) \lgccond (y = x_0) }\text{.}\) This translates as the following.
For all \(y\text{,}\) if \(A(y)\) is true, then \(y=x_0\text{.}\)
That is, the only way object \(y\) can satisfy \(A(y)\) is if \(y\) is actually our original example \(x_0\text{.}\)
Procedure 6.10.2. Proving uniqueness.
To prove that \(x = x_0\) is the unique instance of an object \(x\) such that \(A(x)\) is true, assume that \(y\) is also an object such that \(A(y)\) is true, and prove that \(y = x_0\text{.}\)
Worked Example 6.10.3.
Prove that \(2\) is the unique positive number that is both prime and even.
Solution.Suppose \(n\) is a positive number which is both prime and even. Since \(n\) is even, it is divisible by \(2\text{.}\) But since \(n\) is prime, it is divisble by only \(1\) and itself. Therefore, \(2\) and “itself” must be the same, i.e. \(n = 2\text{.}\)
