Algebraic Structures: Group Theory IISlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Lagrange’s TheoremSlide 15Lagrange’s Theorem: what is for?Slide 17Slide 18Lagrange’s TheoremIsomorphismSlide 21Group IsomorphismSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Cyclic GroupsSlide 31Slide 32Permutation GroupsSlide 34Slide 35Slide 36Algebraic Structures: Group Theory IIGreat Theoretical Ideas In Computer ScienceVictor AdamchikDanny SleatorCS 15-251 Spring 2010Lecture 17 Mar. 17, 2010 Carnegie Mellon University3. (Inverses) For every a S there is b S such that:GroupA group G is a pair (S,), where S is a set and is a binary operation on S such that:1. is associative2. (Identity) There exists an element e S such that:e a = a e = a, for all a S a b = b a = eRevieworder of a group G = size of the group Gorder of an element g = (smallest n>0 s.t. gn = e)g is a generator if order(g) = order(G)Theorem: Let x be an element of G. The order of x divides the order of GOrders(Z10: +) Orders: example{0,1,2,3,4,5,6,7,8,9}smallest n>0 such that gn = e1 10 5 10 5 2Let G be a group. A non-empty set H G is a subgroup if it forms a group under the same operation.SubgroupsExercise. Does {0,2,4} form a subgroup of Z6 under +?Exercise. Does {2n, nZ} form a subgroup of Q\{0} under *?Let G be a group. A non-empty set H G is a subgroup if it forms a group under the same operation.SubgroupsExercise. List all subgroups of Z12 under +.Z12{0}{0,6}{0,4,8}{0,3,6,9}{0,2,4,6,8,10}We are going to generalize the idea of congruent classes mod n in (Z,+).Theorem. Let H is a subgroup of G. Define a relation: ab iff a b-1 H.Then is an equivalence relation.Cosetsa = b (mod n) iff a - b <n>Theorem. Let H is a subgroup of G. Define a relation: ab iff a b-1 H.Then is an equivalence relation.Proof. Reflexive: aa iff a a-1 =e HCosetsTransitive: a c-1=(a b-1)(b c-1) H Symmetric: b a-1=(a b-1)-1 HThe equivalent classes for this relation is called the right cosets of H in G.CosetsIf H is a subgroup of a group G then for any element g of the group the set of products of the form h g where hH is a right coset of H denoted by the symbol Hg.Exercise.Write down the right coset of the subgroup {0,3,6,9} of Z12 under +.CosetsRight coset = {h g | h H, g G} {0,3,6,9} + {0,1,2,3,4,5,6,7,8,9,10,11} =[3]+0 = {0,3,6,9}[3]+1 = {1,4,7,10}[3]+2 = {2,5,8,11}Theorem.If H is a finite subgroup of G and xG, then |H|=|Hx|CosetsProof. We prove this by finding a bijection between H and Hx.It is onto, because Hx consists of the elements of the form hx, where hH.Assume that there are h1, h2H. .Then h1x= h2x. It follows, h1=h2.Theorem.If H is a finite subgroup of G, then G = xG Hx.Cosets: partitioningProof. Cosets are equivalent classes.The two cosets are either equal or disjoint.Since G is finite, there are finitely many such cosets.Every element x of G belongs to the coset determined by it.x = x e Hx, since eH.Lagrange’s Theorem Theorem: If G is a finite group, and H is a subgroup then the order of H divides the order of G. In symbols, |H| divides |G|.Lagrange’s Theorem Theorem: |H| divides |G|.Proof: G is partitioning into cosets.Pick a representative from each cosetG = j=1…k HxjEach coset contains |H| elements.It follows |G| = k |H|. Thus |H| is a divisor of |G|.Lagrange’s Theorem: what is for? The theorem simplifies the problem of finding all subgroups of a finite group.Consider group of symmetry of square YSQ = { R0, R90, R180, R270, F|, F—, F , F }Except {R0} and Ysq, all other subgroups must have order 2 or 4.R90R180R270R0F|F—F FR0R90R180R270F|F—FFR0R90R180R270F|F—F FR90R180R270F|F—FFR180R270R0R270R0R90R0R90R180F F F|F—F—F|F FF F F—F|F F—FF F|FF—F F|F|F F—R0R0R0R0R180R90R270R180R270R90R270R90R180R90R270R180Order 2R90R180R270R0F|F—F FR0R90R180R270F|F—FFR0R90R180R270F|F—F FR90R180R270F|F—FFR180R270R0R270R0R90R0R90R180F F F|F—F—F|F FF F F—F|F F—FF F|FF—F F|F|F F—R0R0R0R0R180R90R270R180R270R90R270R90R180R90R270R180Order 4Lagrange’s TheoremExercise.Suppose that H and K are subgroups of G and assume that |H| = 9, |K| = 6, |G| < 50. What are the possible values of |G|?LCM(9,6) = 18, so |G|=18 or 36IsomorphismMapping between objects, which shows that they are structurally identical.Any property which is preserved by an isomorphism and which is true for one of the objects, is also true of the other.IsomorphismExample. {1,2,3,…}, or {I, II, III,…}, or {один, два, три,…}Mathematically we want to think aboutthese sets as being the same.Group IsomorphismDefinition. Let G be a group with operation and H with . An isomorphism of G to H is a bijectionf: GH that satisfiesf(x y) = f(x) f(y)If we replace bijection by injection, such mapping is called a homomorphism.Group IsomorphismExample. G = (Z, +), H = (even, +)Isomorphism is provided by f(n) = 2 nf(n + m) = 2 (n+m) = (2n)+(2m)=f(n)+f(m)Group IsomorphismExample. G = (R+, ), H = (R, +)Isomorphism is provided by f(x) = log(x)f(x y) = log(x y) = log(x) + log(y) = f(x) + f(y)Group IsomorphismTheorem. Let G be a group with operation , H with and they are isomorphic f(x y) = f(x) f(y). Then f(eG) = eHProof. f(eG)= f(eG eG) = f(eG) f(eG). On the other hand, f(eG)=f(eG) eHf(eG) eH = f(eG) f(eG) f(eG) = eHGroup IsomorphismTheorem. Let G be a group with operation , H with and they are isomorphic f(x y) = f(x) f(y). Then f(x-1) = f(x)-1, xGProof. f(x) f(x-1) = f(x x-1) =f(eG) = eH.Group IsomorphismIn order to prove that two groups and are not isomorphic, one needs to demonstrate that there is no isomorphism from onto . Usually, in practice, this is accomplished by finding some property that holds in one group, but not in the other. Examples. (Z4, +) and (Z6, +)They have different orders.+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2* 1 2 3 41 1 2 3 42 2 4 1 33 3 1 4 24 4 3 2 1Exercise. Verify that (Z4, +) is isomorphic to (Z*5, *)Group IsomorphismExercise. Verify that (Z4, +) is isomorphic to (Z*5, *)Z4 is generated by 1 as in 0, 1, 2, 3, (then back to 0)Z*5 is generate by 2 as in 1, 2, 4, 3, (then back to 1)0 1 1 2 2 4 3 3 f(x)= 2x mod 5Cyclic GroupsDefinition. Let G be a group and xG. Then <x>={xk | k Z} is a
View Full Document
Unlocking...