BookofProof - Virginia Commonwealth University

1 Book of ProofThird EditionRichard HammackPublished by Richard HammackRichmond, VirginiaBook of ProofEdition 2018 by Richard HammackThis work is licensed under the Creative Commons International LicenseTypeset in 11pt TEX Gyre Schola using PDFLATEXC over by R. Hammack. The cover diagrams are based on a geometric construction thatrenders a correct perspective view of an object (here an octagonal column) from its floorplan. The method was invented by Piero della Francesca 1415 1492, a Renaissance painterand my studentsContentsPrefaceviiIntroductionvi iiI Fundamentals1.

2 Introduction to The Cartesian Power Union, Intersection, Venn Indexed Sets That Are Number Russell s Paradox322. And, Or, Conditional Biconditional Truth Tables for Logical More on Conditional Translating English to Symbolic Negating Logical An Important Note643. The Multiplication The Addition and Subtraction Factorials and Counting Pascal s Triangle and the Binomial The Inclusion-Exclusion Counting The Division and Pigeonhole Combinatorial Proof108vII How to Prove Conditional Statements4. Direct Direct Using Treating Similar Cases1255.

3 Contrapositive Contrapositive Congruence of Mathematical Writing1336. Proof by Proving Statements with Proving Conditional Statements by Combining Some Words of Advice143 III More on Proof7. Proving Non-Conditional If-and-Only-If Equivalent Existence Proofs; Existence and Uniqueness Constructive Versus Non-Constructive Proofs1548. Proofs Involving How to Provea How to ProveA How to ProveA= Examples: Perfect Numbers1659. Disproving Existence Disproof by Contradiction17810. Mathematical Proof by Proof by Strong Proof by Smallest The Fundamental Theorem of Fibonacci Numbers193viIV Relations, Functions and Cardinality11.

4 Properties of Equivalence Equivalence Classes and The Integers Relations Between Sets22112. Injective and Surjective The Pigeonhole Principle Inverse Image and Preimage24213. Proofs in The Triangle Definition of a Limits That Do Not Limit Continuity and Limits at Series26514. Cardinality of Sets with Equal Countable and Uncountable Comparing The Cantor-Bernstein-Schr der Theorem284 Conclusion291 Solutions292 Preface to the Third EditionMygoal in writing this book has been to create a very inexpensivehigh-quality textbook.

5 The book can be downloaded from my webpage inPDFformat for free, and the print version costs considerably lessthan comparable traditional this third edition, Chapter 3 (on counting) has been expanded, and anew chapter on calculus proofs has been added. New examples and exerciseshave been added throughout. My decisions regarding revisions have beenguided by both the Amazon reviews and emails from readers, and I amgrateful for all have taken pains to ensure that the third edition is compatible with thesecond. Exercises have not been reordered, although some have been editedfor clarity and some new ones have been appended.

6 (The one exceptionis that Chapter 3 s reorganization shifted some exercises.) The chaptersequencing is identical between editions, with one exception: The finalchapter on cardinality has become Chapter 14 in order to make way for thenew Chapter 13 on calculus proofs. There has been a slight renumbering ofthe sections within chapters 10 and 11, but the numbering of the exerciseswithin the sections is core of this book is an expansion and refinement of lecture notes Ideveloped while teaching proofs courses over the past 18 years at VirginiaCommonwealth University (a large state University ) and Randolph-MaconCollege (a small liberal arts college).

7 I found the needs of these two audiencesto be nearly identical, and I wrote this book for them. But I am mindful of alarger audience. I believe this book is suitable for almost any undergraduatemathematics HammackLawrenceville, VirginiaFebruary 14, 2018 IntroductionThis is a book about how to prove this point in your education, mathematics has probably beenpresented as a primarily computational discipline. You have learned tosolve equations, compute derivatives and integrals, multiply matrices andfind determinants; and you have seen how these things can answer practicalquestions about the real world.

8 In this setting your primary goal in usingmathematics has been to compute there is another side of mathematics that is more theoretical thancomputational. Here the primary goal is to understand mathematicalstructures, to prove mathematical statements, and even to invent or discovernew mathematical theorems and theories. The mathematical techniquesand procedures that you have learned and used up until now are foundedon this theoretical side of mathematics. For example, in computing the areaunder a curve, you use the fundamental theorem of calculus. It is becausethis theorem is true that your answer is correct.

9 However, in learningcalculus you were probably far more concerned with how that theorem couldbe applied than in understanding why it is true. But how do weknowit istrue? How can we convince ourselves or others of its validity? Questions ofthis nature belong to the theoretical realm of mathematics. This book is anintroduction to that book will initiate you into an esoteric world. You will learn andapply the methods of thought that mathematicians use to verify theorems,explore mathematical truth and create new mathematical theories. Thiswill prepare you for advanced mathematics courses, for you will be betterable to understand proofs, write your own proofs and think critically andinquisitively about book is organized into four parts, as outlined I Fundamentals Chapter 1: Sets Chapter 2: Logic Chapter 3: CountingChapters 1 and 2 lay out the language and conventions used in all advancedmathematics.

10 Sets are fundamental because every mathematical structure,object, or entity can be described as a set. Logic is fundamental because itallows us to understand the meanings of statements, to deduce facts aboutmathematical structures and to uncover further structures. All subsequentchapters build on these first two chapters. Chapter 3 is included partlybecause its topics are central to many branches of mathematics, but alsobecause it is a source of many examples and exercises that occur throughoutthe book. (However, the course instructor may choose to omit Chapter 3.)PART II Proving Conditional Statements Chapter 4: Direct Proof Chapter 5: Contrapositive Proof Chapter 6: Proof by ContradictionChapters 4 through 6 are concerned with three main techniques used forproving theorems that have the conditional form IfP, then Q.