702
Modeling Arithmetic, Computation, and Languages
Not only is 3nZ, + 4 a subgroup of 3Z, + 4 for any fixed n, but sets of the form
nZ are the only subgroups of 3Z, + 4 To illustrate, let 3S, + 4 be any subgroup of
3Z, + 4. If S = 506, then S = 0Z. If S ∙ 506, let m be a member of S, m ∙ 0.
Either m is positive or, if m is negative, −m [ S and −m is positive. The subgroup
S, therefore, contains at least one positive integer. Let n be the smallest positive
integer in S (which exists by the principle of well-ordering). We will now see that
S = nZ.
First, since 0, n, and −n are members of S and S is closed under +, nZ # S.
To obtain inclusion in the other direction, let s [ S. Now we divide the integer
s by the integer n to get an integer quotient q and an integer remainder r with
0 ≤ r < n. Thus, s = nq + r. Solving for r, r = s + (−nq). But nq [ S; therefore −nq [ S, and s [ S, so by closure of S under +, r [ S. If r is positive, we
have a contradiction of the definition of n as the smallest positive number in S.
Therefore, r = 0 and s = nq + r = nq. We now have S # nZ, and thus S = nZ,
which completes the proof of the following theorem.
PrACtiCe 26 Show that for any n [ N, 3nZ, + 4 is a subgroup of 3Z, + 4.
■
tHeoRem on suBGrouPs of 3Z, + 4
Subgroups of the form 3nZ, + 4 for n [ N are the only subgroups of 3Z, + 4.
isomorphic Groups
Suppose that 3S, # 4 and 3T, + 4 are isomorphic groups; what would this mean? From
the discussion of isomorphism in Section 8.1, isomorphic structures are the same
except for relabeling. There must be a bijection from S to T that accomplishes the
relabeling. This bijection must also preserve the effects of the binary operation;
that is, it must be true that “operate and map” yields the same result as “map and
operate.” The following definition is more precise.
Definition GrouP isoMorPhisM
Let 3S, # 4 and 3T, + 4 be groups. A mapping f : S S T is an isomorphism from
3S, # 4 to 3T, + 4 if
1. the function f is a bijection.
2. for all x, y [ S, f (x # y) = f (x) + f ( y).
Property (2) is expressed by saying that f is a homomorphism.
PrACtiCe 27 Illustrate the homomorphism property of the definition of group isomorphism by a
commutative diagram.
■
If isomorphic groups are really the same except for the relabeling accomplished by the bijection, then we would expect that the identity of one group maps
Modeling Arithmetic, Computation, and Languages
Not only is 3nZ, + 4 a subgroup of 3Z, + 4 for any fixed n, but sets of the form
nZ are the only subgroups of 3Z, + 4 To illustrate, let 3S, + 4 be any subgroup of
3Z, + 4. If S = 506, then S = 0Z. If S ∙ 506, let m be a member of S, m ∙ 0.
Either m is positive or, if m is negative, −m [ S and −m is positive. The subgroup
S, therefore, contains at least one positive integer. Let n be the smallest positive
integer in S (which exists by the principle of well-ordering). We will now see that
S = nZ.
First, since 0, n, and −n are members of S and S is closed under +, nZ # S.
To obtain inclusion in the other direction, let s [ S. Now we divide the integer
s by the integer n to get an integer quotient q and an integer remainder r with
0 ≤ r < n. Thus, s = nq + r. Solving for r, r = s + (−nq). But nq [ S; therefore −nq [ S, and s [ S, so by closure of S under +, r [ S. If r is positive, we
have a contradiction of the definition of n as the smallest positive number in S.
Therefore, r = 0 and s = nq + r = nq. We now have S # nZ, and thus S = nZ,
which completes the proof of the following theorem.
PrACtiCe 26 Show that for any n [ N, 3nZ, + 4 is a subgroup of 3Z, + 4.
■
tHeoRem on suBGrouPs of 3Z, + 4
Subgroups of the form 3nZ, + 4 for n [ N are the only subgroups of 3Z, + 4.
isomorphic Groups
Suppose that 3S, # 4 and 3T, + 4 are isomorphic groups; what would this mean? From
the discussion of isomorphism in Section 8.1, isomorphic structures are the same
except for relabeling. There must be a bijection from S to T that accomplishes the
relabeling. This bijection must also preserve the effects of the binary operation;
that is, it must be true that “operate and map” yields the same result as “map and
operate.” The following definition is more precise.
Definition GrouP isoMorPhisM
Let 3S, # 4 and 3T, + 4 be groups. A mapping f : S S T is an isomorphism from
3S, # 4 to 3T, + 4 if
1. the function f is a bijection.
2. for all x, y [ S, f (x # y) = f (x) + f ( y).
Property (2) is expressed by saying that f is a homomorphism.
PrACtiCe 27 Illustrate the homomorphism property of the definition of group isomorphism by a
commutative diagram.
■
If isomorphic groups are really the same except for the relabeling accomplished by the bijection, then we would expect that the identity of one group maps