Notes Archives - Page 24 of 84 - Shawn Zhong

5.1 Mathematical Induction

$Climbing an Infinite Ladder • Suppose we have an infinite ladder: ○ We can reach the first rung of the ladder. ○ If we can reach a particular rung of the ladder ○ then we can reach the next rung. • From (1), we can reach the first rung. • Then by applying (2), we can reach the second rung. • Applying (2) again, the third rung. And so on. • We can apply (2) any number of times to reach any particular rung, no matter how high up. Principle of Mathematical Induction • To prove that P(n) is true for all positive integers n, we complete these steps: ○ Basis Step: Show that P(1) is true. ○ Inductive Step: Show that P(k)→P(k+1) is true for all positive integers k • To complete the inductive step ○ assuming the inductive hypothesis that P(k) holds for an arbitrary integer k ○ show that must P(k+1) be true. • Climbing an Infinite Ladder Example: ○ Basis Step § By (1), we can reach rung 1. ○ Inductive Step § Assume the inductive hypothesis that we can reach rung k § Then by (2), we can reach rung k+1. ○ Hence, P(k)→P(k+1) is true for all positive integers k ○ We can reach every rung on the ladder. Important Points About Using Mathematical Induction • Mathematical induction can be expressed as the rule of inference ○ (P(1)∧∀k(P(k)→P(k+1)))→∀n P(n) ○ where the domain is the set of positive integers. • In mathematical induction, we don’t assume that P(k) is true for all positive integers! • We show that if we assume that P(k) is true, then P(k+1) must also be true. • Proofs by mathematical induction do not always start at the integer 1. • In such a case, the basis step begins at a starting point b where b is an integer. • We will see examples of this soon. Proving a Summation Formula by Mathematical Induction • Example ○ Show that:∑_(i=1)^n▒i=n(n+1)/2 • Solution ○ Basis Step § P(1) is true since 1(1+1)/2=1 ○ Inductive Step § Assume true for P(k) § The inductive hypothesis is ∑_(i=1)^k▒i=k(k+1)/2 § Under this assumption § 1+2+…+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2 Validity of Mathematical Induction • Mathematical induction is valid because of the well ordering property, which states that • every nonempty subset of the set of positive integers has a least element • Suppose that P(1) holds and P(k)→P(k+1) is true for all positive integers k. • Assume there is at least one positive integer n for which P(n) is false. • Then the set S of positive integers for which P(n) is false is nonempty. • By the well-ordering property, S has a least element, say m. • We know that m cannot be 1 since P(1) holds. • Since m is positive and greater than 1, m−1 must be a positive integer. • Since m−1 m, it is not in S, so P(m−1) must be true. • But then, since the conditional P(k)→P(k+1) for every positive integer k holds, • P(m) must also be true. This contradicts P(m) being false. • Hence, P(n) must be true for every positive integer n. Conjecturing and Proving Correct a Summation Formula • Example ○ Conjecture and prove correct a formula for the sum of the first n positive odd integers ○ Then prove your conjecture • Solution ○ We have § 1= 1 § 1 + 3 = 4 § 1 + 3 + 5 = 9 § 1 + 3 + 5 + 7 = 16 § 1 + 3 + 5 + 7 + 9 = 25. ○ We can conjecture that the sum of the first n positive odd integers is n^2, § 1+3+5+…+(2n−1)+(2n+1)=n^2 ○ We prove the conjecture is proved correct with mathematical induction. ○ Basis Step § P(1) is true since 1^2 = 1. ○ Inductive Step: P(k)→P(k+1) for every positive integer k. § Inductive Hypothesis: 1+3+5+…+(2k−1)=k^2 § So, assuming P(k), it follows that: § 1+3+5+…+(2k−1)+(2k+1) § =[1+3+5+…+(2k−1)]+(2k+1) § =k^2+(2k+1) § =(k+1)^2 ○ Hence, we have shown that P(k+1) follows from P(k). ○ Therefore the sum of the first n positive odd integers is n^2 Proving Inequalities • Example ○ Use mathematical induction to prove that n 2^n for all positive integers n. • Solution ○ Let P(n) be the proposition that n 2^n. ○ Basis Step § P(1) is true since 1 2^1 = 2. ○ Inductive Step § Assume P(k) holds, i.e., k 2^k, for an arbitrary positive integer k. § Must show that P(k + 1) holds. § Since by the inductive hypothesis, k 2^k, it follows that: § k+1 2^k+1≤2^k+2^k=2⋅2^k=2^(k+1) § Therefore n 2^n holds for all positive integers n. • Example ○ Use mathematical induction to prove that 2^n n!, for every integer n≥4 • Solution ○ Let P(n) be the proposition that 2^n n! ○ Basis Step § P(4) is true since 24 = 16 4! = 24 ○ Inductive Step § Assume P(k) holds, i.e., 2^k k! for an arbitrary integer k ≥ 4. § To show that P(k+1) holds § 2^(k+1)=2∙2^k 2⋅2^k (k+1)k!=(k+1)! § Therefore, 2^n n! holds, for every integer n ≥ 4 Proving Divisibility Results • Example ○ Use mathematical induction to prove that n^3−n is divisible by 3 ○ for every positive integer n. • Solution ○ Let P(n) be the proposition that n^3−n is divisible by 3. ○ Basis Step § P(1) is true since 13 − 1 = 0, which is divisible by 3 ○ Inductive Step § Assume P(k) holds, i.e., k^3−k is divisible by 3, for an arbitrary positive integer k § To show that P(k + 1) follows § (k+1)^3−(k+1)=(k^3+3k^2+3k+1)−(k+1)=(k^3−k)+3(k^2+k) § By the inductive hypothesis, the first term (k^3−k) is divisible by 3 § and the second term is divisible by 3 since it is an integer multiplied by 3. § So by part (i) of Theorem 1 in Section 4.1, (k+1)^3−(k+1) is divisible by 3 ○ Therefore, n^3−n is divisible by 3, for every integer positive integer n. Number of Subsets of a Finite Set • Example ○ Use mathematical induction to show that if S is a finite set with n elements ○ where n is a nonnegative integer, then S has 2^n subsets. ○ (Chapter 6 uses combinatorial methods to prove this result.) • Solution ○ Let P(n) be the proposition that a set with n elements has 2^n subsets. ○ Basis Step § P(0) is true, because the empty set has only itself as a subset and 2^0 = 1. ○ Inductive Step § Assume P(k) is true for an arbitrary nonnegative integer k. § Inductive Hypothesis § For an arbitrary nonnegative integer k, every set with k elements has 2^k subsets § Let T be a set with k+1 elements § Then T=S∪{a}, where a∈T and S=T−{a}. Hence |S| = k. § For each subset X of S, there are exactly two subsets of T, i.e., X and X∪{a}. § By the inductive hypothesis S has 2^k subsets. § Since there are two subsets of T for each subset of S, § the number of subsets of T is 2⋅2^k=2^(k+1) An Incorrect “Proof” by Mathematical Induction • P(n)≔every set of n lines in the plane, no two of which are parallel, meet in a point • Here is a “proof” that P(n) is true for all positive integers n≥2. • Basis Step ○ The statement P(2) is true ○ because any two lines in the plane that are not parallel meet in a common point. • Inductive hypothesis ○ P(k) is true for the positive integer k ≥ 2 ○ every set of k lines in the plane, no two of which are parallel, meet in a common point. • Inductive Step ○ We must show that if P(k) holds, then P(k+1) holds ○ If every set of k lines in the plane, no two of which are parallel, k ≥ 2, meet in a point ○ Then every set of k+1 lines in the plane, no two of which are parallel, meet in a point. ○ Consider a set of k + 1 distinct lines in the plane, no two parallel. ○ By the inductive hypothesis, the first k of these lines must meet in a common point p_1. ○ By the inductive hypothesis, the last k of these lines meet in a common point p_2. ○ If p_1 and p_2 are different points, all lines containing both of them must be the same line since two points determine a line. ○ This contradicts the assumption that the lines are distinct. ○ Hence, p_1=p_2 lies on all k + 1 distinct lines, and therefore P(k+1) holds. ○ Assuming that k ≥ 2, distinct lines meet in a common point ○ Then every k + 1 lines meet in a common point. • There must be an error in this proof since the conclusion is absurd. But where is the error? ○ P(k)→P(k+1) only holds for k≥3 ○ It is not the case that P(2) implies P(3) ○ The first two lines must meet in a common point p_1 and the second two must meet in a common point p_2 ○ They do not have to be the same point since only the second line is common to both sets of lines.$

