Logic Under Construction

In last week’s discussion of proofs by contradiction and nonconstructive proofs, we showed:

Theorem: There exist irrational numbers $$x$$ and $$y$$ with the property that $$x^y$$ is rational.

However, our proof was nonconstructive: it did not pinpoint explicit values for $$x$$ and $$y$$ that satisfy the condition, instead proving only that such numbers must exist. Would a more constructive proof be more satisfying? Let’s see! I claim $$x=\sqrt{2}$$ and $$y=\log_2 9$$ work, because $$\sqrt{2}$$ we already know to be irrational, $$y=\log_2 9$$ can be similarly proved to be irrational (try this!), and $$x^y = \sqrt{2}^{\log_2 9} = \sqrt{2}^{\log_{\sqrt{2}}3}=3,$$ which is rational.

Let’s further discuss why last week’s proof was less satisfying. The following rephrasing of this proof may help shed some light on the situation:

Proof: Assume the theorem were false, so that any time $$x$$ and $$y$$ were irrational, $$x^y$$ would also be irrational. This would imply that $$\sqrt{2}^{\sqrt{2}}$$ would be irrational, and by applying our assumption again, $$\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}$$ would also be irrational. But this last number equals 2, which is rational. This contradiction disproves our assumption and thereby proves the theorem, QED.

So perhaps this argument seems less satisfactory simply because it is, at its core, a proof by contradiction. It does not give us evidence for the positive statement “$$x$$ and $$y$$ exist”, but instead only for the negative statement “$$x$$ and $$y$$ don’t not exist.” (Note the double negative.) This distinction is subtle, but a similar phenomenon can be found in the English language: the double negative “not bad” does not mean “good” but instead occupies a hazy middle-ground between the two extremes. And even though we don’t usually think of such a middle-ground existing between logic’s “true” and “false”, proofs by contradiction fit naturally into this haze. In fact, these ideas motivate a whole branch of mathematical logic called Constructive logic that disallows double negatives and proofs by contradiction, instead requiring concrete, constructive justifications for all statements.

But wait; last week’s proof that $$\sqrt{2}$$ is irrational used contradiction, and therefore is not acceptable in constructive logic. Can we prove this statement constructively? We must show that $$\sqrt{2}$$ is not equal to any rational number; what does it even mean to do this constructively? First, we turn it into a positive statement: we must show that $$\sqrt{2}$$ is unequal to every rational number. And how do we constructively prove that two numbers are unequal? By showing that they are measurably far apart. So, here is a sketch of a constructive proof: $$\sqrt{2}$$ is unequal to every rational number $$a/b$$ because $$\left|\sqrt{2} – \frac{a}{b}\right| \ge \frac{1}{3b^2}.$$ See if you can verify this inequality![1]

PS. In case you are still wondering whether $$\sqrt{2}^{\sqrt{2}}$$ is rational or irrational: It is irrational (moreover, transcendental), but the only proof that I know uses a very difficult theorem of Gelfond and Schneider.

Notes

1. This inequality would also have to be proven in a constructive manner. See these Wikipedia articles for more information: Intuitionistic logic (another name for Constructive logic) and Square root of 2: Constructive proof. []