Proof by Contradiction
Proof by contradiction (reductio ad absurdum) is a logical proof technique in which one assumes the negation of the statement to be proved, then derives a logical contradiction, thereby establishing the original statement's truth. It relies on the law of the excluded middle: a proposition is either true or false, with no middle ground. Classic examples include proofs that √2 is irrational and that there are infinitely many prime numbers.
Worked Example
Problem
Prove that √2 is irrational.
Solution
Step 1 (Assume negation): Suppose √2 is rational. Then √2 = p/q where p, q ∈ ℤ, q ≠ 0, and gcd(p, q) = 1 (fraction in lowest terms). Step 2: Square both sides: 2 = p²/q², so p² = 2q². Step 3: p² is even, so p must be even (if p were odd, p² would be odd). Write p = 2m. Step 4: Then (2m)² = 2q², so 4m² = 2q², giving q² = 2m². Step 5: q² is even, so q must be even. Step 6 (Contradiction): Both p and q are even, contradicting gcd(p, q) = 1. Conclusion: The assumption that √2 is rational is false.
Answer
√2 is irrational. (Proven by contradiction.)
Comparison of Proof Techniques in Discrete Mathematics
| Technique | Assumption | Mechanism | Best Used When |
|---|---|---|---|
| Direct Proof | P is true | Derive Q step by step | Clear algebraic chain exists |
| Proof by Contradiction | Negate the conclusion | Reach absurdity | Negation is easier to manipulate |
| Proof by Contrapositive | Assume ¬Q | Derive ¬P | ¬Q → ¬P is simpler than P → Q |
| Mathematical Induction | P(1) true + P(k) true | Extend to P(k+1) | Statement involves all naturals |
| Existence Proof | None | Construct or count | Need to show something exists |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Mathematical Induction
Mathematical induction is a proof technique used to establish that a statement P(n) holds for all natural numbers n by verifying a base case and then proving an inductive step. In the inductive step, one assumes P(k) is true (the inductive hypothesis) and derives that P(k+1) must also be true. This technique is analogous to a line of dominoes: knocking the first triggers an infinite chain.
Pigeonhole Principle
The Pigeonhole Principle states that if n items are placed into m containers and n > m, then at least one container must hold more than one item. It is a fundamental combinatorial tool used to prove the existence of certain configurations without constructing them explicitly. Applications range from proving that two people in a city share a birthday to guaranteeing collisions in hash functions.
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
The Latin phrase reductio ad absurdum means "reduction to the absurd." The technique was used extensively by ancient Greek mathematicians, including Euclid (c. 300 BCE) in his proof that there are infinitely many primes, and by Aristotle who discussed it in Prior Analytics.