How to prove it. A structured approach. (English) Zbl 0816.00004

Cambridge: Univ. Press. ix, 309 p. £ 14.95; $ 19.95 /sc; £ 30.00; $ 49.95 /hc (1994).
The author of this book is right that many students have problems with writing down proofs of even simple theorems, such as “if \(V \subseteq W\), then \(V \cap W = V\)”. According to the author, many of the considerations that have led computer scientists to embrace the structured approach to programming apply to proof-writing as well.
Since the choice of proof structure is guided by the logical form of the statement being proven, the book begins with sentential logic in chapter 1 and quantificational logic in chapter 2. Chapter 3 covers structured proving techniques in a systematic way. Chapters 4 and 5 treat relations and functions, respectively. These chapters not only introduce fundamental concepts, but also provide material for the students to practice the proof-writing techniques from chapter 3. Chapter 6 is on mathematical induction. Finally, chapter 7 studies infinite sets and hence gives a number of interesting theorems to be proved.
In his introduction, the author starts with looking at the numbers \(n\) and \(2^ n - 1\) for \(n = 1, \dots, 10\). This results in two conjectures.
Conjecture 1: If \(n\) is an integer larger than 1 and \(n\) is prime, then \(2^ n - 1\) is prime.
Conjecture 2: If \(n\) is larger than 1 and \(n\) is not prime, then \(2^ n - 1\) is prime.
By considering \(n = 11\) one finds out that conjecture 1 is incorrect. Checking more and more natural numbers, our confidence in conjecture 2 increases. But the only way to be sure that conjecture 2 is correct is to prove it.
Since Euclid proved (constructively) that there are infinitely many prime numbers, the question arises whether there are infinitely many prime numbers of the form \(2^ n - 1\) (with \(n\) prime). The author mentions that this question is still an open problem.
I consider chapter 3, called “Proofs”, as the main chapter of the book. Figuring out a proof is compared with solving jigsaw puzzles. There is no algorithm for solving these problems, but some strategies work better than others. The author presents the proof strategies related to the logical connectives and the quantifiers. These strategies are illustrated for theorems about numbers and sets and also examples of incorrect proofs are given.
Chapter 6 on mathematical induction contains many interesting proofs that illustrate the wide range of uses of induction. For instance, the following theorems are shown.
Example 6.2.1. If \(R\) is a partial order on a set \(A\), then every finite, non-empty set \(B \subseteq A\) has an \(R\)-minimal element.
Example 6.2.2. If \(A\) is a finite set and \(R\) is a partial order on \(A\), then there is a total order \(T\) on \(A\) such that \(R \subseteq T\).
Example 6.2.3. For all \(n\geq 3\), if \(n\) distinct points on a circle are connected in consecutive order with straight lines, then the interior angles of the resulting polygon add up to \((n - 2)180^ \circ\).
Example 6.2.4. For any positive integer \(n\), a \(2^ n \times 2^ n\) square grid with any one square removed can be covered with \(L\)-shaped tiles.
The book teaches the student how to find proofs, how to write them down and how to read them. At the same time, it reveals the beauty of mathematics by giving proofs of many interesting, quite natural and nonartificial conjectures (about numbers, for instance).


00A35 Methodology of mathematics
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
00-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematics in general