Proof by Contradiction
Some of the most beautiful results in mathematics — $\sqrt{2}$ is irrational, there are infinitely many primes, no smallest positive rational exists — share one technique. Assume the opposite of what you want, follow the consequences, and reach an impossibility. The contradiction forces the original claim. This lesson teaches the structure and the three classics that every Extension 2 student must know.
If $n^2$ is even, what can you say about $n$? Before checking — write the contrapositive ("if $n$ is odd, then $n^2$ is odd") and prove that one-line algebra. Then explain why this fact will be needed inside the $\sqrt{2}$ irrational proof.
Every contradiction proof rewards two habits: negate the claim cleanly (write down what "assume the opposite" actually means), then drive forward by deduction until two of your deductions disagree. Skipping the explicit negation step is the most common cause of a stalled proof.
The assume-deduce-contradict structure: (1) Assume $\neg P$ (the opposite of what you want), (2) Derive consequences step by step, (3) Reach a statement of the form $A \wedge \neg A$, (4) Conclude $P$ must be true.
If $\neg P \Rightarrow (A \wedge \neg A)$, then $P$ must be true.
Key facts
- The structure: assume $\neg P$, derive a contradiction $A \wedge \neg A$, conclude $P$
- $\sqrt{2}$ is irrational (Pythagorean classic)
- There are infinitely many primes (Euclid's argument)
- There is no smallest positive rational
Concepts
- Why a single contradiction is enough — the law of excluded middle
- How $\gcd(p,q) = 1$ in lowest-terms assumption drives the $\sqrt{2}$ argument
- Why Euclid's prime-list trick produces a number coprime to every listed prime
Skills
- Set up a contradiction proof: state assumption, label the negation
- Reproduce the three classic contradiction proofs from scratch
- Apply contradiction to new statements (e.g., $\sqrt{3}$ irrational, no largest natural)
To prove a statement $P$ by contradiction:
- State the negation. Begin: "Assume, for the sake of contradiction, that $\neg P$."
- Deduce consequences. Use definitions and known results to derive further statements.
- Reach a contradiction. Produce some $A$ together with $\neg A$ — or a statement that contradicts a known fact (e.g., $0 = 1$, or "$n$ is even and $n$ is odd").
- Conclude. "Since $\neg P$ leads to a contradiction, $P$ must be true."
Worked through the hook ($\sqrt{2}$ is irrational):
- Assume $\sqrt{2}$ is rational: $\sqrt{2} = \dfrac{p}{q}$ with $\gcd(p,q) = 1$ (lowest terms).
- Square: $2 = \dfrac{p^2}{q^2}$, so $p^2 = 2q^2$. Thus $p^2$ is even, so $p$ is even (by the lemma). Write $p = 2k$.
- Substitute: $4k^2 = 2q^2 \Rightarrow q^2 = 2k^2$. So $q^2$ is even, hence $q$ is even.
- But then $2 \mid p$ and $2 \mid q$, contradicting $\gcd(p,q) = 1$.
- Therefore $\sqrt{2}$ is not rational, i.e., $\sqrt{2}$ is irrational. $\blacksquare$
Four steps: assume $\neg P$, deduce, contradict, conclude · $\sqrt{2}$ irrational: assume $\sqrt{2} = p/q$ in lowest terms; show $2 \mid p$ and $2 \mid q$; contradicts $\gcd = 1$ · Always state the assumption explicitly at the start · The contradiction must be a specific statement of form $A \wedge \neg A$
Pause — copy the four contradiction steps and the $\sqrt{2}$ irrationality proof skeleton (assume $p/q$ in lowest terms, show $2 \mid p$ and $2 \mid q$, contradict $\gcd = 1$) into your book.
Quick check: In the standard proof that $\sqrt{2}$ is irrational, what is the explicit contradiction reached?
We just saw the four-step contradiction template: assume $\neg P$, deduce, reach $A \wedge \neg A$, conclude. That raises a question: can this technique handle an infinite set? This card answers it → Euclid's proof that infinitely many primes exist, using $N = p_1 \cdots p_n + 1$ to force a contradiction.
Euclid's argument is the canonical contradiction proof. Claim: there are infinitely many prime numbers.
- Assume the contrary: there are only finitely many primes. List them all: $p_1, p_2, \ldots, p_n$.
- Construct $N = p_1 p_2 \cdots p_n + 1$. $N$ is an integer greater than $1$, so it has at least one prime factor.
- Identify the contradiction. Dividing $N$ by any $p_i$ leaves remainder $1$, so no $p_i$ divides $N$. But every prime factor of $N$ should appear in the list — contradiction.
- Conclude: the list cannot be exhaustive, so primes are infinite. $\blacksquare$
Assume finitely many primes: $p_1, \ldots, p_n$ · Let $N = p_1 \cdots p_n + 1$ · $N$ has a prime factor $q$, but $q \neq p_i$ for any $i$ (since $p_i \nmid N$) · Contradiction — list was supposed to contain ALL primes · $N$ itself is NOT necessarily prime (e.g., $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$)
Pause — copy Euclid's construction $N = p_1 \cdots p_n + 1$, the argument that no $p_i$ divides $N$, and the warning that $N$ need not itself be prime, into your book.
Did you get this? True or false: in Euclid's proof of infinitely many primes, the number $N = p_1 p_2 \cdots p_n + 1$ is itself guaranteed to be prime.
Worked examples · 3 in a row, reveal as you go
Prove by contradiction that $\sqrt{2}$ is irrational, citing every step.
Prove by contradiction that there is no smallest positive rational number.
Prove by contradiction that there are infinitely many prime numbers.
Fill the gap: To prove $P$ by contradiction, you assume , derive a contradiction of the form $A \wedge \neg A$, and conclude that $P$ must be .
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: the same contradiction proof structure used for $\sqrt{2}$ can be adapted to prove that $\sqrt{3}$ is irrational, by using the lemma "if $3 \mid n^2$ then $3 \mid n$".
Activities · practice with the ideas
Prove by contradiction that $\sqrt{3}$ is irrational. Use the lemma "if $3 \mid n^2$ then $3 \mid n$".
Prove by contradiction that there is no largest natural number.
Prove by contradiction that if $n^2$ is odd, then $n$ is odd. (Note: the direct proof uses the contrapositive, but you can also do this by contradiction.)
Prove that the sum of a rational and an irrational is irrational.
Show that there are infinitely many primes of the form $4k + 3$. (Adapt Euclid's argument; consider $N = 4 p_1 p_2 \cdots p_n - 1$.)
Odd one out: Three of these are correct steps in the proof that $\sqrt{2}$ is irrational. Which one is NOT?
Earlier you analysed $2q^2 = p^2$ and predicted what it told you about $p$ and $q$.
$2q^2 = p^2$ forces $p^2$ even, so $p$ even (by the lemma); writing $p = 2k$ then forces $q^2 = 2k^2$, so $q^2$ even, so $q$ even. The hidden contradiction with $\gcd(p,q) = 1$ surfaces at this step — both $p$ and $q$ share factor 2. The proof's elegance is in how the lowest-terms assumption is precisely the seed of its own destruction.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. State the structure of a proof by contradiction in four numbered steps. (2 marks)
Q2. Prove by contradiction that $\sqrt{2}$ is irrational. (3 marks)
Q3. Prove by contradiction that there are infinitely many prime numbers. Be explicit about what is contradicted. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Assume $\sqrt{3} = p/q$ with $\gcd(p,q)=1$. Then $3q^2 = p^2$, so $3 \mid p^2$, hence $3 \mid p$. Write $p = 3k$: $3q^2 = 9k^2 \Rightarrow q^2 = 3k^2$, so $3 \mid q^2$ and $3 \mid q$. Both divisible by 3 contradicts $\gcd(p,q) = 1$. $\therefore \sqrt{3}$ is irrational.
2. Suppose $N \in \mathbb{N}$ is the largest. Then $N + 1 \in \mathbb{N}$ and $N + 1 > N$ — contradicting the assumption that $N$ is largest. $\therefore$ no largest natural exists.
3. Assume $n^2$ odd but $n$ even. Then $n = 2k$, so $n^2 = 4k^2 = 2(2k^2)$, which is even — contradicting $n^2$ odd. $\therefore$ $n$ must be odd.
4. Let $r$ rational, $x$ irrational. Assume $r + x = s$ is rational. Then $x = s - r$; since rationals are closed under subtraction, $x$ is rational — contradicting $x$ irrational. $\therefore r + x$ is irrational.
5. Suppose only finitely many primes $\equiv 3 \pmod 4$: $p_1, \ldots, p_n$. Let $N = 4 p_1 \cdots p_n - 1 \equiv -1 \equiv 3 \pmod 4$. Since $N$ is odd, all its prime factors are odd. Not every odd prime factor can be $\equiv 1 \pmod 4$ (product of such is $\equiv 1$, but $N \equiv 3$); so some prime factor $q \equiv 3 \pmod 4$. But $q \neq p_i$ for any $i$ (else $q \mid 1$). Contradiction.
Q1 (2 marks): (1) Assume the negation $\neg P$ [1]; (2) deduce consequences; (3) reach a contradiction $A \wedge \neg A$; (4) conclude $P$ holds [1].
Q2 (3 marks): Assume $\sqrt{2} = p/q$ in lowest terms, $\gcd(p,q) = 1$ [1]. Then $p^2 = 2q^2$, so $p^2$ even, so $p$ even; write $p = 2k$: $q^2 = 2k^2$, so $q$ even [1]. Both $p$ and $q$ even contradicts $\gcd = 1$, hence $\sqrt{2}$ irrational [1].
Q3 (3 marks): Assume finitely many primes $p_1, \ldots, p_n$ [1]. Let $N = p_1 \cdots p_n + 1$; $N > 1$ has a prime factor $q$ [1]. Since $p_i \mid p_1 \cdots p_n$ but $p_i \nmid 1$, $p_i \nmid N$, so $q \neq p_i$ — contradicts the list being complete [1].
Five timed questions on the structure of contradiction proofs and the three classics. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering quick contradiction-proof questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.