Mathematical Reasoning Writing and Proof Version2.1 December 3, 2016 Ted Sundstrom Grand Valley State University TedSundstrom DepartmentofMathematics GrandValleyStateUniversity Allendale,MI49401 [email protected] MathematicalReasoning:WritingandProof PreviousversionsofthisbookwerepublishedbyPearsonEducation,Inc. Changes Made in Version 2.1 There are no changes in content between Version 2.0 of this book and Version 2.1. A few minor errors in Version 2.0 have been corrected in Version 2.1. In addition, there are no changes in content between Version 1.1 of this book and Version2.0. TheonlychangeisthatAppendixC,AnswersandHintsforSelected Exercises, now contains solutions and hints for more exercises. Those exercises withananswerorahintintheappendixareprecededbyastar.?/. License This workis licensed under the Creative Commons Attribution-NonCommercial- ShareAlike3.0UnportedLicense. Thegraphic thatappears throughoutthetextshowsthattheworkis licensedwiththe Creative Commons, that the workmay be usedfor free byany partyso longas attribution is given to the author(s), that the work and itsderivativesare used in the spiritof “share and share alike,” and that no party other than the author(s) may sell this workoranyofitsderivativesforprofit. Fulldetailsmaybefoundbyvisiting http://creativecommons.org/licenses/by-nc-sa/3.0/ or sendinga letter toCreative Commons, 444 Castro Street, Suite 900, Mountain View,California,94041,USA. Contents NotetoStudents vi Preface viii SupplementaryMaterialsfortheInstructor . . . . . . . . . . . . . . . . xiv 1 IntroductiontoWritingProofsinMathematics 1 1.1 StatementsandConditionalStatements. . . . . . . . . . . . . . . 1 1.2 ConstructingDirectProofs . . . . . . . . . . . . . . . . . . . . . 15 1.3 Chapter1Summary . . . . . . . . . . . . . . . . . . . . . . . . . 31 2 LogicalReasoning 33 2.1 StatementsandLogicalOperators . . . . . . . . . . . . . . . . . 33 2.2 LogicallyEquivalentStatements . . . . . . . . . . . . . . . . . . 43 2.3 OpenSentencesandSets . . . . . . . . . . . . . . . . . . . . . . 52 2.4 QuantifiersandNegations. . . . . . . . . . . . . . . . . . . . . . 63 2.5 Chapter2Summary . . . . . . . . . . . . . . . . . . . . . . . . . 80 3 ConstructingandWritingProofsinMathematics 82 3.1 DirectProofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.2 MoreMethodsofProof . . . . . . . . . . . . . . . . . . . . . . . 102 3.3 ProofbyContradiction . . . . . . . . . . . . . . . . . . . . . . . 116 3.4 UsingCasesinProofs . . . . . . . . . . . . . . . . . . . . . . . . 131 iii iv Contents 3.5 TheDivisionAlgorithmandCongruence . . . . . . . . . . . . . . 141 3.6 ReviewofProofMethods . . . . . . . . . . . . . . . . . . . . . . 158 3.7 Chapter3Summary . . . . . . . . . . . . . . . . . . . . . . . . . 166 4 MathematicalInduction 169 4.1 ThePrincipleofMathematicalInduction . . . . . . . . . . . . . . 169 4.2 OtherFormsofMathematicalInduction . . . . . . . . . . . . . . 188 4.3 InductionandRecursion . . . . . . . . . . . . . . . . . . . . . . 200 4.4 Chapter4Summary . . . . . . . . . . . . . . . . . . . . . . . . . 213 5 SetTheory 215 5.1 SetsandOperationsonSets. . . . . . . . . . . . . . . . . . . . . 215 5.2 ProvingSetRelationships. . . . . . . . . . . . . . . . . . . . . . 230 5.3 PropertiesofSetOperations . . . . . . . . . . . . . . . . . . . . 244 5.4 CartesianProducts . . . . . . . . . . . . . . . . . . . . . . . . . 254 5.5 IndexedFamiliesofSets . . . . . . . . . . . . . . . . . . . . . . 264 5.6 Chapter5Summary . . . . . . . . . . . . . . . . . . . . . . . . . 277 6 Functions 281 6.1 IntroductiontoFunctions . . . . . . . . . . . . . . . . . . . . . . 281 6.2 MoreaboutFunctions . . . . . . . . . . . . . . . . . . . . . . . . 294 6.3 Injections,Surjections,andBijections . . . . . . . . . . . . . . . 307 6.4 CompositionofFunctions. . . . . . . . . . . . . . . . . . . . . . 323 6.5 InverseFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 334 6.6 FunctionsActingonSets . . . . . . . . . . . . . . . . . . . . . . 349 6.7 Chapter6Summary . . . . . . . . . . . . . . . . . . . . . . . . . 359 7 EquivalenceRelations 362 7.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 7.2 EquivalenceRelations. . . . . . . . . . . . . . . . . . . . . . . . 375 7.3 EquivalenceClasses . . . . . . . . . . . . . . . . . . . . . . . . . 387 Contents v 7.4 ModularArithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 400 7.5 Chapter7Summary . . . . . . . . . . . . . . . . . . . . . . . . . 411 8 TopicsinNumberTheory 414 8.1 TheGreatestCommonDivisor . . . . . . . . . . . . . . . . . . . 414 8.2 PrimeNumbersandPrimeFactorizations . . . . . . . . . . . . . 426 8.3 LinearDiophantineEquations . . . . . . . . . . . . . . . . . . . 439 8.4 Chapter8Summary . . . . . . . . . . . . . . . . . . . . . . . . . 449 9 FiniteandInfiniteSets 452 9.1 FiniteSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 9.2 CountableSets . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 9.3 UncountableSets . . . . . . . . . . . . . . . . . . . . . . . . . . 476 9.4 Chapter9Summary . . . . . . . . . . . . . . . . . . . . . . . . . 490 A GuidelinesforWritingMathematicalProofs 492 B AnswersfortheProgressChecks 497 C AnswersandHintsforSelectedExercises 536 D ListofSymbols 582 Index 585 Note to Students Thisbookmaybedifferentthanothermathematicstextbooksyouhaveusedsince oneofthemaingoalsofthisbookistohelpyoutodeveloptheabilitytoconstruct andwritemathematicalproofs. Sothisbookisnotjustaboutmathematicalcontent but isalso aboutthe processof doingmathematics. Alongthe way, youwillalso learn some importantmathematical topicsthat will help you in your future study ofmathematics. Thisbookisdesignednottobe justcasuallyread butrather tobe engaged. It may seem likea cliche´ (because itis in almostevery mathematics booknow)but thereistruthinthestatementthatmathematicsisnotaspectatorsport.Tolearnand understandmathematics,youmustengageintheprocessofdoingmathematics. So youmustactivelyreadandstudythebook,whichmeanstohaveapencilandpaper with you and be willing to follow along and fill in missing details. This type of engagement is noteasy and is often frustrating,but if you do so, you willlearn a greatdealaboutmathematicsandmoreimportantly,aboutdoingmathematics. Recognizingthatactivelystudyinga mathematics bookis oftennoteasy, sev- eralfeaturesofthetextbookhavebeendesignedtohelpyoubecomemoreengaged asyoustudythematerial. Someofthefeaturesare: PreviewActivities. WiththeexceptionofSections1.1and3.6,eachsection (cid:15) hasexactlytwopreviewactivities.SomePreviewActivitieswillreviewprior mathematical work that is necessary for the new section. This prior work maycontainmaterialfrompreviousmathematicalcoursesoritmay contain material covered earlier in thistext. Other previewactivitieswillintroduce newconceptsanddefinitionsthatwillbeusedwhenthatsectionisdiscussed inclass. Itisveryimportantthatyouworkonthesepreviewactivitiesbefore starting the rest of the section. Please note that answers to these preview activitiesare notincluded in the text. This bookis designed to be used for a courseand itisleftup tothediscretionof each individualinstructoras to howtodistributetheanswerstothepreviewactivities. vi NotetoStudents vii Progress Checks. Several Progress Checks are included in each section. (cid:15) These are either shortexercises or short activitiesdesignedto help you de- termineifyouareunderstandingthematerialasyouarestudyingthematerial inthesection.Assuch,itisimportanttoworkthroughtheseprogresschecks totestyourunderstanding,andifnecessary, studythematerialagainbefore proceedingfurther. Soitisimportanttoattempttheseprogresschecksbefore checkingtheanswers,whichareareprovidedinAppendixB. Chapter Summaries. To assistyou with studyingthe material in the text, (cid:15) there is a summary at the end of each chapter. The summaries usually list theimportantdefinitionsintroducedinthechapterandtheimportantresults proveninthechapter. Ifappropriate,thesummaryalsodescribestheimpor- tantprooftechniquesdiscussedinthechapter. AnswersforSelected Exercises. Answersorhintsforseveralexercisesare (cid:15) includedinan AppendixC. Thoseexercises withananswerora hintinthe appendixareprecededbyastar.?/. ThemainchangeinVersion2.0ofthis textbook from the previous versions is the addition of more exercises with answersorhintsintheappendix. Althoughnot part of the textbook, there are now 107 onlineideoswith about 14 hours of content that span the first seven chapters of this book. These videos arefreelyavailableonlineatGrandValley’sDepartmentofMathematicsYouTube channelonthisplaylist: http://gvsu.edu/s/0l1 These online videos were created and developed by Dr. Robert Talbert of Grand ValleyStateUniversity. Thereisalsoawebsiteforthetextbookat https://sites.google.com/site/mathematicalreasoning3ed/ Youmayfindsomethingstherethatcouldbeofhelp. Forexample,therecurrently is a link to study guides for the sections of this textbook. Good luck with your studyof mathematics and please make use of the onlinevideosandthe resources availableinthetextbookandatthewebsiteforthetextbook.Iftherearethingsthat youthinkwouldbegoodadditionstothebookor theweb site, pleasefeel free to [email protected]. Preface MathematicalReasoning: WritingandProof is designedto be a text for the first course in the college mathematics curriculum that introducesstudentsto the pro- cesses of constructingand writingproofs and focuses on the formal development ofmathematics. Theprimarygoalsofthetextaretohelpstudents: Developlogical thinkingskillsand to develop the abilityto thinkmore ab- (cid:15) stractlyinaprooforientedsetting. Develop the ability to construct and write mathematical proofs using stan- (cid:15) dard methods of mathematical proof includingdirect proofs, proof by con- tradiction,mathematicalinduction,caseanalysis,andcounterexamples. Developtheabilitytoreadandunderstandwrittenmathematicalproofs. (cid:15) Developtalentsforcreativethinkingandproblemsolving. (cid:15) Improve theirqualityof communicationin mathematics. Thisincludesim- (cid:15) proving writing techniques, reading comprehension, and oral communica- tioninmathematics. Betterunderstandthenatureofmathematicsanditslanguage. (cid:15) Anotherimportantgoalofthistextistoprovidestudentswithmaterialthatwillbe neededfortheirfurtherstudyofmathematics. Thistypeofcoursehasnowbecomeastandardpartofthemathematicsmajorat manycollegesanduniversities. Itisoftenreferredtoasa“transitioncourse”from thecalculussequencetotheupper-levelcoursesinthemajor. Thetransitionisfrom the problem-solving orientation of calculus to the more abstract and theoretical upper-level courses. This is needed today because many students complete their study of calculus withoutseeing a formal proof or having constructed a proof of their own. This is in contrast to many upper-level mathematics courses, where viii Preface ix the emphasis is on the formal development of abstract mathematical ideas, and theexpectationsarethatstudentswillbeabletoreadandunderstandproofsandbe abletoconstructandwritecoherent,understandablemathematicalproofs. Students shouldbeabletousethistextwithabackgroundofonesemesterofcalculus. Important Features of the Book Following are some of the important features of this text that will help with the transitionfromcalculustoupper-levelmathematicscourses. 1. EmphasisonWritinginMathematics Issuesdealingwithwritingmathematical expositionare addressedthrough- out the book. Guidelines for writing mathematical proofs are incorporated intothe book. Theseguidelinesare introducedas neededand begininSec- tion 1.2. AppendixA contains a summary of all the guidelinesfor writing mathematicalproofsthatareintroducedthroughoutthetext. Inaddition,ev- eryattempthasbeenmadetoensurethateverycompletedproofpresentedin thistextiswrittenaccordingtotheseguidelines.Thisprovidesstudentswith examplesofwell-writtenproofs. Oneofthemotivatingfactorsforwritingthisbookwastodevelopatextbook forthecourse“CommunicatinginMathematics”atGrandValleyStateUni- versity. This course is part of the university’sSupplemental WritingSkills Program,andtherewasnotextthatdealtwithwritingissuesinmathematics thatwassuitableforthiscourse. Thisiswhysomeofthewritingguidelines in the text deal withthe use of LATEXor a word processor that is capable of producing the appropriate mathematical symbols and equations. However, thewritingguidelinescaneasilybeimplementedforcourseswherestudents donothaveaccesstothistypeofwordprocessing. 2. InstructionintheProcessofConstructingProofs One of the primary goals of this book is to develop students’ abilities to constructmathematical proofs. Another goal is to develop their abilitiesto write the proof in a coherent manner that conveys an understanding of the prooftothereader. Thesearetwodistinctskills. InstructiononhowtowriteproofsbeginsinSection1.2andisdevelopedfur- ther inChapter3. In addition,Chapter 4 isdevotedto developingstudents’ abilitiestoconstructproofsusingmathematicalinduction. x Preface Studentsareintroducedtoamethodtoorganizetheirthoughtprocesseswhen attemptingtoconstructa proofthatusesa so-calledknow-showtable. (See Section1.2andSection3.1.) Studentsusethistabletoworkbackwardfrom what it is they are trying to prove while at the same time workingforward fromtheassumptionsoftheproblem. Theknow-showtablesare usedquite extensivelyinChapters1and3. However,theexplicituseofknow-showta- blesisgraduallyreducedandthesetablesarerarelyusedinthelaterchapters. One reason for this is that these tables may work well when there appears tobe onlyone wayof provinga certain result. As theproofs become more complicatedorothermethodsofproof(suchasproofsusingcases)areused, theseknow-showtablesbecomelessuseful. So the know-showtables are not to be considered an absolute necessity in usingthetext. However,theyare usefulforstudentsbeginningtolearnhow toconstructandwriteproofs. Theyprovideaconvenientwayforstudentsto organizetheir work. More importantly,they introducestudentsto a way of thinkingaboutaproblem. Insteadofimmediatelytryingtowriteacomplete proof,theknow-showtableforcesstudentstostop,think,andaskquestions suchas JustexactlywhatisitthatIamtryingtoprove? (cid:15) HowcanIprovethis? (cid:15) WhatmethodsdoIhavethatmayallowmetoprovethis? (cid:15) Whataretheassumptions? (cid:15) HowcanIusetheseassumptionstoprovetheresult? (cid:15) Being able toask these questionsis a bigstep in constructinga proof. The nexttask istoanswer the questionsand touse thoseanswersto constructa proof. 3. EmphasisonActiveLearning Oneoftheunderlyingpremisesofthistextisthatthebestwaytolearn and understand mathematics is to be actively involved in the learning process. However,itisunlikelythatstudentswilllearnallthemathematicsinagiven course on their own. Students actively involved in learning mathematics need appropriate materials that will provide guidance and support in their learningof mathematics. There are several waysthistext promotesactivite learning.