January 30, 2018 - Page 2 of 3 - Shawn Zhong

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

Math 541 – 1/26

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

Math 541 – 1/24

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

Shawn Zhong

Shawn Zhong

1.1 Propositional Logic

0. Introductory Lecture

Math 541 – 1/29

Math 541 – 1/26

Math 541 – 1/24

Search

WeChat Account