The Art Of Proof - Mathematics

1 Matthias Beck & Ross Geoghegan The Art Of Proof Basic Training For Deeper Mathematics August 8, 2011. Springer Great teachers introduced us to the arts of Mathematics and writing: To Harald Kohl and Hartmut Stapf To the memory of Fr. Harry Lawlor, SJ and Fr. Joseph Veale, SJ. Preface PEANUTS: c United Feature Syndicate, Inc. Reprinted with permission. We have written this book with several kinds of readers in mind: (a) Undergraduates who have taken courses such as calculus and linear algebra, but who are not yet prepared for upper-level Mathematics courses. We cover mathematical topics that these students should know. The book also provides a bridge to the upper-level courses, since we discuss formalities and conventions in detail, including the axiomatic method and how to deal with proofs.

2 (b) Mathematics teachers and teachers-in-training. We present here some of the foundations of Mathematics that anyone teaching Mathematics beyond the most elementary levels should know. (c) High-school students with an unusually strong interest in Mathematics . Such students should find this book interesting and (we hope) unconventional. (d) Scientists and social scientists who have found that the Mathematics they studied as undergraduates is not sufficient for their present needs. Typically, the problem here is not the absence of training in a particular technique, but rather a general feeling of insecurity about what is correct or incorrect in Mathematics , a sense of material only partly understood. Scientists must be confident that they are using Mathematics correctly: fallacious Mathematics almost guarantees bad science.

3 In so far as possible we try to work in the formal methods indirectly, as we take the reader through some interesting Mathematics . Our subject is number systems: the integers and the natural numbers (that's the discrete Part I), the real numbers and the rational numbers (the continuous Part II). In this there is emphasis on induction, vii viii Preface recursion, and convergence. We also introduce cardinal number, a topic that links the discrete to the continuous. We teach method: how to organize a Proof correctly, how to avoid fallacies, how to use quantifiers, how to negate a sentence correctly, the axiomatic method, etc. We assert that computer scientists, physicists, Mathematics teachers, mathematically inclined economists, and biologists need to understand these things.

4 Perhaps you too if you have read this far. We sometimes hear students speak of theoretical math, usually in a negative tone, to describe Mathematics that involves theorems and proofs rather than computations and applications. The trouble with this is that, sooner or later, Mathematics becomes sufficiently subtle that fundamentals have to be understood. [W]e share the view that applied Mathematics may not exist only applied mathematicians (R. C. Buck, Preface to Advanced Calculus). We sometimes hear students say, I like math but I don't like proofs. They have not yet realized that a Proof is nothing more than an explanation of why a carefully worded statement is true. The explanation too should be carefully worded: what is said should be what is meant and what is meant should be what is said.

5 But who needs that level of precision? The answer is that almost all users of mathe- matics, except perhaps users at purely computational levels, need to understand what they are doing, if only to have confidence that they are not making mistakes. Here are some examples. Every mathematically trained person should understand induction arguments and recursive definitions. It is hard to imagine how one could write a nontrivial computer program without this basic understanding. Indeed, a software engineer of our acquaintance tells us that his (small) company's software has million lines of code, which must be easy to manage; therefore recursive algorithms are forbidden unless very clearly marked as such, and most of his programmers do not You had better be clear understand recursion deeply enough that their recursive programs can be trusted about what axioms you are to be error-free: so they just insert a recursion package taken from a software assuming for the integers library.

6 And natural numbers, something discussed in Here is an algorithm problem: You have known since childhood how to add a detail in this book. column of many-digit numbers. Certainly, you normally do this in base 10. Can you write down, as a formally correct recursion, the algorithm you learned as a child for addition of a column of base-10 whole numbers? Your algorithm should be such that, in principle, the input can be any finite list of whole numbers, and the output should print out the digits of their sum. And (now the challenging part) once you have done this, can you prove that your algorithm always gives the correct answer? Do you even know what such a question means? Here is a simple probability question: A deck of n different cards is shuffled and laid on the table by your left hand, face down.

7 An identical deck of cards, independently shuffled, is laid at your right hand, also face down. You start turning Preface ix up cards at the same rate with both hands, first the top card from both decks, then the next-to-top cards from both decks, and so on. What is the probability that We learned of this neat you will simultaneously turn up identical cards from the two decks? The answer example from Persi should depend on n. As n gets very large what happens to this probability? Does Diaconis. it converge to 0? Or to 1? Or to some number in between? And if so, what is that number? And what exactly is meant by saying that this number is the limit of the probabilities as n gets larger and larger? And how fast (in terms of n) does the nth probability approach this limiting number?

8 Our point is not that you should solve this little problem though it is fun to do and not hard but that you should be able to say with confidence that in principle you understand all the questions raised. If you cannot say that, you may need (something like) this book. We have heard students say: Only the integers, and perhaps the rational numbers, have any relevance in the world; the irrational real numbers are artificial academic constructs. Why, you can't even write down their decimal expansions. This is only true in the narrowest of senses. Against the notion that irrational numbers do not appear in real life we offer: . The diagonal of a square of side one foot has length 2 feet. The ratio of the circumference of a circle to its diameter is . The answer to our limit problem about the two decks of cards is 1 1e.

9 One encounters e also in mortgage calculations and exponential growth or decay. Besides this, irrational numbers often have to be approximated by rationals up to some specified error. How is one to do this without an understanding of the issues involved in approximation: algorithms and computation of error? There is an old joke among physicists that All series converge uniformly and absolutely everywhere. Often, a physics instructor will disregard questions of convergence. For example, all terms in a power series beyond the first or second order will be discarded on the assumption that they are too small to influence the answer significantly. This works in classical situations in which the series under discussion has been known for many years to give physically plausible answers in line with often-measured experimental data (and the instructor either knows what the convergence situation is, or knows that others have checked it carefully).

10 But your knowledge should not be so weak that you are not sure whether your series converges or converges absolutely or converges uniformly, and what the difference between these is. If any of these examples seem intriguing to you, this book was written for you. x Preface Acknowledgments This book is a development of class notes Ross Geoghegan has been using and altering for the past twenty-five years. He experienced a version of the Moore Method of learning through discovery as a graduate student, and its influence has stuck. We thank Laura Anderson, Federico Ardila, Matthew Brin, Fernando Guzm an, Eric Hayashi, Paul Loya, Marcin Mazur, David Meredith, Gene Murrow, Dennis Pixton, Wendell Ressler, Dmytro Savchuk, James T. Smith, Marco Varisco, Diane Vavrichek, and Thomas Zaslavsky who tried out variants on these notes and generously gave us much useful feedback and suggestions for further material.