Proof by Contradiction

In this post we’ll learn one of the most elegant and beautiful logical weapons that mathematicians can wield.  Every mathematician develops a toolbox for proving theorems, and this is one of the most powerful.  Its Latin name is reductio ad absurdum, and its English name is proof by contradiction.

How it works

Suppose we’re trying to prove that a statement (call it A) is true.  Also suppose that there are other statements that have already been proven true.  It doesn’t really matter what these other statements are, except for the fact that they have already been proven completely true.

What we do is suppose that the statement A is false.  There is nothing wrong with supposing something, so long as we never confuse it with something that is proven false.  Now, from this supposition we can start to derive other “valid” statements (scare quotes here to remind us that the subsequent statements are valid only if the supposition is correct (i.e., if A is actually false)).  Using logical deductions from our supposition, we want to arrive at a conclusion that contradicts something else that we know is true.

For example, call one of our already-proven-true statements B, and then suppose that A is false.  If we can use this supposition to show that B is false, then we have a contradiction because B is both true (already proven true) and false (just proven false)!  This is clearly not okay, and it tells us that the initial assumption was wrong.  What was the initial assumption?  That A was false.  Thus, A must be true!  Think about this one, it’s important.  In the meantime, here is a very trivial example (a better example is the proof of infinity primes).

Example

Suppose it is already proven that 0=0, and 0 doesn’t equal anything else.  I.e., zero only equals zero.  (This is obvious, but remember that we’re just looking at the logic here, not the math).  Suppose it is also known that we can add and subtract numbers in the normal way.  We can now ask the following trivial question: does 1=2?  Clearly the answer is no, but how can we prove it?  (obviousness is not a mathematical proof).

First, we assume the opposite.  Suppose that 1=2.  If that’s the case, then let’s see what happens when we subtract 1 from both sides (there’s nothing wrong with doing that).  Then 0=1.  But, we already know that zero equals zero and nothing else!  Therefore the conclusion that we’ve drawn here, namely that 0=1, is a contradiction!  This means our supposition was impossible.  What was our supposition?  That 1=2.  Thus it is the case that 1 does not equal 2.

Yes, this is trivial, but we use this method all the time for proving cooler stuff.  For example, it’s used in lesson 13 for showing that there are, in fact, at least two fundamentally different kinds of infinities, and again in lesson 14 to show that there are infinitely many different kinds of infinity!

Advertisements

About TrueBeautyOfMath

Lover of math, and lover of teaching it.
This entry was posted in Mathematics. Bookmark the permalink.

2 Responses to Proof by Contradiction

  1. Ricardo says:

    You really make it apaepr so easy together with your presentation however I to find this topic to be actually one thing that I think I’d never understand. It kind of feels too complicated and extremely large for me. I am looking ahead in your subsequent post, I will attempt to get the hold of it!

    • Hi Ricardo, I’m glad you’re liking the site. As for this topic, let me try again here in this reply, since I think the length of my post may have made the topic seem more complicated than it actually is.

      Suppose we want to ask whether or not some statement is true. We might as well call this statement “S”. “S” can be any statement, and it must either be true or not true. For example, “All fish are blue” is a statement, so “S” could be “All fish are blue”. Now, I strongly believe that this statement is false, but how do I prove it?

      In order to prove that “All fish are blue” is false, I need some other information. Suppose that the two statements “one plus one equals two” and “There are red fish if one plus one equals two”, are already proven to be true. In other words, suppose that we, the human race, already know with certainty that “one plus one equals two” is true, and that “there are red fish if one plus one equals two” is true. Now we can inquire about the truth or falseness of “all fish are blue”. In this proof, we’ll use proof by contradiction, even though it’s not totally necessary.

      What we do is SUPPOSE that “all fish are blue” is true, and then by deriving true statements from that supposition, we’ll come to a conclusion that contradicts one of our two pre-established truths. By doing this, we’ll have proved that our supposition is impossible, and since every statement is either true or not true, we’ll find that “all fish are blue” must be false. Let’s see this.

      Suppose “all fish are blue” is true. Then we know that there are no red fish (because all fish are blue). But if there are no red fish, then one plus one does not equal two. This follows from our pre-established truth “there are red fish if one plus one equals two”, since if one plus one did equal two then there would be red fish, but we’ve already seen that there are no red fish (because they’re all blue). But this contradicts our other pre-established fact, which says that one plus one does equal two. Thus, our supposition “all fish are blue” has led us to the conclusion that one plus one does not equal two, which contradicts the truth that we’re assuming exists, which is that one plus one does equal two. Therefore our supposition must have been wrong, which means it must be the case that “all fish are blue” is false. And that’s the proof!

      Admittedly, this is a weird example (it’s just the first one I’ve thought of), but I do think it shows the logic. If it doesn’t help clarify things then let me know and I’ll try again!

      Cheers

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