Math 521 – 3/12

$Theorem 2.34 • Statement ○ Compact subsets of metric spaces are closed • Proof ○ Let K be a compact subset of a metric space X ○ We shall prove that the complement of K is open ○ Let p∈K^c, q∈K ○ Let V_q=N_r (p),W_q=N_s (q) where r,s 1/2 d(p,q) ○ Since K is compact, ∃q_1,q_2,…q_n∈K s.t. ○ K⊂W_(q_1 )∪W_(q_2 )∪…∪W_(q_n )=W ○ Let V=V_(q_1 )∩V_(q_2 )∩…∩V_(q_n ) ○ Then V is a neighborhood of p that does not intersect W ○ V⊂K^c⇒p is an interior point of K^c ○ So K^c is open and therefore K is closed Theorem 2.35 • Statement ○ Closed subsets of compact sets are compact • Proof ○ Let X be a metric space ○ Suppose F⊂K⊂X, where F is closed, and K is compact ○ Let {V_α } be an open cover of F ○ Consider {V_α }∪{F^c }, where F^c is open ○ Then {V_α }∪{F^c } is an open cover of K ○ Since K is compact, K has a finite subcover Φ ○ If F^c∈Φ, then Φ∖{F^c } is still finite and covers F ○ So we have a finite subcover of {V_α } ○ Therefore F is compact • Corollary ○ If F is closed and K is compact , then F∩K is compact • Proof ○ K compact ⇒K is closed ○ We know F is closed, so F∩K is closed ○ F∩K⊂K, and K is compact ○ So F∩K is compact Theorem 2.36 (Cantor s Intersection Theorem) • Statement ○ If {K_α } is a collection of compact subsets of a metric space X s.t. ○ The intersection of every finite subcollection of {K_α } is nonempty ○ Then ⋂_α▒K_α is nonempty • Proof ○ Fix K_1∈{K_α } and let G_α=K_α^c \,∀α ○ Assume no point of K_1 belongs to every K_α ○ Then {G_α } is an open cover of K_1 ○ Since K_1 is compact, K_1⊂G_(α_1 )∩G_(α_2 )∩…∩G_(α_n ) ○ Where α_1,α_2,…,α_n is a finite collection of indices ○ Then K_1∩G_(α_2 )∩…∩G_(α_n )=∅ ○ This is a contradiction, so no such set K_1 exists ○ The result follows • Corollary ○ If {K_n } is a sequence of nonempty compact sets s.t. K_n⊃K_(n+1),∀n∈N ○ Then ⋂24_(n=1)^∞▒K_n is nonempty Theorem 2.37 • Statement ○ If E is an infinite subset of a compact set K ○ Then E has a limit point in K • Proof ○ If no point of K were a limit point of E ○ Then ∀q∈K, ∃N(q) s.t. no point of E other than q ○ i.e. N(q) contains at most one point of E (namely, q, if q∈E) ○ So no finite sub-collection of {N(q)} can cover E, and thus not K ○ This is a contradiction, so E has a limit point in K$

