Here’s a cheat sheet to help you with proofs by contradiction, explaining the key steps, common pitfalls, and things to watch out for:
Proof by Contradiction Cheat Sheet
What is Proof by Contradiction?
A proof by contradiction is a method where you assume the opposite (negation) of what you want to prove. Then, you logically deduce consequences from that assumption. If this leads to a contradiction, it means your original assumption (the negation) must be false, so the statement you're trying to prove must be true.
Steps to Follow:
- Identify the Statement to Prove (P): Clearly state the proposition you're trying to prove.
- Negate the Statement (~P): Assume the opposite of what you're trying to prove. This is key—write down the negation of the original statement.
- Start Reasoning from the Negation: Based on this assumption, work through logical steps using definitions, theorems, or prior results. Derive consequences from this assumption.
- Reach a Contradiction: Show that this assumption leads to something impossible or contradictory:
- Contradicts a known fact or theorem.
- Contradicts your initial assumptions (both within the problem and any givens).
- Leads to an absurd conclusion (e.g., \(1 = 0\)).
- Conclude the Original Statement is True: Since assuming ~P leads to a contradiction, the assumption must be false. Therefore, P (the original statement) must be true.
Pitfalls to Avoid:
- Negating Incorrectly: Be very careful with negating statements. Sometimes the negation of a conditional statement or a universal statement can be tricky:
- The negation of "All X are Y" is "There exists an X that is not Y."
- The negation of "If P then Q" is "P and not Q."
- Forgetting to State the Contradiction: You need to clearly state what the contradiction is. Often students don’t explicitly write down what’s contradictory, which weakens the proof.
- Invalid Logical Steps: Every step after you assume the negation must follow logically. If you make a logical error, your conclusion (contradiction) is not valid. Be rigorous!
Things to Watch Out For:
- Strong Setup: Before starting the proof by contradiction, make sure you clearly understand the structure of the statement and any assumptions or givens.
- Overcomplicating the Proof: Sometimes students try too many complex steps. Keep it simple: the contradiction might come sooner than expected.
- Know Common Contradictions: In many cases, contradictions come in the form of:
- Contradicting the problem’s givens.
- Violating known mathematical principles (e.g., an even number being odd).
- Producing absurd results (e.g., dividing by zero, or 1 = 0).