Proof by Contradiction and Contrapositive

Section 3.4 Proof by Contradiction and Contrapositive

In this section we will learn two new proof techniques, contradiction and contrapositive. Both proof techniques rely on being able to negate mathematical statements.

🔗

As we add more proof techniques, it is important to realize that you are not expected to know which technique to use when you start a proof. Proof-writing often takes some trial and error. First try a direct proof, if you get stuck, you may think about whether breaking your set into cases will help, or whether negating a statement will make it easier to use. It is also quite possible that different methods can be used to prove the same statement.

🔗

Subsection 3.4.1 Proof by Contradiction

The basic idea behind proof by contradiction is that if you assume the statement you want to prove is false, and this forces a logical contradiction, then you must have been wrong to start. Thus, you can conclude the original statement was true. By a logical contradiction, we generally mean a statement that must be both true and false at the same time. When writing a proof by contradiction you must be very careful in your logical reasoning. It must be clear that you reach a contradiction though careful logical deduction.

🔗

Method of Proof by Contradiction.

Assume the statement to be proved is false. Or, assume the negation of the statement is true.
🔗

🔗
Show you reach some logical contradiction. This means you have a statement in your proof that must be both true and false.
🔗

🔗
Conclude the original statement is true.
🔗

🔗

🔗

Since contradiction relies on negating statements, recall the following negations from Section 1.3:

\(p\rightarrow q\) has negation \(p\ \wedge \neg q\)

🔗
\(p\ \wedge q\) has negation \(\neg p\ \vee \neg q\)

🔗
\(p\ \vee q\) has negation \(\neg p\ \wedge \neg q\)

🔗

🔗

Example 3.4.1. Proof by Contradiction.

Prove if \(x^2+y=13\) and \(y\neq 4\) then \(x\neq 3\text{.}\)

🔗

Before proving this statement, we note that it has logical form \((p\wedge q)\rightarrow r\text{.}\) Since we are doing a proof by contradiction, we need to negate this statement. The negation has form \((p\wedge q) \wedge \neg r\text{.}\) Thus, we will assume \(p\) is true, \(q\) is true, and \(r\) is false.

🔗

Proof.

By contradiction. We assume \(x^2+y=13, y\neq 4\) and \(x=3\text{.}\) Since \(x=3\) and \(x^2+y=13\text{,}\) we get \(9+y=13\text{.}\) Thus, \(y=4\text{.}\) But this contradicts that \(y\neq 4\text{.}\)

🔗

Example 3.4.2. There Is No Greatest Integer.

Prove there is no greatest integer.

🔗

Proof.

By contradiction. Assume there is a greatest integer. Call this greatest integer \(N\text{.}\) Now consider \(N+1\text{.}\) Since \(N\) is an integer, \(N+1\) is an integer. We can see that \(N+1>N\text{,}\) which contradicts that \(N\) was the greatest. Therefore, there is no greatest integer.

🔗

Activity 3.4.1. Rational Plus Irrational.

Consider the statement: the sum of a rational number and an irrational number is irrational.

🔗

(a)

Try to determine if the statement is true or false by trying examples and looking for a counterexample.

🔗

(b)

Write the statement using variables and quantifiers.

🔗

(c)

Write the negation of the statement.

🔗

(d)

Now assume the negation is true and find a contradiction.

🔗

(e)

The work in (d) is your scratch work. Write a careful proof by contradiction to show the original statement is true.

🔗

Subsection 3.4.2 Proof by Contrapositive

Recall from Section 1.3 the contrapositive of \(p\rightarrow q\) is \(\neg q\rightarrow \neg p\text{.}\) Also recall, that \(p\rightarrow q\) and \(\neg q\rightarrow \neg p\) are logically equivalent. This allows us to use the contrapositive in place of the original statement. Thus, a proof by contrapositive is just a direct proof of the contrapositive statement.

🔗

Method of Proof by Contrapositive.

Write the statement to be proved in the form \(\forall x\in D\text{,}\) if \(P(x)\) then \(Q(x)\text{.}\)
🔗

🔗
Write the contrapositive of the statement: \(\forall x\in D\text{,}\) if \(\neg Q(x)\) then \(\neg P(x)\text{.}\)
🔗

🔗
Prove the contrapositive directly: assume \(\neg Q(x)\text{,}\) show \(\neg P(x)\text{.}\)
🔗

