26 The UNDERPGRuAreD UanATdE A p TpEliXeTdS SERIES Sally The Tools of Mathematical Reasoning Tamara J. Lakins American Mathematical Society The Tools of Mathematical Reasoning T h e UNDERPGRuAreD aUnAdT EA p pTlEiXedTS • 26 SERIES Sally The Tools of Mathematical Reasoning Tamara J. Lakins American Mathematical Society Providence, Rhode Island EDITORIAL COMMITTEE Gerald B. Folland (Chair) Steven J. Miller Jamie Pommersheim Serge Tabachnikov 2010 Mathematics Subject Classification. Primary 00-01. For additional informationand updates on this book, visit www.ams.org/bookpages/amstext-26 Library of Congress Cataloging-in-Publication Data Names: Lakins,TamaraJ.,1963- Title: Thetoolsofmathematicalreasoning/TamaraJ.Lakins. Description: Providence,RhodeIsland: AmericanMathematicalSociety,[2016]|Series: Pure andappliedundergraduatetexts;volume26|Includesbibliographicalreferencesandindex. Identifiers: LCCN2016021930|ISBN9781470428990(alk. paper) Subjects: LCSH:Mathematicalanalysis–Foundations–Textbooks. |Logic,Symbolicandmath- ematical–Textbooks. |AMS:General–Instructionalexposition(textbooks,tutorialpapers,etc.). msc Classification: LCCQA300.L262016|DDC511.3–dc23LCrecordavailable athttps://lccn. loc.gov/2016021930 Copying and reprinting. Individual readersofthispublication,andnonprofit librariesacting 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,providedthecustomaryacknowledgmentofthesourceisgiven. Republication,systematiccopying,ormultiplereproductionofanymaterialinthispublication 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(cid:2) service. Formoreinformation,pleasevisit: http://www.ams.org/rightslink. Sendrequestsfortranslationrightsandlicensedreprintstoreprint-permission@ams.org. Excludedfromtheseprovisionsismaterialforwhichtheauthorholdscopyright. Insuchcases, requestsforpermissiontoreuseorreprintmaterialshouldbeaddresseddirectlytotheauthor(s). Copyrightownershipisindicatedonthecopyrightpage,oronthelowerright-handcornerofthe firstpageofeacharticlewithinproceedingsvolumes. (cid:2)c 2016bytheauthor. Allrightsreserved. PrintedintheUnitedStatesofAmerica. (cid:2)∞ Thepaperusedinthisbookisacid-freeandfallswithintheguidelines establishedtoensurepermanenceanddurability. VisittheAMShomepageathttp://www.ams.org/ 10987654321 212019181716 For my husband Harald Ellers, my son Michael Ellers, and my parents Billy and Lois Lakins, with love Contents Preface ix To Students xii Acknowledgements xiii Chapter 1. Language, Logic, and Proof 1 1.1. Language and logic 1 1.2. Proof 16 Chapter 2. Techniques of Proof 25 2.1. More direct proofs 25 2.2. Indirect proofs: Proofs by contradiction and contrapositive 38 2.3. Two important theorems 44 2.4. Proofs of statements involving mixed quantifiers 47 Chapter 3. Induction 53 3.1. Principle of Mathematical Induction 53 3.2. Strong induction 61 Chapter 4. Sets 67 4.1. The language of sets 67 4.2. Operations on sets 74 4.3. Arbitrary unions and intersections 83 4.4. Axiomatic set theory 89 Chapter 5. Functions 93 5.1. Definitions 93 5.2. Function composition 104 5.3. One-to-one and onto functions 107 vii viii Contents 5.4. Invertible functions 114 5.5. Functions and sets 121 Chapter 6. An Introduction to Number Theory 131 6.1. The Division Algorithm and the Well-Ordering Principle 131 6.2. Greatest common divisors and the Euclidean Algorithm 135 6.3. Relatively prime integers and the Fundamental Theorem of Arithmetic 141 6.4. Congruences 145 6.5. Congruence classes 149 Chapter 7. Equivalence Relations and Partitions 155 7.1. Introduction 155 7.2. Equivalence relations 157 7.3. Partitions 162 Chapter 8. Finite and Infinite Sets 167 8.1. Introduction 167 8.2. Finite sets 170 8.3. Infinite sets 179 8.4. What next? 188 Chapter 9. Foundations of Analysis 191 9.1. Introduction 191 9.2. The Completeness Axiom 193 9.3. The Archimedean Property and its consequences 202 9.4. What next? 207 Appendix. Writing Mathematics 209 Bibliography 211 Index 213 Preface Theideaforthistextbookwasconceivedasadirectresultofmyexperienceteaching the “introduction to proofs” course at Allegheny College. When I first started teaching this course, there were only a handful of appropriate textbooks on the market. My experience teaching from various textbooks clarified in my mind what I wanted to accomplish in such a course and how to accomplish it. Onepossibletitle(andtheoneusedatAlleghenyCollege)foran“introduction to proofs” course is “Foundations of Mathematics”, which can conjure up at least two possibilities for the focus of the course. The word “foundations” could be interpreted in the sense of the logician: working axiomatically and in the language of set theory, or working within a formal proof system. On the other hand, the coursecanbeviewedasastudent’sfirst exposuretoproofs, sets, functions, etc.,as mathematicians use them, giving students a practical collection of tools that will enablethemtobesuccessfulinlatermathematicscourses, suchasabstractalgebra and real analysis. As interesting as the first interpretation is, in my opinion the second interpretation is the right one for a first exposure to these ideas and for the average mathematics major. It is important that students begin writing proofs as early as possible in the course,hopefullybytheendofthesecondweekofclasses. Toachievethis,Ipresent onlyenoughlogicforstudentstobeabletoworkwiththepropositionalconnectives and the quantifiers. Although the initial treatment of this material is streamlined, the importance of this material is emphasized throughout the book. Students are frequentlyreminded,especiallyintheearlychapters,oftheimportanceofthelogical structure of a mathematical statement as a framework for finding a proof of that statement. Inparticular, the importanceof the logical structureof amathematical definition as a framework for proving that an object has (or does not have) that property is a constant theme throughout the textbook. Focusing on logical structure is an important first step in addressing the ques- tion, “How do I start?” that students who are learning to write proofs often ask. ix