Proof by Contradiction: Basic Idea
What You'll Learn
You'll learn how to prove a statement is true by showing that assuming it's false leads to a logical impossibility.
The Core Strategy
Proof by contradiction is a powerful technique where instead of proving a statement directly, you:
- Assume the opposite of what you want to prove
- Follow the logical consequences of that assumption
- Reach an impossibility (a contradiction)
- Conclude the original statement must be true
Think of it like a detective story: if assuming "the butler didn't do it" leads you to discover he was in two places at once (impossible!), you conclude the butler must have done it.
Why It Works
This method relies on a fundamental principle of logic: a statement is either true or false, never both. If assuming "false" produces nonsense, then "true" is the only remaining option.
The contradiction you derive might be:
- Two conflicting facts (like "x > 0" and "x < 0" simultaneously)
- A statement contradicting a known theorem
- A violation of a given hypothesis
- Any logical impossibility
A Simple Sketch
Claim: There is no largest prime number.
Contradiction approach:
- Assume the opposite: suppose there is a largest prime, call it P
- Follow the logic... (you'd construct a number that must be prime and larger than P)
- Reach impossibility: we found a prime larger than the "largest" prime!
- Conclude: our assumption was wrong; there is no largest prime
Notice you never proved the statement directly—you showed that its negation can't possibly be true.
Key Takeaway: Proof by contradiction assumes the statement is false, derives a logical impossibility from that assumption, and concludes the statement must therefore be true.