Proof and the Art of Mathematics

by Joel David Hamkins

Overview

An introduction to writing proofs, presented through compelling mathematical statements with interesting elementary proofs.

This book offers an introduction to the art and craft of proof-writing. The author, a leading research mathematician, presents a series of engaging and compelling mathematical statements with interesting elementary proofs. These proofs capture a wide range of topics, including number theory, combinatorics, graph theory, the theory of games, geometry, infinity, order theory, and real analysis. The goal is to show students and aspiring mathematicians how to write proofs with elegance and precision.

Product Details

ISBN-13:	9780262360937
Publisher:	MIT Press
Publication date:	09/29/2020
Sold by:	Penguin Random House Publisher Services
Format:	eBook
Pages:	240
File size:	22 MB
Note:	This product may take a few minutes to download.

About the Author

Joel David Hamkins is Professor of Logic at Oxford University and Sir Peter Strawson Fellow in Philosophy at University College, Oxford. The author of Proof and the Art of Mathematics (MIT Press), he is the creator of the popular blog Mathematics and Philosophy of the Infinite. He is a prominent contributor to MathOverflow, where he has posted more than 1,000 mathematical arguments.

Table of Contents

Preface xiii

A Note to the Instructor xvii

A Note to the Student xxi

About the Author xxv

1 A Classical Beginning 1

1.1 The number √2 is irrational 2

1.2 Lowest terms 4

1.3 A geometric proof 5

1.4 Generalizations to other roots 6

Mathematical Habits 7

Exercises 8

2 Multiple Proofs 9

2.1 n²-n is even 10

2.2 One theorem, seven proofs 10

2.3 Different proofs suggest different generalizations 12

Mathematical Habits 13

Exercises 14

Credits 14

3 Number Theory 15

3.1 Prime numbers 15

3.2 The fundamental theorem of arithmetic 16

3.3 Euclidean division algorithm 19

3.4 Fundamental theorem of arithmetic, uniqueness 21

3.5 Infinitely many primes 21

Mathematical Habits 24

Exercises 25

4 Mathematical Induction 27

4.1 The least-number principle 27

4.2 Common induction 28

4.3 Several proofs using induction 29

4.4 Proving the induction principle 32

4.5 Strong induction 33

4.6 Buckets of Fish via nested induction 34

4.7 Every number is interesting 37

Mathematical Habits 37

Exercises 38

Credits 39

5 Discrete Mathematics 41

5.1 More pointed at than pointing 41

5.2 Chocolate bar problem 43

5.3 Tiling problems 44

5.4 Escape! 47

5.5 Representing integers as a sum 49

5.6 Permutations and combinations 50

5.7 The pigeon-hole principle 52

5.8 The zigzag theorem 53

Mathematical Habits 55

Exercises 55

Credits 56

6 Proofs without Words 57

6.1 A geometric sum 57

6.2 Binomial square 58

6.3 Criticism of the "without words" aspect 58

6.4 Triangular choices 59

6.5 Further identities 60

6.6 Sum of odd numbers 60

6.7 A Fibonacci identity 61

6.8 A sum of cubes 61

6.9 Another infinite series 62

6.10 Area of a circle 62

6.11 Tiling with dominoes 63

6.12 How to lie with pictures 66

Mathematical Habits 68

Exercises 69

Credits 70

7 Theory of Games 71

7.1 Twenty-One 71

7.2 Buckets of Fish 73

7.3 The game of Nim 74

7.4 The Gold Coin game 79

7.5 Chomp 81

7.6 Games of perfect information 83

7.7 The fundamental theorem of finite games 85

Mathematical Habits 89

Exercises 89

Credits 90

8 Pick's Theorem 91

8.1 Figures in the integer lattice 91

8.2 Pick's theorem for rectangles 92

8.3 Pick's theorem for triangles 93

8.4 Amalgamation 95

8.5 Triangulations 97

8.6 Proof of Pick's theorem, general case 98

Mathematical Habits 98

Exercises 99

Credits 100

9 Lattice-Point Polygons 101

9.1 Regular polygons in the integer lattice 101

9.2 Hexagonal and triangular lattices 104

9.3 Generalizing to arbitrary lattices 106

Mathematical Habits 107

Exercises 108

Credits 110

10 Polygonal Dissection Congruence Theorem 111

10.1 The polygonal dissection congruence theorem 111

10.2 Triangles to parallelograms 112

10.3 Parallelograms to rectangles 113

10.4 Rectangles to squares 113

10.5 Combining squares 114

10.6 Full proof of the dissection congruence theorem 115

10.7 Scissors congruence 115

Mathematical Habits 117

Exercises 118

Credits 119

11 Functions and Relations 121

11.1 Relations 121

11.2 Equivalence relations 122

11.3 Equivalence classes and partitions 125

11.4 Closures of a relation 127

11.5 Functions 128

Mathematical Habits 129

Exercises 130

12 Graph Theory 133

12.1 The bridges of Konigsberg 133

12.2 Circuits and paths in a graph 134

12.3 The five-room puzzle 137

12.4 The Euler characteristic 138

Mathematical Habits 139

Exercises 140

Credits 142

13 Infinity 143

13.1 Hilbert's Grand Hotel 143

Hubert's bus 144

Hilbert's train 144

Hilbert's half marathon 145

Cantor's cruise ship 146

13.2 Countability 146

13.3 Uncountability of the real numbers 150

Alternative proof of Cantor's theorem 152

Cranks 153

13.4 Transcendental numbers 154

13.5 Equinumerosity 156

13.6 The Shröder-Cantor-Bernstein theorem 157

13.7 The real plane and real line are equinumerous 159

Mathematical Habits 160

Exercises 160

Credits 161

14 Order Theory 163

14.1 Partial orders 163

14.2 Minimal versus least elements 164

14.3 Linear orders 166

14.4 Isomorphisms of orders 167

14.5 The rational line is universal 168

14.6 The eventual domination order 170

Mathematical Habits 171

Exercises 171

15 Real Analysis 173

15.1 Definition of continuity 173

15.2 Sums and products of continuous functions 175

15.3 Continuous at exactly one point 177

15.4 The least-upper-bound principle 178

15.5 The intermediate-value theorem 178

15.6 The Heine-Borel theorem 179

15.7 The Bolzano-Weierstrass theorem 181

15.8 The principle of continuous induction 182

Mathematical Habits 185

Exercises 185

Credits 187

Answers to Selected Exercises 189

Bibliography 199

Index of Mathematical Habits 201

Notation Index 203

Subject Index 205