Recipe

Prove a claim by contradiction

Use when: a direct forward chain from hypothesis to conclusion isn't obvious — especially when the claim asserts that something does NOT exist or CANNOT happen

Goal: a valid chain of steps from the claim's negation to an outright logical impossibility, which forces the original claim to be true

Taught in Reading and writing a proof

1. 1

   Write the exact negation of the claim. A quantifier flips every time the negation moves past it: \neg(\forall x,\ P(x)) becomes \exists x,\ \neg P(x), and \neg(\exists x,\ P(x)) becomes \forall x,\ \neg P(x).

   Example

   The claim "no smallest positive rational number exists" is \neg\big(\exists\, r\in\mathbb Q,\ r>0 \text{ and } r \text{ is smallest}\big) on its face, so its negation flips right back to the existence statement: "there exists a positive rational r that IS the smallest positive rational."

   • the claim is a "for all" statement — its negation becomes a "there exists" statement.
   • the claim already has the form "there is no X" (itself a negation) — negating it produces the plain existence statement "there is an X."

   Why: a sloppy negation — swapping "everyone" for "someone" by accident — aims every later step at the wrong target, even if each one is individually valid.

2. 2

   Take the negated statement as a working hypothesis. If it asserts something exists, give it a name — a symbol standing for an unknown object, not a specific number.

   Example

   Assume: there exists r\in\mathbb Q with r>0 such that r is the smallest positive rational.

   Why: naming the hypothetical object is what lets the next steps reason about it concretely, the same role Step 1 of a direct proof plays by fixing an arbitrary element.

3. 3

   Chain valid, justified steps from the assumption until you reach a statement of the form R \wedge \neg R, or a plain falsehood like 0=1.

   Example

   \dfrac r2 is rational (half a rational is rational) and positive (half a positive number is positive), and since r>0, \dfrac r2 < r — so \dfrac r2 is a positive rational strictly smaller than r.

   Why: only an actual logical impossibility forces the blame onto the assumption; a merely surprising or unlikely consequence doesn't finish the proof.

4. 4

   State explicitly which two statements contradict each other, conclude the Step 2 assumption must be false, and then state the conclusion in terms of the ORIGINAL claim, not just "the assumption is false."

   Example

   "r is the smallest positive rational" and "\dfrac r2 is a smaller positive rational" can't both hold — that's the impossibility. So the assumption is false, and no smallest positive rational number exists, exactly the original claim.

   Why: this is the step that actually finishes the logical move: since every step from the assumption was valid, the only thing that could be false is the assumption itself — but only if the final line explicitly returns to what was originally claimed.