# 7.2 Proof by Contradiction

## 7.2 Proof by Contradiction

Proof by contradiction proves a statement by showing that its negation is impossible. Instead of proving $P$ directly, we assume $\neg P$ and derive a contradiction.

The logical form is:

$$
\neg P \Rightarrow \bot.
$$

Here $\bot$ denotes contradiction. Once contradiction is reached, classical logic allows us to conclude $P$.

This method is useful when the desired conclusion is difficult to construct directly, but the assumption that it fails leads to strong consequences.

A standard example is the proof that $\sqrt{2}$ is irrational.

Assume, for contradiction, that $\sqrt{2}$ is rational. Then there exist integers $a$ and $b$, with $b \neq 0$, such that

$$
\sqrt{2} = \frac{a}{b}.
$$

Choose this fraction in lowest terms. Then

$$
2 = \frac{a^2}{b^2},
$$

so

$$
a^2 = 2b^2.
$$

Thus $a^2$ is even, so $a$ is even. Write $a = 2k$. Substituting gives

$$
(2k)^2 = 2b^2,
$$

so

$$
4k^2 = 2b^2,
$$

and therefore

$$
b^2 = 2k^2.
$$

Thus $b^2$ is even, so $b$ is even. Now both $a$ and $b$ are even, contradicting the assumption that the fraction $a/b$ was in lowest terms.

Therefore, $\sqrt{2}$ is irrational.

The proof works because the negation of the claim creates an impossible arithmetic condition.

Proof by contradiction is especially useful for nonexistence statements. To prove that no object has a certain property, assume such an object exists and derive an impossibility.

For example, to prove that there is no largest integer, assume there is a largest integer $N$. Then $N+1$ is also an integer and

$$
N+1 > N.
$$

This contradicts the assumption that $N$ was largest. Therefore, no largest integer exists.

The method is also useful when a direct construction is unavailable. Some existence proofs show that nonexistence leads to contradiction. These are valid in classical mathematics, but they may not provide an explicit object.

This distinction matters. A contradiction proof of existence may show that some object must exist without telling us how to find it. Constructive mathematics often requires more: it asks for a witness or an algorithm.

Proof by contradiction should be used with care. The contradiction must follow from the temporary assumption together with accepted hypotheses. It is not enough to reach a surprising result. The result must be logically impossible or must contradict a known fact, an assumption, or a previously proved theorem.

Common sources of contradiction include:

A statement and its negation:

$$
Q \quad \text{and} \quad \neg Q.
$$

An impossible equality:

$$
0 = 1.
$$

A violation of an assumption, such as a fraction being both in lowest terms and having a common factor.

A violation of order, such as producing an integer larger than the assumed largest integer.

There is a related method called proof by contrapositive. To prove

$$
P \Rightarrow Q,
$$

one proves

$$
\neg Q \Rightarrow \neg P.
$$

This is not the same as proof by contradiction, although the two are often confused. A contrapositive proof changes the implication into an equivalent implication. A contradiction proof assumes the whole statement is false and derives impossibility.

For example, to prove that if $n^2$ is even then $n$ is even, a contrapositive proof shows: if $n$ is odd, then $n^2$ is odd.

Assume $n$ is odd. Then $n = 2k+1$ for some integer $k$. Then

$$
n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1.
$$

So $n^2$ is odd. Therefore, if $n^2$ is even, $n$ is even.

This proof avoids contradiction and often reads more cleanly.

A good rule is: use direct proof when the assumptions naturally lead to the conclusion; use contrapositive when the negation of the conclusion is easier to analyze; use contradiction when assuming failure creates a strong impossible condition.

Proof by contradiction is powerful because it turns impossibility into evidence. It shows that every alternative to the desired claim collapses. In classical mathematics, this is enough to establish the claim.