Undergraduate Texts in Mathematics Béla Bajnok An Invitation to Abstract Mathematics Undergraduate Texts in Mathematics Undergraduate Texts in Mathematics SeriesEditors: SheldonAxler SanFranciscoStateUniversity,SanFrancisco,CA,USA KennethRibet UniversityofCalifornia,Berkeley,CA,USA AdvisoryBoard: ColinAdams,WilliamsCollege,Williamstown,MA,USA AlejandroAdem,UniversityofBritishColumbia,Vancouver,BC,Canada RuthCharney,BrandeisUniversity,Waltham,MA,USA IreneM.Gamba,TheUniversityofTexasatAustin,Austin,TX,USA RogerE.Howe,YaleUniversity,NewHaven,CT,USA DavidJerison,MassachusettsInstituteofTechnology,Cambridge,MA,USA JeffreyC.Lagarias,UniversityofMichigan,AnnArbor,MI,USA JillPipher,BrownUniversity,Providence,RI,USA FadilSantosa,UniversityofMinnesota,Minneapolis,MN,USA AmieWilkinson,UniversityofChicago,Chicago,IL,USA Undergraduate Texts in Mathematics are generally aimed at third- and fourth- year undergraduate mathematics students at North American universities. These texts strive to provide students and teachers with new perspectives and novel approaches.Thebooksincludemotivationthatguidesthereadertoanappreciation ofinterrelationsamongdifferentaspectsofthesubject.Theyfeatureexamplesthat illustratekeyconceptsaswellasexercisesthatstrengthenunderstanding. Forfurthervolumes: http://www.springer.com/series/666 Be´la Bajnok An Invitation to Abstract Mathematics 123 Be´laBajnok DepartmentofMathematics GettysburgCollege Gettysburg,PA,USA ISSN0172-6056 ISBN978-1-4614-6635-2 ISBN978-1-4614-6636-9(eBook) DOI10.1007/978-1-4614-6636-9 SpringerNewYorkHeidelbergDordrechtLondon LibraryofCongressControlNumber:2013935711 MathematicsSubjectClassification:00-01,01-01,03-01 ©Be´laBajnok2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface to Instructors WhatKindofaBookIs This? Ithasbeenmorethanthreedecadessincethefirstso-calledtransitionbookappeared on the mathematics shelves of college bookstores, and there are currently several dozen such booksavailable. The aim of these booksis to bridge the gap between the traditionallower-levelcourses, primarilycalculus, and the upper-levelcourses that require deeper understanding and maturity, such as modern algebra and real analysis.Thus,themainfocusoftransitionbooksisonthefoundationsofabstract mathematics, giving a thorough treatment of elementary logic and set theory and introducingstudentstotheartandcraftofproofwriting. While this book certainly hopes to provide students with a firm foundationfor theupper-levelcoursesofanundergraduatemathematicsprogram,itisnotgeared solelytowardstudentswhointendtomajorinmathematics.Itisthedisappointing realityatmanyinstitutionsthatsomeofthemostablestudentsarenotconsidering mathematics as a possible major; in fact, coming out of a standard calculus sequence, most students are not familiar with the true nature of this beautiful subject. Therefore, an important mission of the book is to provide students with anunderstandingandanappreciationof(abstract)mathematics,withthehopethat theychoosetostudythesetopicsfurther. Recognizingthatnotallourstudentswillhavetheopportunitytotakeadditional courses in mathematics, this textbook attempts to give a broad view of the field. Evenstudentsmajoringinmathematicsusedto complainthattheywere notgiven an opportunity to take a course on “mathematics” without an artificial division of subjects. In this textbook, we make an attempt to remedy these concerns by providing a unified approach to a diverse collection of topics, by revisiting concepts and questions repeatedly from differing viewpoints, and by pointing out connections, similarities, and differences among subjects whenever possible. If during or after reading this book students choose to take further courses in mathematics,thenwehaveachievedourmostimportantgoal. v vi PrefacetoInstructors In order to provide students with a broad exposure to mathematics, we have includedanunusuallydiversearrayoftopics.Beyondathoroughstudyofconcepts that are expectedto be foundin similar books,we briefly discuss importantmile- stonesinthehistoryofmathematicsandfeaturesomeofthemostinterestingrecent accomplishmentsinthefield.Thisbookaimstoshowstudentsthatmathematicsisa vibrantanddynamichumanenterprisebyincludinghistoricalperspectivesandnotes on the giants of mathematics and their achievements; by mentioning more recent resultsandupdatesonavarietyofquestionsofcurrentactivityinthemathematical community; and by discussing many famous and less well-known questions that have not yet been resolved and that remain open for the mathematicians of the future. We alsointendedtogobeyondthetypicalelementarytextbyprovidingamore thoroughanddeepertreatmentwheneverfeasible.Whilewefinditimportantnotto assumeanyprerequisitesforthebook,weattempttotravelfurtheronsomeofthe mostenchantingpathsthaniscustomaryatthebeginninglevel.Althoughwerealize thatperhapsnotallstudentsare willing tojoin usonthese excursions,we believe thatthereareagreatmanystudentsforwhomtherewardsareworththeeffort. Another important objective—and here is where the author’s Hungarian roots are truly revealed—isto center much of the learning on problem solving. George Po´lya’s famous book How to Solve It1 introduced students around the world to mathematicalproblemsolving,and,asitseditorialreviewsays,“show[ed]anyonein anyfieldhowtothinkstraight.”PaulHalmos—anothermathematicianofHungarian origin2—isoftenquoted3abouttheimportanceofproblems: Themajorpartofeverymeaningfullifeisthesolutionofproblems;aconsiderable partoftheprofessionallifeoftechnicians,engineers,scientists,etc.,isthesolution of mathematical problems. It is the duty of all teachers, and of teachers of mathematics in particular, to expose their students to problems much more than tofacts.4 Ourtexttakestheserecommendationstoheartbyofferingasetofcarefullychosen, instructive,andchallengingproblemsineachchapter. Itistheauthor’shopethatthisbookwillconvincestudentsthatmathematicsis a wonderful and important achievement of humankind and will generate enough enthusiasmtoconvincethemtotake morecoursesinmathematics.Intheprocess, 1OriginallypublishedinhardcoverbyPrincetonUniversityPressin1945.Availableinpaperback fromPrincetonUniversityPress(2004). 2Halmos,authorofnumerousprize-winningbooksandarticlesonmathematicsanditsteaching,is alsoknownastheinventorofthe(cid:2)symbol,usedtomarktheendofproofs,andtheword“iff,”a now-standardabbreviationforthephrase“if,andonlyif.” 3Forexample,byareportoftheMathematicalAssociationofAmericaCommitteeontheTeaching of Undergraduate Mathematics (Washington, D.C., 1983) and by the Notices of the American MathematicalSociety(October,2007,page1141) 4“TheHeartofMathematics,”AmericanMathematicalMonthly87(1980),519–524 PrefacetoInstructors vii studentsshouldlearnhowtothink,write,andtalk abstractlyandprecisely—skills thatwillproveimmeasurablyusefulintheirfuture. HowCan OneTeach from ThisBook? Can abstract mathematical reasoning be taught? In my view, it certainly can be. However, an honest answer would probably qualify this by saying that not all students will be able (or willing) to acquire this skill to the maximal degree. I often tell people that, when teaching this course, I feel like a ski instructor; I can show them how the pros do it and be there for them when they need my advice, praise, or criticism, but how well they will learn it ultimately depends on their abilities, dedication, and enthusiasm. Some students will become able to handle thesteepestslopesandthemostdangerouscurves,whileotherswillmostlyremain on friendlier hills. A few might become Olympic champions, but most will not; however, everyone who gives it an honest effort will at least learn how to move forward without falling. And, perhaps most importantly, I hope that, even though someoccasionallyfindthetrainingfrighteninganddifficult,theywillallenjoythe process. The book contains 24 chapters. Each chapter consists of a lecture followed by about a dozen problems. I am a strong believer in the “spiral” method: topics are often discussed repeatedly throughout the book, each time with more depth, additional insights, or different viewpoints. The chapters are written in an increasinglyadvancedfashion;thelasteightchapters(andespeciallythelastthree orfour)areparticularlychallenginginbothcontentandlanguage.Thelecturesand theproblemsbuildononeanother;theconceptsofthelecturesareoftenintroduced byproblemsinpreviouschaptersorareextendedanddiscussedagaininproblems insubsequentchapters.(TheLATEXcommand“ref”appearsmorethanonethousand timesinthesourcefile.)Therefore,ifanypartofalectureoranyproblemisskipped, this should be done with caution. The material can be covered in a one-semester course or in a two-semester sequence;the latter choice will obviouslyallow for a moreleisurelypacewithopportunitiesfordeeperdiscussionsandadditionalstudent interactions. The heart and soul of this book is in its approximately 280 problems (some with multiple parts); the lectures are intended to be as brief as possible and yet provideenoughinformationforstudentstoattacktheproblems.Iputconsiderable effort into keeping the number of problems relatively small. Each problem was carefully chosen to clarify a concept, to demonstrate a technique, or to enthuse. Thereareveryfewroutineproblems;mostproblemswillrequirerelativelyextensive arguments,creativeapproaches,orboth.Particularlyinlaterchapters,theproblems aimforstudentstodevelopsubstantialinsight.Tomakeeventhemostchallenging problems accessible to all students, hints are provided liberally. An Instructor’s Guide, containingsolutions to all problemsin the book,is available on request at thebook’sproductpageonwww.springer.com. viii PrefacetoInstructors Manyoftheproblemsarefollowedbyremarksaimedatconnectingtheproblems to areasof currentresearchwith the hopethatsomeof these noteswill invitestu- dentstocarryoutfurtherinvestigations.Thebookalsocontainsseveralappendices withadditionalmaterialandquestionsforpossiblefurtherresearch.Someofthese questions are not difficult, but others require a substantial amount of ingenuity— thereareevenknownopenconjecturesamongthem;anyprogressonthesequestions would indeed be considered significant and certainly publishable. I feel strongly thateveryundergraduatestudentshouldengagein aresearchexperience.Whether they will go on to graduate school, enroll in professional studies, or take jobs in education,government,orbusiness,studentswillbenefitfromtheopportunitiesfor perfectingavarietyofskillsthataresearchexperienceprovides. Allowmetoaddafewnotesonmypersonalexperienceswiththisbook.Itaught courses using this text more than 20 times but find it challenging each time. The approach I find best suited for this course is one that maximizes active learning andclass interaction(amongstudentsandbetweenstudentsandmyself).Students are asked to carefully read the lecture before class and to generate solutions to the assigned problems. Our organized and regular out-of-class “Exploratorium” sessions—wherestudentsworkalone orwith otherstudentsin the class underthe supervisionofteachingassociates—seemparticularlybeneficialinhelpingstudents prepareforclass.Ispendnearlyeveryclassbyaskingstudentstopresenttheresults oftheirworktotheclass.AsItellthem,itisnotnecessarythattheyhavecompletely correctsolutions, but I expect them to have worked on all of the problemsbefore classtothebestoftheirability.Itrytobegenerouswithencouragement,praise,and constructivecriticism,butIamnotsatisfieduntilathoroughandcompletesolution ispresentedforeachproblem.Itisnotunusualforaproblemtobediscussedseveral timesbeforeitgetsmyfinalPFB(“PerfectforBe´la”)approval. Without a doubt, teaching this course has been one of the most satisfying experiencesthat I have had in this profession.Watching my students develop and succeed,perhapsmoresothaninanyothercourse,isalwaysasuperblyrewarding adventure. Preface to Students For WhomIs ThisBookWritten? This bookis intendedfor a broadaudience.Any student who wishes to learn and perfect his or her ability to think and reason at an advanced level will benefit from taking a course based on this textbook. The skills of understanding and communicating abstract ideas will prove useful in every professional career: law, medicine,engineering,business,education,politics,science,economics,andothers. Theabilitytoexpressoneselfandtoargueclearly,precisely,andconvincinglyhelps ineverydayinteractionsaswell.Justasotherscanseeifwelookhealthyphysically, they can also assess our intellectual fitness when they listen to our explanations or read our writings. Abstract mathematics, perhaps more than any other field, facilitatesthelearningoftheseessentialskills. An important goal of this book, therefore, is to help students become more comfortablewith abstraction.Paradoxically,the moreone understandsan abstract topic or idea, the less abstract it will seem! Thus, the author’s hope is that his InvitationtoAbstractMathematicsisaccepted,butthatbythetimestudentsfinish thebook,theyagreethatthereisnoneedfortheword“abstract”inthetitle—indeed, thisbookis(just)aboutmathematics. The prerequisites to the text are minimal; in particular, no specific knowledge beyond high school mathematics is assumed. Instead, students taking this course should be willing to explore unusual and often difficult topics and be ready to facechallenges.Facingandovercomingthesechallengeswillbestudents’ultimate rewardattheend. HowCan OneLearn from ThisBook? Welcome to abstract mathematics! If you are like 99% of the students who have takenacoursebasedonthisbook,youwillfindthatthecourseischallengingyouin ix