The proofs we've looked at so far have been all about directly proving something is true. That seems pretty obvious, but sometimes it's simpler to prove something isn't true. The truth is fun and all, but now it's time to put on your best fibbing face and tell some straight-up lies.
In a proof by contradiction (sometimes called an indirect proof), we prove our conclusion by showing that the opposite is impossible. To do this, we assume that the thing we're trying to prove is not true, and then show how that assumption leads to some kind of logical contradiction.
It's like trying to prove to your parents that you finished reading The Catcher in the Rye for your English class. They won't let you take the family station wagon to the movies this weekend otherwise, so you've got a lot riding on this proof.
You can't let them see inside your head to prove you read the book, so instead, you might show them a copy of your English midterm. "See? I got an A," you might say. "If I hadn't done the reading, there's no way I could've got that grade. Therefore, I did the reading."
You assumed the opposite was true (that you didn't do the reading), then you showed how your A on the midterm contradicted that assumption. Your parents would be suitably impressed by your proof by contradiction skills and hopefully let you off the hook.
Believe it or not, this type of proof is used fairly frequently by mathematicians. Proof by contradiction forms the bedrock of all kinds of theorems we take for granted, like the fact that intersecting lines cross at only one point, or that the square root of 2 is an irrational number.
To rock a proof by contradiction, follow these steps:
- Assume the statement you're trying to prove is false.
- Try to prove the opposite statement (i.e., the negation).
- Come across a contradiction somewhere in your proof.
- State that since the contradiction disproves the negation, the original statement must be true.
Let's take these steps for a quick test drive.
Sample Problem
Use contradiction to prove that there are an infinite number of positive integers.
Obviously, this would be obscenely hard to prove normally—how do we count to infinity? But with contradiction, it's actually pretty straightforward.
1. Assume the statement you're trying to prove is false.
Okay, let's assume that there isn't an infinite number of positive integers. In other words, there's a finite number of them, which means we should be able to count them all.
2. Try to prove the opposite statement (i.e., the negation).
Now we're trying to prove there's a finite number of positive integers. That means there must be one integer that's the biggest, right? "Finite" means they end somewhere, so there must be one integer at the end of the line.
We'll call this king of integers N. We should be able to theoretically count all the positive integers like this:
I = 1, 2, 3, 4, …, N
So far, so good.
3. Come across a contradiction somewhere in your proof.
We can always add 1 to any number. What happens if we add 1 to N? We already decided N was just some really huge integer, so there's nothing stopping us from adding 1 to it.
N + 1
Hey, wait a sec: N + 1 must, by definition, be larger than N. Or, in more math-y language:
N + 1 > N
Again, that's just how numbers work. Adding 1 makes any number larger. Plus, N + 1 must be an integer, because that's what happens when we add two integers together.
But since there exists a number N + 1 that's bigger than N, and since N + 1 must also be an integer, we just broke our proof. This is a contradiction: N can't be the biggest integer and also not the biggest integer.
That must mean there's no greatest integer, because we can keep on adding 1 as many times as we want.
4. State that since the contradiction disproves the negation, the original statement must be true.
Now we formalize our proof with some fancy language:
"Since it's always possible to find an integer N + 1 that's greater than an integer N, this contradicts the supposition that there's a finite number of positive integers. Hence, our original proposition is true: there's an infinite number of positive integers."
By the way, a proposition is just the statement we're proposing to be true (i.e., the original statement we're proving). A supposition is the statement we're supposing is true (i.e., our assumed opposite statement). We should always end our contradiction proofs with that same format we used above:
Since __________, this contradicts the supposition that __________. Hence, our original proposition is true: __________.
Like a mathematical Mad Lib, we can just fill in the blanks with the details from our actual problem.