Existence Proofs

Section 5.4 Existence Proofs

Sometimes, in mathematics, we want to prove that a certain object exists. For example, given an equation, a solution to this equation exists.

Subsection 5.4.1 Existence Proofs

Definition 5.4.1.

An existence theorem is a theorem which asserts that something exists, without providing information about how to find it.

There are two classes of proofs of existence theorems: constructive proofs and non-constructive proofs. Literally, constructive proofs involve explicitly constructing the object that satisfies the properties of the theorem, and proving that it does satisfy these properties. On the other hand, non-constructive proof show the existence of the object without constructing it.

Subsection 5.4.2 Famous Non-Constructive Proof

Theorem 5.4.2. There exists a power of irrationals which is rational.

There exists two irrational numbers $a$ and $b$ such that $a^b$ is rational.

This theorem is not intuitive, and it has an elegant non-constructive proof. It uses the fact that $\sqrt{2}$ is irrational.

Proof.

Consider the number $\sqrt{2}^{\sqrt{2}\text{.}$

If $\sqrt{2}^{\sqrt{2}}$ is rational, then we can let $a = b = \sqrt{2}$ (which are both irrational) and we are done.
If $\sqrt{2}^{\sqrt{2}}$ is irrational, then consider raising this number to the exponent $\sqrt{2}\text{,}$
\begin{align*} \brac{\sqrt{2}^{\sqrt{2}}^{\sqrt{2}} \amp = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} \amp\amp \text{by properties of exponents}\\ \amp = \sqrt{2}^2\\ \amp = 2 \end{align*}
Thus, we can let $a = \sqrt{2}^{\sqrt{2}}$ (which is irrational, by assumption), and $b = \sqrt{2}\text{.}$ Then, $a^b = 2$ is rational, and we are done.

This proof is very subtle. Notice that this proof doesn't actual show that $\sqrt{2}^{\sqrt{2}}$ is rational or not (in fact, it is not). Rather, it shows that either way, we can construct the desired result.

Subsection 5.4.3 Remark on Existence Theorems

Sometimes, existence theorems seem unhelpful. It seems intuitive that if there is a method to determine how to find something, then that method can just be used to determine the solution, without considering whether it exists. However, this can sometimes lead to pitfalls.

Subsection 5.4.4 False Existence Proof

Fact 5.4.3. False proof 1 is the largest positive Integer (Perron's paradox).

1 is the largest positive integer.

This result is clearly false, as there is no largest positive integer. However, if we assume that a largest positive integer does exist, then we can “prove” the result.

Proof.

Let $n$ be the largest positive integer. Then, $n$ is a positive integer, so $n \geq 1\text{.}$ Then, multiplying both sides by $n$ (which is positive), we have $n^2 \geq n\text{.}$ Also, $n$ is a positive integer so $n^2$ is also a positive integer. Since $n$ is the largest positive integer, we have $n^2 \leq n\text{.}$ Thus, $n^2 = n\text{,}$ so $n^2 - n = 0\text{,}$ so $n(n - 1) = 0\text{.}$ The solutions to this equation are $n = 0, 1\text{.}$ Since 0 is not a positive integer, this implies that $n = 1\text{.}$

The only mistake in this proof is the initial assumption, that a largest positive integer $n$ exists. In fact, this theorem proves the implication, “if the largest positive integer exists, then it is 1”. This implication is true, however, the hypothesis is false.

The more general principle is that if you assume a false statment, then you can prove anything, because the condition $\text{false} \implies Q$ is true always. This false proof is called Perron's paradox, named after German mathematician Oskar Perron.