Transcript Finite Groups & Subgroups

Finite Groups & Subgroups
Order of a group
• Definition:
The number of elements of a group
(finite or infinite) is called its order.
• Notation:
We will use |G| to denote the order of
group G.
Examples
|D4| =
|Dn| =
|<R90>| =
|Zn| =
|U(8)| =
|U(11)| =
|Z| =
8
2n
4
n
4
10
∞
Order of an element
• Definition:
The order of an element g in a group G is the
smallest positive integer n such that
gn = e (In additive notation, ng = 0).
If no such integer exists, we say g has
infinite order.
• Notation:
The order of g is denoted |g|.
Examples
In D4, |R90| =
In D4, |H| =
In Z10, |4| =
In Z11, |4| =
In U(8), |5| =
In U(9), |5| =
In Z, |1| =
4 ( R490 = R0)
2 ( H2 = R 0 )
5 (5•4 mod 10 = 0)
11 (11•4 mod 11 = 0)
2 (52 mod 8 = 1)
6 {5, 7, 8, 4, 2, 1}
∞ (n•1 ≠ 0 for n>0)
Group G (•mod 35)
•
5
10
15
20
25
30
5
25
15
5
30
20
10
10
15
30
10
25
5
20
15
5
10
15
20
25
30
20
30
25
20
15
10
5
25
20
5
25
10
30
15
30
10
20
30
5
15
25
|G| =
e =
|5| =
|10| =
|15| =
|20| =
|30| =
6
15
6
6
1
2
3
Subgroups
• Definition:
If a subset H of a group G is itself a
group under the operation of G, then
we say that H is a subgroup of G.
Notation:
• We write H ≤ G to mean H is a
subgroup of G.
• If H is not equal to G, we write H < G.
We say H is a proper subgroup of G.
• {e} is called the trivial subgroup.
All other subgroups are nontrivial.
R90  D4
•
R0
R90 R180 R270
H
V
D
D'
R0 R0 R90 R180 R270 H
V
D
D'
R90 R90 R180 R270 
R0 D'
D
H
V
R180 R180 R270 R0 R90 V
H
D'
D
R270 R270 R0 R90 R180 D
D'
V
H
H
H
D
V
D' R0 R180 R90 R270
V
V
D'
H
D R180 R0 R270 R90
D
D
V
D'
H R270 R90 R0 R180
D'
D'
H
D
V R90 R270 R180 R0
R180  R90  D4
•
R0
R90 R180 R270
R0 R0 R90
R90 R90 R180

