15 251 Great Theoretical Ideas in Computer Science Algebraic Structures Group Theory Lecture 15 October 12 2010 Number Theory Naturals Integers Zn closed under closed under closed under n a b b a a b b a a n b b n a a b c a b c a b c a b c a nb nc a n b nc a 0 0 a a 0 0 a a n 0 0 n a a a 0 a n a 0 Number Theory Matrices Integers Zn closed under closed under closed under n A B B A a b b a a n b b n a A B C A B C a b c a b c a nb nc a n b nc A 0 0 A a 0 0 a a n 0 0 n a A A 0 a a 0 a n a 0 closed under closed under closed under n a b c a c b c ditto ditto ditto 1 a may not exist ditto Number Theory Invertible Matrices Zn n prime Rationals closed under closed under closed under n A B B A a b b a a n b b n a A B C A B C a b c a b c a nb nc a n b nc A 0 0 A a 0 0 a a n 0 0 n a A A 0 a a 0 a n a 0 closed under closed under closed under n a b c a c b c ditto ditto ditto 1 a exists if a 0 ditto Abstraction Abstract away the inessential features of a problem Today we are going to study the abstract properties of binary operations Rotating a Square in Space 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 study theseways 8 motions In how many different can called theon square we putsymmetries the square of back the frame R90 R180 R270 R0 F F F F Symmetries of the Square YSQ R0 R90 R180 R270 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 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 F F F F F R0 R180 R90 R270 F F F F F R180 R0 R270 R90 F F F F F R270 R90 F F F F F R90 R270 R180 R0 R180 R0 How many symmetries for n sided body R0 R1 R2 Rn 1 F0 F1 F2 Fn 1 Ri Rj Ri j Ri Fj Fj i Fj Ri Fj i Fi Fj Rj i 2n 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 If S has n elements how many elements does S n2S have Formally is a function from YSQ YSQ to YSQ YSQ YSQ YSQ As shorthand we write a b as a b 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 defined by f x y xy y is a binary operation on 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 defined by f x y xy y abassociative b c c a bc c bc c NO Is the operation on the set of symmetries of the square associative YES Commutativity A binary operation on a set S is commutative if For all a b S a b b a Is the operation on the set of symmetries of the square commutative NO R90 F F R90 Identities R0 is like a null motion Is this true a YSQ a R0 R0 a a YES R0 is called the identity of on YSQ 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 a b b a R0 Examples R90 inverse R270 R180 inverse R180 F inverse F Every element in YSQ has a unique inverse 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 F F F F F R0 R180 R90 R270 F F F F F R180 R0 R270 R90 F F F F F R270 R90 F F F F F R90 R270 R180 R0 R180 R0 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 Commutative or Abelian Groups If G S and is commutative then G is called a commutative group remember commutative means a b b a for all a b in S 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 3 Check there is a identity 4 Check every element has an inverse Some examples Examples Is a group Is closed under YES Is associative on YES Is there an identity YES 0 Does every element have an inverse NO is NOT a group Examples Is Z a group Is Z closed under YES Is associative on Z YES Is there an identity YES 0 Does every element have an inverse YES Z is a group Examples Is Odds a group Is Odds closed under NO Is associative on Odds YES Is there an identity NO Does every element have an inverse YES Odds is NOT a group Examples Is YSQ a group Is YSQ closed under YES Is associative on YSQ YES Is there an identity YES R0 Does every element have an inverse YES YSQ is a group the dihedral group D4 Examples Is Zn n 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 …
View Full Document
Unlocking...