##
By way of contradiction *May 5, 2013*

*Posted by Ezra Resnick in Logic, Math.*

trackback

trackback

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?*

LOL interesting post. Can’t wait to see more logic-related content 🙂

Thanks, Tiffany! You can see all my logic-related posts here.

Yes. Convert the negated universal quantifier into an existentially quantified assertion for the existence of such a proposition. The demonstrated existence of p (given you accept the argument for p as given) then directly proves the case for the existence of such a proposition.

Hi there, what does the symbol mean at the top of the page? The cross with the 4 dots? Thanks

This symbol is sometimes used in mathematical proofs to indicate a contradiction.