Proof by Contrapositive

Sometimes when you are trying to solve a problem, you realize you really don’t have a lot of information to start with. One piece of good advice in problem-solving is to try to work backwards. That is, sometimes if you know what you want your solution to look like, you can backtrack to learn something about how you should be creating that solution.

One of the mathematical versions of this is proof by contradiction – this has already been discussed. But there is another that is called proof by contrapositive. And this one doesn’t involve the very strange idea of intentionally saying something false.

The method of contrapositive comes from the broader field of logic and is a method of rewriting any statement that looks like “If A is true, then B is true.” To see how this works, we will use visuals using what are normally called Venn diagrams. In case this isn’t familiar, a Venn diagram is a collection of circles used to represent some kind of situation happening. You can represent some kind of event as a circle, and to be inside the circle means the event happened, and to be outside means it did not happen.

Consider the Venn diagram below, where the blue region B should be thought of as containing the red region R, which in turn contains the green region G.

A visual for understanding the inside/outside nature of contrapositives.

We can think of the ‘if-then’ structure in terms of the ‘inside-outside’ relationship in the picture. When we said before that ‘If A, then B,’ we can equally well phrase that as ‘In every situation that A happens, then we also know B happens.’ In terms of our picture, we might say something like ‘Whenever we are inside the green circle G, we are also inside the red circle R.’ True enough – the green circle is perfectly inside the red circle. Translating this into ‘if-then’ language as we did earlier with A and B, we can say that ‘If G, then R‘ (where by G we mean ‘inside of the green circle, and similarly with R).

So this gives us a visual depiction, via Venn diagrams, of an if-then situation. In this new visual situation, it is equally easy to think about outsides of shapes rather than their insides. So, for a moment, we will think about the outside of R and G rather than their insides. When we do this, things get a little flipped around. The outside of the red circle R is the region colored blue. The outside of the green circle G are the regions colored blue and red. So, the outside of R is literally contained inside of the outside of G. Since we have already learned that this ‘contained in’ relationship can be translated into if-then, we can use this to express the idea

If outside of R, then outside of G.

We aren’t quite back to normal if-then statements yet – what exactly do we mean by ‘outside’? Well, if we remember that the inside represents something happening (or being true), while the outside represents something not happening (or being false), then we can do a little bit better.

If R is false, then G is false.

Or, we could more concisely say

If not R, then not G.

Now, one last comment is needed. We have to notice that the reason we were capable of making these kinds of statements about the outside of R and the outside of G was because G was inside of R. Since G is totally inside of R, anything outside of R couldn’t be inside of G (since that would make it inside R also). In other words, you begin to realize that the inside/outside statements are actually just different ways of saying the same thing. So the ‘if-then’ versions must also be saying the same thing.

What we have learned then is that if we have a statement if A, then B, we can equally use the statement if not B, then not A. The rule I have just described is what goes by the title of ‘contrapositive.’

This method can have the convenience that working backwards has in problem-solving. You can choose whether not B or A gives you more usable information. If A gives you plenty of information, you are working forwards towards B. If not B gives you more usable information, then use contrapositive and work backwards towards not A.

To conclude this article on proof by contrapositive, I will write an example using odd and even numbers. You can solve this problem in the ‘regular way’ if you use some information about prime numbers – but if you do contrapositive, the only thing involved is the distributive property and the definition of even and odd numbers – which are simpler than the ideas you have to use to go directly from A to B.

So, here is the proof – using contrapositive. For anyone curious about the ‘forwards’ proof (or ‘inside’ using the visual language of the Venn diagrams) I’ll give a hint at the end about how to do that.

Note: When made to match the Venn diagram earlier in the article, the green region is to be thought of as ‘x^2 is an even number’ and the red region is to be thought of as ‘x is also even.’

Theorem: If x^2 is an even number, then x is also even.

Proof: We use the method of contrapositive. That is, we will actually prove that if x is not even, then x^2 is not even. Since the opposite of even is odd, this means we want to prove that if x is odd, then x^2 is odd. Since all odd numbers have the shape x = 2y + 1 for some other whole number y, we can calculate x^2 using substitution:

x^2 = (2y+1)^2 = 4y^2 + 4y + 1 = 2(2y^2 + 2y) + 1.

Since 2y^2 + 2y is a whole number, this means that x^2 is odd. We have therefore completed our proof.

(Hint: To begin with x^2 is even and end with x is even, we know since x^2 is even that x^2 = 2y for some whole number y. You can use a proof by contradiction by assuming that x is odd, or alternatively you can use the fact that the only way to multiply two positive whole numbers to obtain 2 is 1 \times 2.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: