Onetone Blog

Math 521 – 3/21

$Theorem 3.11 • Statement (a) ○ In any metric space X, every convergent sequence is a Cauchy sequence • Proof (a) ○ Suppose p_n→p ○ Let ε 0,then ∃N∈N s.t. d(p,p_n ) ε/2, ∀n≥N ○ d(p_n,p_m )≤d(p,p_n )+d(p,p_m ) ε/2+ε/2=ε, ∀n,m≥N ○ So {p_n } is a Cauchy sequence • Statement (b) ○ If X is a compact metric space and {p_n } is a Cahchy sequence ○ Then {p_n } converges to some point of X • Proof (b) ○ Let {p_n } be a Cauchy sequenec in compact metric space X ○ For N∈N, let E_N={p_N,p_(N+1),…} ○ By Theorem 3.10,lim_(N→∞)⁡〖diam (E_N ) ̅ 〗=lim_(N→∞)⁡〖diam E_N 〗=0 ○ By Theorem 2.35, (E_N ) ̅ as closed subset of X is compact ○ Since E_(N+1)⊂E_N, (E_(N+1) ) ̅⊂(E_N ) ̅,∀N∈N ○ By Theorem 3.10 (b), ∃!p∈X s.t. p∈(E_N ) ̅, ∀N∈N ○ Let ε 0 be given,∃N_0∈N s.t. diam (E_N ) ̅ ε,∀N≥N_0 ○ Since p∈(E_N ) ̅,d(p,q) ε,∀q∈E_N={p_N,p_(N+1),…}⊂(E_N ) ̅ ○ In other word, d(p,p_n ) ε for n≥N_0 ○ So lim_(n→∞)⁡〖p_n 〗=p • Statement (c) ○ In Rk, every Cauchy sequence converges • Proof (c) ○ Let {(x_n ) ⃗ } be a Cauchy sequence in Rk ○ Let E_N={(x_N ) ⃗,(x_(N+1) ) ⃗,…} ○ For some N∈N,diam E_N 1 ○ Then the range of {(x_n ) ⃗ } is {(x_1 ) ⃗,…,(x_(N−1) ) ⃗ }∪E_N ○ By Theorem 2.41, every bounded subset of Rk has compact closure in Rk ○ (c) follows from (b) Complete Metric Space • Definition ○ A metric space X is said to be complete if ○ every Cauchy sequence converges in X • Examples ○ Rk is complete ○ Compact metric space X is complete ○ Q is not complete (convergence may lie outside of Q) Monotonic Sequence • A sequence {s_n } of real numbers is said to be • monotonically increasing if s_n≤s_(n+1), ∀n∈N • monotonically decreasing if s_n≥s_(n+1), ∀n∈N • monotonic if {s_n } is either monotonically increasing or decreasing Theorem 3.14 (Monotone Convergence Theorem) • Statement ○ If {s_n } is monotonic, then {s_n } converges if and only if it is bounded • Proof ○ By Theorem 3.2 (c), converge implies boundedness ○ Without loss of generality, suppose {s_n } is monotonically increasing ○ Let E=range {s_n }, and s=sup⁡E, then s_n≤s,∀n∈N ○ Given ε 0,∃N∈N s.t. s−ε s_n≤s,∀n≥N ○ Since s−ε is not an upper bound of E, and {s_n } is increasing ○ s−s_n ε,∀n≥N⇒lim_(n→∞)⁡〖s_n 〗=s$

6.2 The Pigeonhole Principle

