Abstract algebra dan saracino pdf

Abstract Algebra

CONTENTS

o Sets and Induction ............ ......... .... .... ................ ......... .... ........ ... ............... ...... 1 1 Binary Operations ..... .... ... ........... .. ... ......... ... .......... .... .. .. ....... ..... .. ... .. ........... 10 2 Groups .. ... ............. ..... .................. ... ........... ........ ............. ....... .... .... .. ... .......... 16 3 Fundamental Theorems about Groups ...... ....... .. ... .......... ...... ........ .......... ...... 25 4 Powers of an Element; Cyclic Groups .......................................................... 33 5 Subgroups .......... .......... ................ .. ........ ....... ........ ............... ... ....... ........ ........ 43 6 Direct Products ............................................................................................. 55 7 Functions ...................................................................................................... 59 8 Symmetric Groups ................................................ ..................... ........... ....... 66 9 Equivalence Relations; Cosets ....... ... .... ... ............... ............. ............... ......... 80

10 Counting the Elements of a Finite Group ..................................................... 88 11 Normal Subgroups ....................................................................................... 99 12 Homomorphisms ........................................................................................ 109 13 Homomorphisms and Normal Subgroups .................................... ..... .. ... .... 121 14 Direct Products and Finite Abelian Groups ....... ... .......... ......... .... ... ...... ...... 133 15 Sylow Theorems ........................................................................... ..... ... .. .... 143 16 Rings .......................................................................................................... 153 17 Subrings, Ideals, and Quotient Rings ....................... .... ............ .. ....... ......... 164 18 Ring Homomorphisms ............................................................................... 177 19 Polynomials .................. ..... ....... ..... .............. ............ ........... ................. .... ... 191 20 From Polynomials to Fields .... ......... ........ ...... .. ....... .................. ........... ... ... 205 21 Unique Factorization Domains ...... .... ..... ........ ............ .......... ......... ... .......... 211 22 Extensions of Fields ................. ..... .. .... ....................... ............... ........ ...... .. . 227 23 Constructions with Straightedge and Compass .......... .. ............ ........... ... .. .. 240 24 Normal and Separable Extensions ... ..... .... ....................... ......... ....... ..... ... ... 249 25 Galois Theory ............................................................................................. 265 26 Solvability ........... ... ........... ................... ...... .... ............................................ 279

Suggestions for Further Reading .... .. .......... ............... ............ ..... .... ........ ... 297 Answers to Selected Exercises ....................... ....... ........ ............. ... .... ......... 301 Index .......................................................................................... ........ ....... .. 307

PREFACE

This book is intended for use in a junior-senior level course in abstract algebra. The main change from the first edition is the addition of five new sections on field extensions and Galois theory, providing enough material for a two- semester course. More minor changes include the simplification of some points in the presentation, the addition of some new exercises, and the updating of some historical material.

In the earlier sections of the book I have preserved the emphasis on providing a large number of examples and on helping students learn how to write proofs. In the new sections the presentation is at a somewhat higher level. Unusual features, for a book that is still relatively short, are the inclusion of full proofs of both directions of Gauss' theorem on constructible regular polygons and Galois ' theorem on solvability by radicals, a Galois-theoretic proof of the Fundamental Theorem of Algebra, and a proof of the Primitive Element Theorem.

A one-semester course should probably include the material of Sections 0-13 , and some of the material on rings in Section 16 and the following sections. Sections 14 and 15 allow the inclusion of some deeper results on groups. The results of Section 14 are used in Section 15, and the First Sylow Theorem from Section 15 is used in Sections 25 and 26.

In two semesters it should be possible to cover the whole book, possibly omitting Section 21.

I want to express my appreciation to my students who used the manuscript for the five new sections as a text and pointed out to me parts of the presentation that needed clarification. I also want to thank all those who have sent me comments about the book over the years, and those who suggested that a new edition would be a good idea. I hope this second edition will be useful.

Dan Saracino

SECTION 0

SETS AND INDUCTION

One of the most fundamental notions in any part of mathematics is that of a set. You are probably already familiar with the basics about sets, but we will start out by running through them quickly, if for no other reason than to establish some notational conventions. After these generalities, we will make some remarks about the set of positive integers, and in particular about the method of mathematical induction, which will be useful to us in later proofs.

For us, a set will be just a collection of entities, called the elements or members of the set. We indicate that some object x is an element of a set S by writing xES. If x is not an element of S, we write x f£ S.

In order to specify a set S, we must indicate which objects are elements of S. If S is finite, we can do this by writing down all the elements inside braces. For example, we write

S={1,2,3,4}

to signify that S consists of the positive integers 1,2,3, and 4. If S is infinite, then we cannot list all its elements, but sometimes we can give enough of them to make it clear what set S is. For instance,

S= {1,4, 7,10,13,16, ... }

indicates the set of all positive integers that are of the form 1 + 3k for some nonnegative integer k.

We can also specify a set by giving a criterion that determines which objects are in the set. Using this method, the set {l,2,3,4} could be denoted by

{xix is a positive integer ~4},

where the vertical bar stands for the words "such that." Likewise, the set {1,4,7, 10, 13, 16, ... } could be written as

{xix = 1 + 3k for some nonnegative integer k}.

1

2 Section O. Sets and Induction

Some sets occur so frequently that it IS worthwhile to adopt special notations for them. For example, we use

Z to denote the set of all integers,

Q to denote the set of all rational numbers,

R to denote the set of all real numbers, and

C to denote the set of all complex numbers.

The symbol 0 denotes the empty set or null set, i.e., the set with no elements. Sometimes we wish to express the fact that one set is included in another,

i.e., that every element of the first set is also an element of the second set. We do so by saying that the first set is a subset of the second.

DEFINITION If Sand T are sets, then we say that S is a subset of T, and write S k T, if every element of S is an element of T.

Examples If S={1,2,3} and T={l,2,3,4,5}, then SkT. If S= {7T, V2} and T= {7T,5, V2 }, then S k T. We write S g{5, V2}

because 71' E S but 71' f1. {5, V2 }. If we let

z+ = {xix is a positive integer}, then Z+ kZ; similarly, we have Q+ kQ and R+ kR

Observe that for any set S, S k S, that is, S is a subset of itself. Also observe that 0 k S, no matter what set S is. Perhaps the best way to see this is to ask yourself how it could be false. If 0 g S, then there is some x E0 which is not in S; but this is nonsense, because there is no x E0, period.

We say that two sets Sand T are equal, and we write S= T, if S and T have the same elements. Clearly, then, saying that S = T is equivalent to saying that both S k T and T k S. If S k T but S=I=T, we say that S is a proper subset of T. If we wish to emphasize that S is a proper subset, we write

S 1- T. Very often we consider sets that are obtained by performing some

operation on one or more given sets. For example, if Sand T are sets, then their intersection, denoted by S n T, is defined by

S n T= {xlxES and xE T}. The union of Sand T, denoted by S U T, is given by

S U T = { x I xES or x E T or both}.

Section O. Sets and Induction 3

The union and intersection of more than two sets are defined in an analogous way; for instance,

S n Tn U = {xix E S and x E T and x E U}.

Examples Let S={1,2,3,4,5} and T={2,4,6}. Then SnT={2,4} and S U T= {l,2,3,4,5,6}.

Again let S= {l,2,3,4,5}. Then S n ~= Sand S u ~= IR.

We can illustrate many of the notions we have introduced by generalizing this last example.

THEOREM 0.1 Let Sand T be sets. Then S ~ T if and only if S n T= S.

PROOF. We must show that S ~ T implies S n T= S, and that conversely S n T= S implies S ~ T.

Assume S ~ T. To show that S n T= S we have to show that S n T ~ S and S ~ S n T. The first is clear; for the second we must show that every element of S is an element of S and of T. Clearly any element of S is an element of S; and since we are assuming S ~ T, any element of S is an element of T, too, so we are done with the first half of the proof.

Now assume S n T= S; we show that S ~ T. Why is it true that any element of S is an element of T? Because any element of S is an element of S n T by our assumption, and any element of S nTis clearly an element of T·O

It is also true that S ~ T if and only if S u T= T. The proof of this is left as an exercise.

As a matter of notation, we adopt the abbreviation "iff" for "if and only if." Thus we say that S ~ Tiff S u T= T. Sometimes the symbol ~ is used in place of iff; using ~, we would write S ~ T~S U T= T.

One set that is particularly important in mathematics is the set 1.. + of positive integers. We will see that, in abstract algebra, concepts defined in terms of positive integers can often help to clarify what is going on. For this reason, methods for working with integers can be very valuable tools. Perhaps the most useful strategy for proving things about 1..+ is the method of mathematical induction.

Suppose we have in mind a statement P(n) about the integer n. For example, P(n) might say "n is even," or "n is the square of some integer," or "If p is a prime, then every group of order p n has nontrivial center" (whatever that means). Mathematical induction provides us with a way of trying to prove that P(n) is true for every positive n.

4 Section O. Sets and Induction

The technique rests on an intuitively acceptable axiom called the

Well-Ordering Principle: Every nonempty subset of 7L.+ has a smallest element.

The well-ordering principle yields two slightly different forms of induction, both of which are good to know.

nIEOREM 0.2 (Mathematical Induction, first form) Suppose pen) is a state- ment about positive integers, and we know two things:

i) pel) is true;

ii) for every positive m, if P( m) is true, then P( m + 1) is true. Under these circumstances, we can conclude that pen) is true for all positive n.

PROOF. Suppose pen) is false for some positive n. Then S={nlnE7L.+ and P( n) is false} is a nonempty subset of 7L. +. By the well-ordering principle, S has a smallest element, say no' Clearly no*" 1, because P(1) is true by (i). Therefore, no - 1 is a positive integer, and P( no - I) is true because no - I is smaller than no' By (ii), this means that P(no -I + I) is true; that is, P(no) is true, and this contradicts the fact that P(no) is false!

