Home All Subjects Progress Videos Graphics

Progress

241 / 241 subjects

Phases

29-02 — Proof by Contradiction

Phase: 29 — Proof Techniques Subject: 29-02 Prerequisites: 29-01 (Direct Proof and Contrapositive), 00-08 (Basic Number Theory) Next subject: 29-03 — Induction Deep Dive

Learning Objectives

By the end of this subject, you will be able to:

  1. Structure a proof by contradiction (reductio ad absurdum)
  2. Prove the irrationality of $\sqrt{2}$ and other numbers
  3. Prove infinitude results (infinitely many primes of various forms)
  4. Distinguish proof by contradiction from proof by contrapositive
  5. Know when contradiction is the most natural approach

Core Content

1. Proof by Contradiction — The Method

Proof by contradiction (reductio ad absurdum) assumes the NEGATION of what you want to prove, then derives an impossibility (a contradiction).

Template:

Assume the statement is FALSE.
[Derive logical consequences]
[Arrive at a contradiction: something known to be false, or P and not P]
Therefore the assumption is false, so the original statement is TRUE. ∎

Why it works: If assuming $\neg S$ leads to nonsense, then $\neg S$ must be false, so $S$ must be true.

2. Classic Example: $\sqrt{2}$ is Irrational

Theorem: $\sqrt{2}$ is irrational.

Proof (by contradiction):

Assume $\sqrt{2}$ is RATIONAL. Then $\sqrt{2} = a/b$ where $a, b$ are integers with no common factor (lowest terms).

Squaring: $2 = a^2/b^2$, so $a^2 = 2b^2$.

This means $a^2$ is even, so $a$ is even (proved in 29-01). So $a = 2k$ for some integer $k$.

Substituting: $(2k)^2 = 2b^2$, so $4k^2 = 2b^2$, so $b^2 = 2k^2$.

This means $b^2$ is even, so $b$ is even.

Contradiction: Both $a$ and $b$ are even, meaning they share a factor of 2. But we assumed $a/b$ was in lowest terms (no common factors).

Therefore $\sqrt{2}$ is irrational. ∎

