The method of proof by contraposition is based on the logical equivalence between a statement and its contrapositive. The underlying reasoning is that since a conditional statement is logically equivalent to its contrapositive, if the contrapositive is true, then the statement must also be true. To see why this assertion is correct let us start with the following. [See my logic page for details.]
Let p and q be propositions. The contrapositive of the implication p → q is the implication
We can state state this fact as follows:
An implication and its contrapositive have the same truth-value. That is, proposition p → q and proposition
p are logically equivalent.
From the above fact, one can easy derive the conclusion that to prove p → q one might just as well prove
p, if this is for one reason or another
more feasible. Then, to prove
p, one has access to the syllogistic and reductio ad absurdum method for the contrapoitive is again only an implication.
From practical or computational point of view, we follow following three steps to proof the statement by contraposition:
Step 1. Take the contrapositive of the given statement.
Step 2. Prove the contrapositive by a direct proof or reductio ad absurdum.
Step 3. Conclude the given statement is true (using the above-mentioned fact).
Step 1. Express the statement to be proved in the form:
∀ x ∈ D, if P(x), then Q(x)
Step 2. Rewrite this statement in the contrapositive form:
∀ x ∈ D, if Q(x) is false, then P(x) is false
Step 3. Prove the contrapositive statement by direct proof:
If the square of an integer n is even, then integer is even.