Section 9.1 Algebraic Structures
695
Basic results about Groups
We will now prove some basic theorems about groups. There are hundreds of
theorems about groups and many books devoted exclusively to group theory, so
we are barely scratching the surface here. The results we will prove follow almost
immediately from the definitions involved.
By definition, a group 3G, # 4 (or a monoid) has an identity element, and we
have tried to be careful to refer to an identity element rather than the identity element. However, it is legal to say the identity because there is only one. To prove
that the identity element is unique, suppose that i 1 and i 2 are both identity elements. Then
i 1 = i 1 # i 2 = i 2
The empty string l should not be confused with the empty set [; even if A
itself is [, then A* = 5l6. If A is nonempty, then whatever the size of A, A* is a
denumerable (countably infinite) set. If A contains only one element, say A = 5a6,
then l, a, aa, aaa, … , is an enumeration of A*. If A contains more than one element, then a lexicographical (alphabetical) ordering can be imposed on the elements of A. An enumeration of A* is then obtained by counting the empty string
first, then lexicographically ordering all strings of length 1 (there is a finite number
of these), then lexicographically ordering all strings of length 2 (there is a finite
number of these), and so forth. Note also that if A is nonempty, strings of arbitrary
length can be found in A*.
Concatenation is a binary operation on A*, and it is associative. The empty
string l is an identity because for any string x [ A*,
x # l = l # x = x
Therefore, 3A*, # 4 is a monoid, called the free monoid generated by A.
PrACtiCe 14 For A = 5a, b6
a. Is 3A*, # 4 a commutative monoid?
b. Is 3A*, # 4 a group?
ReminDeR
To prove that something is
unique …
PrACtiCe 15 Justify the foregoing equality signs.
■
Because i 1 = i 2 , the identity element is unique. Thus, we have proved the following theorem.
tHeoRem on thE uniquEnEss of thE iDEntity in A GrouP
In any group (or monoid) 3G, # 4, the identity element i is unique.
Each element x in a group 3G, # 4 has an inverse element x
−1
. Therefore, G contains
many different inverse elements, but for each x, the inverse is unique.
■
695
Basic results about Groups
We will now prove some basic theorems about groups. There are hundreds of
theorems about groups and many books devoted exclusively to group theory, so
we are barely scratching the surface here. The results we will prove follow almost
immediately from the definitions involved.
By definition, a group 3G, # 4 (or a monoid) has an identity element, and we
have tried to be careful to refer to an identity element rather than the identity element. However, it is legal to say the identity because there is only one. To prove
that the identity element is unique, suppose that i 1 and i 2 are both identity elements. Then
i 1 = i 1 # i 2 = i 2
The empty string l should not be confused with the empty set [; even if A
itself is [, then A* = 5l6. If A is nonempty, then whatever the size of A, A* is a
denumerable (countably infinite) set. If A contains only one element, say A = 5a6,
then l, a, aa, aaa, … , is an enumeration of A*. If A contains more than one element, then a lexicographical (alphabetical) ordering can be imposed on the elements of A. An enumeration of A* is then obtained by counting the empty string
first, then lexicographically ordering all strings of length 1 (there is a finite number
of these), then lexicographically ordering all strings of length 2 (there is a finite
number of these), and so forth. Note also that if A is nonempty, strings of arbitrary
length can be found in A*.
Concatenation is a binary operation on A*, and it is associative. The empty
string l is an identity because for any string x [ A*,
x # l = l # x = x
Therefore, 3A*, # 4 is a monoid, called the free monoid generated by A.
PrACtiCe 14 For A = 5a, b6
a. Is 3A*, # 4 a commutative monoid?
b. Is 3A*, # 4 a group?
ReminDeR
To prove that something is
unique …
PrACtiCe 15 Justify the foregoing equality signs.
■
Because i 1 = i 2 , the identity element is unique. Thus, we have proved the following theorem.
tHeoRem on thE uniquEnEss of thE iDEntity in A GrouP
In any group (or monoid) 3G, # 4, the identity element i is unique.
Each element x in a group 3G, # 4 has an inverse element x
−1
. Therefore, G contains
many different inverse elements, but for each x, the inverse is unique.
■