Proof by Contradiction

What you'll get from this section. Starting from the contrapositive you already know, you'll build up to proof by contradiction — one of the most powerful tools in mathematics. You'll learn the recipe, see it on the classic example, and learn to tell it apart from proof by contrapositive.

Starting from the contrapositive

From Section 4: to prove $P \Rightarrow Q$, you may instead prove its contrapositive $\neg Q \Rightarrow \neg P$ — assume $\neg Q$ and deduce $\neg P$. This is proof by contrapositive.

Here it is in action. Suppose we want to prove:

If $n^2$ is even, then $n$ is even.

The contrapositive is "if $n$ is odd, then $n^2$ is odd". So assume $n$ is odd and write $n = 2k + 1$. Then

which is odd. We've proved the contrapositive, so the original statement holds.

From contrapositive to contradiction

Look closely at what just happened. When we prove $P \Rightarrow Q$, we are entitled to assume $P$ — it's the hypothesis. In the argument above we assumed $\neg Q$ and reached $\neg P$. But $P$ was supposed to be true. So we'd be holding $P$ and $\neg P$ at once — an impossibility.

That suggests a slightly different way to run the same argument. Instead of quietly proving the contrapositive, assume the thing you want to prove is false, and chase that assumption until it forces something impossible. The only way an implication $P \Rightarrow Q$ can be false is for $P$ to hold while $Q$ fails — so we suppose exactly that, $P$ and $\neg Q$ together, and look for the impossibility.

Recast our example this way:

Suppose, for contradiction, that $n^2$ is even but $n$ is odd. Since $n$ is odd, $n^2$ is odd (as above). But $n^2$ is even. So $n^2$ is both even and odd — impossible. Hence no such $n$ exists, and the statement holds.

Same mathematics, dressed as a contradiction. That "reach an impossibility" move is the whole idea.

The method in general

Proof by contradiction is not limited to implications. To prove any statement $S$:

1. Assume $\neg S$ — that $S$ is false.
2. Reason validly from that assumption.
3. Arrive at a contradiction — typically some statement $R$ together with its negation $\neg R$, or a clash with a known fact.
4. Since assuming $\neg S$ led to the impossible, $\neg S$ cannot hold. Therefore $S$ is true.

The power of the method is that step 1 hands you an extra assumption to work with, and you only need to reach one absurdity to win.

The classic: √2 is irrational

This is the proof everyone meets, and it isn't about an implication at all — which is exactly why it shows the method's reach.

Suppose, for contradiction, that $\sqrt{2}$ is rational. Then we may write

where $a$ and $b$ are integers with no common factor (the fraction is in lowest terms) and $b \neq 0$. Squaring both sides,

Then $a^2$ is even, and so — by the lemma we proved above — $a$ is even. Write $a = 2k$:

so $b^2$ is even, and therefore $b$ is even too. But now $a$ and $b$ are both even, so they share a factor of $2$ — contradicting our choice of a fraction in lowest terms.

The assumption that $\sqrt{2}$ is rational is therefore untenable, so $\sqrt{2}$ is irrational. ∎

Notice the teamwork: the contradiction proof leans on the lemma "$a^2$ even $\Rightarrow a$ even", which we ourselves proved by contrapositive. (Euclid's proof that there are infinitely many primes is another famous argument of the same shape.)

Contrapositive or contradiction?

They're close cousins, but worth keeping apart:

• Proof by contrapositive works only on an implication $P \Rightarrow Q$. You assume $\neg Q$, deduce $\neg P$, and you're done — there's no "absurdity", just a clean deduction that lands on $\neg P$.
• Proof by contradiction works on any statement. You assume the statement is false and derive an impossibility.

For an implication the two run almost in parallel — a contradiction proof of $P \Rightarrow Q$ assumes $P$ and $\neg Q$ and often retraces the very steps of the contrapositive until $P$ and $\neg P$ collide. But contradiction is the more general weapon: it can prove things, like the irrationality of $\sqrt{2}$, that aren't implications at all.

Common mistakes

1. Never actually reaching a contradiction. The argument only works if you hit something genuinely impossible — a statement and its negation, or a clash with a known fact. "Surprising" isn't enough.

2. Assuming too little for an implication. To prove $P \Rightarrow Q$ by contradiction, assume both $P$ and $\neg Q$ — that is the full statement of "the implication is false". Assuming only $\neg Q$ is the contrapositive setup, and then you should be deducing $\neg P$, not hunting a contradiction.

3. Negating the claim wrongly at the start. Step 1 is "assume $\neg S$", so $S$ must be negated correctly — use the rules from Section 3.

Summary

• Proof by contrapositive: to prove $P \Rightarrow Q$, assume $\neg Q$ and deduce $\neg P$.
• Proof by contradiction: to prove any statement $S$, assume $\neg S$ and derive an impossibility.
• For an implication the two are close kin; contradiction is the more general tool.
• The classic worked example is the irrationality of $\sqrt{2}$, which itself reuses a contrapositive lemma.

Next: Section 6 — Equivalence.