Prove statements by showing their negation leads to impossibility
Proof by contradiction (also called reductio ad absurdum) is a powerful indirect technique. Instead of proving P directly, assume ¬P and show this leads to a logical impossibility. Since mathematics cannot tolerate contradictions, ¬P must be false, so P is true.
This technique is especially useful for non-existence, irrationality, and infinitude statements where a direct proof would have no natural starting point.
See the logical structure of a contradiction proof: assume ¬P, derive consequences, reach an impossibility, conclude P.
Watch how proof by contradiction flows: we assume the opposite, derive consequences, and reach an impossibility.
The contradiction proves our assumption (¬P) was false. Since ¬P is false, P must be true! This indirect approach often works when direct proof is difficult.
Key insight: By assuming the opposite of what we want to prove, we often gain concrete information to work with. The negation gives us an object (a rational representation, a finite list, etc.) that we can manipulate until it self-destructs.
The most famous contradiction proof: assume √2 = a/b in lowest terms, then show both a and b must be even -- contradicting "lowest terms."
This classic proof shows that √2 cannot be written as a fraction. Watch the "lowest terms" badge as we progress!
We want to prove that √2 is irrational (cannot be written as a fraction).
Key insight: The assumption "√2 is rational" gives us integers a and b to manipulate. Squaring both sides and chasing parity produces two contradictory facts: the fraction is in lowest terms AND both numerator and denominator are even.
Euclid's classic proof: assume finitely many primes p1, p2, ..., pk. Then consider N = p1 * p2 * ... * pk + 1. No prime on the list divides N -- contradiction.
Suppose we had a "complete list" of all primes. We'll construct a number N that contradicts this assumption!
Since N = (p₁ × p₂ × ... × pₖ) + 1, dividing N by any pᵢ gives remainder 1. The product part is divisible by pᵢ, but then we added 1, leaving remainder 1. This guarantees N cannot be divisible by any prime in our list!
Key insight: The number N = p1*p2*...*pk + 1 is not necessarily prime itself -- but it must have a prime factor not on the list, since dividing by any listed prime leaves remainder 1.