Proof by Contraposition

 

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 ~q → ~p.

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 ~q → ~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 ~q → ~p, if this is for one reason or another more feasible. Then, to prove ~q → ~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).

 

Formally,

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:

    3a. Suppose x is a [particular but arbitrarily chosen] element of D such that Q(x) is false.

    3b. Show that P(x) is false.

 

Now we follow the above-mentioned three steps to prove the given statement by the method of contraposition. The given statement is:

If the square of an integer n is even, then integer is even.

Formally,

∀ all integers n, if n2 is even, then n is even.

 

Step 1. Form the contrapositive of the given statement. That is,

For all integers n, if n is not even, then n2 is not even

But, we know that an integer is not even if, and only if, it is odd [by parity property]. So, the contrapositive becomes

For all integer n, if n is odd, then n2 is odd
Step 2. Now prove the contrapositive using method of direct proof:

Suppose n is [particular but arbitrarily chosen] integer. [We must show that n2 is also odd.] By definition of odd, we have

n = 2k + 1 for some integer k.

Then by substitution, we have

                                     n . n = (2k + 1) . (2k + 1)

                                             = 4k2 + 2k + 2k + 1

                                             = 2(2k2 + 2k) + 1

Now ((2k2 + 2k) is an integer. [Because products and sums of integers are integers and 2 and k are both integers.] Hence, we have a form:

                                          n . n = 2 . (some integer) + 1

or                                          n2 = 2 . (some integer) + 1

and so by definition of odd is n2 odd.
Step 3. Therefore, the given statement is true by the logical equivalence between a statement and its contrapositve.

Note that most mathematics textbooks do not write this step and end proofs at the point at which the direct proof has been obtained.