2018 - Page 33 of 41 - Shawn Zhong

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

Math 521 – 1/31

$Upper Bound and Lower Bound • Suppose S is an ordered set and E⊂S • If there exists β∈S such that x≤β, ∀x∈E • We say that x is bounded above and call β an upper bound for E • If there exists β∈S such that x≥β, ∀x∈E • We say that x is bonded below by β, and β is a lower bound for E Least Upper Bound and Greatest Lower Bound • Definition ○ Suppose S is an ordered set and E⊂S is bounded above. ○ Suppose there exists α∈S s.t. § α is an upper bond of E § If γ α, then γ is not an upper bound of E ○ Then we call α the least upper bound (or lub or sup or supremium) of E ○ Suppose there exists α∈S s.t. § α is an lower bond of E § If γ α, then γ is not an lower bound of E ○ Then we call α the greastst lower bound (or glb or inf or infimum) of E • Examples ○ Recall § A={q∈Qq^2 2} has no sup in Q § B={q∈Qq^2 2} has no inf in Q ○ If α=sup⁡E exists, α may or may not be in E § E_1≔{r∈Qr 0} □ inf⁡〖E_1 〗 doesn t exist □ sup⁡〖E_1 〗=0∉E_1 § E_2≔{r∈Qr≤0} □ inf⁡〖E_2 〗 doesn t exist □ sup⁡〖E_2 〗=0∈E_2 § E≔{1/n│n∈N={1, 1/2,1/3,1/4,⋯} □ inf⁡E=0∉E □ sup⁡E=1∈E • Least-upper-bound property ○ We say that a ordered set S has least-upper-bound property provided that ○ if E∈S s.t. E≠∅ and E is bounded above, then sup⁡E exists and sup⁡E∈S Theorem 1.11 • Statement ○ Suppose S is an ordered set with the least-upper-bound property ○ Suppose B⊂S, B≠∅ and B is bounded below ○ Let L be the set of lower bounds of B ○ Then α=sup⁡L exists in S and α=inf⁡B • Proof ○ L≠∅ § B is bounded below, so L is not empty ○ L is bounded above § Given b∈B and l∈L, we have l≤b by definition of L § Therefore, L is bounded above ○ sup⁡L exists in S § L≠∅, L is bounded above § And S has least upper bound property § So sup⁡L exists § Let α=sup⁡L∈S ○ α is a lower bound for B (i.e. α∈L) § If γ α, then γ is not an upper bound for L, so γ∉B § So α≤x for all x∈B § Thus, α is a lower bound for B § i.e. α∈L ○ α=inf⁡B § If β α is another lower bound for B § Then β∉L since α is an upper bound for L § So, α∈L, but β∉L if β α § Therefore α is the least upper bound of B § i.e. α=inf⁡B ○ Therefore α=sup⁡L=inf⁡B∈S Ordered Field • Definition ○ An ordered field is a field F which is also an ordered set, such that § x+y x+z if x,y,z∈F and y z § xy 0 if x,y∈F, x 0 and y 0 ○ If x 0, we call x positive ○ If x 0, we call x negative • Examples ○ N,Z,Q, R • Note ○ R is an ordered field with least-upper-bound property$

Shawn Zhong

Shawn Zhong

Math 521 – 2/2

Math 541 – 2/5

Math 541 – 2/2

Math 541 – 1/31

Math 521 – 1/31

Search

WeChat Account