The Pigeonhole Principle • Introduction ○ If a flock of 20 pigeons roosts in a set of 19 pigeonholes ○ Then, one of the pigeonholes must have more than 1 pigeon. • Pigeonhole Principle ○ If k is a positive integer and k + 1 objects are placed into k boxes ○ Then at least one box contains two or more objects. • Proof ○ We use a proof by contraposition. ○ Suppose none of the k boxes has more than one object ○ Then the total number of objects would be at most k. ○ This contradicts the statement that we have k + 1 objects. • Corollary 1 ○ A function f from a set with k + 1 elements to a set with k elements is not one-to-one. • Proof ○ Use the pigeonhole principle. ○ Create a box for each element y in the codomain of f . ○ Put in the box for y all of the elements x from the domain such that f(x)=y. ○ Because there are k + 1 elements and only k boxes, at least one box has two or more elements. ○ Hence, f can’t be one-to-one. • Example ○ Among any group of 367 people, there must be at least two with the same birthday ○ Because there are only 366 possible birthdays. • Example ○ Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion. ○ Let n be a positive integer. ○ Consider the n + 1 integers 1, 11, 111, … , 11…1 (where the last has n + 1 1s). ○ There are n possible remainders when an integer is divided by n. ○ By the pigeonhole principle, when each of the n + 1 integers is divided by n, at least two must have the same remainder. ○ Subtract the smaller from the larger and the result is a multiple of n that has only 0s and 1s in its decimal expansion. The Generalized Pigeonhole Principle • The Generalized Pigeonhole Principle ○ If N objects are placed into k boxes ○ Then there is at least one box containing at least ⌈N/k⌉ objects. • Proof ○ We use a proof by contraposition. ○ Suppose that none of the boxes contains more than ⌈N/k⌉−1 objects. ○ Then the total number of objects is at most ○ k(⌈N/k⌉−1) k((⌈N/k⌉+1)−1)=N ○ where the inequality ⌈N/k⌉ ⌈N/k⌉+1 has been used. ○ This is a contradiction because there are a total of n objects. • Example ○ Among 100 people there are at least ⌈100/12⌉ = 9 who were born in the same month. • Example ○ How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen? ○ We assume four boxes; one for each suit. ○ Using the generalized pigeonhole principle, at least one box contains at least ⌈N/4⌉ cards. ○ At least three cards of one suit are selected if ⌈N/4⌉ ≥3. ○ The smallest integer N such that ⌈N/4⌉ ≥3 is N = 2 ∙ 4 + 1 = 9. • Example ○ How many must be selected to guarantee that at least three hearts are selected? ○ A deck contains 13 hearts and 39 cards which are not hearts. ○ If we select 41 cards, we may have 39 cards which are not hearts along with 2 hearts. ○ However, when we select 42 cards, we must have at least three hearts. ○ (Note that the generalized pigeonhole principle is not used here.)

6.1 The Basics of Counting

