Graduate Studies in Mathematics (GSM) Chapter 0 - Algebra (Paolo Aluffi, American Mathematical Society)

Algebra: Chapter 0 4ESPS%PYJ½ Graduate Studies in Mathematics Volume 104 American Mathematical Society Algebra: Chapter 0 Algebra: Chapter 0 Paolo Aluffi Graduate Studies in Mathematics Volume 104 American Mathematical Society Providence, Rhode Island ...

Algebra: Chapter 0 4ESPS%PYJ½ Graduate Studies in Mathematics Volume 104 American Mathematical Society Algebra: Chapter 0 Algebra: Chapter 0 Paolo Aluffi Graduate Studies in Mathematics Volume 104 American Mathematical Society Providence, Rhode Island  Editorial Board David Cox (Chair) Steven G. Krantz Rafe Mazzeo Martin Scharlemann 2010 Mathematics Subject Classification. Primary 00–01; Secondary 12–01, 13–01, 15–01, 18–01, 20–01. For additional information and updates on this book, visit www.ams.org/bookpages/gsm-104 Library of Congress Cataloging-in-Publication Data Aluffi, Paolo, 1960– Algebra: chapter 0 /Paolo Aluffi. p. cm. — (Graduate studies in mathematics ; v. 104) Includes index. ISBN 978-0-8218-4781-7 (alk. paper) 1. Algebra—Textbooks. I. Title. QA154.3.A527 2009 512—dc22 2009004043 Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy select pages for use in teaching or research. Permission is granted to quote brief passages from this publication in reviews, provided the customary acknowledgment of the source is given. Republication, systematic copying, or multiple reproduction of any material in this publication is permitted only under license from the American Mathematical Society. Permissions to reuse portions of AMS publication content are handled by Copyright Clearance Center’s RightsLink service. For more information, please visit: http://www.ams.org/rightslink. Send requests for translation rights and licensed reprints to [email protected]. Excluded from these provisions is material for which the author holds copyright. In such cases, requests for permission to reuse or reprint material should be addressed directly to the author(s). Copyright ownership is indicated on the copyright page, or on the lower right-hand corner of the first page of each article within proceedings volumes.  c 2009 by the American Mathematical Society. All rights reserved. Reprinted with corrections by the American Mathematical Society, 2016. The American Mathematical Society retains all rights except those granted to the United States Government. Printed in the United States of America.  ∞ The paper used in this book is acid-free and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at http://www.ams.org/ 10 9 8 7 6 5 4 3 2 21 20 19 18 17 16 Contents Preface to the second printing xv Introduction xvii Chapter I. Preliminaries: Set theory and categories 1 §1. Naive set theory 1 1.1. Sets 1 1.2. Inclusion of sets 3 1.3. Operations between sets 4 1.4. Disjoint unions, products 5 1.5. Equivalence relations, partitions, quotients 6 Exercises 8 §2. Functions between sets 8 2.1. Definition 8 2.2. Examples: Multisets, indexed sets 10 2.3. Composition of functions 10 2.4. Injections, surjections, bijections 11 2.5. Injections, surjections, bijections: Second viewpoint 12 2.6. Monomorphisms and epimorphisms 14 2.7. Basic examples 15 2.8. Canonical decomposition 15 2.9. Clarification 16 Exercises 17 §3. Categories 18 3.1. Definition 18 3.2. Examples 20 Exercises 26 v vi Contents §4. Morphisms 27 4.1. Isomorphisms 27 4.2. Monomorphisms and epimorphisms 29 Exercises 30 §5. Universal properties 31 5.1. Initial and final objects 31 5.2. Universal properties 33 5.3. Quotients 33 5.4. Products 35 5.5. Coproducts 36 Exercises 38 Chapter II. Groups, first encounter 41 §1. Definition of group 41 1.1. Groups and groupoids 41 1.2. Definition 42 1.3. Basic properties 43 1.4. Cancellation 45 1.5. Commutative groups 45 1.6. Order 46 Exercises 48 §2. Examples of groups 49 2.1. Symmetric groups 49 2.2. Dihedral groups 52 2.3. Cyclic groups and modular arithmetic 54 Exercises 56 §3. The category Grp 58 3.1. Group homomorphisms 58 3.2. Grp: Definition 59 3.3. Pause for reflection 60 3.4. Products et al. 61 3.5. Abelian groups 62 Exercises 63 §4. Group homomorphisms 64 4.1. Examples 64 4.2. Homomorphisms and order 66 4.3. Isomorphisms 66 4.4. Homomorphisms of abelian groups 68 Exercises 69 §5. Free groups 70 5.1. Motivation 70 5.2. Universal property 71 5.3. Concrete construction 72 5.4. Free abelian groups 75 Contents vii Exercises 78 §6. Subgroups 79 6.1. Definition 79 6.2. Examples: Kernel and image 80 6.3. Example: Subgroup generated by a subset 81 6.4. Example: Subgroups of cyclic groups 82 6.5. Monomorphisms 84 Exercises 85 §7. Quotient groups 88 7.1. Normal subgroups 88 7.2. Quotient group 89 7.3. Cosets 90 7.4. Quotient by normal subgroups 92 7.5. Example 94 7.6. kernel ⇐⇒ normal 95 Exercises 95 §8. Canonical decomposition and Lagrange’s theorem 96 8.1. Canonical decomposition 97 8.2. Presentations 99 8.3. Subgroups of quotients 100 8.4. HK/H vs. K/(H ∩ K) 101 8.5. The index and Lagrange’s theorem 102 8.6. Epimorphisms and cokernels 104 Exercises 105 §9. Group actions 108 9.1. Actions 108 9.2. Actions on sets 109 9.3. Transitive actions and the category G-Set 110 Exercises 113 §10. Group objects in categories 115 10.1. Categorical viewpoint 115 Exercises 117 Chapter III. Rings and modules 119 §1. Definition of ring 119 1.1. Definition 119 1.2. First examples and special classes of rings 121 1.3. Polynomial rings 124 1.4. Monoid rings 126 Exercises 127 §2. The category Ring 129 2.1. Ring homomorphisms 129 2.2. Universal property of polynomial rings 130 2.3. Monomorphisms and epimorphisms 132 viii Contents 2.4. Products 133 2.5. EndAb (G) 134 Exercises 136 §3. Ideals and quotient rings 138 3.1. Ideals 138 3.2. Quotients 139 3.3. Canonical decomposition and consequences 141 Exercises 143 §4. Ideals and quotients: Remarks and examples. Prime and maximal ideals 144 4.1. Basic operations 144 4.2. Quotients of polynomial rings 146 4.3. Prime and maximal ideals 150 Exercises 153 §5. Modules over a ring 156 5.1. Definition of (left-)R-module 156 5.2. The category R-Mod 158 5.3. Submodules and quotients 160 5.4. Canonical decomposition and isomorphism theorems 162 Exercises 163 §6. Products, coproducts, etc., in R-Mod 164 6.1. Products and coproducts 164 6.2. Kernels and cokernels 166 6.3. Free modules and free algebras 167 6.4. Submodule generated by a subset; Noetherian modules 169 6.5. Finitely generated vs. finite type 171 Exercises 172 §7. Complexes and homology 174 7.1. Complexes and exact sequences 174 7.2. Split exact sequences 177 7.3. Homology and the snake lemma 178 Exercises 183 Chapter IV. Groups, second encounter 187 §1. The conjugation action 187 1.1. Actions of groups on sets, reminder 187 1.2. Center, centralizer, conjugacy classes 189 1.3. The Class Formula 190 1.4. Conjugation of subsets and subgroups 191 Exercises 193 §2. The Sylow theorems 194 2.1. Cauchy’s theorem 194 2.2. Sylow I 196 2.3. Sylow II 197 Contents ix 2.4. Sylow III 199 2.5. Applications 200 Exercises 202 §3. Composition series and solvability 205 3.1. The Jordan-Hölder theorem 205 3.2. Composition factors; Schreier’s theorem 207 3.3. The commutator subgroup, derived series, and solvability 210 Exercises 213 §4. The symmetric group 214 4.1. Cycle notation 214 4.2. Type and conjugacy classes in Sn 216 4.3. Transpositions, parity, and the alternating group 219 4.4. Conjugacy in An ; simplicity of An and solvability of Sn 220 Exercises 224 §5. Products of groups 226 5.1. The direct product 226 5.2. Exact sequences of groups; extension problem 228 5.3. Internal/semidirect products 230 Exercises 233 §6. Finite abelian groups 234 6.1. Classification of finite abelian groups 234 6.2. Invariant factors and elementary divisors 237 6.3. Application: Finite subgroups of multiplicative groups of fields 239 Exercises 240 Chapter V. Irreducibility and factorization in integral domains 243 §1. Chain conditions and existence of factorizations 244 1.1. Noetherian rings revisited 244 1.2. Prime and irreducible elements 246 1.3. Factorization into irreducibles; domains with factorizations 248 Exercises 249 §2. UFDs, PIDs, Euclidean domains 251 2.1. Irreducible factors and greatest common divisor 251 2.2. Characterization of UFDs 253 2.3. PID =⇒ UFD 254 2.4. Euclidean domain =⇒ PID 255 Exercises 258 §3. Intermezzo: Zorn’s lemma 261 3.1. Set theory, reprise 261 3.2. Application: Existence of maximal ideals 264 Exercises 265 §4. Unique factorization in polynomial rings 267 4.1. Primitivity and content; Gauss’s lemma 268 x Contents 4.2. The field of fractions of an integral domain 270 4.3. R UFD =⇒ R[x] UFD 273 Exercises 276 §5. Irreducibility of polynomials 280 5.1. Roots and reducibility 281 5.2. Adding roots; algebraically closed fields 283 5.3. Irreducibility in C[x], R[x], Q[x] 285 5.4. Eisenstein’s criterion 288 Exercises 289 §6. Further remarks and examples 291 6.1. Chinese remainder theorem 291 6.2. Gaussian integers 293 6.3. Fermat’s theorem on sums of squares 297 Exercises 300 Chapter VI. Linear algebra 305 §1. Free modules revisited 305 1.1. R-Mod 305 1.2. Linear independence and bases 306 1.3. Vector spaces 308 1.4. Recovering B from F R (B) 309 Exercises 312 §2. Homomorphisms of free modules, I 314 2.1. Matrices 314 2.2. Change of basis 318 2.3. Elementary operations and Gaussian elimination 320 2.4. Gaussian elimination over Euclidean domains 323 Exercises 324 §3. Homomorphisms of free modules, II 327 3.1. Solving systems of linear equations 327 3.2. The determinant 328 3.3. Rank and nullity 333 3.4. Euler characteristic and the Grothendieck group 334 Exercises 338 §4. Presentations and resolutions 340 4.1. Torsion 340 4.2. Finitely presented modules and free resolutions 341 4.3. Reading a presentation 344 Exercises 347 §5. Classification of finitely generated modules over PIDs 349 5.1. Submodules of free modules 350 5.2. PIDs and resolutions 353 5.3. The classification theorem 354 Exercises 357 Contents xi §6. Linear transformations of a free module 359 6.1. Endomorphisms and similarity 359 6.2. The characteristic and minimal polynomials of an endomorphism 361 6.3. Eigenvalues, eigenvectors, eigenspaces 365 Exercises 368 §7. Canonical forms 371 7.1. Linear transformations of free modules; actions of polynomial rings 371 7.2. k[t]-modules and the rational canonical form 373 7.3. Jordan canonical form 377 7.4. Diagonalizability 380 Exercises 381 Chapter VII. Fields 385 §1. Field extensions, I 385 1.1. Basic definitions 385 1.2. Simple extensions 387 1.3. Finite and algebraic extensions 391 Exercises 397 §2. Algebraic closure, Nullstellensatz, and a little algebraic geometry 400 2.1. Algebraic closure 400 2.2. The Nullstellensatz 404 2.3. A little affine algebraic geometry 406 Exercises 414 §3. Geometric impossibilities 417 3.1. Constructions by straightedge and compass 417 3.2. Constructible numbers and quadratic extensions 422 3.3. Famous impossibilities 425 Exercises 427 §4. Field extensions, II 428 4.1. Splitting fields and normal extensions 429 4.2. Separable polynomials 433 4.3. Separable extensions and embeddings in algebraic closures 436 Exercises 438 §5. Field extensions, III 440 5.1. Finite fields 441 5.2. Cyclotomic polynomials and fields 445 5.3. Separability and simple extensions 449 Exercises 452 §6. A little Galois theory 454 6.1. The Galois correspondence and Galois extensions 454 6.2. The fundamental theorem of Galois theory, I 459 6.3. The fundamental theorem of Galois theory, II 461 6.4. Further remarks and examples 464 Exercises 466 xii Contents §7. Short march through applications of Galois theory 468 7.1. Fundamental theorem of algebra 468 7.2. Constructibility of regular n-gons 469 7.3. Fundamental theorem on symmetric functions 471 7.4. Solvability of polynomial equations by radicals 474 7.5. Galois groups of polynomials 478 7.6. Abelian groups as Galois groups over Q 479 Exercises 480 Chapter VIII. Linear algebra, reprise 483 §1. Preliminaries, reprise 483 1.1. Functors 483 1.2. Examples of functors 485 1.3. When are two categories ‘equivalent’ ? 487 1.4. Limits and colimits 489 1.5. Comparing functors 492 Exercises 496 §2. Tensor products and the Tor functors 500 2.1. Bilinear maps and the definition of tensor product 501 2.2. Adjunction with Hom and explicit computations 504 2.3. Exactness properties of tensor; flatness 507 2.4. The Tor functors. 509 Exercises 511 §3. Base change 515 3.1. Balanced maps 515 3.2. Bimodules; adjunction again 517 3.3. Restriction and extension of scalars 518 Exercises 520 §4. Multilinear algebra 522 4.1. Multilinear, symmetric, alternating maps 522 4.2. Symmetric and exterior powers 525 4.3. Very small detour: Graded algebra 527 4.4. Tensor algebras 529 Exercises 532 §5. Hom and duals 535 5.1. Adjunction again 536 5.2. Dual modules 537 5.3. Duals of free modules 538 5.4. Duality and exactness 539 5.5. Duals and matrices; biduality 541 5.6. Duality on vector spaces 542 Exercises 543 §6. Projective and injective modules and the Ext functors 545 6.1. Projectives and injectives 546 Contents xiii 6.2. Projective modules 547 6.3. Injective modules 548 6.4. The Ext functors 551 6.5. Ext∗Z (G, Z) 554 Exercises 555 Chapter IX. Homological algebra 559 §1. (Un)necessary categorical preliminaries 560 1.1. Undesirable features of otherwise reasonable categories 560 1.2. Additive categories 561 1.3. Abelian categories 564 1.4. Products, coproducts, and direct sums 567 1.5. Images; canonical decomposition of morphisms 570 Exercises 574 §2. Working in abelian categories 576 2.1. Exactness in abelian categories 576 2.2. The snake lemma, again 578 2.3. Working with ‘elements’ in a small abelian category 581 2.4. What is missing? 587 Exercises 589 §3. Complexes and homology, again 591 3.1. Reminder of basic definitions; general strategy 591 3.2. The category of complexes 594 3.3. The long exact cohomology sequence 597 3.4. Triangles 600 Exercises 602 §4. Cones and homotopies 605 4.1. The mapping cone of a morphism 605 4.2. Quasi-isomorphisms and derived categories 607 4.3. Homotopy 611 Exercises 614 §5. The homotopic category. Complexes of projectives and injectives 616 5.1. Homotopic maps are identified in the derived category 616 5.2. Definition of the homotopic category of complexes 618 5.3. Complexes of projective and injective objects 619 5.4. Homotopy equivalences vs. quasi-isomorphisms in K(A) 620 5.5. Proof of Theorem 5.9 624 Exercises 626 §6. Projective and injective resolutions and the derived category 628 6.1. Recovering A 629 6.2. From objects to complexes 631 6.3. Poor man’s derived category 635 Exercises 638 xiv Contents §7. Derived functors 641 7.1. Viewpoint shift 641 7.2. Universal property of the derived functor 643 7.3. Taking cohomology 645 7.4. Long exact sequence of derived functors 647 7.5. Relating F , Li F , Ri F 653 7.6. Example: A little group cohomology 655 Exercises 658 §8. Double complexes 661 8.1. Resolution by acyclic objects 662 8.2. Complexes of complexes 665 8.3. Exactness of the total complex 670 8.4. Total complexes and resolutions 672 8.5. Acyclic resolutions again and balancing Tor and Ext 675 Exercises 677 §9. Further topics 680 9.1. Derived categories 681 9.2. Triangulated categories 683 9.3. Spectral sequences 686 Exercises 695 Index 699 Preface to the second printing In the occasion of the second printing of this book I have corrected the errors of which I am aware and implemented several other minor adjustments to the ex- position. I take this opportunity to collectively thank all who had the patience to suggest corrections. Special thanks are due to Cihan Bahran and Amit Shah for par- ticularly extensive comments. Ettore Aldrovandi, Selcan Aksoy, Maarten Bergvelt, Joseph Berner, Henk Brozius, Alex Cameron, Owen Colman, Izzet Coskun, Lou van den Dries, Georges Elencwajg, Neil Epstein, David Feuer, Thomas Frey, Mark Gi- rard, William Giuliano, Guillaume Gouge, Venkata Krishna Kishore Gangavarapu, Hamza Hajji, Joseph Hoisington, Tyler Holden, Amanda Hussey, Stephan Kirchner, Jay Kopper, Jeremy Kun, Janis Lazovskis, Xia Liao, Trevor Leslie, Michael Mal- oney, Justin Mohr, Christopher Perez, Vanessa Radzimski, Aamir Rasheed, Matt Sourisseau, Avery St. Dizier, Brennan Vincent, Jon Weed, Dylan Wilson, Jonathan Wolf, Bei Ye, Mirroslav Yotov, Hui Yu, Chris Ziembko all contributed errata that have been incorporated in the current edition. October 2015 Paolo Aluffi xv Introduction This text presents an introduction to algebra suitable for upper-level undergraduate or beginning graduate courses. While there is a very extensive offering of textbooks at this level, in my experience teaching this material I have invariably felt the need for a self-contained text that would start ‘from zero’ (in the sense of not assuming that the reader has had substantial previous exposure to the subject) but that would impart from the very beginning a rather modern, categorically minded viewpoint and aim at reaching a good level of depth. Many textbooks in algebra brilliantly satisfy some, but not all, of these requirements. This book is my attempt at providing a working alternative. There is a widespread perception that categories should be avoided at first blush, that the abstract language of categories should not be introduced until a student has toiled for a few semesters through example-driven illustrations of the nature of a subject like algebra. According to this viewpoint, categories are only tangentially relevant to the main topics covered in a beginning course, so they can simply be mentioned occasionally for the general edification of the reader, who will in time learn about them (by osmosis?). Paraphrasing a reviewer of a draft of the present text, ‘Discussions of categories at this level are the reason why God created appendices.’ It will be clear from a cursory glance at the table of contents that I think otherwise. In this text, categories are introduced on page 18, after a scant reminder of the basic language of naive set theory, for the main purpose of providing a context for universal properties. These are in turn evoked constantly as basic definitions are introduced. The word ‘universal’ appears at least 100 times in the first three chapters. I believe that awareness of the categorical language, and especially some ap- preciation of universal properties, is particularly helpful in approaching a subject such as algebra ‘from the beginning’. The reader I have in mind is someone who has reached a certain level of mathematical maturity—for example, who needs no xvii xviii Introduction special assistance in grasping an induction argument—but may have only been ex- posed to algebra in a very cursory manner. My experience is that many upper-level undergraduates or beginning graduate students at Florida State University and at comparable institutions fit this description. For these students, seeing the many in- troductory concepts in algebra as instances of a few powerful ideas (encapsulated in suitable universal properties) helps to build a comforting unifying context for these notions. The amount of categorical language needed for this catalyzing function is very limited; for example, functors are not really necessary in this acclimatizing stage. Thus, in my mind the benefit of this approach is precisely that it helps a true beginner, if it is applied with due care. This is my experience in the classroom, and it is the main characteristic feature of this text. The very little categorical language introduced at the outset informs the first part of the book, introducing in general terms groups, rings, and modules. This is followed by a (rather tradi- tional) treatment of standard topics such as Sylow theorems, unique factorization, elementary linear algebra, and field theory. The last third of the book wades into somewhat deeper waters, dealing with tensor products and Hom (including a first introduction to Tor and Ext) and including a final chapter devoted to homological algebra. Some familiarity with categorical language appears indispensable to me in order to appreciate this latter material, and this is hopefully uncontroversial. Having developed a feel for this language in the earlier parts of the book, students find the transition into these more advanced topics particularly smooth. A first version of this book was essentially a careful transcript of my lectures in a run of the (three-semester) algebra sequence at FSU. The chapter on homological algebra was added at the instigation of Ed Dunne, as were a very substantial number of the exercises. The main body of the text has remained very close to the original ‘transcript’ version: I have resisted the temptation of expanding the material when revising it for publication. I believe that an effective introductory textbook (this is Chapter 0, after all... ) should be realistic: it must be possible to cover in class what is covered in the book. Otherwise, the book veers into the ‘reference’ category; I never meant to write a reference book in algebra, and it would be futile (of me) to try to ameliorate excellent available references such as Lang’s ‘Algebra’. The problem sets will give an opportunity to a teacher, or any motivated reader, to get quite a bit beyond what is covered in the main text. To guide in the choice of exercises, I have marked with a  those problems that are directly referenced from the text, and with a ¬ those problems that are referenced from other problems. A minimalist teacher may simply assign all and only the  problems; these do nothing more than anchor the understanding by practice and may be all that a student can realistically be expected to work out while juggling TA duties and two or three other courses of similar intensity as this one. The main body of the text, together with these exercises, forms a self-contained presentation of essential material. The other exercises, and especially the threads traced by those marked with ¬, will offer the opportunity to cover other topics, which some may well consider just as essen- tial: the modular group, quaternions, nilpotent groups, Artinian rings, the Jacob- son radical, localization, Lagrange’s theorem on four squares, projective space and Introduction xix Grassmannians, Nakayama’s lemma, associated primes, the spectral theorem for normal operators, etc., are some examples of topics that make their appearance in the exercises. Often a topic is presented over the course of several exercises, placed in appropriate sections of the book. For example, ‘Wedderburn’s little theorem’ is mentioned in Remark III.1.16 (that is: Remark 1.16 in Chapter III); particular cases are presented in Exercises III.2.11 and IV.2.17, and the reader eventually ob- tains a proof in Exercise VII.5.14, following preliminaries given in Exercises VII.5.12 and VII.5.13. The ¬ label and perusal of the index should facilitate the navigation of such topics. To help further in this process, I have decorated every exercise with a list (added in square brackets) of the places in the book that refer to it. For example, an instructor evaluating whether to assign Exercise V.2.25 will be imme- diately aware that this exercise is quoted in Exercise VII.5.18, proving a particular case of Dirichlet’s theorem on primes in arithmetic progressions, and that this will in turn be quoted in §VII.7.6, discussing the realization of abelian groups as Galois groups over Q. I have put a high priority on the requirement that this should be a self-contained text which essentially crosses all t’s and dots all i’s, and does not require that the reader have access to other texts while working through it. I have therefore made a conscious effort to not quote other references: I have avoided as much as possible the exquisitely tempting escape route ‘For a proof, see....’ This is the main reason why this book is as thick as it is, even if so many topics are not covered in it. Among these, commutative algebra and representation theory are perhaps the most glaring omissions. The first is represented to the extent of the standard basic definitions, which allow me to sprinkle a little algebraic geometry here and there (for example, see §VII.2), and of a few slightly more advanced topics in the exercises, but I stopped short of covering, e.g., primary decompositions. The second is missing altogether. It is my hope to complement this book with a ‘Chapter 1’ in an undetermined future, where I will make amends for these and other shortcomings. By its nature, this book should be quite suitable for self-study: readers working on their own will find here a self-contained starting point which should work well as a prelude to future, more intensive, explorations. Such readers may be helped by the following ‘9-fold way’ diagram of logical interdependence of the chapters: IV II IX I VII VIII III VI V xx Introduction This may however better reflect my original intention than the final product. For a more objective gauge, this alternative diagram captures the web of references from a chapter to earlier chapters, with the thickness of the lines representing (roughly) the number of references: With the self-studying reader especially in mind, I have put extra effort into providing an extensive index. It is not realistic to make a fanfare for each and every new term introduced in a text of this size by an official ‘definition’; the index should help a lone traveler find the way back to the source of unfamiliar terminology. Internal references are handled in a hopefully transparent way. For example, Remark III.1.16 refers to Remark 1.16 in Chapter III; if the reference is made from within Chapter III, the same item is called Remark 1.16. The list in brackets following an exercise indicates other exercises or sections in the book referring to that exercise. For example, Exercise 3.1 in Chapter I is followed by [5.1, §VIII.1.1, §IX.1.2, IX.1.10]: this alerts the reader that there are references to this problem in Exercise 5.1 in Chapter I, section 1.1 in Chapter VIII, section 1.2 in Chapter IX, and Exercise 1.10 in Chapter IX (and nowhere else). Acknowledgments. My debt to Lang’s book, to David Dummit and Richard Foote’s ‘Abstract Algebra,’ or to Artin’s ‘Algebra’ will be evident to anyone who is familiar with these sources. The chapter on homological algebra owes much to David Eisenbud’s appendix on the topic in his ‘Commutative Algebra’, to Gelfand- Manin’s ‘Methods of homological algebra’, and to Weibel’s ‘An introduction to homological algebra’. But in most cases it would simply be impossible for me to retrace the original source of an expository idea, of a proof, of an exercise, or of a specific pedagogical emphasis: these are all likely offsprings of ideas from any one of these and other influential references and often of associations triggered by following the manifold strands of the World Wide Web. This is another reason why, in a spirit of equanimity, I resolved to essentially avoid references altogether. In any case, I believe all the material I have presented here is standard, and I only retain absolute ownership of every error left in the end product. Introduction xxi I am very grateful to my students for the constant feedback that led me to write this book in this particular way and who contributed essentially to its success in my classes. Some of the students provided me with extensive lists of typos and outright mistakes, and I would especially like to thank Kevin Meek, Jay Stryker, and Yong Jae Cha for their particularly helpful comments. I had the opportunity to try out the material on homological algebra in a course given at Caltech in the fall of 2008, while on a sabbatical from FSU, and I would like to thank Caltech and the audience of the course for their hospitality and the friendly atmosphere. Thanks are also due to MSRI for hospitality during the winter of 2009, when the last fine-tuning of the text was performed. A few people spotted big and small mistakes in preliminary versions of this book, and I will mention Georges Elencwajg, Xia Liao, and Mirroslav Yotov for particularly precious contributions. I also commend Arlene O’Sean and the staff at the AMS for the excellent copyediting and production work. Special thanks go to Ettore Aldrovandi for expert advice, to Matilde Marcolli for her encouragement and indispensable help, and to Ed Dunne for suggestions that had a great impact in shaping the final version of this book. Support from the Max-Planck-Institut in Bonn, from the NSA, and from Cal- tech, at different stages of the preparation of this book, is gratefully acknowledged.  Chapter I Preliminaries: Set theory and categories Set theory is a mathematical field in itself, and its proper treatment (say via the famous ‘Zermelo-Fränkel’ axioms) goes well beyond the scope of this book and the competence of this writer. We will only deal with so-called ‘naive’ set theory, which is little more than a system of notation and terminology enabling us to express precisely mathematical definitions, statements, and their proofs. Familiarity with this language is essential in approaching a subject such as algebra, and indeed the reader is assumed to have been previously exposed to it. In this chapter we first review some of the language of naive set theory, mainly in order to establish the notation we will use in the rest of the book. We will then get a small taste of the language of categories, which plays a powerful unifying role in algebra and many other fields. Our main objective is to convey the notion of ‘universal property’, which will be a constant refrain throughout this book. 1. Naive set theory 1.1. Sets. The notion of set formalizes the intuitive idea of ‘collection of objects’. A set is determined by the elements it contains: two sets A, B are equal (written A = B) if and only if they contain precisely the same elements. ‘What is an ele- ment?’ is a forbidden question in naive set theory: the buck must stop somewhere. We can conveniently pretend that a ‘universe’ of elements is available to us, and we draw from this universe to construct the elements and sets we need, implicitly assuming that all the operations we will explore can be performed within this uni- verse. (This is the tricky point!) In any case, we specify a set by giving a precise recipe determining which elements are in it. This definition is usually put between braces and may consist of a simple, complete, list of elements: A := {1, 2, 3} 1 2 I. Preliminaries: Set theory and categories is1 the set consisting of the integers 1, 2, and 3. By convention, the order2 in which the elements are listed, or repetitions in the list, are immaterial to the definition. Thus, the same set may be written out in many ways: {1, 2, 3} = {1, 3, 2} = {1, 2, 1, 3, 3, 2, 3, 1, 1, 2, 1, 3}. This way of denoting sets may be quite cumbersome and in any case will only really work for finite sets. For infinite sets, a popular way around this problem is to write a list in which some of the elements are understood as being part of a pattern—for example, the set of even integers may be written E = {· · · , −2, 0, 2, 4, 6, · · · }, but such a definition is inherently ambiguous, so this leaves room for misinterpre- tation. Further, some sets are simply ‘too big’ to be listed, even in principle: for example (as one hopefully learns in advanced calculus) there are simply too many real numbers to be able to ‘list’ them as one may ‘list’ the integers. It is often better to adopt definitions that express the elements of a set as elements s of some larger (and already known) set S, satisfying some property P. One may then write A = {s ∈ S | s satisfies P } (∈ means element of... ) and this is in general precise and unambiguous3. We will occasionally encounter a variation on the notion of set, called ‘multiset’. A multiset is a set in which the elements are allowed to appear ‘with multiplicity’: that is, a notion for which {2, 2} would be distinct from {2}. The correct way to define a multiset is by means of functions, which we will encounter soon (see Ex- ample 2.2). A few famous sets are ∅: the empty set, containing no elements; N: the set of natural numbers (that is, nonnegative integers); Z: the set of integers; Q: the set of rational numbers; R: the set of real numbers; C: the set of complex numbers. Also, the term singleton is used to refer to any set consisting of precisely one element. Thus {1}, {2}, {3} are different sets, but they are all singletons. Here are a few useful symbols (called quantifiers): ∃ means there exists... (the existential quantifier); 1 := is a notation often used to mean that the symbol on the left-hand side is defined by whatever is on the right-hand side. Logically, this is just expressing the equality of the two sides and could just as well be written ‘=’; the extra : is a psychologically convenient decoration inherited from computer science. 2 Ordered lists are denoted with round parentheses: (1, 2, 3) is not the same as (1, 3, 2). 3 But note that there exist pathologies such as Russell’s paradox, showing that even this style of definitions can lead to nonsense. All is well so long as S is indeed known to be a set to begin with. 1. Naive set theory 3 ∀ means for all... (the universal quantifier). Also, ∃! is used to mean there exists a unique... For example, the set of even integers may be written as E = {a ∈ Z | (∃n ∈ Z) a = 2n} : in words, “all integers a such that there exists an integer n for which a = 2n”. In this case we could replace ∃ by ∃! without changing the set—but that has to do with properties of Z, not with mathematical syntax. Also, it is common to adopt the shorthand E = {2n | n ∈ Z}, in which the existential quantifier is understood. Being able to parse such strings of symbols effortlessly, and being able to write them out fluently, is extremely important. The reader of this book is assumed to have already acquired this skill. Note that the order in which things are written may make a big difference. For example, the statement (∀a ∈ Z) (∃b ∈ Z) b = 2a is true: it says that the result of doubling an arbitrary integer yields an integer; but (∃b ∈ Z) (∀a ∈ Z) b = 2a is false: it says that there exists a fixed integer b which is ‘simultaneously’ twice as much as every integer—there is no such thing. Note also that writing simply b = 2a by itself does not convey enough information, unless the context makes it completely clear what quantifiers are attached to a and b: indeed, as we have just seen, different quantifiers may make this into a true or a false statement. 1.2. Inclusion of sets. As mentioned above, two sets are equal if and only if they contain the same elements. We say that a set S is a subset of a set T if every element of S is an element of T , in symbols, S ⊆ T. By convention, S ⊂ T means the same thing: that is (unlike < vs. ≤), it does not exclude the possibility that S and T may be equal. To avoid any confusion, I will consistently use ⊆ in this book. One adopts S  T to mean that S is ‘properly’ contained in T : that is, S ⊆ T and S = T. We can think of ‘inclusion of sets’ in terms of logic: S ⊆ T means that s ∈ S =⇒ s ∈ T (the quantifier ∀s is understood); that is, ‘if s is an element of S, then s is an element of T ’; that is, all elements of S are elements of T ; that is, S ⊆ T as promised. Note that for all sets S, ∅ ⊆ S and S ⊆ S. If S ⊆ T and T ⊆ S, then S = T. 4 I. Preliminaries: Set theory and categories The symbol |S| denotes the number of elements of S, if this number is finite; otherwise, one writes |S| = ∞. If S and T are finite, then S ⊆ T =⇒ |S| ≤ |T |. The subsets of a set S form a set, called the power set, or the set of parts of S. For example, the power set of the empty set ∅ consists of one element: {∅}. The power set of S is denoted P(S); a popular alternative is 2S , and indeed |P(S)| = 2|S| if S is finite (cf. Exercise 2.11). 1.3. Operations between sets. Once we have a few sets to play with, we can obtain more by applying certain standard operations. Here are a few: ∪: the union; ∩: the intersection; : the difference; : the disjoint union; ×: the (Cartesian) product; and the important notion of ‘quotient by an equivalence relation’. Most of these operations should be familiar to the reader: for example, {1, 2, 4} ∪ {3, 4, 5} = {1, 2, 3, 4, 5} while {1, 2, 4}  {3, 4, 5} = {1, 2}. In terms of Venn diagrams of infamous ‘new math’ memory: S T S∪T S∩T ST (the solid black contour indicates the set included in the operation). Several of these operations may be written out in a transparent way in terms of logic: thus, for example, s ∈ S ∩ T ⇐⇒ (s ∈ S and s ∈ T ). Two sets S and T are disjoint if S ∩ T = ∅, that is, if no element is ‘simulta- neously’ in both of them. The complement of a subset T in a set S is the difference set S  T consisting of all elements of S which are not in T. Thus, for example, the complement of the set of even integers in Z is the set of odd integers. The operations , ×, and quotients by equivalence relations are slightly more mysterious, and it is very instructive to contemplate them carefully. We will look 1. Naive set theory 5 at them in a particularly naive way first and come back to them in a short while when we have acquired more language and can view them from a more sophisticated viewpoint. 1.4. Disjoint unions, products. One problem with these operations is that their output may not be defined as a set, but rather as a set up to isomorphisms of sets, that is, up to bijections. To make sense out of this, we have to talk about functions, and we will do that in a moment. Roughly speaking, the disjoint union of two sets S and T is a set S T obtained by first producing ‘copies’ S  and T  of the sets S and T , with the property that S  ∩ T  = ∅, and then taking the (ordinary) union of S  and T . The careful reader will feel uneasy, since this ‘recipe’ does not define one set: whatever it means to produce a ‘copy’ of a set, surely there are many ways to do so. This ambiguity will be clarified below. Nevertheless, note that we can say something about S  T even on these very shaky grounds: for example, if S consists of 3 elements and T consists of 4 elements, the reader should expect (correctly) that S  T consists of 7 elements. Products are marred by the same kind of ambiguity, but fortunately there is a convenient convention that allows us to write down ‘one’ set representing the product of two sets S and T : given S and T , we let S × T be the set whose elements are the ordered pairs 4 (s, t) of elements of S and T : S × T := {(s, t) such that s ∈ S, t ∈ T }. Thus, if S = {1, 2, 3} and T = {3, 4}, then S × T = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)}. For a more sophisticated example, R × R is the set of pairs of real numbers, which (as we learn in calculus) is a good way to represent a plane. The set Z × Z could be represented by considering the points in this plane that happen to have integer coordinates. Incidentally, it is common to denote these sets R2 , Z2 ; and similarly, the product A × A of a set by itself is often denoted A2. If S and T are finite sets, clearly |S × T | = |S| |T |. Also note that we can use products to obtain explicit ‘copies’ of sets as needed for the disjoint union: for example, we could let S  = {0} × S, T  = {1} × T , guaranteeing that S  and T  are disjoint (why?); and there is an evident way to ‘identify’ S and S  , T and T . Again, making this precise requires a little more vocabulary. The operations ∪, ∩, , × extend to operations on whole ‘families’ of sets: for example, if S1 ,... , Sn are sets, we write  n Si = S1 ∩ S2 ∩ · · · ∩ Sn i=1 4 One can define the ordered pair (s, t) as a set by setting (s, t) = {s, {s, t}}: this carries the information of the elements s, t, as well as conveying the fact that s is special (= the first element of the pair). 6 I. Preliminaries: Set theory and categories for the set whose elements are those elements which are simultaneously elements of all sets S1 ,... , Sn ; and similarly for the other operations. But note that while it is clear from the definitions that, for example, S1 ∪ S2 ∪ S3 = (S1 ∪ S2 ) ∪ S3 = S1 ∪ (S2 ∪ S3 ), it is not so clear in what sense the sets S1 × S2 × S3 , (S1 × S2 ) × S3 , S1 × (S2 × S3 ) should be ‘identified’ (where we can define the leftmost set as the set of ‘ordered triples’ of elements of S1 , S2 , S3 , by analogy with the definition for two sets). In fact, again, we can really make sense of such statements only after we acquire the language of functions. However, all such statements do turn out to be true, as the reader probably expects; by virtue of this fortunate circumstance, we can be somewhat cavalier and gloss over such subtleties. More generally, if S is a set of sets, we may consider sets     S, S, S, S, S∈S S∈S S∈S S∈S for the union, intersection, disjoint union, product of all sets in S. There are important subtleties concerning  these definitions: for example, if all S ∈ S are nonempty, does it follow that S∈S S is nonempty? The reader probably thinks so, but (if S is infinite) this is a rather thorny issue, amounting to the axiom of choice. By and large, such subtleties do not affect the material in this course; we will partly come to terms with them in due time5 , when they become more relevant to the issues at hand (cf. §V.3). 1.5. Equivalence relations, partitions, quotients. Intuitively, a relation on elements of a set S is some special affinity among selections of elements of S. For example, the relation < on the set Z is a way to compare the size of two integers: since 2 < 5, 2 ‘is related to’ 5 in this sense, while 5 is not related to 2 in the same sense. For all practical purposes, what a relation ‘means’ is completely captured by which elements are related to which elements in the set. We would really know all there is to know about < on Z if we had a complete list of all pairs (a, b) of integers such that a < b. For example, (2, 5) is such a pair, while (5, 2) is not. This leads to a completely straightforward definition of the notion of relation: a relation on a set S is simply a subset R of the product S × S. If (a, b) ∈ R, we say that a and b are ‘related by R’ and write a R b. Often we use fancier symbols for relations, such as 10100 , which is substantially larger than the estimated number of elementary particles in the observable universe. Potentially confusing point: The various conventions clash in the way the op- eration in SA should be written. From the ‘automorphism’ point of view, elements of SA are functions and should be composed as such; thus, if f, g ∈ SA = AutSet (A), then the ‘product’ of f and g should be written g ◦ f and should act as follows: (∀p ∈ A) : g ◦ f (p) = g(f (p)). But the prevailing style of notation in group theory would write this element as f g, apparently reversing the order in which the operation is performed. Everything would fall back into agreement if we adopted the convention of writ- ing functions after the elements on which they act rather than before: (p)f rather than f (p). But one cannot change century-old habits, so we have no alternative but to live with both conventions and to state carefully which one we are using at any given time. Contemplating the groups Sn for small values of n is an exercise of inestimable value. Of course S1 is a trivial group; S2 consists of the two possible permutations:   1 → 1 1 → 2 and 2 → 2 2 → 1 which we could call e (identity) and f (flip), with operation ee = f f = e, ef = f e = f. In practice we cannot give a new name to every different element of every permuta- tion group, so we have to develop a more flexible notation. There are in fact several possible choices for this; for the time being, we will indicate an element σ ∈ Sn by listing the effect of applying σ underneath the list 1,... , n, as a matrix9. Thus the elements e, f in S2 may be denoted by 1 2 1 2 e= , f=. 1 2 2 1 9 This is only a notational device—these matrices should not be confused with the matrices appearing in linear algebra. 2. Examples of groups 51 In the same notational style, S3 consists of             1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 , , , , ,. 1 2 3 2 1 3 3 2 1 1 3 2 3 1 2 2 3 1 For the multiplication, I will adopt the sensible (but not very standard) convention mentioned above and have permutations act ‘on the right’: thus, for example, 1 2 3 1 2 3 1 2 3 1 =2 =1 2 1 3 3 1 2 3 1 2 and similarly 1 2 3 1 2 3 1 2 3 1 2 3 2 = 3, 3 = 2. 2 1 3 3 1 2 2 1 3 3 1 2 That is, 1 2 3 1 2 3 1 2 3 = 2 1 3 3 1 2 1 3 2 since the permutations on both sides of the equal sign act in the same way on 1, 2, 3. The reader should now check that 1 2 3 1 2 3 1 2 3 =. 3 1 2 2 1 3 3 2 1 That is, letting 1 2 3 1 2 3 x= , y= , 2 1 3 3 1 2 then yx = xy, showing that the operation in S3 does not satisfy the commutative axiom. Thus, S3 is a noncommutative group; the reader will immediately realize that in fact Sn is noncommutative for all n ≥ 3. While the commutation relation does not hold, other interesting relations do hold in S3. For example, x2 = e, y 3 = e, showing that S3 contains elements of order 1 (the identity e), 2 (the element x), and 3 (the element y); cf. Exercise 2.2. (Incidentally, this shows that the result of Exercise 1.15 does require the commutativity hypothesis.) Also, 1 2 3 yx = = xy 2 3 2 1 as the reader may check. Using these relations, we see that every product of any assortment of x and y, xi1 y i2 xi3 y i4 · · · , may be reduced to a product xi y j with 0 ≤ i ≤ 1, 0 ≤ j ≤ 2, that is, to one of the six elements e, y, y2 , x, xy, xy 2 : for example, y 7 x13 y 5 = (y 3 )2 y(x2 )6 xy 3 y 2 = (yx)y 2 = (xy 2 )y 2 = xy 3 y = xy. 52 II. Groups, first encounter On the other hand, these six elements are all distinct—this may be checked by cancellation and order considerations10. For example, if we had xy 2 = y, then we would get x = y −1 by cancellation, and this cannot be since the relations tell us that x has order 2 and y −1 has order 3. The conclusion is that the six products displayed above must be all six elements of S3 : S3 = {e, x, y, xy, y 2 , xy 2 }. In the process we have verified that S3 may also be described as the group ‘gener- ated’ by two elements x and y, with the ‘relations’ x2 = e, y 3 = e, yx = xy 2. More generally, a subset A of a group G ‘generates’ G if every element of G may be written as a product of elements of A and of inverses of elements of A. We will deal with this notion more formally in §6.3 and with descriptions of groups in terms of generators and relations in §8.2. 2.2. Dihedral groups. A ‘symmetry’ is a transformation which preserves a struc- ture. This is of course just a loose way to talk about automorphisms, when we may be too lazy to define rigorously the relevant category. As automorphisms of objects of a category, symmetries will naturally form groups. One context in which this notion may be visualized vividly is that of ‘geometric figures’ such as polygons in the plane or polyhedra in space. The relevant category could be defined as follows: let the objects be subsets of an ordinary plane R2 and let morphisms between two subsets A, B consist of the ‘rigid motions’ of the plane (such as translations, rotations, or reflections about a line) which map A to a subset of B. A rigorous treatment of these notions would be too distracting at this point, so I will appeal to the intuition of the reader, as I do every now and then. From this perspective, the ‘symmetries’ of a subset of the plane are the rigid motions which map it onto itself; they clearly form a group. The dihedral groups may be defined as these groups of symmetries for the regular polygons. Placing the polygon so that it is centered at the origin (thereby excluding translations as possible symmetries), we see that the dihedral group for a regular n-sided polygon consists of the n rotations by 2π/n radians about the origin and the n distinct reflections about lines through the origin and a vertex or a midpoint of a side. Thus, the dihedral group for a regular n-sided polygon consists of 2n elements; I will denote11 this group by the symbol D2n. Again, contemplating these groups, at least for small values of n, is a wonder- ful exercise. There is a simple way to relate the dihedral groups to the symmetric groups of §2.1, capturing the fact that a symmetry of a regular polygon P is de- termined by the fate of the vertices of P. For example, label the vertices of an equilateral triangle clockwise by 1, 2, 3; then a counterclockwise rotation by an angle of 2π/3 sends vertex 1 to vertex 3, 3 to 2, and 2 to 1, and no other symmetry of the triangle does the same. 10 It may of course also be checked by explicit computation of the corresponding permutations, but I am trying to illustrate the fact that the relations are ‘all we need to know’. 11 Unfortunately there does not seem to be universal agreement on this notation: some ref- erences use the symbol Dn for what I call D2n here. 2. Examples of groups 53 Visually, this looks like 1 3 2 In other words, we can associate with the counterclockwise rotation of an equilateral triangle by 2π/3 the permutation 1 2 3 ∈ S3. 3 1 2 Such a labeling defines a function D6 → S3 ; further, this function is injective (since a symmetry is determined by the permuta- tion of vertices it induces). In fancier language, which we will master in due time, we say that D6 acts (faithfully) on the set {1, 2, 3}. It is clear that this can be done in several ways (for example, we could label the vertices in different ways). However, any such assignment will have the property that composition of symmetries in D2n corresponds to composition of permutations in Sn ; the reader should carefully work this out for several examples involving D6 → S3 and D8 → S4. A concise way to describe the situation is that these functions are (group) homomorphisms (cf. §4). Since both D6 and S3 have 6 elements and the function D6 → S3 given above is injective, it must also be surjective. Thus there are bijective homomorphisms between D6 and S3 ; we say that these groups are isomorphic (cf. §4.3). We will study these concepts very carefully in the next several sections. As an alternative (and more abstract) way to draw the same conclusion, denote by y the counterclockwise rotation considered above and by x the reflection about the line through the center and vertex 3 of our equilateral triangle: 1 3 2 Reflecting twice gives the identity, as does rotating three times; thus x2 = e, y 3 = e. Further, yx (rotating counterclockwise by 2π/3, then flipping about the slanted line) is the same symmetry as xy 2 (flipping first, then rotating clockwise by 2π/3). That is, yx = xy 2. 54 II. Groups, first encounter In other words, the group D6 is also generated by two elements x, y, subject to the relations x2 = e, y 3 = e, yx = xy 2 —precisely as we found for S3. Since D6 and S3 admit matching descriptions in terms of generators and relations (that is, matching presentations; cf. §8.2), ‘of course’ they are isomorphic. 2.3. Cyclic groups and modular arithmetic. Let n be a positive integer. Con- sider the equivalence relation on Z defined by12 (∀a, b ∈ Z) : a ≡ b mod n ⇐⇒ n | (b − a). This is called congruence modulo n. We have encountered this relation already, for n = 2, in Example I.1.3. It is very easy to check that it is an equivalence relation, for all n; the set of equivalence classes is often denoted by Zn , Z/(n), Z/nZ, or Fn. We will opt for Z/nZ, which is not preempted by other notions13. I will denote by [a]n the equivalence class of the integer a modulo n, or simply [a] if no ambiguity arises. The reader should check carefully that Z/nZ consists of exactly n elements, namely n , n , · · · , [n − 1]n. We can use the group structure on Z to induce an (abelian) group structure on Z/nZ. In order to do this, we define an operation + on Z/nZ, by setting ∀a, b ∈ Z [a] + [b] := [a + b]. Of course we have to check that this prescription is well-defined; luckily, this is very easy: the following small lemma does the job, as it shows that the result of the operation does not depend on the representatives chosen for the classes. Lemma 2.2. If a ≡ a mod n and b ≡ b mod n, then (a + b) ≡ (a + b ) mod n. Proof. By hypothesis n | (a − a) and n | (b − b); therefore ∃k, ∈ Z such that (a − a) = kn, (b − b) = n. Then (a + b ) − (a + b) = (a − a) + (b − b) = kn + n = (k + )n, proving that n divides (a + b ) − (a + b), as needed.  Therefore, we have a binary operation + on Z/nZ. It is immediately checked that the resulting structure is a group. Associativity is inherited from Z: ([a] + [b]) + [c] = [a + b] + [c] = [(a + b) + c] = [a + (b + c)] = [a] + [b + c] = [a] + ([b] + [c]); and so are the identity and ‘inverse’ −[a] = [−a]. It is also immediately checked that the resulting groups Z/nZ are commutative, as the abelian-style notation suggests: [a] + [b] = [a + b] = [b + a] = [b] + [a]. 12 Thenotation n | m stands for n is a divisor of m; that is, m = nk for some integer k. 13 When n = p is prime, Zp is the official notation for ‘p-adic integers’, which are a completely different concept; see Exercise VIII.1.19. 2. Examples of groups 55 I trust that this material is not new to the reader, who should in any case check all these assertions carefully. The abelian groups thus obtained, together with Z, are called cyclic groups; a popular alternative notation for the group (Z/nZ, +) is Cn. This is adopted especially when one wants to use the ‘multiplicative’ rather than ‘additive’ notation; thus we can say that Cn is generated by one element x, with the relation xn = e. Cyclic groups are tremendously important, and we will come back to them in later sections. For the time being we record the fact that the element n ∈ Z/nZ generates the group, in the sense that every other element may be obtained as a multiple of this element. For example, if m ≥ 0 is an integer, then  + · · · + 1]n = [m]n = [1  n + · · · + n = m · n. m times m times Equivalently, we may phrase this fact by observing that the order of n in Z/nZ is n: this implies that the n multiples 0 · n , 1 · n ,... , (n − 1) · n must all be distinct, and hence they must fill up Z/nZ. Proposition 2.3. The order of [m]n in Z/nZ is 1 if n | m, and more generally n |[m]n | =. gcd(m, n) Proof. If n | m, then [m]n = n. If n does not divide m, observe again that [m]n = m n and apply Proposition 1.13.  Remark 2.4. As a consequence, the order of every element of Z/nZ divides n = |Z/nZ|, the order of the group. We will see later (Example 8.15) that this is a general feature of the order of elements in any finite group.  Corollary 2.5. The class [m]n generates Z/nZ if and only if gcd(m, n) = 1. This simple result is quite important. For example, if n = p is a prime integer, it shows that every nonzero class in the group Z/pZ generates it. In any case, it allows us to construct more examples of interesting groups. The reader should check (or recall; cf. Exercise 2.14) that there also is a well-defined multiplication on Z/nZ, given by [a]n · [b]n := [ab]n. This operation does not define a group structure on Z/nZ: indeed, the class n does not have a multiplicative inverse. On the other hand, for any positive n denote by (Z/nZ)∗ the subset of Z/nZ consisting of classes [m]n such that gcd(m, n) = 1: (Z/nZ)∗ := {[m]n ∈ Z/nZ | gcd(m, n) = 1}. This subset is clearly well-defined: if m ≡ m mod n, then gcd(m, n) = 1 ⇐⇒ gcd(m , n) = 1 (Exercise 2.17), so the defining property of classes in (Z/nZ)∗ is independent of representatives. Proposition 2.6. Multiplication makes (Z/nZ)∗ into a group. 56 II. Groups, first encounter Proof. Simple properties of gcd’s show that if gcd(m1 , n) = gcd(m2 , n) = 1, then gcd(m1 m2 , n) = 1. (For example, if a prime integer divided both n and m1 m2 , then it would necessarily divide m1 or m2 , and one of the two gcd’s would not be 1.) Therefore, the product of two elements in (Z/nZ)∗ is an element of (Z/nZ)∗ , and · does define a binary operation (Z/nZ)∗ × (Z/nZ)∗ → (Z/nZ)∗. It is clear that this operation is associative (because multiplication is associative in Z); n is an element of (Z/nZ)∗ and is an identity with respect to multiplication; so all we have to check is that elements of (Z/nZ)∗ have multiplicative inverses in (Z/nZ)∗. This follows from Corollary 2.5. If gcd(m, n) = 1, then [m]n generates the additive group Z/nZ, and hence some multiple of [m]n must equal n : (∃a ∈ Z) : a · [m]n = n ; this implies [a]n [m]n = n. Therefore [m]n does have a multiplicative inverse in Z/nZ, namely [a]n. The reader will verify that gcd(a, n) = 1, completing the proof.  For instance, 15 has a multiplicative inverse in (Z/15Z)∗. Tracing the argu- ment given in the proof, 2 · 8 + (−1) · 15 = 1, and hence 15 · 15 = 15 : the multiplicative inverse of 15 is 15. For n = p a positive prime integer, the group ((Z/pZ)∗ , ·) has order (p − 1). We will have more to say about these groups in later sections (cf. Example 4.6). Exercises 2.1. ¬ One can associate an n × n matrix Mσ with a permutation σ ∈ Sn by letting the entry at (i, (i)σ) be 1 and letting all other entries be 0. For example, the matrix corresponding to the permutation 1 2 3 σ= ∈ S3 3 1 2 would be ⎛ ⎞ 0 0 1 Mσ = ⎝1 0 0⎠. 0 1 0 Prove that, with this notation, Mστ = Mσ Mτ for all σ, τ ∈ Sn , where the product on the right is the ordinary product of matrices. [IV.4.13] Exercises 57 2.2.  Prove that if d ≤ n, then Sn contains elements of order d. [§2.1] 2.3. For every positive integer n find an element of order n in SN. 2.4. Define a homomorphism D8 → S4 by labeling vertices of a square, as we did for a triangle in §2.2. List the 8 permutations in the image of this homomorphism. 2.5.  Describe generators and relations for all dihedral groups D2n. (Hint: Let x be the reflection about a line through the center of a regular n-gon and a vertex, and let y be the counterclockwise rotation by 2π/n. The group D2n will be generated by x and y, subject to three relations14. To see that these relations really determine D2n , use them to show that any product xi1 y i2 xi3 y i4 · · · equals xi y j for some i, j with 0 ≤ i ≤ 1, 0 ≤ j < n.) [8.4, §IV.2.5] 2.6.  For every positive integer n construct a group containing elements g, h such that |g| = 2, |h| = 2, and |gh| = n. (Hint: For n > 1, D2n will do.) [§1.6] 2.7. ¬ Find all elements of D2n that commute with every other element. (The parity of n plays a role.) [IV.1.2] 2.8. Find the orders of the groups of symmetries of the five ‘platonic solids’. 2.9. Verify carefully that ‘congruence mod n’ is an equivalence relation. 2.10. Prove that Z/nZ consists of precisely n elements. 2.11.  Prove that the square of every odd integer is congruent to 1 modulo 8. [§VII.5.1] 2.12. Prove that there are no nonzero integers a, b, c such that a2 +b2 = 3c2. (Hint: By studying the equation [a]24 + [b]24 = 3[c]24 in Z/4Z, show that a, b, c would all have to be even. Letting a = 2k, b = 2 , c = 2m, you would have k2 + 2 = 3m2. What’s wrong with that?) 2.13.  Prove that if gcd(m, n) = 1, then there exist integers a and b such that am + bn = 1. (Use Corollary 2.5.) Conversely, prove that if am+bn = 1 for some integers a and b, then gcd(m, n) = 1. [2.15, §V.2.1, V.2.4] 2.14.  State and prove an analog of Lemma 2.2, showing that the multiplication on Z/nZ is a well-defined operation. [§2.3, §III.1.2] 2.15. ¬ Let n > 0 be an odd integer. Prove that if gcd(m, n) = 1, then gcd(2m + n, 2n) = 1. (Use Exercise 2.13.) Prove that if gcd(r, 2n) = 1, then gcd( r+n 2 , n) = 1. (Ditto.) Conclude that the function [m]n → [2m + n]2n is a bijection between (Z/nZ)∗ and (Z/2nZ)∗. 14 Two relations are evident. To ‘see’ the third one, hold your right hand in front of and away from you, pointing your fingers at the vertices of an imaginary regular pentagon. Flip the pentagon by turning the hand toward you; rotate it counterclockwise w.r.t. the line of sight by 72◦ ; flip it again by pointing it away from you; and rotate it counterclockwise a second time. This returns the hand to the initial position. What does this tell you? 58 II. Groups, first encounter The number φ(n) of elements of (Z/nZ)∗ is Euler’s φ-function. The reader has just proved that if n is odd, then φ(2n) = φ(n). Much more general formulas will be given later on (cf. Exercise V.6.8). [VII.5.11] 2.16. Find the last digit of 123823718238456. (Work in Z/10Z.) 2.17.  Show that if m ≡ m mod n, then gcd(m, n) = 1 if and only if gcd(m , n) = 1. [§2.3] 2.18. For d ≤ n, define an injective function Z/dZ → Sn preserving the operation, that is, such that the sum of equivalence classes in Z/dZ corresponds to the product of the corresponding permutations. 2.19.  Both (Z/5Z)∗ and (Z/12Z)∗ consist of 4 elements. Write their multiplica- tion tables, and prove that no re-ordering of the elements will make them match. (Cf. Exercise 1.6.) [§4.3] 3. The category Grp Groups will be the objects of the category Grp. In this section we define the morphisms in the category and deal with simple properties of these morphisms. 3.1. Group homomorphisms. As we know, a group consists of two distinct types of information: a set G and an operation15 mG : G × G → G satisfying certain properties. For two groups (G, mG ) and (H, mH ), a group homo- morphism ϕ : (G, mG ) → (H, mH ) is first of all a function (usually given the same name, ϕ in this case) between the underlying sets; but this function must ‘know about’ the operations mG on G, mH on H. What is the most natural requirement of this sort? Note that the set-function ϕ : G → H determines a function (ϕ × ϕ) : G × G → H × H : we could invoke the universal property of products to obtain this function (cf. Ex- ercise 3.1), but since we are dealing with sets, there is no need for fancy language here—just define the function by (∀(a, b) ∈ G × G) : (ϕ × ϕ)(a, b) = (ϕ(a), ϕ(b)). There is a diagram combining all these maps: G×G ϕ×ϕ / H ×H mG mH   G /H ϕ 15 In §1, m G was denoted ; here we need to keep track of operations on different groups, so for a moment I will use a symbol recording the group (and evoking ‘multiplication’). 3. The category Grp 59 What requirement could be more natural than asking that this diagram commute? Definition 3.1. The set-function ϕ : G → H defines a group homomorphism if the diagram displayed above commutes.  This is a seemingly complicated way of saying something simple: since ϕ and mG , mH are functions of sets, commutativity means the following. For all a, b ∈ G, the two ways to travel through the diagram give (a, b) (a, b)  / (ϕ(a), ϕ(b)) _ _   a·b  / ϕ(a · b) ϕ(a) · ϕ(b) where I now write · for both operations: in G on the left, in H on the right. Commutativity of the diagram means that we must get the same result in both cases; therefore, Definition 3.1 can be rephrased as the set-function ϕ : G → H is a group homomorphism if ∀a, b ∈ G ϕ(a · b) = ϕ(a) · ϕ(b). In other words, ϕ is a homomorphism if it ‘preserves the structure’. This may sound more familiar to our reader. As usual, the reason to bring in diagrams (as in Definition 3.1) is that this would make it easy to transfer part of the discussion to other categories. If the context is clear, one may simply write ‘homomorphism’, omitting the qualifier ‘group’. 3.2. Grp: Definition. For G, H groups16 we define HomGrp (G, H) to be the set of group homomorphisms G → H. If G, H, K are groups and ϕ : G → H, ψ : H → K are two group homo- morphisms, it is easy to check that the composition ψ ◦ ϕ : G → K is a group homomorphism: from the diagram point of view, this amounts to observing that the ‘outer rectangle’ in (ψ◦ϕ)×(ψ◦ϕ) + G×G / H ×H / K ×K ϕ×ϕ ψ×ψ mG mH mK    G ϕ /H ψ /5 K ψ◦ϕ 16 I am yielding to the usual abuse of language that lets us omit explicit mention of the operation. 60 II. Groups, first encounter must commute if the two ‘inner rectangles’ commute. For arbitrary a, b ∈ G, this means, (1) (2) (ψ ◦ ϕ)(a · b) = ψ(ϕ(a · b)) = ψ(ϕ(a) · ϕ(b)) = ψ(ϕ(a)) · ψ(ϕ(b)) = (ψ ◦ ϕ)(a) · (ψ ◦ ϕ)(b) where (1) holds because ϕ is a homomorphism and (2) holds because ψ is a homo- morphism. Further, it is clear that composition is associative (because it is for set-functions) and that the identity function idG : G → G is a group homomorphism. Therefore, Grp is indeed a category. 3.3. Pause for reflection. The careful reader might raise an objection: the group axioms prescribe the existence of an identity element eG and of an ‘inverse’, that is, a specific function ιG : G → G, ιG (g) := g −1. Shouldn’t the definition of morphism in Grp keep track of this type of data? The definition we have given only keeps track of the multiplication map mG. The reason why we can get away with this is that preserving m automatically preserves e and ι: Proposition 3.2. Let ϕ : G → H be a group homomorphism. Then ϕ(eG ) = eH ; ∀g ∈ G, ϕ(g −1 ) = ϕ(g)−1. In terms of diagrams, the second assertion amounts to saying that G ϕ /H ιG ιH   G /H ϕ must commute. Proof. The first item follows from the definition of homomorphism and cancella- tion: since eH = eH · eH , eH · ϕ(eG ) = ϕ(eG ) = ϕ(eG · eG ) = ϕ(eG ) · ϕ(eG ), which implies eH = ϕ(eG ) by ‘cancelling ϕ(eG )’. The proof of the second assertion is similar: ∀g ∈ G, ϕ(g −1 ) · ϕ(g) = ϕ(g −1 · g) = ϕ(eG ) = eH = ϕ(g)−1 · ϕ(g), implying ϕ(g −1 ) = ϕ(g)−1 by cancellation.  3. The category Grp 61 3.4. Products et al. The categories Grp and Set look rather alike at first: given a group, we can ‘forget’ the information of multiplication and we are left with a set; given a group homomorphism, we can forget that it preserves the multiplication and we are left with a set-function. A concise way to express this fact is that there is a ‘functor’ Grp ; Set (called in fact a ‘forgetful’ functor); we will deal with functors more extensively much later on, starting in Chapter VIII. However, there are important differences between these two categories. For example, recall that Set has a unique initial object (that is, ∅) and this is not the same as the final objects (that is, the singletons). Also recall that a trivial group is a group consisting of a single element (Example 1.3). Proposition 3.3. Trivial groups are both initial and final in Grp. This makes trivial groups ‘zero-objects’ of the category Grp. Proof. It should be clear that trivial groups are final: there is only one function from a set to a singleton, that is, the constant function; this is vacuously a group homomorphism. To see that trivial groups are initial, let T = {e} be a trivial group; for any group G, define ϕ : T → G by T (e) = eG. This is clearly a group homomorphism, and it is the only possible one since every group homomorphism must send the identity to the identity (Proposition 3.2).  Here is a similarity: Grp has products; in fact, the product of two groups G, H is supported on the product G × H of the underlying sets. To see this, we need to define a multiplication on G × H; the catchword here is componentwise: define the operation in G × H by performing the operation on each component separately. Explicitly, define ∀g1 , g2 ∈ G, ∀h1 , h2 ∈ H (g1 , h1 ) · (g2 , h2 ) := (g1 g2 , h1 h2 ). This operation defines a group structure on G × H: the operation is associative, the identity is (eG , eH ), and the inverse of (g, h) is (g −1 , h−1 ). All needed verifications are left to the reader. The group G × H is called the direct product of the groups G and H. Also note that the natural projections G × HJ uu JJJπH πG zuuu J$ G H (defined as set-functions as in §I.2.4) are group homomorphisms: again, this follows immediately from the definitions. Proposition 3.4. With operation defined componentwise, G × H is a product in Grp. Proof. Recall (§I.5.4) that this means that G × H satisfies the following universal property: for any group A and any choice of group homomorphisms ϕG : A → G, 62 II. Groups, first encounter ϕH : A → H, there exists a unique group homomorphism ϕG × ϕH making the diagram.G oo7 ϕG πG oooo oo o ooo ϕG ×ϕH A / G×H OOO OOO OO πH OOO OO' ϕH /H commute. Now, a unique set-function ϕG × ϕH exists making the diagram commute, because the set G × H is a product of G and H in Set. So we only need to check that ϕG × ϕH is a group homomorphism, and this is immediate (if cumbersome): ∀a, b ∈ A, ϕG × ϕH (ab) = (ϕG (ab), ϕH (ab)) = (ϕG (a)ϕG (b), ϕH (a)ϕH (b)) = (ϕG (a), ϕH (a))(ϕG (b), ϕH (b)) = (ϕG × ϕH (a))(ϕG × ϕH (b)).  What about coproducts? They do exist in Grp, but their construction requires handling presentations more proficiently than we do right now, and general coprod- ucts of groups will not be used in the rest of the book; so the reader will have to deal with them on his or her own. For an important example, see Exercise 3.8; more will show up in Exercises 5.6 and 5.7, since free groups are themselves par- ticular cases of coproducts. The reader will finally produce the coproduct of any two groups explicitly in Exercise 8.7. For now, just realize that the disjoint union, which works as a coproduct in Set (Proposition I.5.6), is not an option in Grp: there is no reasonable group structure on the disjoint union. The coproduct of G and H in Grp is denoted G ∗ H and is called the free product of G and H. 3.5. Abelian groups. The category Ab whose objects are abelian groups, and whose morphisms are group homomorphisms, will in a sense be more important for us than the category Grp. In many ways, as we will see, Ab is a ‘nicer’ category17 than Grp. Again the trivial groups are both initial and final (that is, ‘zero’) objects; products exist and coincide with products in Grp. But here is a difference: unlike in Grp, coproducts in Ab coincide with products. That is, if G and H are abelian groups, then the product G×H (with the two natural homomorphisms G → G×H, H → G × H) satisfies the universal property for coproducts in Ab (cf. Exercise 3.3). When working as a coproduct, the product G × H of two abelian groups is often called their direct sum and is denoted G ⊕ H. There is a pretty subtlety here, which may highlight the power of the language: even if G and H are commutative, the product G × H does not (necessarily) satisfy 17 As we will see in due time (Proposition III.5.3), Ab is one instance of a general class of categories of ‘modules over a commutative ring R’ (for R = Z). Unlike Grp, these categories are abelian, which makes them very well-behaved. We will learn two or three things about abelian categories in Chapter IX. Exercises 63 the universal property for coproducts in Grp, even if it does in Ab. For an explicit example, see Exercise 3.6. Exercises 3.1.  Let ϕ : G → H be a morphism in a category C with products. Explain why there is a unique morphism (ϕ × ϕ) : G × G → H × H compatible in the evident way with the natural projections. (This morphism is defined explicitly for C = Set in §3.1.) [§3.1, 3.2] 3.2. Let ϕ : G → H, ψ : H → K be morphisms in a category with products, and consider morphisms between the products G × G, H × H, K × K as in Exercise 3.1. Prove that (ψϕ) × (ψϕ) = (ψ × ψ)(ϕ × ϕ). (This is part of the commutativity of the diagram displayed in §3.2.) 3.3.  Show that if G, H are abelian groups, then G × H satisfies the universal property for coproducts in Ab (cf. §I.5.5). [§3.5, 3.6, §III.6.1] 3.4. Let G, H be groups, and assume that G = ∼ H × G. Can you conclude that H is trivial? (Hint: No. Can you construct a counterexample?) 3.5. Prove that Q