|
ARITHMETIC RULES m, n, k, q, x, y are integers |
|---|
|
#1. Direct Proof (follow the implication)
Given p -> q, assume p and show q.
Example 1:
"Show that n is an even integer whenever n^2 is an even integer."
Since an even n^2 is sufficient to know that n is even, we can restate
the original claim as an implication:
"If n^2 is even then n is even."
In a direct proof we assume the antecedent (n^2 is even) is true. Then by
definition we know n^2 = 2k for some integer k. Solving for n:
n^2 = 2k
n = (2k)/n
n = 2(k/n).
By definition, since n has a factor of 2 we know n is even. qed.
#2. Proof by Contrapositive (contraposition)
If p->q then ~q -> ~p. Given ~q -> ~p, assume ~q and show ~p.
For certain problems it is easier to show ~q -> ~p than it is to show p->q.
E.g., in the proof below, math is simpler with an even integer than it is
with an odd integer.
Ex. "Show that n is an odd integer whenever n^2 is an odd integer."
First re-write the statement as an implication. We now have:
"If n^2 is odd then n is odd."
p -> q
For n to be not odd means n is even we can state ~q -> ~p like this:
"If n is even then n^2 is even."
Assuming n is even, we know n=2k. Replacing n with 2k we have:
n^2 = (2k)^2.
= (2k)(2k)
= 2(2k^2).
By definition, since n^2 has a factor of 2, we know n^2 is even. qed.
#3. Proof by Contradiction
In this method you show p->q is always true by showing that p->q can never
be false; i.e., show ~(p -> q) is a contradiction.
~(p -> q) == ~(~p v q) == p ^ ~q.
Since ~(p->q) is equivalent to p^~q, ~(p->q) -> p^~q. (p->p is a tautology)
Once you show that p^~q is a contradiction (never true) it follows that
~(p -> q) is never true and thus p->q must be true.
Essentially, try to show that the implication is false. When you hit
a contradiction you know the implication must be true.
EXAMPLE.
Show that the product of two integers m and n, where m is odd and n is even,
is even.
The implication is this:
"If m is odd and n is even then mn is even."
---------------------- -----------
p q
Try to show p and ~q. If p then m = 2k+1 and n = 2j. Then
mn = (2k+1)(2j)
= (4kj+2j)
= 2(2kj+j)
But mn has a factor of 2, thus cannot be even and odd at the same time.
The original proposition must be true.
EXAMPLE.
Show that in a room of 8 students, at least 2 must be born on the same day
of the week.
Try to show that 2 are not born on the same day of the week. In the best
case let 7 students be born on different days of the week. But the 8th
student must be born on the same day as another student. This contradicts
what we are trying to show thus the original claim must be true.
EXAMPLE.
Show that out of 3 arbitrary students in a group of 30 students, 2 of
those students must be male or female.
Rephrase as an implication:
"If you pick 3 students then 2 must be male or female."
p -> q
Try to show p and ^q.
"You pick 3 students and 2 are NOT male or female."
p ^ ~q
You have 3 students. Assign one student male and one student female. Any
other assignment is false. But the third student must be male or female.
You have a contradiction. Since p ^ ~q is never true, p -> q must be true.
EXAMPLE.
Show sqrt(2) is an irrational number. Rephrased as an implication:
"If n = sqrt(2), then n is not rational (irrational)."
p: n = sqrt(2)
q: n is irrational
Our goal is to show that p ^ ~q is a contradiction.
Definition of a rational number.
If n is a rational number, then n = x/y, where x and y are integers with
no common factor, and y != 0. Informally, n is rational if n can be
expressed as a simple fraction, otherwise n is irrational.
Let n = sqrt(2). Assume n is rational. By definition, if n is rational then
sqrt(2) = x/y, where x and y are integers with no common factors and y != 0.
Replacing n with x/y we have:
x/y = sqrt(2).
Rearrange and solve for 2:
sqrt(2) = x/y
(sqrt(2))^2 = (x/y)^2
2 = (x^2)/(y^2)
2(y^2) = x^2 (Equation 1)
For Equation 1 to be true, x^2 must be even. For (x)(x) to be even, x must
have a factor of 2 and thus x must be even. By definition x = 2k, for some k.
Replacing x with 2k in Equation 1, we have:
2(y^2) = (2k)^2
2(y^2) = 4(k^2)
y^2 = 2(k^2) (Equation 2)
For Equation 2 to be true, y^2 must be even. For (y)(y) to be even, y must
have a factor of 2 and thus y must be even. By definition y = 2j, for some j.
But if x=2k and y=2j, x and y share a common factor. By the definition of
a rational number, sqrt(2) cannot be rational since x and y share a common
factor. We have a contradiction. Thus, since sqrt(2) cannot be rational, it
must be irrational.
#4. Proof by Cases (split up the domain of the problem)
Ex. Prove that if x and y are integers, x != y, max(x,y) + min(x,y) = x+y.
Case 1. x >= y
If x >= y then max(x,y) = x and min(x,y) = y. Thus x + y = x + y. True.
Case 2. x < y
If x < y then max(x,y) = y and min(x,y) = x. Thus x + y = y + x. True.
#5. Proof by Equivalence
This method works for problems that can be stated as a biconditional.
Show that the biconditional to be a tautology (logically equivalent):
p <-> q == (p -> q) ^ (q -> p)
Ex. "Show n is congruent to 0 mod 2 if and only if n is even."
Step 1. Show p -> q: "If n is congruent to 0 mod 2 then n is even."
Assume n is congruent to n mod 2: n mod 2 = 0. Show n = 2k.
By definition if n mod 2 = 0, n has a factor of 2. Thus n is even and
can be expressed as 2k. check.
Step 2. Show q -> p: "If n is even then n is congruent to 0 mod 2."
Assume n is even. Then n = 2k. Replace n with 2k. Show 2k is congruent
to 0 mod 2. 2k mod 2 = 0. check.
#6. Existence Proof (two forms)
Constructive existence proof: find a concrete value to show true
Ex.
"Show there is a positive integer n < 2000 that can be written as a sum
of cubes x^3 + y^3, in 2 ways, where n,x,y are positive integers."
Unfortunately, problems like this generally require brute force. But
follow a pattern so you know you are covering all possible solutions in
an orderly fashion. Also look for little tricks that will make your life
easier. How do you do this? Look for patterns!
Fix y=1 and work through x starting at 1 and factor each result. What are
we looking for? We are looking for a way to partition the result into
two chunks, each of which is a perfect triplet.
x=1 y=1 1 + 1 = 2. nothing possible here.
x=2 y=1 2^3 + 1 = 9. again, no help.
x=3 y=1 3^3 + 1 = 28. hmmm....not sure
By now you should see that since we are looking for is an integer that
can be divided into two perfect triplets it will be useful to write out
the triplets:
1^3 2^3 3^3 4^3 5^3 6^3 7^3 8^3 9^3 10^3 11^3 12^3
1 8 9 64 125 216 343 512 729 1000 1331 1728
Now, with that list handly, start your brute force search again.
x=4 y=1 4^3 + 1 = 65. nope.
x=5 y=1 5^3 + 1 = 126. nope.
x=6 y=1 6^3 + 1 = 217. nope.
x=7 y=1 7^3 + 1 = 344. no.
x=8 y=1 8^3 + 1 = 513. no.
x=9 y=1 9^3 + 1 = 730. no.
x=10 y=1 10^3 + 1 = 1001. no.
x=11 y=1 11^3 + 1 = 1332. no.
x=12 y=1 12^3 + 1 = 1729. YES!
x=9 y=10 9^3+10^3=1729. 1728+1. BINGO.
Solution:
1729 = 10^3 + 9^3 = 12^3 + 1^3
EX. "Show that there is number that is twice the sum of its digits."
Proof: 18 = 2(9)
Nonconstructive: reason about the existence of a value
Ex.
Show that there exists two irrational numbers x,y such that x^y is
rational (x != y or x = y)
We know that sqrt(2) is irrational (shown above). Consider sqrt(2)^(sqrt(2).
If rational then QED. If irrational, then let x = sqrt(2)^sqrt(2) and
y = sqrt(2). Thus
x^y = [sqrt(2)^sqrt(2)]^sqrt(2)
= sqrt(2)^(sqrt(2)*sqrt(2))
= sqrt(2)^sqrt(4)
= sqrt(2)^2
= 2
We don't know if sqrt(2)^sqrt(2) is rational or irrational, but we have a
solution in either case!
#7 Uniqueness Proof (one and only one)
ex.
There is one and only one integer x, such that x + 3 = 5.
s+3=5; x=5-3=2. Suppose there is an integer r such that r+3=5 and r != 2.
Then r+3=5 and r=5-3 and r=2. But r=2 and r!=2 contradict each other. Thus,
must be unique.
#8. Proof by Counterexample
Find one false example to prove Ax P(x) is false.
Ex. "All cats have green eyes." Find one cat that disproves the predicate.
#9. Vacuous/trivial proofs. p -> q, where p is false
Show P(0) true for P(n); if n > 1, then n^2 > n.
P(0): if o > 1, then 0^2 > 0. Since 0 > 1 is false, trivially true.
===========================================================
MORE PROOF EXAMPLES
===========================================================
Example of a constructive proof:
Prove that there are 100 consecutive positive integers that are not perfect
squares.
10,001, 10,002, 10,003, ...10,100 are all consecutive positive integers that
are not perfect squares since 100^2 = 10,000 and the next closest square is
101^2, which is 10,201.
================================================================
Example of an INCORRECT proof by cases.
If x is an integer, then x^2 is a positive integer.
p1: x is positive
p2: x is negative
q: x^2 is positive
p1 -> q because if p1 is positive then x^2 must be positive
p2 -> q because if p2 is positive then x^2 must be positive
thus, q
This proof by cases is incorrect because it misses the case where x=0.
================================================================
Example of an INCORRECT direct proof.
Show that n is an even integer whenever n^2 is an even integer.
Restate as p->q:
"If n^2 is even then n is even."
Assume n^2 is even. Then n^2 = 2k for some integer k. Let n = 2m for some
integer m. This shows that n is even.
The above argument is incorrect since the conclusion (n is even) is used as
one of the premises. This is circular reasoning or "begging the question."
==========================================================================
Example of a proof using quantifiers
A student in cs295 has not read the book. Everyone in cs295 passed
the first exam. Conclusion: someone who passed the first exam has not read
the book.
Universe of discourse: all students in cs295
P(x) : x has read the book
Q(x) : x passed the exam
Argument:
Ex ~P(x))
Ax Q(x)
-----------------
Ex (Q(x) ^ ~P(x))
Proof:
1. Ex ~P(x) Premise
2. ~P(c) Existential Instantiation from (1)
3. Ax Q(x) Premise
4. Q(c) Universal instantiation from (3)
5. ~P(c) ^ Q(c) Conjunction from (2) and (4)
6. Ex(~P(x) ^ Q(x)) Existential generalization from (5)
Thus, the conclusion is establised from the premises.