Existence Proofs

An existence proof is just a proof of an existence theorem, which is just a statement saying something exists. For example:

Proposition 1. There exists an even prime number.

Constructive existence proof

The most straightforward way of proving existence theorems is to simply give an example that fits. For example, we can easily prove Proposition 1 by giving an example of an even prime number, namely $2$. Note that no other even prime number exists, but that's okay. The statement doesn't say anything about the number of even prime numbers.

Here's a less trivial example.


Proposition 2. For any positive integer $n$, there exist $n$ consecutive composite numbers.

Proof. Let's fix a positive integer $n$. Now we want to showcase $n$ consecutive composite numbers.

Let $k$ be the product of all integers from $2$ to $n+1$. Then consider the following list of $n$ consecutive numbers: $$k+2, k+3, k+4, \ldots, k+n, k+(n+1)$$

The first number is composite because it's divisible by $2$ and greater than $2$. The second number is also composite because it's divisible by $3$ and greater than $3$. In fact, we can prove similarly that every number in this sequence is composite. Thus, we have just provided a sequence of $n$ consecutive composite numbers!

Since this works for any positive integer $n$, we have just proven the proposition.

Nonconstructive existence proof

The proof above is constructive because we constructed the example explicitly. However, sometimes we can prove that something exists without actually finding one. We call these proofs nonconstructive.

Now, you might be thinking why we would want to prove that an object exists without actually finding it. I mean, wouldn't it be better if we just had the object? Well, you are mostly correct. But there are some occasions that nonconstructive proofs are easier than constructive proofs, and there are even some occasions where you have no choice but to use nonconstructive proofs! (Seriously.)

Here is the prototypical example.


Proposition 3. There exist two irrational numbers $a$ and $b$ such that $a^b$ is rational.

Now, before reading the proof, try finding a suitable $(a,b)$ pair yourself first.

...

...

...

...

...

...

...

...

...

...

Okay, did you find such a pair? If you did, then great, because you've proven Proposition 3! (Assuming you also proved that $a$ and $b$ are irrational and $a^b$ is rational.) But let's read the nonconstructive proof anyway.

Proof. We have proven in the previous section that $\sqrt{2}$ is irrational. Now, consider the number $\sqrt{2}^\sqrt{2}$. This number is either rational or irrational.

If $\sqrt{2}^\sqrt{2}$ is rational, then let $a = b = \sqrt{2}$. Now, $a$ and $b$ are irrational and $a^b = \sqrt{2}^\sqrt{2}$ is rational, and we are done.

If $\sqrt{2}^\sqrt{2}$ is irrational, then let $a = \sqrt{2}^\sqrt{2}$ and $b = \sqrt{2}$. Now, $a$ and $b$ are irrational and $a^b = \left(\sqrt{2}^\sqrt{2}\right)^\sqrt{2} = \sqrt{2}^2 = 2$ is rational, and we are done!

Since we have exhausted all possibilities, we have now proven the proposition.

Notice that we have proven the proposition without actually giving an explicit pair $(a,b)$! Well, we have two candidates, but it depends on whether $\sqrt{2}^\sqrt{2}$ is rational or irrational. But the great thing is that we don't actually need to know which case is correct; the proposition is proved either way!