Proof by Contradiction

Mathematical Logic · Axiom Academy

Master the powerful technique of reductio ad absurdum - proving a statement by showing its negation leads to impossibility 1. The Core Idea: Proving Through Impossibility The Strategy: To prove a statement P is true, we: Derive logical consequences from this assumption Show these consequences lead to a contradiction Conclude that our assumption must be wrong, so P must be true 2. Structure of a Contradiction Proof A proof by contradiction follows a specific template: 3. Classic Example: 2 is Irrational Theorem: 2 is irrational (cannot be expressed as a fraction of integers). Proof: Assume for contradiction that 2 is rational. Then 2 = a/b where a, b are integers with no common factors (in lowest terms). Squaring: 2 = a²/b², so 2b² = a² This means a² is even, which implies a is even (if a were odd, a² would be odd). So a = 2k for some integer k. Substituting: 2b² = (2k)² = 4k², thus b² = 2k² This means b² is even, which implies b is even. Conclusion: Our assumption was wrong. Therefore 2 is irrational. 4. Another Classic: Infinitely Many Primes Theorem: There are infinitely many prime numbers. Proof: Assume for contradiction that there are only finitely many primes. List them all: p&sub1;, p&sub2;, ..., p n;. Consider the number N = (p&sub1; × p&sub2; × ... × p n;) + 1 This number N is greater than all the primes in our list. When we divide N by any prime p i; in our list, we get remainder 1.

This is the written version of the interactive lesson above. See the full Mathematical Logic course.