Proof by Contraposition

Proof Technique

Proof by Contraposition is a rule of inference used in proofs.

This rule infers a conditional statement from its contrapositive.

It is based on the Rule of Transposition, which says that a conditional statement and its contrapositive have the same truth value:

$p \implies q \dashv \vdash \neg q \implies \neg p$

In other words, the conclusion:

if $A$, then $B$

is drawn from the single premise:

if not $B$, then not $A$.

Explanation

Proof by Contraposition can be expressed in natural language as follows:

If we know that by making an assumption

$\neg q$

we can deduce

$\neg p$

then it must be the case that

$p \implies q$.

Thus it provides a means of proving a logical implication.

Examples

If $2^n - 1$ is Prime then $n$ is Prime

An example of a proof by contraposition would be as follows:

Let $2^n - 1$ be prime.

Then $n$ is prime.

This is proved by showing that:

If $n$ is composite, then $2^n - 1$ is composite.

Intuitionist Perspective

Proof by Contraposition is often confused with Reductio ad Absurdum, which also starts with an assumption $\neg q$.

Reductio ad Absurdum itself is often confused with Proof by Contradiction.

Unlike Reductio ad Absurdum however, Proof by Contraposition can be a valid proof in intuitionistic logic, just like Proof by Contradiction.

Specifically, suppose:

$p \implies q$

is true.

Suppose furthermore that we have a proof of:

$\neg q$.

Then if we had a proof of $p$, it could be turned into a proof of $q$.

This would imply

$q \land \neg q$

which is impossible.

Therefore, it cannot be the case that $p$ is true.

That is:

$\neg p$

$\Box$

However, now suppose:

$\neg q \implies \neg p$

is true.

Suppose furthermore that we have a proof of $p$.

Then, if we were to find a proof of $\neg q$, it could be turned into a proof of $\neg p$.

This would imply:

$p \land \neg p$

which is impossible.

Thus it is not possible to prove $\neg q$.

Now intuitionistic logic does not accept the Law of Excluded Middle.

That is, from an intuitionist perspective, knowing that a statement $q$ is not false does not automatically allow us to deduce that $q$ is actually true.

Under this assumption, we only know:

$\neg \neg q$

$\Box$

Hence the rejection, by the intuitionist school of the Reductio ad Absurdum, but not the Proof by Contradiction.

Also known as

The Proof by Contraposition is often confused with Reductio ad Absurdum, which also starts with an assumption $\neg q$.

To complicate things further, Reductio ad Absurdum itself is often confused with Proof by Contradiction.

Unlike Reductio ad Absurdum however, Proof by Contraposition is considered a valid proof in intuitionistic logic, as is Proof by Contradiction.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): proof by contraposition
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): proof by contraposition