Discrete Mathematics (DM) Past Paper PDF

B.Tech. st Semester Discrete Mathematics (DM) DU #2101HS302 Unit – 5.2 Group Theory Prof. Punit B. Vadher Department of Humanities & Science Darshan University, Rajkot [email protected] +91 96624 43859  Looping Topics of Unit 5.2...

B.Tech. st Semester Discrete Mathematics (DM) DU #2101HS302 Unit – 5.2 Group Theory Prof. Punit B. Vadher Department of Humanities & Science Darshan University, Rajkot [email protected] +91 96624 43859  Looping Topics of Unit 5.2  Binary Operation  Group  Subgroup  Order of Group and Order of element  Cyclic Group  Outline Looping of Unit 5.2  Examples on Binary operation.  Examples on Group  Examples on sub group.  Examples on order of an elements.  Examples on cyclic group. Important Sets Natural ℕ ¿ {𝟏 ,𝟐 , 𝟑 , … } ℂ¿ { 𝐳 =𝐚 + 𝐢𝐛 : 𝐚 , 𝐛 ∈ ℝ } numbers Comple x Intege ℤ¿ {… ,−𝟏 ,𝟎,𝟏,… } rs Numbe rs S 𝐜 ℝ¿ ℚ ∪ ℚ Real et Ration Numbe al { } rs Numbe𝐩 Irratio ℚ rs¿ 𝐪 : 𝐩 , 𝐪 ∈ ℤ ; 𝐪 ≠ 𝟎 𝐜 nal ℚ Ex. Numbe rs Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 4 Important Sets  Integer modulo n  ¿ { [ 0 ] , [ 1 ] , [ 2 ] ,… , [ n − 1 ] } ……… Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 5 Important Sets Exam ple ¿ {[ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] } ¿ { x ∈ ℤ ; x=4 k ; k∈ ℤ } ¿ {… − 8 , − 4 , 𝟎 , 4 ,8 , … } ¿ { x ∈ ℤ ; x=4 k+1 ; k ∈ ℤ } ¿ {… − 7 , − 3 ,𝟏 ,5 , … } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 6 Important Sets ¿ { x ∈ ℤ ; x=4 k+2 ; k ∈ ℤ } ¿ {… − 6 , − 2 ,𝟐 ,6 , … } ¿ { x ∈ ℤ ; x=4 k+3 ; k ∈ ℤ } ¿ {… − 5 , − 1 ,𝟑 ,7 , … } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 7 Important Sets ¿ {[ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] } [ 0¿ ]{… − 8 , − 4 , 𝟎 , 4 ,8 , … } [ 1¿]{… − 7 , − 3 ,𝟏 ,5 , … } [ 2¿]{… − 6 , − 2 ,𝟐 ,6 , … } [ 3¿]{… − 5 , − 1 ,𝟑 ,7 , … } ∴ ℤ4 =¿ {𝟎 ,𝟏 , 𝟐 , 𝟑} Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 8 Method:1 Binary Operation Binary Operation  A function is known as binary operation on. i.e. if then is known as binary operation on. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 10 Examples of Binary Operation Binary Se Operati Reas Operati t on on +¿ on Yes ∀ a , b∈ ℕ , 𝐚 + 𝐛 ∈ ℕ − No as 2 , 3 ∈ ℕ ,𝟐 −𝟑=−𝟏 ∉ ℕ ℕ × Yes ∀ a , b∈ ℕ , 𝐚 × 𝐛 ∈ ℕ ÷ No as 2 , 3 ∈ ℕ ,𝟐 ÷ 𝟑 ∉ ℕ +¿ Yes ∀ a , b∈ ℤ , 𝐚 + 𝐛 ∈ ℤ − Yes ∀ a , b∈ ℤ , 𝐚 − 𝐛 ∈ ℤ ℤ × Yes ∀ a , b∈ ℤ , 𝐚 × 𝐛 ∈ ℤ ÷ No as 2 , 3 ∈ ℤ , 𝟐÷ 𝟑 ∉ ℤ Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 11 Examples of Binary Operation Binary Se Operati Reas Operati t on on +¿ on Yes ∀ a , b∈ ℚ , 𝐚 + 𝐛 ∈ ℚ − Yes ∀ a , b∈ ℚ , 𝐚 − 𝐛 ∈ ℚ ℚ × Yes ∀ a , b∈ ℚ , 𝐚 × 𝐛 ∈ ℚ ÷ No ∀ 0 , 0 ∈ ℚ , 𝟎÷ 𝟎∉ ℚ +¿ Yes ∀ a , b∈ ℝ , 𝐚 + 𝐛 ∈ ℝ − Yes ∀ a , b∈ ℝ , 𝐚 − 𝐛 ∈ ℝ ℝ × Yes ∀ a , b∈ ℝ , 𝐚 × 𝐛 ∈ ℝ ÷ No as 2 , 0 ∈ ℝ , 𝟐 ÷ 𝟎 ∉ ℝ Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 12 Method 1 Example 1 Questi on On the set, check whether is binary operation or not. (1) (2) Soluti (1) on As we know If we take and then Hence, is not a binary operation on. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 13 Method 1 Example 1 Questi on On the set, check whether is binary operation or not. (1) (2) Soluti (2) on As we know Clearly, positive power of positive integer is again a positive integer. Therefore, Hence, is a binary operation on. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 14 Algebraic Structures  A non-empty set Gequipped with one or more binary operations is known as algebraic structure.  The algebraic structure consisting of a set G and binary operations on G is denoted by Exam ple Is not algebraic structure. Since, is not binary operation on. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 15 Closure Property  A binary operation is define on a set G is known as closure, if for all. Exam ple  Addition and multiplication are closed in  Subtraction is not closed in  Division is not closed in Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 16 Associative Property  A binary operation is define on a set G is known as associative, if Exam for all. ple  (Addition) is associative over. Reason:.  (multiplication) is associative over. Reason:. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 17 Method 1 Example 2 Questi on On the set defined by and is associative or not. Soluti (1) Given, on Let, Associative ( ) a ∗ ( b ∗ c¿) a ∗ b c abc 3 ¿ 9 Property ¿( 3 ) ab abc & ¿ ∗c 9 Therefore, is associative. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 18 Method 1 Example 3 (Continue) (2) Given Let, Associative (b¿¿ c)¿ Property a ∗ ( b ∗ c ) =a ∗ ( b ¿) a c c & ¿(a¿¿b) ¿ take, but, ;. Therefore, is not associative. Clearly, Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 19 Identity (neutral or unity) Element  Let be a binary operation on G. An element G is known as identity element for the binary operation , if for all G. Exam ple  is the identity element of addition as for any.  is the identity element of Multiplication as for any. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 20 Method 1 Example 3 Questi Let be a binary operation on defined by , Examine the on identity element if exist. Soluti Suppose , e is the identity element for on a ∗ e=a e ∗ a=a Identity ⇒ a−e=a ⇒ e−a=a Element ⇒ a−a=e …(2) …(1) From equation (1) and (2) We get, Which is Therefore has contradiction. no identity element. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 21 Method 1 Example 4 Questi Let be a binary operation on defined by then find an on identity element in with respect to. Soluti Suppose, e is the identity element for on a ∗ e=a e ∗ a=a Identity ⇒ a+ e+2 ae=a ⇒ e+ a+2 ea=a Element ⇒ e+2 ae=0 ⇒ e+2 ae=0 ⇒ e ( 1+2 a ) =0 ⇒ e ( 1+2 a ) =0 ⇒ e=0 ⇒ e=0 Hence, is an identity element of with respect to. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 22 Invertible Element (Unit Element)  Let be a non-empty set. If for each there exist such that then ‘’ is known as an inverse of that is. Where, ‘’ is an identity element of  Here, is also inverse of.  Inverse of identity element is it self. Exam ple  For addition, Negative of element is inverse of that element. i.e., ; for all Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 23 Method 1 Example 5 Questi on Let be a binary operation on defined by then which elements has inverse and what are they ? Soluti Suppose that then on Identity ⇒ a∗c =0 −a Element ⇒ c= 1+ 2 a ⇒ a+ c+2 ac=0 ⇒ c+2 ac=− a Where, ⇒ c ( 1+2 a ) =− a i.e. Hence, "each element has inverse in ℝ except Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 24 Commutative Property  A binary operation is define on a set G is known as commutative, if Exam for all. ple  Any two elements in , , , , and are commutative under the binary operations addition and multiplication. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 25 Method 1 Example 6 Questi on On the set, check whether the binary operation is commutative or not. (1) (2) Soluti (2) (1) on Let, for any Let, for any Clearly, i.e. is not commutative i.e. is commutative on on the set the set Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 26 Composition Table (Cayley Table)  Let ∗ be the binary operation on set.  Follow the below steps to make composition table.  Give heading to rows and columns of table as respectively. Entry of and is. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 27 Method 1 Example 8 Questi Let and be a commutative binary operation on. on Find the missing entries in the following table. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 28 Method 1 Example 8 (Continue) Soluti on 𝐛 𝐚 𝐜 𝐝 𝐜 𝐛 Since, ⇒ b∗ a= 𝐛 (Given that is commutative on) Similarly, ⇒ c ∗ a=𝐚 Similarly, ⇒ c ∗b=𝐜 Similarly, ⇒ d ∗ b=𝐜 Similarly, ⇒ d ∗ a=𝐝 Similarly, ⇒ d ∗ c= 𝐛 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 29 Additive Modulo n  For any additive modulo n is defined as , where is remainder when is divided by n.  It is denoted by and read as “Additive modulo n”. 1 Examp 58 le 5  Additive modulo 5 : Let 3  Additive modulo 4 : Let 3 412 12 0 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 30 Multiplicative Modulo n  For any , multiplication modulo n is defined as Where remainder when is divided by n.  It is denoted by and read as “multiplication modulo n”. 2 Examp 512 le 10  Multiplicative modulo 5 : Let. 2  Multiplicative modulo 6 : Let. 3 620 18 2 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 31 Method:2 Group, Semigroup and Monoid Group  Let G be a non-empty set together with a binary operation ‘’ on , Then is known as a group if the following conditions are satisfied. 1. Closure Property 2. Associative Property 3. Existence of identity element in 4. Existence of inverse for each element of Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 33 Examples of Group Exam ple  The set of integers , the set of rational numbers , and the set of real numbers are all groups under ordinary addition. In each case, the identity is and the inverse of is. i.e.,  All algebraic structure are Group. With  identity element is and inverse of is  Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 34 Method 2 Example 1 Questi on Show that the set of cube root of unity forms a group Soluti under multiplication. − 1+ i √ 3 −1−i √3 Here, ⇒ x=1 , x= ∧ x= on 2 2 − 1 +i √ 3 2 −1−i√3 Consid , ω = ∧ω = 2 2 er Let Composition table is 2 Clai ×1 ω ω m: 1 1 ω ω 2 is a Group. ω ω ω 1 2 2 2 ω ω 1 ω Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 35 Method 2 Example 1(continue) Soluti ×1 ω ω 2 on By observing Composition table 1 1 ω ω 2 (1) Closure Property From table, any ω ω ω2 1 2 2 (2) Associative Property ω ω 1 ω From table, any (3) Existence of Identity element Clearly, is the identity element of under multiplication (4) Existence of Inverse element , ,. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 36 Method 2 Example 1(continue) Soluti on Thus, from (1), (2), (3) and (4) cube roots of unity forms a group with respect to multiplication. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 37  Method 2 Example 2 Questi on Show G = A α = { [ c os α sin α − sin α cos α is ;α a ] group } ∈ ℝunder that Matrix Soluti multiplication. Let where on A 1= [ c os α sin α − sin α cos α ] [ A,2= c os β sin β − sin β cos β , A 3= ]c os γ sin γ [ − sin γ cos γ ] (1) Closure Property A 1 ∙ A 2= c os α sinα [ cos α ∙ ][ − sin α c os β − sin β sin β cos β ] Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 38 Method 2 Example 2 (Continue) A 1 ∙ A 2= [ c os α sinα cos α ][ − sin α c os β − sin β ∙ sin β cos β ] ¿ ¿ ¿ ¿ ¿ [ c os ⁡(α+ β) sin ⁡(α+ β) − sin ⁡(α+ β) cos ⁡(α+ β) ∈G ] i.e. is closed under matrix multiplication. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 39  Method 2 Example 2 (Continue) 2) Associative Property Clearly, 3) Existence of Identity element Clearly, identity matrix is the identity element. 4) Existence of Inverse element Let, be any element of Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 40 Method 2 Example 2 (Continue) Let, be any element of As, Then, Thus, from above four conditions, is a group. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 41 Method 2 Example 3 (note : = ) Questi Check (, ) is a group or not ? on whether Soluti Here on [ 1 ] ={… ,− 9 , − 4 , 𝟏 ,6 ,11 , …} [ 2 ] ={… ,− 8 , − 3 , 𝟐 , 7 , 12 ,… } [ 3 ] ={… ,− 7 , − 2 , 𝟑 , 8 , 13 ,… } [ 4 ] ={… , − 6 , − 1 , 𝟒 , 9 , 14 , … } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 42 Method 2 Example 3 (Continue) (note : = ) Composition Table × ­5 1 2 3 From composition table we observe that, 4 1 1 2 3 (1) Closure Property 2 2 4 4 1 3 3 3 1 4 For any 4 4 2 3 2 (2) Associative Property 1 For any ⇒ a× ­5 ( b × ­5 c ) =( a × ­5 b ) × ­5 c Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 43  Method 2 Example 3 (Continue) (note : = ) ) Existence of Identity element 1 2 3 Clearly, is an identity element of × ­5 4 with respect to. 1 2 3 4 1 2 4 1 3 ) Existence of Inverse element 2 3 1 4 2 −1 −1 1 =1 3 =2 3 4 3 2 1 −1 2 =3 4 − 1=4 4 Thus, from above four conditions, is a group. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 44 Method 2 Example 4 Questi Check G =( { 5 , 15 ,25 , 3 5 } , × 40 )is a group or on whether not ? Soluti Here, on 5 15 25 Composition ×­40 5 35 25 35 5 Table 1 15 35 25 15 5 2 55 15 25 5 3 35 15 5 35 5 25 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 45  Method 2 Example 4 (Continue) 5 15 25 m composition table we observe that, ×­40 5 35 25 35 5 (1) Closure Property 1 15 35 25 15 5 55 For any 2 15 25 5 3 35 15 5 35 (2) Associative Property 5 25 For any ⇒ 𝐚 × ­𝟒𝟎 ( 𝐛 × ­𝟒𝟎 𝐜 ) =( 𝐚 × ­𝟒𝟎 𝐛 ) ×­𝟒𝟎 𝐜 3) Existence of Identity element From composition table we observe that, is the identity element. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 46  Method 2 Example 4 (Continue) ×­40 5 15 25 35 ) Existence of Inverse element 5 25 35 5 1 15 35 25 15 −1 25 =25asis the identity element 5 2 55 15 25 −1 5 =5 −1 5 3 35 15 5 35 5 25 15 =15 −1 35 =35 Thus, from above four conditions, is a group. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 47 Semigroup  Let G be a non-empty set together with a binary operation ‘’ on , Then is known as a semigroup if the following conditions are satisfied. 1. Closure Property 2. Associative Property Examp  One thing is clear that all group are semigroup. le  Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 48 Method 2 Example 5 Questi Let be a binary operation on defined by is on semigroup? Soluti Given that, on (1)Closure Property Let a∗ b=a+b+2 ab∈ ℝ is closed under Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 49 Method 2 Example 5 (Continue) (1)Associative a∗ b=a+b+2 ab Property L.H.S. L.H.S. L.H.S. L.H.S. L.H.S.. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 50 Method 2 Example 5 (Continue) (1)Associative a∗ b=a+b+2 ab Property R.H.S. i.e. is associative over. Hence, is a semigroup. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 51 Monoid  Let G be a non-empty set together with a binary operation ‘’ on , Then is known as a monoid if the following conditions are satisfied. 1. Closure Property 2. Associative Property 3. Existence of identity Examp  One thing is clear that all group are monoid. le  Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 52 All Definitions Together Let be a non-empty set and ‘∗’ be an operation define on. is closed under (G, ) is Semi Group ‘∗’. (G, ) is (G, ) is ‘∗’ is associative (G, ) Monoi Commutati is over. d ve Group Grou p OR Abelian There exist an identity element of under ‘∗’. Group There exist an inverse for each element of under ‘∗’. ‘∗’ is commutative over. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 53 Think ! Questi on Check whether the following algebraic structures are Abelian group or not. ( 𝟏𝟔 ) ( ℤ4 , ×4 ) ( 𝟐) ¿ ( 𝟕 ) ( ℤ , ×) ( 𝟏𝟐 ) ( { − 1 ,1 } , × ) ( 𝟏𝟕 ) ( ℤ7 , ×7 ) ( 𝟑) ¿ ( 𝟖 )( ℚ , × ) ( 𝟏𝟑 ) ( ℚ − { 0 } ,× ) ( 𝟏𝟖 ) ¿ (𝟒 ) ¿ ( 𝟗 ) ( ℝ , ×) ( 𝟏𝟒 ) ( ℝ − {0 } , × ) ( 𝟏𝟗 ) ¿ ( 𝟓) ¿ ( 𝟏𝟎 ) ( ℂ , × ) ( 𝟏𝟓 ) ( ℂ − { 0 } , × ) ( 𝟐𝟎 ) ( ℤ8 , × 8 ) Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 54 Method:3 sub group Subgroup  Let be a group and H be non empty subset of. If forms a group then is a subgroup of. it is denoted as  For any group , and are always subgroup of. Exampl es    Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 56 Subgroup (Important Notes) (1) Every group has at least two subgroup (improper subgroup ). Which are (1) identity & (2) Group itself. (2) If and are two subgroups of a group G, then ∩ is also a subgroup of G. (3) The union of two subgroups is not necessarily a subgroup. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 57 Method 3 Example 1 Questio Find all subgroups of (). n Solutio n We know that Step - & 1 Step - Divisor of : 2 Step - Make subgroup of order 3 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 58 Method 3 Example 1 (Continue) Step - Make subgroup of order 3 H 3 =⟨ 1 ⟩ Process : 1 1 =1 2 1 =¿𝟏+¿ 12 𝟏¿¿ 2 3 𝟏+¿ 12 𝟏+¿ 12 𝟏¿¿¿ 3 1 =¿ 4 𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏¿¿¿¿ 4 1 =¿ Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 59 Method 3 Example 1 (Continue) Process : 5 1 =¿𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏¿¿¿ ¿¿ 5 1 =¿𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏¿ ¿¿¿¿ ¿ 6 6 1 =¿𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿12 𝟏¿¿¿¿¿¿¿ 7 7 1 =¿ 𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏¿¿¿¿ ¿¿¿¿ 8 8 1 =¿𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏¿¿ ¿¿¿¿¿¿¿ 9 9 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 60 Method 3 Example 1 (Continue) Process : 1 =¿𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿ 12 𝟏¿¿¿¿¿¿¿ ¿¿¿ 10 10 1 =¿𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿12 𝟏+¿12 𝟏+¿ 12 𝟏+¿ 12 𝟏+¿12 𝟏¿¿¿¿¿ ¿¿¿¿¿¿ 11 11 12 1 =12¿ 0 ∴ H 3= ⟨ 1¿⟩{0 ,1,2,3,4 ,5 ,6,7,8,9 ,10 ,11 } ¿ ℤ 12 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 61 Method 3 Example 1 (Continue) H 4 = ⟨ 2¿⟩ {0 , 2 , 4 , 6 , 8 , 10 } Process :1 2 =2 2 =¿𝟐+¿ 12 𝟐¿¿ 4 2 2 =¿𝟐+¿ 12 𝟐+¿ 12 𝟐¿¿¿ 6 3 2 =¿𝟐+¿ 12 𝟐+¿ 12 𝟐+¿12 𝟐¿¿¿¿ 8 4 5 2 =¿𝟐+¿ 12 𝟐+¿ 12 𝟐+¿12 𝟐+¿12 𝟐¿¿¿ ¿¿ 10 6 2 =¿𝟐+¿ 12 𝟐+¿ 12 𝟐+¿12 𝟐+¿12 𝟐+¿ 12 𝟐¿ ¿¿¿¿¿ 12¿ 0 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 62 Method 3 Example 1 (Continue) H 5 =⟨ 3 ⟩ Process :1 3 =3 3 =¿𝟑 +¿ 12 𝟑 ¿¿ 6 2 3 3 =¿𝟑+¿ 12 𝟑+¿ 12 𝟑¿¿¿ 9 3 =¿𝟑+¿ 12 𝟑+¿ 12 𝟑+¿12 𝟑¿¿¿¿ 12¿ 0 4 H 5 =⟨ 3¿⟩ {0 , 3 , 6 , 9 } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 63 Method 3 Example 1 (Continue) H 6 =⟨ 4 ⟩ Process :1 4 =4 2 4 =¿𝟒 +¿ 12 𝟒 ¿¿ 8 4 =¿𝟒+¿ 12 𝟒+¿ 12 𝟒 ¿¿¿ 12¿ 0 3 H 4 = ⟨ 4¿⟩ {0 , 4 , 8 } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 64 Method 3 Example 1 (Continue) H 5 =⟨ 6 ⟩ Process :1 6 =6 2 6 =¿𝟔 +¿ 12 𝟔 ¿¿ 12 ¿ 0 H 5 =⟨ 6¿ ⟩ {0 , 6 } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 65 Method 3 Example 2 Questi on Show that is a subgroup of Solutio W.K.T n Clearly, here H (Say) Claim : Composition ×𝟏𝟕 1 4 13 Table 16 1 1 4 13 16 4 16 1 13 13 1 16 4 4 16 13 4 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 66  Method 3 Example 2 (1) Closure ×17 1 4 13 Property 16 For any 1 1 4 13 16 (2) Associative 4 16 1 Property 13 For any 13 1 16 4 ⇒ 𝐚 × ­𝟏𝟕 ( 𝐛 ×­𝟏𝟕 𝐜 ) =( 𝐚 × ­𝟏𝟕 𝐛 ) × ­𝟏𝟕 𝐜 4 16 13 4 1 1 3) Existence of Identity element 3 Clearly 1 is the identity element of 1 6 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 67  Method 3 Example 2 (Continue) ) Existence of Inverse element ×17 1 4 13 −1 −1 16 1 =1 16 =16 1 1 4 13 −1 −1 4 =13 13 =4 16 4 16 1 13 13 1 16 Thus, from the above conditions, 4 4 16 13 4 is a subgroup of. 1 1 3 1 6 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 68 Method:4 Abelian Group Abelian Group (Commutative Group)  Let G be a non-empty set together with a binary operation ‘’ on , Then is known as a group if the following conditions are satisfied. 1. Closure Property 2. Associative Property 3. Existence of identity element in 4. Existence of inverse for each element of 5. Commutative Property Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 70  Method 4 Example 1 Questi Show that forms an Abelian group. Where, defined on by. Soluti on 1) Closure Property (2) Associative Property for any, Claim: for any, ab + ¿¿ L.H.S a ∗ b= ∈ℚ ( ) 2 bc ¿ abc ¿a ∗ L.H.S R.H.S is closed under. 2 4 Prof. Punit B. Vadher R.H.S ¿ ab 2 ∗¿c abc 4 ( ) #2101HS302(DM)   Unit 5 – Group Theory 71  Method 4 Example 1 (continue) ) Existence of Identity element (4) Existence of Inverse element such that Suppose that then ae ⇒ =a 2 ⇒ a∗c =2 ⇒ e=2 ac ⇒ =2 Hence, is an identity element 2 4 +¿ ¿ of with respect to. ⇒ c= ∈ ℚ a −1 4 ∴ a =c= a is an inverse of from. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 72  Method 4 Example 1 (continue) 5) Commutative Property Clai ∀ a , b ∈ ℚ+ ¿ ⇒ a ∗ b=b ∗ a ¿ m: L.H.S. ab ¿ 2 ba ¿ 2 R.H.S Hence, from above five conditions… is a commutative group. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 73 Method 4 Example 2 Questi on Show ¿ is an Abelian that group. Soluti Here, on [ 0 ] ={… ,− 12 , − 6 , 𝟎 ,6 ,12 , … } [ 1 ] ={… ,− 11 , − 5 , 𝟏 , 7 ,13 , … } [ 2 ] ={… ,− 10 , − 4 ,𝟐 ,8 , 14 , … } [ 3 ] ={… , − 9 , − 3 , 𝟑 , 9 , 15 , … } [ 4 ] ={… , − 8 , − 2 , 𝟒 , 10 , 16 ,… } [ 5 ] ={… ,− 7 , − 1 , 𝟓 , 11 ,17 , … } Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 74 Method 4 Example 2 (Continue) Composition ℤ6 ={0 , 1 , 2 , 3 , 4 , 5 } 6 0 +­ 1 2 3 Table 4 0 0 5 1 2 3 1 14 25 3 4 2 25 30 4 5 3 30 41 5 0 4 41 52 0 1 5 52 03 1 2 3 4 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 75  Method 4 Example 2 (continue) om composition table we observe that, (1) Closure Property For any (2) Associative Property For any 3) Existence of Identity element Clearly, is an identity element of with respect to. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 76  Method 4 Example 2 (continue) ) Existence of Inverse element −1 0 =0 2 −1 =4 4 −1 =2 −1 −1 −1 1 =5 3 =3 5 =1 5) Commutative Property For any ⇒ ¿ Hence, from above five condition is an Abelian group. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 77 Method:5 Order of Group and Order of Elements Order of a Group  The number of elements of a group is known as order of group.  We will use to denote the order of. Examp le 1. If group then. 2. If group then. 3. If group then. 4. If group is the set of cube root of unity under multiplication then,. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 79 Order of an elements  The order of an element a in group is the smallest positive integer such that. (In additive notation, this would be.)  If no such integer exists, we say that has infinite order.  The order of an element is denoted by.  The order of identity element is always 1. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 80 Method 5 Example 1 Questi Find order of each elements of (, ) on Solutio n Here 1 as 0 is the identity element Order of 1 I.e., one time one 𝐧 =𝟏 ⇒𝟏 ⋅ 𝟏 ¿ 𝟏≠ 𝟎 I.e., Two times one 𝐧 =𝟐 ⇒𝟐 ⋅𝟏¿ 𝟏 +¿ 10 𝟏 ¿¿ 𝟐 ≠ 𝟎 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 81 Method 5 Example 1 (Continue) 𝐧 =𝟑⇒ 𝟑 ⋅ 𝟏¿ 𝟏+¿ 10 𝟏+¿10 𝟏¿ ¿¿ 𝟑≠ 𝟎 𝐧 =𝟒⇒ 𝟒⋅ 𝟏 ¿ 𝟒≠ 𝟎 𝐧 =𝟓⇒ 𝟓 ⋅ 𝟏 ¿ 𝟓≠ 𝟎 𝐧 =𝟔⇒ 𝟔 ⋅ 𝟏 ¿ 𝟔≠ 𝟎 𝐧 =𝟕⇒ 𝟕 ⋅ 𝟏 ¿ 𝟕≠𝟎 𝐧 =𝟖⇒ 𝟖 ⋅ 𝟏 ¿ 𝟖≠𝟎 𝐧 =𝟗⇒ 𝟗 ⋅ 𝟏 ¿ 𝟗≠ 𝟎 𝐧 =𝟏𝟎⇒𝟏𝟎 ⋅𝟏 ¿ 𝟏𝟎¿ 𝟎 ∴|𝟏|=𝟏𝟎 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 82 Method 5 Example 1 (Continue) Order of 𝐧 =𝟏 ⇒𝟏 ⋅ 𝟐 ¿ 𝟐≠ 𝟎 𝐧 =𝟐 ⇒𝟐 ⋅𝟐¿ 𝟐 +¿ 10 𝟐 ¿¿ 𝟒 ≠ 𝟎 𝐧 =𝟑⇒ 𝟑 ⋅ 𝟐¿ 𝟐+¿ 10 𝟐+¿10 𝟐¿ ¿¿ 𝟔≠ 𝟎 𝐧 =𝟒⇒ 𝟒⋅ 𝟐 ¿ 𝟖≠ 𝟎 𝐧 =𝟓⇒ 𝟓 ⋅ 𝟐 ¿ 𝟏𝟎¿ 𝟎 ∴|𝟐|=𝟓 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 83 Method 5 Example 1 (Continue) Order of 𝐧 =𝟏 ⇒𝟏 ⋅ 𝟑 ¿ 𝟑≠ 𝟎 𝐧 =𝟐 ⇒𝟐 ⋅𝟑¿ 𝟑 +¿ 10 𝟑 ¿¿ 𝟔 ≠ 𝟎 𝐧 =𝟑⇒ 𝟑 ⋅ 𝟑¿ 𝟑+¿ 10 𝟑+¿10 𝟑¿ ¿¿ 𝟗≠ 𝟎 𝐧 =𝟒⇒ 𝟒⋅ 𝟑 ¿ 𝟐≠ 𝟎 𝐧 =𝟓⇒ 𝟓 ⋅ 𝟑 ¿𝟓≠𝟎 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 84 Method 5 Example 1 (Continue) 𝐧 =𝟔⇒ 𝟔 ⋅ 𝟑 ¿ 𝟖≠ 𝟎 𝐧 =𝟕⇒ 𝟕 ⋅ 𝟑 ¿ 𝟏≠𝟎 𝐧 =𝟖⇒ 𝟖 ⋅ 𝟑 ¿ 𝟒≠𝟎 𝐧 =𝟗⇒ 𝟗 ⋅ 𝟑 ¿ 𝟕≠ 𝟎 𝐧 =𝟏𝟎⇒𝟏𝟎 ⋅𝟏 ¿𝟎 ∴|𝟑|=𝟏𝟎 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 85 Method 5 Example 1 (Continue) Similarly we can find order of remaining elements Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 86 Method 5 Example 2 Questi Find order of each elements of (, ) on Solutio Here n Here binary operation is multiplicative modulo Therefore , is the identity element. so, order of is. Order of 2 𝟐 𝟐 =¿𝟐 ×7 𝟐=¿𝟒≠𝟏 𝟏 𝟐 =𝟐≠ 𝟏 𝟑 ∴|𝟐|=𝟑 𝟐𝟖=𝟏 𝟐 =𝟐 × 7 𝟐 × 7¿ Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 87 Method 5 Example 2 (Continue) Order of 3 𝟏 𝟑 =¿𝟑≠𝟏 𝟐 𝟑 =𝟑 ¿ ×7 𝟑¿ 𝟗≠ 𝟏 𝟑 𝟑 =¿𝟑 ×7 𝟑 ×7 𝟑¿ 𝟐𝟕 ≠𝟏 𝟒 𝟑 =¿𝟑 ×7 𝟑 ×7 𝟑 ×7 𝟑¿ 𝟖𝟏≠ 𝟏 𝟓 𝟑 =¿𝟑 ×7 𝟑 ×7 𝟑 ×7 𝟑× 7 𝟑¿ 𝟐𝟒𝟑≠𝟏 𝟑 =¿𝟑 ×7 𝟑 ×7 𝟑 ×7 𝟑× 7 𝟑× 7 𝟑¿ 𝟕𝟐𝟗 ¿ 𝟏 𝟔 ∴|𝟑|=𝟔 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 88 Method 5 Example 2 (Continue) Order of 4 Similarly, we can find the order of 𝟏 remaining elements. 𝟒 =¿𝟒 ≠ 𝟏 𝟐 𝟒 =¿𝟒 × 7 𝟒 ¿ 𝟏𝟔≠𝟏 𝟑 𝟒 =¿𝟒 × 7 𝟒 × 7 𝟒¿ 𝟔𝟒¿ 𝟏 ∴|𝟒|=𝟏 Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 89 Method 5 Example 3 Questi Find order of each elements of (, ) on Solutio Here n Here binary operation is addition Therefore , is the identity element. so, order of is. 𝐧 +¿¿ Now, take ∋ 𝐚 =𝟎 ; 𝐧 ∈ ℤ Clearly, any , Therefore, order of all non zero element in are Infinite. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 90 Method:6 cyclic group Cyclic group  A group is said to be cyclic group if there exist an element such that every element of G can be written as some power of ‘a’. i.e., Note:. Where, a is called generator of. is always cyclic group. The number of generators of are relatively prime is to n. cyclic group then it is abelian. But, converse may not be true. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 92 Method 6 Example 1 Questio Prove that is cyclic group. n Solutio We know that, is a group. n Take, Now, , , Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 93  Method 6 Example 1 (Continue) , ∴ ⟨ 𝟏 ⟩ ={ 0 ,1 ,2 , 3 , 4 ,5 }=G i.e. 1 is generator of. Take, 𝟏 𝟐 =𝟐 , , Here, 2 produce only three elements of group. 𝟑 𝟐 =𝟐 + ¿6 𝟐+ ¿6 𝟐=𝟔=𝟎 ¿ ¿ Therefore 2 is not generator of. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 94 Method 6 Example 1 (Continue) Take, 𝟏 𝟑 =𝟑 , Here, 3 produce only two elements 𝟐 of group. 𝟑 =𝟑+¿6 𝟑=𝟔=𝟎¿ Therefore 3 is not generator of. Take, 𝟏 𝟒 =𝟑 , 𝟐 𝟒 =𝟒+¿ 6 𝟒=𝟖¿ Here, 4 produce only three 𝟑 elements of group. 𝟒 =𝟒 +¿ 6 𝟒+ ¿6 𝟒=𝟏𝟐=𝟎 ¿ ¿ Therefore 4 is not generator of. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 95  Method 6 Example 1 (Continue) Take, , 𝟑 𝟓 =𝟓 + ¿6 𝟓+ ¿6 𝟓=𝟏𝟓=𝟑 ¿ ¿ 𝟒 𝟓 =𝟓 +¿6 𝟓 +¿ 6 𝟓 +¿ 6 𝟓=𝟐𝟎=𝟐 ¿ ¿ ¿ 𝟓 𝟓 =𝟓 +¿6 𝟓+¿6 𝟓 +¿6 𝟓 +¿ 6 𝟓=𝟐𝟒=𝟏 ¿ ¿ ¿ ¿ 𝟔 𝟓 =𝟓 +¿6 𝟓+¿6 𝟓 +¿6 𝟓 +¿ 6 𝟓 +¿ 6 𝟓=𝟑𝟎=𝟎 ¿ ¿ ¿ ¿ ¿ ∴ ⟨ 𝟓 ⟩ ={ 0 ,1 ,2 , 3 , 4 ,5 }=G i.e. 5 is generator of Prof. Punit B. Vadher #2101HS302(DM)  . Unit 5 – Group Theory 96 Method 6 Example 1 (Continue) Thus, has two generators. &. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 97 Method 6 Example 2 Questio Find all the generators of cyclic groups n solutio n (a) We know that Here, 5 is a prime number. So all the numbers in are relatively prime to 5 Except 0. generators of are 1, 2, 3, 4. Therefore, Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 98 Method 6 Example 2 (Continue) (b) We know that Here, 6 is not a prime. But 1 and 5 are relatively prime to 6. Therefore, 1 and 5 are the generators of. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 99 Method 6 Example 3 Questio Prove that third root of unity is cyclic group. n solutio We know that third root of unity is group with n multiplication.. Here where Clearly, 1 is not generator of group as it is identity element of group. Take, − 1+i √ 3 ω 3=ω 2 ⋅ ω= − 1 − i √ 3 ⋅ − 1+i √ 3 =1 1 ω =ω= 2 2 2 −1−i √3 2 So, is generator of. ω = 2 Hence it is cyclic group. Prof. Punit B. Vadher #2101HS302(DM)   Unit 5 – Group Theory 100  B.Tech. st Semester Discrete Mathematics (DM) DU #2101HS302 THA NK YOU Prof. Punit B Vadher Department of Humanities & Science Darshan University, Rajkot [email protected] 9727747320