# 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.

## Contents

## 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 **Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A=\{a_{1},a_{2},\ldots ,a_{n}\}}**
and **Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle B=\{b_{1},b_{2},\ldots ,b_{m}\}}**
. Since **Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\neq m}**
, 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 **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle P\Rightarrow Q}**
and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \lnot P\Rightarrow \lnot Q.}**

### 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 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***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n^2 = n\cdot n}**is even.**Proof**- First we do a constructive proof. Suppose that
*n*is an even integer. Then by defintion of even,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n = 2\cdot k}**for some integer*k*. Then**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n^2 = (2k)^2 = 2k\cdot 2k = 2(k\cdot 2\cdot k)}**. Since**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle k\cdot 2\cdot k}**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.

- First we do a constructive proof. Suppose that

## Exercises[edit]

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

- An integer