Mathematics Archives - Page 27 of 60 - Shawn Zhong

Math 541 – 2/26

$Proposition 21: Construction of ⟨A⟩ • Statement ○ If A⊆G, then ⟨A⟩={a_1^(ε_1 ) a_2^(ε_2 )…a_n^(ε_n )│n∈Z( 0),a_i∈A,ε∈{±1} } ○ (when n=0, we get 1) • Proof ○ Denote the right hand side by A ̅ ○ A ̅≠∅, since 1∈A ̅ (take n=0) ○ If a=a_1^(ε_1 ) a_2^(ε_2 )…a_n^(ε_n ),b=b_1^(δ_1 ) b_2^(δ_2 )…b_m^(δ_m )∈A ̅ ○ ab^(−1)=a_1^(ε_1 ) a_2^(ε_2 )…a_n^(ε_n ) b_m^(−δ_1 ) b_(m−1)^(−δ_2 )…b_1^(−δ_m )∈A ̅ ○ Thus A ̅≤G ○ A⊆A ̅, and ⟨A⟩ is the smallest subgroup of G containing A, so ⟨A⟩⊆A ̅ ○ A ̅⊆⟨A⟩, since every subgroup of G containing A (i.e. ⟨A⟩) ○ must contain every finite product of elements of A and their inverses. ○ Therefore ⟨A⟩=A ̅={a_1^(ε_1 ) a_2^(ε_2 )…a_n^(ε_n )│n∈Z( 0),a_i∈A,ε∈{±1} } • Example ○ If G is a group, and g∈G, then ⟨{g}⟩=⟨g⟩ • Note ○ When G is abelian and A⊆G, then ○ ⟨A⟩={a_1^(n_1 )…a_m^(n_m )│n_i∈Za_i∈A,m∈Z(≥0) } Finitely Generated Group • Definition ○ A group G is finitely generated if ○ there is a finite subset A of G s.t. ⟨A⟩=G • Example 1 ○ Cyclic groups are finitely generated • Example 2 ○ Finite groups are finitely generated • Example 3 ○ If G,H are finitely generated, then G×H is also finitedly generated ○ For instance, Z×Z is finitely generated by A={(1,0),(0,1)} ○ In particular, products of cyclic groups are finitely generated ○ Every finitely generated abelian group is a product of cyclic groups ○ (We won t prove this in Math 541) • Example 4 ○ Every finitely generated subgroup of Q is cyclic. ○ It follows that Q is not finitely generated, since Q is not cyclic (QZ ○ Suppose H≤Q, and H=⟨a_1/b_1 ,a_2/b_2 ,…,a_n/b_n ⟩ where a_i,b_i∈Z and b_i≠0 ○ Without loss of generality, assume a_i≠0 ○ Let S≔{x∈Z( 0)│x/(b_1 b_2…b_n )∈H} § S≠∅, since±(a_1 a_2…a_n)/(b_1 b_2…b_n )∈H § Applying the Well-Ordering Principle § Choose a minimum element e∈S ○ Claim:H=⟨e/(b_1 b_2…b_n )⟩ § Notice that H={c_1 a_1/b_1 +c_2 a_2/b_2 +…+c_n a_n/b_n │c_i∈Z § So we only need to check a_i/b_i ∈⟨e/(b_1 b_2…b_n )⟩ ∀i § Let i be fixed § Set z≔b_1…b_(i−1) a_i b_(i+1)…b_n § So a_i/b_i =z/(b_1 b_2…b_n ) § Choose q,r∈Z s.t z=qe+r, 0≤r e § (z−qe)/(b_1 b_2…b_n )∈H⇒r/(b_1 b_2…b_n )∈H § Thus, by the minimality of e, r=0 § This shows e|z § So a_i/b_i =z/(b_1 b_2…b_n )∈⟨e/(b_1 b_2…b_n )⟩ § Therefore H=⟨e/(b_1 b_2…b_n )⟩ ○ So H is cyclic$

Math 541 – 2/23

$Theorem 20 • Let G=⟨g⟩ be a cyclic group • Statement (1) ○ Every subgroup of G is cyclic ○ More precisely, if H≤G, then either H={1} or ○ H=⟨g^d ⟩, where d is the smallest positive integer s.t. g^d∈H • Proof (1) ○ Assume H≠{1} ○ Choose a≠0 s.t. g^a∈H, then (g^a )^(−1)=g^(−a)∈H ○ Thus, H contains some positive power of g ○ Let S≔{b∈Z( 0) |g^b∈H}, then S≠∅ ○ By the Well-Ordering Principle, S contains a minimum element d ○ Thus, ⟨g^d ⟩⊆H; we must show H⊆⟨g^d ⟩ ○ Let h∈H, then h=g^a for some a∈Z ○ Choose q,r∈Z s.t. a=qd+r, 0≤r d ○ g^d∈H⇒g^(−qd)∈H⇒g^a g^(−qd)∈H⇒g^r∈H ○ If r 0, then r∈S, which is impossible, since r d ○ Therefore r=0 ○ So g^a=g^qd∈⟨g^d ⟩⇒H⊆⟨g^d ⟩ ○ Therefore H=⟨g^d ⟩ • Statement (2) ○ If G is finite, then for all positive integers a dividing n ○ ∃! subgroup H≤G of order a ○ Moreover, this subgroup is ⟨g^d ⟩, where d=n/a • Proof (2) ○ Let a be a positive divisor of n=|G| ○ Let d≔n/a⇒n/d=a ○ Existence § |⟨g^d ⟩|=n/((d,n) )=n/d=a by Proposition 19 § This proves existence ○ Uniqueness § Without loss of generality, assume a 1 § Suppose H≤G and |H|=a § We must show H=⟨g^d ⟩ § By (1), H=⟨g^b ⟩, where b is the smallest positive integer s.t. g^b∈H § We have n/d=a=|H|=|⟨g^b ⟩|=n/((n,b) ) by Proposition 19 § Thus d=(n,b) i.e. d|b § Thus g^b∈⟨g^d ⟩⇒⟨g^b ⟩≤⟨g^d ⟩ § Since |⟨g^b ⟩|=|⟨g^d ⟩|, ⟨g^b ⟩=⟨g^d ⟩ § i.e. H=⟨g^d ⟩ Subgroups Generated by Subsets of a Group (Section 2.4) • Lemma: If {H_i }_(i∈I) is a family of subgroups of G, then ⋂136_(i∈I)▒〖H_i≤G〗 ○ Let H≔⋂136_(i∈I)▒H_i ○ H≠∅ because 1∈H_i, ∀i∈I ○ Let h1,h2∈H, then h1,h2∈H_i, ∀i∈I ○ ⇒h1 h2^(−1)∈H_i,∀i∈I ○ ⇒h1 h2^(−1)∈H • Definition ○ Let G be a group and A⊆G ○ The subgroup generated by A is ○ the intersection of every subgroup of G containing A ○ ⟨A⟩≔⋂8_█(H≤G@A⊆H)▒H • Example ○ If A=∅, then ⟨A⟩={1} ○ If A={1}, then ⟨A⟩={1}$

Math 521 – 2/23

$Theorem 2.19 • Statement ○ Every neighborhood is an open set • Proof ○ Let X be a metric space ○ Choose neighborhood N_r (p)=E∈X ○ Let q∈E ○ Choose h s.t. d(p,q)=r−h ○ Consider N_h(q) ○ So, if s∈N_h(q), d(q,s)h ○ d(p,s)≤d(p,q)+d(q,s)r−h+h=r ○ Thus d(p,s)r ○ i.e. s∈N_r (p) ○ So N_h(q)⊂N_r (p) ○ Therefore N_r (p) is open Theorem 2.20 • Statement ○ If p is a limit point of E, then ○ every neighborhood of p contains infinitely many points of E • Proof ○ Suppose the opposite ○ Then there exists a set E with a limit point p s.t. ○ The neighborhood of p contains only finitly many points of E ○ Namely q_1,q_2,…,q_n ○ Let r=min⁡(d(p,q_1 ),d(p,q_2 ),…,d(p,q_n )) ○ By definition, q_i∉N_r (p) for 1≤i≤n ○ This contradicts the fact that p is a limit point ○ So, this neighborhood about p must contain infinitely many points • Corollary ○ A finite set has no limit points Theorem 2.22 (De Morgan s Law) • Statement ○ Let {E_x } be a finite or infinite collection of sets, then ○ (⋃8_α▒E_α )^c=⋂8_α▒(E_α )^c • Proof ○ Suppose x∈(⋃8_α▒E_α )^c § Then x∉⋃8_α▒E_α § So x∉E_α for all α § Thus, x∈(E_α )^c for all α § So, x∈⋂8_α▒(E_α )^c § Therefore (⋃8_α▒E_α )^c⊂⋂8_α▒(E_α )^c ○ Suppose x∈⋂8_α▒(E_α )^c § Then x∈(E_α )^c for all α § So x∉E_α for all α § x∉⋃8_α▒E_α § Thus, x∈(⋃8_α▒E_α )^c § So ⋂8_α▒(E_α )^c ⊂(⋃8_α▒E_α )^c ○ Therefore (⋃8_α▒E_α )^c=⋂8_α▒(E_α )^c Theorem 2.23 • Statement ○ A set E is open if and only if E^c is closed ○ Note: This does not say that open is not closed and closed is not open • Proof ○ Suppose E^c is closed § Choose x∈E, so x∉E^c § So, x is not a limit point of E^c § So, there exists a neighborhood N_r (x) that contains no points of E^c § So, N_r (x)∩E^c=∅ § Consequently, N_r (x)⊂E § So, x is an interior point of E § By definition, E is open ○ Suppose E is open § Let x be a limit point of E^c (if exists) § So, every neighborhood of x contains a point in E^c § So, x is not an interior point of E § E is open, so x∈E^c § Thus, E^c contains its limit points and is closed by definition • Corollary ○ A set E is closed if and only if E^c is open Examples 2.21 • Let X=R2 Subset Closed Open Perfect Bounded {x ⃗∈R2│|x ⃗ |1} × ✓ × ✓ {x ⃗∈R2│|x ⃗ |≤1} ✓ × ✓ ✓ A nonempty finite set ✓ × × ✓ Z ✓ × × × {1/n│n∈N × × × ✓ R2 ✓ ✓ ✓ × (a,b) × ? × ✓ • Note: (a,b) is open as a subset of R, but not as a subtset of R2$

3.1 Algorithms

Algorithms • Definition ○ An algorithm is a finite set of precise instructions for performing a computation or for solving a problem. • Example: Describe an algorithm for finding the maximum value in a finite sequence of integers. ○ Perform the following steps: ○ Set the temporary maximum equal to the first integer in the sequence. ○ Compare the next integer in the sequence to the temporary maximum. § If it is larger than the temporary maximum, § set the temporary maximum equal to this integer. ○ Repeat the previous step if there are more integers. If not, stop. ○ When the algorithm terminates, the temporary maximum is the largest integer in the sequence. Specifying Algorithms • Algorithms can be specified in different ways. • Their steps can be described in English or in pseudocode. • Pseudocode is an intermediate step between an English language description of the steps and a coding of these steps using a programming language. • The form of pseudocode we use is specified in Appendix 3. • It uses some of the structures found in popular languages such as C++ and Java. • Programmers can use the description of an algorithm in pseudocode to construct a program in a particular language. • Pseudocode helps us analyze the time required to solve a problem using an algorithm, independent of the actual programming language used to implement algorithm. Properties of Algorithms • Input ○ An algorithm has input values from a specified set. • Output ○ From the input values, the algorithm produces the output values from a specified set. ○ The output values are the solution. • Correctness ○ An algorithm should produce the correct output values for each set of input values. • Finiteness ○ An algorithm should produce the output after a finite number of steps for any input. • Effectiveness ○ It must be possible to perform each step of the algorithm correctly and in a finite amount of time. • Generality ○ The algorithm should work for all problems of the desired form. Finding the Maximum Element in a Finite Sequence • The algorithm in pseudocode: • Does this algorithm have all the properties listed on the previous slide? Some Example Algorithm Problems • Three classes of problems will be studied in this section. • Searching Problems ○ finding the position of a particular element in a list. • Sorting problems ○ putting the elements of a list into increasing order. • Optimization Problems ○ determining the optimal value of a particular quantity over all possible inputs. Searching Problems • The general searching problem is to locate an element x in the list of distinct elements a_1,a_2,…,a_n, or determine that it is not in the list. • The solution to a searching problem is the location of the term in the list that equals x (that is, i is the solution if x=a_i) or 0 if x is not in the list. • For example, a library might want to check to see if a patron is on a list of those with overdue books before allowing him/her to checkout another book. • We will study two different searching algorithms; linear search and binary search. Linear Search Algorithm • The linear search algorithm locates an item in a list by examining elements in the sequence one at a time, starting at the beginning. • First compare x with a1. If they are equal, return the position 1. • If not, try a_2. If x=a_2, return the position 2. • Keep going, and if no match is found when the entire list is scanned, return 0. Binary Search • Assume the input is a list of items in increasing order. • The algorithm begins by comparing the element to be found with the middle element. ○ If the middle element is lower, the search proceeds with the upper half of the list. ○ If it is not lower, the search proceeds with the lower half of the list ○ Repeat this process until we have a list of size 1. ○ If the element we are looking for is equal to the element in the list, the position is returned. ○ Otherwise, 0 is returned to indicate that the element was not found. • In Section 3.3, we show that the binary search algorithm is much more efficient than linear search. • Here is a description of the binary search algorithm in pseudocode. Sorting • To sort the elements of a list is to put them in increasing order (numerical order, alphabetic, and so on). • Sorting is an important problem because: ○ A nontrivial percentage of all computing resources are devoted to sorting different kinds of lists, especially applications involving large databases of information that need to be presented in a particular order (e.g., by customer, part number etc.). ○ An amazing number of fundamentally different algorithms have been invented for sorting. Their relative advantages and disadvantages have been studied extensively. ○ Sorting algorithms are useful to illustrate the basic notions of computer science. • A variety of sorting algorithms are studied in this book; binary, insertion, bubble, selection, merge, quick, and tournament. • In Section 3.3, we’ll study the amount of time required to sort a list using the sorting algorithms covered in this section. Bubble Sort • Bubble sort makes multiple passes through a list. • Every pair of elements that are found to be out of order are interchanged. Insertion Sort • Insertion sort begins with the 2nd element. • It compares the 2nd element with the 1st and puts it before the first if it is not larger. • Next the 3rd element is put into the correct position among the first 3 elements. • In each subsequent pass, the (n+1)\-th element is put into its correct position among the first n+1 elements. • Linear search is used to find the correct position. Greedy Algorithms • Optimization problems minimize or maximize some parameter over all possible inputs. • Among the many optimization problems we will study are: ○ Finding a route between two cities with the smallest total mileage. ○ Determining how to encode messages using the fewest possible bits. ○ Finding the fiber links between network nodes using the least amount of fiber. • Optimization problems can often be solved using a greedy algorithm, which makes the “best” choice at each step. • Making the “best choice” at each step does not necessarily produce an optimal solution to the overall problem, but in many instances, it does. • After specifying what the “best choice” at each step is, we try to prove that this approach always produces an optimal solution, or find a counterexample to show that it does not. • The greedy approach to solving problems is an example of an algorithmic paradigm, which is a general approach for designing an algorithm. • We return to algorithmic paradigms in Section 3.3. Greedy Algorithms: Making Change • Example ○ Design a greedy algorithm for making change (in U.S. money) of n cents with the following coins § quarters (25 cents) § dimes (10 cents) § nickels (5 cents) § pennies (1 cent) ○ using the least total number of coins. • Idea ○ At each step choose the coin with the largest possible value that does not exceed the amount of change left. ○ If n = 67 cents, first choose a quarter leaving 67−25 = 42 cents. Then choose another quarter leaving 42 −25 = 17 cents ○ Then choose 1 dime, leaving 17 − 10 = 7 cents. ○ Choose 1 nickel, leaving 7 – 5 = 2 cents. ○ Choose a penny, leaving one cent. Choose another penny leaving 0 cents. • Solution ○ G reedy change-making algorithm for n cents. ○ The algorithm works with any coin denominations c_1, c_2, …,c_r. ○ For the example of U.S. currency, we may have quarters, dimes, nickels and pennies, with c_1=25, c_2=10, c_3=5, c_4=1. • Proving Optimality ○ Lemma 1 § If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies, using the fewest coins possible has at most 2 dimes, 1 nickel, 4 pennies, and cannot have 2 dimes and a nickel. § The total amount of change in dimes, nickels, and pennies must not exceed 24 cents. ○ Proof § If we had 3 dimes, we could replace them with a quarter and a nickel. § If we had 2 nickels, we could replace them with 1 dime. § If we had 5 pennies, we could replace them with a nickel. § If we had 2 dimes and 1 nickel, we could replace them with a quarter. § The allowable combinations, have a maximum value of 24 cents; 2 dimes and 4 pennies. ○ Theorem § The greedy change-making algorithm for U.S. coins produces change using the fewest coins possible. ○ Proof § Assume there is a positive integer n such that change can be made for n cents using quarters, dimes, nickels, and pennies, with a fewer total number of coins than given by the algorithm. § Then, q̍q where q̍ is the number of quarters used in this optimal way and q is the number of quarters in the greedy algorithm’s solution. § But this is not possible by Lemma 1, since the value of the coins other than quarters cannot be greater than 24 cents. § Similarly, by Lemma 1, the two algorithms must have the same number of dimes, nickels, and quarters. Halting Problem • Can we develop a procedure that takes as input a computer program along with its input and determines whether the program will eventually halt with that input. • Solution: Proof by contradiction. • Assume that there is such a procedure and call it H(P,I). • The procedure H(P,I) takes as input a program P and the input I to P. ○ H outputs “halt” if it is the case that P will stop when run with input I. ○ Otherwise, H outputs “loops forever.” • Since a program is a string of characters, we can call H(P,P). • Construct a procedure K(P), which works as follows. ○ If H(P,P) outputs “loops forever” then K(P) halts. ○ If H(P,P) outputs “halt” then K(P) goes into an infinite loop printing “ha” on each iteration. • Now we call K with K as input, i.e. K(K). ○ If the output of H(K,K) is “loops forever” then K(K) halts. A Contradiction. ○ If the output of H(K,K) is “halts” then K(K) loops forever. A Contradiction. • Therefore, there cannot be a procedure that can decide whether or not an arbitrary program halts. • The halting problem is unsolvable.

Math 541 – 2/21

$Cyclic Group • Definition ○ A group G is cyclic if ∃g∈G s.t. ⟨g⟩=G • Note ○ A finite group G of order n is cyclic iff ∃g∈G s.t. |g|=n • Example 1: Z is cyclic ○ Z=⟨1⟩ ○ Z=⟨−1⟩ • Example 2: Z\/nZ is cyclic ○ If (a,n)=1, Z\/nZ=⟨a ̅ ⟩ ○ (We will prove this later) • Example 3: S_3 is not cyclic ○ Note: If (a_1,…,a_t )∈S_n is a t-cycle, then |(a_1,…,a_t )|=t ○ S_3={(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2)} ○ Every element in S_3 have order 1,2, or 3 ○ So S_3 cannot be cyclic Proposition 18 • Let G be a cyclic group • If |G|=∞, then G≅Z ○ Choose g∈G s.t. G=⟨g⟩ ○ Define a map f:Z→G by n↦g^n ○ Check homomorphism § If n_1,n_2∈Z § then f(n_1+n_2 )=g^(n_1+n_2 )=g^(n_1 ) g^(n_2 )=f(n_1 )f(n_2 ) § Thus, f is a homomorphism ○ Check surjectivity § Surjectivity is clear ○ Check injectivity § Suppose f(n_1 )=f(n_2 ) § Then g^(n_1 )=g^(n_2 ) § Without loss of generality, assume n_1≥n_2 § Then g^(n_1−n_2 )=1 § Since |g|=∞ § n_1−n_2=0 § i.e. n_1=n_2 § Thus f is injective • If |G|=n ∞, then G≅Z\/nZ ○ Choose g∈G s.t. G=⟨g⟩ ○ Define a map f:Z\/nZ→G by a ̅↦g^a ○ Check well-definedness § We need to check that f is well-defined. § That is we must show that if a ̅=b ̅ in Z\/nZ, then f(a ̅ )=f(b ̅ ) § Let a,b∈Z, suppose a ̅=b ̅ in Z\/nZ § Choose q∈Z s,t, nq=a−b § f(a ̅ )=g^a=g^(nq+b)=g^nq g^b=g^b=f(b ̅ ) § Thus, f is well-defined ○ Check homomorphism § f(a ̅+b ̅ )=g^(a+b)=g^a g^b=f(a ̅ )f(b ̅ ) § Thus, f is a homomorphism ○ Check surjectivity § Surjectivity is clear ○ Check injectivity § If f(a ̅ )=f(b ̅ ) § g^a=g^b § g^(a−b)=1 § ├ |g|┤|├ (a−b)┤ § n|(a−b) § a ̅=b ̅ § Thus f is injective Least Common Multiple • Definition ○ Let a,b∈Z where one of a,b is nonzero. ○ A least common multiple of a and b is a positive integer m s.t. § a|m and b|m § If a|m′ and b|m′, then m|m^′ ○ We denote the lcm of a and b by [a,b] ○ Define [0,0]≔0 • Uniqueness ○ Similar to the proof of uniqueness of gcd • Existence: If a,b∈Z, and one of a,b is nonzero, then ab/((a,b) ) is the lcm of a,b ○ ab/((a,b) ) is a multiple of a and b ○ Suppose m^′∈Z s.t. a|m′ and b|m′ ○ We must show ├ ab/((a,b) )┤|├ m′┤ ○ Choose q,q^′∈Z s,t, aq=m′ and bq^′=m′ ○ Choose x,y∈Z s.t. ax+by=(a,b) ○ m^′ (a,b)=m^′ (ax+by)=m^′ ax+m^′ by=bq^′ ax+aqby=ab(q^′ x+qy) ○ Thus ab|(m^′ (a,b)) ○ i.e. ab/((a,b) )=m^′ Proposition 19 • Statement ○ If G=⟨g⟩ is cyclic, and |G|=n ∞, then |g^a |=n/((a,n) ) • Proof ○ Let a∈Z ○ If a=0, this is clear ○ So, assume a≠0 ○ (g^a )^(n/((a,n) ))=g^(an/((a,n) ))=g^[a,n] =g^kn for some integer k ○ Thus, (g^a )^(n/((a,n) ))=(g^n )^k=1 since n=|g| ○ Suppose t∈Z( 0) and (g^a )^t=1 ○ By HW3, g^at=1⇒n|at ○ Thus, at is a common multiple of n and a ○ ├ [a,n]┤|├ at┤ ○ ⇒├ an/((a,n) )┤|├ at┤ ○ ⇒├ n/((a,n) )┤|├ t┤ ○ In particular, n/((a,b) )≤t Theorem 20 • Let G=⟨g⟩ be a cyclic group • Statement (1) ○ Every subgroup of G is cyclic ○ More precisely, if H≤G, then either H={1} or ○ H=⟨g^d ⟩, where d is the smallest positive integer s.t. g^d∈H • Statement (2) ○ If G is finite, then for all positive integers a dividing n ○ ∃! subgroup H≤G of order a. ○ Moreover, this subgroup is ⟨g^d ⟩, where d=n/a$

Mathematics

Math 541 – 2/26

Math 541 – 2/23

Math 521 – 2/23

3.1 Algorithms

Math 541 – 2/21

Search

WeChat Account