Proof by Contrapositive - Forms of Argument

Mathematical Writing - Vivaldi Franco 2014

Proof by Contrapositive
Forms of Argument

In Sect. 4.2 we saw that every implication $$P\Rightarrow Q$$ is equivalent to its contrapositive $$\lnot Q \Rightarrow \lnot P$$: they are both true or both false for any value of $$P$$ and $$Q$$. This equivalence gives us a method for proving implications, called proof by contrapositive, which is a useful alternative to a direct proof. To prove by contrapositive that

If $$P$$ then $$Q$$,

we prove instead that

If not $$Q$$ then not $$P$$,

that is, we assume that $$Q$$ is false and then deduce that $$P$$ is false .

A proof by contrapositive is structurally identical to a direct proof, only the predicates are different. Thus in place of (7.2) we consider the statement

$$\begin{aligned} \forall x\in X,\,\,\lnot {\fancyscript{Q}}(x)\,\Rightarrow \,\lnot {\fancyscript{P}}(x). \end{aligned}$$

(7.3)

In forming the contrapositive we haven’t altered the quantifier; we have merely replaced a boolean function with an equivalent function, much like replacing $$\sin ^2(x)$$ with $$1-\cos ^2(x)$$.

How do we decide between a direct proof and a proof by contrapositive? We must compare the assumptions $$P$$ and $$\lnot Q$$, and decide which of the two is easier to handle. Sometimes it’s necessary to try both approaches to find out. The following examples show the reasoning behind such decisions.

EXAMPLE. Consider the statement

$$\begin{aligned} \forall n\in \mathbb {N},\,\,(2^n<n!) \Rightarrow (n>3). \end{aligned}$$

(7.4)

The assumption $${\fancyscript{P}}(n)=(2^n<n!)$$ is problematic, because its value is not easily computable. By contrast, $$\lnot {\fancyscript{Q}}(n)=(n\leqslant 3)$$ is straightforward, and the contrapositive implication

$$\begin{aligned} \forall n\in \mathbb {N}, \,\,n\leqslant 3 \Rightarrow \,\,(2^n\geqslant n!) \end{aligned}$$

(7.5)

involves checking that the boolean expression $$(2^n\geqslant n!)$$ is true for only three values of $$n$$.

PROOF. We only have to check three cases:

·  $$n=1$$: $$2=2^1\geqslant 1!=1$$

·  $$n=2$$: $$4=2^2\geqslant 2!=2$$

·  $$n=3$$: $$8=2^3\geqslant 3!=6$$.

Thus the expression (7.5) is true, and the proof is complete. $$\square $$

EXAMPLE. Consider the statement

If the average of four distinct integers is equal to 10, then one of the integers is greater than 11.

The direct implication involves an assumption on an average value, which entails loss of information; the contrapositive implication involves four integers of bounded size. We opt for the latter, which seems easier.

Given four distinct integers not greater than 11, their average is not equal to 10.

PROOF. Let four distinct integers be given. If none of them exceeds 11, then the largest value their sum can assume is $$11+10+9+8=38$$. So the largest possible average is

$$ \frac{38}{4}=\frac{19}{2}<10 $$

as desired. $$\square $$