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

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 $P\Rightarrow Q$, 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 $\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$, 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

The most basic example would be to redo a proof given in the last [[../Constructive Proof|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 $|A|\ne |B|$, then $A\ne B$.

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 $n=|A|$ and $m=|B|$. Then, number the elements in A and B, so $A=\{a_1,a_2,\dots ,a_n\}$ and $B=\{b_1,b_2,\dots ,b_m\}$. Since $n\ne m$, either $n<m$ or $m<n$. Without loss of generality, we assume that $n<m$. Consider the set $B-A$. 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 $B\ne A$.

Arithmetic

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 $\{1,1+1,1+1+1,1+1+1+1,\dots \}$ is an infinite set. We write the elements of this set as $1,2,3,4,\dots$ and define $n+m=(1+1+\cdots (n\text{ times}))+(1+1+\cdots (m\text{ times}))=(1+1+\cdots (n+m\text{ times}))$.

Definition 2.2.3. The operator $\cdot$ is defined so that $1\cdot 0=0,$ $1\cdot 1=1$ and $n\cdot 1=1+1+\cdots (n\text{ times}).$ We also define $n\cdot m=m+m+m+\cdots (n\text{ times}).$

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 $x+y$ is odd, then $x\ne y.$

To prove this by contrapositive, we assume that $x=y$ and show that $x+y$ is even. If $x=y$, then $x+y=x+x$, which by Definition 2.2.3 is $2\cdot x$, so $x+y$ is a multiple of 2 and is therefore even.

Biconditionals

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

More Arithmetic

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 $n^2=n\cdot n$ is even.

Proof

• First we do a constructive proof. Suppose that n is an even integer. Then by definition of even, $n=2\cdot k$ for some integer k. Then $n^2=(2k{)}^2=2k\cdot 2k=2(k\cdot 2\cdot k)$. Since $k\cdot 2\cdot k$ is an integer because it is the product of integers, we see that $n^2$ 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 $n=a_1^{k_1}\cdot a_2^{k_2}\cdots a_m^{k_m}$ be the prime factorization of n. Then none of the $a_i$ are 2 for any i. We consider the square $n^2=a_1^{2k_1}\cdots a_m^{2k_m}$ and notice that there are no multiples that are equal to 2, so we conclude that $n^2$ is odd. This proves the theorem.

Exercises

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.