Everything You Always Wanted To Know About Mathematics

Description

A Guided Journey Into the World of Abstract Mathematics and the Writing of Proofs I Learning to Think Mathematically 11 1 What Is Mathematics? 13 1.1 Truths and Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.1 Triangle Tangle . . . . . . . . . . . . . . . . . . . . . . . . 14 1.1.2 Prime Time . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.1.3 Irrational Irreverence . . . . . . . . . . . . . . . . . . . . . 21 1.2 Exposition Exhibition . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.1 Simply Symbols . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.2 Write Right . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.2.3 Pick Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.2.4 Obvious Obfuscation . . . . . . . . . . . . . . . . . . . . . 37 1.3 Review, Redo, Renew . . . . . . . . . . . . . . . . . . . . . . . . 41 1.3.1 Quick Arithmetic . . . . . . . . . . . . . . . . . . . . . . . 42 1.3.2 Algebra Abracadabra . . . . . . . . . . . . . . . . . . . . 43 1.3.3 Polynomnomnomials . . . . . . . . . . . . . . . . . . . . . 49 1.3.4 Let's Talk About Sets . . . . . . . . . . . . . . . . . . . . 59 1.3.5 Notation Station . . . . . . . . . . . . . . . . . . . . . . . 60 1.4 Quizzical Puzzicles . . . . . . . . . . . . . . . . . . . . . . . . . . 61 1.4.1 Funny Money . . . . . . . . . . . . . . . . . . . . . . . . . 61 1.4.2 Gauss in the House . . . . . . . . . . . . . . . . . . . . . . 65 1.4.3 Some Other Sums . . . . . . . . . . . . . . . . . . . . . . 71 1.4.4 Friend Trends . . . . . . . . . . . . . . . . . . . . . . . . . 77 1.4.5 The Full Monty Hall . . . . . . . . . . . . . . . . . . . . . 86 1.5 It's Wise To Exercise . . . . . . . . . . . . . . . . . . . . . . . . . 92 1.6 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 2 Mathematical Induction 101 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 2.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 2.1.2 Segue from previous chapter . . . . . . . . . . . . . . . . . 102 2.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 102 2.1.4 Goals and Warnings for the Reader . . . . . . . . . . . . . 103 2.2 Examples and Discussion . . . . . . . . . . . . . . . . . . . . . . 104 2.2.1 Turning Cubes Into Bigger Cubes . . . . . . . . . . . . . 104 3 4 CONTENTS 2.2.2 Lines On The Plane . . . . . . . . . . . . . . . . . . . . . 112 2.2.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 117 2.3 Dening Induction . . . . . . . . . . . . . . . . . . . . . . . . . . 119 2.3.1 The Domino Analogy . . . . . . . . . . . . . . . . . . . . 119 2.3.2 Other Analogies . . . . . . . . . . . . . . . . . . . . . . . 125 2.3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 2.3.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 127 2.4 Two More (Dierent) Examples . . . . . . . . . . . . . . . . . . . 129 2.4.1 Dominos and Tilings . . . . . . . . . . . . . . . . . . . . . 129 2.4.2 Winning Strategies . . . . . . . . . . . . . . . . . . . . . . 133 2.4.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 137 2.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 2.5.1 Recursive Programming . . . . . . . . . . . . . . . . . . . 137 2.5.2 The Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . 139 2.5.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 143 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 2.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 144 2.8 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3 Sets 149 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.1.2 Segue from previous chapter . . . . . . . . . . . . . . . . . 150 3.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 150 3.1.4 Goals and Warnings for the Reader . . . . . . . . . . . . . 151 3.2 The Idea of a \Set" . . . . . . . . . . . . . . . . . . . . . . . . . . 151 3.3 Denition and Examples . . . . . . . . . . . . . . . . . . . . . . . 153 3.3.1 Denition of \Set" . . . . . . . . . . . . . . . . . . . . . . 153 3.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 3.3.3 How To Dene a Set . . . . . . . . . . . . . . . . . . . . . 154 3.3.4 The Empty Set . . . . . . . . . . . . . . . . . . . . . . . . 158 3.3.5 Russell's Paradox . . . . . . . . . . . . . . . . . . . . . . . 159 3.3.6 Standard Sets and Their Notation . . . . . . . . . . . . . 162 3.3.7 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 163 3.4 Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.4.1 Denition and Examples . . . . . . . . . . . . . . . . . . . 164 3.4.2 The Power Set . . . . . . . . . . . . . . . . . . . . . . . . 167 3.4.3 Set Equality . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.4.4 The \Bag" Analogy . . . . . . . . . . . . . . . . . . . . . 168 3.4.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 170 3.5 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.5.1 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.5.2 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 3.5.3 Dierence . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 3.5.4 Complement . . . . . . . . . . . . . . . . . . . . . . . . . 175 3.5.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 176 CONTENTS 5 3.6 Indexed Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 3.6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 177 3.6.2 Indexed Unions and Intersections . . . . . . . . . . . . . . 181 3.6.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 3.6.4 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 3.6.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 184 3.7 Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . . 186 3.7.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 3.7.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 3.7.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 189 3.8 Dening the Natural Numbers . . . . . . . . . . . . . . . . . . . 190 3.8.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 3.8.2 Principle of Mathematical Induction . . . . . . . . . . . . 193 3.8.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 193 3.9 Proofs Involving Sets . . . . . . . . . . . . . . . . . . . . . . . . . 194 3.9.1 Logic and Rigor: Using Denitions . . . . . . . . . . . . . 194 3.9.2 Proving \" . . . . . . . . . . . . . . . . . . . . . . . . . 195 3.9.3 Proving \=" . . . . . . . . . . . . . . . . . . . . . . . . . 198 3.9.4 Disproving Claims . . . . . . . . . . . . . . . . . . . . . . 203 3.9.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 206 3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 3.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 208 3.12 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 4 Logic 215 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 4.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 4.1.2 Segue from previous chapter . . . . . . . . . . . . . . . . . 216 4.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 216 4.1.4 Goals and Warnings for the Reader . . . . . . . . . . . . . 216 4.2 Mathematical Statements . . . . . . . . . . . . . . . . . . . . . . 217 4.2.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 4.2.2 Examples and Non-examples . . . . . . . . . . . . . . . . 219 4.2.3 Variable Propositions . . . . . . . . . . . . . . . . . . . . 221 4.2.4 Word Order Matters! . . . . . . . . . . . . . . . . . . . . . 224 4.2.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 224 4.3 Quantiers: Existential and Universal . . . . . . . . . . . . . . . 226 4.3.1 Usage and notation . . . . . . . . . . . . . . . . . . . . . . 226 4.3.2 The phrase \such that", and the order of quantiers . . . 229 4.3.3 \Fixed" Variables and Dependence . . . . . . . . . . . . . 230 4.3.4 Specifying a quantication set . . . . . . . . . . . . . . . . 232 4.3.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 233 4.4 Logical Negation of Quantied Statements . . . . . . . . . . . . . 235 4.4.1 Negation of a universal quantication . . . . . . . . . . . 235 4.4.2 Negation of an existential quantication . . . . . . . . . . 236 4.4.3 Negation of general quantied statements . . . . . . . . . 237 6 CONTENTS 4.4.4 Method Summary . . . . . . . . . . . . . . . . . . . . . . 239 4.4.5 The Law of the Excluded Middle . . . . . . . . . . . . . . 240 4.4.6 Looking Back: Indexed Set Operations and Quantiers . 241 4.4.7 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 242 4.5 Logical Connectives . . . . . . . . . . . . . . . . . . . . . . . . . 244 4.5.1 And . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 4.5.2 Or . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 4.5.3 Conditional Statements . . . . . . . . . . . . . . . . . . . 246 4.5.4 Looking Back: Set Operations and Logical Connectives . 255 4.5.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 256 4.6 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . 258 4.6.1 Denition and Uses . . . . . . . . . . . . . . . . . . . . . 259 4.6.2 Necessary and Sucient Conditions . . . . . . . . . . . . 263 4.6.3 Proving Logical Equivalences: Associative Laws . . . . . . 264 4.6.4 Proving Logical Equivalences: Distributive Laws . . . . . 268 4.6.5 Proving Logical Equivalences: De Morgan's Laws (Logic) 269 4.6.6 Using Logical Equivalences: DeMorgan's Laws (Sets) . . . 270 4.6.7 Proving Set Containments via Conditional Statements . . 271 4.6.8 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 276 4.7 Negation of Any Mathematical Statement . . . . . . . . . . . . . 278 4.7.1 Negating Conditional Statements . . . . . . . . . . . . . . 278 4.7.2 Negating Any Statement . . . . . . . . . . . . . . . . . . . 280 4.7.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 282 4.8 Truth Values and Sets . . . . . . . . . . . . . . . . . . . . . . . . 284 4.9 Writing Proofs: Strategies and Examples . . . . . . . . . . . . . . 286 4.9.1 Proving 9 Claims . . . . . . . . . . . . . . . . . . . . . . . 287 4.9.2 Proving 8 Claims . . . . . . . . . . . . . . . . . . . . . . . 291 4.9.3 Proving _ Claims . . . . . . . . . . . . . . . . . . . . . . . 293 4.9.4 Proving ^ Claims . . . . . . . . . . . . . . . . . . . . . . . 295 4.9.5 Proving =) Claims . . . . . . . . . . . . . . . . . . . . . 297 4.9.6 Proving () Claims . . . . . . . . . . . . . . . . . . . . . 304 4.9.7 Disproving Claims . . . . . . . . . . . . . . . . . . . . . . 307 4.9.8 Using assumptions in proofs . . . . . . . . . . . . . . . . . 309 4.9.9 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 311 4.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 4.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 313 4.12 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 5 Rigorous Mathematical Induction 321 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 5.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 5.2 Regular Induction . . . . . . . . . . . . . . . . . . . . . . . . . . 322 5.2.1 Theorem Statement and Proof . . . . . . . . . . . . . . . 322 5.2.2 Using Induction: Proof Template . . . . . . . . . . . . . . 324 5.2.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 5.2.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 329 CONTENTS 7 5.3 Other Variants of Induction . . . . . . . . . . . . . . . . . . . . . 331 5.3.1 Starting with a Base Case other than n = 1 . . . . . . . . 331 5.3.2 Inducting Backwards . . . . . . . . . . . . . . . . . . . . . 334 5.3.3 Inducting on the Evens/Odds . . . . . . . . . . . . . . . . 335 5.3.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 341 5.4 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 5.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 342 5.4.2 Theorem Statement and Proof . . . . . . . . . . . . . . . 343 5.4.3 Using Strong Induction: Proof Template . . . . . . . . . . 348 5.4.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 5.4.5 Comparing \Regular" and Strong Induction . . . . . . . . 355 5.4.6 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 356 5.5 Variants of Strong Induction . . . . . . . . . . . . . . . . . . . . 357 5.5.1 \Minimal Criminal" Arguments . . . . . . . . . . . . . . . 358 5.5.2 The Well-Ordering Principle of N . . . . . . . . . . . . . . 362 5.5.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 364 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 5.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 366 5.8 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 II Learning Mathematical Topics 375 6 Relations and Modular Arithmetic 377 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 6.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 6.1.2 Segue from previous chapter . . . . . . . . . . . . . . . . . 378 6.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 379 6.1.4 Goals and Warnings for the Reader . . . . . . . . . . . . . 379 6.2 Abstract (Binary) Relations . . . . . . . . . . . . . . . . . . . . . 380 6.2.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 6.2.2 Properties of Relations . . . . . . . . . . . . . . . . . . . . 383 6.2.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 6.2.4 Proving/Disproving Properties of Relations . . . . . . . . 386 6.2.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 391 6.3 Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 6.3.1 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 398 6.4 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . 399 6.4.1 Denition and Examples . . . . . . . . . . . . . . . . . . . 399 6.4.2 Equivalence Classes . . . . . . . . . . . . . . . . . . . . . 402 6.4.3 More Examples . . . . . . . . . . . . . . . . . . . . . . . . 409 6.4.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 412 6.5 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 414 6.5.1 Denition and Examples . . . . . . . . . . . . . . . . . . . 414 6.5.2 Equivalence Classes modulo n . . . . . . . . . . . . . . . . 423 6.5.3 Multiplicative Inverses . . . . . . . . . . . . . . . . . . . . 433 8 CONTENTS 6.5.4 Some Helpful Theorems . . . . . . . . . . . . . . . . . . . 447 6.5.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 455 6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 6.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 457 6.8 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 7 Functions and Cardinality 467 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 7.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 7.1.2 Segue from previous chapter . . . . . . . . . . . . . . . . . 468 7.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 469 7.1.4 Goals and Warnings for the Reader . . . . . . . . . . . . . 469 7.2 Denition and Examples . . . . . . . . . . . . . . . . . . . . . . . 469 7.2.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 7.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 7.2.3 Equality of Functions . . . . . . . . . . . . . . . . . . . . 476 7.2.4 Schematics . . . . . . . . . . . . . . . . . . . . . . . . . . 480 7.2.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 481 7.3 Images and Pre-images . . . . . . . . . . . . . . . . . . . . . . . . 482 7.3.1 Image: Denition and Examples . . . . . . . . . . . . . . 482 7.3.2 Proofs about Images . . . . . . . . . . . . . . . . . . . . . 490 7.3.3 Pre-Image: Denition and Examples . . . . . . . . . . . . 493 7.3.4 Proofs about Pre-Images . . . . . . . . . . . . . . . . . . . 495 7.3.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 496 7.4 Properties of Functions . . . . . . . . . . . . . . . . . . . . . . . 497 7.4.1 Surjective (Onto) Functions . . . . . . . . . . . . . . . . . 497 7.4.2 Injective (1-to-1) Functions . . . . . . . . . . . . . . . . . 502 7.4.3 Proof Techniques for Jections . . . . . . . . . . . . . . . . 506 7.4.4 Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 7.4.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 509 7.5 Compositions and Inverses . . . . . . . . . . . . . . . . . . . . . . 511 7.5.1 Composition of Functions . . . . . . . . . . . . . . . . . . 511 7.5.2 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 7.5.3 Bijective () Invertible . . . . . . . . . . . . . . . . . . . 519 7.5.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 521 7.6 Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522 7.6.1 Motivation and Denition . . . . . . . . . . . . . . . . . . 522 7.6.2 Finite Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 528 7.6.3 Countably Innite Sets . . . . . . . . . . . . . . . . . . . 530 7.6.4 Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . 549 7.6.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 555 7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 7.8 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 558 7.9 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566 CONTENTS 9 8 Combinatorics 567 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 8.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 8.1.2 Segue from previous chapter . . . . . . . . . . . . . . . . . 568 8.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 568 8.1.4 Goals and Warnings for the Reader . . . . . . . . . . . . . 569 8.2 Basic Counting Principles . . . . . . . . . . . . . . . . . . . . . . 570 8.2.1 The Rule of Sum . . . . . . . . . . . . . . . . . . . . . . . 570 8.2.2 The Rule of Product . . . . . . . . . . . . . . . . . . . . . 574 8.2.3 Fundamental Counting Objects and Formulas . . . . . . . 580 8.2.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 588 8.3 Counting Arguments . . . . . . . . . . . . . . . . . . . . . . . . . 589 8.3.1 Poker Hands . . . . . . . . . . . . . . . . . . . . . . . . . 589 8.3.2 Other Card-Counting Examples . . . . . . . . . . . . . . . 595 8.3.3 Other Counting Objects . . . . . . . . . . . . . . . . . . . 604 8.3.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 620 8.4 Counting in Two Ways . . . . . . . . . . . . . . . . . . . . . . . . 623 8.4.1 Method Summary . . . . . . . . . . . . . . . . . . . . . . 623 8.4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 8.4.3 Standard Counting Objects . . . . . . . . . . . . . . . . . 634 8.4.4 Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . 639 8.4.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 641 8.5 Selections with Repetition . . . . . . . . . . . . . . . . . . . . . . 643 8.5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 643 8.5.2 Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644 8.5.3 Equivalent Forms . . . . . . . . . . . . . . . . . . . . . . . 645 8.5.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 8.5.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 651 8.6 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . 652 8.6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 652 8.6.2 Statement and Proof . . . . . . . . . . . . . . . . . . . . . 653 8.6.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 654 8.6.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 656 8.7 Inclusion/Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 657 8.7.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 657 8.7.2 Statement and Proof . . . . . . . . . . . . . . . . . . . . . 658 8.7.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 659 8.7.4 Questions & Exercises . . . . . . . . . . . . . . . . . . . . 662 8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662 8.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 663 8.10 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669 10 CONTENTS A Denitions and Theorems 671 A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 A.1.1 Standard Sets . . . . . . . . . . . . . . . . . . . . . . . . . 671 A.1.2 Set-Builder Notation . . . . . . . . . . . . . . . . . . . . . 671 A.1.3 Elements and Subsets . . . . . . . . . . . . . . . . . . . . 672 A.1.4 Power Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 672 A.1.5 Set Equality . . . . . . . . . . . . . . . . . . . . . . . . . . 673 A.1.6 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . 673 A.1.7 Indexed Set Operations . . . . . . . . . . . . . . . . . . . 674 A.1.8 Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . 674 A.2 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675 A.2.1 Statements and Propositions . . . . . . . . . . . . . . . . 675 A.2.2 Quantiers . . . . . . . . . . . . . . . . . . . . . . . . . . 675 A.2.3 Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . 676 A.2.4 Logical Negation . . . . . . . . . . . . . . . . . . . . . . . 677 A.2.5 Proof Strategies . . . . . . . . . . . . . . . . . . . . . . . 678 A.3 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680 A.3.1 Principle of Specic Mathematical Induction . . . . . . . 680 A.3.2 Principle of Strong Mathematical Induction . . . . . . . . 680 A.3.3 \Minimal Criminal" Argument . . . . . . . . . . . . . . . 681 A.4 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682 A.4.1 Properties of Relations . . . . . . . . . . . . . . . . . . . . 682 A.4.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . 682 A.4.3 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . 684 A.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686 A.5.1 Images and Pre-Images . . . . . . . . . . . . . . . . . . . 686 A.5.2 Jections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687 A.5.3 Composition of Functions . . . . . . . . . . . . . . . . . . 687 A.5.4 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688 A.5.5 Proof Techniques for Functions . . . . . . . . . . . . . . . 688 A.6 Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692 A.6.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . 692 A.6.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692 A.6.3 Standard Catalog of Cardinalities . . . . . . . . . . . . . . 694 A.7 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695 A.7.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . 695 A.7.2 Counting Principles . . . . . . . . . . . . . . . . . . . . . 695 A.7.3 Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . 695 A.7.4 Standard Counting Objects . . . . . . . . . . . . . . . . . 696 A.7.5 Counting In Two Ways . . . . . . . . . . . . . . . . . . . 696 A.7.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696 A.7.7 Inclusion/Exclusion . . . . . . . . . . . . . . . . . . . . . 697 A.7.8 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . 697 A.8 Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698 A.8.1 General Phrases . . . . . . . . . . . . . . . . . . . . . . . 698 A.8.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . 698