Proof by Contradiction

Math for CS · Axiom Academy

Assume the opposite and show it leads to an impossibility A proof by contradiction works by assuming the negation of what you want to prove, then showing this assumption leads to a logical contradiction (something that is both true and false). Use logical deduction to derive consequences Show you've reached a contradiction: P ∧ ¬P Conclude that ¬Q must be false, so Q is true Claim: √2 is irrational (cannot be expressed as a ratio of integers). Assume the opposite: √2 is rational, so √2 = p/q where p and q are integers with no common factors (lowest terms) Square both sides: 2 = p²/q², so 2q² = p² Deduce about p: Since p² = 2q², p² is even, which means p must be even Substitute: If p = 2k, then 2q² = (2k)² = 4k², so q² = 2k² Deduce about q: Since q² = 2k², q² is even, which means q must be even Reach contradiction: Both p and q are even, contradicting that p/q is in lowest terms! Conclusion: Our assumption was wrong. √2 must be irrational. QED Claim: There is no largest prime number (infinitely many primes exist). Assume the opposite: There is a largest prime number, call it p Consider the number: N = (2 × 3 × 5 × 7 × ... × p) + 1 Analyze N: When we divide N by any prime up to p, we get remainder 1 Two cases: Either N is prime (but N > p, contradicting that p is the largest prime) Or N has a prime factor (but that prime can't be any of 2, 3, ..., p) Reach contradiction: Either way, there's a prime larger than p!

This is the written version of the interactive lesson above. See the full Math for CS course.