Since the supposition that Pen) is false for some n has led us to a contradiction, we conclude that P( n) holds for all n E 7L. +. 0

What you do to prove something by induction, then, is this. You first show that P(I) is true (this is usually trivial). You then show that for an arbitrary positive m, if P(m) is true, then P(m + I) is true. You do this by assuming that P(m) is true and using this assumption to establish that P(m + 1) is true.

Sometimes people are bothered by the word "assuming" in the last sentence. They get worried that "assuming that P(m) is true" amounts to assuming what we are trying to prove. But it does not, for we are not assuming that P(m) is true for all m. Rather we are arguing, for an arbitrary fixed m, that if P( m) is true for that m, then so is P( m + I). The only way of doing this is to show that P( m + 1) is true on the basis of the assumption that P( m) is.

Examples

1. You may recall that, in calculus, when you are evaluating definite integrals from the definition as a limit of Riemann sums, you run into sums such as 1 + 2 + 3 + ... + n, and you need formulas for these sums in terms of n. The formula for 1 +2+··· + n, for example, is n(n+ 1)/2. Let's prove it, by induction.

We take for pen) the statement that

1+2+··· +n=n(n+l)/2;

Section O. Sets and Induction 5

we hope to show that P(n) is true for all positive n. First we check P(l): It says that 1 = 1(1 + 1)/2, which is certainly true. Second, we assume that P(m) is true for some arbitrary positive m, and we use this assumption to show that P(m + 1) is true. That is, we assume that

1 +2+··· + m=m(m+ 1)/2 [0.1]

and we try to show that

1 + 2 + ... + m + m + 1 = (m + 1)( m + 1 + 1)/2.

The natural thing to do is to add m + 1 to both sides of Eq. [0.1]: 1 +2+··· +m+m+ 1 = [m(m+ 1)/2] +m+ 1.

Now

[U]

[m(m+ 1)/2] +m+ I = [m(m+ 1)+2(m+ 1)]/2= [(m+ 1)(m+2)]/2,

so we have Eq. [0.2]. Therefore, by induction, P(n) holds for all positive n, and we are done.

2. A similar formula, also used in calculus, is

12+22+ ... + n2= n(n + 1~(2n+ 1) .

If we take this equation as P(n), then P(I) says

12= 1(1+1)(2+1) 6 '

which is true. To show that P(m) implies P(m+ I), we assume that

12+22+ ... +m2= m(m+ 1)(2m+ I) 6 '

and we try to show that

2 2 2 (m+ 1)(m+2)[2(m+ 1)+ 1] 1 +2 + ... +(m+ 1) = 6 .

If we add (m+ 1)2 to both sides of Eq. [0.3], we conclude that

12+22+ ... +m2+(m+ 1)2= m(m+ 1!(2m+ 1) +(m+ 1)2,

and the right-hand side is

m(m+ 1)(2m+ 1) +6(m+ Ii (m+ 1)[ m(2m+ 1)+6(m+ 1)] 6 = 6

[0.3]

[004]

(m+ 1)(2m2+7m+6) (m+ 1)(m+2)(2m+3) = 6 = 6 '

so we have Eq. [0.4]. Thus our formula is established by induction.

6 Section O. Sets and Induction

3. The following popular example illustrates the fact that some care is necessary in trying to prove something by induction. We shall "prove" that all horses are the same color.

Let P(n) be the statement: "For every set of n horses, all the horses in the set are the same color." We "prove" P(n) for all n by induction. Clearly, P(l) is true since any horse is the same color as itself. Now assume that P(m) is true and let us show that P(m + 1) holds. Let S be a set of m+ 1 horses; say the horses in S are h l ,h2, ••• ,hm + 1 (h for horse). Now h l ,h2, ••• ,hm comprise a set of m-horses, so since P(m) holds, hl ,h2, ••• ,hm are all the same color. Likewise, h2, h3, • •• , hm + I make up a set of m horses, so h2, h3, ••• , hm + I are all the same color. Combining these statements, we see that all m + I horses are the same color (for instance, they are all the same color as h0.

There must be something wrong with this, but what?

The second form of induction is similar to the first, except that (ii) is modified somewhat.

THEOREM 0.3 (Mathematical Induction, second form) Suppose P(n) is a state- ment about positive integers and we know two things:

i) P(l) is true;

ii) for every positive m, if P(k) is true for all positive k

Under these circumstances, we can conclude that P(n) is true for all positive n.

The verification that this works is like that for the first form, and we leave it as an exercise.

The part that one assumes in trying to establish (ii) in a proof by induction (either form) is called the inductive hypothesis. Thus in the first form, the inductive hypothesis is the assumption that P(m) is true, from which we try to argue that P(m+ 1) is true. In the second form, the inductive hypothesis is that P(k) is true for all positive k

Which form of induction one should use in any particular case depends on the situation at hand. We have seen some examples where the fif$t form is appropriate, and we would like to close with a significant instance where the second form is called for.

U a and b are integers, then we say that a divides b, and we write alb, if there is an integer c such that b=ac. If no such c exists, we write a{b. For instance, 216, 7114, and 3{1O. A positive integer p is called a prime if p > 1 and the only positive integers that divide p are 1 and p. The first few primes are 2, 3,5,7, 11, 13, 17, ....

Section O. Sets and Induction 7

The Fundamental Theorem of Arithmetic asserts that every positive n> 1 can be written as the product of finitely many primes, and that except for a possible rearrangement of the factors, there is only one such factorization.

TIlEOREM 0.4 (Fundamental Theorem of Arithmetic) Let n > 1. Then there are primes PI' P2' P3"" ,Pr (not necessarily distinct) such that n = PIP2' .. Pr' Moreover, if n = ql q2' .. qs is another such factorization, then r = s and the p;'s are the q/s, possibly rearranged.

PROOF. We prove only the existence of a factorization here. The proof of the uniqueness assertion requires some more groundwork and is left to the exercises in Section 4.

We wish to prove that pen) holds for every n ~ 2, where pen) says that n can be written as a product of primes. Accordingly, we start our induction at 2 rather than at 1; we show (see Exercise 0.13) that P(2) is true and that for any m > 2, if P(k) holds for all 2 <. k 2. If m is a prime, then P(m) holds. If m is not a prime, then we can write m = ab, where neither a nor b is m. Thus 2 <. a, b

a=PIP2" ·Pt ' b=qlq2" 'qu

for primes Pi' 'ij. Then

m'" ab = PIP2' .. Pt Qlq2' .. qu'

and we have shown that m can be factored into primes. 0

Notice that all we can say about a and b here is that they are less than m, so we need the inductive hypothesis as in the second form of induction, in order for this proof to go through.

EXEROSES

Sets

0.1 Let S={2,5, Vi ,25,'IT,5/2} and let T={4,25, Vi ,6,3/2}. Find S n T and S U T.

0.2 With Sand T as in Exercise 0.1, show that

In(Su T)=(lnS)u(ln T) and lu(Sn T)=(luS)n(lu T).

0.3 Let S and T be sets. Prove that

Sn(Su T)=S and Su(Sn T)=S.

0.4 Let Sand T be sets. Prove that S U T= T iff S k T.

0.5 Let A, B, and C be sets. Prove that A nCB u C)=(A n B)u(A n C).

0.6 Let A, B, and C be sets. Prove that A U(B n C)=(A u B)n(A u C).

8 Section O. Sets and Induction

Induction

0.7 What's wrong with the proof that all horses are the same color?

0.8 Prove that

for all n> l.

0.9 Prove that

for all n> l.

0.10 Prove that

for all n> l.

1 +3+5+ ... +(2n+ I)=(n + 1)2

2 + 4 + 6 + ... + 2n = n( n + 1)

0.11 Prove Theorem 0.3.

0.12 Prove the following more general form of Theorem 0.2:

THEOREM. Suppose P(n) is a statement about positive integers and c is some fixed positive integer. Assume

i) P(c) is true; and

ii) for every m >c, if P(m) is true, then P(m+ 1) is true. Then P(n) is true for all n >c.

0.13 Prove the following more general version of Theorem 0.3:

THEOREM. Suppose P(n) is a statement about positive integers and c is some fixed positive integer. Assume

i) P(c) is true; and

ii) for every m >c, if P(k) is true for all k such that c

0.14 Prove that

for all n >2.

1· 2 + 2·3 +3 ·4+ ... + (n - I)n = -'.,(n_-----"I).",(n.-<-)-'.,(n_+_1....<..,) 3

0.15 By trying a few cases, guess at a formula for

1 1 1 1 -+-+-+ ... + n>2 1·2 2·3 3·4 (n-I)n' .

Try to prove that your guess is correct.

0.16 Prove that for every n> 1, 3 divides n3 - n.

0.17 Prove that if a set S has n elements (where nEZ+), then S has 2n subsets.

Section O. Sets and Induction 9

0.18 The Fibonacci sequence 11.J2.J3,'" is defined as follows:

11 = 12= 1, 13=2, 14=3, Is=5, 16=8, ... ,

and in general,

In=ln-l+ln-2 foralln~3.

Prove thatlsk is divisible by 5 for every k;;;. 1, that is, 5 divides every 5th member of the sequence.

0.19 As in the preceding exercise, letfi denote the kth Fibonacci number. Prove that for every n ~ 1,