🔗

🔗

Example 3.4.3. A Divisibility Proof by Contrapositive.

Prove for all \(a, b, c\in \mathbb{Z}\text{,}\) if \(a \nmid bc\) then \(a \nmid b\text{.}\)

🔗

This statement has contrapositive: for all \(a, b, c\in \mathbb{Z}\text{,}\) if \(a \mid b\) then \(a \mid bc\text{.}\)

🔗

Proof.

By contrapositive. Let \(a, b, c\in \mathbb{Z}\text{.}\) Assume \(a \mid b\text{.}\) This means \(b=ak\) for some \(k\in\mathbb{Z}\text{.}\) Then \(bc=(ak)c=a(kc)\text{,}\) where \(kc \in \mathbb{Z}\text{.}\) Thus, \(a \mid bc\text{.}\)

🔗

Activity 3.4.2. If the Square is Even.

Consider the statement: for all integers \(n\text{,}\) if \(n^2\) is even then \(n\) is even.

🔗

(a)

Write the contrapositive of the statement.

🔗

(b)

To prove the statement by contrapositive, what should you assume?

🔗

(c)

To prove the statement by contrapositive, what should you show?

🔗

(d)

Give a direct proof of the contrapositive. You have now proven the original statement by contrapositive.

🔗

Since we can use either contradiction or contrapositive on statements of the form \(p\rightarrow q\text{,}\) the following comparison may be helpful.

🔗

Comparison of the Techniques of Contradiction and Contrapositive.

Contradiction with \(p\rightarrow q\text{:}\)

Assume \(p\ \wedge \neg q\text{.}\)

🔗
Show any contradiction. The contradiction may be \(\neg p\) or it may be \(q\text{,}\) or some other logical contradiction.

🔗
Since you can reach any contradiction at all, it may be difficult to know what you are looking for. It also may be difficult to know if you’ve made an error.

🔗
With contradiction you get to assume more, but it is less clear what you want to show.

🔗

🔗

Contrapositive with \(p\rightarrow q\text{:}\)

Assume \(\neg q\text{.}\)

🔗
Show \(\neg p\text{.}\)

🔗
With contrapositive you assume less than contradiction, but you know exactly what you are trying to show.

🔗

🔗

Subsection 3.4.3 Two Classical Proofs

We are now able to use contradiction and contrapositive to prove two classical theorems in mathematics.

🔗

In Activity 3.4.2 you used contrapositive to prove if \(n^2\) is even, then \(n\) is even. This statement is an important step in our first big theorem. We state it here formally as a lemma.

🔗

Lemma 3.4.4.

Let \(n\in \mathbb{Z}\text{.}\) If \(n^2\) is even, then \(n\) is even.

🔗

Proof.

We will prove this by contrapositive. Assume \(n\) is odd. Show \(n^2\) is odd. Since \(n\) is odd, \(n=2k+1\) for some \(k\in \mathbb{Z}\text{.}\) Then

\begin{equation*} n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1. \end{equation*}

Since \(2k^2+2k\in \mathbb{Z}\text{,}\) \(n^2\) is odd.

🔗

Theorem 3.4.5.

\(\sqrt{2}\) is irrational.

🔗

Proof.

We will prove this by contradiction. Assume \(\sqrt{2}\) is rational. Then \(\sqrt{2}=\frac{p}{q}\) with \(p, q\in\mathbb{Z}, q\neq 0\text{.}\) We will additionally assume \(p\) and \(q\) have no common factors. [Note, this additional assumption just makes the proof simpler. You should convince yourself that it is reasonable to add this assumption--that given any fraction, we can always reduce so \(p\) and \(q\) have no common factors.]

🔗

Now, using algebra on the equation,

\begin{align*} \sqrt{2}&=\frac{p}{q}\\ 2&=\frac{p^2}{q^2}\\ 2q^2&=p^2. \end{align*}

Since \(q^2\in\mathbb{Z}\text{,}\) \(p^2\) must be even. Then by Lemma 3.4.4, \(p\) must be even.

🔗

Since \(p\) is even, \(p=2k\) for some \(k\in \mathbb{Z}\text{.}\) Thus, we can substitute into the above equation.

\begin{align*} 2q^2&=(2k)^2\\ 2q^2&=4k^2\\ q^2&=2k^2. \end{align*}

