Proof Method: Contrapositive proof

On my journey to improve my mathematical rigour I have covered direct proofs and Proof by Contradiction. In this post I will cover the third method for proving theorems.

Reading up on different methods for proving things I realized that a contrapositive proof is a really clever thing to used and often a better way to prove things than a proof by contradiction. However, I love the proof by contradiction so much that I wanted to cover it first.

The contrapositive proof goes the opposite way of the direct proof. In the direct proof we had

Given P then Q

In the Contrapositive proof we are turning it around and

Given ~Q then ~P

Notice that we are not trying to show that ~P infers ~Q as that would be the same as to say Q infers P. We are showing that if Q is false then P must be false as well.

The simplest example I can conjure up based on this logic is

Proposition if x > 1 then x > 0

Here we have that P is the conditional statement that if x> 1 then Q follows and Q is the statement that x > 0.

A direct proof assumes that P is true and then shows that Q follows, in this example it would go:

Proof: Assume that x > 1

then x > 0.

QED.

A contrapositive proof goes the other way assuming that ~Q and then it follows that ~P. In this example it goes

Proof: Assume that x < 0

then x < 1.

QED.

Which in this case is obviously true.

A contrapositive proof should not be confused for a converse proof where we want to show that Q implies P which in the above example is false not necessarily the case

Proposition: If x > 0 then x > 1

Assume that x > 0

then x > 0.

QED.

Which is not true.

But why turn it all upside down? Couldn’t we just use direct proof? In many cases yes we could use a direct proof, but the contrapositive version is easier to read. Let us grab an example.

Example 1

Proposition: If x and y are to integers for which x+y is even then x and y have same parity (either both are even or both are odd).

Contrapositive proof: Assume that x and y have different parity (~Q). I will assume that x is odd and y is even without loss of generality, since x and y are commutative.

Then from the definitions of even and odd defined in example 1 in the contradiction post we have that there exists two number m and n such that x = 2m + 1 and y = 2n.

This means we have x + y = 2m + 1 + 2n = 2(m+n) +1. This is the definition of an odd number and thus x+y is odd (~P).

QED.

This is a proof by a contrapositive statement by assuming that we have the opposite result, what is the starting condition. We could very well have done this as a direct proof as well and we would end up with two cases – let’s try.

Direct proof: We have two cases of same parity either x and y is even or x and y is odd

odd: if x and y are odd there exists two integers m,n such that x = 2m+1 and y = 2n+1.

This means awe have x + y = 2m+1 + 2n+1 = 2(m+n+1). This is the definition of an even number.

Even:

if x and y are even there exists two integers m,n such that x = 2m and y = 2n.

This means awe have x + y = 2m + 2n = 2(m+n). This is the definition of an even number

So in both cases x+y is even if x and y have the same parity

QED.

As you can see we can easily show it through direct proof, but it flows better as a contrapositive proof since we don’t have to go through two different cases.

Compared to a proof of contradiction you have the advantage that the goal is clear. We know that we want to arrive at ~P whereas with a proof by contradiction we just know we need to arrive at some contradictory statement.

Example 2

Let me show you another example where a contrapositive proof is so much easier to carry out.

Proposition: If $x^2$ is even then x is even

Proof: Assume that x is odd then we have an integer k such that x = 2k+1.

Then $x^2 = (2k+1)^2 = 4k^2 + 4k +1 = 2(2k^2 + 2k) + 1$ which is an odd number. This means that if $x^2$ is even then x is even.

QED.

Proving this with a direct proof would us to show that $x^2 = 2k$ can be transformed into $x = 2m$ for some value of m, something which I would not really enjoy all that much.

Wrapping up

There are some rather nice things happening when using contrapositive proofs, the difficulty lies in identifying when it will be easier to use than a direct proof. I haven’t been able to find some good guidelines for when to try to apply a contrapositive proof. Do you have some good guidelines, or does it come with experience?

I found one person Tao Jiang who tries to answer the question

When do we use proof by contrapositive? We try this if it is easier to prove than the original statement. Usually this is the case if condition ~B is more convenient to work with than condition A.

I havn’t been able to trace the pdf file back to one person, but I believe it supports my statement that knowing when to use a contrapositive proof comes with intuition.

As usual Hammacks book has a lot of good exercises in it if you are looking for some problems to practice on. I have solved a few of them to taste the idea of a contrapositive proof.

Posted by Kristian

SuprDewd

The simplest example you could conjure up was pretty confusing. 😀

Kristian

Hi SuprDewd

I have just rewritten that part, so I hope it has become a lot clearer what I mean. I could definitely see that it wasn’t clear before when I reread the paragraph. So thanks for letting me know.

/Kristian

meryl

is there any example or i need more example ‘coz this is just an example already to our teacher….

Kristian

Hi Meryl

There are several good examples in Hammacks book http://www.people.vcu.edu/~rhammack/BookOfProof/

KRYSTA

HOW DO I PROVE BY CONTRAPOSITIVE THAT “IF N IS ODD, THEN 5N+11 IS EVEN”

Kristian

First of all, please don’t write in all caps. It is difficult to read. Besides it is considered shouting by many. Me included.

That being said, the problem sounds like something you are supposed to do for homework. Otherwise it would be simpler to do it by a direct proof.

However, you want to assume the opposite, and then show that you arrive at the opposite result. Thereby concluding that you are right.

So what you can do is to plug in the definition for an even number (N = 2k) for some integer k and then show that you will arrive at the definition of an odd number.

charmie

how do i prove 2 to the power of n minus 1 is prime, then n is prime.

Kristian

You don’t since it is not true. 2^11-1 = 2047 = 23*89

Ben Tilly

A few years late, but I just stumbled across this and thought I should answer when you would use the contrapositive proof.

There is a connection between contrapositive proofs and proof by contradiction. The connection is that any proof by contrapositive can trivially be turned into a proof by contradiction, and most proofs by contradiction can EITHER be turned into a contrapositive proof OR ELSE has a simpler hidden direct proof.

Basically people try to prove that A implies B by assuming A and not B and trying to derive a contradiction. Generally they either find a direct proof that A implies B and then point to the contradiction with the assumption of not B (thereby obfuscating a simpler proof), or else they prove that not B implies not A and point to the contradiction when they could have equally easily called it a proof of the contrapositive.

Theoretically a proof by contradiction does not need to take either of those simple forms. However I have never seen an example in the wild that doesn’t.

Therefore there is no need to try both the contrapositive and proof by contradiction. But I prefer encouraging the contrapositive because reaching for contradiction first can result in accidental obfuscation.

@Kristian: He was asking how to prove that (2^n – 1 being prime) ==> (n is prime), not the other way around. This statement is true, and proven. If you have a Mersenne prime (2^n – 1), then its exponent `n` is guaranteed to be prime. What you showed as a “counter-example” is actually for the converse statement, which is false: `n` being prime does not guarantee `2^n – 1` being prime too.

@charmie: To prove your statement, you can try proving its contrapositive: consider what would happen if `n` were composite, that is `n = a·b`. If you can prove from it that `2^(a·b) – 1` is also composite, then you proved the contrapositive, which automatically proves your original statement, because they’re logically equivalent. In your proof, you can use the known and proven fact that `x^n – y^n` is divisible by `x – y`, and make sure that `x – y` is not 1 (which would be the trivial divisor, which is a factor of every number, including primes), but greater than 1.