How to Prove It: A Structured Approach

Citation

Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press.

Chapter Summary

The third edition has an introduction, eight chapters and about 450 pages of text, followed by solutions to selected exercises (some fifty pages), suggestions for further reading and a one-page summary of proof techniques. The book first appeared in 1994, with a second edition in 2006. Its organising idea, set out in the preface, is "structured proving": just as structured programs are built by nesting a few basic constructs, proofs are built by nesting a few basic structures, and the logical form of the statement to be proved tells the reader which structure to use.

Introduction

A taste of proofs before any theory. Working with prime numbers and numbers of the form 2ⁿ − 1, the introduction shows how a pattern in a table becomes a conjecture, how a single counterexample refutes one conjecture, and how a proof settles another. It also presents Euclid's proof that there are infinitely many primes, and promises to return to these proofs after Chapter 3 to analyse how they were constructed.

Chapter 1: Sentential Logic

Deductive reasoning and the logical connectives, truth tables, and the conditional and biconditional. Variables, sets and the operations on sets are introduced in the same chapter, both because set theory is used throughout the book and because it illustrates the logic.

Chapter 2: Quantificational Logic

Quantifiers, equivalences involving quantifiers (such as how negation passes through "for all" and "there exists"), and a section on more operations on sets.

Chapter 3: Proofs

The heart of the book. The chapter runs through the forms a statement can take and the proof structure suited to each: proof strategies in general, then proofs involving negations and conditionals, quantifiers, conjunctions and biconditionals, and disjunctions, followed by existence and uniqueness proofs and a section of further examples. The preface warns that early examples are chosen for the structures they illustrate, not their content, and are therefore rather trivial; the proofs grow more interesting as more techniques become available.

Chapter 4: Relations

Ordered pairs and Cartesian products, relations and their properties, ordering relations and equivalence relations. The preface explains that Chapters 4 and 5 serve both as material on which to practise the techniques of Chapter 3 and as an introduction to concepts used across mathematics.

Chapter 5: Functions

Functions, one-to-one and onto functions, inverses, and closures of sets under functions (a section new to this edition), ending with a short section titled as a research project on images and inverse images.

Chapter 6: Mathematical Induction

Proof by induction, more examples, recursion, strong induction, and a return to closures. The presentation builds on Chapter 3, which the preface expects the reader to have mastered by this point.

Chapter 7: Number Theory

New in the third edition: greatest common divisors, prime factorization, modular arithmetic, Euler's theorem and public-key cryptography. With Chapter 8, it is meant to give more practice with proofs and a first look at what more advanced mathematics is like.

Chapter 8: Infinite Sets

Equinumerous sets, countable and uncountable sets, and the Cantor–Schröder–Bernstein theorem.

Key Concepts

Chapters 1–2: Logic and sets

• Logical form: the structure of a statement in terms of connectives and quantifiers, which determines how it can be proved.
• Truth tables and logical equivalence: a way of checking when two statements always have the same truth value.
• Quantifiers: "for all" and "there exists", and the rules for negating and combining them.
• Set operations: union, intersection, difference and the like, defined through the logical connectives and quantifiers.

Chapter 3: Proofs

• Proof structures: patterns such as supposing P until Q is reached (for "if P then Q") or letting x be arbitrary (for "for all x"), nested to prove complex statements.
• Negations and disjunctions: statements whose proofs, or whose use as hypotheses, call for their own strategies, treated in separate sections.
• Existence and uniqueness: proving that exactly one object has a property.

Chapters 4–6: Relations, functions and induction

• Equivalence relations and partial orders: relations that classify objects or arrange them in order.
• One-to-one and onto functions: injective and surjective functions, and the inverses they allow.
• Closures: the smallest set containing given elements and closed under a function.
• Induction and recursion: proving statements about all natural numbers and defining sequences step by step, including strong induction.

Chapters 7–8: Number theory and infinite sets

• Modular arithmetic and Euler's theorem: arithmetic of remainders, the basis of public-key cryptography.
• Countable and uncountable sets: comparing the sizes of infinite sets through one-to-one correspondences.
• Cantor–Schröder–Bernstein theorem: two injections in opposite directions guarantee that two sets have the same size.

Critical Analysis

Strengths

• A method, not only examples. The book's central claim is that a proof's structure follows from the logical form of what is being proved. By teaching logic first and then, in Chapter 3, going systematically through each form and the structure it calls for, it gives beginners a way to start a proof instead of waiting for inspiration. The one-page summary of proof techniques collects the method in one place.
• Ordinary proofs as the goal. The preface stresses that the indented outlines used to display structure are a teaching device; the aim is proofs written in paragraphs as mathematicians write them.
• Plenty of exercises with partial solutions. Every section ends with exercises; the third edition added more than 150, and starred ones have solutions or hints in an appendix of about fifty pages, which makes the book usable for self-study.
• Free software companions. Exercises marked PD can be done with the author's free Proof Designer, and the author has since published How To Prove It with Lean, a free online companion whose sections match this book and teach the same techniques in the Lean proof assistant.

Limitations

• A slow start by design. The preface concedes that the early proofs in Chapter 3 are rather trivial, since they are chosen to show structure. Readers who already write simple proofs may find the first half deliberate.
• Long for its scope. Over 400 pages go to logic, sets, relations, functions, induction and short chapters on number theory and infinite sets. Topics such as real numbers, limits or combinatorial counting, found in some other transition books, are not covered.
• Logic as a tool, not a subject. The logic in Chapters 1–2 is informal and serves proof writing; formal systems, soundness and completeness are left to books on mathematical logic.

Where It Fits in the Course

This is a natural first book for the course, read before the books on mathematical logic. Richard Hammack's Book of Proof, freely available, covers similar ground (sets, logic, the standard proof methods, relations, functions and cardinality) and can be used as an alternative or as a second source of exercises; Velleman's distinctive contribution is the systematic link between logical form and proof structure in Chapter 3. Peter Eccles's An Introduction to Mathematical Reasoning, R. B. J. T. Allenby's Numbers and Proofs and Martin Liebeck's A Concise Introduction to Pure Mathematics are further introductions to proof that place more weight on number systems and other pure mathematics, and suit readers who want more mathematical content alongside the method.

After Velleman, the course moves to logic as a subject in its own right. Leary and Kristiansen's A Friendly Introduction to Mathematical Logic develops first-order logic, completeness and Gödel's incompleteness theorems; Herbert Enderton's A Mathematical Introduction to Logic is a more rigorous treatment of propositional and first-order logic for students already at ease with mathematical reasoning. Chapters 1–3 here are good preparation for both.

How to Use This Book

The book is for students meeting proofs seriously for the first time, in mathematics or computer science, typically in the first or second year; secondary-school algebra is enough. It also suits self-learners, thanks to the solutions to starred exercises.

A reading plan:

• Core: the Introduction, Chapters 1–3 and Chapter 6. Do not rush Chapter 3; it is the method the rest of the book applies, and its final section returns to the introduction's proofs to show how they were built.
• Practice and vocabulary: Chapters 4 and 5, which supply the relations and functions that later courses assume.
• Choose one or both: Chapter 7 (number theory, ending with public-key cryptography) or Chapter 8 (infinite sets), depending on interest. Chapter 8 links naturally to the cardinality topics in courses on analysis and set theory.

Work exercises in every section, starting with the starred ones so you can check answers in the appendix; before writing a proof, write down the logical form of what you are given and what you must prove, as Chapter 3 teaches, and keep the summary of proof techniques at hand. For immediate feedback, try the PD exercises in Proof Designer, or work through the matching sections of the free How To Prove It with Lean once Chapter 3 has begun.