Indirect Proof

An indirect proof does not follow the most direct route from hypothesis to conclusion. Two important forms are proof by contradiction and proof by contrapositive. Their logical structures are different, even though both can simplify a difficult argument.

Proof by contradiction

Proof by contradiction assumes that the target statement is false and derives an impossibility. The contradiction must be explicit: it should violate a definition, an established theorem, or one of the hypotheses.

ExampleThe irrationality of $\\sqrt{2}$

Prove that the diagonal of a unit square, whose length is $\sqrt{2}$, is irrational.

Proof

Assume for contradiction that $\sqrt{2}=p/q$, where $p$ and $q$ are coprime integers and $q\ne0$. Squaring gives

$$p^2=2q^2.$$

Thus $p^2$ is even, so $p$ is even. Write $p=2r$. Substitution gives $q^2=2r^2$, so $q$ is even as well. This contradicts the assumption that $p$ and $q$ are coprime. Therefore $\sqrt{2}$ is irrational.

The same lowest-terms argument proves that $\sqrt{5}$ is irrational. The key number-theoretic fact is that if a prime divides a square, it divides the number being squared.

ExerciseNo smallest positive rational

Prove that there is no smallest positive rational number.

Solution

Suppose $p/q$ were the smallest positive rational number, with $p,q>0$. Then $p/(2q)$ is also positive and rational, but

$$0<\frac{p}{2q}<\frac{p}{q}.$$

This contradicts the assumed minimality.

Proof by contrapositive

To prove an implication $P\to Q$, it is enough to prove the logically equivalent implication

$$\neg Q\to\neg P.$$

For example, to prove “if $n^2$ is even, then $n$ is even,” prove instead that an odd integer has an odd square. If $n=2k+1$, then

$$n^2=2(2k^2+2k)+1,$$

which is odd. Hence $n^2$ being even forces $n$ to be even.

ExerciseA product that is odd

Prove that if $ab$ is odd for integers $a$ and $b$, then both $a$ and $b$ are odd.

Solution

Prove the contrapositive. If either factor is even, say $a=2k$, then

$$ab=2(kb),$$

which is even. Therefore an odd product cannot have an even factor, so both factors are odd.

Contrapositive proof directly proves an equivalent implication. Contradiction proof instead assumes the negation of the target and derives an impossible statement. Keeping those two patterns distinct makes the proof strategy easier to audit.