y , MATHEMATICAL T H I N K I N G A N D W R I T I N G y , This Page Intentionally Left Blank y , RANDALL B. MADDOX Pepperdine University, Malibu, CA MATHEMATICAL T H I N K I N G A N D W R I T I N G A Transition to Abstract Mathematics A C A D E M I C P R E S S A Harcourt Science and Technology Company y , SponsoringEditor BarbaraHolland ProductionEditor AmyFleischer MarketingCoordinator StephanieStevens Cover/InteriorDesign CatandMouse CoverImage RosmiDuaso/Timepix Copyeditor Editor’sInk Proofreader PhyllisCoyneetal. Composition InteractiveCompositionCorporation Printer InterCityPress,Inc. Thisbookisprintedonacid-freepaper.(cid:3)∞ Copyright(cid:3)c 2002byHARCOURT/ACADEMICPRESS Allrightsreserved. Nopartofthispublicationmaybereproducedortransmittedinanyformorbyany means,electronicormechanical,includingphotocopy,recording,oranyinformation storageandretrievalsystem,withoutpermissioninwritingfromthepublisher. Requestsforpermissiontomakecopiesofanypartoftheworkshouldbemailedto: PermissionsDepartment,Harcourt,Inc.,6277SeaHarborDrive,Orlando,Florida32887-6777. AcademicPress AHarcourtScienceandTechnologyCompany 525BStreet,Suite1900,SanDiego,California92101-4495,USA http://www.academicpress.com AcademicPress HarcourtPlace,32JamestownRoad,LondonNW17BY,UK http://www.academicpress.com Harcourt/AcademicPress AHarcourtScienceandTechnologyCompany 200WheelerRoad,Burlington,Massachusetts01803,USA http://www.harcourt-ap.com LibraryofCongressControlNumber:2001091290 InternationalStandardBookNumber:0-12-464976-9 PRINTEDINTHEUNITEDSTATESOFAMERICA 01 02 03 04 05 06 IP 9 8 7 6 5 4 3 2 1 y , ForDeanPriest whounwittinglyplantedtheseedofthisbook y , This Page Intentionally Left Blank y , Contents WhyReadThisBook xiii Preface xv CHAPTER0 NotationandAssumptions 1 0.1 SetTerminologyandNotation 1 0.2 Assumptions 5 0.2.1 Basicalgebraicpropertiesofrealnumbers 5 0.2.2 Orderingofrealnumbers 7 0.2.3 OtherassumptionsaboutR 9 PARTI FOUNDATIONS OF LOGIC AND PROOF WRITING 11 CHAPTER1 Logic 13 1.1 IntroductiontoLogic 13 1.1.1 Statements 13 1.1.2 Negationofastatement 15 1.1.3 CombiningstatementswithAND/OR 15 1.1.4 Logicalequivalence 18 1.1.5 Tautologiesandcontradictions 18 1.2 If-ThenStatements 20 1.2.1 If-thenstatements 20 1.2.2 Variationsonp→q 22 1.2.3 Logicalequivalenceandtautologies 23 vii y , viii Contents 1.3 UniversalandExistentialQuantifiers 27 1.3.1 Theuniversalquantifier 27 1.3.2 Theexistentialquantifier 29 1.3.3 Uniqueexistence 30 1.4 NegationsofStatements 31 1.4.1 Negationsofp∧qandp∨q 32 1.4.2 Negationsofp→q 33 1.4.3 Negationsofstatements with∀and∃ 33 CHAPTER2 Beginner-LevelProofs 38 2.1 ProofsInvolvingSets 38 2.1.1 Termsinvolvingsets 38 2.1.2 Directproofs 41 2.1.3 Proofsbycontrapositive 44 2.1.4 Proofsbycontradiction 45 2.1.5 Disprovingastatement 45 2.2 IndexedFamiliesofSets 47 2.3 AlgebraicandOrderingPropertiesofR 53 2.3.1 Basicalgebraicproperties ofrealnumbers 53 2.3.2 Orderingoftherealnumbers 56 2.3.3 Absolutevalue 57 2.4 ThePrincipleofMathematicalInduction 61 2.4.1 ThestandardPMI 62 2.4.2 VariationofthePMI 64 2.4.3 Stronginduction 65 2.5 EquivalenceRelations:TheIdeaofEquality 68 2.5.1 Analyzingequality 68 2.5.2 Equivalenceclasses 72 2.6 Equality,Addition,andMultiplicationinQ 76 2.6.1 EqualityinQ 77 2.6.2 Well-defined+and×onQ 78 2.7 TheDivisionAlgorithmandDivisibility 79 2.7.1 Evenandoddintegers;thedivision algorithm 79 2.7.2 DivisibilityinZ 81 2.8 Rootsandirrationalnumbers 85 2.8.1 Rootsofrealnumbers 86 2.8.2 Existenceofirrationalnumbers 87 2.9 RelationsInGeneral 90 y , Contents ix CHAPTER3 Functions 97 3.1 DefinitionsandTerminology 97 3.1.1 Definitionandexamples 97 3.1.2 Otherterminologyandnotation 101 3.1.3 Threeimportanttheorems 103 3.2 CompositionandInverseFunctions 106 3.2.1 Compositionoffunctions 106 3.2.2 Inversefunctions 108 3.3 CardinalityofSets 110 3.3.1 Finitesets 111 3.3.2 Infinitesets 113 3.4 CountingMethodsandtheBinomialTheorem 118 3.4.1 Theproductrule 118 3.4.2 Permutations 122 3.4.3 Combinationsandpartitions 122 3.4.4 Countingexamples 125 3.4.5 Thebinomialtheorem 126 PARTII BASIC PRINCIPLES OF ANALYSIS 131 CHAPTER4 TheRealNumbers 133 4.1 TheLeastUpperBoundAxiom 134 4.1.1 Leastupperbounds 134 4.1.2 TheArchimedeanpropertyofR 136 4.1.3 Greatestlowerbounds 137 4.1.4 TheLUBandGLBpropertiesapplied tofinitesets 137 4.2 SetsinR 140 4.2.1 Openandclosedsets 140 4.2.2 Interior,exterior,andboundary 142 4.3 LimitPointsandClosureofSets 143 4.3.1 Closureofsets 144 4.4 Compactness 146 4.5 SequencesinR 149 4.5.1 Monotonesequences 150 4.5.2 Boundedsequences 151 4.6 ConvergenceofSequences 153 4.6.1 Convergencetoarealnumber 154 4.6.2 Convergenceto±∞ 158 4.7 TheNestedIntervalProperty 160 4.7.1 FromLUBaxiomtoNIP 161