A proof by contrapositive, or proof by contraposition, is based on the fact that $p\Rightarrow q$ means exactly the same as $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$. This is easier to see with an example:

Example 1

If it has rained, the ground is wet.

This is a claim

$$p\Rightarrow q,$$ |

where $p=$ “it has rained” and $q=$ “the ground is wet”. The claim

$$\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$$ |

will then be as follows:

If the ground is not wet, it hasn’t rained.

You can see that these two sentences logically express the same thing, but in two different ways. (In other words: They are equivalent.) Both of them say that it can’t both have rained, and the ground not be wet, at the same time.

Theory

$\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$ is the contrapositive of the implication $p\Rightarrow q$.

Theory

To prove that $p\Rightarrow q$, it is sufficient to prove that

$$\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right).$$ |

So, $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)$ implies $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$.

With proofs by contrapositive, you’re supposed to make a logical chain. You begin with $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)$. The claim $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)$ needs to imply something, which then implies something else, and so on, until you end up implying $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$, where $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$ is what you were supposed to prove from $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)$.

Example 2

Take a look at this claim about the kinship of David Beckham and Brooklyn Beckham:

“Brooklyn is David’s son” implies that David is Brooklyn’s dad.

$p\Rightarrow q$

You can rewrite this and claim something that is still true by logic (you know that this is not informative):

“David is not Brooklyn’s dad” implies that Brooklyn is not David’s son.

$\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$

The claim is true by logic, because if David wasn’t Brooklyn’s dad, then Brooklyn wouldn’t be David’s son either.

Example 3

**Prove that the square root of an irrational number is an irrational number: **

In this case you want to show that if a number $a$ is irrational, then the number $\sqrt{a}$ is also irrational—you want to show an implication. The implication you want to show is that $p\Rightarrow q$, where $p=$ “$a$ is irrational” and $q=$ “$\sqrt{a}$ is irrational”. The contrapositive is $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$, or in other words

$\sqrt{a}$ is not irrational $\Rightarrow a$ is not irrational

Since “not irrational” is the same as “can be written as a fraction”, you can begin with the implication “$\sqrt{a}$ can be written as a fraction”, and then try to show that $a$ can be written as a fraction. If you can do this, then you are done with the proof.

Write your implication as the equation $\sqrt{a}=\frac{p}{q}$. You want to show that $a$ is a fraction, so square both sides. Then you get $a$ on one side, and a fraction on the other side, so you have shown that $a$ is not irrational. This is the same as the contrapositive $\phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$. You have shown that

$$\phantom{\rule{-0.17em}{0ex}}\left(\text{not}q\right)\Rightarrow \phantom{\rule{-0.17em}{0ex}}\left(\text{not}p\right)$$ |

Mathematically you can write the reasoning like this: Assume

$$\begin{array}{cc}\sqrt{a}=\frac{p}{q}& \\ \text{where}p\text{and}q\text{areintegers}.& \end{array}$$

$$\sqrt{a}=\frac{p}{q}\text{where}p\text{and}q\text{areintegers}.$$ |

$$a=\frac{{p}^{2}}{{q}^{2}}$$ |

It shows that $a$ can be written as a fraction, such that $a$ is not an irrational number. You have shown that $$\begin{array}{cc}\text{}\sqrt{a}\text{isnotirrational}& \\ \Downarrow & \\ \sqrt{a}=\frac{p}{q}& \\ \Downarrow & \\ a=\frac{{p}^{2}}{{q}^{2}}& \\ \Downarrow & \\ \text{}a\text{isnotirrational}& \end{array}$$

which is the contrapositive version of what you wanted to show, which was that if $a$ is an irrational number, $\sqrt{a}$ must be an irrational number.

Q.E.D

The reason why a proof by contrapositive often works when you are constructing proofs with irrational numbers is that instead of working with claims such as “$a$ is irrational”, you can work with claims llike “$a$ is not irrational”. These are much easier to work with, because a number which is not irrational is a fraction—something that is much easier to determine.

Previous entry

What Is Direct Proof?

Next entry

What Is Proof by Induction?