708
Modeling Arithmetic, Computation, and Languages
S e c t i o n 9 . 1 review
tecHniQueS
• Test whether a given set and operation have the
properties necessary to form a semigroup, monoid,
or group structure.
• Test whether a given subset of a group is a subgroup.
• Test whether a given function from one group to
another is an isomorphism.
• Decide whether two groups are isomorphic.
main iDeaS
• Many elementary arithmetic systems are instances
of a semigroup, monoid, or group structure.
• In any group structure, the identity and inverse
elements are unique, cancellation laws hold, and
linear equations are solvable; these and other
properties follow from the definitions involved.
• A subset of a group may itself be a group under the
inherited operation.
• The order of a subgroup of a finite group divides
the order of the group.
• The only subgroups of the group 3Z, + 4 are of the
form 3nZ, + 4, where nZ is the set of all integral
multiples of a fixed n [ N.
• If f is an isomorphism from one group to another,
f maps the identity to the identity and inverses to
inverses, and it preserves commutativity.
• If S and T are isomorphic groups, they are identical
except for relabeling, and each simulates any
computation in the other.
• Isomorphism is an equivalence relation on groups.
• To within an isomorphism, there is only one group
of order 2, one group of order 3, and two groups of
order 4.
• Every group is essentially a permutation group.
PrACtiCe 33
a. Let 1 denote the identity of G. Show that a 1 is an identity for P under function composition.
b. For a g [ P, a g
−1 [ P; show that a g
−1 = (a g )
−1
.
■
We now know that 3P, + 4 is a permutation group, and it only remains to show
that the function f: G S P given by f (g) = a g is an isomorphism. Clearly, f is an
onto function.
PrACtiCe 34 Show that f: G S P defined by f (g) = a g is
a. one-to-one.
b. a homomorphism.
■
We have now proved the following theorem, first stated and proved by the
English mathematician Arthur Cayley in the mid-1800s.
tHeoRem CAyLEy’s thEorEM
Every group is isomorphic to a permutation group.
exeRciSeS 9.1
1. a. A binary operation # is defined on the set 5a, b, c, d6 by the table on the left. Is # commutative?
Is # associative?
b. Let S = 5p, q, r, s6. An associative binary operation # is partly defined on S by the table on the right.
Complete the table to preserve associativity. Is # commutative?
W
Modeling Arithmetic, Computation, and Languages
S e c t i o n 9 . 1 review
tecHniQueS
• Test whether a given set and operation have the
properties necessary to form a semigroup, monoid,
or group structure.
• Test whether a given subset of a group is a subgroup.
• Test whether a given function from one group to
another is an isomorphism.
• Decide whether two groups are isomorphic.
main iDeaS
• Many elementary arithmetic systems are instances
of a semigroup, monoid, or group structure.
• In any group structure, the identity and inverse
elements are unique, cancellation laws hold, and
linear equations are solvable; these and other
properties follow from the definitions involved.
• A subset of a group may itself be a group under the
inherited operation.
• The order of a subgroup of a finite group divides
the order of the group.
• The only subgroups of the group 3Z, + 4 are of the
form 3nZ, + 4, where nZ is the set of all integral
multiples of a fixed n [ N.
• If f is an isomorphism from one group to another,
f maps the identity to the identity and inverses to
inverses, and it preserves commutativity.
• If S and T are isomorphic groups, they are identical
except for relabeling, and each simulates any
computation in the other.
• Isomorphism is an equivalence relation on groups.
• To within an isomorphism, there is only one group
of order 2, one group of order 3, and two groups of
order 4.
• Every group is essentially a permutation group.
PrACtiCe 33
a. Let 1 denote the identity of G. Show that a 1 is an identity for P under function composition.
b. For a g [ P, a g
−1 [ P; show that a g
−1 = (a g )
−1
.
■
We now know that 3P, + 4 is a permutation group, and it only remains to show
that the function f: G S P given by f (g) = a g is an isomorphism. Clearly, f is an
onto function.
PrACtiCe 34 Show that f: G S P defined by f (g) = a g is
a. one-to-one.
b. a homomorphism.
■
We have now proved the following theorem, first stated and proved by the
English mathematician Arthur Cayley in the mid-1800s.
tHeoRem CAyLEy’s thEorEM
Every group is isomorphic to a permutation group.
exeRciSeS 9.1
1. a. A binary operation # is defined on the set 5a, b, c, d6 by the table on the left. Is # commutative?
Is # associative?
b. Let S = 5p, q, r, s6. An associative binary operation # is partly defined on S by the table on the right.
Complete the table to preserve associativity. Is # commutative?
W