By way of contradiction May 5, 2013Posted by Ezra Resnick in Logic, Math.
An indirect proof (or proof by contradiction) establishes the truth of a proposition by showing that the proposition’s negation implies a contradiction. For example, we can indirectly prove that the square root of 2 is irrational (i.e., it cannot be expressed as a ratio a/b where a and b are integers) by assuming the opposite — that √2 can be expressed as a ratio of integers — and showing that such an assumption leads to a contradiction (e.g., that b is both even and odd).
Some people find indirect proofs unsatisfying, or even a bit suspicious: it feels like we’ve been cheated out of understanding why the proposition is true. Direct proofs seem more intuitive and dependable. This raises the question: Does every proposition that can be proved indirectly have a direct proof as well? Or are there propositions that can be proved indirectly, for which no direct proof exists?
Before attempting to answer that question, let us first consider this humble proposition:
(p) This proposition cannot be proved directly.
We can prove proposition p is true — indirectly. Start by assuming the opposite, that is, assume there exists a direct proof of p. In particular, that means p is true. But p states that there is no direct proof of p — contradicting our assumption. So our assumption must be false; hence p is true.
Let us now attempt to prove the following proposition:
(q) Not all propositions that can be proved indirectly can also be proved directly.
We shall prove the truth of proposition q (you guessed it) indirectly. Assume the opposite: that is, assume any proposition that can be proved indirectly can also be proved directly. Then, since p can be proved indirectly (as demonstrated above), there must also exist a direct proof of p. However, the existence of such a proof contradicts (the proven) proposition p! So our assumption must be false — and q is true.
Ah, but the question remains: Can q be proved directly?