Transcript Ch1.4 - Colorado Mesa University

Ch 1.4: Basic Proof Methods I
A theorem is a proposition, often of special interest.
A proof is a logically valid deduction of a theorem, using
axioms, premises stated in the theorem, or previously
established results.
Axioms (or postulates) are initial statements assumed to be
true, from which new concepts can be deduced.
Proofs & Tautologies
In writing proofs, a working knowledge of tautologies is
helpful. For example, De Morgan’s laws, contrapositive,
transitivity, modus ponens, etc. See pages 13, 27.
These tautologies may be used as justification for proof
techniques, or as a replacement.
Justification: “Either x < 0 or x => 0” (P \/ ~P).
Replacement: “f differentiable => f continuous”  “f
discontinuous => f not differentiable.”
Modus Ponens
Suppose we know that the following are true:
P
P => Q
Then Q is true.
Example Calculus result: f differentiable => f continuous.
(1) Given: g is differentiable
Therefore g is continuous, by modus ponens.
(2) Given: g is continouous
Cannot conclude g is differentiable by modus ponens.
Direct Proof of P => Q
Assume P.
…proof details here…
Therefore, Q.
Thus P => Q.
Number Theory Basics
Let a, b be natural numbers. Then a divides b if there
exists a natural number k such that b = ka.
A prime number is a natural number greater than one that
is only divisible by 1 and itself.
An integer x is even if there is an integer k such that
x = 2k.
An integer x is odd if there is an integer j such that
x = 2j+1.
Example: Direct proof of P => Q
Suppose that a and b are integers. Prove that if a is even
and b is odd, then a + b is odd.
Proof. Assume that a is an even integer and that b is an
odd integer. Then
There exists integers k, j such that a = 2k and b = 2j+1.
Then a + b = 2k + 2j+1
= 2(k+j) + 1
= 2m + 1, where m=k+j is an integer.
Therefore a + b is odd.•
Example: Direct proof of P => Q
Suppose that a, b and c are natural numbers. Prove that if
c divides a and c divides b, then c divides a + b.
Proof. Assume that a, b, c are natural numbers, and that c
divides a and c divides b. Then
There exist natural numbers m, n st mc = a and nc = b.
Then a + b = mc + nc
= (m+n)c
= kc, where k=m+n is a natural number.
Therefore c divides a + b. •
Strategies for Direct Proof of P => Q
Determine precisely the antecedent and the consequent (P and Q).
Replace, if necessary, the antecedent with a more usable equivalent.
Replace, if necessary, the consequent with something equivalent and
more readily shown.
Develop a chain of statements, each deducible from its predecessors or
other known results, that leads from antecedent to consequent.
Every step of proof should express a complete sentence, using
important connective words to complete meaning of symbols used.
Sometimes it is helpful to work backward to discover a proof, by first
determining the end result that needs to be shown, and then seeing
what steps are needed to get there.
Example: Direct proof of P => Q
Prove that if x 2  1, then x 2  7 x  10.
Proof : Assume x 2  1, and consider x 2  7 x  10.
x 2  7 x  10  x 2  7 x  10  0
 ( x  5)( x  2)  0
Now x 2  1   1  x  1, and
1  x  1  x  5  0 and x  2  0
 x  5x  2  0
Therefore x 2  7 x  10.
•
Strategies for Direct Proof of P => Q
For P => (Q \/ R), one might prove the equivalent
(P /\ ~Q) => R
(P /\ ~R) => Q
(All three are equivalent to ~P \/ Q \/ R)
For (P \/ Q) => R, one might first prove the cases
P => R
Q => R
Example: Direct proof of P => (Q \/ R)
Prove that if n is an odd integer, then n = 4j+1 for some integer j or n =
4i –1 for some integer i.
Proof. Assume n is an odd integer. Then n= 2m+1 for some integer m.
Case 1: m even => m = 2j for some integer j
=> n = 2m+1 = 4j+1
Case 1: m odd => m = 2k + 1 for some integer k
=> n = 2m+1 = 2(2k + 1) + 1
=> n = 4k+3 = 4(k+1) – 1 = 4i-1,
where i=k+1 is an integer.
Thus if n is an odd integer, then n = 4j+1 for some integer j or n= 4i –1
for some integer i.•
Example: Proof by cases (exhaustion)
Let x be a real number. Prove that  x  x  x
Proof :
Case 1 : Suppose x  0. Then x  x, and since x  0,
 x  x  x   x  x  x in this case.
Case 2 : Suppose x  0. Then x   x, and since x  0,
x  x   x   x  x  x in this case.
Thus, in all cases,  x  x  x
•
Homework
Read Ch 1.4
Do 35(4a-c,5a,b,6a-d,10)