Shawn Zhong

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Math 541

Home / Mathematics / Notes / Math 541 / Page 8

Math 541 - 1/31

  • Jan 31, 2018
  • Shawn
  • Math 541
  • No comments yet
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
Read More >>

Math 541 - 1/29

  • Jan 30, 2018
  • Shawn
  • Math 541
  • No comments yet
Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤r b • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤r b § We know 0≤r, since r∈S, so we just need to show r b § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, r b ○ Therefore we ve proven the existence of q and r • Proof (Uniqueness) ○ Suppose ∃q,q^′,r,r^′∈Z s.t. § a=bq+r, where 0≤r b § a=bq^′+r^′, where 0≤r^′ b ○ We must show q=q′ and r=r^′ ○ Suppose r≠r^′ § Without loss of generality, assume r^′ r § Then 0 r^′−r=(a−bq^′ )−(a−bq)=b(q−q^′ ) § Thus, ├ b┤|├ (r^′−r)┤, but 0 r^′−r≤r^′ b. § This is impossible, thus r=r^′ ○ We have bq+r=bq^′+r⇒q=q^′ ○ Therefore we ve proven the uniqueness of q and r • Note we can prove the following stronger statement ○ If a,b∈Z, and b≠0, then ∃!q,r∈Z ○ s.t. a=bq+r, and 0≤r |b| • Proof (Existence) ○ Assume b 0 ○ Choose q,r∈Z s.t. a=(−b)q+r, and 0≤r −b ○ Then a=b(−q)+r, and 0≤r |b| ○ This proves existence • Proof (Uniqueness) ○ Assume b 0 ○ Suppose ∃q,q^′,r,r^′∈Z s.t. § a=bq+r, where 0≤r b § a=bq^′+r^′, where 0≤r^′ b ○ Then § a=(−b)(−q)+r, where 0≤r |b|=−b § a=(−b)(−q′)+r^′, where 0≤r^′ |b|=−b ○ Since −b 0, our previous result implies −q=−q^′ ○ ⇒q=q′ and r=r^′ Greatest Common Divisor • If a,b∈Z, where either a≠0 or b≠0 • A greatest common divisor of a and b is a positive integer d s.t. ○ d|a and d|b ○ If e∈Z s.t. e|a and e|b then e|d • We write the g.c.d. of a and b, if it exists, as (a,b) • As a convention (0,0)≔0 Proposition 3: Uniqueness of Greatest Common Divisor • Statement ○ Let a,b∈Z, where either a≠0 or b≠0 ○ Suppose ∃d,d^′∈Z( 0) s.t. (1) d and d′ both divide a and b (2) If e∈Z s.t. e|a and e|b, then e|d and e|d^′ ○ Then d=d^′ • Proof ○ Combining properties (1) and (2), we have d|d′ and d^′ |d ○ Choose q,q^′∈Z s.t. dq=d′ and d^′ q^′=d ○ By substitution, we get dqq^′=d ○ Then qq^′=1⇒q=q^′=±1 ○ If q=q^′=−1, then d=−d^′ 0. ○ This is impossible since d and d′ are both positive ○ Therefore q=q^′=1 and d=d^′ Proposition 4 • Statement ○ Suppose a,b∈Z, where b≠0 ○ Choose q,r∈Z s.t. a=qb+r, and 0≤r |b| ○ If (b,r) exists, then (a,b) exists and (a,b)=(b,r) • Proof ○ Set d≔(b,r) ○ d|a and d|b § Choose q_1,q_2∈Z s.t. dq_1=b and dq_2=r § Then a=qb+r=qq_1 d+q_2 d=d(qq_1+q_2 ), so d|a § And we already know d|b ○ If e∈Z s.t. e|a and e|b, then e|d § Let e∈Z s.t. e|a and e|b § Choose q_3,q_4∈Z s.t. eq_3=a and eq_4=b § a=qb+r § ⇒a−qb=r § ⇒eq_3−qeq_4=r § ⇒e(q_3−qq_4 )=r § Thus e|r § Since e|b and d=(b,r) § We can conclude that e|d ○ By Proposition 3, (a,b)=(b,r) Proposition 5 • Statement ○ (a,0)=|a|,∀a∈Z • Proof ○ If a=0 § This is true by our convention ○ If a≠0 § Certainly ├ |a|┤|├ a┤, and ├ |a|┤|├ 0┤ § If e∈Z s.t. e|a and ├ e┤|├ 0┤, then ├ e┤|├ |a|┤ § Therefore (a,0)=|a|
Read More >>

Math 541 - 1/26

  • Jan 30, 2018
  • Shawn
  • Math 541
  • No comments yet
Induction • Prove that ∑_(i=1)^n▒i=n(n+1)/2, ∀n≥1 • Base case, n=1 ○ ∑_(i=1)^i▒i=1=(1×2)/2 • Induction step ○ For n 1 ○ Assume ∀k s.t. 1≤kn, ∑_(i=1)^k▒i=k(k+1)/2 ○ Then∑_(i=1)^n▒i=(∑_(i=1)^(n−1)▒i)+n=(n−1)(n)/2+n=n(n+1)/2 Proposition 1: Well-ordering of Z • Statement ○ Every nonempty set S of Z(≥0) has a unique minimum element ○ That is, ∃!m∈S s.t. m≤s, ∀s∈S • Proof (Existence) ○ Assume S is finite § We will argue by induction on |S| § Base case: |S|=1 □ This is clear § Assume |S| 1 □ Choose x∈S, then |S∖{x}|=|S|−1 □ By induction S∖\{x} has a minimum value: call it m □ Case 1: xm, then x is a minimum value of S □ Case 2: mx, then m is a minimum value of S ○ Now we prove the general case § Choose x∈S § Let S^′≔{s∈S│s≤x} § Then |S^′ |≤x+1∞ § Choose a minimum element of S: call it m § Let s∈S □ If s∈S^′, then m≤s □ If s∉S′, then m≤xs § In either case, m≤s, so m is a minimum element of S ○ This proves existence • Proof (Uniqueness) ○ Suppose m and m′ are both minimum elements of S ○ m≤m′, and m^′≤m ○ Thus, m=m^′ ○ This proves uniqueness Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤rb • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤rb § We know 0≤r, since r∈S, so we just need to show rb § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, rb ○ Therefore we ve proven the existence of q and r
Read More >>

