
# 7.4: Constructive Versus Non-Constructive Proofs


Existence proofs fall into two categories: constructive and non-constructive. Constructive proofs display an explicit example that proves the theorem; non-constructive proofs prove an example exists without actually giving it. We illustrate the difference with two proofs of the same fact: There exist irrational numbers x and y (possibly equal) for which $$x^y$$ is rational.

Proposition There exist irrational numbers x, y for which $$x^y$$ is rational.

Proof. Let $$x = \sqrt{2}^{\sqrt{2}}$$ and $$y = \sqrt{2}$$. We know y is irrational, but it is not clear whether x is rational or irrational. On one hand, if x is irrational, then we have an irrational number to an irrational power that is rational:

$$x^y = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^(\sqrt{2}\sqrt{2}) = \sqrt{2}^2 = 2$$

On the other hand, if x is rational, then $$y^y = \sqrt{2}^{\sqrt{2}} = x$$ is rational. Either way, we have an irrational number to an irrational power that is rational.

The above is a classic example of a non-constructive proof. It shows that there exist irrational numbers x and y for which $$x^y$$ is rational without actually producing (or constructing) an example. It convinces us that one of $$(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}$$ or $$\sqrt{2}^{\sqrt{2}}$$ is an irrational number to an irrational power that is rational, but it does not say which one is the correct example. It thus proves that an example exists without explicitly stating one.

Next comes a constructive proof of this statement, one that produces (or constructs) two explicit irrational numbers x, y for which $$x^y$$ is rational.

Proposition There exist irrational numbers x, y for which $$x^y$$ is rational.

Proof. Let $$x = \sqrt{2}$$ and $$y = log_{2} 9$$. Then

$$x^y = \sqrt{2}^{log_{2} 9} =\sqrt{2}^{log_{2} 3^2} = \sqrt{2}^{2log_{2} 3} = (\sqrt{2}^{2})^{log_{2} 3} = 2^{log_{2} 3} = 3$$.

As 3 is rational, we have shown that $$x^y = 3$$ is rational.

We know that $$x = \sqrt{2}$$ is irrational. The proof will be complete if we can show that $$y = log_{2} 9$$ is irrational. Suppose for the sake of contradiction that $$log_{2} 9$$ is rational, so there are integers a and b for which $$\frac{a}{b} = log_{2} 9$$. This means $$2^{a/b} = 9$$, so $$(2^{a/b})^{b} = 9^b$$, which reduces to $$2^a = 9^b$$. But $$2^a$$ is even,while $$9^b$$ is odd (because it is the product of the odd number 9 with itself b times). This is a contradiction; the proof is complete.

This existence proof has inside of it a separate proof (by contradiction) that $$log_{2} 9$$ is irrational. Such combinations of proof techniques are, of course, typical.

Be alert to constructive and non-constructive proofs as you read proofs in other books and articles, as well as to the possibility of crafting such proofs of your own.