712
Modeling Arithmetic, Computation, and Languages
b. Let a function f: M 2
0
(Z) S Z be defined by
f a c
1 z
0 1
d b = z
Prove that f is an isomorphism from 3M 2
0
(Z), # 4 to 3Z, + 4
c. Use 3Z, + 4 to simulate the computation
c
1 7
0 1
d # c
1 − 3
0
1
d
in 3M 2
0
(Z), # 4.
d. Use 3M 2
0
(Z), # 4 to simulate the computation 2 + 3 in 3Z, + 4.
22. a. Let S = 51, −16. Show that 3S, # 4 is a group where # denotes ordinary integer multiplication.
b. Let f be the function from the group 3S n , + 4 to the group 3S, # 4 given by
f (a) = e
−1 if a is even
−1 if a is odd
Prove that f is a homomorphism.
23. In any group 3G, # 4, show that
a. i
−1
= i
b. (x
−1
)
−1
= x for any x [ G
24. a. Show that any group of order 2 is commutative by constructing a group table on the set 51, a6 with 1
as the identity.
b. Show that any group of order 3 is commutative by constructing a group table on the set 51, a, b6 with
1 as the identity. (You may assume associativity.)
c. Show that any group of order 4 is commutative by constructing a group table on the set 51, a, b, c6 with
1 as the identity. (You may assume associativity.) There will be four such tables, but three of them are
isomorphic because the elements have simply been relabeled from one to the other. Find these three
groups and indicate the relabeling. Thus, there are two essentially different groups of order 4, and both
of these are commutative.
25. Let 3G, # 4 be a group and let x, y [ G. Define a relation r on G by x r y 4 g # x # g
−1
= y for some g [ G.
a. Prove that r is an equivalence relation on G.
b. Prove that for each x [ G, 3x 4 = 5x6 if and only if G is commutative.
26. For x a member of a group 3G, # 4, we can define x
n
for any positive integer n by x
1
= x, x
2
= x # x, and
x
n
= x
n−1 # x for n > 2. Prove that in a finite group 3G, # 4, for each x [ G there is a positive integer k such
that x
k
= i.
27. Let 3S, # 4 be a semigroup. An element i L [ S is a left identity element if for all x [ S, i L # x = x. An
element i R [ S is a right identity element if for all x [ S, x # i R = x.
a. Prove that if a semigroup 3S, # 4 has both a left identity element and a right identity element, then 3S, # 4
is a monoid.
b. Give an example of a finite semigroup with two left identities and no right identity.
c. Give an example of a finite semigroup with two right identities and no left identity.
d. Give an example of a semigroup with neither a right nor a left identity.
Modeling Arithmetic, Computation, and Languages
b. Let a function f: M 2
0
(Z) S Z be defined by
f a c
1 z
0 1
d b = z
Prove that f is an isomorphism from 3M 2
0
(Z), # 4 to 3Z, + 4
c. Use 3Z, + 4 to simulate the computation
c
1 7
0 1
d # c
1 − 3
0
1
d
in 3M 2
0
(Z), # 4.
d. Use 3M 2
0
(Z), # 4 to simulate the computation 2 + 3 in 3Z, + 4.
22. a. Let S = 51, −16. Show that 3S, # 4 is a group where # denotes ordinary integer multiplication.
b. Let f be the function from the group 3S n , + 4 to the group 3S, # 4 given by
f (a) = e
−1 if a is even
−1 if a is odd
Prove that f is a homomorphism.
23. In any group 3G, # 4, show that
a. i
−1
= i
b. (x
−1
)
−1
= x for any x [ G
24. a. Show that any group of order 2 is commutative by constructing a group table on the set 51, a6 with 1
as the identity.
b. Show that any group of order 3 is commutative by constructing a group table on the set 51, a, b6 with
1 as the identity. (You may assume associativity.)
c. Show that any group of order 4 is commutative by constructing a group table on the set 51, a, b, c6 with
1 as the identity. (You may assume associativity.) There will be four such tables, but three of them are
isomorphic because the elements have simply been relabeled from one to the other. Find these three
groups and indicate the relabeling. Thus, there are two essentially different groups of order 4, and both
of these are commutative.
25. Let 3G, # 4 be a group and let x, y [ G. Define a relation r on G by x r y 4 g # x # g
−1
= y for some g [ G.
a. Prove that r is an equivalence relation on G.
b. Prove that for each x [ G, 3x 4 = 5x6 if and only if G is commutative.
26. For x a member of a group 3G, # 4, we can define x
n
for any positive integer n by x
1
= x, x
2
= x # x, and
x
n
= x
n−1 # x for n > 2. Prove that in a finite group 3G, # 4, for each x [ G there is a positive integer k such
that x
k
= i.
27. Let 3S, # 4 be a semigroup. An element i L [ S is a left identity element if for all x [ S, i L # x = x. An
element i R [ S is a right identity element if for all x [ S, x # i R = x.
a. Prove that if a semigroup 3S, # 4 has both a left identity element and a right identity element, then 3S, # 4
is a monoid.
b. Give an example of a finite semigroup with two left identities and no right identity.
c. Give an example of a finite semigroup with two right identities and no left identity.
d. Give an example of a semigroup with neither a right nor a left identity.