Proof by Contradiction - Forms of Argument

Mathematical Writing - Vivaldi Franco 2014

Proof by Contradiction
Forms of Argument

A proof by contradiction of a proposition $$P$$ consists of assuming $$\lnot P$$ and deducing a false statement:

$$\begin{aligned} \lnot P\Rightarrow \textsc {False}. \end{aligned}$$

(7.6)

The false statement could be anything, including any assertion that contradicts the assumption $$\lnot P$$. Formally, contradiction works because from (7.6) and the truth table (4.9) of the implication operator we deduce that $$\lnot P$$ is false and hence $$P$$ is true.

For example, in the proof by contradiction of the irrationality of $$\sqrt{2}$$, presented in Sect. 7.1, we assumed that $$\sqrt{2}\in \mathbb {Q}$$, and deduced that

$$ \exists m,n\in \mathbb {N},\,\,(\mathrm{gcd}(m,n)=1) \, \Rightarrow \, (m,n\in 2\mathbb {Z}) $$

which is clearly false.

A classic proof by contradiction is Euclid’s proof of the infinitude of primes.

Theorem 7.1. The number of primes is infinite.

PROOF. Assume there are only finitely many primes, $$p_1,\ldots ,p_n$$. Consider the integer

$$\begin{aligned} N=1+\prod _{k=1}^n p_k. \end{aligned}$$

(7.7)

Then $$N$$ is greater than all the primes; moreover, if we divide $$N$$ by $$p_k$$ we get remainder 1, and therefore $$N$$ is not divisible by any of the primes. Now, every integer greater than 1 is divisible by some prime. It follows that $$N$$ must be divisible by a prime not in the given list, a contradiction. $$\square $$

The statement that every integer greater than 1 is divisible by some prime needs some justification (see Sect. 8.1).

To apply the method of contradiction to an implication $$P\Rightarrow Q$$, we assume the negation of the implication, namely $$\lnot (P\Rightarrow Q)$$. By Theorem 4.1, this is equivalent to $$P\wedge \lnot Q$$, so our proof amounts to establishing that

$$ (P\wedge \lnot Q) \Rightarrow \textsc {False}. $$

This form of proof by contradiction is called the both ends method: to prove that if $$P$$ then $$Q$$, we assume both $$P$$ and not-$$Q$$, and we deduce something impossible. The appealing feature of this method is that it gives us two assumptions to exploit, namely $$P$$ and $$\lnot Q$$. This is often how mathematicians work, although this strategy may not be made explicit. It also easily causes confusion in writing, as the following example (from a textbook) shows.

Theorem. For all real numbers $$x$$, if $$x > 0$$, then $$1/x > 0$$.

BAD PROOF: If $$1/x < 0$$ then $$(-1)/x > 0$$, so $$x((-1)/x) > 0$$, i.e., $$-1 > 0$$, a contradiction. Therefore $$1/x \geqslant 0$$. Since $$1/x$$ can’t be $$0$$, we conclude that $$1/x > 0$$.$$\,\,\,\,\square $$

In this proof, the assumption of $$P$$ is hidden, and the assumption of $$\lnot Q$$ is confused. Not helpful writing!

PROOF. We use contradiction. Let us assume that $$x>0$$ and $$1/x\leqslant 0$$. Multiplying the second inequality by $$-1$$, we obtain $$-{1}/{x}\geqslant 0$$, and since $$x$$ is positive, multiplication by $$x$$ yields $$x(-1/x)\geqslant 0$$. Simplification gives $$-1\geqslant 0$$, which is false. $$\square $$

The final deduction rests on the inequality $$0<1$$, which may be derived from the axioms of the real number system.