Proof by Contraposition

From ProofWiki
Jump to navigation Jump to search

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