Exploring Mathematics: An Engaging Introduction to Proof

Contents......Page 6
Preface......Page 9
 1.1 A Direct Approach......Page 16
 1.2 Fibonacci Numbers and the Golden Ratio......Page 18
 1.3 Inductive Reasoning......Page 21
 1.4 Natural Numbers and Divisibility......Page 24
 1.5 The Primes......Page 25
 1.6 The Integers......Page 26
 1.7 The Rationals, the Reals, and the Square Root of 2......Page 28
 1.8 End-of-Chapter Exercises......Page 30
 2.1 Truth, Tabulated......Page 40
 2.2 Valid Arguments and Direct Proofs......Page 44
 2.3 Proofs by Contradiction......Page 47
 2.4 Converse and Contrapositive......Page 49
 2.5 Quantifiers......Page 50
 2.6 Induction......Page 52
 2.7 Ubiquitous Terminology......Page 59
 2.8 The Process of Doing Mathematics......Page 60
 2.9 Writing Up Your Mathematics......Page 65
 2.10 End-of-Chapter Exercises......Page 70
 3.1 Set Builder Notation......Page 83
 3.2 Sizes and Subsets......Page 84
 3.3 Union, Intersection, Difference, and Complement......Page 86
 3.4 Many Laws and a Few Proofs......Page 88
 3.5 Indexing......Page 90
 3.6 Cartesian Product......Page 92
 3.7 Power......Page 93
 3.8 Counting Subsets......Page 96
 3.9 A Curious Set......Page 98
 3.10 End-of-Chapter Exercises......Page 100
 4.1 The Well-Ordering Principle and Criminals......Page 109
 4.2 Integer Combinations and Relatively Prime Integers......Page 111
 4.3 The Fundamental Theorem of Arithmetic......Page 113
 4.4 LCM and GCD......Page 115
 4.5 Numbers and Closure......Page 117
 4.6 End-of-Chapter Exercises......Page 121
 5.1. What is a Function?......Page 126
 5.2. Domain, Codomain, and Range......Page 129
 5.3 Injective, Surjective, and Bijective......Page 130
 5.4 Composition......Page 133
 5.5 What is a Function? Redux!......Page 135
 5.6. Inverse Functions......Page 137
 5.7. Functions and Subsets......Page 140
 5.8. A Few Facts About Functions and Subsets......Page 144
 5.9 End-of-Chapter Exercises......Page 146
 6.1 Introduction to Relations......Page 156
 6.2 Partial Orders......Page 157
 6.3 Equivalence Relations......Page 160
 6.4 Modulo m......Page 163
 6.5 Modular Arithmetic......Page 164
 6.6 Invertible Elements......Page 167
 6.7 End-of-Chapter Exercises......Page 171
 7.1 The Hilbert Hotel, Count von Count, and Cookie Monster......Page 179
 7.2 Cardinality......Page 181
 7.3 Countability......Page 183
 7.4. Key Countability Lemmas......Page 184
 7.5 Not Every Set is Countable......Page 187
 7.6 Using the Schröder-Bernstein Theorem......Page 190
 7.7. End-of-Chapter Exercises......Page 193
 8.1. Completeness......Page 199
 8.2 The Archimedean Property......Page 201
 8.3. Sequences of Real Numbers......Page 203
 8.4. Geometric Series......Page 206
 8.5 The Monotone Convergence Theorem......Page 210
 8.6. Famous Irrationals......Page 212
 8.7 End-of-Chapter Exercises......Page 218
 9.1. A Class of Lyin’ Weasels......Page 224
 9.2. Probability......Page 225
 9.3 Revisiting Combinations......Page 229
 9.4 Events and Random Variables......Page 231
 9.5 Expected Value......Page 232
 9.6 Flipped or Faked?......Page 233
 9.7 End-of-Chapter Exercises......Page 237
 10.1 An Example from Modular Arithmetic......Page 244
 10.2 The Symmetries of a Square......Page 245
 10.3 Group Theory......Page 249
 10.4 Cayley Tables......Page 251
 10.5 Group Properties......Page 253
 10.6 Isomorphism......Page 255
 10.7 Isomorphism and Group Properties......Page 256
 10.8 Examples of Isomorphic and Non-isomorphic Groups......Page 258
 10.9 End-of-Chapter Exercises......Page 261
 11.1 The Pythagorean Theorem......Page 265
 11.2 Chomp and the Divisor Game......Page 268
 11.3 Arithmetic-Geometric Mean Inequality......Page 271
 11.4 Complex Numbers and the Gaussian Integers......Page 273
 11.5 Pigeons!......Page 277
 11.6 Mirsky’s Theorem......Page 279
 11.7 Euler’s Totient Function......Page 283
 11.8 Proving the Schröder-Bernstein Theorem......Page 286
 11.9 Cauchy Sequences and the Real Numbers......Page 287
 11.10. The Cantor Set......Page 291
 11.11 Five Groups of Order 8......Page 295
Solutions, Answers, or Hints to In-Text Exercises......Page 297
Bibliography......Page 333
Index......Page 336