Proof by contradiction
Learn proof by contradiction for Year 11 Specialist Mathematics in Queensland (QCAA). It is a key method in the nature of proof: to prove a statement, you assume its opposite is true and show that this leads to an impossibility.
You will learn to write the opening negation, negate implications and "for all" statements, and run classic arguments such as there being no largest integer — building the reasoning skills assessed across the course.
Theory
Proof by contradiction is a core method of proof in Year 11 Specialist Mathematics (QCAA, Queensland). To prove a statement S, you assume its negation (not S), reason validly until you reach an impossibility, and conclude that S must be true. This page shows how to write the opening assumption and how to run the argument to a contradiction.
A proof by contradiction establishes a statement \(S\) indirectly. Instead of building \(S\) up from known facts, you suppose \(S\) is false and show that this leads to something impossible.
The opening move is the heart of the method: you assume the negation \(\lnot S\) — the exact opposite of the goal. From \(\lnot S\) you make only valid deductions. When these force a contradiction (a statement that is both true and false, or that breaks a known fact), the assumption \(\lnot S\) is to blame, so \(S\) must be true.
A common target is an implication \(P \Rightarrow Q\). Its negation is \(P \text{ and } \lnot Q\): you keep the hypothesis \(P\) and negate the conclusion \(Q\). For a universal statement \(\forall n,\ P(n)\), the negation is \(\exists n,\ \lnot P(n)\) — a single counterexample.
The one rule never to break: the first line is the negation of the goal, never the goal itself. Assuming \(S\) is true and finding no problem proves nothing.
The method follows one logical shape. To prove \(S\):
Negating an implication (keep the hypothesis, negate the conclusion):
Negating a universal claim (swap the quantifier, negate the inside):
How to run a proof by contradiction
- Write the negation \(\lnot S\): state the goal \(S\), then form its exact opposite. For \(P \Rightarrow Q\), assume \(P\) and \(\lnot Q\); for \(\forall n,\ P(n)\), assume some \(n\) with \(\lnot P(n)\).
- Assume \(\lnot S\) and deduce validly: work forward using correct algebra and known facts only — every step must be sound.
- Reach a contradiction: keep going until two results clash, or a known truth is broken (an integer equals a fraction, a lowest-terms fraction has a common factor, and so on).
- Conclude \(S\): the contradiction shows \(\lnot S\) is false, so the original statement \(S\) is true.
State the goal and assume its negation:
| \(S\) | \(:\) | \(\text{there is no largest integer}\) |
| \(\lnot S\) | \(:\) | \(\text{a largest integer } N \text{ exists}\) |
Build a larger integer from \(N\):
| \(N+1\) | \(>\) | \(N\) |
| \(N+1\) | \(\in\) | \(\mathbb{Z}\) |
So \(N+1\) is an integer greater than \(N\), yet \(N\) was assumed to be the largest. This is a contradiction.
\(\therefore\ \lnot S\) is false: there is no largest integer.
Keep the hypothesis, negate the conclusion:
| \(\text{assume}\) | \(:\) | \(n^2 \text{ even and } n \text{ odd}\) |
Square the odd form \(n = 2k+1\):
| \(n^2\) | \(=\) | \((2k+1)^2\) |
| \(=\) | \(4k^2 + 4k + 1\) | |
| \(=\) | \(2(2k^2 + 2k) + 1\) |
This is odd, so \(n^2\) is odd — contradicting the assumption that \(n^2\) is even. The contradiction rules out \(n\) being odd.
\(\therefore\ n\) must be even.
Assume it is rational, written in lowest terms:
| \(\sqrt2\) | \(=\) | \(\dfrac{a}{b} \ \text{(lowest terms)}\) |
| \(2b^2\) | \(=\) | \(a^2\) |
\(a^2\) is even, so \(a\) is even; put \(a=2c\):
| \(2b^2\) | \(=\) | \((2c)^2 = 4c^2\) |
| \(b^2\) | \(=\) | \(2c^2\) |
So \(b\) is even too. Then \(a\) and \(b\) share the factor \(2\), contradicting the assumption that \(\dfrac{a}{b}\) was in lowest terms.
\(\therefore\ \sqrt2\) is irrational.
Negate the implication \(P \Rightarrow Q\) as \(P \wedge \lnot Q\):
| \(\text{statement}\) | \(:\) | \((n \text{ prime},\ n>2) \Rightarrow n \text{ odd}\) |
| \(\lnot(P \Rightarrow Q)\) | \(\equiv\) | \(P \ \text{and}\ \lnot Q\) |
| \(P\) | \(:\) | \(n \text{ prime and } n>2\) |
| \(\lnot Q\) | \(:\) | \(n \text{ even}\) |
Keep the full hypothesis and negate only the conclusion — do not drop \(n>2\) or negate \(P\).
\(\therefore\) assume \(n\) is prime, \(n>2\), and \(n\) is even.
Common pitfalls
Frequently asked questions
What is proof by contradiction?
A method that proves a statement \(S\) by assuming its negation \(\lnot S\), deducing validly until an impossibility appears, and concluding that \(S\) must be true.
What do you assume first in a proof by contradiction?
You assume the negation of the goal, \(\lnot S\) — the exact opposite of what you want to prove, never the statement itself.
How do you negate an if-then statement?
The negation of \(P \Rightarrow Q\) is \(P \text{ and } \lnot Q\). Keep the hypothesis \(P\) and negate only the conclusion \(Q\).
How do you prove there is no largest integer?
Assume a largest integer \(N\) exists. Then \(N+1\) is also an integer and \(N+1 > N\), so \(N\) is not the largest — a contradiction. Hence there is no largest integer.
Why does proof by contradiction work?
If assuming \(\lnot S\) forces an impossibility, then \(\lnot S\) cannot be true. Since a statement is either true or false, \(S\) must therefore be true.
Is a counterexample a proof by contradiction?
No. A counterexample disproves a universal ("for all") claim with a single case. A proof by contradiction instead proves a statement by ruling out its negation.