Proof by Contrapositive

Proof by contrapositive takes advantage of the logical equivalence between "P implies Q" and "Not Q implies Not P". For example, the assertion "If it is my car, then it is red" is equivalent to "If that car is not red, then it is not mine". So, to prove "If P, Then Q" by the method of contrapositive means to prove "If Not Q, Then Not P".

Example: Parity

Here is a simple example that illustrates the method. The proof will use the following definitions.

Definitions.

  1. An integer x is called even (respectively odd) if there is another integer k for which x = 2k (respectively 2k+1).
  2. Two integers are said to have the same parity if they are both odd or both even.
For the purpose of this example we will assume as proved that each integer is either even or odd.

Theorem. If x and y are two integers for which x+y is even, then x and y have the same parity.

Proof. The contrapositive version of this theorem is "If x and y are two integers with opposite parity, then their sum must be odd." So we assume x and y have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose x is even and y is odd. Thus, there are integers k and m for which x = 2k and y = 2m+1. Now then, we compute the sum x+y = 2k + 2m + 1 = 2(k+m) + 1, which is an odd integer by definition.

q

How Is This Different From Proof by Contradiction?

The difference between the Contrapositive method and the Contradiction method is subtle. Let's examine how the two methods work when trying to prove "If P, Then Q". The method of Contrapositive has the advantage that your goal is clear: Prove Not P. In the method of Contradiction, your goal is to prove a contradiction, but it is not always clear what the contradiction is going to be at the start.

A Test For Perfect Squares

In this example, we will need two notions. An integer n is called a perfect square if there is another integer k such that n = k2. For example, 13689 is a perfect square since 13689 = 1172.

The second idea is the remainder and modular arithmetic. For two integers m and n, n mod(m) = r will be the remainder resulting when we divide m into n. This means that there is an integer q such that n = mq + r. For example, 127 mod(29) = 11 since 29 will go into 127 4 times with a remainder of 11 (or, in other words, 127 = (4)(29) + 11). Determining whether or not a positve integer is a perfect square might be difficult. For example, is 82,642,834,671 a perfect square? First we compute 82,642,834,671 mod(4) = 3. Then use this theorem:

Theorem. If n is a positive integer such that n mod(4) is 2 or 3, then n is not a perfect square.

Proof. We will prove the contrapositive version: "If n is a perfect square then n mod(4) must be 0 or 1." (Do you understand why this is the contrapositive version?) Suppose n = k2. There are four cases to consider.

  1. If k mod(4) = 0, then k = 4q, for some integer q. Then, n = k2 = 16 q2 = 4(4 q2) , i.e. n mod(4) = 0.
  2. If k mod(4) = 1, then k = 4q + 1, for some integer q. Then, n = k2 = 16 q2 + 8 q + 1= 4(4 q2 + 2 q) + 1, i.e. n mod(4) = 1.
  3. If k mod(4) = 2, then k = 4q + 2, for some integer q. Then, n = k2 = 16 q2 + 16 q + 4 = 4(4 q2 + 4 q + 1), i.e. n mod(4) = 0.
  4. If k mod(4) = 3, then k = 4q + 3, for some integer q. Then, n = k2 = 16 q2 + 24 q + 9 = 4(4 q2 + 6 q + 2) + 1, i.e. n mod(4) = 1.
q

Exercises

Prove each of the following by the contrapositive method.

  1. If x and y are two integers whose product is even, then at least one of the two must be even.

  2. If x and y are two integers whose product is odd, then both must be odd.

  3. If n is a positive integer such that n mod(3) = 2, then n is not a perfect square.

  4. If a and b a real numbers such that the product a b is an irrational number, then either a or b must be an irration number.

Next==>If, and Only If

<==Back To Proof by Contradiction

Back to Proofs

In Polish