# 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.

This proof 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

- $\neg p$.

However, now suppose

- $\neg q \implies \neg p$

is true.

Suppose furthermore that we have a proof of

- $p$.

Then if we had 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$.

That means in this case we only know

- $\neg \neg q$

## Sources

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