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.

2 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. (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.

3 (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. In so far as possible we try to work in the formal methods indirectly, as we take the reader through some interesting Mathematics .

4 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.

5 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.

6 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. 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.

7 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.

8 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?

9 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. 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?

10 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? 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.