文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-Tzu Juan
Chapter 16 Groups, Coding Theory,
and Polya’s Method of Enumeration
§§§ Homomorphisms, Isomorphisms,
and Cyclic Groups (2)
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5 th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-Tzu Juan 1
§§§ Homomorphisms, Isomorphisms, and Cyclic Groups
Def : A group G is called cyclic if ∃∃∃ x ∈∈∈ G .
∀∀∀ a ∈∈∈ G, a = xn for some n ∈∈∈ Z.
Ex : (a) H = ( Z4, +) is cyclic. (∵∵∵ the operation is addition.)
Sol.
1 ⋅⋅⋅[3] = [3], 2 ⋅⋅⋅[3] = [3] + [3] = [2] ( ∴∴∴ multiples instead of powers)
3 ⋅⋅⋅[3] = [1], 4 ⋅⋅⋅[3] = [0] ⇒⇒⇒ H = 〈〈〈[3] 〉〉〉(= 〈〈〈[1] 〉〉〉)
. [1], [3] generate H.
⋅⋅⋅
(b) ( U9) = ({1, 2, 4, 5, 7, 8}, ) in is cyclic.
Sol.
1 2 3 4 5 6
2 = 2, 2 = 4, 2 = 8, 2 = 7, 2 = 5, 2 = 1 ∴∴∴ U9 = 〈〈〈2〉〉〉
1 2 3 4 5 6
∵∵∵ 5 = 5, 5 = 7, 5 = 8, 5 = 4, 5 = 2, 5 = 1 ∴∴∴ U9 = 〈〈〈5〉〉〉
(c) Spring 2007, Justie Su-Tzu Juan 2
≠≠≠φφφ⊆⊆⊆⋅⋅⋅⇔
Thm : H and H G: ( Hi) is a subgroup of ( G, )
§§§ Homomorphisms, Isomorphisms,a) ∀∀∀ a, b ∈∈∈ H, ab ∈∈∈andH. Cyclic Groups
b) ∀∀∀ a ∈∈∈ H, a−−−1 ∈∈∈ H.
Def : Given a group G, let a ∈∈∈ G, the set S = { ak | k ∈∈∈ Z} is called the
subgroup generated by a and is designated by 〈〈〈a〉〉〉.
Note : By Thm , S is a subgroup of G.
Ex: 111 In Ex , G = 〈〈〈i〉〉〉 or 〈〈〈−−−i〉〉〉; 〈〈〈−−−i〉〉〉= { −−−1, 1}; 〈〈〈1〉〉〉= {1}
222 In Ex (a) , H = 〈〈〈[1] 〉〉〉= 〈〈〈[3] 〉〉〉;
〈〈〈[2] 〉〉〉= {0, 2};
〈〈〈[0] 〉〉〉= {[0]};
333 In Ex (b) , U9 = 〈〈〈2〉〉〉= 〈〈〈5〉〉〉;
〈〈〈4〉〉〉= {1, 4, 7} = 〈〈〈7〉〉〉;
〈〈〈8〉〉〉= {1, 8};
〈〈〈1〉〉〉= {1}.
(c) Spring 2007, Justie Su-Tzu Juan 3
§§§ Homomorphisms, Isomorphisms, and Cyclic Groups
Def : If G is a group and a ∈∈∈ G,
111 o(a) ≡≡≡|〈〈〈a〉〉〉|, the order of a.
222 If | 〈〈〈a〉〉〉| is infinite, we say that a has infini