Prove statements by showing their negation leads to impossibility
Assume the opposite of what you want, follow the consequences, and watch them collapse into nonsense. The thing you assumed false must have been true all along.
Pick an example and play or step through the flow: 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.
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.
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.
Step through the argument that √2 = a/b in lowest terms forces both a and b to be even, which can’t happen.
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).
The most famous contradiction proof: assume √2 = a/b in lowest terms, then show both a and b must be even -- contradicting "lowest terms."
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.
Choose a list of primes, calculate N, and check divisibility. No prime on your list divides N.
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!
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.
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.
Spot a mistake or have an idea?