Great Theoretical Ideas In Computer Science Victor Adamchik Danny Sleator Lecture 17 CS 15 251 Mar 17 2010 Algebraic Structures Group Theory II Spring 2010 Carnegie Mellon University Group A group G is a pair S where S is a set and is a binary operation on S such that 1 is associative 2 Identity There exists an element e S such that e a a e a for all a S 3 Inverses For every a S there is b S such that a b b a e Review order of a group G size of the group G rder of an element g smallest n 0 s t gn e g is a generator if order g order G Orders Theorem Let x be an element of G The order of x divides the order of G Orders example Z10 0 1 2 3 4 5 6 7 8 9 smallest n 0 such that gn e 1 10 5 10 5 2 Subgroups Let G be a group A non empty set H G is a subgroup if it forms a group under the same operation Exercise Does 0 2 4 form a subgroup of Z6 under Exercise Does 2n n Z form a subgroup of Q 0 under Subgroups Let G be a group A non empty set H G is a subgroup if it forms a group under the same operation Exercise List all subgroups of Z12 under Z12 0 0 6 0 4 8 0 3 6 9 0 2 4 6 8 10 Cosets We are going to generalize the idea of congruent classes mod n in Z a b mod n iff a b n Theorem Let H is a subgroup of G Define a relation a b iff a b 1 H Then is an equivalence relation Cosets Theorem Let H is a subgroup of G Define a relation a b iff a b 1 H Then is an equivalence relation Proof Reflexive a a iff a a 1 e H Symmetric b a 1 a b 1 1 H Transitive a c 1 a b 1 b c 1 H Cosets The equivalent classes for this relation is called the right cosets of H in G If 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 h H is a right coset of H denoted by the symbol Hg Cosets Exercise Write down the right coset of the subgroup 0 3 6 9 of Z12 under Right 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 Cosets Theorem If H is a finite subgroup of G and x G then H Hx Proof 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 h H Assume that there are h1 h2 H Then h1x h2x It follows h1 h2 Cosets partitioning Theorem If H is a finite subgroup of G then G x G Hx Proof 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 e H 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 coset G j 1 k Hxj Each 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 Order R0 2 R90 R180 R270 F F F F R90 R180 R270 F F F F R0 F F F F R90 F F F F F F F R0 R0 R90 R90 R180 R270 R180 R180 R270 R0 R270 R270 R0 R90 R180 F R0 F F F F F R180 R90 R270 F F F F F R180 R0 F F F F F R270 R90 F F F F F R90 R270 R180 R0 R270 R90 R0 R180 Order R0 4 R90 R180 R270 F F F F R90 R180 R270 F F F F R0 F F F F R90 F F F F F F F R0 R0 R90 R90 R180 R270 R180 R180 R270 R0 R270 R270 R0 R90 R180 F R0 F F F F F R180 R90 R270 F F F F F R180 R0 F F F F F R270 R90 F F F F F R90 R270 R180 R0 R270 R90 R0 R180 Lagrange s Theorem Exercise 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 36 Isomorphism Mapping 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 Isomorphism Example 1 2 3 or I II III or Mathematically we want to think about these sets as being the same Group Isomorphism Definition Let G be a group with operation and H with An isomorphism of G to H is a bijection f G H that satisfies f x y f x f y If we replace bijection by injection such mapping is called a homomorphism Group Isomorphism Example G Z H even Isomorphism is provided by f n 2 n f n m 2 n m 2n 2m f n f m Group Isomorphism Example 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 Isomorphism Theorem Let G be a group with operation H with and they are isomorphic f x y f x f y Then f eG eH Proof f eG f eG eG f eG f eG On the other hand f eG f eG eH f eG eH f eG f eG f eG eH Group Isomorphism Theorem 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 x G Proof f x f x 1 f x x 1 f eG eH Group Isomorphism In 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 …
View Full Document
Unlocking...