Abstract algebra a first course dan saracino pdf

ABSTRACT ALGEBRA

Second Edition

ABSTRACT ALGEBRA

A First Course

Second Edition

Dan Saracino Colgate University

WAVEIAND

PRESS, INC. Long Grove, illinois

For information about this book, contact: Waveland Press, Inc. 4180 IL Route 83, Suite 101 Long Grove, IL 60047-9580 (847) 634-0081 info@waveland.com www.waveland.com

Copyright © 2008, 1980 by Dan Saracino

I O-digit ISBN 1-57766-536-8 13-digit ISBN 978-1-57766-536-6

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without permission in writing from the publisher.

Printed in the United States of America

7 6 543 2

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 <m, then P(m) is true.

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 <m, and our task is to use this to show that P( m) holds.

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 <m, then P(m) holds. Clearly P(2) is true, since 2 is itself a prime. Now take m > 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 <m, and by the inductive hypothesis we can write

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 <k <m, then P(m) is true. Then P(n) is true for all n;;.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.