Building Proofs: A Practical Guide

The book is divided into five chapters. Chapter one is entitled “Getting Started” and includes examples of standard types of proofs with comments on the difference between definitions and axioms, variable choices, mathematical notation and the purpose of pictures. The chapter opens with a proof that the square root of two is irrational, using italicized comments as a guide in between each proof line. This chapter is aimed at a student who is just learning to write proofs. The tone is conversational and, for the most part, the definitions and proofs deal with topics with which a student who has taken the Calculus sequence and a linear algebra course will be familiar. Each section also contains an example or two to illustrate the authors’ point. The only complaint I have is that proof by contraposition and proof by contradiction are considered the same technique.

In chapter two the authors give a summary of the major topics found in most discrete math textbooks. This is the chapter in which you begin to feel the computer science bent of the text — nearly half the chapter is spent on logic, from propositional calculus through rules of inference. The chapter concludes with several pages on algorithms and how to prove them. In the middle, sets and functions are discussed briefly (about a page each) followed by sums and induction. With the exception of the induction section, there are fewer examples in this chapter. A student who had not taken a discrete mathematics or introduction to proof course would need other resources to elucidate the ideas. A particularly nice example of induction is given, involving Egyptian fractions, that I have not seen in any other text.

A significant shift in the level of difficulty happens in chapter three; most of the proofs require a decent level of mathematical maturity to understand, especially with the minimal context given. Theorems are proved in a variety of different areas, including the Cauchy-Schwartz inequality, results on convex functions, the division algorithm, the fundamental theorem of arithmetic, Lagrange’s Theorem (although it is not labeled as such), a theorem about Eulerian paths and cycles, and results on convergence of infinite sums. A gem in this chapter is an example given in the “Calculate the same thing in two different ways” section in which the improper integral \(\int_{-\infty}^{\infty}e^{-x^2}dx\) is computed.

Chapter four is entitled “More Advanced Proof Making,” but while some of the topics are advanced (Russell paradox, Gӧdel’s incompleteness theorem, duality and Hӧlder inequalities), I would consider the proof building techniques as more straightforward ones that would warrant being seen earlier in the text. These techniques include using conjectures and counterexamples to precisely word theorems, “bootstrapping” by showing a result holds in simpler cases to build up to a general case, and asking natural questions to prove lemmas that guide us to more general results.

Chapter five is the shortest chapter at only six pages (not including the exercises) but this is the one I found the most interesting and helpful. In this chapter the authors briefly discuss the ways in which mathematicians build theories and do research, touching on the importance of definitions, generalizing concepts, the relationships between different areas of mathematics, and asking good questions. Full proofs are not given, but many examples for further study are mentioned.

Every chapter concludes with a set of exercises covering the majority of the topics mentioned in that chapter. Some hints are given and the level of the exercises ranges from fairly straightforward to very advanced.

In the preface the authors describe this book as a “guide” in the art of proof writing that the reader should “keep around and pull out when trying to puzzle out a new proof.” I could see this as a book used for both a freshman seminar and a senior level capstone course. In the former, the first chapter could be used to introduce the idea of proof and the last chapter could motivate mathematics research and provide topics for further study. In the latter, students could use the book as a reference or exercises could be assigned from each chapter. I would also recommend this book to a senior math major planning on attending graduate school as a reference or for summer reading.

Erin E. Bancroft (eebancroft@gcc.edu) is an assistant professor at Grove City College in Grove City, Pennsylvania.