R180 R180 R270
R270 R270 R0
H
H
D
V
V
D'
D
D
V
D'
D'
H
H
V
D
D'
R180 R270 H
V
D
D'
R270 R0 D'
D
H
V
R0 R90 V
H
D'
D
R90 R180 D
D'
V
H
V
D' R0 R180 R90 R270
H
D R180 R0 R270 R90
D'
H R270 R90 R0 R180
D
V R90 R270 R180 R0
R0  R180  R90  D4
•
R0
R90 R180 R270
H
V
D
D'
R0 R0 R90 R180 R270 H
V
D
D'
R90 
R90 R180 R270 R0 D'
D
H
V
R180 R180 R270 R0 R90 V
H
D'
D
R270 R270 R0 R90 R180 D
D'
V
H
H
H
D
V
D' R0 R180 R90 R270
V
V
D'
H
D R180 R0 R270 R90
D
D
V
D'
H R270 R90 R0 R180
D'
D'
H
D
V R90 R270 R180 R0
{R0 ,R180 ,H,V}  D4
•
R0
R90 R180 R270
H
V
D
D'
R0 R0 R90 R180 R270 H
V
D
D'
R90 R90 R
R0 D'
D
H
V
180 R270
R180 R180 R270 R0 R90 V
H
D'
D
R270 R270 R0 R90 R180 D
D'
V
H
H
H
D
V
D' R0 R180 R90 R270
V
V
D'
H
D R180 R0 R270 R90
D
D
V
D'
H R270 R90 R0 R180
D'
D'
H
D
V R90 R270 R180 R0
{R0 ,R180 ,D,D'}  D4
•
R0
R90 R180 R270
H
V
D
D'
R0 R0 R90 R180 R270 H
V
D
D'
R90 R90 R
R0 D'
D
H
V
180 R270
R180 R180 R270 R0 R90 V
H
D'
D
R270 R270 R0 R90 R180 D
D'
V
H
H
H
D
V
D' R0 R180 R90 R270
V
V
D'
H
D R180 R0 R270 R90
D
D
V
D'
H R270 R90 R0 R180
D'
D'
H
D
V R90 R270 R180 R0
{R0 ,H,V} not a subgroup of D4
•

R0
R90 R180 R270
H
V
D
D'
R0 R0 R90 R180 R270 H
V
D
D'
R90 R90 R180 R270 R0 D'
D
H
V
R180 R180 R270 R0 R90 V
H
D'
D
R270 R270 R0 R90 R180 D
D'
V
H
H
H
D
V
D' R0 R180 R90 R270
V
V
D'
H
D R180 R0 R270 R90
D
D
V
D'
H R270 R90 R0 R180
D'
D'
H
D
V R90 R270 R180 R0
Subgroup tests
• Three important tests tell us if a
nonempty subset of a group G is a
subgroup of G.
• One-Step Subgroup Test
• Two-Step Subgroup Test
• Finite Subgroup Test
One-Step Test
Let H be a nonempty subset of a group
G.
If ab-1 belongs to H whenever a and b
belong to H, then H is a subgroup of G.
(In additive groups:
If a–b belongs to H whenever a and b
belong to H, then H ≤ G.)
Proof of One Step Test.
• Let G be a group, and H a nonempty subset
of G. Suppose
ab-1 is in H whenever a and b are in H. (*)
We must show:
1. In H, multiplication is associative
2. The group identity e is in H
3. H has inverses
4. H is closed under the group multiplication.
Then, H must be a subgroup of G.
(1) Multiplication is
Associative:
• Choose any elements a, b, c in H.
• Since H is a subset of G, these
elements are also in the group G, so
(ab)c = a(bc) as required.
(2) H contains e
• Choose any x in H.
(Since H is nonempty there has to be
some element x in H)
• Let a = x and b = x.
Then a and b are in H, so by (*)
ab-1 = xx-1 = e is in H, as required.
(3) H has inverses
• Choose any x in H.
• Let a = e and b = x.
Since a and b are in H,
ab-1 = ex-1 = x-1 must be in H as well.
(4) H is closed
•
•
•
Choose any x and y in H.
Let a = x and b = y-1.
Since a and b are in H,
ab-1 = x(y-1)-1 = xy is also in H.
We have shown that H is closed under the
multiplication in G, and that H is
associative, contains the identity, and has
inverses.
Therefore, H is a subgroup of G.
To use the One-Step
Test
1. Identify the defining property P that
distinguishes elements of H.
H≠
2. Prove the identity has property P.
3. Assume that two elements have a,b in H
property P
-1 in H
-1
ab
4. Show that ab has property P.
Then by the one-step test, H ≤ G.
Example: One Step
• Prove: Let G be an Abelian group with
identity e.
Let H = {x |x2 = e}. Then H ≤ G.
• Proof: e2 = e, so that H is nonempty.
Assume a, b in H. Then
(ab-1)2 = a(b-1a)b-1 = aab-1b-1 (G is Abelian)
= a2b-2 = a2(b2)-1
= ee-1 (since a and b in H)
= e.
By the one-step test, H ≤ G.
Example One-Step
• Prove: The set 3Z = {3n | n in Z} (i.e.
the integer multiples of 3) under the
usual addition is a subgroup of Z.
• Proof: 0 = 3•0, so 3Z is not empty.
• Assume 3a and 3b are in 3Z.
• Then 3a – 3b = 3(a–b) is in 3Z.
• By the One-Step test, 3Z ≤ Z.
Terminology
• Let H be a nonempty subset of a group G
with operation *.
• We say
"H is closed under *" or "H is closed"
when we mean
"ab is in H whenever a and b are in H"
• We say
"H is closed under inverses"
when we mean
"a-1 is in H whenever a is in H"
Two Step Test
• Let H be a nonempty subset of group G with
operation *. If (1) H is closed under * and
(2) H is closed under inverses, then H ≤ G
• Proof: Assume a and b are in H.
By (2), b-1 is in H.
By (1) ab-1 is in H.
By the one-step test, H ≤ G.
Finite Subgroup Test
• Let H be a nonempty finite subset of a
group G. If H is closed under the
operation of G, then H ≤ G.
• Proof. Choose any a in H.
By the two step test, it only remains to
show that a-1 is in H.
To show a-1 is in H
If a = e, then a-1 (= e) is in H.
If a ≠ e, consider the sequence a,a2,a3…
Since H is closed, all are in H.
Since H is finite, not all are unique.
Say ai = aj where i < j.
Cancel ai to get e = aj-i.
Since a ≠ e, j-i > 1.
Let b = aj-i-1.
Then ab = a1 aj-i-1 = aj-i = e
So b = a-1 and b belongs to H.
Definition
• Let a be an element of a group G.
The cyclic group generated by a,
denoted <a> is the set of all powers of
a.
That is, <a> = {an | n is an integer}
• In additive groups,
<a> = {na | n is a integer}
<a> is a subgroup
• Let G be group, and let a be any element of
G.
Then <a> is a subgroup of G.
• Proof: a is in <a>, so <a> is not empty.
Choose any x = am and y = an in <a>.
xy–1= am(an)-1 = am-n which belongs to <a>
since m–n is an integer.
By the one-step test, <a> is a subgroup of G.
Example
•
5
10
15
20
25
30
5
25
15
5
30
20
10
10
15
30
10
25
5
20
15
5
10
15
20
25
30
20
30
25
20
15
10
5
25
20
5
25
10
30
15
30
10
20
30
5
15
25
• <25> =
Example
•
5
10
15
20
25
30
5
25
15
5
30
20
10
10
15
30
10
25
5
20
15
5
10
15
20
25
30
20
30
25
20
15
10
5
25
20
5
25
10
30
15
30
10
20
30
5
15
25
• <25> =
{25, 30, 15}