Proof by contradiction - Cheat sheet

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:

1. Identify the Statement to Prove (P): Clearly state the proposition you're trying to prove.
2. 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.
3. Start Reasoning from the Negation: Based on this assumption, work through logical steps using definitions, theorems, or prior results. Derive consequences from this assumption.
4. 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\)).
5. 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).