3. Infinitude of Primes (Euclid's Proof)

Theorem: There are infinitely many prime numbers.

Proof (by contradiction):

Assume there are FINITELY many primes: $p_1, p_2, ..., p_n$.

Consider $N = p_1 p_2 ... p_n + 1$.

$N$ is either prime or composite: - If $N$ is prime: we found a prime not in our list (since $N > p_n$). Contradiction. - If $N$ is composite: by the Fundamental Theorem of Arithmetic, $N$ has a prime factor $p$. But $p$ cannot be any of $p_1, ..., p_n$ because $N \equiv 1 \pmod{p_i}$ (dividing $N$ by any $p_i$ leaves remainder 1). So $p$ is a prime not in our list. Contradiction.

Therefore there are infinitely many primes. ∎

4. When to Use Contradiction

Good candidates for contradiction: - Proving something doesn't exist (e.g., "no rational solution") - Proving irrationality or transcendence - Proving infinitude - When the direct approach seems blocked

When to avoid: - When a direct proof is shorter and clearer - When the contradiction is contrived rather than natural - In constructive settings where you need to build the object, not just prove existence

5. Contrapositive vs Contradiction

Method Assumes Derives
Contrapositive Not Q Not P
Contradiction Not S (the whole statement) P and not P (direct contradiction)

Key difference: Contrapositive stays within the original statement's logic. Contradiction widens to assume the entire statement is false.

Worked Examples

Example 1: $\sqrt{3}$ is Irrational

Problem: Prove that $\sqrt{3}$ is irrational.

Solution:

Assume $\sqrt{3}$ is rational: $\sqrt{3} = a/b$ in lowest terms.

$3 = a^2/b^2$, so $a^2 = 3b^2$. Thus $a^2$ is divisible by 3, so $a$ is divisible by 3. Let $a = 3k$. Then $(3k)^2 = 3b^2$, so $9k^2 = 3b^2$, so $b^2 = 3k^2$.

Thus $b^2$ is divisible by 3, so $b$ is divisible by 3.

Contradiction: Both $a$ and $b$ are divisible by 3, contradicting that $a/b$ is in lowest terms.

Answer: $\sqrt{3}$ is irrational. ∎

Example 2: No Integer Solutions to $x^2 - y^2 = 2$

Problem: Prove that $x^2 - y^2 = 2$ has no integer solutions.

Solution:

Assume there ARE integer solutions $x, y$.

$x^2 - y^2 = (x-y)(x+y) = 2$.

Since $x-y$ and $x+y$ are both integers and their product is 2, the possibilities are: - $x-y = 1, x+y = 2$ → $2x = 3$ → $x = 1.5$ (not integer) - $x-y = 2, x+y = 1$ → $2x = 3$ → $x = 1.5$ (not integer) - $x-y = -1, x+y = -2$ → same issue - $x-y = -2, x+y = -1$ → same issue

Also consider: $x-y$ and $x+y$ have the same parity (both even or both odd), since $(x+y) - (x-y) = 2y$ is even. But 2 cannot be factored into two integers of the same parity (the only factorisations of 2 are $1 \cdot 2$ and $(-1) \cdot (-2)$, and 1 and 2 have opposite parity).

Contradiction: No valid integer factorisation exists.

Answer: $x^2 - y^2 = 2$ has no integer solutions. ∎

Example 3: Infinitude of Primes of Form $4k+3$

Problem: Prove there are infinitely many primes congruent to 3 mod 4.

Solution:

Assume finitely many: $p_1, p_2, ..., p_n$ where each $p_i \equiv 3 \pmod{4}$.

Consider $N = 4(p_1 p_2 ... p_n) - 1 = 4(p_1...p_n) - 1$.

$N \equiv -1 \equiv 3 \pmod{4}$.

Factor $N = q_1 q_2 ... q_m$ into primes. Each $q_j$ is either $\equiv 1$ or $3 \pmod{4}$.

But $N \equiv 3 \pmod{4}$, and a product of numbers $\equiv 1 \pmod{4}$ is $\equiv 1 \pmod{4}$. So at least one prime factor $q$ satisfies $q \equiv 3 \pmod{4}$.

This $q$ cannot be any of $p_1, ..., p_n$ because $N \equiv -1 \pmod{p_i}$ (since $N = 4(\text{product}) - 1 \equiv -1$ mod each $p_i$).

Contradiction: We found a prime $q \equiv 3 \pmod{4}$ not in our finite list.

Answer: There are infinitely many primes $\equiv 3 \pmod{4}$. ∎

Practice Problems

Problem 1: Prove by contradiction that $\sqrt{5}$ is irrational.

Problem 2: Prove that there is no rational number $r$ such that $r^2 = 3$.

Problem 3: Prove that $\log_2(3)$ is irrational.

Problem 4: Prove that the equation $x^2 + y^2 = 3$ has no integer solutions.

Problem 5: Prove that if $a$ and $b$ are odd integers, then $a+b$ is even (try both direct and contradiction).

Summary

  1. Proof by contradiction assumes the statement is false and derives an impossibility
  2. $\sqrt{2}$ is irrational is the canonical example — assume rational, derive that both numerator and denominator are even
  3. Euclid's proof of infinite primes uses contradiction with $N = p_1...p_n + 1$
  4. Contrapositive is a one-statement equivalence; contradiction assumes the entire claim is false
  5. Use contradiction for non-existence, irrationality, and infinitude proofs

Key Terms

Pitfalls

Quiz

  1. Assuming the wrong negation. If proving 'If P then Q', the negation is 'P and not Q', not just 'not Q'. Forgetting P leads to proving something weaker.
  2. Deriving a trivial contradiction. Reaching '0 = 0' or '1 = 1' doesn't help — you need to derive something known to be false (e.g., '2 is odd', '√2 is rational').
  3. Hiding the contradiction. Sometimes the contradiction is implicit (e.g., 'x is both rational and irrational'). Make it explicit for clarity.
  4. Overusing contradiction. Not every proof needs contradiction. Direct proof or contrapositive is often cleaner. Use contradiction when negation naturally leads somewhere interesting.
  5. Ignoring the law of excluded middle. Classical contradiction relies on P ∨ ¬P being always true. In intuitionistic logic, this doesn't hold — but standard math courses assume classical logic.
  6. Conflating proof by contradiction with proof by counterexample. Counterexamples disprove universal claims; contradiction proves them (or their negations).

Q1: Proof by contradiction is also known as:

A) Modus ponens B) Reductio ad absurdum C) Mathematical induction D) Direct proof

Correct: B)

Q2: The proof that $\sqrt{2}$ is irrational uses which technique?

A) Direct proof B) Proof by contrapositive C) Proof by contradiction D) Proof by induction

Correct: C)

Q3: Euclid's proof that there are infinitely many primes uses:

A) Proof by induction B) Proof by contradiction C) Direct proof D) Proof by construction

Correct: B)

Q4: The contrapositive of "If $n$ is prime, then $n > 1$" is:

A) If $n > 1$, then $n$ is prime B) If $n \leq 1$, then $n$ is not prime C) If $n$ is not prime, then $n \leq 1$ D) If $n \leq 1$, then $n$ is prime

Correct: B)

Q5: Which is easiest to prove by contradiction?

A) The sum of two even numbers is even B) $\sqrt{2}$ is irrational C) $2 + 2 = 4$ D) If $n$ is even, then $n^2$ is even

Correct: B)

Q6: A proof by contradiction of "There does NOT exist an $x$ with property P" begins by:

A) Assuming there exists an $x$ with property P B) Assuming all $x$ have property P C) Proving P is impossible directly D) Showing a counterexample

Correct: A)

Q7: In the $\sqrt{2}$ proof, the contradiction arises because:

A) $\sqrt{2}$ turns out to be rational B) Both $a$ and $b$ are shown to be even, contradicting that $a/b$ was in lowest terms C) $a^2 = 2b^2$ has no integer solutions D) 2 is not a perfect square

Correct: B)

Q8: Proof by contradiction is most powerful when:

A) The statement is obviously true B) The negation of the statement leads to a clear, unavoidable contradiction C) You can't think of a direct proof D) The statement involves only prime numbers

Correct: B)

Next Steps

Continue to 29-03 — Induction Deep Dive to explore advanced induction techniques including strong induction, structural induction, and the well-ordering principle.