4.4 Solving Congruences

Linear Congruences • Definition ○ A congruence of the form ax≡b (mod m), ○ where m is a positive integer, a and b are integers, and x is a variable ○ is called a linear congruence. ○ The solutions to a linear congruence ax≡b (mod m) are ○ all integers x that satisfy the congruence. • Definition ○ An integer ā such that āa≡1 (mod m) is said to be an inverse of a modulo m. • Example ○ 5 is an inverse of 3 modulo 7 since 5∙3=15≡1 (mod 7) • One method of solving linear congruences makes use of an inverse ā, if it exists. • Although we can not divide both sides of the congruence by a • we can multiply by ā to solve for x. Inverse of a modulo m • The following theorem guarantees that • an inverse of a modulo m exists whenever a and m are relatively prime. • Two integers a and b are relatively prime when gcd(a,b) = 1. • Theorem 1 ○ If a and m are relatively prime integers and m 1, then an inverse of a modulo m exists. ○ Furthermore, this inverse is unique modulo m. ○ So, there is a unique positive integer ā less than m that is an inverse of a modulo m ○ And every other inverse of a modulo m is congruent to ā modulo m • Proof ○ Since gcd(a,m) = 1 ○ By Theorem 6 of Section 4.3, there are integers s and t such that sa + tm = 1. ○ Hence, sa + tm ≡ 1 (mod m). ○ Since tm ≡ 0 (mod m), it follows that sa ≡ 1 (mod m) ○ Consequently, s is an inverse of a modulo m. ○ The uniqueness of the inverse is Exercise 7. Finding Inverses • The Euclidean algorithm and Bézout coefficients gives us • a systematic approaches to finding inverses. • Find an inverse of 3 modulo 7. ○ Because gcd(3,7) = 1, by Theorem 1, an inverse of 3 modulo 7 exists. ○ Using the Euclidian algorithm: 7 = 2∙3 + 1. ○ From this equation, we get −2∙3 + 1∙7 = 1 ○ and see that −2 and 1 are Bézout coefficients of 3 and 7. ○ Hence, −2 is an inverse of 3 modulo 7. ○ Also every integer congruent to −2 modulo 7 is an inverse of 3 modulo 7 ○ i.e., 5, −9, 12, etc. • Find an inverse of 101 modulo 42620. ○ First use the Euclidian algorithm to show that gcd(101,42620) = 1. § 42620 = 45∙101 + 75 § 101 = 1∙75 + 26 § 75 = 2∙26 + 23 § 26 = 1∙23 + 3 § 23 = 7∙3 + 2 § 3 = 1∙2 + 1 § 2 = 2∙1 ○ Working Backwards § 1 = 3 − 1 ∙ 2 § 1 = 3 − 1 ∙ (23 − 7∙3) = − 1 ∙ 23 + 8 ∙ 3 § 1 = −1 ∙ 23 + 8 ∙ (26 − 1 ∙ 23) = 8 ∙ 26 − 9 ∙ 23 § 1 = 8 ∙26 − 9 ∙ (75 − 2 ∙ 26)= 26 ∙ 26 − 9 ∙ 75 § 1 = 26 ∙ (101 − 1∙75) − 9 ∙75 = 26 ∙ 101 − 35 ∙ 75 § 1 = 26 ∙ 101 − 35 ∙ (42620 − 45 ∙ 101) = − 35 ∙ 42620 + 1601 ∙ 101 ○ Bézout coefficients : − 35 and 1601 ○ Therefore 1601 is an inverse of 101 modulo 42620 Using Inverses to Solve Congruences • We can solve the congruence ax≡b (mod m) by multiplying both sides by ā. • What are the solutions of the congruence 3x ≡ 4 (mod 7). ○ We found that −2 is an inverse of 3 modulo 7 (two slides back). ○ We multiply both sides of the congruence by −2 giving ○ −2 ∙ 3x ≡ −2 ∙ 4(mod 7). ○ Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7) ○ It follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7) ○ We need to determine if every x with x ≡ 6 (mod 7) is a solution. ○ Assume that x ≡ 6 (mod 7). ○ By Theorem 5 of Section 4.1, it follows that 3x ≡ 3 ∙ 6 = 18 ≡ 4 (mod 7) ○ which shows that all such x satisfy the congruence. ○ The solutions are the integers x such that x ≡ 6 (mod 7) ○ Namely, 6,13,20… and −1, − 8, − 15, … The Chinese Remainder Theorem • In the first century, the Chinese mathematician Sun-Tsu asked: ○ There are certain things whose number is unknown. ○ When divided by 3, the remainder is 2 ○ When divided by 5, the remainder is 3 ○ When divided by 7, the remainder is 2. ○ What will be the number of things? • This puzzle can be translated into the solution of the system of congruences: ○ x ≡ 2 (mod 3) ○ x ≡ 3 (mod 5) ○ x ≡ 2 (mod 7) • Theorem 2: (The Chinese Remainder Theorem) ○ Let m_1,m_2,…,m_n be pairwise relatively prime positive integers greater than one ○ Let a_1,a_2,…,a_n be arbitrary integers. ○ Then the system § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) ○ has a unique solution modulo m=m_1 m_2⋯m_n. ○ That is, there is a solution x with 0≤x m ○ and all other solutions are congruent modulo m to this solution. • Proof ○ We’ll show that a solution exists by describing a way to construct the solution. ○ Showing that the solution is unique modulo m is Exercise 30. • Algorithm ○ To construct a solution first let M_k=m/m_k for k=1,2,…,n and m=m_1 m_2,…,m_n ○ Since gcd(m_k,M_k) = 1, there is an integer y_k, an inverse of M_k modulo m_k, such that § M_k y_k≡1 (mod m_k ) ○ Form the sum § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 ○ Note that because M_j ≡ 0 (mod m_k) whenever j≠k ○ all terms except the kth term in this sum are congruent to 0 modulo m_k . ○ Because M_k y_k ≡ 1 (mod m_k), we see that x ≡ a_k M_K y_k ≡ a_k (mod m_k), for k = 1,2,…,n. ○ Hence, x is a simultaneous solution to the n congruences. § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) • Example ○ Consider the 3 congruences from Sun-Tsu’s problem: § x ≡ 2 (mod 3) § x ≡ 3 (mod 5) § x ≡ 2 (mod 7) ○ Let § m = 3∙ 5 ∙ 7 = 105 § M_1=m/3=35 § M_2=m/5=21 § M_3=m/7=15 ○ We see that § y_1= 2 is an inverse of M_1 = 35 modulo 3 since 35 ∙ 2 ≡ 2 ∙ 2 ≡ 1 (mod 3) § y_2= 1 is an inverse of M_2 = 21 modulo 5 since 21 ≡ 1 (mod 5) § y_3= 1 is an inverse of M_3 = 15 modulo 7 since 15 ≡ 1 (mod 7) ○ Hence, § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 § = 2 ∙ 35 ∙ 2 + 3 ∙ 21 ∙ 1 + 2 ∙ 15 ∙ 1 = 233 ≡ 23 (mod 105) ○ We have shown that 23 is the smallest positive integer that is a simultaneous solution. • Back Substitution ○ We can also solve systems of linear congruences with pairwise relatively prime moduli ○ by rewriting a congruences as an equality using Theorem 4 in Section 4.1 ○ substituting the value for the variable into another congruence, ○ and continuing the process until we have worked through all the congruences. ○ This method is known as back substitution. • Example ○ Use the method of back substitution to find all integers x such that § x ≡ 1 (mod 5) § x ≡ 2 (mod 6) § x ≡ 3 (mod 7). ○ By Theorem 4, the first congruence can be rewritten as x = 5t +1, where t is an integer. ○ Substituting into the second congruence yields 5t +1 ≡ 2 (mod 6). ○ Solving this tells us that t ≡ 5 (mod 6). ○ Using Theorem 4 again gives t = 6u + 5 where u is an integer. ○ Substituting this back into x = 5t +1, gives x = 5(6u + 5) +1 = 30u + 26. ○ Inserting this into the third equation gives 30u + 26 ≡ 3 (mod 7). ○ Solving this congruence tells us that u ≡ 6 (mod 7). ○ By Theorem 4, u = 7v + 6, where v is an integer. ○ Substituting this expression for u into x = 30u + 26 ○ tells us that x = 30(7v + 6) + 26 = 210v + 206. ○ Translating this back into a congruence we find the solution x ≡ 206 (mod 210) Fermat’s Little Theorem • Theorem 3: (Fermat’s Little Theorem) ○ If p is prime and a is an integer not divisible by p, then a^(p−1) ≡ 1 (mod p) ○ Furthermore, for every integer a we have a^p ≡ a (mod p) • This is useful in computing the remainders modulo p of large powers of integers. • Find 7^222 mod 11. ○ By Fermat’s little theorem, we know that 7^10 ≡ 1 (mod 11) ○ and so (7^10 )^k ≡ 1 (mod 11), for every positive integer k ○ Therefore, 7^222 = 7^(22×10+2)=(7^10 )^22×7^2 ≡ 1^22×49 ≡ 5 (mod 11). ○ Hence, 7^222 mod 11 = 5. Pseudoprimes • By Fermat’s little theorem n 2 is prime, where ○ 2^(n−1) ≡ 1 (mod n). • But if this congruence holds, n may not be prime. • Composite integers n such that 2^(n−1) ≡ 1 (mod n) are called pseudoprimes to the base 2. • Example: The integer 341 is a pseudoprime to the base 2. ○ 341 = 11 ∙ 31 ○ 2^340 ≡ 1 (mod 341) (see in Exercise 37) ○ We can replace 2 by any integer b ≥ 2. • Definition ○ Let b be a positive integer. ○ If n is a composite integer, and b^(n−1) ≡ 1 (mod n) ○ then n is called a pseudoprime to the base b • Given a positive integer n, such that 2^(n−1) ≡ 1 (mod n): ○ If n does not satisfy the congruence, it is composite. ○ If n does satisfy the congruence, it is either prime or a pseudoprime to the base 2. • Doing similar tests with additional bases b, provides more evidence as to whether n is prime. • Among the positive integers not exceeding a positive real number x, compared to primes • there are relatively few pseudoprimes to the base b. • For example, among the positive integers less than 〖10〗^10 there are 455,052,512 primes • but only 14,884 pseudoprimes to the base 2 Primitive Roots • Definition ○ A primitive root modulo a prime p is an integer r in Zp such that ○ every nonzero element of Zp is a power of r • Example ○ Since every element of Z11 is a power of 2, 2 is a primitive root of 11. ○ Powers of 2 modulo 11 § 2^1=2 § 2^2=4 § 2^3=8 § 2^4=5 § 2^5=10 § 2^6=9 § 2^7=7 § 2^8=3 § 2^9=6 § 2^10=1 • Example ○ Since not all elements of Z11 are powers of 3, 3 is not a primitive root of 11. ○ Powers of 3 modulo 11 § 3^1=3 § 3^2=9 § 3^3=5 § 3^4=4 § 3^5=1 § and the pattern repeats for higher powers. • Important Fact ○ There is a primitive root modulo p for every prime number p Discrete Logarithms • Suppose p is prime and r is a primitive root modulo p. • If a is an integer between 1 and p −1, that is an element of Zp, • there is a unique exponent e such that r^e = a in Zp, that is, r^e mod p = a. • Definition ○ Suppose p is prime ○ r is a primitive root modulo p ○ and a is an integer between 1 and p −1, inclusive. ○ If r^3 mod p = a and 1 ≤ e ≤ p − 1 ○ We say that e is the discrete logarithm of a modulo p to the base r and we write log_r⁡a=e • Example 1 ○ We write log_2⁡3=8 ○ Since the discrete logarithm of 3 modulo 11 to the base 2 is 8 as 28 = 3 modulo 11. • Example 2 ○ We write log_2⁡5=4 ○ since the discrete logarithm of 5 modulo 11 to the base 2 is 4 as 24 = 5 modulo 11. • There is no known polynomial time algorithm for computing the discrete logarithm • The problem plays a role in cryptography as will be discussed in Section 4.6.