Math 541 - 1/24

  • Jan 30, 2018
  • Shawn
  • Math 541
  • No comments yet
Introduction • Course Plan ○ Frist 2/3 - Groups ("Sets with a multiplication rule") ○ Last 1/3 - Rings ("Set with notions of addition and multiplication") • Office Hours ○ Tuesdays 2:30 p.m. - 4:00 p.m. ○ Wednesdays 12:30 p.m. - 2:00 p.m. Notations • "□(≔) " means "equals, by definition" • Z≔{0,±1,±2,±3,…} the set of integers • Q≔{a/b│a,b∈Zb≠0} • R≔ the set of all real numbers • ℂ≔{a+bi│a,b∈Ri^2=−1} • Z(≥0)≔{a∈Za≥0} • S∖{x}≔{s∈S│s≠x} • Denote a function f from a set A to set B by f:A→B • Denote the image of f by im(f)≔{b∈B│∃a∈A s.t. f(a)=b} Injective, Surjective and Bijective • Definition ○ Let f:A→B be a function, then ○ f is injective if ∀a,a^′∈A, a≠a^′, f(a)≠f(a′) ○ f is surjective if ∀b∈B, ∃a∈A s.t. f(a)=b (i.e. im(f)=B) ○ f is bijective if f is both injective and surjective. • Example 1 ○ For f:Z→Z, f(a)=2a ○ f is injective § Let a,a^′∈Z § Suppose f(a)=f(a′) § ⇒2a=2a^′ § ⇒2a−2a^′=0 § ⇒2(a−a^′ )=0 § ⇒a−a^′=0 § ⇒a=a^′ § Therefore f is injective ○ f is not surjective § Because the image of f does not contain any odd integers § im(f)={even integer} • Example 2 ○ Let f:Q→Q is given by f(a)=2a ○ f is injective § By the same proof as before ○ f is surjective § Let b∈Q, then b/2∈Q § And f(b/2)=2(b/2)=b∈Q § Therefore f is surjective ○ f is bijective § Since f is both injective and surjective. Divides • Definition ○ If x,y∈Z, and x≠0 ○ We say x divides y and write x|y, if ∃q∈Z s.t. xq=y • Examples ○ ∀x∈Z\\{0}, x|0, since x⋅0=0 ○ ∀x∈Z, 1|x, since 1⋅x=x ○ ∀x∈Z, −1|x, since (−1)⋅(−x)=x Equivalence Relations • Product of Two Sets ○ If A and B are sets, then the product of A and B is ○ A×B≔{(a,b)│a∈A, b∈B} • Relations ○ A relation on a set A is a subset R of A×A ○ We write a~a′ if (a,a^′ )∈R • Equivalence Relations ○ A equivalence relation is a relation R on A such that R is ○ Reflexive § if a∈A, a~a § i.e. (a,a)∈R ○ Symmetric § if a~a′, then a^′~a § i.e. (a,a′)∈R⇒(a′,a)∈R ○ Transitive § if a~a^′, a^′~a^′′, then a~a′′ § i.e. if (a,a′)∈R and (a^′,a^′′ )∈R, then (a,a^′′ )∈R • Example 1 ○ Let R be a relation on set A such that R≔{(a,a)│a∈A} ○ Then R is an equivalence relation (a~a^′⟺a=a^′) ○ Reflexive § If a∈A,(a,a)∈R ○ Symmetric § If a~a′,a=a^′ § Thus a^′=a, hence a^′~a ○ Transitive § If a~a^′,a^′~a′′ then a=a′ and a=a′′ § Thus a=a^′′, hence a~a^′′ • Example 2 ○ Let n be a positive integer ○ Then R≔{(a,b)∈ZZn|(a−b) } is an equivalence relation ○ Reflexive § Recall that n|0 § Thus, n|(a−a), ∀a∈Z § It follows that a~a,∀a∈Z ○ Symmetric § Let a,b∈Z, and suppose n|(a−b) (i.e. a~b) § Choose q∈Z s.t. nq=a−b § Then n(−q)=−(a−b)=b−a § Thus, n|(b−a), and so b~a ○ Transitive § Suppose a,b,c∈Z, and we have a~b, b~c § Then n|(a−b) and n|(b−c) § Choose q,q^′∈Z s.t. nq=a−b, nq^′=b−c § Then n(q+q^′ )=(a−b)+(b−c)=a−c § Thus, n|(a−c), and so a~c
Read More >>
  • 1
  • …
  • 6
  • 7
  • 8

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 - Discrete Math
    • Math 375 - Linear Algebra
    • Math 431 - Intro to Probability
    • Math 514 - Numerical Analysis
    • Math 521 - Analysis I
    • Math 541 - Abstract Algebra
    • Math 632 - Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 - Intro to Computer Engr.
    • CS/ECE 352 - Digital System Fund.
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E&M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (4)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP