2018 - Page 32 of 41 - Shawn Zhong

1.8 Proof Methods and Strategy

$Proof by Cases • To prove a conditional statement of the form: ○ \(p_1∨p_2∨…∨p_n)→q • Use the tautology ○ \(p_1∨p_2∨…∨p_n)→q ↕ ○ (p_2→q)∧(p_2→q)∧…∧(p_n→q) • Each of the implications p_i→q is a case. • Example ○ Let a@b=max{a, b}=a if a≥b, ○ otherwise a@b=max{a, b}=b. ○ Show that for all real numbers a, b, c § (a@b)@c=a@(b@c) ○ (This means the operation @ is associative.) ○ Let a, b, and c be arbitrary real numbers. ○ Then one of the following 6 cases must hold. § a≥b≥c § a≥c≥b § b≥a≥c § b≥c≥a § c≥a≥b § c≥b≥a Without Loss of Generality • Show that if x and y are integers and both x∙y and x+y are even, • then both x and y are even. • Use a proof by contraposition. • Suppose x and y are not both even. • Then, one or both are odd. • Without loss of generality, assume that x is odd. • Then x=2m+1 for some integer m. • Case 1: y is even. ○ Then y=2n for some integer n, so ○ x+y=(2m+1)+2n=2(m+n)+1 is odd. • Case 2: y is odd. ○ Then y=2n+1 for some integer n, so ○ x∙y=(2m+1)(2n+1)=2(2m∙n+m+n)+1 is odd. • We only cover the case where x is odd • because the case where y is odd is similar. • The use phrase without loss of generality (WLOG) indicates this. Existence Proofs • Proof of theorems of the for ∃x P(x). • Constructive existence proof: ○ Find an explicit value of c, for which P(c) is true. ○ Then ∃x P(x) is true by Existential Generalization (EG). • Example: ○ Show that there is a positive integer that can be written as ○ the sum of cubes of positive integers in two different ways: ○ 1729=〖10〗^3+9^3=〖12〗^3+1^3 • Nonconstructive existence proof ○ In a nonconstructive existence proof, ○ we assume no c exists which makes P(c) true ○ and derive a contradiction. • Example ○ Show that there exist irrational numbers x,y such that x^y is rational. ○ We know that √2 is irrational. ○ Consider the number 〖√2〗^√2. ○ If 〖√2〗^√2 is rational § we have two irrational numbers x and y with x^y rational § namely x=√2 and y=√2. ○ If 〖√2〗^√2 is irrational § then we can let x=〖√2〗^√2 and y=√2 so that § x^y= (〖√2〗^√2 )^√2=〖√2〗^(√2×√2)=〖√2〗^2=2. Uniqueness Proofs • Some theorems asset the existence of • a unique element with a particular property, ∃!x P(x). • The two parts of a uniqueness proof are ○ Existence § We show that an element x with the property exists. ○ Uniqueness § We show that if y≠x, then y does not have the property. • Example ○ Show that if a and b are real numbers and a≠0, then ○ there is a unique real number r such that ar+b=0. ○ Existence § The real number r =−b/a is a solution of ar+b=0 § because a(−b/a)+b=−b+b=0. ○ Uniqueness § Suppose that s is a real number such that as+b=0. § Then ar+b=as+b, where r=−b/a. § Subtracting b from both sides § and dividing by a shows that r = s. Additional Proof Methods • Later we will see many other proof methods: • Mathematical induction ○ which is a useful method for proving statements of the form ∀n P(n), ○ where the domain consists of all positive integers. • Structural induction ○ which can be used to prove such results about recursively defined sets. • Cantor diagonalization ○ used to prove results about the size of infinite sets. • Combinatorial proofs use counting arguments.$

1.7 Introduction to Proofs

1.6 Rules of Inference

1.5 Nested Quantifiers

Math 521 – 2/5

