MISSION · Algebra
Direct Proof, Contradiction and Contrapositive
Three ways to get from "if" to "then", and how to tell which one fits
LEVEL 1 · EXPLORE
Make the idea move
Change the controls and watch what happens. Follow your curiosity and see what you notice.
Loading the activity…
LEVEL 2 · LEARN
Unlock the explanation
Open the chapters in any order. Try the examples as you go.
The idea in one sentence
A proof is an argument that leaves no room for a counterexample, and there are three standard routes from the assumption to the conclusion.
Direct proof
Assume what you are given, work forwards, arrive at what you want.
If \(n\) is even then \(n^2\) is even. Even means \(n = 2k\) for some integer \(k\). Then \(n^2 = 4k^2 = 2(2k^2)\), which is 2 times an integer, so \(n^2\) is even. \(\blacksquare\)
Notice the shape. The definition of “even” was turned into algebra immediately, and the conclusion was reached by putting the answer back into that same form. Most direct proofs are exactly this: unpack the definitions, do algebra, repack.
The other thing to notice is the letter \(k\). It stands for any integer, so the argument covers every even number at once. Checking \(2, 4, 6\) and stopping is not a proof, no matter how many cases you try.
Proof by contrapositive
“If P then Q” and “if not Q then not P” are logically identical — they are true in exactly the same situations. So proving one proves the other, and sometimes the flipped version is much easier.
If \(n^2\) is even then \(n\) is even. Going forwards is awkward: knowing \(n^2 = 2m\) tells you little about \(n\). The contrapositive is if \(n\) is odd then \(n^2\) is odd, and that is a one-liner: \(n = 2k+1\) gives \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), which is odd. \(\blacksquare\)
The rule of thumb: when the hypothesis is hard to use but the negated conclusion is easy to use, flip it. And be careful to negate both parts and swap them — swapping without negating gives the converse, which is a different claim and often false.
Proof by contradiction
Assume the opposite of what you want, and derive something impossible. Since the reasoning was valid, the assumption must have been wrong.
\(\sqrt 2\) is irrational. Suppose not. Then \(\sqrt 2 = \frac{a}{b}\) in lowest terms. Squaring, \(a^2 = 2b^2\), so \(a^2\) is even, so \(a\) is even (by the contrapositive proof above — proofs stack). Write \(a = 2c\): then \(4c^2 = 2b^2\), so \(b^2 = 2c^2\), so \(b\) is even too.
But \(a\) and \(b\) were in lowest terms and cannot both be even. The assumption collapses, so \(\sqrt 2\) is irrational. \(\blacksquare\)
This is the tool for proving something does not exist or cannot happen, where there is nothing to construct and no forwards path to walk.
Disproving: one counterexample is enough
The asymmetry here is the most useful thing on this page.
To prove “every \(n\) has property \(P\)” you must cover all \(n\). To disprove it you need one \(n\) that fails.
Every prime is odd. Counterexample: 2. Done — no further argument required.
\(n^2 + n + 41\) is prime for every positive integer \(n\). It is prime for \(n = 1, 2, 3, \dots, 39\), which is encouraging and irrelevant. At \(n = 40\) it gives \(40^2 + 40 + 41 = 41 \times 41\). One counterexample beats forty confirmations.
Choosing a method
- The conclusion is an equation or construction you can build → direct.
- The conclusion is a negative — “not”, “no such”, “cannot” → contradiction.
- The hypothesis is unwieldy but its negated conclusion is concrete → contrapositive.
- The claim is about every positive integer, with each case leaning on the previous → induction.
- You suspect the claim is false → hunt for a counterexample first. Ten minutes looking for one saves an hour failing to prove something untrue.
Common mix-ups
- Proving the converse. “If P then Q” is not “if Q then P”. The contrapositive is the equivalent one.
- Proving by example. Examples motivate; they do not prove a universal claim.
- Assuming what you are proving. Starting from the conclusion and reaching something true proves nothing unless every step is reversible.
- Negating sloppily. The opposite of “all swans are white” is “some swan is not white”, not “no swans are white”.
- Stopping before the contradiction. A contradiction proof has to end with two statements that cannot both hold, stated plainly.
Check yourself
What does it take to disprove a universal claim, what is the contrapositive of “if P then Q”, and which method proves \(\sqrt 2\) irrational?
One counterexample. The contrapositive is “if not Q then not P” — negated and swapped. And \(\sqrt 2\) is done by contradiction, assuming it is a fraction in lowest terms.
LEVEL 3 · REFLECT
Add this quest to your trail
When you feel ready, mark this idea as explored. You can always come back and try it again.
EXPLORER STRATEGIES