jump to navigation

By way of contradiction May 5, 2013

Posted by Ezra Resnick in Logic, Math.
trackback

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

Advertisements

Comments»

1. tiffany267 - May 5, 2013

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

Ezra Resnick - May 5, 2013

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

2. Peter - March 8, 2014

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.

3. Adam - January 17, 2017

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

Ezra Resnick - January 17, 2017

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s