Since \(k^2\in\mathbb{Z}\text{,}\) \(q^2\) must be even. Then by Lemma 3.4.4, \(q\) must be even.

🔗

But now we have \(p\) and \(q\) both even, which means they both have a common factor of 2. This contradicts our assumption that \(p\) and \(q\) have no common factors. Since we reached a contradiction, we can conclude that \(\sqrt{2}\) is irrational.

🔗

Make sure you can read through the above proof and follow from one step to the next.

🔗

Activity 3.4.3. If the Square is Divisible by 3.

In Lemma 3.4.4 and Activity 3.4.2, we proved if \(n^2\) is even then \(n\) is even. Now suppose you want to prove if \(n^2\) is divisible by 3 then \(n\) is divisible by 3.

🔗

(a)

To prove the statement by contrapositive, what should you assume?

🔗

(b)

To prove the statement by contrapositive, what should you show?

🔗

(c)

The problem with now giving a direct proof of the contrapositive is that we need to know what we mean by “\(n\) is not divisible by 3.” Recall the Division Algorithm, Theorem 3.3.3. If \(n\) is not divisible by 3, what are the possible forms for \(n\text{?}\)

🔗

Hint.

\(n=3q+r\text{.}\)

🔗

(d)

Now write a proof by cases using the cases for \(n\) from (c) to show if \(n\) is not divisible by 3, then \(n^2\) is not divisible by 3.

🔗

Our second classical theorem is to prove there are infinitely many prime numbers. In Example 3.4.2 we proved there are infinitely many integers. In that proof, if we had a biggest integer, \(N\text{,}\) we were able to construct an integer that was greater than \(N\text{,}\) namely \(N+1\text{.}\) However, primes are not that nice. If you were to list out several prime numbers, it would be impossible to find a pattern for the next prime. Sometimes primes are close together, like 17 and 19, and sometimes they are far apart. In fact, it is possible to prove that we can find a list of \(n\) consecutive integers where none of the consecutive integers are prime for any positive integer \(n\text{.}\) This means there are arbitrarily long sequences of consecutive integers with no primes, or there are primes that are arbitrarily far apart.

🔗

First we need to understand a bit more about divisibilty with primes.

🔗

Activity 3.4.4. Prime Divisor of \(a+1\).

Consider the statement: for all \(a\in \mathbb{Z}\) and primes \(p\text{,}\) if \(p\mid a\) then \(p \nmid (a+1)\text{.}\)

🔗

(a)

Write the contrapositive of the statement.

🔗

(b)

Write the negation of the statement.

🔗

(c)

Based on the contrapositive and the negation, which seem easier to use in a proof?

🔗

(d)

Assume \(p\mid a\) and \(p \mid (a+1)\text{.}\) Can you find a contradiction?

🔗

(e)

If you were able to find a contradiction, try to write a careful proof by contradiction for the statement.

🔗

The statement in Activity 3.4.4 is an important lemma for proving there are infinitely many primes.

🔗

Lemma 3.4.6.

For all \(n\in\mathbb{Z}\) and all primes \(p\text{,}\) if \(p\mid n\) then \(p\nmid n+1\text{.}\)

🔗

Proof.

We will prove this by contradiction. Let \(n\in\mathbb{Z}\text{,}\) \(p\) prime. Assume \(p\mid n\) and \(p\mid n+1\text{.}\) Since \(p\mid n\text{,}\) \(n=pk\) for some \(k\in \mathbb{Z}\text{.}\) Since \(p\mid n+1\text{,}\) \(n+1=pj\) for some \(j\in \mathbb{Z}\text{.}\) Thus,

\begin{align*} n+1&=pj\\ pk+1&=pj\\ 1&=pj-pk=p(k-j). \end{align*}

Since \(k-j\in\mathbb{Z}, p\mid 1\text{,}\) and \(p\) is a factor of 1. However, the only factors of 1 are 1 and -1, which are not prime. Thus, we have a contradiction.

🔗

Theorem 3.4.7.

There are infinitely many primes.

🔗

Proof.

