文档介绍：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
§§§ Definition, Examples, and
Elementary Properties (1)
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
§§§ Definition, Examples, and Elementary Properties
Def :
• G: a nonempty set; 。。。: a binary operation of G
then ( G,。。。) is called a group ≡≡≡
111 ∀∀∀ a, b ∈∈∈ G, a。。。b ∈∈∈ G (Closure of G under 。。。)
222 ∀∀∀ a, b, c ∈∈∈ G, a。。。(b。。。c) = ( a。。。b)。。。c (The Associative Property)
333 ∃∃∃ e ∈∈∈ G, . a。。。e = e。。。a = a, ∀∀∀ a ∈∈∈ G (The Existence of an Identity)
444 ∀∀∀ a ∈∈∈ G, ∃∃∃ b ∈∈∈ G . a。。。b = b。。。a = e (Existence of Inverses)
• If 555 ∀∀∀ a, b ∈∈∈ G, a。。。b = b。。。a hold, then
G is called mutative (or abelian) group.
Note : ∀∀∀ r, n ∈∈∈ Z+, with n ≥≥≥ 3, and 1 ≤≤≤ r < n:
(a1。。。a2。。。a3。。。…。。。ar)。。。(ar+1 。。。…。。。an) = a1。。。a2。。。…。。。ar。。。ar+1 。。。…。。。an
∈∈∈
where a1, a2, …, an G.
(c) Spring 2007, Justie Su-Tzu Juan 2
§§§ Definition, Examples, and Elementary Properties
Ex :111 For ordinary addition +: ( Z, +), ( Q, +), ( R, +), ( C, +) are the
abelian groups.
222 For ordinary multiplication ⋅⋅⋅: Each ( Z, ⋅⋅⋅), ( Q, ⋅⋅⋅), ( R, ⋅⋅⋅), ( C, ⋅⋅⋅) is
not an abelian group: ∵∵∵ 0 has no inverse.
333 For ordinary multiplication: let Q* = Q −−−{0}, R* = R −−−{0},
C* = C −−−{0}, then each ( Q*, ⋅⋅⋅), ( R*, ⋅⋅⋅), ( C*, ⋅⋅⋅) is an abelian
group.
Note : 111 If ( R, +, ⋅⋅⋅) is a ring ⇒⇒⇒(R, +) is an abelian group.
222 If ( F, +, ⋅⋅⋅) is a field
⇐⇐⇐⇒⇒⇒(F, +) is an abelian group.
(F*, ⋅⋅⋅) is an abelian group, where F* = F −−−{0},
0: the zero element of ( F, +, ⋅⋅⋅).
∀∀∀ a, b, c ∈∈∈ F, a ⋅⋅⋅(b + c) = a ⋅⋅⋅ b + a ⋅⋅⋅ c
(c) Spring 2007, Justie Su-Tzu Juan 3
§§§ Definition, Examples