# 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. []

# Methods of Irrationality

Being a mathematician requires you to think in strange ways.

For starters, you might think that mathematicians spend all day pondering purely theoretical things that only exist in Mathematical abstraction, right? Well, it can get even stranger than that: sometimes we have to think about things that don’t exist, even in the abstraction! It’s called a proof by contradiction, and here’s an example:

Theorem: The number $$\sqrt{2}$$ is irrational.

Proof: To prove that $$\sqrt{2}$$ is irrational, we have to show that we can never write it as a ratio of integers, $$\sqrt{2}=a/b$$. So let’s assume we can find such a fraction and see where it leads us.

Let’s cancel common factors in the numerator and denominator so that $$a/b$$ is in lowest terms. Squaring our equation shows that $$a^2=2b^2$$, so $$a^2$$ is even and so $$a$$ itself is even. Since $$a/b$$ is in lowest terms, $$b$$ must be odd.

Since $$a$$ is even, $$a^2$$ is in fact divisible by 4. On the other hand, since $$b$$ is odd, $$2b^2$$ is not divisible by 4. But then the integer $$a^2=2b^2$$ is both divisible by 4 and not divisible by 4, which is absurd! The only explanation for this contradiction is that our original assumption—that $$\sqrt{2}$$ is rational—is false. So we’re done with the proof! Notice that we spent most of our effort reasoning about integers that never existed (specifically $$a$$ and $$b$$).

But that’s not the only twisted thing about Mathematical thinking. Here’s a delightfully short yet aggravatingly unsatisfying proof:

Theorem: There exist irrational numbers $$x$$ and $$y$$ such that $$x^y$$ is rational.

Proof: We already know that $$\sqrt{2}$$ is irrational, so maybe we can use $$\sqrt{2}^{\sqrt{2}}$$. Is this number rational? If it is, then we’re done: $$x=\sqrt{2},y=\sqrt{2}$$ solves the problem. But what if $$\sqrt{2}^{\sqrt{2}}$$ is irrational? In this case, I claim $$x=\sqrt{2}^{\sqrt{2}},y=\sqrt{2}$$ works: indeed, $$\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot\sqrt{2}} = \sqrt{2}^2 = 2,$$ which is rational. In either case the required numbers $$x$$ and $$y$$ exist, so this completes the proof.

But wait; which is it? The proof shows us that one of the pairs $$x=\sqrt{2},y=\sqrt{2}$$ or $$x=\sqrt{2}^{\sqrt{2}},y=\sqrt{2}$$ works, but it doesn’t tell us which one! So, have we proven the theorem? Yes, technically, but only nonconstructively.

Frustrating, isn’t it?