Back to the on-screen lesson ·
Supposing the claim false, deriving an impossibility, and naming what the impossibility collides with — which is always something the proof put on the table itself.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to open a proof by contradiction with the full negation of the claim, add the free conditions that give the argument something to strike, derive an impossibility and name what it collides with. You will also be able to tell a genuine contradiction from an argument that merely derives something true, and to recognise a proof by contradiction that is really a contrapositive proof with an unused assumption in front of it.
Lesson 5 taught you to negate a statement in full, pushing the negation inward until nothing is left negated but the atoms. That skill is the whole of the first line here, and a proof by contradiction is no better than the negation it starts from.
A supposition for contradiction is the negation of the claim, assumed in order to be destroyed. A contradiction is a statement of the form $R \wedge \neg R$ — something and its own denial, both derived. Reductio ad absurdum is the same technique's older name. A vacuous argument is one that derives only true things and therefore establishes nothing.
To prove $S$: suppose $\neg S$, derive a statement that cannot hold, and conclude that $\neg S$ cannot hold either. The logic is the one row of the implication table you already know: if $\neg S$ implies something impossible, $\neg S$ cannot be true.
Three things make or break such a proof.
The negation must be complete. '$\sqrt{2}$ is rational' is the negation; '$\sqrt{2} = p/q$' is that negation unfolded, and the standard proof adds 'in lowest terms', which is free — every fraction can be reduced — and is the thing the contradiction will eventually strike. Omit it and the argument runs and reaches nothing.
The impossibility must be genuine. Deriving a true statement from the supposition proves nothing whatever. A false statement implies true ones exactly as readily as a true one does, and an argument that ends 'and this is true, hence the supposition is false' has ended backwards.
Say what broke. The last line names the collision: not just 'contradiction' but contradicting the choice of a fraction in lowest terms, contradicting the supposition that the list was complete. The collision is always with something the proof itself put on the table, and naming it is how a reader checks the proof rather than trusting it.
Contradiction is the natural technique for non-existence claims — no largest prime, no rational square root of two, no smallest positive rational — because there is nothing to construct and so nothing for a direct proof to start from. The supposition hands you the object you need to reason about.
Another way: steps
Another way: example
There is no smallest positive rational. Suppose $r$ is one. Then $r/2$ is rational and $0 < r/2 < r$, so $r$ was not smallest. The supposition handed us an $r$ to halve, which is exactly what a direct proof of a non-existence claim could never have got hold of.
They look alike and they are not the same. To prove $P \Rightarrow Q$:
| Assumes | Derives | Concludes | |
|---|---|---|---|
| Contrapositive | $\neg Q$ | $\neg P$ | by contraposition, the claim |
| Contradiction | $P$ and $\neg Q$ | something impossible | the pair cannot both hold |
The contrapositive assumes one thing; contradiction assumes two and gets more to work with, at the cost of a proof that is harder to read, because the reader has to keep track of which lines rest on an assumption that is about to be thrown away.
The practical rule: if you never actually use $P$, you have written a contrapositive proof with extra words. Cross out the supposition of $P$, relabel the last line, and the proof is shorter and clearer. Many published proofs 'by contradiction' are this, and spotting it is a useful habit.
Negating incompletely. Supposing $\sqrt{2} = p/q$ without demanding lowest terms leaves nothing to break.
Deriving something true. '$p^2$ is a multiple of $2$ — which is true — hence the supposition fails' is not an argument. Nothing impossible happened.
Not naming the collision. A proof that ends with the word 'contradiction' and does not say what with cannot be checked.
Reaching for it first. Contradiction will formally prove anything a direct proof will, which is precisely why it is easy to hide a gap in: the supposition makes every line feel productive. Try direct and contrapositive first.
The contradiction has to be a statement and its own denial, both established. 'This gives a very large number' is not a contradiction; nor is 'this cannot be right'. The test is mechanical: point at two lines of your proof and say that one is the negation of the other. If you cannot point at two such lines, the proof has not finished, however strongly the last line feels like an ending.
Suppose the primes are exactly $p_1, \ldots, p_k$. Let $N = p_1 \cdots p_k + 1$.
The supposition supplies the finite list.
$N$ has a prime factor. Dividing $N$ by any $p_i$ leaves remainder $1$, so that factor is not on the list.
Every listed prime is ruled out, one at a time.
That contradicts the supposition that the list held every prime. Note what is not claimed: $N$ itself need not be prime — $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$.
The claim is about a factor, not about $N$.
'Claim: if $n^2$ is even then $n$ is even. Suppose $n^2$ is even and $n$ is odd. Then $n = 2k+1$, so $n^2 = 2(2k^2+2k)+1$ is odd, contradicting that $n^2$ is even.'
It works — but watch which assumption did the work.
Every line after the first used only '$n$ is odd'. The assumption '$n^2$ is even' appears once, at the end, to make the collision.
One of the two assumptions was never used.
So this is the contrapositive proof of lesson 7 with a supposition bolted on. Removing it loses nothing and makes the argument easier to check, which is reason enough to remove it.
A shorter proof is a more checkable proof.
Suppose, for contradiction, that $n$ is both. Then $n = 2k$ and $n = 2m + 1$ for integers $k$ and $m$.
The negation hands you two equations.
Setting them equal, $2k = 2m + 1$, so $2(k - m) = 1$.
Rearrange to isolate the impossibility.
The left side is even and the right side is $1$, so $1$ would be even. That contradicts the fact that $1$ is odd, which was never in doubt — so no integer is both. Here the collision is with arithmetic rather than with a choice, which happens when the supposition imposed no conditions of its own.
Build the classical proof that $\sqrt{2}$ is irrational.
This task has no paper form; do it on a device.
Here are the four lines of a proof, by contradiction, that there is no largest prime. Put them in order.
Number the steps in order (write the number in the box):
To prove that a set has strictly fewer elements than its power set, we suppose that some function from $S$ onto its power set exists. What does the impossibility we reach collide with?
You are about to prove, by contradiction, that there is no largest prime. Mark every opening that is a correct and complete supposition to start from.
This task has no paper form; do it on a device.
Somebody writes: 'Suppose $\sqrt{3}$ were rational, say $\sqrt{3} = p/q$. Then $3q^2 = p^2$, so $p^2$ is a multiple of $3$ — which is true. Hence $\sqrt{3}$ is irrational.' What is wrong with it?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
To prove that no rational number squares to $3$, we suppose that $p/q$ in lowest terms has $(p/q)^2 = 3$. What does the impossibility we reach collide with?
You can open with a complete negation, reach an impossibility and say what it strikes. Say in your own words why deriving a true statement from the supposition establishes nothing, and what the lowest-terms condition is doing in the proof about the square root of two. Next: the claims that split into cases, and the single counterexample that settles a universal claim.
10. Your turn: prove that no integer is both even and odd, step 3