Undergraduate Texts in Mathematics Editorial Board S. Axler K.A. Ribet For other titles Published in this series, go to www.springer.com/series/666 Ethan D. Bloch Proofs and Fundamentals A First Course in Abstract Mathematics Second Edition Ethan D. Bloch Mathematics Department Bard College Annandale-on-Hudson, NY 12504 USA [email protected] Editorial Board S. Axler K.A.Ribet Mathematics Department Mathematics Department San Francisco State University University of California at Berkeley San Francisco, CA 94132 Berkeley, CA 94720-3840 USA USA [email protected] [email protected] ISSN 0172-6056 ISBN 978-1-4419-7126-5 e-ISBN 978-1-4419-7127-2 DOI 10.1007/978-1-4419-7127-2 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011921408 © Springer Science+Business Media, LLC 2011 Allrightsreserved. Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewritten permissionofthepublisher(SpringerScience+BusinessMedia,LLC,233SpringStreet,NewYork,NY 10013,USA),exceptforbriefexcerptsinconnectionwithreviewsorscholarlyanalysis.Useinconnection withanyformofinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilar ordissimilarmethodologynowknownorhereafterdevelopedisforbidden. Theuseinthispublicationoftradenames,trademarks,servicemarks,andsimilarterms,eveniftheyare notidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyaresubject toproprietaryrights. Printedonacid-freepaper Springer is part of Springer Science+Business Media (www.springer.com) DedicatedtomywifeNancy,inappreciationofherloveandsupport Contents PrefacetotheSecondEdition........................................ xi PrefacetotheFirstEdition .......................................... xiv TotheStudent ..................................................... xix TotheInstructor ...................................................xxiii PartI PROOFS 1 InformalLogic................................................. 3 1.1 Introduction ............................................... 3 1.2 Statements ................................................ 4 1.3 RelationsBetweenStatements................................ 15 1.4 ValidArguments ........................................... 25 1.5 Quantifiers ................................................ 34 2 StrategiesforProofs............................................ 47 2.1 MathematicalProofs—WhatTheyAreandWhyWeNeedThem... 47 2.2 DirectProofs .............................................. 53 2.3 ProofsbyContrapositiveandContradiction..................... 57 2.4 Cases,andIfandOnlyIf .................................... 64 2.5 QuantifiersinTheorems ..................................... 70 2.6 WritingMathematics ....................................... 80 PartII FUNDAMENTALS 3 Sets........................................................... 91 3.1 Introduction ............................................... 91 3.2 Sets—BasicDefinitions ..................................... 93 viii Contents 3.3 SetOperations ............................................. 101 3.4 FamiliesofSets............................................ 109 3.5 AxiomsforSetTheory ...................................... 115 4 Functions ..................................................... 129 4.1 Functions ................................................. 129 4.2 ImageandInverseImage .................................... 140 4.3 CompositionandInverseFunctions ........................... 146 4.4 Injectivity,SurjectivityandBijectivity ......................... 154 4.5 SetsofFunctions........................................... 164 5 Relations...................................................... 171 5.1 Relations ................................................. 171 5.2 Congruence ............................................... 177 5.3 EquivalenceRelations....................................... 185 6 FiniteSetsandInfiniteSets...................................... 195 6.1 Introduction ............................................... 195 6.2 PropertiesoftheNaturalNumbers ............................ 196 6.3 MathematicalInduction ..................................... 201 6.4 Recursion ................................................. 212 6.5 CardinalityofSets.......................................... 221 6.6 FiniteSetsandCountableSets................................ 231 6.7 CardinalityoftheNumberSystems............................ 240 PartIII EXTRAS 7 SelectedTopics................................................. 251 7.1 BinaryOperations .......................................... 251 7.2 Groups ................................................... 257 7.3 HomomorphismsandIsomorphisms........................... 265 7.4 PartiallyOrderedSets....................................... 270 7.5 Lattices................................................... 280 7.6 Counting:ProductsandSums ................................ 288 7.7 Counting:PermutationsandCombinations ..................... 297 7.8 LimitsofSequences ........................................ 312 8 Explorations................................................... 323 8.1 Introduction ............................................... 323 8.2 GreatestCommonDivisors .................................. 324 8.3 DivisibilityTests ........................................... 326 8.4 Real-ValuedFunctions ...................................... 326 8.5 IterationsofFunctions ...................................... 327 8.6 FibonacciNumbersandLucasNumbers ....................... 328 8.7 FuzzySets ................................................ 330 Contents ix 8.8 YouAretheProfessor....................................... 332 Appendix:PropertiesofNumbers .................................... 341 References......................................................... 345 Index ............................................................. 351