700
Modeling Arithmetic, Computation, and Languages
If 3G, # 4 is a group with identity i, then it is true that 3 5i6, # 4 and 3G, # 4 are subgroups of 3G, # 4. These somewhat trivial subgroups of 3G, # 4 are called improper
subgroups. Any other subgroups of 3G, # 4 are proper subgroups.
■
PrACtiCe 23
a. Show that 3 50, 2, 4, 66, + 8 4 is a subgroup of the group 3Z 8 , + 8 4.
b. Show that 3 51, 2, 46, # 7 4 is a subgroup of the group 3 51, 2, 3, 4, 5, 66, # 7 4.
PrACtiCe 24 Find all the proper subgroups of S 3 , the symmetric group of degree 3. (You can find
them by looking at the group table; see Practice 13.)
One point of confusing terminology: The set of all bijections on a set A into itself under function composition (like S 3 ) is called the group of permutations on A,
and any subgroup of this set (such as those in Practice 24) is called a permutation
group. The distinction is that the group of permutations on a set A includes all bijections on A into itself, but a permutation group may not. Permutation groups are
of particular importance, not only because they were the first groups to be studied,
but also because they are the only groups if we consider isomorphic structures to
be the same. We will see this result shortly.
There is an interesting subgroup we can always find in the symmetric group S n for n > 1. We know that every member of S n can be written as a
composition of cycles, but it is also true that each cycle can be written as the
composition of cycles of length 2, called transpositions. In S 7 , for example,
(5, 1, 7, 2, 3, 6) = (5, 6) + (5, 3) + (5, 2) + (5, 7) + (5, 1). We can verify this by
computing (5, 6) + (5, 3) + (5, 2) + (5, 7) + (5, 1). Working from right to left,
1 S 5 S 7 S 7 S 7 S 7
so 1 maps to 7. Similarly,
7 S 7 S 5 S 2 S 2 S 2
so 7 maps to 2, and so on, resulting in (5, 1, 7, 2, 3, 6). It is also true that
(5, 1, 7, 2, 3, 6) = (1, 5) + (1, 6) + (1, 3) + (1, 2) + (2, 4) + (1, 7) + (4, 2).
For any n > 1, the identity permutation i in S n can be written as
i = (a, b) + (a, b) for any two elements a and b in the set 51, 2, … , n6. This
equation also shows that the inverse of the transposition (a, b) in S n is (a, b). Now
we borrow (without proof) one more fact: Even though there are various ways to
write a cycle as the composition of transpositions, for a given cycle the number
of transpositions will either always be even or always be odd. Consequently, we
classify any permutation in S n , n > 1, as even or odd according to the number
of transpositions in any representation of that permutation. For example, in
S 7 , (5, 1, 7, 2, 3, 6) is odd. If we denote by A n the set of all even permutations in
S n , then A n determines a subgroup of 3S, + 4. The composition of even permutations
produces an even permutation, and i [ A n . If a [ A n , and a as a product of
transpositions is a = a 1 + a 2 + c + a k , then a
−1
= a k
−1 + a k−1
−1 + c + a 1
−1
. Each
inverse of a transposition is a transposition, so a
−1
is also even.
■
Modeling Arithmetic, Computation, and Languages
If 3G, # 4 is a group with identity i, then it is true that 3 5i6, # 4 and 3G, # 4 are subgroups of 3G, # 4. These somewhat trivial subgroups of 3G, # 4 are called improper
subgroups. Any other subgroups of 3G, # 4 are proper subgroups.
■
PrACtiCe 23
a. Show that 3 50, 2, 4, 66, + 8 4 is a subgroup of the group 3Z 8 , + 8 4.
b. Show that 3 51, 2, 46, # 7 4 is a subgroup of the group 3 51, 2, 3, 4, 5, 66, # 7 4.
PrACtiCe 24 Find all the proper subgroups of S 3 , the symmetric group of degree 3. (You can find
them by looking at the group table; see Practice 13.)
One point of confusing terminology: The set of all bijections on a set A into itself under function composition (like S 3 ) is called the group of permutations on A,
and any subgroup of this set (such as those in Practice 24) is called a permutation
group. The distinction is that the group of permutations on a set A includes all bijections on A into itself, but a permutation group may not. Permutation groups are
of particular importance, not only because they were the first groups to be studied,
but also because they are the only groups if we consider isomorphic structures to
be the same. We will see this result shortly.
There is an interesting subgroup we can always find in the symmetric group S n for n > 1. We know that every member of S n can be written as a
composition of cycles, but it is also true that each cycle can be written as the
composition of cycles of length 2, called transpositions. In S 7 , for example,
(5, 1, 7, 2, 3, 6) = (5, 6) + (5, 3) + (5, 2) + (5, 7) + (5, 1). We can verify this by
computing (5, 6) + (5, 3) + (5, 2) + (5, 7) + (5, 1). Working from right to left,
1 S 5 S 7 S 7 S 7 S 7
so 1 maps to 7. Similarly,
7 S 7 S 5 S 2 S 2 S 2
so 7 maps to 2, and so on, resulting in (5, 1, 7, 2, 3, 6). It is also true that
(5, 1, 7, 2, 3, 6) = (1, 5) + (1, 6) + (1, 3) + (1, 2) + (2, 4) + (1, 7) + (4, 2).
For any n > 1, the identity permutation i in S n can be written as
i = (a, b) + (a, b) for any two elements a and b in the set 51, 2, … , n6. This
equation also shows that the inverse of the transposition (a, b) in S n is (a, b). Now
we borrow (without proof) one more fact: Even though there are various ways to
write a cycle as the composition of transpositions, for a given cycle the number
of transpositions will either always be even or always be odd. Consequently, we
classify any permutation in S n , n > 1, as even or odd according to the number
of transpositions in any representation of that permutation. For example, in
S 7 , (5, 1, 7, 2, 3, 6) is odd. If we denote by A n the set of all even permutations in
S n , then A n determines a subgroup of 3S, + 4. The composition of even permutations
produces an even permutation, and i [ A n . If a [ A n , and a as a product of
transpositions is a = a 1 + a 2 + c + a k , then a
−1
= a k
−1 + a k−1
−1 + c + a 1
−1
. Each
inverse of a transposition is a transposition, so a
−1
is also even.
■