Back to the on-screen lesson ·
When the hypothesis gives a proof nothing to unfold, assume the negated conclusion instead — and why that proves the same claim.
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 write the contrapositive of a claim with its compound halves negated correctly, decide from the two candidate assumptions which one unfolds into an equation, carry out the proof by the direct method's four moves, and finish by naming contraposition as the rule that turns what you proved into what was asked. You will also be able to tell a contrapositive proof from a proof of the inverse or the converse, which differ from it by one negation and one reversal.
Lesson 2 established that $P \Rightarrow Q$ and $\neg Q \Rightarrow \neg P$ have the same four rows and are therefore the same claim. Lesson 6 gave the four moves of a direct proof. This lesson spends the first fact: when the direct proof's first move produces nothing usable, prove the equivalent statement instead.
The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$, and contraposition is the rule that the two are the same claim. Modus tollens is the argument from $P \Rightarrow Q$ and $\neg Q$ to $\neg P$: contraposition used on a particular case. A rule is applied to lines already written, which is what makes a line-by-line proof checkable.
Try to prove if $n^2$ is even then $n$ is even directly. Assume the hypothesis: $n^2 = 2m$. Now what? Taking a square root leaves the integers, and there is no definition left to unfold. The direct route has stalled at move two, and no amount of cleverness at move three will rescue it.
So prove the contrapositive: if $n$ is odd then $n^2$ is odd. Its hypothesis unfolds immediately to $n = 2k+1$, the algebra is one squaring, and the proof is three lines. Because the contrapositive is the same claim, the original is proved.
The test for when to reach for it is not subtle. Write down both the hypothesis and the negated conclusion, unfold each into an equation, and ask which one you can actually compute with. If the negated conclusion is the concrete one, use the contrapositive.
That happens most often when the hypothesis is about a derived quantity — $n^2$, $3n+2$, $a + b$ — and the conclusion is about the thing itself. Negating swaps them round, and the thing itself is always the easier one to write $2k+1$ for.
A proof by contrapositive must end by saying so. Having proved $\neg Q \Rightarrow \neg P$, the last line names contraposition as the rule that turns it into $P \Rightarrow Q$. Without that line a reader is entitled to say you proved something else.
Another way: steps
Another way: example
Claim: if $a + b \ge 10$ then $a \ge 5$ or $b \ge 5$. The conclusion is a disjunction, so its negation is a conjunction: $a < 5$ and $b < 5$. From those two, $a + b < 10$, which is $\neg P$. Two lines — and the whole difficulty was negating the or correctly.
A contrapositive proof is usually easy once it starts, and the place it goes wrong is before it starts, in writing $\neg Q$ and $\neg P$ down. Everything lesson 5 said applies here and is now load-bearing:
| Conclusion $Q$ | $\neg Q$, correctly |
|---|---|
| $a \ge 5$ or $b \ge 5$ | $a < 5$ and $b < 5$ |
| $x$ and $y$ are both rational | $x$ is irrational or $y$ is |
| $f$ is injective | some two distinct inputs share an output |
| $n$ is odd | $n$ is even |
The first row is the one that catches people: negating an or gives an and, which is a stronger assumption and therefore a more useful one. A disjunction in the conclusion is one of the clearest signals that the contrapositive is the road to take.
Assuming $\neg P$ instead of $\neg Q$. That proves the inverse, $\neg P \Rightarrow \neg Q$, which is the converse in disguise and is a different claim.
Negating half a compound conclusion. '$a \ge 5$ or $b \ge 5$' does not negate to '$a < 5$ or $b < 5$'.
Omitting the last line. A proof that ends at $\neg P$ has proved the contrapositive and not said that this is the claim. Name the rule.
Mixing it with contradiction. A contrapositive proof assumes one thing, $\neg Q$, and derives $\neg P$. It does not assume $P$ as well; if you find yourself using both, you are writing a proof by contradiction, and you should say so.
A contrapositive proof establishes exactly what a direct proof of the same claim would establish, with the same force, because the two statements are the same statement. There is no sense in which it proves 'nearly' the claim or proves it 'the other way round'. The only thing that distinguishes it is which of two equivalent starting points you chose, and that is a question about which assumption gives you an equation — a question of convenience, decided before any mathematics happens.
Claim: if $3n + 2$ is odd then $n$ is odd. Directly: $3n + 2 = 2k+1$, so $3n = 2k - 1$ — and $3n$ odd does not obviously give $n$ odd without more work.
The direct route is not impossible, only awkward.
Contrapositive: assume $n$ is even, so $n = 2k$. Then $3n + 2 = 6k + 2 = 2(3k + 1)$, which is even.
One substitution and one factorisation.
So $n$ even implies $3n+2$ even; by contraposition, $3n+2$ odd implies $n$ odd.
The last line names the rule.
Claim: if $xy$ is irrational then $x$ is irrational or $y$ is irrational. Negate the conclusion with De Morgan: $x$ and $y$ are both rational.
An or negates to an and.
Unfold: $x = p/q$ and $y = r/s$ with $q, s \ne 0$. Then $xy = pr/(qs)$, and $qs \ne 0$.
Two definitions, one product.
So $xy$ is rational, which is the negated hypothesis; by contraposition the claim follows. The direct proof would have had to argue about an irrational product with no handle on it at all.
The negation handed us two equations instead of none.
Assuming $n^3 = 2k+1$ gives nothing to unfold, so go contrapositive: assume $n$ is even.
Pick the assumption that becomes an equation.
$n = 2m$, so $n^3 = 8m^3 = 2(4m^3)$, which is even.
Unfold, cube, regroup.
That is the negated hypothesis, so by contraposition the claim holds. Notice that the same three lines prove the same statement about any power of $n$ — which is a sign that the real theorem here is about parity being preserved by multiplication.
Build the proof, by contrapositive, that if $n^2$ is even then $n$ is even.
This task has no paper form; do it on a device.
From the premises P -> Q, Q -> R and ~R, derive ~P. Give one line at a time, with the rule and the lines it uses.
P -> Q
Q -> R
~R
∴ ~P
| # | Formula | Rule | Lines |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
P stands for “the sample is pure” and Q for “the reading is drifting”. Write the contrapositive of $P \Rightarrow \neg Q$.
Answer:
You are proving 'if $n^3$ is odd then $n$ is odd' by contrapositive. What do you assume, and what do you set out to derive?
The claim is: if $6n + 2$ is odd then $n$ is odd. Mark every opening that is a legitimate first line of a proof **by contrapositive**.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
P stands for “the tap is running” and Q for “the sink is filling”. Write the contrapositive of $P \Rightarrow Q$.
Answer:
You can choose the contrapositive when the hypothesis is unusable, negate a compound conclusion correctly and finish by naming the rule. Say in your own words why proving the contrapositive proves the claim, and why assuming the negated hypothesis instead does not. Next: the proofs that assume the claim is false and drive that assumption into an impossibility.
10. Your turn: if $n^3$ is odd then $n$ is odd, step 3