🔥

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).