710
Modeling Arithmetic, Computation, and Languages
e. S = R−5−16; x # y = x + y + xy
f. S = 5 f 0 f : N S N6; # = function addition, that is, ( f + g)(x) = f (x) + g (x)
8. Let A = 51, 26.
a. Describe the elements and write the table for the semigroup of transformations on A.
b. Describe the elements and write the table for the group of permutations on A.
9. Given an equilateral triangle, six permutations can be performed on the triangle that will leave its image in the
plane unchanged. Three of these permutations are clockwise rotations in the plane of 120°, 240°, and 360°
about the center of the triangle; these permutations are denoted R 1 , R 2 , and R 3 , respectively. The triangle
can also be flipped about any of the axes 1, 2, and 3 (see the accompanying figure); these permutations are
denoted F 1 , F 2 , and F 3 , respectively. During any of these permutations, the axes remain fixed in the plane.
Composition of permutations is a binary operation on the set D 3 of all six permutations. For example,
F 3 + R 2 = F 2 . The set D 3 under composition is a group, called the group of symmetries of an equilateral
triangle. Complete the group table below for 3D 3 , + 4. What is an identity element in 3D 3 , + 4? What is an
inverse element for F 1 ? For R 2 ?
+
R 1
R 2
R 3
F 1
F 2
F 3
R 1
R 2
R 3
F 1
F 2
F 3
F 2
10. The set S 3 , the symmetric group of degree 3, is isomorphic to D 3 , the group of symmetries of an equilateral triangle (see Exercise 9). Find a bijection from the elements of S 3 to the elements of D 3 that preserves
the operation. (Hint: R 1 of D 3 may be considered a permutation in S 3 sending 1 to 2, 2 to 3, and 3 to 1.)
11. In each case, decide whether the structure on the left is a subgroup of the group on the right. If not, why
not? (Note that here S* denotes S − 506.)
a. 3Z 5 *, # 5 4; 3Z 5 , + 5 4
b. 3P, + 4; 3R3x 4, + 4 where P is the set of all polynomials in x over R of degree ≥ 3
c. 3Z*, # 4; 3Q*, # 4
d. 3K, + 4; 3R3x 4, + 4 where K is the set of all polynomials in x over R of degree ≤ k for some fixed k
12. In each case, decide whether the structure on the left is a subgroup of the group on the right. If not,
why not?
a. 3A, + 4; 3S, + 4 where S is the set of all bijections on N and A is the set of all bijections on N
mapping 3 to 3
b. 3Z, + 4; 3M 2 (Z), + 4
c. 3 50, 3, 66, + 8 4; 3Z 8 , + 8 4
d. 3A, + 2 4; 3Z
5
2 , + 2 4 where A = 500000, 01111, 10101, 110106
13. Find all the distinct subgroups of 3Z 12 , + 12 4.
14. a. Show that the subset
a l = i
a 3 = (1, 4) + (2, 3)
a 2 = (1, 2) + (3, 4)
a 4 = (1, 3) + (2, 4)
forms a subgroup of the symmetric group S 4 .
Modeling Arithmetic, Computation, and Languages
e. S = R−5−16; x # y = x + y + xy
f. S = 5 f 0 f : N S N6; # = function addition, that is, ( f + g)(x) = f (x) + g (x)
8. Let A = 51, 26.
a. Describe the elements and write the table for the semigroup of transformations on A.
b. Describe the elements and write the table for the group of permutations on A.
9. Given an equilateral triangle, six permutations can be performed on the triangle that will leave its image in the
plane unchanged. Three of these permutations are clockwise rotations in the plane of 120°, 240°, and 360°
about the center of the triangle; these permutations are denoted R 1 , R 2 , and R 3 , respectively. The triangle
can also be flipped about any of the axes 1, 2, and 3 (see the accompanying figure); these permutations are
denoted F 1 , F 2 , and F 3 , respectively. During any of these permutations, the axes remain fixed in the plane.
Composition of permutations is a binary operation on the set D 3 of all six permutations. For example,
F 3 + R 2 = F 2 . The set D 3 under composition is a group, called the group of symmetries of an equilateral
triangle. Complete the group table below for 3D 3 , + 4. What is an identity element in 3D 3 , + 4? What is an
inverse element for F 1 ? For R 2 ?
+
R 1
R 2
R 3
F 1
F 2
F 3
R 1
R 2
R 3
F 1
F 2
F 3
F 2
10. The set S 3 , the symmetric group of degree 3, is isomorphic to D 3 , the group of symmetries of an equilateral triangle (see Exercise 9). Find a bijection from the elements of S 3 to the elements of D 3 that preserves
the operation. (Hint: R 1 of D 3 may be considered a permutation in S 3 sending 1 to 2, 2 to 3, and 3 to 1.)
11. In each case, decide whether the structure on the left is a subgroup of the group on the right. If not, why
not? (Note that here S* denotes S − 506.)
a. 3Z 5 *, # 5 4; 3Z 5 , + 5 4
b. 3P, + 4; 3R3x 4, + 4 where P is the set of all polynomials in x over R of degree ≥ 3
c. 3Z*, # 4; 3Q*, # 4
d. 3K, + 4; 3R3x 4, + 4 where K is the set of all polynomials in x over R of degree ≤ k for some fixed k
12. In each case, decide whether the structure on the left is a subgroup of the group on the right. If not,
why not?
a. 3A, + 4; 3S, + 4 where S is the set of all bijections on N and A is the set of all bijections on N
mapping 3 to 3
b. 3Z, + 4; 3M 2 (Z), + 4
c. 3 50, 3, 66, + 8 4; 3Z 8 , + 8 4
d. 3A, + 2 4; 3Z
5
2 , + 2 4 where A = 500000, 01111, 10101, 110106
13. Find all the distinct subgroups of 3Z 12 , + 12 4.
14. a. Show that the subset
a l = i
a 3 = (1, 4) + (2, 3)
a 2 = (1, 2) + (3, 4)
a 4 = (1, 3) + (2, 4)
forms a subgroup of the symmetric group S 4 .