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

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