Basic Counting Principles: The Product Rule • The Product Rule ○ A procedure can be broken down into a sequence of two tasks. ○ There are n_1 ways to do the first task and n_2 ways to do the second task. ○ Then there are n_1∙n_2 ways to do the procedure. • Example 1 ○ How many bit strings of length seven are there? ○ Since each of the seven bits is either a 0 or a 1, the answer is 2^7 = 128. • Example 2 ○ How many different license plates can be made if ○ each plate contains a sequence of 3 uppercase English letters followed by 3 digits? ○ There are 26 ∙ 26 ∙ 26 ∙ 10 ∙ 10 ∙ 10 = 17,576,000 different possible license plates. • Example 3: Counting Functions ○ How many functions are there from a set with m elements to a set with n elements? ○ A function represents a choice of one of the n elements of the codomain for each of the m elements in the domain ○ The product rule tells us that there are n⋅n⋯n = n^m such functions. • Example 4: Counting One-to-One Functions ○ How many 1-to-1 functions are there from a set with m elements to one with n elements? ○ Suppose the elements in the domain are a_1,a_2,…,a_m. ○ There are n ways to choose the value of a_1 and n−1 ways to choose a_2, etc. ○ The product rule tells us that there are n(n−1)(n−2)⋯(n−m+1) functions. • Example 5: Counting Subsets of a Finite Set ○ Show that the number of different subsets of a finite set S is 2^|S| ○ When the elements of S are listed in an arbitrary order ○ There is a one-to-one correspondence between subsets of S and bit strings of length |S|. ○ When the ith element is in the subset, the bit string has a 1 in the ith position and a 0 otherwise. ○ By the product rule, there are 2^|S| such bit strings, and therefore 2^|S| subsets. • Example 6: Product Rule in Terms of Sets ○ Let A_1,A_2,…,A_m be finite sets ○ The number of elements in the Cartesian product of these sets is the product of the number of elements of each set. ○ The task of choosing an element in the Cartesian product A_1×A_2×…×A_m is done by ○ choosing an element in A_1, an element in A_2 , …, and an element in A_m. ○ By the product rule, it follows that: |A_1×A_2×…×A_m |=|A_1 |⋅|A_2 |⋯|A_m | • Example 7: DNA and Genomes ○ A gene is a segment of a DNA molecule that encodes a particular protein and the entirety of genetic information of an organism is called its genome. ○ DNA molecules consist of two strands of blocks known as nucleotides. ○ Each nucleotide is composed of bases: adenine(A), cytosine(C), guanine(G), thymine(T). ○ The DNA of bacteria has between 〖10〗^5 and 〖10〗^7 links (one of the four bases). ○ Mammals have between 〖10〗^8 and 〖10〗^10 links. ○ So, by the product rule there are at least 4^(〖10〗^5 ) different sequences of bases in the DNA of bacteria and 4^(〖10〗^8 ) different sequences of bases in the DNA of mammals. ○ The human genome includes approximately 23,000 genes, each with 1,000 or more links. Basic Counting Principles: The Sum Rule • The Sum Rule ○ If a task can be done either in one of n_1 ways or in one of n_2, ○ where none of the set of n_1 ways is the same as any of the n_2 ways, ○ then there are n_1+n_2 ways to do the task. • Example ○ The mathematics department must choose either a student or a faculty member as a representative for a university committee. ○ How many choices are there for this representative if there are 37 members of the mathematics faculty and 83 mathematics majors and no one is both a faculty member and a student. ○ There are 37 + 83 = 120 possible ways to pick a representative. • The Sum Rule in terms of sets ○ The sum rule can be phrased in terms of sets. ○ |A ∪ B|= |A| + |B| as long as A and B are disjoint sets. ○ Or more generally, § |A_1∪A_2∪…∪A_m |=|A_1 |+|A_2 |+…+|A_m |, when A_i∩A_j=∅ for all i,j Combining the Sum and Product Rule • Example 1 ○ Suppose statement labels in a programming language can be either a single letter or a letter followed by a digit. ○ Find the number of possible labels. ○ Use the product rule: 26 + 26 ∙ 10 = 286 • Example 2: Counting Passwords ○ Each user on a computer system has a password ○ which is 6 to 8 characters long, where each character is an uppercase letter or a digit. ○ Each password must contain at least one digit. ○ How many possible passwords are there? ○ Let P be the total number of passwords ○ Let P_6, P_7, and P_8 be the passwords of length 6, 7, and 8. ○ By the sum rule P=P_6+P_7+P_8. ○ To find each of P_6, P_7, and P_8, we find the number of passwords of the specified length composed of letters and digits and subtract the number composed only of letters. ○ We find that: § P_6 = 〖36〗^6 − 〖26〗^6 = 2,176,782,336 − 308,915,776 =1,867,866,560 § P_7 = 〖36〗^7 − 〖26〗^7 = 78,364,164,096 − 8,031,810,176 = 70,332,353,920 § P_8 = 〖36〗^8 − 〖26〗^8 = 2,821,109,907,456 − 208,827,064,576 = 2,612,282,842,880 ○ Consequently, P=P_6+P_7+P_8 = 2,684,483,063,360. Basic Counting Principles: Subtraction Rule • The Subtraction Rule ○ If a task can be done either in one of n_1 ways or in one of n_2 ways ○ Then the total number of ways to do the task is n_1 + n_2 minus the number of ways to do the task that are common to the two different ways. ○ Also known as, the principle of inclusion-exclusion: ○ |A∪B|=|A|+|B|−|A∩B| • Example: Counting Bit Strings ○ How many bit strings of length eight either start with a 1 bit or end with the two bits 00? ○ Use the subtraction rule. ○ Number of bit strings of length eight that start with a 1 bit: 2^7 = 128 ○ Number of bit strings of length eight that end with bits 00: 2^6 = 64 ○ Number of bit strings of length eight that start with a 1 bit and end with bits 00: 2^5 = 32 ○ Hence, the number is 128 + 64 − 32 = 160. Basic Counting Principles: Division Rule • Division Rule ○ There are n/d ways to do a task if ○ it can be done using a procedure that can be carried out in n ways ○ and for every way w, exactly d of the n ways correspond to way w. • In terms of sets ○ If the finite set A is the union of n pairwise disjoint subsets each with d elements ○ then n = |A|/d. • In terms of functions ○ If f is a function from A to B, where both are finite sets, and for every value y ∈ B there are exactly d values x ∈ A such that f(x)=y, then |B|=|A|/d. • Example ○ How many ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left and right neighbor? ○ Number the seats around the table from 1 to 4 proceeding clockwise. ○ There are four ways to select the person for seat 1, 3 for seat 2, 2, for seat 3, and one way for seat 4. ○ Thus there are 4! = 24 ways to order the four people. ○ But since two seatings are the same when each person has the same left and right neighbor, for every choice for seat 1, we get the same seating. ○ Therefore, by the division rule, there are 24/4 = 6 different seating arrangements. Tree Diagrams • Tree Diagrams ○ We can solve many counting problems through the use of tree diagrams, where a branch represents a possible choice and the leaves represent possible outcomes. • Example ○ Suppose that “I Love Discrete Math” T-shirts come in five different sizes: S, M, L, XL, XXL. ○ Each size comes in four colors (white, red, green, and black), except XL, which comes only in red, green, and black, and XXL, which comes only in green and black. ○ What is the minimum number of shirts that the campus book store needs to stock to have one of each size and color available? ○ Draw the tree diagram. The store must stock 17 T-shirts.

