Introduction to Algebra This page intentionally left blank Introduction to Algebra Second Edition Peter J. Cameron Queen Mary, University of London 1 3 GreatClarendonStreet,Oxfordox26dp OxfordUniversityPressisadepartmentoftheUniversityofOxford. ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship, andeducationbypublishingworldwidein Oxford NewYork Auckland CapeTown DaresSalaam HongKong Karachi KualaLumpur Madrid Melbourne MexicoCity Nairobi NewDelhi Shanghai Taipei Toronto Withofficesin Argentina Austria Brazil Chile CzechRepublic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore SouthKorea Switzerland Thailand Turkey Ukraine Vietnam OxfordisaregisteredtrademarkofOxfordUniversityPress intheUKandincertainothercountries PublishedintheUnitedStates byOxfordUniversityPressInc.,NewYork (cid:1)c PeterJ.Cameron,2008 Themoralrightsoftheauthorhavebeenasserted DatabaserightOxfordUniversityPress(maker) Firstpublished2008 Allrightsreserved.Nopartofthispublicationmaybereproduced, storedinaretrievalsystem,ortransmitted,inanyformorbyanymeans, withoutthepriorpermissioninwritingofOxfordUniversityPress, orasexpresslypermittedbylaw,orundertermsagreedwiththeappropriate reprographicsrightsorganization.Enquiriesconcerningreproduction outsidethescopeoftheaboveshouldbesenttotheRightsDepartment, OxfordUniversityPress,attheaddressabove Youmustnotcirculatethisbookinanyotherbindingorcover andyoumustimposethesameconditiononanyacquirer BritishLibraryCataloguinginPublicationData Dataavailable LibraryofCongressCataloginginPublicationData Dataavailable TypesetbyNewgenImagingSystems(P)Ltd.,Chennai,India PrintedinGreatBritain onacid-freepaperby BiddlesLtd.,King’sLynn,Norfolk ISBN 978–0–19–856913–8 978–0–19–852793–0(Pbk.) 1 3 5 7 9 10 8 6 4 2 Preface This new edition of my algebra textbook has a number of changes. The most significant is that the book now tries to live up to its title better than it did in the previous edition: the introductory chapter has more than doubledinlength,includingbasicmaterialonproofs,numbers,algebraicmanip- ulations, sets, functions, relations, matrices, and permutations. I hope that it is now accessible to a first-year mathematics undergraduate, and suitable for use in a first-year mathematics course. Indeed, much of this material comes from a course (also with the title ‘Introduction to Algebra’) which I gave at Queen Mary, University of London, in spring 2007. I have also revised and corrected the rest of the book, while keeping the structure intact. In particular, the pace of the first chapter is quite gentle; in Chapters 2 and 3 it picks up a bit, and in the later chapters it is a bit faster again. Once you are used to the way I write mathematics, you should be able to take this in your stride. Since the book is intended to be used in a variety of courses,thereisacertainamountofrepetition.Forexample,conceptsorresults introduced in exercises may be dealt with later in the main text. New material ontheAxiomofChoice,p-groups,andlocalringshasbeenadded,andthereare many new exercises. Iamgratefultomanypeoplewhohavehelpedme.Firstandforemost,Robin Chapman,forspottingmanymisprintsandmakingmanysuggestions;andCsaba Szabo´, who encouraged his students (named below) to proofread the book very thoroughly! Also, Gary McGuire spotted a gap in the proof of the Fundamental TheoremofGaloisTheory,andR.A.BaileysuggestedadifferentproofofSylow’s Theorem. The people who notified me of errors in the book, or who suggested improvements (as well as the above) are Laura Alexander, Richard Anderson, M. Q. Baig, Steve DiMauro, Karl Fedje, Emily Ford, Roderick Foreman, Will Funk, Rippon Gupta, Matt Harvey, Jessica Hubbs, Young-Han Kim, Bill Mar- tin, William H. Millerd, Ioannis Pantelidakis, Brandon Peden, Nayim Rashid, Elizabeth Rothwell, Ben Rubin, and Amjad Tuffaha; my thanks to all of you, and to anyone else whose name I have inadvertently omitted! P.J.C. London April 2007 Preface to the first edition The axiomatic method is characteristic of modern mathematics. By making our assumptionsexplicit,wereducetheriskofmakinganerrorinourreasoningbased vi Preface onfalseanalogy;andourresultshaveaclearlydefinedareaofapplicabilitywhich is as wide as possible (any situation in which the axioms hold). However, switching quickly from the concrete to the abstract makes a heavy demandonstudents.Theaxiomaticstyleofmathematicsisusuallymetfirstina coursewithatitlesuchas‘AbstractAlgebra’,‘AlgebraicStructures’,or‘Groups, Rings and Fields’. Students who are used to factorising a particular integer or finding the stationary points of a particular curve find it hard to verify that a set whose elements are subsets of another set satisfies the axioms for a group, and even harder to get a feel for what such a group really looks like. For this reason, among others, I have chosen to treat rings before groups, although they are logically more complicated. Everyone is familiar with the set of integers, and can see that it satisfies the axioms for a ring. In the early stages, when one depends on precedent, the integers form a fairly reliable guide. Also, the abstract factorisation theorems of ring theory lead to proofs of impor- tant and subtle properties of the integers, such as the Fundamental Theorem of Arithmetic. Finally, the path to non-trivial applications is shorter from ring theory than from group theory. I have been teaching algebra for the whole of my professional career, and thisbookreflectsthatexperience.Mostimmediately,itgrewoutoftheAbstract AlgebracourseatQueenMaryandWestfieldCollege.Chapters2and3arebased fairly directly on the course content, and provide an introduction to rings (and fields) and to groups. The first chapter contains essential background material that every student of mathematics should know, and which can certainly stand repetition. (A great deal of algebra depends on the concept of an equivalence relation.) Chapter 4, on vector spaces, does not try to be a complete account, since most students would have met vector spaces before they reach this point. The purpose is twofold: to give an axiomatic approach; and to provide material in a form which generalises to modules over Euclidean rings, from where two very importantapplications(finitelygeneratedabeliangroupsandcanonicalformsof matrices) come. Chapter 7 carries further the material of Chapters 2 and 3, and also intro- duces some other types of algebra, chosen for their unifying features: universal algebra,lattices,andcategories.Thisfollowsachapterinwhichthenumbersys- tems are defined (so that our earlier trust that the integers form a ring can be firmly founded), the distinction between algebraic and transcendental numbers is established, and certain ruler-and-compass construction problems are shown to be impossible. The final chapter treats two important applications, drawing on much of what has gone before: coding theory and Galois Theory. Asmentionedearlier,Chapters2and3canformthebasisofafirstcourseon algebra,followedbyacoursebasedonChapters5and7.Alternatively,Chapter3 andSections7.1–7.8couldformagrouptheorycourse,andChapters2and5and Sections7.9–7.14aringtheorycourse.Sections2.14–2.16,6.6–6.8,7.15–7.18,and 8.6–8.11 make up a Galois Theory course. Sections 6.1–6.5, and 6.9–6.10 could Preface vii supplement a course on set theory, and Sections 2.14–2.16, 7.15–7.18, and 8.1– 8.5 could be used in conjunction with some material on information theory for a coding theory course. Some parts of the book (Sections 7.8, 7.13, and probably the last part of Chapter 7) are really too sketchy to be used for teaching a course; they are designed to tempt students into further exploration. At the end, there is a list of books for further reading, and solutions to selected exercises from the first three chapters. Asterisks denote harder exercises. There is a World Wide Web site associated with this book. It contains solu- tionstotheremainingexercises,furthertopics,problems,andlinkstoothersites of interest to algebraists. The address is http://www.maths.qmul.ac.uk/˜pjc/algebra/ Thanks are due to many generations of students, whose questions and per- plexities have helped me clarify my ideas and so resulted in a better book than I might otherwise have written. P.J.C. London December 1997 This page intentionally left blank Contents 1. Introduction 1 What is mathematics? 1 Numbers 10 Elementary algebra 23 Sets 32 Modular Arithmetic 48 Matrices 52 Appendix: Logic 58 2. Rings 63 Rings and subrings 63 Homomorphisms and ideals 74 Factorisation 87 Fields 99 Appendix: Miscellany 103 3. Groups 110 Groups and subgroups 110 Subgroups and cosets 119 Homomorphisms and normal subgroups 124 Some special groups 132 Appendix: How many groups? 147 4. Vector spaces 150 Vector spaces and subspaces 150 Linear transformations and matrices 161 5. Modules 182 Introduction 182 Modules over a Euclidean domain 190 Applications 196 6. The number systems 209 To the complex numbers 210 Algebraic and transcendental numbers 220 More about sets 230 7. Further topics 237 Further group theory 237 Further ring theory 256