g+l- /,,[,,+2 = (-1)".

0.20 Again let//; denote the kth Fibonacci number. Let

l+JS I-JS a=-- and p=--.

2 2

Prove that for every n ~ 1

a" _po 1.= JS .

0.21 The nth Fermat number is Fn = 2(2") + 1. Prove that for every n ~ I

F'oF;Fz ... Fn_1 = F" - 2.

0.22 Prove that the following statement is true for every integer n ~ 1: If the number of squares in a "checkerboard" is 2" x 2" and we remove anyone square, then the remaining part of the board can be broken up into L-shaped regions each consisting of

3 squares.

SECTION 1

BINARY OPERATIONS

In high school algebra, we spend a great deal of time solving equations involving real or complex numbers. At the heart of it, what we are really doing is answering questions about the addition and multiplication of these numbers.

In abstract algebra, we take a more general view, starting from the observation that addition and multiplication are both just ways of taking two elements and producing a third, in such a way that certain laws are obeyed. We study the situation where we have a set and one or more "operations" for producing outputs from given inputs, subject to some specified rules.

From this description, it i~ probably not clear to you why abstract algebra is any more profitable than going off and counting the grains of sand on the nearest beach. But it can be very profitable, for a number of reasons. For one thing, the abstract approach may clarify our thinking about familiar situa- tions ~y stripping away irrelevant aspects of what is happening. For another, it may lead us to consider new systems that are valuable because they shed light on old problems. Yet again, a general approach can save us effort by dealing with a number of specific situations all at once. And finally, although it can take some time to appreciate this, abstraction can be just plain beautiful.

DEFINITION If S is a set, then a binary operation * on S is a function that associates to each ordered pair (S),S2) of elements of S an element of S, which we denote by s) * S2'

Observe that the definition says ordered pair. Thus (S),S2) is not neces- sarily the same thing as (S2'S)), and S) * S2 is not necessarily the same thing as S2 * s). Notice too that * must assign an element of S to each and every pair (S),S2)' including those pairs in which s) and s2 are the same element of S.

10

Section 1. Binary Operations 11

Examples

1. Addition is a binary operation on Z+: a * b = a + b. Subtrac- tion (a *b = a - b) is not; but subtraction is· a binary operation on Z.

2. Multiplication (a*b=a·b) is a binary operation on Z+ or Z or ~ or Ill. Division (a * b = a / b) is a binary operation on III + or ~ + but not Z or Z + or ~ or Ill.

3. a*b=a3 +b2 +1 is a binary operation on Z, 1Il,~, Z+, 1Il+, or ~+.

4. Let X be some set and let S be the set of all subsets of X. For example, if X={1}, then S={0,{I}}, and if X={1,2}, then

S = {0, { I }, {2 }, { 1,2} }.

The operation of intersection is a binary operation on S, since if A,B are elements of S, then A * B = An B is an element of S. Similarly, union gives us another binary operation on S.

S. Let S be the set of all 2 X 2 matrices with real entries. Thus an element of S looks like (: !), where a,b,c,deR. Define x*y to be the matrix product of x and y, that is,

f)=(ae+bg h ce+dg

Then * is a binary operation on S. For instance,

af+bh). cf+dh

I ) _(." -1 I

3-.,,) o . The definition of binary operation doesn't impose any restrictions on *,

and in general a binary operation can be wildly misbehaved. Ordinarily, we want to consider operations that have at least something in common with familiar, concrete examples.

DEFINITIONS If * is a binary operation on S, then * is called commutative if 3 1 *32 =32 *31 for every 3 1,32 E S. On the other hand, * is called associative if (31 *32)*33 =SI * (S2 *33) for every 31,32,S3ES.

Examples

1. Subtraction on Z is neither commutative nor associative. For example,

1-2::;=2-1 and (1-2)-3*1-(2-3).

2. Let a*b=2(a+b) on Z; then clearly * is commutative. Now (a * b) *c =2(a + b) *c=2(2(a + b) + c)=4a+4b+2c,

12 Section 1. Binary Operations

and

a. (b.c) = a .2(b+ c)=2(a+2(b+ c»=2a +4b+4c. Since these are not always the same, • is not associative.

3. Let a. b = 2ab on lL. Commutativity is again clear, and since (a.b).c =2ab .c=4abc and a. (b*c)= a*2bc=4abc,

* is also associative in this case.

4. Multiplication of 2 X 2 matrices is associative:

as may be verified by multiplying out both sides. This operation is not commutative, however. For example,

(01 01)*(31 42)=(31 4) (1 2) (0 1) (2 1) 2 but 3 4 * 1 0 = 4 3· Before we consider a slightly more complicated example, observe that

these first four examples say something about the relationship between commutativity and associativity-namely, that there isn't any! A binary operation can be commutative with or without being associative, and it can be noncommutative with or without being associative.

5. We introduce another operation on sets: If A,B are sets, then A t:;.B denotes the symmetric difference of A and B. This is by definition the set of all elements that belong to either A or B, but not to both. Thus

A t:;.B=(A - B)U(B-A),

where A - B denotes the set of elements of A that are not elements of B, and B-A denotes the set of elements of B that are not elements of A. We can also write

At:;.B=(AUB)-(AnB).

In Fig. 1.1, if A is the set of points inside the square, and B is the set of points inside the circle, then At:;. B consists of the points in the shaded region:

FIgure 1.1

Section 1. Binary Operations 13

For example, if A = {1,2,3,4,5} and B= {2,4,6}, then A .::.B= {l,3,5,6}. If

A={xlxElandx>O} and B={xlxElandx

then

A .::.B= {xIXE land x*O}.

For any set A, A.::.A =0 and A .::.0=A. Now let X be a set and let S be the set of subsets of X. Then A .B=A.::.B

defines a binary operation on S. It is easy to see that .::. is commutative (Exercise 1.7). We claim that.::. is an associative operation on S; that is, if A, B, C are subsets of X, then

(A .::.B).::.C=A .::.(B.::.C).

To verify this we have to show that each side of the equation is contained in the other. Let's assume that xE(A .::.B).::.C and show that xEA .::.(B.::.C).

Since xE(A.::.B).::.C, we have either:

Case I. x E(A .::. B) and x f1. C, or

Case II. x f1.(A .::. B) and x E C.

In Case I, xE(A.::.B) implies that either xEA and xf1.B or xf1.A and x E B. If the first of these holds, then we have x EA,x f1. B,x f1. C, so that xEA and xf1.(B.::.C), so xEA.::.(B.::.C). If the second holds, then we have xf1.A,xE B,x f1. C, so that x f1.A and xE(B.::. C), so xEA .::.(B.::. C).

In Case II, x f/. A .::. B implies that either x E A and x E B, or x f1. A and xf1.B. If the first alternative holds, then we have xEA, xEB, and xEC, so that xEA and xf1.(B.::.C), and therefore xEA.::.(B.::.C). If the second alternative holds, then we have x f1. A , x f1. B, and x E C, so x f1. A and xE(B.::.C), and therefore xEA.::.(B.::.C).

This completes the proof that (A .::.B).::. C <;:A .::.(B.::. C). The proof of the reverse inclusion is left as an exercise.

Before leaving these ideas it might be well to say a bit more about the need for talking about them in the first place. We are all so familiar with the commutativity and associativity of addition and multiplication on the in- tegers, rationals, and reals that we take them for granted. It never occurs to us that they could be called into question. The point is that as we broaden our perspective and consider less familiar systems, we run into many where commutativity and associativity no longer hold true. Thus we have to be careful in working with such systems; we can only use commutativity and associativity in carrying out calculations if we have first ascertained that they happen to hold for the system we are working with. Calculations with the

14 Section 1. Binary Operations

integers are easy because we can replace xy by yx whenever we feel like it, and we never have to worry about (x+y)+z being the same as x+(y+z). In general, we are not so lucky, and we do 4ave to worry about such things.

EXERCISES

1.1 For the given sets S and T, find SAT.

a) S .. {2,5, V2 , 25, "IT, 5/2}, T= {4,25, V2 ,6,3/2}

b)S={(! ~),(~ ~),(g !I)'(! !)}, T= {(~ ~),(g n,u ~)}

1.1 If A, B, and C are the sets of points inside the three circles below, what region represents (A A B) A C?

1.3 In each case, determine whether or not the given • is a binary operation on the given set S.

a) S .... Z, a.b=a+,b2

b) S ... Z, a.b=a2b3 a

c) S-a,a.b=-- a2 +b2

d) S=Z a.b= a2 +2ab+ b2 , a+b

e) S .. Z, a.b=a+b-ab

f) S-R, a.b=b

g) S- {I, -2,3,2, -4}, a.b= Ibl h) S={1,6,3,2,18}, a.b=ab.

i) S .. the set of all 2 x 2 matrices with real entries, and if

then

j) S-the set of all subsets of a set X, A .B=(A AB)AB.

Section 1. Binary Operations 15

1.4 Is division a commutative operation on R+? Is it associative?

1.5 If 8 is the set of subsets of a set X, is the operation of intersection commutative on 8? Is it associative?

1.6 For each case in Exercise 1.3 in which. is a binary operation on 8, determine whether • is commutative and whether it is associative.

1.7 Show that symmetric difference is a commutative operation.

1.8 Complete the proof that symmetric difference is an associative operation.

1.9 If 8 is a finite set, then we can define a binary operation on 8 by writing down all the values of $. *$2 in a table. For instance, if 8= {a,b,c,d}, then the following gives a binary operation on 8.

Columns

• a b c d a a c b d

Rows b c a d b c b d a c d d b c a

Here, for $.,$2 E 8, $. *$2 is the element in row $. and column $'];. For example, c. b = d.

Is the above binary operation commutative? Is it associative?

1.10 How many binary operations are there on a set 8 with n elements? How many of these binary operations are commutative?

SECTION 2

GROUPS

As we have said, algebra is the study of various kinds of abstract systems. One of the most fundamental of these systems is the kind known as a group. In this section we shall get acquainted with this concept.

Certainly one of the attractive features of modem mathematics is the intertwining that takes place among its different branches. If you study algebra, analysis, topology, or mathematical logic, for example, you will see that certain ideas recur in all of them. The notion of a group is one of these ideas that seem to crop up everywhere. Beyond that, groups are important in areas where mathematics is used as a tool, such as chemistry, quantum mechanics, and elementary particle physics.

DEFINI110N Suppose that:

