3 3 2009 15 251 Great Theoretical Ideas in Computer Science Algebraic Structures Group Theory Lecture 15 March 3 2009 Rotating a Square in Space Today we are going to study the abstract properties of binary operations Imagine we can pick up the square rotate it in any way we want and then put it back on the white frame We will now these 8 motions In how manystudy different ways can we called of on thethe square put thesymmetries square back frame Symmetries of the Square YSQ R0 R90 R180 R270 F F F F R90 F R180 F R270 F R0 F 1 3 3 2009 R0 R90 R180 R270 F F F F R0 R0 R90 R180 R270 F F F F R90 R90 R180 R270 R0 F F F F R180 R180 R270 R0 R90 F F F F R270 R270 R0 R90 R180 F F F F Composition Define the operation to mean first do one symmetry and then do the next For example R90 R180 means first rotate 90 clockwise and then 180 R270 F R90 means first flip horizontally and then rotate 90 F Question if a b YSQ does a b YSQ Yes F F F F F R0 R180 R90 R270 F F F F F R180 F F F F F R270 R90 F F F F F R0 R270 R90 R0 R90 R270 R180 R180 R0 Some Formalism If S is a set S S is the set of all ordered pairs of elements of S S S a b a S and b S How many symmetries for n sided body R0 R1 R2 Rn 1 YSQ YSQ YSQ Ri Fj Fj i Fj Ri Fj i If S has n elements how many elements does S S have n2 Formally is a function from YSQ YSQ to YSQ F0 F1 F2 Fn 1 Ri Rj Ri j 2n Fi Fj Rj i Binary Operations is called a binary operation on YSQ Definition A binary operation on a set S is a function S S S Example The function f N N N defined by f x y xy y is a binary operation on N As shorthand we write a b as a b Associativity A binary operation on a set S is associative if for all a b c S a b c a b c Examples Is f N N N defined by f x y xy y associative ab b c c a bc c bc c NO Is the operation on the set of symmetries of the square associative YES 2 3 3 2009 Identities Commutativity R0 is like a null motion A binary operation on a set S is commutative if For all a b S Is this true a YSQ a R0 R0 a a YES a b b a R0 is called the identity of on YSQ Is the operation on the set of symmetries of the square commutative NO R90 F F R90 In general for any binary operation on a set S an element e S such that for all a S e a a e a is called an identity of on S Inverses Definition The inverse of an element a YSQ is an element b such that Every element in YSQ has a unique inverse a b b a R0 Examples R90 inverse R270 R180 inverse R180 F inverse F R0 R90 R180 R270 F F F F R0 R0 R90 R180 R270 F F F F R90 R90 R180 R270 R0 F F F F R180 R180 R270 R0 R90 F F F F 1 is associative R270 R270 R0 R90 R180 F F F F 2 Identity There exists an element e S such that e a a e a for all a S F F F F F R0 R180 R90 R270 F F F F F R180 F F F F F R270 R90 F F F F F R0 Groups A group G is a pair S where S is a set and is a binary operation on S such that R270 R90 R0 R90 R270 R180 R180 3 Inverses For every a S there is b S such that a b b a e R0 3 3 3 2009 Commutative or Abelian Groups If G S and is commutative then G is called a commutative group To check group ness Given S 1 Check closure for S i e for any a b in S check a b also in S 2 Check that associativity holds remember commutative means a b b a for all a b in S 3 Check there is a identity 4 Check every element has an inverse Examples Is N a group Is N closed under Some examples YES Is associative on N YES Is there an identity YES 0 Does every element have an inverse NO N is NOT a group Examples Is Z a group Is Z closed under Examples Is Odds a group YES Is Odds closed under NO Is associative on Z YES Is associative on Odds Is there an identity YES 0 Is there an identity NO Does every element have an inverse YES Does every element have an inverse YES Z is a group YES Odds is NOT a group 4 3 3 2009 Examples Is YSQ a group Is YSQ closed under Examples Is Zn n a group YES Is associative on YSQ YES Is there an identity YES R0 Does every element have an inverse YES YSQ is a group Zn is the set of integers modulo n Is Zn closed under n YES Is n associative on Zn YES Is there an identity YES 0 Does every element have an inverse YES the dihedral group D4 Zn n is a group Examples Examples Is Zn n a group Is Zn n a group Zn is the set of integers modulo n Is n associative on Zn YES Is there an identity YES 1 Does every element have an inverse NO Zn is the set of integers modulo n that are relatively prime to n Is n associative on Zn YES Is there an identity YES 0 Does every element have an inverse YES Zn n is NOT a group Zn n is a group Groups 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 5 3 3 2009 Identity Is Unique Theorem A group has at most one identity element Some properties of groups Proof Suppose e and f are both identities of G S Then f e f e We denote this identity by e Inverses Are Unique Theorem Every element in a group has a unique inverse Proof Orders and generators Suppose b and c are both inverses of a Then b b e b a c b a c c Order of …
View Full Document
Unlocking...