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 $p$ is true, then $q$ is true. Mathematically, we can represent this statement as:
Where $\implies$ is read as a “implies”. For instance, $p$ and $q$ might represent the following statements:
This means that "if the grass is wet, then it must be raining".
One way of proving $p\implies{q}$ is by proving its contrapositive statement:
Where $\neg$ represents negation. For instance, the contrapositive statement of \eqref{eq:FwsUDnZaQYqFKgubtxe} is:
As we shall explore more later, the reason we can prove \eqref{eq:RNvuMYDlbKO5aM4QztY} to prove \eqref{eq:CEgUEbg0dDnD8oiqo5Y} is that a statement and its contrapositive statement are logically equivalent:
Where $\equiv$ represents logical equivalence. Notice how the contrapositive statement is the complete reverse of the original statement - not only did we switch the ordering of$\implies$, but we’re also now dealing with negated $p$ and negated $q$.
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 $p\implies{q}$ is logically equivalent to $\neg{q}\implies{\neg{p}}$. We can prove this logical equivalence by using the so-called truth table. The truth table for $p\implies{q}$ is shown below:
$p$ | $q$ | $p\implies{q}$ |
|---|---|---|
$T$ | $T$ | $T$ |
$T$ | $F$ | $F$ |
$F$ | $T$ | $T$ |
$F$ | $F$ | $T$ |
For those unfamiliar with truth tables, the truth table checks every combination of boolean propositions $p$ and $q$. For instance, let $p$ and $q$ be defined as follows:
$p$ - passing the exam
$q$ - get a dollar
So the $p\implies{q}$ means that if you pass the exam, then you get a dollar. One way of thinking about this implication is to treat this as a promise, that is, if you pass the exam, then my promise is to give you a dollar. Now, let's understand the rows of the truth table one by one:
for the first row, since $p=T$ and $q=F$, $p\implies{q}$ means you've passed the test and is given a dollar. Because I have kept my promise, $p\implies{q}$ is true.
for the second row, since $ p=T$ and $q=F$, $p\implies{q}$ means that you've passed the test but were not given a dollar. Because I have not kept my promise, then $p\implies{q}$ is false.
for the third and fourth rows where $p=F$, the conditions of the promise does not apply because you didn't pass the exam in the first place. Since no promises were broken, $p\implies{q}$ is true. You may argue that I have not kept my promise so $p\implies{q}$ 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 $p\implies{q}$, let's examine the truth table for the contrapositive statement, that is, $\neg{q}\implies\neg{p}$ and compare this with $p\implies{q}$ like so:
$p$ | $q$ | $\neg{p}$ | $\neg{q}$ | $p\implies{q}$ | $\neg{q}\implies{p}$ |
|---|---|---|---|---|---|
$T$ | $T$ | $F$ | $F$ | $ T$ | $T$ |
$T$ | $F$ | $F$ | $T$ | $F$ | $F$ |
$F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
$F$ | $F$ | $T$ | $T$ | $T$ | $T$ |
Notice how the column for $p\implies{q}$ is identical to the column for $\neg{q}\implies{\neg{p}}$. Therefore, we can say that $p\implies{q}$ and $\neg{q}\implies{\neg{p}}$ are different ways of expressing the same logic.
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 ($p\implies{q}$).
(contrapositive): If the grass is not wet, then it is not raining ($\neg{q}\implies\neg{p}$).
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 $?$. Beware, the second implication is trickier compared to the first case.
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 $p\implies{q}$ is logically equivalent to the contrapositive $\neg{q}\implies\neg{p}$, we can choose to prove the contrapositive instead. In other words, if we can prove that the contrapositive is true, then the original proposition must also be true. The motivation behind this is that sometimes the contrapositive is simpler to prove than the original proposition. In the following section, we will look at a basic example of such a case.
Case when proof by contraposition is simpler than direct proof
Prove that if $x^3$ is odd, then $x$ is odd.
Solution. Let's first attempt to prove this directly. We know that any odd number can be represented as:
Where $n$ is some integer. Therefore, since $x^3$ is given to be odd, we have that:
Solving for $x$ gives us:
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 $x$ is even, then $x^3$ is even. If we can prove this contrapositive statement, then the original statement is also proven.
We know that all even numbers can be expressed as $2n$ where $n$ is some integer:
Taking the cube of both sides gives:
Again, since any number multiplied by $2$ is even, we have shown that $x^3$ must be even. Therefore, since the contrapositive statement is true, the original statement must also be true, that is, if $x^3$ is odd, then $x$ is odd as well.
