P1: JZZ This page intentionally left blank

1 P1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0iThis page intentionally left blankP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0 How To Prove ItiP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0iiP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0 HOW TO PROVE ITA Structured Approach, Second EditionDaniel J. VellemanDepartment of Mathematics and Computer ScienceAmherst Collegeiiicambridge university pressCambridge, New York, Melbourne, Madrid, Cape Town, Singapore, S o PauloCambridge University PressThe Edinburgh Building, Cambridgecb2 2ru,UKFirst published in print formatisbn-13978-0-521-86124-3isbn-13978 -0-521-67599-4isbn-13978-0-511-16116-2 Cambridge University Press 1994, 20062006 publication is in copyright.

2 Subject to statutory exception and to the provision ofrelevant collective licensing agreements, no reproduction of any part may take placewithout the written permission of Cambridge University University Press has no responsibility for the persistence or accuracy ofurlsfor external or third-party internet websites referred to in this publication, and does notguarantee that any content on such websites is, or will remain, accurate or in the United States of America by Cambridge University Press, New (EBL)eBook (EBL)hardbackP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0To ShelleyvP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0viP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0 ContentsPrefacepageixIntroduction11 Sentential Deductive Reasoning and Logical Truth Variables and Operations on The Conditional and Biconditional Connectives432 Quantificational Equivalences Involving More Operations on Sets733 Proof Proofs Involving Negations and Proofs Involving Proofs Involving Conjunctions and Proofs Involving Existence and Uniqueness More Examples of Proofs1554 Ordered Pairs and Cartesian More About Ordering Relations189viiP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23.

3 41 0 521 86124 1 Char Count= Equivalence Relations2135 One-to-one and Inverses of Images and Inverse Images: A Research Project2556 Mathematical Proof by Mathematical More Strong Closures Again3007 Infinite Equinumerous Countable and Uncountable The Cantor Schr oder Bernstein Theorem322 Appendix 1: Solutions to Selected Exercises329 Appendix 2: Proof Designer373 Suggestions for Further Reading375 Summary of Proof Techniques376 Index381P1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0 PrefaceStudents of mathematics and computer science often have trouble the firsttime they re asked to work seriously with mathematical proofs, because theydon t know the rules of the game.

4 What is expected of you if you are askedto prove something? What distinguishes a correct proof from an incorrectone? This book is intended to help students learn the answers to these ques-tions by spelling out the underlying principles involved in the construction students get their first exposure to mathematical proofs in a highschool course on geometry. Unfortunately, students in high school geometryare usually taught to think of a proof as a numbered list of statements andreasons, a view of proofs that is too restrictive to be very useful. There is aparallel with computer science here that can be instructive. Early programminglanguages encouraged a similar restrictive view of computer programs as num-bered lists of instructions.

5 Now computer scientists have moved away fromsuch languages and teach programming by using languages that encourage anapproach called structured programming. The discussion of proofs in thisbook is inspired by the belief that many of the considerations that have ledcomputer scientists to embrace the structured approach to programming ap-ply to proof-writing as well. You might say that this book teaches structuredproving. In structured programming, a computer program is constructed, not by listinginstructions one after another, but by combining certain basic structures suchas the if-else construct and do-while loop of the Java programming structures are combined, not only by listing them one after another, butalso bynestingone within another.

6 For example, a program constructed byixP1: JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0xPrefacenesting an if-else construct within a do-while loop would look like this:doif [condition][List of instructions goes here.]else[Alternate list of instructions goes here.]while [condition]The indenting in this program outline is not absolutely necessary, but it is aconvenient method often used in computer science to display the underlyingstructure of a proofs are also constructed by combining certain basic proofstructures. For example, a proof of a statement of the form ifPthenQ oftenuses what might be called the suppose-until structure: WesupposethatPistrueuntilwe are able to reach the conclusion thatQis true, at which point weretract this supposition and conclude that the statement ifPthenQ is example is the for arbitraryxprove structure: To prove a statementof the form for allx,P(x), wedeclare x to be an arbitrary objectand thenprove P(x).

7 Once we reach the conclusion thatP(x) is true we retract thedeclaration ofxas arbitrary and conclude that the statement for allx,P(x) is true. Furthermore, to prove more complex statements these structures areoften combined, not only by listing one after another, but also by nesting onewithin another. For example, to prove a statement of the form for allx,ifP(x)thenQ(x) we would probably nest a suppose-until structure within a forarbitraryxprove structure, getting a proof of this form:Letxbe (x) is true.[Proof ofQ(x) goes here.]Thus, ifP(x) thenQ(x).Thus, for allx,ifP(x) thenQ(x).As before, we have used indenting to make the underlying structure of the course, mathematicians don t ordinarily write their proofs in this indentedform.

8 Our aim in this book is to teach students to write proofs in ordinaryEnglish paragraphs, just as mathematicians do, and not in the indented , our approach is based on the belief that if students are to succeedatwritingsuchproofs,theymustunder standtheunderlyingstructurethatproofshav e. They must learn, for example, that sentences like Letxbe arbitrary and SupposeP are not isolated steps in proofs, but are used to introduce the forarbitraryxprove and suppose-until proof structures. It is not uncommonfor beginning students to use these sentences inappropriately in other : JZZ/JZK0521861241pre CB996/Velleman October 19, 2005 23:41 0 521 86124 1 Char Count= 0 PrefacexiSuch mistakes are analogous to the programming error of using a do with nomatching while.

9 Note that in our examples, the choice of proof structure is guided by the log-ical form of the statement being proven. For this reason, the book begins withelementary logic to familiarize students with the various forms that mathemati-cal statements take. Chapter 1 discusses logical connectives, and quantifiers areintroduced in Chapter 2. These chapters also present the basics of set theory,because it is an important subject that is used in the rest of the book (andthroughout mathematics), and also because it serves to illustrate many of thepoints of logic discussed in these 3 covers structured proving techniques in a systematic way, runningthrough the various forms that mathematical statements can take and discussingthe proof structures appropriate for each form.

10 The examples of proofs in thischapter are for the most part chosen, not for their mathematical content, but forthe proof structures they illustrate. This is especially true early in the chapter,when only a few proof techniques have been discussed, and as a result many ofthe proofs in this part of the chapter are rather trivial. As the chapter progressesthe proofs get more sophisticated and more interesting, 4 and 5, on relations and functions, serve two purposes. First,they provide subject matter on which students can practice the proof-writingtechniques from Chapter 3. And second, they introduce students to some fun-damental concepts used in all branches of 6 is devoted to a method of proof that is very important in bothmathematics and computer science: mathematical induction.