Section 9.1 Algebraic Structures
693
The next two examples give us algebraic structures where the elements are
functions, mappings from a domain to a codomain.
ReminDeR
In the group 3Z 2 , + 2 4, the
set is 50, 16 and the operation is addition modulo
2. In the group 3Z
n
2 , + 2 4 for
any n, the set is all binary
n-tuples and the operation
is componentwise addition modulo 2.
example 8
Let Z
n
2 be the set of all binary n-tuples with n ≥ 1. We’ll usually use a little shorthand and write, for example, 1101 instead of (1, 1, 0, 1). Using componentwise
addition modulo 2, + 2 . it’s easy to see that the addition operation is associative
and commutative and that the n-tuple of all 0s is an identity. Each n-tuple has an
inverse. Therefore 3Z
n
2 , + 2 4 is a commutative group.
example 9
Let A be a set and consider the set S of all functions f such that f: A S A. The
binary operation is function composition, denoted by + . Note that S is closed under
+ and that function composition is associative (see Practice 12). Thus 3S, + 4 is a
semigroup, called the semigroup of transformations on A. Actually 3S, + 4 is a
monoid because the identity function i A that takes each member of A to itself has
the property that for any f [ S,
f + i A = i A + f = f
PrACtiCe 12 Prove that function composition on the set S just defined is associative.
■
example 10
Again let A be a set and consider the set S A of all bijections f such that f: A S A
(permutations of A). Bijectiveness is preserved under function composition, function composition is associative, the identity function i A is a permutation, and for
any f [ S A , the inverse function f
−1
exists and is a permutation. Furthermore,
f + f
−1
= f
−1 + f = i A
Thus, 3S A , + 4 is a group, called the group of permutations on A.
If A = 51, 2, … , n6 for some positive integer n, then S A is called the symmetric group of degree n and denoted by S n . Thus, S 3 , for example, is the set of all
permutations on 51, 2, 36. There are 3! = 6 such permutations, which we name
as follows (using the cycle notation of Section 5.4):
a l = i
a 2 = (1, 2)
a 3 = (1, 3)
a 4 = (2, 3)
a 5 = (1, 2, 3)
a 6 = (1, 3, 2)
PrACtiCe 11 In the group 3Z
5
2 , + 2 4, what is
a. 01101 + 2 11011?
b. −10100?
■
693
The next two examples give us algebraic structures where the elements are
functions, mappings from a domain to a codomain.
ReminDeR
In the group 3Z 2 , + 2 4, the
set is 50, 16 and the operation is addition modulo
2. In the group 3Z
n
2 , + 2 4 for
any n, the set is all binary
n-tuples and the operation
is componentwise addition modulo 2.
example 8
Let Z
n
2 be the set of all binary n-tuples with n ≥ 1. We’ll usually use a little shorthand and write, for example, 1101 instead of (1, 1, 0, 1). Using componentwise
addition modulo 2, + 2 . it’s easy to see that the addition operation is associative
and commutative and that the n-tuple of all 0s is an identity. Each n-tuple has an
inverse. Therefore 3Z
n
2 , + 2 4 is a commutative group.
example 9
Let A be a set and consider the set S of all functions f such that f: A S A. The
binary operation is function composition, denoted by + . Note that S is closed under
+ and that function composition is associative (see Practice 12). Thus 3S, + 4 is a
semigroup, called the semigroup of transformations on A. Actually 3S, + 4 is a
monoid because the identity function i A that takes each member of A to itself has
the property that for any f [ S,
f + i A = i A + f = f
PrACtiCe 12 Prove that function composition on the set S just defined is associative.
■
example 10
Again let A be a set and consider the set S A of all bijections f such that f: A S A
(permutations of A). Bijectiveness is preserved under function composition, function composition is associative, the identity function i A is a permutation, and for
any f [ S A , the inverse function f
−1
exists and is a permutation. Furthermore,
f + f
−1
= f
−1 + f = i A
Thus, 3S A , + 4 is a group, called the group of permutations on A.
If A = 51, 2, … , n6 for some positive integer n, then S A is called the symmetric group of degree n and denoted by S n . Thus, S 3 , for example, is the set of all
permutations on 51, 2, 36. There are 3! = 6 such permutations, which we name
as follows (using the cycle notation of Section 5.4):
a l = i
a 2 = (1, 2)
a 3 = (1, 3)
a 4 = (2, 3)
a 5 = (1, 2, 3)
a 6 = (1, 3, 2)
PrACtiCe 11 In the group 3Z
5
2 , + 2 4, what is
a. 01101 + 2 11011?
b. −10100?
■