i) G is a set and * is a binary operation on G, ii) * is associative,

iii) there is an element e in G such that x * e = e * x = x for all x in G, and iv) for each element x E G there is an elementy E G such that x * y = y *x = e.

Then G, together with the binary operation *, is called a group, and is denoted by (G, *).

Observe that (iii) implies that G is nonempty. The element e in (iii) is called an identity element of G (we shall soon see that there is only one such element, so we will be able to call it the identity element of G). The elementy in (iv) is called an inverse of x; we shall see that any element x has only one inverse, so we can call it the inverse of x. It is worth emphasizing the fact that the single identity element e satisfies x * e = e * x = x for any choice of x, while the y in (iv) depends on x. We shall see that two distinct elements of G can

16

Section 2. Groups 17

never have the same inverse, so that if we picked a different x we would have a differenty.

It is also worth emphasizing that we do not assume that. is commutative. Groups with the special added property that their operation is commutative are called abelian, after the Norwegian mathematician Niels Abel (1802- 1829).

Before we begin investigating the properties of groups in general, we will examine a number of examples in order to try to convey some impression of the universality of this notion. Historically, of course, the examples preceded the abstract definition; the abstract concept of "group" came into being only when people realized that many objects they were working with had various structural characteristics in common, and got the idea that some economy of effort could be achieved by studying these common features abstractly rather than over and over again in each separate case. In discussing the development of the subject, E. T. Bell has remarked that "wherever groups disclosed themselves, or could be introduced, simplicity crystallized out of comparative chaos."

We begin with the most familiar examples.

1. (I, +). 0 is an identity element, and - x is an inverse for x:

x+( - x)=( -x)+x=O.

We are all familiar with the fact that + is an associative binary operation on I.

Similarly, (0, +) and (R, + ) are groups.

2. (0 +, .). Multiplication is an associative binary operation on 0 +, 1 is an identity element, and 1/ x is an inverse for x since x . (1 / x) = (1 / x)· x = 1.

Similarly, (R+, .) is a group. Observe, however, that (l+, .) is not a group, since no element other than 1 has an inverse. (R - {OJ, .) and (0 - {OJ, .) are groups. The set R - of negative real numbers under multiplication is not a group because multiplication is not a binary operation on R-.

3. The set of n-tuples (a" ... ,a,,) of real numbers is a group under the binary operation given by addition of n-tuples:

(a"a2, ... ,a,,). (b"b2, ... ,bn) = (a, + b"a2 + b2, ... ,an +bn).

(0,0, ... ,0) is an identity element and (- a" - a2, ••• , - an) is an inverse for (a" a2, ... , an). The fact that this operation is associative follows from the associativity of addition on R.

If you have studied vector spaces, then you can see that, more generally, the elements of any vector space form a group under vector addition.

18 Section 2. Groups

4. Consider the binary operation on R given by a. b = 2( a + b). Then (R, .) fails to be a group for several reasons. First of all, • is not associative. Secondly, there is no identity element. For suppose e were one. Then we would have a.e=a for every a, that is, 2(a+e)=a. But this implies that e = - a /2, and clearly no one number can satisfy this equation for all a's. Thus there is no identity element e.

However, if we try instead R-{O} with the binary operation a.b=2ab, then we do get a group. For now • is associative, and 1/2 is an identity element because for any a we have a.(l /2) = 2a· (I /2) = a, and similarly (1/2).a=2·(1/2)·a=a. What is an inverse for a? If x is to work, then we need a. x = 1/2 = x. a, that is, 2ax = 1/2 = 2xa. Clearly x = 1/ 4a meets ·the requirement.

S. Consider the set of 2 X 2 matrices with real entries, under the binary operation given by matrix multiplication. Is this a group? The only candidate for an identity element is 1= (~ ~), because this is the one and only matrix

(; ~) such that

(~ ;)(; {)=(; {)(~ ;)=(~ ;) for all matrices (= !). [Try (= !)= U ~)!] But then an inverse for (= !) would just be a matrix (; ~) such that

0) I . Since such a matrix need not exist [try (= !) = (~ ~)], we do not have a group.

However, we can attempt to salvage something here by throwing away the matrices that do not have inverses. That is, we now let G be the set of all invertible 2 x 2 real matrices. An immediate question is whether matrix multiplication still gives us a binary operation on this smaller set. That is, if A and B are invertible, then is AB invertible? Recalling that matrix multiplica- tion is associative, we see that if A' and B' are inverses for A and B, respectively, then

(AB)(B' A') = «AB)B')A' = (A(BB'»A' = (AJ)A' = AA' = I,

and similarly (B'A')(AB)=I,

so B'A' serves as an inverse for AB. Thus we do have a binary operation on the restricted set G, and it is

associative. There is an identity element in G, because I=(~ ~) is invertible.

Section 2. Groups 19

Finally, any A E G has an inverse A' which is in G, because the equations AA I = A I A = I tell us that A I is invertible (its inverse is A). Thus G is indeed a group under matrix multiplication. It is called the general linear group of degree 2 over IR and denoted by GL(2, IR).

If A = ( : !) is a matrix, then the number ad - be is called the determi- nant of A. Determinants are often very useful in working with matrices. For instance, it is easy to check that if ad-be=l=O, then A is invertible, and the matrix

ad: be

ad-be ad-be

is an inverse for A.

( ad~~ch< -b) 6. Let G consist of all real-valued functions on the real line, with the

binary operation given by pointwise addition of functions: If f,gE G then f+g is the function whose value at any xEIR isf(x)+g(x).

It is clear that this does give us a binary operation on G. To check associativity, we must verify that

(f+g)+h=f+(g+h)

for allf,g,hEG, and this means that for every xEIR,

[(f+ g) + h ](x)= [f+ (g+ h) ](x), that is, (f + g)(x) + hex) = f(x) + (g+ h){x), that is,

[f( x) + g( x) ] + h( x) = f{ x) + [ g{ x) + h{ x) ], which is true since f(x), g(x), and h(x) are real numbers and addition of real numbers is associative.

The zero function-that is, the functionfoEG such thatfo(x)=O for all x E IR-is an identity element:

(fo+ g) = (g+ fo) = g for all gE G.

Why? We must check that for any x E IR,

which is true.

(fo+ g){x) = (g+ fo)(x) = g{x), that is,

fo(x) + g(x) = g(x) + fo(x) = g(x), that is,

0+ g{x) = g(x)+O= g{x),

If f E G, then - f is an inverse of f, where - f is defined by

(- f){x) = - [f(x)] for all xER

20 Section 2. Groups

Why? We have

(- f+ f)(x)=( - f)(x) + f(x) = - [f(x)] + f(x) =0, and

[f+( -f) ](x)= f(x)+( - f)(x) = f(x)- [f(x)] =0, for all xER. Thus (-j)+f=fo andf+(-j)=fo, so (-j) is an inverse off.

Thus G is a group with the given operation.

7. Let X be a set, let S be the set of all subsets of X, and consider the binary operation of symmetric difference on S.

This is indeed a binary operation on S, and we have seen that it is associative: (A L!.B)L!. C=A L!.(B L!. C).

Is there an identity element? In other words, is there e E S such that A L!.e= eL!.A =A for all A E S? Well, A L!.e=A implies that An e=0, and it also implies that e!;;;A. Thus e would have to be the null set. Let's check that e=0 works:

A L!.0=(A u0)-(A n0)=A -0=A,

and

0L!.A =(0UA)-(0nA)=A,

so 0 is in fact an identity element. How about inverses? An inverse B of A would have to satisfy

AL!.B=0=BL!.A.

This implies that A!;;;B and B !;;;A, so B would have to be A; in fact A L!.A =0, so A itself is an inverse for A.

Thus S forms a group under the operation of symmetric difference. As a matter of notation, the set of subsets of a set X is called the power set of X, and denoted by P(X). Thus we have the group (P(X), L!.).

Finally, we consider some groups obtained from Z.

8. Additive group of integers modulo n. Let n be a positive integer and consider the set Zn = {O, 1,2, ... ,n-l}. We add the elements of Zn modulo n, i.e., we add them as integers and then disregard multiples of n so as to produce an answer that is one of 0, 1,2, ... , n - 1. There is a lemma which we need to make this work. (A lemma in mathematics is a preliminary or auxiliary result, not the main result one is aiming at.)

LEMMA l.1 (Ibe Division Algoritbm) If a and n are integers and n is positive, then there exist unique integers q and r such that a = qn + r and 0'" r

PROOF. We prove the existence of q and r, then the uniqueness.

Section 2. Groups 21

Existence: Let qn be the greatest multiple of n that is <; a. If we let r = a - qn then clearly r> 0 and a = qn + r, so all we have to check is that r < n. But if r>n, then

r-n=a-(q+ l)n > 0,

so (q+ l)n is a multiple of n that is <; a, contradicting the choice of qn as the greatest such multiple.

so rz-rl is a multiple of n; but -n< rz-rl < n, so rz-rl=O, so rz=rl. Thus q1n=qzn, so ql =qz· 0

We denote the unique r guaranteed by the lemma by ii, and call it the remainder of a mod n.

Observe that two integers a l and az have the same remainder mod n iff a l - az is a multiple of n. When this happens, we say that a l and az are congruent modulo n, and we write a l == az(mod n).

Examples Let n=7. Then if a= 16, we get 16=2·7+2, so q=2, r=2, and 16=r=2. If a=35, we get 35=5'7+0, so 35=0.

By the lemma we can unambiguously define a binary operation E9 on In by setting xE9y =x+ y. For example, if n=7, then In = {O, 1,2,3,4,5,6}, and 3E92=3+2=5=5, 3E94=3+4=7=0, and 6E93=6+3=9.=2.

We claim that this operation turns In into a group (In, e).

Associativity: The question is whether (xE9y)E9z = xE9(yez), that is, -- ? -- x+y E9z = xey+z,

? ---===- x+y+z=x+y+z.

Well,

x+y +z = (x+y)+z

since x+y and (x+y) differ by a multiple of n; similarly,

x+ y+z = x+(y+z).

So all we have to check is whether (x+y)+z equals x+(y+z). But this is obviously so, since (x+y)+z=x+(y+z).

22 Section 2. Groups

Identity: The identity element is O. Why? Qffix=O+x=x=x if O<;x<;n-l, and, similarly, xffiO= x.

Inverses: We know that 0 is an inverse for 0, since OffiO=O+O=O=O, the identity element. Now if x * 0, then x E {I, 2, ... , n - I}, so n - x E {1,2, ... ,n-l}, and we see that n-x is an inverse of x:

xffi(n-x)= x+n-x =n=O,

and, similarly, (n-x)ffix=O. For example, in (1:.7' ffi), 1 is an inverse for 6, and 3 is an inverse for 4. In

(1:.)3' ffi), 5 is an inverse for 8.

The group (1:.n' ffi) is called the additive group of integers mod n. Notice that, for n = 1, we have 1:.) = {OJ, so (1:.), ffi) is a group with only one element in it. In general, any group having only one element is called trivial. If x is any object whatsoever (e.g., x = Whistler's Mother), then we get a trivial group ({x},*) by defining x*x=x.

EXEROSES

2.1 Which of the following are groups? Why?

a) R+ under addition

b) The set 3l of integers that are multiples of 3, under addition

c) R - {O} under the operation a. b = labl d) The set p, -I} under multiplication e) The subset of Q consisting of all positive rationals that have rational square

