## Read an Excerpt

#### Basic Algebra I

**By Nathan Jacobson**

**Dover Publications, Inc.**

**Copyright © 1985 Nathan Jacobson**

All rights reserved.

ISBN: 978-0-486-13522-9

All rights reserved.

ISBN: 978-0-486-13522-9

CHAPTER 1

**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 1*T* is the identity map *t* ->*t* on *T*, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and β1*T* = β 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 *a*1 = *a* = 1*a* 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 *u*1*u*2 [member of] *U(M)*. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and, similarly, (*u*2-1*u*1-1)(*u*1*u*2) = 1. Hence *u*1*u*2 [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

*(Continues...)*

Excerpted fromBasic Algebra IbyNathan 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.