Many interesting and important theorems have the
form $\exists x\,P(x)$, that is, that there exists an
object $x$ satisfying some formula $P$. In such **existence
proofs**, try to be as specific as
possible. The most satisfying and useful existence proofs often give a
concrete example, or describe explicitly how to produce the object
$x$.

Example 2.3.1 To prove the statement,
*there is a prime number $p$ such that $p+2$ and $p+6$ are
also prime numbers*,
note that $p=5$ works because $5+2=7$ and $5+6=11$ are also primes.

In this example, 5 is not the only number that works (e.g., 11 works as well). In fact, it is a famous unsolved problem whether there are infinitely many primes that work. This would be a more interesting theorem, but the point remains: when doing an existence proof, be as concrete as possible.

Example 2.3.2 Suppose $U$ is a universe which is appropriate for a calculus
class. To prove the statement, *there is a function $f$ such that
$f'=f$*, note that $f(x)=e^x$ works (as does any constant multiple of
$e^x$).

A slight variation on the existence proof is the *counter-example*. Suppose you look at a
sentence of the form $\forall x P(x)$ and you come to the conclusion
that it is false and you wish to prove this. What you wish to prove,
then, is $\lnot\forall x P(x)$, which by De Morgan's
law is equivalent to $\exists x \lnot P(x)$.
A specific $x$ satisfying $\lnot P(x)$ is called a counter-example to
the assertion that $\forall x P(x)$.

Example 2.3.3
To disprove the sentence *for every integer $x$, if* $6x$ *is even
then $x$ is even*, we write it symbolically as
$$
\forall x\,(6x \hbox{ is even}\implies x \hbox{ is even}).
$$
To disprove this, note that $x=3$ is a counter-example, because
$6\cdot 3$ is even but $3$ is odd. It may help, especially in more
complicated examples, to form the denial explicitly:
$$\exists x\,(6x \hbox{ is even}\land x \hbox{ is not even}).$$
Now it is easy to see that $x=3$ makes the formula in parentheses true.

Example 2.3.4 Suppose $U$ is the universe of example 2.3.2.
To disprove the sentence *for every function $f$, if $f$ is
continuous at $0$ then it is differentiable at $0$*,
note that $f(x)=\vert x\vert$ is a counter-example.

Once again, the most satisfying way to prove something false is to come up with a specific counter-example, though sometimes this is difficult or impossible. Note well that it is never sufficient simply to find an error in the proof of some sentence to conclude that it is false—it is easy to come up with erroneous proofs of correct facts. If you have trouble proving a statement of the form $\forall x\,P(x)$, try looking at some particular cases of the result. You may find a counter-example, or you may get a hint about why the statement really is true.

There are occasions when it is impossible, or very difficult, to find a specific example. An existence proof sometimes can be constructed by indirect means, or by using other existence results.

Example 2.3.5 Using a universe as in example 2.3.2,
show *there is a solution for the equation $x^3+3x-2 =0$ in the
interval $[0,1]$*. Let $f(x)=x^3+3x-2$; then
since $f(0)=-2$ and $f(1)=2$, the Intermediate Value
Theorem says that there is an $x$ in
$[0,1]$ for which $f(x)=0$.

If you consult a good calculus text, you should find that the Mean Value Theorem (which is an existence result), is proved by referring to Rolle's Theorem (another existence result), which is proved by referring to the Maximum Value Theorem (yet a third existence result, sometimes called the Extreme Value Theorem), which is proved "indirectly,'' without ever exhibiting the object that is claimed to exist. At no point are we given a formula for the quantity we seek, and the result is perhaps not as satisfying as we would like. In general, then, try to be specific when doing an existence proof, but if you cannot, it may still be possible to construct an example using some other existence result or another technique of proof.

Trying to prove a statement of the form $\forall x\exists yP(x,y)$ is rather like trying to do many existence arguments at the same time. For any value $x$ we would like to construct or describe a $y$ that makes $P(x,y)$ true.

Example 2.3.6 *There is no largest integer*.
We want to prove $\forall n\exists m(n< m)$. Argue as follows:
Suppose $n\in \Z$ is given. Let $m=n+1$. Then $n< n+1=m$.

Example 2.3.7 $\forall x\exists y(2y=x^2+x)$. Let $x$ be an arbitrary integer. If $x$ is even, $x^2$ is even and if $x$ is odd, $x^2$ is odd. Since the sum of two even numbers or two odd numbers is even, $x^2+x$ is even. Therefore, $\exists y(2y=x^2+x$), by the definition of even, and in fact $y=(x^2+x)/2$.

Example 2.3.8 *There are arbitrarily long gaps in the sequence of prime
numbers*. In other words, we want to prove that for every positive
integer $n$ there is a positive integer $m$ such that $m+1$, $m+2$,
$…$, $m+n$ are all composite. For any $n$, let
$m=(n+1)!+1=(n+1)n(n-1)\cdots 1+1$. If $1\le k\le n$, then
$m+k=(n+1)!+(k+1)$. Since both $(n+1)!$ and $k+1$ are divisible by
$k+1>1$, $m+k$ is composite.

## Exercises 2.3

The universe of discourse is shown in parentheses.

**Ex 2.3.1**
($\N$) Show that there is a prime number $p$ such that $p+4$
and $p+6$ are also prime numbers.

**Ex 2.3.2**
($\N$) Show that there are prime numbers $p$ and $q$ such
that $p+q=128$. (This is a case of the famous **Goldbach
Conjecture**, which says that every even
integer $n\ge 4$ can be written as the sum of two primes. It seems
highly probable from work with computers that the Goldbach Conjecture
is true, but no one has discovered a proof.)

**Ex 2.3.3**
($\Z$) Show that every odd integer is the sum of two
consecutive integers.

**Ex 2.3.4**
($\Z$) Show that every odd integer is the difference between
two consecutive perfect squares.

**Ex 2.3.5**
($\N$) Disprove the following: If $12\vert x^2$, then $12\vert x$.

**Ex 2.3.6**
($\N$) Disprove the following: If $x\vert ab$, then $x\vert a$ or
$x\vert b$.

**Ex 2.3.7**
($\N$) Disprove the following: If $n^2\vert m^3$, then $n\vert m$.

**Ex 2.3.8**
($\R$)
Show there is an $x\in [0,\pi/2]$ such that $\cos x=x$.