Lesson 7.3 — Proof by Contradiction

Assume the opposite of what you want to prove. Derive a contradiction. Conclude the original.

The Trick

Direct proof walks forward — premises to conclusion. Proof by contradiction walks backward.

The setup:

1. You want to prove some sentence — call it X.
2. Instead of trying to derive X directly, you assume the opposite: ¬X.
3. You combine ¬X with your premises and start deriving consequences.
4. Eventually you reach a sentence that contradicts something else on the page — typically you get both Y and ¬Y.
5. Contradictions can't be true. So your assumption (¬X) must have been wrong.
6. Therefore X is true.

That's the whole structure. The Latin name is reductio ad absurdum — "reduction to the absurd."

A Worked Example, Step by Step

We'll prove that Modus Tollens is valid — but using contradiction instead of just citing the rule. This shows how the contradiction technique can derive other rules.

Setup:

• Premise 1: P → Q   (e.g., "Mom always smiles when she's happy.")
• Premise 2: ¬Q   (e.g., "Mom is not smiling.")
• Goal: prove ¬P   (e.g., "Mom is not happy.")

Click through the proof one step at a time.

Watch the structure: assumption ¬¬P (which is just P) leads, via MP, to Q. But we already have ¬Q. That's the contradiction. Since the assumption produced a contradiction, the assumption itself was the problem — meaning ¬P must be true after all.

When to Use It

Proof by contradiction is the right tool when:

1. Direct proof is hard or unclear. When you don't see how to derive the conclusion forward, try assuming its opposite and see what breaks.
2. The conclusion is negative. Statements like "X doesn't exist" or "there's no such Y" are often easier to prove by assuming the opposite (that X DOES exist) and deriving a contradiction.
3. You're proving an "impossible" claim. Mathematicians use contradiction to prove things like "there's no largest prime number" — they assume there IS one, then derive a paradox.

Why It Works

A contradiction (any statement of the form Y ∧ ¬Y) is always false. It can't be true in any consistent system. So if your assumption forced you into a contradiction, the only way out is to reject the assumption.

Logically: (¬X → ⊥) → X. If assuming ¬X leads to a contradiction (⊥), then X must be true.

A Famous Example (Outside Sentential Logic)

The most famous proof by contradiction in mathematics shows that √2 can't be written as a fraction. The proof:

1. Assume √2 can be written as a/b (the opposite of what we want to prove).
2. Without loss of generality, assume a/b is in lowest terms (no common factors).
3. Then 2 = a²/b², so a² = 2b².
4. So a² is even.
5. If a² is even, a must be even (only way).
6. So write a = 2k. Then a² = 4k².
7. But a² = 2b², so 4k² = 2b², meaning b² = 2k².
8. So b² is even, meaning b is even.
9. But step 2 said a and b have no common factor. Both being even means they share factor 2. Contradiction.
10. So our assumption was wrong: √2 can NOT be written as a fraction.

This was proved by the ancient Greeks. It's the same shape as our little Mom example: assume opposite, derive contradiction, conclude original.

Tricky Bits

1. The contradiction has to be REAL. A contradiction is two sentences that can't both be true at once — usually Y and ¬Y. If you just get a surprising or weird sentence, that's not a contradiction. Don't fake it.

2. Make sure your assumption was used. If your contradiction comes purely from the premises (without using the assumed ¬X), then the premises were already inconsistent and your proof doesn't actually establish X. The assumption needs to play a load-bearing role.

3. Double-negation cancels. When you "assume the opposite of ¬P," you assume ¬¬P, which is just P. The double-negation cancellation is built into the technique.

Recap

• Proof by contradiction: assume the opposite of what you want to prove; derive a contradiction; conclude the original.
• The contradiction must be a real one (Y ∧ ¬Y), not just an unexpected result.
• Useful when direct proof is hard, when the conclusion is negative, or when proving impossibility claims.
• Same building blocks as direct proof (MP, MT, etc.) — different framing.