Notes Archives - Page 33 of 84 - Shawn Zhong

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 )$

Math 521 – 2/2

$Proposition 1.18 • Let F be an ordered filed, for x,y,z∈F (1) If x 0 then −x0, and vice versa § x 0 § x+(−x) 0+(−x) § 0 −x∎ (2) If x 0 and yz then xyxz § x 0, z−y 0 § x(z−y) 0 § xz−xy 0 § xyxz∎ (3) If x0 and yz then xy xz § x0 § By (1), −x 0 § By (2), (−x)y(−x)z § 0(−x)(z−y) § By (1), x(z−y)0 § xzxy∎ (4) If x≠0 then x^2 0. In particular 1 0 § If x 0, by (2), x^2 0⋅x=0 § If x0, by (3), x^2 0⋅x=0 § 1=1^2=1×1 0 § So 1 0∎ (5) If 0xy, then 01/y1/x § If y 0, then 1/y⋅y=1 0=0⋅1/y by (4) § So, 1/y must have been positive by (2) § Similarly, 1/x 0 § Therefore (1/x)(1/y) 0 § Multiply both sides of xy by (1/x)(1/y) § We get 1/y1/x § Therefore 01/y1/x∎ Theorem 1.19 • There exists an ordered filed with the least upper bond property called R • Moreover R has Q as a subfield • Proof: See appendix Theorem 1.20 • The Archimedean property of R ○ Given x,y∈R, and x 0 ○ There is a positive integer n such that nx y • Proof: The Archimedean property of R ○ Let A={nx│n is a positive integer} ○ Assume the Archimedean property is false ○ Then A has an upper bound ○ i.e. sup⁡A exists ○ Let α=sup⁡A ○ x 0, so α−xα ○ And α−x is not an upper bound for A ○ By definition of A={nx│n is a positive integer} ○ α−xmx for some positive integer m ○ So, αmx+x=(m+1)x∈A ○ This contradicts α=sup⁡A ○ Therefore the Archimedean property is true • Corollary ○ Given x 0 ○ Let y=1, then ○ ∃n∈Z+ s.t. nx 1 ○ Therefore given x 0, ∃n∈Z+ s.t. 1/nx • Q is dense in R ○ If x,y∈R, and xy, then there exists a p∈Q s.t. xpy ○ We can always find a rational number between two real numbers • Proof: Q is dense in R ○ Let x,y∈R, and xy ○ So y−x 0 ○ By the Archimedean property of R § There exists a positive integer n s.t. § n(y−x) 1 § ⇒ny−nx 1 § ⇒ny nx+1 ○ By the Archimedean property of R again § There are positive integers m_1,m_2 s.t. § m_1 nx, m_2 −nx § i.e. −m_2nxm_1 § So there is an integer m s.t. § −m_2≤m≤m_1 § And more importantly, m−1≤nxm ○ Combining two parts together, we have § nxm≤1+nxny § In particular, nxmny § Since n 0, we can multiply by 1/n and get § 1/n (nx)1/n (m)1/n (ny) § Therefore xqy, where q=m/n∈Q 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_1y_2 ○ Then y_1^ny_2^n, so they can t both equal x ○ So, there is at most one such y • Proof (Existence) ○ (To be continued)$

Math 541 – 2/5