Math 541 – 3/12

$Theorem 35 (The Third Isomorphism Theorem) • Statement ○ Let G be a group, and H,K⊴G, where H≤K ○ Then K\/H⊴G\/H, and (G/H)⁄(K/H)≅G\/K • Note ○ K\/H≔{gH∈G/H│g∈K} ○ Also, H⊴G⇒H⊴K, and so K\/H makes sense • Recall: First Isomorphism Theorem ○ Given a homomorphism f:G→H ○ Then f ̅:G⁄ker⁡f ⟶┴≅ im(f) ○ In particular, if f is surjective, then G⁄ker⁡f ≅H • Proof ○ Check that K\/H≤G\/H § Certainly K\/H≠∅ since K≠∅ § Let k_1 H,k_2 H∈K\/H § Then k_1 H(k_2 H)^(−1)=k_1 Hk_2^(−1) H=k_1 k_2^(−1) H∈K\/H ○ Next, we show K\/H⊴G\/H § Let kH∈K\/H and gH∈G\/H § Then gHkH(gH)^(−1)=(⏟(gkg^(−1) ) H)┬(∈K)∈K\/H ○ Define a homomorphism § α:G\/H→G\/K gH↦gK ○ α is well-defined § Suppose g_1 H=g_2 H § Then g_2^(−1) g_1∈H § ⇒g_2^(−1) g_1∈K⟺g_1 K=g_2 K ○ α is surjective § If gK∈G\/K, α(gH)=gK ○ Compute ker⁡α § ker⁡α={gH∈G/H│gK=K} § ={gH∈G/H│g∈K} § =K\/H ○ By First Isomorphism Theorem § (G/H)⁄(K/H)=(G/H)⁄ker⁡α ≅im α=G\/K • Example ○ Let G=Z, K=⟨2⟩, H=⟨4⟩ ○ Then The Third Isomorphism Theorem tells us the map § Z\/4Z→Z\/2Z § a ̅→a ̅ ○ is well-defined and surjective ○ with kernel 2Z\/4Z={0 ̅,2 ̅ }⊆Z\/4Z ○ Therefore, (Z4Z⁄(2Z4Z≅Z\/2Z Proposition 36 • Statement ○ Let G,H be groups, and N⊴G ○ A homomorphism α:G→H induces a homomorphism § α ̅:G\/N→H gN↦α(g) ○ If and only if N≤ker⁡α • Proof (⟹) ○ α ̅(nN)=1_H, ∀n∈N, since homomorphisms preserve identities ○ But, α ̅(nN)=α(n) ○ Thus, α(n)=1_H,∀n∈N ○ i.e. N⊆ker⁡α ○ And N certainly meets the Subgroup Criteria ○ Therefore N≤ker⁡α • Proof (⟸) ○ We must check that α ̅:G\/N→H,gN↦α(g) is well-defined § Suppose g_1 N=g_2 N, we must check that α(g_1 )=α(g_2 ) § g_1 N=g_2 N § ⟺g_2^(−1) g_1∈N § ⇒α(g_2^(−1) g_1 )=1_H (since N≤ker⁡α) § ⟺α(g_2 )^(−1) α(g_1 )=1_H § ⟺α(g_2 )=α(g_1 ) ○ Also, α ̅ is a homomorphism § α ̅(g_1 Hg_2 H)=α ̅(g_1 g_2 H)=α(g_1 g_2 )=α(g_1 )α(g_2 )=α ̅(g_1 H) α ̅(g_2 H)$

Math 541 – 3/9

$Corollary 31 • Recall (Proposition 30) ○ If H,K≤G, then HK≤G⟺HK=KH • Statement ○ If H,K≤G, and either H or K is normal in G, then HK≤G • Proof ○ Without loss of generality, assume K⊴G ○ We will prove HK=KH ○ Let h∈H,k∈K ○ hk=hk(h(−1) h=⏟(h�h(−1) )┬(∈K) h∈KH⇒HK≤KH ○ kh=(h^(−1) )kh=h ⏟(h(−1) kh┬(∈K)∈HK⇒KH≤HK ○ Therefore HK=KH Theorem 32 (The First Isomorphism Theorem) • Statement ○ If f:G→H is a hormorphism, then f induces an isomorphism § f ̅:G⁄ker⁡f ⟶┴≅ im(f) § f ̅(g ker⁡f )=f(g) • Intuition ○ This is an analogue of the Rank-Nullity Theorem ○ Given vector space V,W and a linear transformation A:V→W ○ dim⁡(V⁄ker⁡A )=dim⁡〖im A〗 ○ ⇒dim⁡V−nullity A=rank A • Proof ○ f ̅ is well-defined and injective § Let g_1,g_2∈G § g_1 ker⁡f=g_2 ker⁡f § ⟺g_2^(−1) g_1∈ker⁡f § ⟺f(g_2^(−1) g_1 )=1 § ⟺f(g_2 )^(−1) f(g_1 )=1 § ⟺f(g_1 )=f(g_2 ) § ⟺f ̅(g_1 ker⁡f )=f ̅(g_2 ker⁡f ) § Thus f is well-defined and injective ○ f ̅ is surjective § Let h∈im f § Choose g∈G s.t. f(g)=h § Notice f ̅(g ker⁡f )=h ○ f ̅ is a hormorphism § If g_1 ker⁡f,g_2 ker⁡f∈G\/ker⁡f § f ̅(g_1 ker⁡f⋅g_2 ker⁡f ) § =f ̅(g_1 g_2 ker⁡f ) § =f(g_1 g_2 )=f(g_1 )f(g_2 ) § =f ̅(g_1 ker⁡f ) f ̅(g_2 ker⁡f ) § Thus, f ̅ is a hormorphism Corollary 33 • Statement ○ [G:ker⁡f ]=|im f| • Example ○ Let m,n∈Z, and assume (m,n)=1 ○ Then any homomorphism f:Z\/mZ→Z\/nZ is trivial ○ i.e. f(n ̅ )=0 ̅, ∀n ̅ • Proof ○ Let f be such a homomorphism ○ By the First Isomorphism Theorem ○ |(ZnZ⁄ker⁡f |=|im f| ○ ⇒n/|ker⁡f | =|im f|, where § n/|ker⁡f | is a divisor of n § |im f| is a divisor of m by Lagrange^′ s Theorem ○ Thus, |im f|=1, so im f={0 ̅ } • Note ○ The same proof tells us that ○ If G,H are finite groups such (|G|,|H|)=1, then ○ All homomorphism between them are trivial Theorem 34 (The Second Isomorphism Theorem) • Statement ○ Let A,B≤G, and assume B⊴G ○ Then A∩B⊴A, and AB⁄B≅A⁄(A∩B) • Intuition • Note ○ By Corollary 31, AB≤G ○ And since B⊴G, B⊴AB ○ So, AB⁄B make sense • Proof ○ We have homomorphisms § α:A→AB a↦a § β:AB→AB⁄B x↦xB ○ Set f≔βα, so § f:A→AB⁄B a↦aB ○ f(a)=1_(AB⁄B)=B⟺a∈B ○ Thus, ker⁡f=A∩B ○ Since kernels are normal, A∩B⊴A ○ The First Isomorphism Theorem gives an isomorphism ○ f ̅:A⁄(A∩B) ⟶┴≅ AB⁄B$

Shawn Zhong

Shawn Zhong

Notes

5.1 Mathematical Induction

Math 521 – 3/12

4.4 Solving Congruences

Math 541 – 3/12

Math 541 – 3/9

Search

WeChat Account