706
Modeling Arithmetic, Computation, and Languages
Also, f is a homomorphism from 3M 2 (Z), + 4 to 3M 2 (Z), + 4 because
f a c
a b
c d
d + c
e f
g h
d b = f a c
a + e b + f
c + g d + h
d b = c
a + e c + g
b + f d + h
d
= c
a c
b d
d + c
e g
f h
d = f a c
a b
c d
d b + f a c
e f
g h
d b
The function f is therefore an isomorphism from 3M 2 (Z), + 4 to 3M 2 (Z), + 4.
PrACtiCe 30 Let 5Z = 55z 0 z [ Z6. Then 35Z, + 4 is a group. Show that f: Z S 5Z given by f (x) = 5x
is an isomorphism from 3Z, + 4 to 35Z, + 4.
■
If f is an isomorphism from 3S, # 4 to 3T, + 4, then f
−1
exists and is a bijection. Further, f
−1
is also a homomorphism, this time from T to S. To see this, let
t 1 and t 2 belong to T and consider f
−1
(t 1 + t 2 ). Because t 1 , t 2 [ T and f is onto,
t 1 = f (s 1 ) and t 2 = f (s 2 ) for some s 1 and s 2 in S. Thus,
f
−1
(t 1 + t 2 ) = f
−1
( f (s 1 ) + f (s 2 ))
= f
−1
( f (s 1 # s 2 ))
= ( f
−1 + f )(s 1 # s 2 )
= s 1 # s 2
= f
−1
(t 1 ) # f
−1
(t 2 )
Therefore we can speak of S and T as being simply isomorphic, denoted by S . T ,
without having to specify that the isomorphism is from S to T or vice versa.
Checking whether a given function is an isomorphism from S to T, as in
Practice 30, is not hard. Deciding whether S and T are isomorphic may be harder.
To prove that they are isomorphic, we must produce a function. To prove that they
are not isomorphic, we must show that no such function exists. Since we can’t try
all possible functions, we use ideas such as the following: There is no one-to-one
correspondence between S and T, S is commutative but T is not, and so on.
We have noted that isomorphic groups are alike except for relabeling and
that each can be used to simulate the computations in the other. Isomorphism of
groups is really an equivalence relation, as Practice 31 shows; thus isomorphic
groups belong to the same equivalence class. Thinking of isomorphic groups as
“alike except for labeling” is consistent with the idea that elements in an equivalence class represent different names for the same thing.
PrACtiCe 31
a. Let f: S S T be an isomorphism from the group 3S, # 4 to the group 3T, + 4 and g: T S U be an
isomorphism from 3T, + 4 to the group 3U, * 4. Show that g + f is an isomorphism from S to U.
b. Let t be a collection of groups and define a binary relation r on t by S r T 4 S . T. Show that
r is an equivalence relation on t.
■
Modeling Arithmetic, Computation, and Languages
Also, f is a homomorphism from 3M 2 (Z), + 4 to 3M 2 (Z), + 4 because
f a c
a b
c d
d + c
e f
g h
d b = f a c
a + e b + f
c + g d + h
d b = c
a + e c + g
b + f d + h
d
= c
a c
b d
d + c
e g
f h
d = f a c
a b
c d
d b + f a c
e f
g h
d b
The function f is therefore an isomorphism from 3M 2 (Z), + 4 to 3M 2 (Z), + 4.
PrACtiCe 30 Let 5Z = 55z 0 z [ Z6. Then 35Z, + 4 is a group. Show that f: Z S 5Z given by f (x) = 5x
is an isomorphism from 3Z, + 4 to 35Z, + 4.
■
If f is an isomorphism from 3S, # 4 to 3T, + 4, then f
−1
exists and is a bijection. Further, f
−1
is also a homomorphism, this time from T to S. To see this, let
t 1 and t 2 belong to T and consider f
−1
(t 1 + t 2 ). Because t 1 , t 2 [ T and f is onto,
t 1 = f (s 1 ) and t 2 = f (s 2 ) for some s 1 and s 2 in S. Thus,
f
−1
(t 1 + t 2 ) = f
−1
( f (s 1 ) + f (s 2 ))
= f
−1
( f (s 1 # s 2 ))
= ( f
−1 + f )(s 1 # s 2 )
= s 1 # s 2
= f
−1
(t 1 ) # f
−1
(t 2 )
Therefore we can speak of S and T as being simply isomorphic, denoted by S . T ,
without having to specify that the isomorphism is from S to T or vice versa.
Checking whether a given function is an isomorphism from S to T, as in
Practice 30, is not hard. Deciding whether S and T are isomorphic may be harder.
To prove that they are isomorphic, we must produce a function. To prove that they
are not isomorphic, we must show that no such function exists. Since we can’t try
all possible functions, we use ideas such as the following: There is no one-to-one
correspondence between S and T, S is commutative but T is not, and so on.
We have noted that isomorphic groups are alike except for relabeling and
that each can be used to simulate the computations in the other. Isomorphism of
groups is really an equivalence relation, as Practice 31 shows; thus isomorphic
groups belong to the same equivalence class. Thinking of isomorphic groups as
“alike except for labeling” is consistent with the idea that elements in an equivalence class represent different names for the same thing.
PrACtiCe 31
a. Let f: S S T be an isomorphism from the group 3S, # 4 to the group 3T, + 4 and g: T S U be an
isomorphism from 3T, + 4 to the group 3U, * 4. Show that g + f is an isomorphism from S to U.
b. Let t be a collection of groups and define a binary relation r on t by S r T 4 S . T. Show that
r is an equivalence relation on t.
■