Method of Proof by Contradiction.
- Assume the statement to be proved is false. Or, assume the negation is true.
- Show you reach some logical contradiction.
- Conclude the original statement is true.
Section 4.5 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.
Example 4.5.1. 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.
Since contradiction relies on negating statements, recall the following negations:
- \(p\rightarrow q\) has negation \(p\ \wedge \sim q\)
- \(p\ \wedge q\) has negation \(\sim p\ \vee \sim q\)
- \(p\ \vee q\) has negation \(\sim p\ \wedge \sim q\)
Activity 4.5.1.
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.
Recall from Section 2.2 that a conditional, \(p\rightarrow q\text{,}\) and its contrapositive, \(\sim q\rightarrow \sim p\text{,}\) are logically equivalent. This means we can prove the contrapositive rather than the original 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 \(\sim Q(x)\) then \(\sim P(x)\text{.}\)
- Prove the contrapositive directly: assume \(\sim Q(x)\text{,}\) show \(\sim P(x)\text{.}\)
Example 4.5.2. 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 4.5.2.
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.
Comparing Contradiction and Contrapositive.
Contradiction with \(p\rightarrow q\text{:}\)
- Assume \(p\ \wedge \sim q\text{.}\)
- Show any contradiction. The contradiction may be \(\sim 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 \(\sim q\text{.}\)
- Show \(\sim p\text{.}\)
- With contrapositive you assume less than contradiction, but you know exactly what you are trying to show.
Reading Questions Check Your Understanding
1.
Give the negation for the statement: There does not exist a greatest odd integer.
2.
Give the negation for the statement: For all real numbers \(r\text{,}\) if \(r\) is not rational then \(3r\) is not rational.
3.
Suppose you want to prove the following statement by contradiction: For all real numbers \(r\text{,}\) if \(r\) is not rational then \(3r\) is not rational. What should you assume? What should you show?
4.
Give the contrapositive for the statement: For all real numbers \(r\text{,}\) if \(r\) is not rational then \(3r\) is not rational.
5.
Suppose you want to prove the following statement by contrapositive: For all real numbers \(r\text{,}\) if \(r\) is not rational then \(3r\) is not rational. What should you assume? What should you show?
6.
Give the negation for the statement: For all integers \(n\) and primes \(p\text{,}\) if \(p\mid n^2\) then \(p \mid n\text{.}\)
7.
Suppose you want to prove the following statement by contradiction: For all integers \(n\) and primes \(p\text{,}\) if \(p\mid n^2\) then \(p \mid n\text{.}\) What should you assume? What should you show?
8.
Give the contrapositive for the statement: For all integers \(n\) and primes \(p\text{,}\) if \(p\mid n^2\) then \(p \mid n\text{.}\)
9.
Suppose you want to prove the following statement by contrapositive: For all integers \(n\) and primes \(p\text{,}\) if \(p\mid n^2\) then \(p \mid n\text{.}\) What should you assume? What should you show?
Exercises Exercises
1.
Is \(\frac{1}{0}\) an irrational number? Explain.
2.
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.
3.
A Test to Determine if a Number is Prime: Given any integer \(n>1\text{,}\) to test whether \(n\) is prime check to see if it is divisible by a prime number less than or equal to \(\sqrt{n}\text{.}\) If it is not divisible by any prime less than or equal to \(\sqrt{n}\text{,}\) then \(n\) is prime.
Use this test to determine if the following numbers are prime or not.
- 527
- 613
4.
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.
5.
Prove by contradiction: If \(a\) and \(b\) are rational numbers, \(b\neq 0\text{,}\) and \(r\) is an irrational number, then \(a+br\) is irrational.
6.
Prove the following statement in two ways: (a) by contrapositive and (b) by contradiction.
For all integers \(n\text{,}\) if \(n^2\) is odd then \(n\) is odd.
You have attempted of activities on this page.
