- Shopping Bag ( 0 items )
Want a NOOK? Explore Now
Monoids and Groups
The theory of groups is one of the oldest and richest branches of algebra. Groups of transformations play an important role in geometry, and, as we shall see in Chapter 4, finite groups are the basis of Galois' discoveries in the theory of equations. These two fields provided the original impetus for the development of the theory of groups, whose systematic study dates from the early part of the nineteenth century.
A more general concept than that of a group is that of a monoid. This is simply a set which is endowed with an associative binary composition and a unit—whereas groups are monoids all of whose elements have inverses relative to the unit. Although the theory of monoids is by no means as rich as that of groups, it has recently been found to have important "external" applications (notably to automata theory). We shall begin our discussion with the simpler and more general notion of a monoid, though our main target is the theory of groups. It is hoped that the preliminary study of monoids will clarify, by putting into a better perspective, some of the results on groups. Moreover, the results on monoids will be useful in the study of rings, which can be regarded as pairs of monoids having the same underlying set and satisfying some additional conditions (e.g., the distributive laws).
A substantial part of this chapter is foundational in nature. The reader will be confronted with a great many new concepts, and it may take some time to absorb them all. The point of view may appear rather abstract to the uninitiated. We have tried to overcome this difficulty by providing many examples and exercises whose purpose is to add concreteness to the theory. The axiomatic method, which we shall use throughout this book and, in particular, in this chapter, is very likely familiar to the reader: for example, in the axiomatic developments of Euclidean geometry and of the real number system. However, there is a striking difference between these earlier axiomatic theories and the ones we shall encounter. Whereas in the earlier theories the defining sets of axioms are categorical in the sense that there is essentially only one system satisfying them—this is far from true in the situations we shall consider. Our axiomatizations are intended to apply simultaneously to a large number of models, and, in fact, we almost never know the full range of their applicability. Nevertheless, it will generally be helpful to keep some examples in mind.
The principal systems we shall consider in this chapter are: monoids, monoids of transformations, groups, and groups of transformations. The relations among this quartet of concepts can be indicated by the following diagram:
[ILLUSTRATION OMITTED]
This is intended to indicate that the classes of groups and of monoids of transformations are contained in the class of monoids and the intersection of the first two classes is the class of groups of transformations. In addition to these concepts one has the fundamental concept of homomorphism which singles out the type of mappings that are natural to consider for our systems. We shall introduce first the more intuitive notion of an isomorphism.
At the end of the chapter we shall carry the discussion beyond the foundations in deriving the Sylow theorems for finite groups. Further results on finite groups will be given in Chapter 4 when we have need for them in connection with the theory of equations. Still later, in Chapter 6, we shall study the structure of some classical geometric groups (e.g., rotation groups).
1.1 MONOIDS OF TRANSFORMATIONS AND ABSTRACT MONOIDS
We have seen in section 0.2 that composition of maps of sets satisfies the associative law. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and βα is the map from S to U defined by (βα)(S) = β(α(s)) then we have γ(βα) = (γβ)α. We recall also that if 1T is the identity map t ->t on T, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and β1T = β for every α:S ->T and β: T ->U. Now let us specialize this and consider the set M(S) of transformations (or maps) of S into itself. For example, let S = {1, 2}. Here M(S) consists of the four transformations
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
where in each case we have indicated immediately below the element appearing in the first row its image under the map. It is easy to check that the following table gives the products in this M(S):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Here, generally, we have put ρσ in the intersection of the row headed by ρ and the column headed by σ (ρ, σ = 1, α, β, γ). More generally, if S = {1, 2, ..., n} then M(S) consists of nn transformations, and for a given n, we can write down a multiplication table like (1) for M(S). Now, for any non-vacuous S, M(S) is an example of a monoid, which is simply a non-vacuous set of elements, together with an associative binary composition and a unit, that is, an element 1 whose product in either order with any element is this element. More formally we give the following
DEFINITION 1.1.A monoid is a triple (M, p, 1) in which M is a non-vacuous set, p is an associative binary composition (or product) in M, and 1 is an element of M such that p( 1, a) = a = p(a, 1) for all a [member of] M.
If we drop the hypothesis that p is associative we obtain a system which is sometimes called a monad. On the other hand, if we drop the hypothesis on 1 and so have just a set together with an associative binary composition, then we obtain a semigroup (M, p). We shall now abbreviate p(a, b), the product under p of a and b, to the customary ab (or a · b). An element 1 of (M, p) such that a1 = a = 1a for all a in M is called a unit in (M, p). If 1' is another such element then 1'1 = 1 and 1'1 = 1', so 1' = 1. Hence if a unit exists it is unique, and so we may speak of the unit of (M, p). It is clear that a monoid can be defined also as a semi-group containing a unit. However, we prefer to stick to the definition which we gave first. Once we have introduced a monoid (M, p, 1), and it is clear what we have, then we can speak more briefly of "the monoid M," though, strictly speaking, this is the underlying set and is just one of the ingredients of (M, p, 1).
Examples of monoids abound in the mathematics that is already familiar to the reader. We give a few in the following list.
EXAMPLES
1. (N, +,0); N, the set of natural numbers, +, the usual addition in N, and 0 the first element of N.
2. (N, ·, 1). Here · is the usual product and 1 is the natural number 1.
3. (P, ·, 1); P, the set of positive integers, · and 1 are as in (2).
4. (z, +, 0); z, the set of integers, + and 0 are as usual.
5. (z, ·, 1); · and 1 are as usual.
6. Let S be any non-vacuous set, P(S) the set of subsets of S. This gives rise to two monoids (P(S), [union], Θ) and (P(S), [intersection], S).
7. Let α be a particular transformation of S and define αk inductively by α0 = 1, αr = αr - 1α, r > 0. Then αkαl = αk + l (which is easy to see and will be proved in section 1.4). Then <a> = {αk|k [member of] N} together with the usual composition of transformations and α0 = 1 constitute a monoid.
If M is a monoid, a subset N of M is called a submonoid of M if N contains 1 and N is closed under the product in M, that is, n1n2 [member of] N for every ni [member of] N. For instance, example 2, (N, ·, 1), is a submonoid of (z, ·, 1); and 3, (P, ·, 1), is a submonoid of (N, ·, 1). On the other hand, the subset {0} of N consisting of 0 only is closed under multiplication, but this is not a submonoid of 2 since it does not contain 1. If N is a submonoid of M, then N together with the product defined in M restricted to N, and the unit, constitute a monoid. It is clear that a submonoid of a submonoid of M is a submonoid of M. A submonoid of the monoid M(S) of all transformations of the set S will be called a monoid of transformations (of S). Clearly the definition means that a subset N of M(S) is a monoid of transformations if and only if the identity map is contained in N and the composite of any two maps in N belongs to N.
A monoid is said to be finite if it has a finite number of elements. We shall usually call the cardinality of a monoid its order, and we shall denote this as |M|. In investigating a finite monoid it is useful to have a multiplication table for the products in M. As in the special case which we considered above, if M = {al = 1, a2, ..., am} the multiplication table has the form
[ILLUSTRATION OMITTED]
where aiaj is tabulated in the intersection of the row headed by ai and the column headed by aj.
EXERCISES
1. Let S be a set and define a product in S by ab = b. Show that S is a semigroup. Under what condition does S contain a unit?
2. Let M = z × z the set of pairs of integers (xl, x2). Define (x1, x2)(y1, y2) = (x1 + 2x2y2, x1y2 + x2y1), 1 = (1, 0). Show that this defines a monoid. (Observe that the commutative law of multiplication holds.) Show that if (x1, x2) ≠ (0,0) then the cancellation law will hold for (x1, x2), that is, (x1, x2)(y1, y2) = (x1, x2)(z1, z2) [??] (y1, y2) = (z1, z2).
3. A machine accepts eight-letter words (defined to be any sequence of eight letters of the alphabet, possibly meaningless), and prints an eight-letter word consisting of the first five letters of the first word followed by the last three letters of the second word. Show that the set of eight-letter words with this composition is a semigroup. What if the machine prints the last four letters of the first word followed by the first four of the second? Is either of these systems a monoid?
4. Let (M, p, 1) be a monoid and let m [member of] M. Define a new product pm in M by pm(a, b) = amb. Show that this defines a semigroup. Under what condition on m do we have a unit relative to pm?
5. Let S be a semigroup, u an element not in S. Form M = S [union] {u} and extend the product in S to a binary product in M by defining ua = a = au for all a [member of] M. Show that M is a monoid.
1.2 GROUPS OF TRANSFORMATIONS AND ABSTRACT GROUPS
An element u of a monoid M is said to be invertible (or a unit) if there exists a v in M such that
(3) uv = 1 = vu.
If v' also satisfies uv' = 1 = v'u then v' = (vu)v' = v(uv') = v. Hence v satisfying (3) is unique. We call this the inverse of u and write v = u-1. It is clear also that u-1 is invertible and (u-1)-1 = u. We now give the following
DEFINITION 1.2.A group G (or (G, p, 1)) is a monoid all of whose elements are invertible.
We shall call a submonoid of a monoid M (in particular, of a group) asubgroup if, regarded as a monoid, it is a group. Since the unit of a submonoid coincides with that of M it is clear that a subset G of M is a subgroup if and only if it has the following closure properties: 1 [member of] G, g1g2 [member of] G for every gi [member of] G, every g [member of] G is invertible, and g-1 [member of] G.
Let U(M) denote the set of invertible elements of the monoid M and let u1u2 [member of] U(M). Then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
and, similarly, (u2-1u1-1)(u1u2) = 1. Hence u1u2 [member of] U(M). We saw also that if u [member of] U(M) then u-1 [member of] U(M), and clearly 1 · 1 = 1 shows that 1 [member of] U(M). Thus we see that U(M) is a subgroup of M. We shall call this the group of units or invertible elements of M. For example, if M = (z, ·, 1) then U(M) = {1, -1} and if M = (N, ·, 1) then U(M) = {1}.
We now consider the monoid M(S) of transformations of a non-vacuous set S. What is the associated group of units U(M(S))? We have seen (p. 8) that a transformation is invertible if and only if it is bijective. Hence our group is just the set of bijective transformations of S with the composition as the composite of maps and the unit as the identity map. We shall call U(M(S)) the symmetric group of the set S and denote it as Sym S. In particular, if S = {1, 2, ..., n) then we shall write Sn for Sym S and call this the symmetric group on n letters. We usually call the elements of Sn permutations of {1, 2, ..., n}. We can easily list all of these and determine the order of Sn. Using the notation we introduced in the case n = 2, we can denote a transformation of {1, 2, ..., n} by a symbol
(4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
where this means the transformation sending i ->i', 1 ≤ i ≤ n. In order for α to be injective the second line 1 ', ..., n' must contain no duplicates, that is, no i can appear twice. This will also assure bijectivity since we cannot have an injective map of {1, 2, ..., n} on a proper subset. We can now count the number of elements in Sn by observing that we can take the element 1' in the symbol (4) to be any one of the n numbers 1,2, ..., n. This gives n choices for 1'. Once this has been chosen, to avoid duplication, we must choose 2' among the n - 1 numbers different from 1'. This gives n - 1 choices for 2'. After the partners of 1 and 2 have been chosen, we have n - 2 choices for 3', and so on. Clearly this means we have n! symbols (4) representing the elements of Sn. We have therefore proved
Excerpted from Basic Algebra I by Nathan Jacobson. Copyright © 1985 Nathan Jacobson. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Overview
A classic text and standard reference for a generation, this volume and its companion are the work of an expert algebraist who taught at Yale for two decades. Nathan Jacobson's books possess a conceptual and theoretical orientation, and in addition to their value as classroom texts, they serve as valuable references.
Volume I explores all of the topics typically covered in undergraduate courses, including the rudiments of set theory, group theory, rings, modules, Galois theory,...