Proof by contrapositive

Proof by contradiction: Assume (for contradiction) that ${\displaystyle \neg A}$ is true. Use this assumption to prove a contradiction. It follows that ${\displaystyle \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 \neg B\to \neg A}$.

Let ${\displaystyle x}$ be an integer.

To prove: If ${\displaystyle x^{2}}$ is even, then ${\displaystyle x}$ is even.

Although a direct proof can be given, we choose to prove this statement by contraposition. The contrapositive of the above statement is:

If ${\displaystyle x}$ is not even, then ${\displaystyle x^{2}}$ is not even.

This latter statement can be proven as follows: suppose that x is not even, then x is odd. The product of two odd numbers is odd, hence ${\displaystyle x^{2}=x\cdot x}$ is odd. Thus ${\displaystyle x^{2}}$ is not even.

Having proved the contrapositive, we can then infer that the original statement is true.[3]

• Contraposition
• Modus tollens
• Reductio ad absurdum
• Proof by contradiction: relationship with other proof techniques.