Week #5
#13
e.g. Prove that for every pair of non-negative real numbers (x,y), if x is greater than y, then the geometric mean sqrt(xy) is less than the arithmetic mean, (x+y)/2
P: x>y>=0, x-y>0, (x-y)2>0
Q: sqrt(xy) < (x+y)/2
scratch work:
sqrt(xy) < (x+y)/2
xy < (x2 + y2 + 2xy)/4
4xy < x2 + y2 + 2xy
0 < x2 + y2 + 2xy
Proof:
Assume x,y are typical non-negative real numbers.
Assume x>y # antecedent
Then x-y>0 # subtracting y from both sides
Then (x-y)2>0 # square positive number -> positive number
Then x2+y2-2xy>0 # algebra
Then x2+y2+2xy>4xy # adding 4xy on both sides
Then (x+y)2>4xy # factor
Then (x+y)2/4>xy # divide both sides by 4
Then x>y => (x+y)/2 > sqrt(xy) # assume the antecedent
# got consequent
Conclude ∀x,y∈R, x>y>=0 => (x+y)/2 > sqrt(xy) # assumed x,y are generic real number
Chain with (P=>Q)and(P=>R) <=> P=>(Q and R)
e.g Prove the square of an odd number is odd.
forall n in N, n odd => n2 odd.
scratch:
n = 2k + 1
n2 = 4k2 + 4k + 1
= 2(2k2+2k) +1
Proof:
Assume n is some typical natural number
Assume n is odd
Then exists k in N, n = 2k + 1 # definition of odd
Then n2 = 4k2 + 4k + 1
= 2(2k2+2k) +1 # algebra
Then exists j in N, n2 = 2j + 1 # j = 2k2 + 2k in N
# since k,2 in N, N closed under +,*
Then n2 is odd # definition of odd
Conclude forall n in N, n odd => n2 odd
Term-test #1
I got a full mark on this test. Since I was not doing so well on my assignment, I worked hard on this test. I did all the past papers that I can find and reviewed all the lecture notes. And I put everything of the sample test down on my cheat-sheet, which is very helpful because the test is very similar to the sample test.
#14
Proving Existence
To prove that a set is non-empty, it's enough to exhibit one element.
e.g. Exists x in R, x3 + 3x2 - 4x = 12
Proof:
Pick x = 2, Then x in R
Then x3 + 3x2 - 4x = 8 + 12 - 8 = 12
Conclude exists x in R, x3 + 3x2 - 4x = 12
Prove a claim about a sequence
e.g. Define a sequence a_n by: forall n in N, a_n = n2.
Now prove: exists i in N, forall j in N, a<=i => j<i
Proof:
Pick i = 2 Then i in N # 2 in N
Assume j is a representative of N
Assume a_j <= i
Then j2 <= 2
Then j < sqrt(2)
so j <= sqrt(2) < 2
Conclude ...
Contradiction
A special case of contrapositive
e.g. Define the prime natural numbers by:
P = {p in N | p has exactly two distinct divisors in N}
How do you prove S: forall n in N, |p| > n # There are infinite prime numbers.
# F1 and F2 and F3 and ... and Fn => S
# neg S => neg F1 or neg F2 or ... or neg Fn
# Suppose the conclusion is False, find a fact that is false.
# neg S: exists n in N, |p| <= n
Proof(by contradiction):
Assume exists n in N, |p| <= n
Then exists k in {0,1,...,n}, |p| = k
Then {p1, p2, p3, ... pk} = P # just list the primes
Then m = p1 * p2 * ... * pk in N # N closed under *
Then m+1 in N # N closed under *
Then m+1 > 1 # m >= 2 * 3 * 5 ...
Then exists p in P, p|(m+1) # every in N > 1 has prime factor
also p|m # since m = p1 * p2 * ... pk
Then p|(m + 1 - m) = 1 # factor divides difference
Then p|1 # contradiction!!
So, our assumption that exists n in N, |p| <= n is false, since it leads to a contradiction.
Thoughts
Basicly this week we talked about structures of proof and some examples of some simple proofs. And here is something I summerized.
1. Proving Universal (e.g. forall x,y... P => Q)
Assume x,y... # introduce forall
Assume P # assume antecedent
Then ... # something reduced from P
... # more steps
Then Q # get Q
Conclude P => Q # get conclusion
Conclude forall x,y... # get conclusion with quantifiers
2. Proving Existence (e.g. exists x,y... P=>Q)
Pick x=..., y=..., ... # introduce exists
Assume P # assume antecedent
Then ... # something reduced from P
... # more steps
Then Q # get Q
Conclude P => Q # get conclusion
Conclude forall x,y... # get conclusion with quantifiers
3. Prove by contradiction (e.g. P)
Assume P # assume the claim is true
Then ... # something reduced form P
... # more steps
Then (some contradiction) # get contradiction
Conclude neg P # get conclusion