Math 541 – 3/21

$Proposition 43 • Statement ○ If G is a group, H≤G, and [G:H]=2, then H⊴G • Proof ○ If g∈H, then gH=H=Hg ○ If g∉H, then gH=G∖H=Hg ○ Therefore gH=Hg,∀g∈G ○ So H⊴G • Corollary ○ Let p be the smallest prime dividing |G| ○ If [G:H]=p, then H⊴G ○ (Not ready to prove this yet) Proposition 44 • Statement ○ If (a_1…a_t ),(a_1′…a_t′) are t-cycles in S_n ○ Then ∃σ∈S_n s.t. σ(a_1…a_t ) σ^(−1)=(a_1′…a_t′) • Proof ○ Choose σ∈S_n s.t. σ(a_i )=a_i^′, ∀i∈{1,…,t} ○ By HW 7 #1, σ(a_1…a_t ) σ^(−1)=(σ(a_1 )…σ(a_t ))=(a_1′…a_t′) Theorem 45 • Statement ○ A_4 have no subgroup of order 6 • Proof ○ By way of contradiction, suppose H≤G, and |H|=6 ○ Then [A_4:H]=2 and thus H⊴A_4 ○ A_4 contains 8 3-cycles, so H contains some 3-cycle α ○ Write α=(a b c), then § (a b d)(a b c) (a b d)^(−1)=(b d c)∈H § (b c d)(a b c) (b c d)^(−1)=(a c d)∈H § (b d c)(a b c) (b d c)^(−1)=(a d b)∈H ○ So far, we have (1), (a b c),(b d c),(a c d),(a d b)∈H ○ Also, since H is closed under inverses, (a c b),(b c d)∈H ○ Thus, |H|≥7, which makes a contradiction ○ Therefore A_4 have no subgroup of order 6 Group Action • Definition ○ An action of G on X is a function G×X→X, (g,x)↦gx where ○ 1_G x=x, ∀x∈X ○ g(h�)=(ghx,∀g,h∈G,x∈X • Examples Set Group Action Rn GL_n (R (A,v)↦Av {1,…,n} S_n (σ,i)↦σ(i) Group G Group G (g,h↦gh Group G Group G (g,h↦ghg^(−1) Set of cosets of H≤G Group G (g,g^′ H)↦gg^′ H Set of all subgroups of group G Group G (g,H)↦gHg^(−1) • Note ○ If H≤G, and g∈G, then gHg^(−1)={gh�^(−1)│hH}≤G ○ gHg^(−1)≠∅, since g1g^(−1)=1∈gHg^(−1) ○ If ghg^(−1),gh′ g^(−1)∈gHg^(−1), then ○ ghg^(−1) (gh′ g^(−1) )^(−1)=ghg^(−1) g(h′ )^(−1) g^(−1)=gh(h′ )^(−1)∈gHg^(−1) Orbit and Stabilizer • Suppose a group G acts on a set X. Let x∈X • The orbit of x, denoted orb(x), is {gx│g∈G}⊆X • The stabilizer of x, denoted stab(x), is {g∈G│gx=x}⊆G Proposition 46 • Statement ○ If G acts on X, and x∈X, then stab(x)≤G • Proof ○ stab(x) ≠∅, because 1x=x ○ Let g,h∈stab(x) ○ (ghx=g(h�)=gx=x⇒gh∈stab(x) ○ x=1⋅x=(g^(−1) g)x=g^(−1) (gx)=g^(−1) x⇒g^(−1)∈stab(x) Centralizer • Let G be a group, and let G act on itself by conjugation • If h∈G, then stab(h={g∈G│gh�^(−1)=h={g∈G│ghh�} • This set is called the centralizer of h, denoted as C_G (h Center • Intersections of subgroups are subgroup • Thus if G acts on a set X, ⋃8_(x∈X)▒stab(x) ≤G • In the example above, ⋃8_(hG)▒〖C_G (h 〗=Z(G) is called the center of G Normalizer • Let G be a group, and let X be the set of subgroups of G • G acts on X by g⋅H=gHg^(−1) • If H≤G, then • stab(H)={g∈G│gHg^(−1)=H}={g∈G│gH=Hg} • This set is called the normalizer of H in G, denoted N_G (H) • N_G (H)=G⟺H⊴G$