Assume there are finitely many primes. Since there are finitely many, we can list them all, say, \(p_1, p_2, \ldots, p_n\text{.}\) Now let \(N=p_1\cdot p_2\cdot p_3\cdots p_n\text{,}\) the product of all the primes. Consider \(N+1\text{.}\) We know \(p_i\mid N\) for each prime \(p_i\text{.}\) By Lemma 3.4.6, \(p_i\nmid N+1\text{.}\) This means \(N+1\) is an integer greater than 1 with no prime divisor, which contradicts Theorem 3.3.2.

🔗

Exercises Exercises

1.

Consider the statement: for all integers \(n\text{,}\) if \(n^2\) is odd then \(n\) is odd.

🔗

Write what you would assume and what you would need to show to prove this statement by contradiction.
🔗

🔗
Write what you would assume and what you would need to show to prove this statement by contrapositive.
🔗

🔗

🔗

2.

Carefully write the negation of each statement then prove the statement by contradiction.

🔗

There is no greatest even integer.
🔗

🔗
There is no least positive rational number.
🔗

🔗

🔗

3.

Prove the following by contrapositive. Make sure you carefully write what you are assuming and what you need to show.

🔗

If the product of two positive real numbers is greater than 100, then at least one of the numbers is greater than 10.
🔗

🔗
If the sum of two real numbers is less than 50 then at least one of the numbers is less than 25.
🔗

🔗

🔗

4.

Prove the following statements by either contradiction or contrapositive (be sure to note which method you used).

🔗

For all integers \(n\text{,}\) if \(n^2\) is odd then \(n\) is odd.
🔗

🔗
For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\) does not divide \((bc)\text{,}\) then \(a\) does not divide \(b\text{.}\)
🔗

🔗
For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\) divides \(b\) and \(a\) does not divide \(c\text{,}\) then \(a\) does not divide \((b+c)\text{.}\)
🔗

🔗

🔗

5.

Determine whether the following statements are true or false. Prove the true statements by contradiction and provide counterexamples for the false ones.

🔗

The sum of any two irrational numbers is irrational.
🔗

🔗
If \(a\) and \(b\) are rational numbers, \(b\neq 0\text{,}\) and \(r\) is an irrational number, then \(a+br\) is irrational.
🔗

🔗
If \(r\) is any rational number, and \(s\) is any irrational number, then \({r\over s}\) is irrational.
🔗

🔗

🔗

6.

From Exercise 1.3.4 we know that, given any statement of truth-functional logic, we can always find a logically equivalent statement that uses only the connectives \(\neg\) and \(\wedge\text{.}\) For example, \([(p\leftrightarrow q) \vee r]\) is logically equivalent to \(\neg\{\neg r\ \wedge\ [\neg (\neg p\ \wedge\ \neg q)\ \wedge\ \neg (p\ \wedge\ q)]\}\text{.}\) So we could, if we wanted to, do without the connectives \(\vee\text{,}\) \(\veebar\text{,}\) \(\rightarrow\text{,}\) and \(\leftrightarrow\text{.}\) Suppose that, instead, we chose to use only the connectives \(\wedge\text{,}\) \(\vee\text{,}\) \(\rightarrow\text{,}\) and \(\leftrightarrow\text{.}\) Would these connective suffice? Why or why not? Remember that whatever your response, you should be able to offer a proof of it!

🔗

7.

Consider the following statement and “proof.” Is the proof correct? If so, what proof strategies does it use? If not, can it be fixed? Is the theorem correct?

🔗

Theorem 3.4.8.

There are irrational numbers \(a\) and \(b\) such that \(a^b\) is rational.

🔗

“Proof:” Either \(\sqrt{2}^{\sqrt{2}}\) is rational or it is irrational.

🔗

Case 1: \(\sqrt{2}^{\sqrt{2}}\) is rational. Let \(a=b=\sqrt{2}\text{.}\) Then \(a\) and \(b\) are irrational, and \(a^b=\sqrt{2}^{\sqrt{2}}\text{,}\) which we assumed was rational.

🔗

Case 2: \(\sqrt{2}^{\sqrt{2}}\) is irrational. Let \(a=\sqrt{2}^{\sqrt{2}}\) and \(b=\sqrt{2}\text{.}\) Then \(a\) is irrational by assumption, and we know that \(b\) is also irrational. Furthermore, \(a^b=\bigl(\sqrt{2}^{\sqrt{2}}\bigr)^{\sqrt{2}}=\sqrt{2}^{(\sqrt{2}\sqrt{2})}=2\text{.}\) Which is rational.

🔗

Prev Top Next