roots, under multiplication

f) The set of all pairs (x,y) of real numbers, under the operation (x,y).(z, w) "'(x+z,y -w)

g) The set of all pairs (x,y) of real numbers such thaty #0, under the operation (x,y).(z, w)=(x+ z,yw)

h) R- {I}, under the operation a*b=a+ b-ab

i) l, under the operation a. b = a + b - 1 2.2 a) Of those examples in Exercise 2.1 that are groups, which are abelian?

b) Which of the groups in Examples 1-8 on pp.17-20are abelian?

2.3 Let X be a set and let P(X) be the power set of X. Does P(X) with the binary operation A • B = A n B form a group? How about P(X) with the binary operation A .B=A UB?

Section 2. Groups 23

1.4 The operation in a finite group can be specified by writing down a table (see Exercise 1.9). Write down the tables for the following.

a) (l4' $)

b) (ls, $)

c) (l6, $)

1.5 The following table defines a binary o~ration on the set S= {a,b,c}.

Is (S,.) a group?

• abc

a b c

a b c

b b c

c c c

1.6 The following table defines a binary operation on the set S={a,b,c}.

• a b c a a b c b b a c c c b a

Is (S,.) a group?

1.7 Let S = {a,b}. Write down a table that defines a binary operation. on S such that (S,.) is a group. Show that your table works.

1.8 Let G be the set of all real-valued functions f on the real line which have the property that f( x) * 0 for all x E R. Define the product f X g of two functions f,ginGby

(fXg)(x)= f(x)g(x) for all xEIIl.

With this operation, does G form a group? Prove or disprove.

1.9 a) Show that for 2 X 2 matrices A and B,

determinant of AB=(determinant of A)(determinant of B).

b) Show that a 2 X 2 matrix A is in GL(2, R) iff the determinant of A is not O.

c) Use the results of (a) and (b) to give another proof that GL(2, Ill) is a group under matrix multiplication.

1.10 Let G be the set of all 2 X 2 matrices (a b), where a, b E III and a2 + b2 * O. -b a

Show that G forms a group under matrix multiplication.

1.11 Let G be the set of a1l2x2 matrices (~ ~), where a and b are nonzero real numbers. Show that G forms a group under matrix multiplication.

l.ll Let G be the set of all triples (a,b,c) such that a,b,c are elements of~. Define * by (aJ, bJ, CI) * (a20 b2, C2) = (al $ a2, bl $ b" CI $ C2 E9 bla~,

where all additions and multiplications are performed mod 3. Prove that (G, *) is a group.

24 Section 2. Groups

2.13 Let al,a2, ... ,an be elements of a group G. Show that

has an unambiguous meaning in the sense that no matter how we insert parentheses into the expression to indicate the order in which the multiplications are carried out, we always get the same result. [Suggestion: Show that any insertion of parentheses gives the same answer as

al. (a2. (a3. (a4 • ...• (an-l .an)·.· »). To do this, use induction on n.]

2.14 If Xis a set and At, ... ,An are elements of (P(X),6.) then by Exercise 2.13 A lM 26.· . 'Mn has an unambiguous meaning. Prove that for every n ;::: 1 the elements of X that are in AlM 26.· . 'M" are exactly those elements that are inAj for an odd number ofj's in {l, 2 •...• n}.

SECTION 3

FUNDAMENTAL THEOREMS ABOUT GROUPS

If we hope to get anywhere in working with groups, there are certain fundamental facts about their behavior that we must master at the outset. The operation * in a group comes to us endowed only with the properties given to it by the group axioms. Everything else must follow from these, and our first task is to use the axioms to set down some basic rules of operation that enable us to carry out with ease at least some elementary calculations.

First, a convention: We usually call the operation in a group "multiplica- tion"; but very often the operation is called "addition" if the group happens to be abelian.

1HEOREM 3.1 (Uniqueness of the identity element) If (G, *) is a group, then there is only one identity element in G.

PROOF. We must establish that if e and e} are two elements of G both of which satisfy the defining property of an identity element in G, then in fact e= e}. That is, we assume that x *e= e*x= x for all x in G and x *e} = e} *x = x for all x in G, and we then proceed to show that e must equal e}.

By the assumption on e, we have in particular (taking x to be e}) e}*e=e*e}=e}.

By the assumption on e}, we have (taking x to be e) e*e}=e}*e=e.

Thus we have e} = e * e} = e, and the proof is complete. 0

1HEOREM 3.2 (Uniqueness of inverses) If (G, *) is a group and x is any element of G, then x has only one inverse in G.

PROOF. We must show that if both y} and Y2 satisfy the definition of an inverse of x, that is, if x*y}=y}*x=e and X*Y2=Y2*x=e, then in fact Y}=Y2·

25

26 Section 3. Fundamental Theorems about Groups

We will take some of the given information and use it to derive an equation which has YI on one side and Y2 on the other. It may leap to your eye, for example, that

because both sides are e. Once this is seen, all that remains is to get rid of the x's. We can do this by using more of the given information, namely the fact thatYI*x=e. We multiply both sides by YI:

YI*(x*YI)=YI*(X*h)·

By using associativity, we get from this

as desired. 0

(YI*X)*YI =(YI*X) *Y2'

e*YI = e *Y2' YI=Y2'

The proof is finished, but we are going to do it again in a slightly different way to illustrate the fact that there are often several different ways to prove something. Suppose, for example, that the equation x * Y I = X * Y2 did not leap to your eye, and that you just took one of the equations given, say

to start with. If you want to get from this an equation withYI on one side and h on the other, then certainly you observe that YI is already on the left, and we can get Y2 on the right by multiplying both sides by h:

(YI *x)*h=e*Y2 =Y2·

Now if only we could get rid of the x and Y2 on the left-hand side, we'd be done; but we know from the equations we had to start with that x * Y2 = e, so we rewrite the left side by using associativity, so as to bring x * Y2 into play:

and we are done. 0

Y I * (x * h) = h, Yl*e=Y2'

YI=Y2'

We emphasize the significance of what we have just proved twice: The group axioms simply assert that for any x, there must exist an inverse; our theorem says that once you know you've got a group, any x has precisely one inverse.

Section 3. Fundamental Theorems about Groups 27

Example Let (G, *) be G L(2, R). Then by applying our general result in this specific case, we conclude that if (: !) is an invertible matrix, then there is only one matrix (; ~) such that

0) I . This fact can of course be established directly, by working with systems

of linear equations in two variables. But one is struck by the economy and elegance-the "cleanness" -of the proof we have obtained by viewing the collection of all invertible 2 X 2 matrices as a group.

Henceforth we will usually denote the unique inverse of x by x -I. When we are dealing with an abelian group and referring to the group operation as addition, however, we will sometimes denote the inverse of x by - x. For example, in GL(2, IR) we write

5)-1={ 7 7 -4

-5) 3 '

and in (Z7' $) we write - 3 =4. The next result will enable us to conclude that no two distinct elements of

a group G can have the same inverse.

TIIEOREM3.3 If (G,*) is a group, then for any xEG we have (X-I)-I=X.

PROOF. Since X-I is the inverse of x, we know that x-I*x=x*x-I=e. By these equations, x satisfies the definition of (X-I)-I, so x=(X-I)-1 by the uniqueness of inverses. 0

That was slick, but let's do it again in a slightly different way. We know that x - I * X = e. We want to get from this to an equation with x on one side and (x - I) - I on the other . We need to get rid of the x - I on the left side, so let's multiply both sides by (X-I)-I:

(X-I) -I * (X-I *x)= (X-I) -I *e

(x -I) -I *x- I) *x = (X-I) -I (using associativity on the left)

e*x=(x-I)-I

x=(x-I)-I. 0

28 Section 3. Fundamental Theorems about Groups

Example Let G = (Z, +). Then for this example the theorem says that - ( - n) = n for any integer n.

Now suppose x,y are elements of a group (G,*) and X-I=y-I. Then by taking inverses on both sides we get (X- I)-I=(y-I)-I, so, by the theorem, x = y. Thus, as promised, if two elements have the same inverse then they must in fact be the same element. It is possible to prove this without reference to the preceding theorem; see Exercise 3.8(b).

Next we examine the inverse of a product.

THEOREM 3.4 If (G, *) is a group and x, y E G, then

PROOF.

