Proof by contrapositive

In mathematics, proof by contrapositive, or proof by contraposition, is a rule of inference used in proofs, where one infers a conditional statement from its contrapositive. In other words, the conclusion "if A, then B" is inferred by constructing a proof of the claim "if not B, then not A" instead. More often than not, this approach is preferred if the contrapositive is easier to prove than the original conditional statement itself.

Logically, the validity of proof by contrapositive can be demonstrated by the use of the following truth table, where it is shown that p → q and ${\displaystyle \mathrm{\neg }}$q → ${\displaystyle \mathrm{\neg }}$p share the same truth values in all scenarios:

Difference with proof by contradiction

Proof by contradiction: Assume (for contradiction) that ${\displaystyle \mathrm{\neg }A}$ is true. Use this assumption to prove a contradiction. It follows that ${\displaystyle \mathrm{\neg }A}$ is false, so ${\displaystyle A}$ is true.

Proof by contrapositive: To prove ${\displaystyle A\to B}$, prove its contrapositive statement, which is ${\displaystyle \mathrm{\neg }B\to \mathrm{\neg }A}$.