Mathematical Proof/Methods of Proof/Proof by Contrapositive

The contrapositive of a statement negates the conclusion as well as the hypothesis. It is logically equivalent to the original statement asserted. Often it is easier to prove the contrapositive than the original statement. This section will demonstrate this fact.

The Concept

edit

The idea of the contrapositive is proving the statement "There is no x such that P(x) is false." as opposed to "P(x) is true for every x."

This is not to be confused with a Proof by Contradiction. If we are trying to prove the statement  , we can do it constructively, by assuming that P is true and showing that the logical conclusion is that Q is also true. The contrapositive of this statement is  , so we assume that Q is false and show that the logical conclusion is that P is also false. However, in a proof by contradiction, we assume that P is true and Q is false and arrive at some sort of illogical statement such as "1=2."

A proof revisited

edit

The most basic example would be to redo a proof given in the last section. We proved Theorem 2.1.4 to be true by the constructive method. Now we can prove the same result using the contrapositive method. For ease of reading, I will change the wording of the theorem.

Theorem 2.2.1 (also Theorem 2.1.4). If A and B are finite sets and  , then  .

The wording is probably more natural in the 2.1.4 version, but this shows how the proof is to be done. We assume that we have two finite sets A and B and that they do not have the same number of elements. So let   and  . Then, number the elements in A and B, so   and  . Since  , either   or  . Without loss of generality, we assume that  . Consider the set  . Since A has only n elements, we can take out at most n elements from B, leaving at least m-n elements in B-A. This shows that there is at least one element in B that is not in A, therefore  .

Arithmetic

edit

I'm sure we all know how to do arithmetic already, but mathematicians like to be "rigorous." That means that we like to have clear definitions of everything we use.

Axiom 7. The numbers 0 and 1 exist.
Definition 2.2.2. The operator + is defined so that 1+0=1 and   is an infinite set. We write the elements of this set as   and define  .
Definition 2.2.3. The operator   is defined so that     and   We also define  

The above definitions are just formalities. We know what numbers are and how they work. This is just a mathematical definition. Notice that only integer multiplication has been defined. Now we need one more definition to prove the following theorem.

Definition 2.2.4. An integer is said to be even if it is a multiple of two. That is, 'n' is even if n = 2k for some integer k. If this is not true, then it is said to be odd. The property of whether a number is even or odd is its parity.
Theorem 2.2.5. If x and y are integers such that   is odd, then  

To prove this by contrapositive, we assume that   and show that   is even. If  , then  , which by Definition 2.2.3 is  , so   is a multiple of 2 and is therefore even.

Biconditionals

edit

Proofs by contrapositive are very helpful in proving biconditional statements. Recall that a biconditional is of the form   (P if and only if Q). To prove a biconditional we need to prove that   and   However, if we use the contrapositive, we can show   and  

More Arithmetic

edit

Prime numbers are very interesting in number theory, but also in arithmetic. In fact, the Fundamental Theorem of Arithmetic has to do with primes. Here we will not give a proof, just a statement of the theorem.

Definition 2.2.6. A prime number is a positive integer that has no multiple other than 1 and itself. A number that is not prime is called composite.
Theorem 2.2.7 (Fundamental Theorem of Arithmetic). Every integer has a unique factorization of primes, excluding reorderings.

This theorem will be very useful in the proof of the next theorem.

Theorem 2.2.8. An integer n is even if and only if its square   is even.
Proof
  • First we do a constructive proof. Suppose that n is an even integer. Then by defintion of even,   for some integer k. Then  . Since   is an integer because it is the product of integers, we see that   is even. This shows the "only-if" part of the theorem.
  • To show the "if" part, we use a proof by contrapositive. Assume that n is not even, or that n is odd. Let   be the prime factorization of n. Then none of the   are 2 for any i. We consider the square   and notice that there are no multiples that are equal to 2, so we conclude that   is odd. This proves the theorem.

Exercises

edit
  1. Prove the following by contrapositive:
    1. An integer n is even if and only if n+1 is odd.
    2. If n and m have the same parity then n+m is even.