= x * ((y *y -I) *x- I) = x * (e*x- I) = x*x- I = e,

and similarly we can show that (y-I*x-I)*(x*y)=e. (Do it!) Thus the elementy-I*x- I satisfies the conditions that define (x*y)-\ and since we already know that inverses are unique, this implies that y -I * X - I and (x * y) -I must be the same element. 0

It is worth emphasizing the reversal of order in the above result. In general, it is not true that (x * y) - 1 is X -I * Y - I. This does, of course, hold true in abelian groups, for then x -I * Y -I is the same thing as y -I * X-I; in fact, the equation (x * y)-I = X-I * Y -I holds for all x, y in a group G if and only if G is abelian (Exercise 3.9).

It is somewhat bothersome to have to check both the conditions (x*y)*(y-I*x-I)=e and (y-I*x-I)*(x*y)=e in the above theorem and, in fact, it is not hard to show that it is really sufficient to check either one of them.

THEOREM 3.5 Let (G, *) be a group and let x, y E G. Suppose that either x * y = e or y * x = e. Then y is x - I.

PROOF. Suppose that x*y=e. We wish to solve this equation for y, so let's mUltiply both sides by x - I :

Section 3. Fundamental Theorems about Groups 29

Thus

(X-1*X)*y=X- 1,

e*y=x-t,

y=x- 1.

A similar argument shows that y * x = e is also by itself sufficient to guarantee thaty=x- 1. (Do it!) 0

The same solving of an equation proves the more general

THEOREM 3.6 (Cancellation laws) Let (G,*) be a group and let x, y, zEG. Then:

i) if x * y = x * z, then y = z; and ii) ify*x=z*x, theny=z.

The proof is left as an exercise. Part (i) is called the left cancellation law, and Part (ii) the right cancellation law.

We close this section by giving another formulation of the axioms for a group which is equivalent to our original definition, but somewhat simpler to work with in establishing that some system is in fact a group.

THEOREM 3.7 Let G be a set and * an associative binary operation on G. Assume that there is an element eEG such that x*e=x for all xEG, and assume that for every x E G there exists an element y in G such that x * y = e. Then (G,*) is a group.

The element e is called a right identity, and the element y associated to x is called a right inverse of x. In order to prove the theorem we have to show that G satisfies all the axioms for a group, and since we have assumed that * is a binary operation on G and * is associative, we have only to verify that e is, in fact, also a left identity, that is, e * x = x for all x E G; and that a right inversey of x is also, in fact, a left inverse of x, that is,y*x=e.

PROOF OF THE THEOREM. First we show that e *x = x for all x E G. Let us do the proof backwards by trying to obtain some equations that we know would yield e * x = x. Let x' denote a right inverse of x. Certainly it would be enough to have

(e*x) *x' = x *x', [3.1)

for then we could mUltiply both sides by a right inverse of x'. But having [3.1] is the same thing as having

e * (x * x') = x * x',

30 Section 3. Fundamental Theorems about Groups

by associativity, and this is the same thing as having

by the definition of the right inverse x'. Certainly we know that e * e = e, because x*e=x for any xEG.

We have proved e*x=x, because each successive equation in our proof implied the one before it, so that when we finally arrived at a true equation, its truth implied the truth of all the previous equations. It is crucial to realize that in this situation it would not have sufficed to have each equation implying the one after it. In other words, if we want to prove e * x = x, it suffices to show that e * x = x is implied by the true statement e * e = e, but it would not be enough to show that e*x=x implies e*e=e. (A simple example: The false statement" -1 = 1" implies the true statement "I = 1," as we see by squaring both sides; but that doesn't prove - 1 = 1.)

Now let's finish the proof of Theorem 3.7 by showing that a right inverse x' of x is also a left inverse of x, that is, x' * x = e. We know that there is some (x')' such that x' * (x')' = e, and it will suffice to show that x = (x')'. Now from

x*x'=e we get

(x *x') * (x')' = e * (x')', and since we know that e is a left identity, this yields x = (x')'. D

An analogous proof shows that assuming associativity and the existence of a left identity and left inverses is also sufficient to guarantee a group. It should be observed, however, that associativity plus the existence of a right identity and left inverses (or a left identity and right inverses) is not enough.

Example Consider the set Z with the binary operation given by

It is easy to check that * is an associative binary operation on Z and that 1 is a right identity element and also a left inverse for every element of Z. However (Z, *) is not a group since, for example, there is no two-sided identity element in (Z, *).

Since the axioms in Theorem 3.7 are manifestly simpler than those in our definition of a group, you may wonder why we didn't use the simpler version as the definition and then show that the stronger axioms follow. We could have done so, but we decided against it in favor of emphasizing the fact that in a group the identity element and inverses work from both sides.

Section 3. Fundamental Theorems about Groups 31

EXERCISES

3.1 In (Z12,EB), solve the equation 2EBxEB7= I for x.

3.2 Let X= {l,2,3,4,5,6, 7,8,9, IO}. In (P(X), 6), consider the elements A = {l,4,5,7,8} and B= {2,4,6}, and solve A u= B for x.

3.3 Find elements A,B, C of GL(2, IR) such that AB = BC but A =foe.

3.4 Let g be an element of a group (G, • ) such that for some one element x E G, x.g=x. Show that g=e.

3.5 If (G,.) is a group and x, y, z E G, then we can unambiguously write x • y *Z to denote either (x .y) *Z or X. (y .z), since, by associativity, these are the same element. Show that

3.6 Prove the cancellation laws (Theorem 3.6).

3.7 Let G be a finite group, and consider the multiplication table for G, i.e., the table that gives the binary operation of G (see Exercise 1.9). Show that every element of G occurs precisely once in each row of the table and precisely once in each column.

3.8 Use the cancellation laws to give alternative proofs of:

a) Theorem 3.1;

b) the fact that if X-1=y-l then x=y.

3.9 Let (G,.) be a group. Show that (G, .) is abelian iff

(X.y)-I=X-1.y-l for all x,yEG.

3.10 Let (G,.) be a group and let g be some fixed element of G. Show that G={gulxEG}.

3.11 Let (G,.) be a group such that x 2 = e for all x E G. Show that (G,.) is abelian. (Here x 2 means x.x.)

3.12 Let (G,.) be a group. Show that (G,.) is abelian iff (x .y)2= x 2 .y2 for all x, y in G.

3.13 Let G be a set and let. be an associative binary operation on G. Assume that there exists a left identity element in G and that every element in G has a left inverse. Prove that (G, .) is a group.

3.14 Let G be a nonempty set and let. be an associative binary operation on G. Assume that for any elements a, b in G, we can find x E G such that a • x = b, and we can find y such that y • a = b. Show that (G, .) is a group.

3.1S Let G be a nonempty set and let. be an associative binary operation on G. Assume that both the left and right cancellation laws hold in (G,.). Assume moreover that G isfinite. Show that (G,.) is a group.

32 Section 3. Fundamental Theorems about Groups

3.16 Give an example to show that if the assumption that G is finite is omitted from Exercise 3.15, then the conclusion need no longer follow, i.e., (G,.) need not be a group.

3.17 Suppose G is a set and * is an associative binary operation on G such that there is a unique right identity element and every element has a left inverse. Prove that (G, * ) is a group.

SECTION 4

POWERS OF AN ELEMENT; CYCLIC GROUPS

Before going any further in our investigation of groups, we pause to stream- line our notation. You have probably already started to get tired of writing * every time you want to indicate the operation in a group (G, *). It is common practice to avoid this encumbrance by writing xy in place of x * y, so long as no confusion can arise. For example, the equation

(X*y)-I=y-I*X- 1

is usually written

and the associative law

is written

(XY)Z=X(yz).

In keeping with this simplification, we will usually refer to an abstract group as G, rather than (G,*).

