Mathematics Archives - Page 29 of 60 - Shawn Zhong

Math 521 – 2/19

$Metric Space • Definition ○ A set X of points is called a metric space if ○ there exists a metric or distance function d(p,q):X×X→R such that § Positivity □ d(p,q)0 if p,q∈X and p≠q □ d(p,p)=0 for all p∈X § Symmetry □ d(p,q)=d(q,p) for all p,q∈X § Triangle Inequality □ d(p,q)≤d(p,r)+d(r,q) for all p,q,r∈X • Example 1 ○ X=Rk ○ d(p ⃗,q ⃗ )=|p ⃗−q ⃗ | ○ If k=1, this is just standard numerical absolute value ○ and d is distance on the number line • Example 2 (Taxicab metric) ○ X=R2 ○ d((p_1,p_2 ),(q_1,q_2 ))=|p_1−q_1 |+|p_2−q_2 | where p_1,p_2,q_1,q_2∈R ○ Is this a true metric space? ○ Positivity § Clearly d((p_1,p_2 ),(q_1,q_2 ))≥0 since it is a sum of absolute values § Suppose d((p_1,p_2 ),(q_1,q_2 ))=0 □ |p_1−q_1 |+|p_2−q_2 |=0 □ |p_1−q_1 |=−|p_2−q_2 | □ {█(|p_1−q_1 |=0@|p_2−q_2 |=0)┤⇒{█(p_1=q_1@p_2=q_2 )┤ □ i.e. (p_1,p_2 )=(q_1,q_2 ) § Suppose (p_1,p_2 )=(q_1,q_2 ) □ d((p_1,p_2 ),(q_1,q_2 ))=|p_1−q_1 |+|p_2−q_2 |=|0|+|0|=0 § Thus d((p_1,p_2 ),(q_1,q_2 ))=0 iff (p_1,p_2 )=(q_1,q_2 ) ○ Symmetry § d((p_1,p_2 ),(q_1,q_2 ))=|p_1−q_1 |+|p_2−q_2 | § =|q_1−p_1 |+|q_2−p_2 |=d((q_1,q_2 ),(p_1,p_2 )) ○ Triangular Inequality § d((p_1,p_2 ),(r_1,r_2 ))+d((r_1,r_2 ),(q_1,q_2 )) § =|p_1−r_1 |+|p_2−r_2 |+|r_1−q_1 |+|r_2−q_2 | § =(|p_1−r_1 |+|r_1−q_1 |)+(|p_2−r_2 |+|r_2−q_2 |) § ≥|p_1−r_2+r_1−q_1 |+|p_2−r_2+r_2−q_2 | by Triangle Inequality of R § =|p_1−q_1 |+|p_2−q_2 | § =d((p_1,p_2 ),(q_1,q_2 )) Definition 2.17 • Interval ○ Segment (a,b) is {x∈Raxb} (open interval) ○ Interval [a,b] is {x∈Ra≤x≤b} (closed interval) ○ We can also have half-open intervals: (a,b] and [a,b) • k-cell ○ If a_ib_i for i=1,2,…,k ○ The set of points x ⃗=(x_1,x_2,…,x_k ) in Rk ○ that satisfy a_i≤x_i≤b_i (1≤i≤k) is called a k-cell • Ball ○ If x ⃗∈Rk and r0 ○ the open ball with center x ⃗ with radius r is {y ⃗∈Rk│|x ⃗−y ⃗ |r} ○ the closed ball with center x ⃗ with radius r is {y ⃗∈Rk│|x ⃗−y ⃗ |≤r} • Convex ○ We call a set E⊂Rk convex if ○ λx ⃗+(1−λ) y ⃗∈E, ∀x ⃗,y ⃗∈E, 0λ1 ○ i.e. All points along a straight line from x ⃗ to y ⃗ and between x ⃗ and y ⃗ is in E • Example: Balls are convex ○ Given an open ball with center x ⃗ and radius r ○ If y ⃗,z ⃗∈B, then |y ⃗−x ⃗ |r and |z ⃗−x ⃗ |r ○ |λz ⃗+(1−λ) y ⃗−x ⃗ | ○ =|λz ⃗+(1−λ) y ⃗−(λ+1−λ) x ⃗ | ○ =|λz ⃗−λx ⃗+(1−λ) y ⃗−(1−λ) x ⃗ | ○ ≤|λz ⃗−λx ⃗ |+|(1−λ) y ⃗−(1−λ) x ⃗ | by Triangle Inequality ○ =λ|z ⃗−x ⃗ |+(1−λ)|y ⃗−x ⃗ | ○ λr+(1−λ)r=r ○ Thus |λz ⃗+(1−λ) y ⃗−x ⃗ |r ○ i.e. λz ⃗+(1−λ) y ⃗∈B Definition 2.18 (a) Neighborhood (b) Limit point (c) Isolated point (d) Closed (e) Interior point (f) Open (g) Complement (h) Perfect (i) Bounded (j) Dense$

Math 521 – 2/16

$Set-Theoretic Operations • Set theoretic union ○ ⋃24_(n=1)^∞▒A_n =A_1∪A_2∪A_3∪⋯ • Set theoretic intersection ○ ⋂24_(n=1)^∞▒A_n =A_1∩A_2∩A_3∩⋯ • Indexing set ○ ⋃8_(α∈A)▒E_α , where ○ A is an indexing set ○ E_α is a specific set that depends on A • Example ○ Let A={x∈R0x≤1} ○ Let E_α={x∈R0xa} ○ Then⋃8_(α∈A)▒E_α =(0,1) and ⋂8_(α∈A)▒E_α =∅ Theorem 2.12 • Statement ○ Let {E_n }_(n∈N be a sequence of countable sets, then ○ S=⋃24_(n=1)^∞▒E_n is also countable • Proof ○ Just like the proof that Q is countable ○ E_n={〖x_n〗_k }={〖x_n〗_1,〖x_n〗_2,〖x_n〗_3,…} ○ ■(x_11&x_12&x_13&x_14&…&@x_21&x_22&x_23&⋱&&@x_31&x_32&⋱&&&@x_41&⋱&&&&@⋮&&&&&) ○ Go along the diagonal, we have ○ S={x_11,x_21,x_12,x_31,x_22,x_13…} • Corollary ○ Suppose A is at most countable ○ If for α∈A, B_α is at most countable, then ○ T=⋃8_(α∈A)▒B_α is also at most countable Theorem 2.13 • Statement ○ Let A be a countable set ○ Let B_n be the set of all n-tuples (a_1,a_2,…a_n ) where a_k∈A for 1≤k≤n ○ And a_k may not be distinct, then B_n is countable • Proof ○ We proof by induction on n ○ Base case: n=2 § ■((a_1,a_1 )&(a_1,a_2 )&(a_1,a_3 )&(a_1,a_4 )&…&@(a_2,a_1 )&(a_2,a_2 )&(a_2,a_3 )&⋱&&@(a_3,a_1 )&(a_3,a_2 )&⋱&&&@(a_4,a_1 )&⋱&&&&@⋮&&&&&) § Here a_i are all the elements of A with possible repetition ○ Now assume for n=m (m≥2) § The set of m-tuples (a_1,a_2,…a_m ) are countable § Now we treat the (m+1)\-tuples as ordered pairs § (a_1,a_2,…a_(m+1) )=((a_1,a_2,…a_m ),a_(m+1) ) § By n=2 case, the set of (m+1)\-tuples is still countable Theorem 2.14 • Statement ○ Let A be the set of all sequqnecse whose digits are 0 and 1 ○ Then A is uncountable • Proof: Cantor$

Math 541 – 2/14

$Homomorphism • Definition ○ Let G,H be groups ○ A function f:G→H is a homomorphism if ○ f(g_1 g_2 )=f(g_1 )f(g_2 ), ∀g_1,g_2∈G ○ One says f "respects", or "preserves" the group operation • Trivial Examples ○ Let G be a group ○ The identity map of G→G is a homomorphism § f(g_1 )f(g_2 )=1⋅1=1=f(g_1 g_2 ) ○ The map G→G given by g↦1 is a homomorphism § This only works if we send every element of G to 1 § If x∈G∖{1}, and f:G→G is given by g↦x,∀g § f(g_1 g_2 )=f(g_1 )(g_2 ) § i.e. x=x^2 § Thus x=1 § This is impossible since x∈G∖{1} • Example 1 ○ Let f:R→R∗ be given by f(x)=e^x ○ f is a homomorphism ○ f(x_1+x_2 )=e^(x_1+x_2 )=e^(x_1 ) e^(x_2 )=f(x_1 )f(x_2 ) • Example 2 ○ Let G be a group, and let x∈G ○ The map f:G→G, g↦xgx^(−1) is a homomorphism ○ f(g_1 g_2 )=xg_1 g_2 x^(−1)=xg_(1 ) x^(−1) xg_2 x^(−1)=f(g_1 )f(g_2 ) ○ This homomorphism is called conjugation by x • Example 3 ○ Let n∈Z ○ Is f:Z→Z, x↦x+n a homomorphism? ○ Answer: Only when n=0 ○ f(0+0)=f(0) ○ i.e. n+n=n ○ Thus n=0 • Example 4 ○ Let n∈{0,1,2,3,…} ○ Is α:Z→Z, x↦x^n a homomorphism? ○ Answer: Only when n=1 ○ When x=0 § α(x)=1 § 1 is not the identity (0 is) § So this doesn’t work ○ For n≥2 § α(x_1+x_2 )=α(x_1 )+α(x_2 ) § (x_1+x_2 )^n=x_1^n+x_2^n § This is not always true § For instance, when x_1=x_2=1, 2^n≠2 for n≥2 • Example 5 ○ Let n∈Z ○ Is β:Z→Z, x↦nx a homomorphism? ○ Answer: Yes ○ β(x_1+x_2 )=n(x_1+x_2 )=nx_1+nx_2=β(x_1 )+β(x_2 ) • Example 6 ○ The previous examples is a special case of the following: ○ Let G be a group, and n∈Z ○ Define β:G→G, g↦g^n ○ Then β is homomorphism ∀n∈Z iff G is abelian ○ Proof: homomorphism ⇒ abelian § Say n=−1 § Let g_1,g_2∈G § β(g_1,g_2 )=β(g_1 )β(g_2 ) § (g_1 g_2 )^(−1)=g_1^(−1) g_2^(−1) § g_2^(−1) g_1^(−1)=g_1^(−1) g_2^(−1) § (g_2^(−1) g_1^(−1) )^(−1)=(g_1^(−1) g_2^(−1) )^(−1) § (g_1^(−1) )^(−1) (g_2^(−1) )^(−1)=(g_2^(−1) )^(−1) (g_1^(−1) )^(−1) § g_1 g_2=g_2 g_1 § Thus G is abelian ○ Proof: abelian ⇒ homomorphism § (Homework) Isomorphism • Definition ○ Let G,H be groups ○ A homomorphism α:G→H is a isomorphism if ○ there is a homomorphism β:H→G s.t. ○ αβ=id_H and βα=id_G ○ In this case, we say G and H are isomorphic • Fact ○ L:G→H is an isomorphism iff it is a bijective homomorphism ○ Proof: isomorphism ⇒ bijective homomorphism § Clear ○ Proof: bijective homomorphism ⇒ isomorphism § Need to show α^(−1) is a homormorphism § (Homework) • Example ○ R(0)≔{r∈Rr0} is a group under multiplication ○ Define f:R→R(0) where f(x)=e^x ○ Then f is a homomorphism ○ Moreover, f is an isomorphism ○ The inverse of f is ln • Observation ○ If G,H are isomorphic groups, then |G|=|H| Proposition 16 • Statement ○ If f:G→H is an isomorphism, then ○ G is abelian iff H is abelian ○ ∀g∈G, |g|=|f(g)| ○ Note |g|=inf⁡{n∈Z(0)│g^n=1}$

Math 521 – 2/14

$Finite and Countable • Definition ○ Let J_n={1,2,3,…,n} and N={1,2,3,…} ○ For any set A, we say ○ A is finite if A~J_n for some n (∅~J_0 so ∅ is finite) ○ A is infinite if A≁J_n for all n ○ A is countable if A~N ○ A is uncountable if A is neither finite nor countable ○ A is at most coutable if A is finite or countable • Examples ○ N is clearly countable § N={1,2,3,…} ○ Z is countable § Z={0,1,−1,2,−2,3,−3,…} § Define f:N→Z by § f(n)≔{■8(n/2&n is even@(1−n)/2&n is odd)┤ § f is injective □ If f(n)=f(m) □ then n/2=m/2 or (1−n)/2=(1−m)/2 □ Either way, n=m § f is surjective □ Given k∈Z, □ If k0, k=f(2k) □ If k≤0, k=f(−2k+1) § Thus f is bijective ○ Q is countable § There are "less" rational numbers q=m/n (m,n∈Z,n≠0) than § there are ordered pairs of integers (m,n) □ 1/2=15/30 but (1,2)≠(15,30) □ We can also ignore negatives and zeros □ because integers are in 1-1 correspondence with N § Idea: Write ordered pairs of integers in a 2 dimension array § Putting this all together, we have § Q={0,±1,±2,±1/2,±1/3,±3,±4,±3/2,±2/3,±1/4,…} Sequence • Definition ○ A sequence is a function defined on N ○ Notationally, this is often written {x_n } ○ Meaning f(x)=x_n for all n∈N • Example ○ {1/n}={1, 1/2,1/3,…} Theorem 2.8 • Statement ○ Every infinite subset of a countable set is countable • Proof ○ Suppose E⊂A, A is countable and E is infinite ○ Since A is countable, its element will be a sequqnce ○ (order given by the bijective function f:N→A) ○ So, A={x_n } as a set ○ Let n_1 be the smallest n∈N such that x_(n_1 )∈E ○ Let n_2 be the next smallest n∈N such that 〖x_n〗_2∈E ○ So E={x_(n_k ) }={x_(n_1 ),x_(n_2 ),x_(n_3 ),…} (A sequence indexed by k∈N) ○ Now consider g:N→E given by g(k)=x_(n_k ) ○ g is clearly one-to-one and onto by construction ○ So E is countable • Example ○ If A={1, 1/2,1/3,…} and E={1, 1/4,1/9,1/16} ○ Then A={1/n}={1, 1/2,1/3,…} ○ and E={1/n_k }={1, 1/4,1/9,1/16} where n_k=k^2 for k∈N ○ f:A→E by f(k)=1/k^2$

2.4 Sequences and Summations

$Introduction • Sequences are ordered lists of elements. ○ 1,2,3,5,8 ○ 1,3,9,27,81,… • Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music. • We will introduce the terminology to represent sequences and sums of the terms in the sequences. Sequences • Definition ○ A sequence is a function from a subset of the integers to a set S. ○ The notation a_n is used to denote the image of the integer n. ○ We can think of a_n as the equivalent of f(n) ○ where f is a function from {0,1,2,…..} to S. ○ We call a_n a term of the sequence. • Example ○ Consider the sequence {a_n } where ○ a_n=1/n, {a_n }={a_1,a_2,a_3,…} ○ 1, 1/2,1/3,… Strings • A string is a finite sequence of characters from a finite set (an alphabet). • Sequences of characters or bits are important in computer science. • The empty string is represented by λ. • The string abcde has length 5. Geometric Progression • Definition ○ A geometric progression is a sequence of the form: a,ar,ar^2,…,ar^n,… ○ where the initial term a and the common ratio r are real numbers • Example 1 ○ Let a = 1 and r = −1. Then: ○ {b_n }={b_0,b_1,b_2,b_3,b_4,…}={1,−1,1,−1,1,…} • Example 2 ○ Let a = 2 and r = 5. Then: ○ {c_n }={c_0,c_1,c_2,c_3,c_4,…}={2,10,50,250,1250,…} • Example 3 ○ Let a = 6 and r=1/3. Then: ○ {d_n }={d_0,d_1,d_2,d_3,d_4,…}={6,2, 2/3,2/9,2/27,…} Arithmetic Progression • Definition ○ A arithmetic progression is a sequence of the form ○ a,a+d,a+2d,…,a+nd,… ○ where the initial term a and the common difference d are real numbers • Example 1 ○ Let a = −1 and d = 4: ○ {s_n }={s_0,s_1,s_2,s_3,s_4…}={−1,3,7,11,15…} • Example 2 ○ Let a = 7 and d = −3: ○ {t_n }={t_0,t_1,t_2,t_3,t_4…}={7,4,1,−2,−5…} • Example 3 ○ Let a = 1 and d = 2: ○ {u_n }={u_0,u_1,u_2,u_3,u_4…}={1,3,5,7,9…} Recurrence Relations • A recurrence relation for the sequence {a_n} is an equation that ○ expresses a_n in terms of a_0, a_1, …, a_(n−1) ○ for all integers n with n≥n_0, where n_0 is a nonnegative integer. • A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. • The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect. • Example ○ Let {a_n} be a sequence that satisfies § the recurrence relation a_n=a_(n−1)+3 for n=1,2,3,4 § and suppose that a_0=2. ○ What are a_1, a_2 and a_3? ○ a_1=a_0+3=2+3=5 ○ a_2=5+3=8 ○ a_3=8+3=11 Fibonacci Sequence • Define the Fibonacci sequence, f0 ,f1 ,f2,…, by: ○ Initial Conditions: f_0=0, f_1=1 ○ Recurrence Relation: f_n=f_(n−1)+f_(n−2) • Find f_2,f_3,f_4,f_5,f_6 ○ f_2=f_1+f_0=1+0=1 ○ f_3=f_2+f_1=1+1=2 ○ f_4=f_3+f_2=2+1=3 ○ f_5=f_4+f_3=3+2=5 ○ f_6=f_5+f_4=5+3=8 Solving Recurrence Relations • Finding a formula for the n-th term of the sequence generated by a recurrence relation is called solving the recurrence relation. • Such a formula is called a closed formula. • Various methods for solving recurrence relations will be covered in Chapter 8 where recurrence relations will be studied in greater depth. • Here we illustrate by example the method of iteration in which we need to guess the formula. The guess can be proved correct by the method of induction (Chapter 5). • Method 1: Working upward, forward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_2=2+3 ○ a_3=(2+3)+3=2+3∙2 ○ a_4=(2+2∙3)+3=2+3∙3 ○ ⋮ ○ a_n=a_(n−1)+3=(2+3∙(n–2))+3=2+3(n–1) • Method 2: Working downward, backward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_n=a_(n−1)+3 ○ =(a_(n−2)+3)+3=a_(n−2)+3∙2 ○ =(a_(n−3)+3)+3∙2=a_(n−3)+3∙3 ○ =… ○ =a_2+3(n–2)=(a_1+3)+3(n–2)=2+3(n–1) Summations • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m+a_(m+1)+…+a_n ○ ∑_(j=m)^n▒a_j • The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n. • More generally for a set S ○ ∑_(j∈S)▒a_j • Examples: ○ r^0+r^1+r^2+r^3+…+r^n=∑_(j=0)^n▒r^j ○ 1+1/2+1/3+1/4+…=∑_(i=1)^∞▒1/i ○ If S={2,5,7,10} then ∑_(j∈S)▒a_j =a_2+a_5+a_7+a_10 Geometric Series • Sums of terms of geometric progressions • Product Notation • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m×a_(m+1)×…×a_n ○ ∏_(j=m)^n▒a_j$

Shawn Zhong

Shawn Zhong

Mathematics

Math 521 – 2/19

Math 521 – 2/16

Math 541 – 2/14

Math 521 – 2/14

2.4 Sequences and Summations

Search

WeChat Account