sets: collection of objects ex: A{6,1,2,0....} * set order does not matter * duplicates are not allowed B={2,{3,4},{}} {} empty set (known as 0 with a slash) not actually zero but is only empty union sets: AuB= {2,6,1,{},0,{3,4}} what if A had 3? 3 is not a element of AuB Intersection set: AnB={2} set minus: A-B = A but not B (A\B) Natural numbers: set of even natural numbers= {n \in N| is even(n)} notes:
. = is such that , after for all or exists
A set cannot have itself as an element.
z\in N {1,4,7} not\in N (or sub in not\in fir subet of c with underline) Z={-2,-2,0,1} Q= Rational R= Real C = complex numbers
what does it mean to prove a statement? Prove existence
Thm: exist n \in N, n >=10 and is prime(n) proof: show n=11 satisfies the condition 11>=10 ^ 11 is prime
Thm: exists x \in S. P(x) proof: choose x= ? \in S. P(x) is true because ?
Prove universality or for all cant just say x=11 but all numbers
proof by example is not the way to go for all x \in R . x^2 -6x>-10 proof: suppose x is in R (x^2-6x+9)=(x-3)^2>=0 x^2-6x=(x^2-6x+9)-9>=-9>-10
square is done with proof or QED
thm: for all x \in S. P(x) proof: suppose x is an arbitrary number of S P(x) is true because reasons.
for all or exists needs a period that means such that
proof of implication: for all n \in Z. ( n is mult. of 10)=> is even(n). proof: suppose n \in Z. assume n is mult of 10 ; WTS n is even, n=10k(k is some int) =25K=2some int
WTS - WANT TO SHOW p->q Assume p is true then Q is true EXPLAIN contrapositive: not p -> not p Assume not Q false then not P false EXPLAIN p->q = not p -> not p
proof by contrapositive: introduce variable for "for all" suppose n\in Z. assume n is odd ; WTS n*n is odd odd x odd =odd
Proof by contradiction: counter intuitive to prove P show that not P is false if its not false its true
Thm:
sqrt2 not \in Q Assume sqrt2 is \in Q sqrt2=a/b for some ints a,b ,b cannot be zero assume lowest form and a and b share no common factors (other than + or - 1 ) a^2=2b^2-> a^2 is even -> a is even a=2A for some int A 4A^2=2b^2->2A^2=b^2 b^2 is even-> b is even b=2B for some B \in Z a=2A, b=2B a/b is not reduced because there is a factor of 2 that's common and 2 is not + - 1 .. CONTRADICTION assumption sqrt2 \in Q must be false -> sqrt2 not\in Q QED.
COMMON FACTORS ARE RATIO OF INTS. --?
Review-
INDUCTION:
thm: for all n >=0 , (1+2+3+...+n)=(n(n+1))/2 [sigma k=1 to n (k)] to exlude 0
n=0 an empty sum is 0 (01)/2 <br /> n=1: 1=? (12)/2 add 1 n=2: 1+2 =? (23)/2 add 2 n=3 1+2+3=? (34)/2 add 3 n=4 1+2+3+4=? (4*5)/2 add 4
verify: 1+2+..+(n-1)=(n-1)(n)/2 add n 1+2+..+(n-1)+n=n(n+1)/2
(n^2+n)/2 - (n^2-n)/2 = 2n/2 = n
(1+2+3+...+n)=(n(n+1))/2=: P(n) [sigma k=1 to n (k)] to exlude 0 induction principle: if you prove the implications are true than the rest are true. p(0) true p(1) true p(1)->p(2) (implies) p(2) -> p(3) p(3) -> p(4) ......
Below is all true because the implications are true aswell. p(1) p(2) p(3) p(4)
principle of induction: if [p(0) and for all n >=1. p(n-1)->p(n)] then [ for all n \in N. p(n)]
outline to follow: thm: p(n) is true for all n \in N
first step: define p(n) recall: p(n) ="(1+2+3+...+n)=(n(n+1))/2" proof by induction on n. base case (p(0): is true b/c ( do some work) if [p(0) and for all n >=1. p(n-1)->p(n)] then [ for all n \in N. p(n)] inductive step: assume n is at least 1 and p(n-1) is true and WTS p(n) IS TRUE -------assume left prove right.--------
Ie. assume
1+2+..+(n-1)=(n-1)(n)/2
WTS 1+2+...(n-1)+n=n(n+1)/2
WTS (n-1)(n)/2 + n=n(n+1)/2
true by algebra by induction p(n) is true for all n>=0
16 x 16 grid want to tile w/o middle cell L-trominoes tile once but not covered twice p(n):=2^nx2^n grid w/o one middle cell can be tile w/ L trominoes
p(0), tile |x| missing middle cell QED P(1): 2X2 1 L trominoe P(2): 4X4 start in middle then outward 8x8 example: highlight middle lines x and y start center and observe 4 quads separately cant invoke p(2) twice. if induction is not working try and prove a stronger thm.<br /> remove middle cell restriction less restrictions are stronger thms.
p(2)->p(3) p(3)->p(4) strat: place one L in the middle , hitting the 3 full quadrants now use p(2) on each quad
3 quads: 2^nx2^n -1 cell missing cell in corner 4th 2^nx2^n missing cell wont be in corner
you can always tile no matter where the face is in 2x2 induction
each p(n) is a algorithm not a thm