Comprehensive Guide on Proof by Contraposition
Start your free 7-days trial now!
What is proof by contraposition?
Proof by contraposition, or proof by contrapositive, is a useful approach for proving certain mathematical statements. Suppose we wanted to prove the statement that if
Where
This means that "if the grass is wet, then it must be raining".
One way of proving
Where
As we shall explore more later, the reason we can prove
Where
In the following sections, we will prove and intuitively understand why a statement and its contrapositive statement are logically equivalent.
Proving that a proposition and its contrapositive proposition are logically equivalent
At first glance, it is difficult to see how
For those unfamiliar with truth tables, the truth table checks every combination of boolean propositions
- passing the exam - get a dollar
So the
for the first row, since
and , means you've passed the test and is given a dollar. Because I have kept my promise, is true.for the second row, since
and , means that you've passed the test but were not given a dollar. Because I have not kept my promise, then is false.for the third and fourth rows where
, the conditions of the promise does not apply because you didn't pass the exam in the first place. Since no promises were broken, is true. You may argue that I have not kept my promise so should be false, but this is not true because you cannot claim that I have not kept my promise because you didn't even pass the exam.
Now that we've looked at the truth table for
Notice how the column for
Intuition behind equivalent between contrapositive statements
If you’re like me, then you might not be satisfied with this technical proof, so let’s go through a simple example to intuitively understand why the contrapositive statement is logically equivalent.
Once again, consider the following statements:
(proposition): If it is raining, then the grass is wet (
).(contrapositive): If the grass is not wet, then it is not raining (
).
Our goal is to show that proposition (1) implies contrapositive (2), and contrapositive implies proposition. This would mean that they are logically equivalent!
Let’s break down the two statements into their essence:
(proposition): Raining ⟹ wet grass.
(contrapositive): Grass not wet ⟹ not raining.
Let’s now examine the logic flow when 1 implies 2 and 2 implies 1:
(proposition ⟹ contrapositive): Given (raining ⟹ wet grass), then (grass not wet ⟹ ?).
(contrapositive ⟹ proposition): Given (grass not wet ⟹ not raining), then (raining ⟹ ?).
Take a moment to think about how we should fill the
For the first case, given that raining implies wet grass is true, if the grass is not wet, then it must not be raining. For the second case, given that grass is not wet implies not raining, if it’s raining, then the grass must be wet. This is summarized below:
(proposition ⟹ contrapositive): Given (raining ⟹ wet grass), then (grass not wet ⟹ not raining)
(contrapositive ⟹ proposition): Given (grass not wet ⟹ not raining), then (raining ⟹ wet grass)
Personally, I find the second case much harder to wrap my head around because of the double negation but I hope you’ll eventually come to terms with the logic after a long thought! The takeaway here is that the proposition implies contrapositive and the contrapositive implies proposition:
This means that the proposition and its contrapositive proposition are logically equivalent!
How does contrapositive proof work?
Because the proposition
Case when proof by contraposition is simpler than direct proof
Prove that if
Solution. Let's first attempt to prove this directly. We know that any odd number can be represented as:
Where
Solving for
Unfortunately, it's quite unclear what our next steps should be.
Let's now try a proof by contraposition instead. The first step is to write the contraposition of our statement - if
We know that all even numbers can be expressed as
Taking the cube of both sides gives:
Again, since any number multiplied by