$Theorem 1.21 • Notation ○ For a positive integer n § x^n≔⏟(x⋅x⋅x⋯x)┬(n times) ○ For a negative integer n § x^n≔⏟((1/x)⋅(1/x)⋅(1/x)⋯(1/x) )┬(−n times) • Statement ○ For every real x 0, and positive integer n ○ There is one and only one positive real number y s.t. y^n=x ○ In this case, we write y=x^(1/n) • Intuition ○ Try this for n=2 and x=2, so y=√2 • Proof (Uniqueness) ○ If there were y_1 and y_2 s.t. ○ y_1^n=x,y_2^n=x, but y_1≠y_2 ○ Without loss of generality, assume y_1 y_2 ○ Then y_1^n y_2^n, so they can t both equal x ○ So, there is at most one such y • Lemma ○ If n is a positive integer, then § b^n−a^n=(b−a)(b^(n−1)+ab^(n−2)+…+a^(n−2) b+a^(n−1) ) ○ Moreover, if b a 0, then § b^n−a^n (b−a) ⏟((b^(n−1)+b^(n−1)+…+b^(n−1)+b^(n−1) ) )┬(n terms) § b^n−a^n (b−a)nb^(n−1) § Also, (b^n−a^n)/(nb^(n−1) ) b−a b • Proof (Existence) ○ Let E≔{t∈Rt 0 and t^n x} ○ E is not empty § Let t≔x/(x+1), then 0 t 1 and t x § So, 0 t^n t x § Thus, t∈E § Therefore E is not empty ○ E is bounded above § Let t∈R s.t. t 1+x § Therefore t^n t 1+x x § So t∉E and E is bounded above by 1+x § By least upper bound property, sup⁡E exists § Let y≔sup⁡E ○ We now show that y^n≮x and y^n≯x ○ Assume y^n x § Choose h∈R s.t. § 0 h 1 and h (x−y^n)/(n(y+1)^(n−1) ) § Then hn(y+1)^(n−1) y^n § Use the lemma b^n−a^n (b−a)nb^(n−1) § Set a≔y,b≔y+h § (y+h^n−y^n (y+hy)n(y+h^(n−1) § (y+h^n−y^n hn(y+1)^(n−1) § (y+h^n−y^n y^n § (y+h^n x § Since y+h h and y+h∈E § y is not an upper bound of E § This contradicts y=sup⁡E § Thus, y^n≮x ○ Assume y^n x § Let k≔(y^n−x)/(ny^(n−1) ) 0 § Use the lemma (b^n−a^n)/(nb^(n−1) ) b § Set b≔y,a^n≔a, then k=(y^n−x)/(ny^(n−1) ) y § Thus,0 k y § Let t∈R s.t. t≥y−k, then § y^n−t^n≤y^n−(y−k)^n § Use the lemma b^n−a^n (b−a)nb^(n−1) § Set a≔y,b≔y−k, then § y^n−t^n≤y^n−(y−k)^n kny^(n−1)=y^n−x § Therefore, t^n x § By definition of E={t∈Rt 0 and t^n x} § t∉E and t is greater than everything in E § Also t≥y−k, so y−k is an upper bound for E § But y−k y, which contradicts y=sup⁡E § Thus, y^n≯x ○ Therefore y^n=x • Corollary: If a,b∈R+, and n∈Z+, then a^(1/n)⋅b^(1/n)=(ab)^(1/n) ○ Let α=a^(1/n), β=b^(1/n), then ○ α^n β^n=ab ○ (αβ)^n=ab ○ So αβ=(ab)^(1/n) Complex Numbers ℂ • Definition ○ The complex numbers ℂ can be thought of ○ as numbers of the form a+bi, where a,b∈R, and i^2=−1 • Addition, multiplication, subtraction, and division ○ If a+bi, c+di∈ℂ, then ○ (a+bi)+(c+di)=(a+c)+(b+d)i ○ (a+bi)−(c+di)=(a−c)+(b−d)i ○ (a+bi)⋅(c+di)=(ac−bd)+(ad+bc)i ○ (a+bi)/(c+di)=((a+bi)/(c+di))((c−di)/(c−di))=(a+bi)(c−di)/(c^2+d^2 )$

Shawn Zhong