GROUP THEORYCS 468 – Lecture 410/16/2Afra Zomorodian – CS 468 Lecture 4 - Page 1M. C. ESCHERI had not yet seen the tile decorations of the Alhambra and never heard of crystal-lography; so I did not even know that my game was based on rules that have beenscientifically investigated.I never got a pass in math.... And just imagine–mathematicians now use my printsto illustrate their books.— M. C. EscherAfra Zomorodian – CS 468 Lecture 4 - Page 2OVERVIEW• Abstract algebra: studying core properties• Groups• Subgroups and Cosets• Homomorphisms• Factor groups• Cyclic groups• Finitely generated abelian groupsAfra Zomorodian – CS 468 Lecture 4 - Page 3BINARY OPERATION• A binary operation ∗ on a set S is a rule that assigns to each orderedpair (a, b) of elements of S some element in S.• If ∗ assigns a single element, it is well-defined; if no element, it is notdefined; if multiple elements, not well-defined.• If it always assigns an element in S, it is closed.• It is associative iff (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ S.• It is commutative iff a ∗ b = b ∗ a for all a, b ∈ S.a b ca b c ac a b cb e a bAfra Zomorodian – CS 468 Lecture 4 - Page 4ABSTRACTION1. 5 + x = 2 =⇒ Z−2. 2x = 3 =⇒ Q3. x2= −1 =⇒ C5 + x = 2 Given−5 + (5 + x) = −5 + 2 Addition property of equality(−5 + 5) + x = −5 + 2 Associative property of addition0 + x = −5 + 2 Inverse property of additionx = −5 + 2 Identity property of additionx = −3 AdditionAfra Zomorodian – CS 468 Lecture 4 - Page 5GROUPS• A group hG, ∗i is a set G, together with a binary operation ∗ on G,such that the following axioms are satisfied:(a) ∗ is associative.(b) G has an identity e element for ∗ such that e ∗ x = x ∗ e = x forall x ∈ G.(c) any element a has an inverse a0with respect to the operation ∗,i.e. ∀a ∈ G, ∃a0∈ G such that a0∗ a = a ∗ a0= e.• If G is finite, the order of G is |G|.• We often omit the operation and refer to G as the group.• hZ, +i, hR, ·i, hR, +i, are all groups.• A group G is abelian if its binary operation ∗ is commutative.Afra Zomorodian – CS 468 Lecture 4 - Page 6SMALL GROUPS(EXAMPLE)Z2e ae e aa a eZ3e a be e a ba a b eb b e aZ40 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2V4e a b ce e a b ca a e c bb b c e ac c b a eAfra Zomorodian – CS 468 Lecture 4 - Page 7SYMMETRY GROUPS(EXAMPLE)• If the space has a metric d, a transformation φ is an isometry ifd(x, y) = d(φ(x), φ(y)), that is, if φ preserves distance.• A symmetry is any isometry that leaves the object as a wholeunchanged. Symmetries form groups!aacbAfra Zomorodian – CS 468 Lecture 4 - Page 8SUBGROUPS• Let hG, ∗i be a group and S ⊆ G. If S is closed under ∗, then ∗ is theinduced operation on S from G.• A subset H ⊆ G of group hG, ∗i is a subgroup of G if H is a groupand is closed under ∗. The subgroup consisting of the identityelement of G, {e} is the trivial subgroup of G. All other subgroupsare nontrivial.• (Theorem)H ⊆ G of a group hG, ∗i is a subgroup of G iff:1. H is closed under ∗,2. the identity e of G is in H,3. for all a ∈ H, a−1∈ H.• Example: subgroups of Z4Afra Zomorodian – CS 468 Lecture 4 - Page 9COSETS• Let H be a subgroup of G. Let the relation ∼Lbe defined on G by:a ∼Lb iff a−1b ∈ H. Let ∼Rbe defined by: a ∼Rb iff ab−1∈ H.Then ∼Land ∼Rare both equivalence relations on G.• Let H be a subgroup of group G. For a ∈ G, the subsetaH = {ah | h ∈ H} of G is the left coset of H containing a, andHa = {ha | h ∈ H} is the right coset of H containing a.• If left and right cosets match, the subgroup is normal.• All subgroups H of an abelian group G are normal, asah = ha, ∀a ∈ G, h ∈ H• {0, 2} is a subgroup of Z4. It is normal. The coset of 1 is1 + {0, 2} = {1, 3}. That’s all folks!Afra Zomorodian – CS 468 Lecture 4 - Page 10FACTOR GROUPS• Let H be a normal subgroup of group G.• Left coset multiplication is well-defined by the equation(aH)(bH) = (ab)H• The cosets of H form a group G/H under left multiplication• G/H is the factor group (or quotient group) of G modulo H.• The elements in the same coset of H are congruent modulo H.Afra Zomorodian – CS 468 Lecture 4 - Page 11FACTOR GROUPS(EXAMPLE)0 33 00 33 00 33 01 4 2 5251 41 44 12 52 5254 14 125ZZ6524130034251*• {0, 3} is a normal subgroup• Cosets {0, 3}, {1, 4}, and {2, 5}• Z6/{0, 3}∼=Z3Afra Zomorodian – CS 468 Lecture 4 - Page 12FACTOR GROUPS(EXAMPLE)ZZ60052 4240 2 41 3 52 4 04 0 2135313 5 15 1 35313 5 15 1 342 040 2 40 2*• {0, 2, 4} is a normal subgroup• Cosets {0, 2, 4}, {1, 3, 5}• Z6/{0, 2, 4}∼=Z2Afra Zomorodian – CS 468 Lecture 4 - Page 13HOMOMORPHISMS• A map ϕ of a group G into a group G0is a homomorphism ifϕ(ab) = ϕ(a)ϕ(b) for all a, b ∈ G.• Trivial homomorphism defined by ϕ(g) = e0for all g ∈ G, where e0is the identity in G0.• A 1-1 homomorphism is an monomorphism.• A homomorphism that is onto is an epimorphism.• A homomorphism that is 1-1 and onto is an isomorphism.• We use∼=for isomorphisms.• (Theorem) Let G be any collection of groups. Then∼=is anequivalence relation on G.Afra Zomorodian – CS 468 Lecture 4 - Page 14PROPERTIES OF HOMOMORPHISMS• If e is the identity in G, then ϕ(e) is the identity e0in G0.• If a ∈ G, then ϕ(a−1) = ϕ(a)−1.• If H is a subgroup of G, then ϕ(H) is a subgroup of G0.• If K0is a subgroup of G0, then ϕ−1(K0) is a subgroup of G.• The normal subgroup ker ϕ = ϕ−1({e0}) ⊆ G, is the kernel of ϕ.e’Gϕker ϕG’Afra Zomorodian – CS 468 Lecture 4 - Page 15CYCLIC GROUPS• Let G be a group and let a ∈ G• H = {an| n ∈ Z} is a subgroup of G• It is the smallest subgroup of G that contains a• H is the cyclic subgroup of G generated by a denoted hai• If hai is finite, the order of a is |hai|• a ∈ G generates G and is a generator for G if hai = G• A group G is cyclic if it has a generator• Is Zmcyclic? Is V4?Afra Zomorodian – CS 468 Lecture 4 - Page …