...

>Proofs>What Is Proof by Contrapositive?

What Is Proof by Contrapositive?

A proof by contrapositive, or proof by contraposition, is based on the fact that $p \Rightarrow q$ means exactly the same as $(not q) \Rightarrow (not p)$ . 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

(not q) \Rightarrow (not p)

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

The Contrapositive

$(not q) \Rightarrow (not p)$ is the contrapositive of the implication $p \Rightarrow q$ .

Read this paragraph slowly:

p \Rightarrow q

and

(not q) \Rightarrow (not p)

are equivalent statements. This means that if you can prove that

(not q) \Rightarrow (not p)

, then you have also proven that

p \Rightarrow q

. This is useful because sometimes it is easier to prove

(not q) \Rightarrow (not p)

than

p \Rightarrow q

Theory

Proof by Contrapositive

To prove that

p \Rightarrow q

, it is sufficient to prove that

(not q) \Rightarrow (not p) .

So, $(not q)$ implies $(not p)$ .

With proofs by contrapositive, you’re supposed to make a logical chain. You begin with

(not q)

. The claim

(not q)

needs to imply something, which then implies something else, and so on, until you end up implying

(not p)

, where

(not p)

is what you were supposed to prove from

(not q)

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.

$(not q) \Rightarrow (not p)$

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 $(not q) \Rightarrow (not p)$ , 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 $(not p)$ . You have shown that

(not q) \Rightarrow (not p)

Mathematically you can write the reasoning like this: Assume

\begin{matrix} \sqrt{a} = \frac{p}{q} \\ where p and q are integers . \end{matrix}

\sqrt{a} = \frac{p}{q} where p and q are integers .

Take the square root on both sides and get

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{matrix} \sqrt{a} is not irrational \\ ⇓ \\ \sqrt{a} = \frac{p}{q} \\ ⇓ \\ a = \frac{p^{2}}{q^{2}} \\ ⇓ \\ a is not irrational \end{matrix}

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.

Want to know more?Sign UpIt's free!

What Is Direct Proof?

What Is Proof by Induction?

Go back