$Examples of Groups • Is Z a group under multiplication? ○ No, because there is no inverses for 2 ○ Let x∈Z∖{±1} ○ The multiplicative inverse of x (i.e. 1/x) is not an integer • What about Q,R, and ℂ? ○ No, because 0 still has no multiplicative inverse • Multiplicative group of Q,R,ℂ ○ Let Q∗=Q∖{0} and R∗, ℂ^∗ similarly ○ Then Q∗,R∗,ℂ^∗ are groups with operation given by multiplication ○ We argue this for Q∗; the same proof works for R∗ and ℂ^∗ ○ Check: multiplication is an operation on Q∗ § If a,b∈Q∗, then ab∈Q∗ ○ Associativity § This is clear ○ Identity § 1∈Q∗ ○ Inverses § If a∈Q∗, then 1/a is the inverse of a, and 1/a∈Q∗ • Is Z a group with operation given by subtration? ○ No, because subtraction is not associative ○ (1−2)−3=−4 ○ 1−(2−3)=2 • GL_n (R under matrix multiplication ○ Let n∈Z( 0) ○ GL_n (R≔{invertible n×n matrices with entries in R ○ GL_n (R is a group under matrix multiplication ○ Check: matrix multiplication is an operation on GL_n (R § If A,B∈GL_n (R § AB∈GL_n (R, since (AB)^(−1)=B^(−1) A^(−1) ○ Associativity § This is clear ○ Identity § I_n, the n×n identity matrix ○ Inverses § If A∈GL_n (R, its inverse is A^(−1) ○ Notice: When n 1, the operation in GL_n (R is not commutative Abelian Group • We say a group G is abelian, if ∀a,b∈G, a⋅b=b⋅a Proposition 9 • Statement ○ Let n∈Z( 0), and let a_1,a_2,b_1,b_2∈Z ○ If (a_1 ) ̅=(b_1 ) ̅, and (a_2 ) ̅=(b_2 ) ̅ in Z\/nZ ○ Then (a_1+a_2 ) ̅=(b_1+b_2 ) ̅, and (a_1 a_2 ) ̅=(b_1 b_2 ) ̅ • Proof: (a_1+a_2 ) ̅=(b_1+b_2 ) ̅ ○ Choose c_1,c_2∈Z s.t. c_1 n=a_1−b_1 and c_2 n=a_2−b_2 ○ (c_1+c_2 )n ○ =a_1−b_1+a_2−b_2 ○ =(a_1+a_2 )−(b_1+b_2 ) ○ Thus, ├ n┤|├ ((a_1+a_2 )−(b_1+b_2 ))┤ ○ So, (a_1+a_2 ) ̅=(b_1+b_2 ) ̅ ∎ • Proof: (a_1 a_2 ) ̅=(b_1 b_2 ) ̅ ○ Choose c_1,c_2∈Z s.t. c_1 n=a_1−b_1 and c_2 n=a_2−b_2 ○ a_1 a_2−b_1 b_2 ○ =a_1 a_2+a_1 b_2−a_1 b_2−b_1 b_2 ○ =a_1 (a_2−b_2 )+(a_1−b_1 ) b_2 ○ =a_1 c_2 n+b_2 c_1 n ○ =(a_1 c_2+b_2 c_1 )n ○ Thus, n|(a_1 c_2+b_2 c_1 ) ○ So, (a_1 a_2 ) ̅=(b_1 b_2 ) ̅ ∎ Well-definedness • Example ○ Say we want to "define" a map § f:Z\/2Z→Z § f(a ̅ )=a ○ f is not a function § 1 ̅=3 ̅ in Z\/2Z § But f(1 ̅ )=1≠f(3 ̅ )=3 ○ So we say that f is not well defined • How to check well-definedness ○ To check that a purported function f:A→B is well-defined ○ (i.e. to check f is a function) ○ one needs to check that a=a^′⇒f(a)=f(a′) Corollary 10 (Integers Modulo n) • Statement ○ If n∈Z( 0), Z\/nZ is a group under the operation § Z\/nZ×Z\/nZ→Z\/nZ § (a ̅,b ̅ )↦(a+b) ̅ ○ We will denote this operation by + ○ So a ̅+b ̅=(a+b) ̅ • Proof ○ Well-definedness § By proposition 9, the operation a ̅+b ̅=(a+b) ̅ is well-defined ○ Associative § Associativity is inherited from associativity of addition for Z ○ Identity § The identity is 0 ̅ § ∀a ̅∈Z\/nZ, a ̅+0 ̅=(a+0) ̅=a ̅=(0+a) ̅=0 ̅+a ̅ ○ Inverses § ∀a ̅∈Z\/nZ, the inverse of a ̅ is (−a) ̅ § a ̅+(−a) ̅=(a−a) ̅=0 ̅=(−a+a) ̅=(−a) ̅+a ̅$

Math 541 – 2/2

$Homework 1 (a) • Let A and B be nonempty sets, and let f:A→B be a function. • Suppose f is injective, prove that f has a left inverse • Since f is injective, ∀b∈im(f),∃!a∈A s.t. f(a)=b • Define g:B→A in the following way ○ Choose a_0∈A ○ If b∈im(f) § Choose a∈A s.t. f(a)=b § Define g(b)=a ○ If b∉im(f) § Define g(b)=a_0 • Check that g is a left inverse ○ If a∈A, (g∘f)(a)=g(f(a))=a ○ Thus, g∘f=id_A Example of The Euclidean Algorithm • Let a=97, b=20 • Use the Euclidean Algorithm to find (a,b) ○ 97=20×4+17 ○ 20=17×1+3 ○ 17=3×5+2 ○ 3=2×1+1 ○ Therefore (a,b)=1 • And then find x,y∈Z s.t. (a,b)=ax+by ○ (a,b)=1 ○ =3−2×1 ○ =3−(17−3×5)×1 ○ =3×6−17×1 ○ =(20−17×1)×6−17 ○ =20×6−17×7 ○ =20×6−(97−20×4)×7 ○ =97×(−7)+20×34 ○ We can take x=−7, y=34 Equivalence Class • Let X be a set, and let ~ be an equivalence relation on X • If x∈X, then the equivalence class represented by x is the set • [x]={x^′∈X│x~x^′ }⊆X Proposition 8 • Statement ○ Let X be a set with equivalence relationship ~ ○ If x,x^′∈X, then [x] and [x′] are either equal or disjoint • Proof ○ Suppose ∃y∈[x]∩[x^′ ] ○ It suffices to show if z∈X, then x~z⟺x^′~z ○ x~z⇒x^′~z § Suppose x~z § ⇒z~x (Symmetry) § ⇒z~y (Transitivity) § ⇒y~z (Symmetry) § ⇒x^′~z (Transitivity) ○ x~z⇐x^′~z § Suppose x′~z § ⇒z~x′ (Symmetry) § ⇒z~y (Transitivity) § ⇒y~z (Symmetry) § ⇒x~z (Transitivity) Integers Modulo n • Let n∈Z( 0) • The relation on Z given by a~b⟺n|(a−b) is an equivalence relation • The set of equivalence classes under ~ is denoted as Z\/nZ • We call this set integers modulo n (or integers mod n) • We can check that there are n elements in Z\/nZ • Use a ̅ to denote the equivalence class in Z\/nZ • Then Z\/nZ={0 ̅,1 ̅,2 ̅,…,(n−1) ̅ } Group • Definition ○ If G is a set equipped with a binary operation § G×G→G § (g,h↦g⋅h ○ that satisfy § Associativity: ∀g,h,k∈G, g⋅(hk)=(g⋅h⋅k § Identity: ∃1∈G s.t. ∀g∈G,1⋅g=g⋅1=g § Inverses: ∀g∈G, ∃g^(−1)∈G s.t. gg^(−1)=g^(−1) g=1 ○ Then we say G is a group under this operation • Z,Q,R,ℂ are groups with operation + ○ If a,b∈Z, then a+b∈Z (Similarly for Q,R,ℂ) ○ + is certainly associative in all 4 sets ○ 0 is the identity in each case ○ If a∈Z (or QRℂ), then the inverse of a is −a$

Math 541 – 1/31

Proposition 6 • Statement ○ If a,b∈Z, then (a,b) exists • Proof ○ By Proposition 5, we may assume b≠0 ○ Choose q,r∈Z s.t. a=bq+r, where 0≤r |b| ○ We argue by induction on r ○ Inductive hypothesis § If a′,b′∈Z s.t. b^′≠0, and a^′=b^′ q^′+r^′, where 0≤r^′ r § Then (a′,b′) exists ○ Base case § Suppose r=0, then a=bq § We have ├ |b|┤|├ a┤ and ├ |b|┤|├ b┤ § If e∈Z s.t. e|a and e|b, then ├ e┤|├ |b|┤ § Therefore (a,b) exists, and is |b| ○ Inductive step § Suppose r 0 § Choose q^′,r^′∈Z s.t. b=q^′ r+r′, where 0≤r^′ r § By induction, (b,r) exists § By Proposition 4, (a,b) exists, and euqals (b,r) The Euclidean Algorithm • Input ○ a,b∈Z with |b|≤|a| • Output ○ (a,b) • Algorithm (0) If b=0, output |a| Else, proceed to step (1) (1) If b≠0, find q,r∈Z s.t. a=bq+r, where 0≤r |b| (2) If r=0, output |b| Otherwise, repeat step (1) with b and r playing the roles of a and b • Note ○ The algorithm terminates ○ Since the remainder decreases at each application of step (1) ○ By Proposition 4, the output will be (a,b) • Example: use the Euclidean Algorithm to compute (4148, 2057) ○ Take a=4148, b=2057 ○ ⏟4148┬a=⏟2057┬b×⏟2┬q+⏟34┬r ○ ⏟2057┬a=⏟34┬b×⏟60┬q+⏟17┬r ○ ⏟34┬a=⏟17┬b×⏟2┬q+⏟0┬r ○ Here r=0, so the algorithm terminates ○ Thus, (4148, 2057)=17 Proposition 7 • Statement ○ If a,b∈Z, then ∃x,y∈Z s.t. (a,b)=ax+by • Note ○ x,y need not to be unique • Proof ○ If a=b=0 § We may take x=y=0 § In fact, any pair of (x,y) works ○ If a=0 or b=0 § Without loss of generality, assume b=0 § Then (a,b)=|a|=±a+b § Take x=±1, y=1 ○ If a≠0 and b≠0 § Without loss of generality, assume |a|≥|b| § Choose q,r∈Z s.t. a=qb+r, where 0≤r |b| § We argue by induction on r § Base case □ Suppose r=0, then (a,b)=|b|=0⋅a+(±1)⋅b □ So take x=0, y=±1 § Inductive step □ Suppose r 0 □ Choose q^′,r^′∈Z s.t. b=q^′ r+r^′, where 0≤r^′ r □ By induction, ∃x^′,y^′∈Z s.t. (b,r)=bx^′+ry^′ □ Thus, by Proposition 4 □ (a,b)=(b,r)=bx^′+(a−bq) y^′=ay^′+b(x^′−qy′) □ Take x=y′ and y=x^′−qy^′ • Example: express (4148, 2057) as 4148x+2057y where x,y∈Z ○ Recall when we computed (4148, 2057), we had § 4148=2057×2+34 § 2057=34×60+17 § 34=17×2+0 ○ Let s now find x,y∈Z s.t. (4148, 2057)=17=4148x+2057y ○ Start with the second to last equation, and "back-fill" § 17=2057−34×60 § =2057−(4148−2×2057)×60 § =4148×(−60)+2057×121 ○ Therefore x=−60, y=121

Shawn Zhong

Shawn Zhong

Notes

Math 521 – 2/5

Math 521 – 2/2

Math 541 – 2/5

Math 541 – 2/2

Math 541 – 1/31

Search

WeChat Account