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.
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.
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.
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.
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).
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.
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
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.
Let me show you another example where a contrapositive proof is so much easier to carry out.
Proposition: If is even then x is even
Proof: Assume that x is odd then we have an integer k such that x = 2k+1.
Then which is an odd number. This means that if is even then x is even.
Proving this with a direct proof would us to show that can be transformed into for some value of m, something which I would not really enjoy all that much.
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.