Colorful House of Math logo
Log in

What Is Proof by Contrapositive?

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

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

(not q) (not p)

will then be as follows:

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

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

Theory

The Contrapositive

(not q) (not p) is the contrapositive of the implication p q.

Read this paragraph slowly:
p q and (not q) (not p) are equivalent. This means that if you can prove that (not q) (not p), then you have also proven that p q. This is useful because sometimes it is easier to prove (not q) (not p) than p q.

Theory

Proof by Contrapositive

To prove that p q, it suffices to prove that

(not q) (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 again 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 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) (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 a is also irrational. You want to show an implication. The implication you want to show is p q, where p =a is irrational” and q =a is irrational”. The contrapositive is (not q) (not p), or in other words

a is not irrational a is not irrational

Since “not irrational” is the same as “can be written as a fraction”, you can begin with the implication “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 a = p q. You want to show that a is a fraction, then 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) (not p).

Mathematically you can write the reasoning like this: Assume

a = p q, where p and q are integers.

a = p q, where p and q are integers.

Take the square root on both sides and get
a = p2 q2.

It shows that a can be written as a fraction, such that a is not an irrational number. You have shown that a is not irrational a = p q a = p2 q2 a is not irrational,

which is the contrapositive version of what you wanted to show, which was that if a is an irrational number, 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 such as “a is not irrational”. These are much easier to work with, because a number which is not irrational is a fraction.

Want to know more?Sign UpIt's free!
White arrow pointing to the LeftPrevious entry
What Is Direct Proof?
Next entryWhite arrow pointing to the right
What Is Proof by Induction?