search
Search
Login
Map of Data Science
menu
menu search toc more_vert
Robocat
Guest 0reps
Sign up
Log in
account_circleMy Profile homeAbout paidPricing
emailContact us
exit_to_appLog out
Map of data science
Thanks for the thanks!
close
Comments
Log in or sign up
Cancel
Post
account_circle
Profile
exit_to_app
Sign out
help Ask a question
Share on Twitter
search
keyboard_voice
close
Searching Tips
Search for a recipe:
"Creating a table in MySQL"
Search for an API documentation: "@append"
Search for code: "!dataframe"
Apply a tag filter: "#python"
Useful Shortcuts
/ to open search panel
Esc to close search panel
to navigate between search results
d to clear all current filters
Enter to expand content preview
icon_star
Doc Search
icon_star
Code Search Beta
SORRY NOTHING FOUND!
mic
Start speaking...
Voice search is only supported in Safari and Chrome.
Navigate to
A
A
brightness_medium
share
arrow_backShare
Twitter
Facebook
check_circle
Mark as learned
thumb_up
0
thumb_down
0
chat_bubble_outline
0
auto_stories new
settings

Comprehensive Guide on Proof by Contraposition

Probability and Statistics
chevron_right
Preliminary mathematics
schedule Dec 9, 2022
Last updated
local_offer
Tags
map
Check out the interactive map of data science

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:

$$\begin{equation}\label{eq:CEgUEbg0dDnD8oiqo5Y} p\implies{q} \end{equation}$$

Where $\implies$ is read as a “implies”. For instance, $p$ and $q$ might represent the following statements:

$$\begin{equation}\label{eq:FwsUDnZaQYqFKgubtxe} (\text{grass is wet}) \implies (\text{it is raining}) \end{equation}$$

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:

$$\begin{equation}\label{eq:RNvuMYDlbKO5aM4QztY} \neg{q}\implies{\neg{p}} \end{equation}$$

Where $\neg$ represents negation. For instance, the contrapositive statement of \eqref{eq:FwsUDnZaQYqFKgubtxe} is:

$$\begin{equation}\label{eq:UalTGfu7zq1R6S2IY2r} (\text{it is not raining}) \implies (\text{grass is not wet}) \end{equation}$$

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:

$$\begin{equation}\label{eq:qYgBNKjv350EmGgTNxQ} p\implies{q}\;\equiv\;\neg{q}\implies{\neg{p}} \end{equation}$$

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:

  1. (proposition): If it is raining, then the grass is wet ($p\implies{q}$).

  2. (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:

  1. (proposition): Raining ⟹ wet grass.

  2. (contrapositive): Grass not wet ⟹ not raining.

Let’s now examine the logic flow when 1 implies 2 and 2 implies 1:

  1. (proposition ⟹ contrapositive): Given (raining ⟹ wet grass), then (grass not wet ⟹ ?).

  2. (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:

  1. (proposition ⟹ contrapositive): Given (raining ⟹ wet grass), then (grass not wet ⟹ not raining)

  2. (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:

$$\begin{equation}\label{eq:tnA5iWEMBNUqZZY3MAy} p\implies{q}\;\equiv\;\neg{q}\implies{\neg{p}} \end{equation}$$

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.

Example.

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:

$$2n+1$$

Where $n$ is some integer. Therefore, since $x^3$ is given to be odd, we have that:

$$x^3=2n+1$$

Solving for $x$ gives us:

$$x=(2n+1)^{1/3}$$

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:

$$x=2n$$

Taking the cube of both sides gives:

$$x^3=8n^3=2(4n^3)$$

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.

robocat
Published by Isshin Inada
Edited by 0 others
Did you find this page useful?
thumb_up
thumb_down
Ask a question or leave a feedback...