15 251 Great Theoretical Ideas in Computer Science Algebraic Structures Group Theory Lecture 15 October 14 2008 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 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 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 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 associative on Odds YES Is there an identity YES 0 Does every element have an inverse YES Are the Odds closed under addition Odds is NOT a group NO Examples Is YSQ a group Is associative on YSQ YES Is there an identity YES R0 Does every element have an inverse YES YSQ is a group Examples Is Zn a group Zn is the set of integers modulo n Is associative on Zn YES Is there an identity YES 0 Does every element have an inverse YES Zn is a group Examples Is Zn a group Zn is the set of integers modulo n Is associative on Zn YES Is there an identity YES 1 Does every element have an inverse NO Zn is NOT a group Examples Is Zn a group Zn is the set of integers modulo n that are relatively prime to n Is associative on Zn YES Is there an identity YES 0 Does every element have an inverse YES Zn is a group And some properties Identity Is Unique Theorem A group has at most one identity element 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 Suppose b and c are both inverses of a Then b b e b a c b a c c Orders and generators Order of a group A group G S is finite if S is a finite set Define G S to be the order of the group i e the number of elements in the group What is the group with the least number of elements G e where e e e How many groups of order 2 are there e f e e f f f e Generators A set T S is said to generate the group G S if every element of S can be expressed as a finite product of elements in T Question Does R90 generate YSQ NO Question Does F R90 generate YSQ An element g S is called a generator of G S if g generates G Does YSQ have a generator NO YES Generators For Zn Any a Zn such that GCD a n 1 generates Zn Claim If GCD a n 1 then the numbers a 2a n 1 a na are all distinct modulo n …
View Full Document
Unlocking...