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