Indirect Argument: Contradiction and Contraposition
Download
Report
Transcript Indirect Argument: Contradiction and Contraposition
Indirect Argument:
Contradiction and Contraposition
1
Method of Proof by Contradiction
1. Suppose the statement to be proved is
false.
2. Show that this supposition logically leads
to a contradiction.
3. Conclude that the statement to be
proved is true.
2
Method of Proof by Contradiction (Ex.)
Theorem: There is no least positive rational number.
Proof:
Suppose the opposite:
least positive rational number x.
That is, xQ+ s.t. for yQ+, y≥x.
(1)
Consider the number y*=x/2.
x>0 implies that y*=x/2>0.
(2)
xQ implies that y*=x/2Q.
(3)
x>0 implies that y*=x/2<x.
(4)
Based on (2),(3),(4), y*Q+ and y<x.
This contradicts (1).
Thus, the supposition is false and
there is no least positive rational number.
■
Method of Proof by
Contraposition
1. Express the statement to be proved in the
form:
xD, if P(x) then Q(x) .
2. Rewrite in the contrapositive form:
xD, if Q(x) is false then P(x) is false.
3. Prove the contrapositive by a direct proof:
(a) Suppose x is an element of D
such that Q(x) is false.
(b) Show that P(x) is false.
4
Method of Proof by
Contraposition (Example)
Proposition 1: For any integer n,
if n2 is even then n is also even.
Proof: The contrapositive is:
For any integer n,
if n is not even then n2 is not even.
Let’s show (1) by direct proof.
Suppose n is not even.
Then n is odd. So n=2k+1 for some kZ.
Hence n2 =(2k+1)2=4k2+4k+1
Thus, n2 is not even.
(1)
■
5
Comparison of Contradiction and
Contrapositive methods
• Advantage of contradiction method:
– Contrapositive method only for universal
conditional statements.
– Contradiction method is more general.
• Advantage of contrapositive method:
– Easier structure: after the first step,
Contrapositive method requires a direct proof.
– Contradiction method normally has more
complicated structure.
6
When to use indirect proof
Statements starting with “There is no”.
(E.g., “There is no greatest integer” ).
If the negation of the statement deals with
sets which are easier to handle with.
(E.g., “ 2 is irrational”; rational numbers
are more structured and easier to handle
with than irrational numbers).
If the infinity of some set to be shown.
(E.g., “The set of prime numbers is infinite” ).
Method of Proof by Contradiction
(Ex.)
Theorem:
2 is irrational.
Proof: Assume the opposite:
2 is rational.
m
Then by definition of rational numbers,
2
n (1)
where m and n are integers with no common factors.
( by dividing m and n by any common factors if necessary)
Squaring both sides of (1),
Then
m2=2n2
2
m
2 2
n
(by basic algebra)
(2)
8
Method of Proof by Contradiction (Ex.)
Proof (cont.):
(2) implies that m2 is even.
(by definition)
Then m is even.
(by Proposition 1)
(3)
So m=2k for some integer k. (by definition)
(4)
By substituting (4) into (2):
2n2 = m2 =(2k)2 = 4k2 .
By dividing both sides by 2,
n2 = 2k2 .
Thus, n2 is even (by definition) and n is even (by Prop. 1). (5)
Based on (3) and (5),
m and n have a common factor of 2.
This contradicts (1).
■
Infinity of Prime Numbers
Lemma 1: For any integer a and
any prime number p,
if p|a then p doesn’t divide a+1.
Proof (by contradiction):
Assume the opposite: p|a and p|(a+1).
Then a=p·n and a+1=p·m for some n,m Z.
So 1=(a+1)-a=p·(m-n) which implies that p|1.
But the only integer divisors of 1 are 1 and -1.
Contradiction.
■
10
Infinity of Prime Numbers
• Theorem: The set of prime numbers is infinite.
• Proof (by contradiction): Assume the opposite:
The set of prime numbers is finite.
Then they can be listed as
p1=2, p2=3, …, pn in ascending order.
Consider M = p1· p2·…·pn+1.
p|M for some prime number p
(1)
(based on the th-m from handout 9/23).
p is one of p1, p2, …, pn..
Thus, p | p1· p2·…·pn..
(2)
By (2) and Lemma 1,
p is not a divisor of M.
(3)
(3) contradicts (1).
■
11