In discussing concrete examples, we continue to use whatever notation is appropriate. For example, if we are talking about (1'., +) we write x+y. You are also reminded that the additive notation is very commonly used in discussing any abelian group.

Another economy in notation is achieved by taking advantage of the associative law in order to eliminate parentheses. For example, we can unambiguously write xyz to denote either (xy)z or x(yz), since these two elements are the same. Similarly, if Xl'''' 'Xn are elements of a group, then XIX2X3' .. xn has an unambiguous meaning; no matter how we insert parentheses into the expression, the resulting product always equals

x l(xix 3('" (Xn-IXn)'" ))).

33

34 Section 4. Powers of an Element; Cyclic Groups

Verifying this for yourself is a good way to check your understanding of the associative law. (See Exercise 2.13.)

A word of caution: There are times when parentheses cannot be omitted without changing the meaning of an expression. For example, (xy)-I is not in general the same thing as xy - I.

Now let x be an element of a group G. We define the powers xn of x (for n E l) as follows:

xO=e; xn = xxx' .. x (n factors), if n > 0;

n (-I)n -I -I -I -I x- = X =x x x "'x , if n >0.

Here are the rules for working with exponents.

1HEOREM 4.1 Let G be a group and let x E G. Let m, n be integers. Then:

i) xmxn = xm+n;

ii) (xn)-I=x- n;

iii) (xmr=xnm=(xn)m.

PROOF. i) First suppose that m and n are both positive. Then

xmxn = xx'" x . xx' .. x = xx" . x (by associativity), '---y---' '---r---' '---y---'

m factors n factors m + n factors and this is xm+n. Next, if m and n are both negative, say m= -r and n= -s, then

xmxn=x-rx-s=(X-IY(X-I),=(X-Iy+s (by the first case),

and this is x-(r+s>, that is, xm+n. If m= -rO, then if r>n we have

The remaining cases can be treated similarly, and are left to the reader. (ii) and (iii) are exercises. 0

We observe that if we are writing the group operation additively, then x 2

means x + x, x 3 means x + x + x, and so on. In this context, we usually write nx in place of xn; then (i) above becomes mx+nx=(m+n)x, (ii) becomes -(nx)=( -n)x, and (iii) becomes n(mx)=(nm)x=m(nx).

DEFINITIONS If G is a group and x E G, then x is said to be of finite order if there exists a positive integer n such that xn = e. If such an integer exists, then the smallest positive n such that xn = e is called the order of x and denoted by o(x). If x is not of finite order, then we say that x is of infinite order and write o(x)= 00.

Section 4. Powers of an Element; Cyclic Groups 35

Examples

1. Let G be (Z3; EEl). Then 0(1) = 3, since

17e O,lEElh"'O, and 1 EEl 1 EEl 1 =0. 2. Let G be (Z, +). Then 0(1)= 00, since

he 0, 1+ heO, 1 + 1 + 1",,0, etc. 3. Let G be (10+, .). Then 0(2)=00, since

2",,1, 22 ",,1, 23",,1, 24 ",,1, etc. 4. Let G be G L(2, R). Then o( ( -;1 ~ I ) ) = 2 since

° )2 = ( 1 0) -1 ° 1·

Since the notion of "order of an element" is defined in terms of integers, it is not surprising that one needs some information on integers in order to investigate its properties. We include this material at this point as a change of pace.

If m,n are integers, not both zero, then (m,n) denotes the greatest common divisor (g.c.d.) of m and n. This is by definition the largest integer d that divides both m and n. [If m = n = 0, then (m, n) doesn't exist because every integer divides 0: O=k·O for any k.] It is clear that (m,n)=(lml,lni), so that in what follows we can assume that m and n are nonnegative integers, at least one of which is not zero.

There is a process called the Euclidean algorithm which enables us to find (m,n) by doing some arithmetic. Say n

m=qn+r and O

Now any integer divides m and n if and only if it divides nand r, so the greatest integer that divides m and n is the same as the greatest integer that divides nand r, that is,

(m,n)=(n,r).

The good thing about knowing this is that we have traded in the pair m,n for the pair n,r and in so doing we have replaced the greater of m,n by r, which is smaller than the smaller of m,n. If r=O, then clearly (m,n)=n and we are done. If r""O, then we repeat our trick and find ql and r l such that

n=q1r+r l , where O

(m,n) = (n,r) =(r,r l ),

36 Section 4. Powers of an Element; Cyclic Groups

and we have traded in n for rl, which is even smaller than r. If rl =0, then (m,n)= r. If rl *0, we find q2 and r2 such that

and if r2=0, (m,n)=rl. If r2*0, then we continue the process, obtaining a sequence of remainders r>rl>r2>r3> ... , where each r;>O. By the well- ordering principle, such a decreasing sequence of nonnegative integers cannot go on forever, so some r; must eventually be 0. If so, then

Thus (m,n) is the last nonzero remainder arising from our repeated divisions.

Example Let's find (1251, 1976):

1976= 1251·1 + 725, 1251 =725·1 +526, 725=526·1+199, 526= 199·2+ 128, 199= 128·1 +71, 128=71'1+57, 71=57·1+14, 57= 14·4+ I, 14= 1·14+0.

Here r= 725, rl = 526, r2 = 199, r3 = 128, r4 = 71, rs = 57, r6= 14, r7= I, rs =0. Thus (1251, 1976) = r7 = l. We indicate the fact that the g.c.d. is I by saying that 1251 and 1976 are relatively prime.

Actually our interest in this process is not so much that it enables us to find (m,n), but that it allows us to establish the following fact.

TIlEOREM 4.2 If m and n are integers, not both zero, then there exist integers x and y such that

mx+ny=(m,n).

Thus the g.c.d. of m and n can be written as a "linear combination" of m and n, with integer coefficients.

The utility of this information will become clear in a moment.

Section 4. Powers of an Element; Cyclic Groups 37

PROOF OF THE THEOREM. We write down the steps in the calculation of (m, n) by the Euclidean algorithm, and then use them in reverse order. We have

m=qn+r, n=q1r+rl,

r=q2rl+ r2' r l = q3r2 + r3,

ri - 4 = qi-2ri-3 + ri- 2, ri- 3 = qi-l ri-2 + ri_ i' (ri _ I 7'=O) ri- 2 = qiri-I +0,

so ri - I =(m,n). Now the next-to-last step can be written as

ri _ 1 = l·ri_ 3 - qi- (ri- 2, [4.1] so (m,n) is written as a linear combination of ri - 3 and ri - 2• The preceding step (ri - 4 = qi-2ri-3 + ri- 2) can be used to replace ri- 2 by rj_ 4 - qj-2rj-3 in Eq. [4.1], resulting in an expression for (m,n) as a linear combination of rj _4 and rj _ 3• Using all the equations from the Euclidean algorithm in reverse order, we eventually arrive at an expression for (m, n) as a linear combination of m and n. D

Example We find x and y such that (1251, 1976)= 1251x+ 1976y. Referring back to our calculation of (1251, 1976)= 1, we get:

1=1·57-4·14 = 1· 57 -4(71- 57)= -4· 71 + 5· 57 = -4·71 +5(128-71)= -9·71 +5·128 =5·128-9(199-128)= 14·128-9·199 = -9'199+ 14(526-199·2)= -37·199+ 14·526 = 14·526-37(725 -526) = 51·526-37 ·725 = -37(725)+51(1251-725)= -88·725+51·1251 =51·1251-88(1976-1251)= 139,1251-88·1976.

Thus we can take x = 139 and y = - 88.

After that, one should be in a good frame of mind to appreciate some good clean abstraction, but before returning to groups we derive a con- sequence of the last result that will be useful.

THEOREM 4.3 (Euclid) If r,s, t are integers, r divides st, and (r,s) = 1, then r divides t.

PROOF. Since (r,s)= I, there exist integers x andy such that

rx+sy= 1.

38 Section 4. Powers of an Element; Cyclic Groups

Multiplying both sides of this equation by t yields

rxt+syt= t, or r(xt) + st(y) = t.

Manifestly, r divides r(xt); and r divides st(y) since it divides st by assump- tion. Thus r divides the sum of r(xt) and st(y), i.e., r divides t, as claimed. 0

There are many simple results in number theory which never lose their charm, and that's one of them.

Back to groups.

THEOREM 4.4 Let G be a group and x E G.

i) o(x) = o(x -1). ii) If o(x)=n and xm=e, then n divides m.

iii) If o(x)=n and (m,n)=d, then o(xm)=n/d.

PROOF. The proof of part i) is left as an exercise.

ii) We have xm = e and we seek to make something of the fact that n is the smallest positive integer such that xn=e. Write m=qn+r, where O

xqn+r=e xqnxr=e

(xn)qxr=e.

But x n = e, so the last equation becomes xr=e.

But r is smaller than n, so this is impossible unless r = O. Thus m = qn + 0, so n divides m.

iii) Here we use our information about greatest common divisors. We must show that n/ d is the smallest positive integer k such that (xmi = e. First of all,

(xm)"/d = xm'(n/d)= x(m/d)'n = (xn)m/d = e m/ d = e,

since o(x) = n. Now suppose k> 0 and (xn'l = e. We will show than nld divides k and therefore, since nld and k are positive integers, nld:s; k. We have xnk = e, so by part (ii) we know that n divides mk, which implies that nld divides (mid) . k. Since (mid, nidi = 1 (why?), this implies that nld divides k (by Theorem 4.3). 0

We will use these results on the order of an element in Section 5, to help us obtain some results about what are known as cyclic groups. For now, we will just introduce cyclic groups.

We remarked that the study of abstract group theory evolved from the study of specific examples. The abstract concept was formulated in an effort

Section 4. Powers of an Element; Cyclic Groups 39

to bring together certain concrete cases. Once this was done, however, there was, of course, a new problem. How far-reaching was the abstract concept? What kinds of groups were there other than those that motivated the abstrac- tion?

A central goal of group theory is to classify all groups, i.e., to see what kinds of groups there are. One would like to start with the easiest groups. It turns out that these are the cyclic groups-those groups that are just the set of powers of some one element.

DEFINITIONS A group G is called cyclic if there is an element x E G such that G= {xnln EZ}; x is then called a generator for G.

It will be convenient to have a more compact notation for the set {xnlnEl}. We will denote it by (x). Thus G is cyclic with x as a generator iff G=(x).

In additive notation, (x)={nxlnEI}.

Examples

1. (ll' €B) is the trivial group {O} consisting of just an identity element. Clearly, then, (ll' €B) = (0).

2. If n > 2, then (In' €B) = (1 ), for the powers

\ 1, 1 €B 1,1 €B 1 ElH, ... ,.1 €B 1 €B 1 ~ ... €B 1, n terms

exhaust (Zn' €B).

3. (l, + ) is cyclic with generator 1, that is, (l, + ) = (1). In this case we have to use all the powers of the generator to get all of the group: 0,1, - 1, 1 + 1, - 1- 1, 1 + 1 + 1, - 1- 1- 1, and so on.

4. (0, +) is not cyclic. For clearly 0 is not a generator, and if q*O then we can easily exhibit rational numbers that are not in (q) = {nqlnEZ}. An example is q/2.

It should be made explicit that the powers of an element need not all be distinct. In fact, we have the following result:

TIIEOREM 4.5 Let G=(x). If o(x)=oo, then xj*xk for J*k, and conse- quently G is infinite. If o(x) = n, then x j = Xk iff} == k (mod n), and conse- quently the distinct elements of G are e, x, x 2, ••• ,xn- I •

PROOF. Suppose thatJ*k and xj=Xk. If, saY,J>k, then we obtain xj-k=e, and J - k > 0, so x has finite order. This proves the first statement.

For the second, suppose that o(x)=n. Then xj=Xk iff xj-k=e iff (by Theorem 4.4 ii) n divides j - k iff j == k (mod n). 0

40 Section 4. Powers of an Element; Cyclic Groups

DEFINITION The order of a group G, denoted by jGj, is the number of elements in G.

Theorem 4.5 has the following immediate consequence, or corollary.

COROLLARY 4.6 If G=

The equality is intended to mean that jGj is infinite iff o(x) is, and that if both sides are finite, then they are equal.

The reader may have noticed that all the examples of cyclic groups that we have looked at are abelian. This is no accident.

THEOREM 4.7 If G is a cyclic group, then G is abelian.

PROOF. Suppose G=

ab = (xm)(xn) = xm+n = xn+m = xnxm = ba,

so we are done. 0

The converse is false; there exist many noncyclic abelian groups. We have already seen· one example: (Q ,+). Another example is Klein's 4-group. This group has four elements, e, a, b, e, and the multiplication is given by ea = ae = a, eb = be = b, ee = ee = e, tl = ti = b2 = ~ = e, ab = ba = e, ae = ea = b, and be = eb = a. Instead of verifying directly that this multiplication gives us a group we can call on the known group (P(X), ~), withX= {I, 2}. If we let e = 0, a = {I}, b = {2}, and e = {I, 2}, then the multiplication specified above for Klein's 4-group is exactly the multiplication in (P(X), ~), so this multiplication does indeed yield a group. Klein's 4-group is not cyclic because none of the elements e. a. b. e has order 4.

Klein's 4-group is named for the German mathematician Felix Klein (1849- 1925). The German word for "4-group" is "Viergruppe," and the 4-group is often denoted by V.

EXERCISES

4.1 Which elements of (ItO, $) are contained in

4.2 Let G be the group of all real-valued functions on the real line under addition of functions, and let fE G be the function such that f(x) = 1 for all x E IR. Indicate what sort of configuration you would get if you drew the graphs of all the functions in

4.3 Let X={I,2,3,4,5}. If A is the element {l,4,5} in (P(X), L::.), how many elements are there in

Section 4. Powers of an Element; Cyclic Groups 41

4.4 In (130, €B), find the orders of the elements 3, 4, 6, 7, and 18.

4.5 Let G be a group and let x E G be an element of order 18. Find the orders of x 2, x 3, X4, xS, X12

4.6 List all the elements of (145' €B) that are of order 15.

4.7 Let G=

4.S The set of even integers forms a group under addition. Is this group cyclic?

4.9 Show that (0 +, . ) is not cyclic.

4.10 Let G={1,2,3,4,5,6} and define an operation 8 on G by a8b=ab, the remainder of ab (mod7). For instance, 284=8= 1, and 586=30=2.

a) Show that (G, 8) is a group.

b) Is this group cyclic?

4.11 Is GL(2,JR) cyclic?

4.12 Consider the group (1,.), where a. b = a + b - 1. Is this group cyclic?

4.13 Show that if G is a finite group, then every element of G is of finite order.

4.14 Give an example of an infinite group G such that every element of G has finite order.

4.15 a) Find (123,321), and find integers x andy such that 123x+32ly=(123,32l).

b) Find (862,347), and find integers x andy such that 862x + 347y =(862,347).

c) Find (7469,2464), and find integers x and y such that 7469x + 2464y = (7469,2464).

4.16 Prove that if G=

4.17 Prove that if G=

4.1S Prove parts (ii) and (iii) of Theorem 4.1.

4.19 Prove part (i) of Theorem 4.4.

4.20 Let G be a group and let a E G. An element bEG is called a conjugate of a if there exists an element x E G such that b = xax - I. Show that any conjugate of a has the same order as a.

4.21 Show that for any two elements x, y of any group G, o(xy) = o(yx).

4.22 Let G be an abelian group and let x, y E G. Suppose that x and yare of finite order. Show that xy is of finite order and that, in fact, o(xy) divides o(x)o(y).

4.23 Let G, x,y be as in Exercise 4.22, and assume in addition that (o(x),o(y» = 1. Prove that o(xy) = o(x)o(y).

4.24 Let G be a group and letx,yEG. Assume that x =Fe, o(y)=2, andyxy-l=x2. Find o(x).

42 Section 4. Powers of an Element; Cyclic Groups

4.25 Show that if I G I is an even integer, then there is an element x E G such that x *e and x 2 =e.

4.26 Let m, nEZ, not both 0, and let d E Z. Show that d = (m, n) iff d has the following properties:

i) d is positive; ii) dim and din; iii) every integer c that divides both m and n divides d.

These three properties are sometimes used to define g.c.d.'s.

4.27 Let P be a prime. Show that if qt, ... , q, are positive integers and P divides qtq2' .. q .. thenp divides some qi'

4.28 Prove the "uniqueness" part of the Fundamental Theorem of Arithmetic (Theorem 0.4). (Suggestion: Use the result of Exercise 4.27 and induction on n.)

4.29 Suppose m and n are positive integers and PI>.'. ,Pr are all the primes that divide m or n or both. Say m=p{tp~2 .. ·Pr;' and n=p{tJ1i2 ... pt,. Sho:w that (m,n)=pf tpf2 .. ·Prlc" where kt is the smaller of i, andj" for each t.

4.30 Let nt, ... , nk be integers, not all O. The greatest common divisor of n t ,.·., nk, denoted by (n t , ••• ,nk), is the largest integer that divides all of nt,n2, ... ,nk. Show that there exist integers at, ... ,ak such that

atn t+ a2n2+··· +aknk=(nl> ... ,nk).

[Suggestion: Use induction on k. Use the inductive hypothesis to show that

(nt,·.· ,nk) = «n!> ... ,nk-t),nk),

and apply Theorem 4.2.]

4.31 If m and n are integers, we define their least common multiple, [m,n], as follows. If m=O or n=O, we set [m,n]=O; otherwise we let [m,n] be the smallest positive integer that is divisible by both m and n.

a) Show that if m and n are both positive and m=p:tp~2 .. 'p/', n=p{tJ1iz ... pt" as in Exercise 4.29, then [m,n]=pftpi2 .. 'P:', where I, is the larger of i, and j" for each t.

b) Show that if m and n are both positive, then

mn=(m,n)[m,n].

4.32 Let G be an abelian group, and let x andy be elements of G such that o(x) = m and o(y)=n. Show that G has an element z such that o(z) is the least common multiple of m and n ..

4.33 a) Show that in the group of Exercise 2.12 we have (xy)3 = xV and (xyt=xY for all x andy, but the group is not abelian. (Compare Exercise 3.12.)

b) Prove that if G is a group and there exists a positive integer n such that for all x, y in Gwe have

(xyr = X'j' and (xy)n+l = rly"'l and (xyr2 = r2y"'2

then G is abelian.

SECTION 5

SUBGROUPS

Up to this point we have been considering groups as separate entities, unrelated to each other. Even so, you have probably observed that some groups sit inside others. For example, in (Z, +), the set 2Z of even integers is itself a group under +: Addition is a binary operation on 2Z since the sum of two even integers is even; addition is associative on 2Z since it is associative on all of Z; 2Z contains the identity element 0 of (Z, +); and if xE2Z then - x E2Z, so 2Z contains the inverse of each of its elements.

Indeed, one of the most natural questions one can ask about a group G is "What groups sit inside G?" Those that do are called subgroups of G.

DEFINI110N A subset H of a group (G,*) is called a subgroup of G if the elements of H form a group under *.

It is worth emphasizing the "under *." For example, (0+,·) is a group and (0, + ) is a group, and ° + k 0, but (0 +, .) is not a subgroup of (0, +) because the operation on (0+, .) is not the operation on (0, +).

Observe that if H is a subgroup of G, then H cannot be empty because H must contain an identity element. In fact, the identity element of H must be e, the identity element of G. For suppose e' is the identity element of H; then in particular e' * e' = e', a relationship between elements of the group G. Thus, multiplying by (e') -1 in G, we get e' = e.

It is convenient to have a more compact criterion for a subset of a group to constitute a subgroup.

TIIEOREM S.l Let H be a nonempty subset of a group G. Then H is a subgroup of G if and only if the following two conditions are satisfied:

i) for all a,bEH, abEH, and ii) for all aEH, a-I EH.

43

44 Section 5. Subgroups

Condition (i) is expressed by saying that H is closed under the operation in G, and condition (ii) is expressed by saying that H is closed under inverses.

PROOF OF THE THEOREM. If H is, in fact, a subgroup of G then it is clear that (i) is satisfied. As for (ii), if we let a _ I denote the inverse of a in H, then aa_ 1 = e (we have remarked that the identity element of H is the same as the identity element of G) in G, which implies that a_I is in fact a- I, the inverse of a in G. Thus a -I E H for any a E H, so (ii) is satisfied.

Conversely, assume that the nonempty subset H is closed under the operation. in G and that H is closed under inverses. To show that H is then a group under. it suffices to check that e E H and that associativity holds in H. Since H is nonempty by assumption, we can let x denote some element of H. Then by (ii) x-IEH, so by (i) xx-IEH. But xx-I=e, so eEH. Finally, H inherits associativity from G: if a,h,cEH then a,h,cEG, so (ah)c = a(hc) by associativity in G. 0

Examples

1. (Q + , .) is a subgroup of (iii + , .), which is, in turn, a subgroup of (R- {O},·).

2. Let G be any group and let aEG .. Then

As a specific example, if G = (1., +) and a = 2, then

3. Let's find all the subgroups of Klein's 4-group, V = { e, a, h, c} with a2 =h2 =c2 =e, ah=ha=c, ac=ca=h, hc=ch=a. The only subgroup that contains none of a, h, or c is obviously {e}. If a subgroup contains just one of a, h, or c then it is either

Klein's 4-group is thus an example of an abelian noncyclic group with the property that all of its proper subgroups are cyclic. (A subgroup H of G is proper if H:#=G.)

We sometimes make a schematic picture of the subgroups of a group by drawing what is called a subgroup lattice. The subgroup lattice for Klein's

Section 5. Subgroups 45

4-group is /.

/I~