Proof by contrapositive
In logic, the contrapositive of a conditional statement is formed by negating both terms and reversing the direction of inference. More specifically, the contrapositive of the statement "if A, then B" is "if not B, then not A." A statement and its contrapositive are logically equivalent, in the sense that if the statement is true, then its contrapositive is true and vice versa.[1]
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.[2] 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 [math]\displaystyle{ \lnot }[/math]q → [math]\displaystyle{ \lnot }[/math]p share the same truth values in all scenarios:
| p | q | [math]\displaystyle{ \lnot }[/math]p | [math]\displaystyle{ \lnot }[/math]q | p → q | [math]\displaystyle{ \lnot }[/math]q → [math]\displaystyle{ \lnot }[/math]p |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Difference with proof by contradiction
Proof by contradiction: Assume (for contradiction) that [math]\displaystyle{ \neg A }[/math] is true. Use this assumption to prove a contradiction. It follows that [math]\displaystyle{ \neg A }[/math] is false, so [math]\displaystyle{ A }[/math] is true.
Proof by contrapositive: To prove [math]\displaystyle{ A \to B }[/math], prove its contrapositive statement, which is [math]\displaystyle{ \neg B \to \neg A }[/math].
Example
Let [math]\displaystyle{ x }[/math] be an integer.
- To prove: If [math]\displaystyle{ x^2 }[/math] is even, then [math]\displaystyle{ x }[/math] 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 [math]\displaystyle{ x }[/math] is not even, then [math]\displaystyle{ x^2 }[/math] 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 [math]\displaystyle{ x^2=x\cdot x }[/math] is odd. Thus [math]\displaystyle{ x^2 }[/math] is not even.
Having proved the contrapositive, we can then infer that the original statement is true.[3]
See also
- Contraposition
- Modus tollens
- Reductio ad absurdum
- Proof by contradiction: relationship with other proof techniques.
References
- ↑ Sheldon, Frederick. "Conditional Statement Forms". https://www.csm.ornl.gov/~sheldon/ds/sec1.2.html.
- ↑ Cusick, Larry. "Proofs by Contrapositive". http://zimmer.csufresno.edu/~larryc/proofs/proofs.contrapositive.html.
- ↑ Franklin, J.; A. Daoud (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 978-0-646-54509-7. http://www.maths.unsw.edu.au/~jim/proofs.html. (p. 50).
 |  |
