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