Great Theoretical Ideas In Computer Science Victor Adamchik Danny Sleator CS 15 251 Lecture 17 Mar 17 2010 Spring 2010 Carnegie Mellon University Algebraic Structures Group Theory II 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 Orders Theorem Let x be an element of G The order of x divides the order of G order of an element g smallest n 0 s t gn e g is a generator if order g order 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 Z 6 under Exercise Does 2n n Z form a subgroup of Q 0 under 1 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 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 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 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 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 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 2 Cosets partitioning Lagrange s Theorem Theorem If H is a finite subgroup of G then G x G Hx Theorem If G is a finite group and H is a subgroup then the order of H divides the order of G Proof Cosets are equivalent classes The two cosets are either equal or disjoint Since G is finite there are finitely many such cosets In symbols H divides G Every element x of G belongs to the coset determined by it x x e Hx since e H Lagrange s Theorem Lagrange s Theorem what is for Theorem H divides G The theorem simplifies the problem of finding all subgroups of a finite group Proof G is partitioning into cosets Pick a representative from each coset G j 1 k Hxj Consider group of symmetry of square YSQ R0 R90 R180 R270 F F F F Each coset contains H elements It follows G k H Thus H is a divisor of G Order 2 R0 Except R0 and Ysq all other subgroups must have order 2 or 4 R90 R180 R270 F F F F Order 4 R0 R90 R180 R270 F F F F R0 R0 R90 R180 R270 F F F F R90 R180 R270 F F F F R0 R0 R90 R90 R180 R270 R0 F F F F R90 R90 R180 R270 R0 F F F F R180 R180 R270 R0 R90 F F F F R180 R180 R270 R0 R90 F F F F R270 R270 R0 R90 R180 F F F F R270 R270 R0 R90 R180 F F F F F F F F F R0 F F F F F R0 F F F F F R180 F F F F F R180 F F F F F R270 R90 R180 F F F F F R270 R90 F F F F F R90 R270 R180 R0 F F F F F R90 R270 R180 R180 R90 R270 R0 R270 R90 R0 R180 R90 R270 R0 R270 R90 R0 R180 R0 3 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 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 LCM 9 6 18 so G 18 or 36 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 Group Isomorphism Example G Z H even Example Isomorphism is provided by f n 2 n Isomorphism is provided by f x log x f n m 2 n m 2n 2m f n f m f x y log x y log x log y f x f y G R H R 4 Group Isomorphism Group Isomorphism Theorem Let G be a group with operation H with and they are isomorphic f x y f x f y Then 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 f x 1 f x 1 x G Proof f eG f eG eG f eG f eG Proof On the other hand f eG f eG eH f eG eH f eG f eG f eG eH f x f x 1 f x x 1 f eG eH Group Isomorphism Group Isomorphism In order to prove that two groups and are not isomorphic one needs to demonstrate that there is no isomorphism from …
View Full Document
Unlocking...