Everything You Always Wanted To Know About Mathematics
Everything You Always Wanted ToKnow About Mathematics*(*But didn’t even know to ask)A Guided Journey Into the World of AbstractMathematics and the Writing of ProofsBrendan W. Sullivanbwsulliv@andrew.cmu.eduwith Professor John MackeyDepartment of Mathematical SciencesCarnegie Mellon UniversityPittsburgh, PAMay 10, 2013This work is submitted in partial fulfillment of the requirements for the degreeof Doctor of Arts in Mathematical Sciences.
2
ContentsILearning to Think Mathematically1 What Is Mathematics?1.1 Truths and Proofs . . . . . .1.1.1 Triangle Tangle . . . .1.1.2 Prime Time . . . . . .1.1.3 Irrational Irreverence .1.2 Exposition Exhibition . . . .1.2.1 Simply Symbols . . .1.2.2 Write Right . . . . . .1.2.3 Pick Logic . . . . . . .1.2.4 Obvious Obfuscation .1.3 Review, Redo, Renew . . . .1.3.1 Quick Arithmetic . . .1.3.2 Algebra Abracadabra1.3.3 Polynomnomnomials .1.3.4 Let’s Talk About Sets1.3.5 Notation Station . . .1.4 Quizzical Puzzicles . . . . . .1.4.1 Funny Money . . . . .1.4.2 Gauss in the House . .1.4.3 Some Other Sums . .1.4.4 Friend Trends . . . . .1.4.5 The Full Monty Hall .1.5 It’s Wise To Exercise . . . . .1.6 Lookahead . . . . . . . . . . 982 Mathematical Induction2.1 Introduction . . . . . . . . . . . . . . . . . .2.1.1 Objectives . . . . . . . . . . . . . . .2.1.2 Segue from previous chapter . . . . .2.1.3 Motivation . . . . . . . . . . . . . .2.1.4 Goals and Warnings for the Reader .2.2 Examples and Discussion . . . . . . . . . .2.2.1 Turning Cubes Into Bigger Cubes .101101101102102103104104.3.
391431441441483 Sets3.1 Introduction . . . . . . . . . . . . . . . . . .3.1.1 Objectives . . . . . . . . . . . . . . .3.1.2 Segue from previous chapter . . . . .3.1.3 Motivation . . . . . . . . . . . . . .3.1.4 Goals and Warnings for the Reader .3.2 The Idea of a “Set” . . . . . . . . . . . . . .3.3 Definition and Examples . . . . . . . . . . .3.3.1 Definition of “Set” . . . . . . . . . .3.3.2 Examples . . . . . . . . . . . . . . .3.3.3 How To Define a Set . . . . . . . . .3.3.4 The Empty Set . . . . . . . . . . . .3.3.5 Russell’s Paradox . . . . . . . . . . .3.3.6 Standard Sets and Their Notation .3.3.7 Questions & Exercises . . . . . . . .3.4 Subsets . . . . . . . . . . . . . . . . . . . .3.4.1 Definition and Examples . . . . . . .3.4.2 The Power Set . . . . . . . . . . . .3.4.3 Set Equality . . . . . . . . . . . . . .3.4.4 The “Bag” Analogy . . . . . . . . .3.4.5 Questions & Exercises . . . . . . . .3.5 Set Operations . . . . . . . . . . . . . . . .3.5.1 Intersection . . . . . . . . . . . . . .3.5.2 Union . . . . . . . . . . . . . . . . .3.5.3 Difference . . . . . . . . . . . . . . .3.5.4 Complement . . . . . . . . . . . . .3.5.5 Questions & Exercises . . . . . . . 2.2.2 Lines On The Plane . .2.2.3 Questions & Exercises .Defining Induction . . . . . . .2.3.1 The Domino Analogy .2.3.2 Other Analogies . . . .2.3.3 Summary . . . . . . . .2.3.4 Questions & Exercises .Two More (Different) Examples2.4.1 Dominos and Tilings . .2.4.2 Winning Strategies . . .2.4.3 Questions & Exercises .Applications . . . . . . . . . . .2.5.1 Recursive Programming2.5.2 The Tower of Hanoi . .2.5.3 Questions & Exercises .Summary . . . . . . . . . . . .Chapter Exercises . . . . . . .Lookahead . . . . . . . . . . . .
5CONTENTS3.6Indexed Sets . . . . . . . . . . . . . . . . .3.6.1 Motivation . . . . . . . . . . . . . .3.6.2 Indexed Unions and Intersections . .3.6.3 Examples . . . . . . . . . . . . . . .3.6.4 Partitions . . . . . . . . . . . . . . .3.6.5 Questions & Exercises . . . . . . . .3.7 Cartesian Products . . . . . . . . . . . . . .3.7.1 Definition . . . . . . . . . . . . . . .3.7.2 Examples . . . . . . . . . . . . . . .3.7.3 Questions & Exercises . . . . . . . .3.8 Defining the Natural Numbers . . . . . . .3.8.1 Definition . . . . . . . . . . . . . . .3.8.2 Principle of Mathematical Induction3.8.3 Questions & Exercises . . . . . . . .3.9 Proofs Involving Sets . . . . . . . . . . . . .3.9.1 Logic and Rigor: Using Definitions .3.9.2 Proving “ ” . . . . . . . . . . . . .3.9.3 Proving “ ” . . . . . . . . . . . . .3.9.4 Disproving Claims . . . . . . . . . .3.9.5 Questions & Exercises . . . . . . . .3.10 Summary . . . . . . . . . . . . . . . . . . .3.11 Chapter Exercises . . . . . . . . . . . . . .3.12 Lookahead . . . . . . . . . . . . . . . . . . 951982032062072082134 Logic4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . .4.1.2 Segue from previous chapter . . . . . . . . . . . . . .4.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . .4.1.4 Goals and Warnings for the Reader . . . . . . . . . .4.2 Mathematical Statements . . . . . . . . . . . . . . . . . . .4.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . .4.2.2 Examples and Non-examples . . . . . . . . . . . . .4.2.3 Variable Propositions . . . . . . . . . . . . . . . . .4.2.4 Word Order Matters! . . . . . . . . . . . . . . . . . .4.2.5 Questions & Exercises . . . . . . . . . . . . . . . . .4.3 Quantifiers: Existential and Universal . . . . . . . . . . . .4.3.1 Usage and notation . . . . . . . . . . . . . . . . . . .4.3.2 The phrase “such that”, and the order of quantifiers4.3.3 “Fixed” Variables and Dependence . . . . . . . . . .4.3.4 Specifying a quantification set . . . . . . . . . . . . .4.3.5 Questions & Exercises . . . . . . . . . . . . . . . . .4.4 Logical Negation of Quantified Statements . . . . . . . . . .4.4.1 Negation of a universal quantification . . . . . . . .4.4.2 Negation of an existential quantification . . . . . . .4.4.3 Negation of general quantified statements . . . . . 32233235235236237
6CONTENTS4.4.4 Method Summary . . . . . . . . . . . . . . . . . . . . . .4.4.5 The Law of the Excluded Middle . . . . . . . . . . . . . .4.4.6 Looking Back: Indexed Set Operations and Quantifiers .4.4.7 Questions & Exercises . . . . . . . . . . . . . . . . . . . .4.5 Logical Connectives . . . . . . . . . . . . . . . . . . . . . . . . .4.5.1 And . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.5.2 Or . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.5.3 Conditional Statements . . . . . . . . . . . . . . . . . . .4.5.4 Looking Back: Set Operations and Logical Connectives .4.5.5 Questions & Exercises . . . . . . . . . . . . . . . . . . . .4.6 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . .4.6.1 Definition and Uses . . . . . . . . . . . . . . . . . . . . .4.6.2 Necessary and Sufficient Conditions . . . . . . . . . . . .4.6.3 Proving Logical Equivalences: Associative Laws . . . . . .4.6.4 Proving Logical Equivalences: Distributive Laws . . . . .4.6.5 Proving Logical Equivalences: De Morgan’s Laws (Logic)4.6.6 Using Logical Equivalences: DeMorgan’s Laws (Sets) . . .4.6.7 Proving Set Containments via Conditional Statements . .4.6.8 Questions & Exercises . . . . . . . . . . . . . . . . . . . .4.7 Negation of Any Mathematical Statement . . . . . . . . . . . . .4.7.1 Negating Conditional Statements . . . . . . . . . . . . . .4.7.2 Negating Any Statement . . . . . . . . . . . . . . . . . . .4.7.3 Questions & Exercises . . . . . . . . . . . . . . . . . . . .4.8 Truth Values and Sets . . . . . . . . . . . . . . . . . . . . . . . .4.9 Writing Proofs: Strategies and Examples . . . . . . . . . . . . . .4.9.1 Proving Claims . . . . . . . . . . . . . . . . . . . . . . .4.9.2 Proving Claims . . . . . . . . . . . . . . . . . . . . . . .4.9.3 Proving Claims . . . . . . . . . . . . . . . . . . . . . . .4.9.4 Proving Claims . . . . . . . . . . . . . . . . . . . . . . .4.9.5 Proving Claims . . . . . . . . . . . . . . . . . . . . .4.9.6 Proving Claims . . . . . . . . . . . . . . . . . . . . .4.9.7 Disproving Claims . . . . . . . . . . . . . . . . . . . . . .4.9.8 Using assumptions in proofs . . . . . . . . . . . . . . . . .4.9.9 Questions & Exercises . . . . . . . . . . . . . . . . . . . .4.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . . . . . . . .4.12 Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 Rigorous Mathematical Induction5.1 Introduction . . . . . . . . . . . . . . . .5.1.1 Objectives . . . . . . . . . . . . .5.2 Regular Induction . . . . . . . . . . . .5.2.1 Theorem Statement and Proof .5.2.2 Using Induction: Proof Template5.2.3 Examples . . . . . . . . . . . . .5.2.4 Questions & Exercises . . . . . 311312313319321321321322322324327329
7CONTENTS5.35.45.55.65.75.8IIOther Variants of Induction . . . . . . . . . . . . .5.3.1 Starting with a Base Case other than n 15.3.2 Inducting Backwards . . . . . . . . . . . . .5.3.3 Inducting on the Evens/Odds . . . . . . . .5.3.4 Questions & Exercises . . . . . . . . . . . .Strong Induction . . . . . . . . . . . . . . . . . . .5.4.1 Motivation . . . . . . . . . . . . . . . . . .5.4.2 Theorem Statement and Proof . . . . . . .5.4.3 Using Strong Induction: Proof Template . .5.4.4 Examples . . . . . . . . . . . . . . . . . . .5.4.5 Comparing “Regular” and Strong Induction5.4.6 Questions & Exercises . . . . . . . . . . . .Variants of Strong Induction . . . . . . . . . . . .5.5.1 “Minimal Criminal” Arguments . . . . . . .5.5.2 The Well-Ordering Principle of N . . . . . .5.5.3 Questions & Exercises . . . . . . . . . . . .Summary . . . . . . . . . . . . . . . . . . . . . . .Chapter Exercises . . . . . . . . . . . . . . . . . .Lookahead . . . . . . . . . . . . . . . . . . . . . . .Learning Mathematical Topics6 Relations and Modular Arithmetic6.1 Introduction . . . . . . . . . . . . . . . . . . . . . .6.1.1 Objectives . . . . . . . . . . . . . . . . . . .6.1.2 Segue from previous chapter . . . . . . . . .6.1.3 Motivation . . . . . . . . . . . . . . . . . .6.1.4 Goals and Warnings for the Reader . . . . .6.2 Abstract (Binary) Relations . . . . . . . . . . . . .6.2.1 Definition . . . . . . . . . . . . . . . . . . .6.2.2 Properties of Relations . . . . . . . . . . . .6.2.3 Examples . . . . . . . . . . . . . . . . . . .6.2.4 Proving/Disproving Properties of Relations6.2.5 Questions & Exercises . . . . . . . . . . . .6.3 Order Relations . . . . . . . . . . . . . . . . . . . .6.3.1 Questions & Exercises . . . . . . . . . . . .6.4 Equivalence Relations . . . . . . . . . . . . . . . .6.4.1 Definition and Examples . . . . . . . . . . .6.4.2 Equivalence Classes . . . . . . . . . . . . .6.4.3 More Examples . . . . . . . . . . . . . . . .6.4.4 Questions & Exercises . . . . . . . . . . . .6.5 Modular Arithmetic . . . . . . . . . . . . . . . . .6.5.1 Definition and Examples . . . . . . . . . . .6.5.2 Equivalence Classes modulo n . . . . . . . .6.5.3 Multiplicative Inverses . . . . . . . . . . . 3398399399402409412414414423433
8CONTENTS.4474554564574667 Functions and Cardinality7.1 Introduction . . . . . . . . . . . . . . . . . .7.1.1 Objectives . . . . . . . . . . . . . . .7.1.2 Segue from previous chapter . . . . .7.1.3 Motivation . . . . . . . . . . . . . .7.1.4 Goals and Warnings for the Reader .7.2 Definition and Examples . . . . . . . . . . .7.2.1 Definition . . . . . . . . . . . . . . .7.2.2 Examples . . . . . . . . . . . . . . .7.2.3 Equality of Functions . . . . . . . .7.2.4 Schematics . . . . . . . . . . . . . .7.2.5 Questions & Exercises . . . . . . . .7.3 Images and Pre-images . . . . . . . . . . . .7.3.1 Image: Definition and Examples . .7.3.2 Proofs about Images . . . . . . . . .7.3.3 Pre-Image: Definition and Examples7.3.4 Proofs about Pre-Images . . . . . . .7.3.5 Questions & Exercises . . . . . . . .7.4 Properties of Functions . . . . . . . . . . .7.4.1 Surjective (Onto) Functions . . . . .7.4.2 Injective (1-to-1) Functions . . . . .7.4.3 Proof Techniques for Jections . . . .7.4.4 Bijections . . . . . . . . . . . . . . .7.4.5 Questions & Exercises . . . . . . . .7.5 Compositions and Inverses . . . . . . . . . .7.5.1 Composition of Functions . . . . . .7.5.2 Inverses . . . . . . . . . . . . . . . .7.5.3 Bijective Invertible . . . . . . .7.5.4 Questions & Exercises . . . . . . . .7.6 Cardinality . . . . . . . . . . . . . . . . . .7.6.1 Motivation and Definition . . . . . .7.6.2 Finite Sets . . . . . . . . . . . . . .7.6.3 Countably Infinite Sets . . . . . . .7.6.4 Uncountable Sets . . . . . . . . . . .7.6.5 Questions & Exercises . . . . . . . .7.7 Summary . . . . . . . . . . . . . . . . . . .7.8 Chapter Exercises . . . . . . . . . . . . . .7.9 Lookahead . . . . . . . . . . . . . . . . . . 5495555575585666.66.76.86.5.4 Some Helpful Theorems6.5.5 Questions & Exercises .Summary . . . . . . . . . . . .Chapter Exercises . . . . . . .Lookahead . . . . . . . . . . . .
9CONTENTS8 Combinatorics8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . .8.1.1 Objectives . . . . . . . . . . . . . . . . . . . .8.1.2 Segue from previous chapter . . . . . . . . . .8.1.3 Motivation . . . . . . . . . . . . . . . . . . .8.1.4 Goals and Warnings for the Reader . . . . . .8.2 Basic Counting Principles . . . . . . . . . . . . . . .8.2.1 The Rule of Sum . . . . . . . . . . . . . . . .8.2.2 The Rule of Product . . . . . . . . . . . . . .8.2.3 Fundamental Counting Objects and Formulas8.2.4 Questions & Exercises . . . . . . . . . . . . .8.3 Counting Arguments . . . . . . . . . . . . . . . . . .8.3.1 Poker Hands . . . . . . . . . . . . . . . . . .8.3.2 Other Card-Counting Examples . . . . . . . .8.3.3 Other Counting Objects . . . . . . . . . . . .8.3.4 Questions & Exercises . . . . . . . . . . . . .8.4 Counting in Two Ways . . . . . . . . . . . . . . . . .8.4.1 Method Summary . . . . . . . . . . . . . . .8.4.2 Examples . . . . . . . . . . . . . . . . . . . .8.4.3 Standard Counting Objects . . . . . . . . . .8.4.4 Binomial Theorem . . . . . . . . . . . . . . .8.4.5 Questions & Exercises . . . . . . . . . . . . .8.5 Selections with Repetition . . . . . . . . . . . . . . .8.5.1 Motivation . . . . . . . . . . . . . . . . . . .8.5.2 Formula . . . . . . . . . . . . . . . . . . . . .8.5.3 Equivalent Forms . . . . . . . . . . . . . . . .8.5.4 Examples . . . . . . . . . . . . . . . . . . . .8.5.5 Questions & Exercises . . . . . . . . . . . . .8.6 Pigeonhole Principle . . . . . . . . . . . . . . . . . .8.6.1 Motivation . . . . . . . . . . . . . . . . . . .8.6.2 Statement and Proof . . . . . . . . . . . . . .8.6.3 Examples . . . . . . . . . . . . . . . . . . . .8.6.4 Questions & Exercises . . . . . . . . . . . . .8.7 Inclusion/Exclusion . . . . . . . . . . . . . . . . . . .8.7.1 Motivation . . . . . . . . . . . . . . . . . . .8.7.2 Statement and Proof . . . . . . . . . . . . . .8.7.3 Examples . . . . . . . . . . . . . . . . . . . .8.7.4 Questions & Exercises . . . . . . . . . . . . .8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . .8.9 Chapter Exercises . . . . . . . . . . . . . . . . . . .8.10 Lookahead . . . . . . . . . . . . . . . . . . . . . . . 657657658659662662663669
10A Definitions and TheoremsA.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . .A.1.1 Standard Sets . . . . . . . . . . . . . . . . . .A.1.2 Set-Builder Notation . . . . . . . . . . . . . .A.1.3 Elements and Subsets . . . . . . . . . . . . .A.1.4 Power Set . . . . . . . . . . . . . . . . . . . .A.1.5 Set Equality . . . . . . . . . . . . . . . . . . .A.1.6 Set Operations . . . . . . . . . . . . . . . . .A.1.7 Indexed Set Operations . . . . . . . . . . . .A.1.8 Partition . . . . . . . . . . . . . . . . . . . .A.2 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . .A.2.1 Statements and Propositions . . . . . . . . .A.2.2 Quantifiers . . . . . . . . . . . . . . . . . . .A.2.3 Connectives . . . . . . . . . . . . . . . . . . .A.2.4 Logical Negation . . . . . . . . . . . . . . . .A.2.5 Proof Strategies . . . . . . . . . . . . . . . .A.3 Induction . . . . . . . . . . . . . . . . . . . . . . . .A.3.1 Principle of Specific Mathematical InductionA.3.2 Principle of Strong Mathematical Induction .A.3.3 “Minimal Criminal” Argument . . . . . . . .A.4 Relations . . . . . . . . . . . . . . . . . . . . . . . .A.4.1 Properties of Relations . . . . . . . . . . . . .A.4.2 Equivalence Relations . . . . . . . . . . . . .A.4.3 Modular Arithmetic . . . . . . . . . . . . . .A.5 Functions . . . . . . . . . . . . . . . . . . . . . . . .A.5.1 Images and Pre-Images . . . . . . . . . . . .A.5.2 Jections . . . . . . . . . . . . . . . . . . . . .A.5.3 Composition of Functions . . . . . . . . . . .A.5.4 Inverses . . . . . . . . . . . . . . . . . . . . .A.5.5 Proof Techniques for Functions . . . . .
Everything You Always Wanted To Know About Mathematics* (*But didn’t even know to ask) A Guided Journey Into the World of Abstract Mathematics and the Writing of Proofs Brendan W. Sullivan bwsulliv@andrew.cmu.edu with Professor John Mackey Department of Mathematical Scienc
Jun 28, 2018 · 245(I): EVERYTHING YOU ALWAYS WANTED TO KNOW BUT WERE AFRAID TO ASK . 4 . 245(I): EVERYTHING YOU ALWAYS WANTED TO KNOW BUT WERE AFRAID TO ASK JUNE 2018 . timeframe, on or before April 30, 2001, there is no visa preference category for siblings of permanent residents. Even though Luis late
Everything You Ever Wanted to Know About Laminates but Were Afraid to Ask Introduction to the 9th Edition Dear Reader, It has been over 25 years since the earliest edition of “Everything You Ever Wanted to Know About Laminates but Were Afraid to
EVERYTHING YOU ALWAYS WANTED TO KNOW ABOUT REDISTRICTING BUT WERE AFRAID TO ASK AMERICAN CIVIL LIBERTIES UNION FOUNDATION VOTING RIGHTS PROJECT 230 Peachtree Street, NW . But to be an effective player, you need to know the rules of the game which are discussed in this pamphlet. For more in
EVERYTHING YOU HAVE ALWAYS WANTED TO KNOW ABOUT HOME COMPOSTING. But Were Afraid to Ask! . YOU HAVE BROWNS AT HAND TO ADD ON TOP OF YOUR GREENS. 4 Chopping or mowing your compost materials speeds the process since it provides more surface area for the compost organisms. As the creature
4 Everything You Wanted to Know About ADHD But Forgot You Wanted to Ask CME Information (cont’d) Learning Objectives After completing this activity, participants should be better able to: recognize how ADHD symptoms change as a patient grows up and h
x Everything You Always Wanted to Know about IDCAMS But Were Afraid to Ask Stephen M. Branch is an IBM Senior Software Engineer whose 40-year career includes all aspects of DFSMS. Stephen specializes in ICF Catalog, IDCAMS, and VSAM. He holds several patents for these components and is the author of the Catalog Search Interface (CSI)
Everything You’ve Always Wanted to Know About PSEs * *But Might Have Been Afraid to Ask. FORWARD: “Show me where it’s written” is probably the most often heard statement made to stewards and officers. It’s made by members, fellow stewards and officers, management, and arbitrators. This is particularly perplexing when dealing with .File Size: 630KB
Abrasive-Jet Machining High pressure water (20,000-60,000 psi) Educt abrasive into stream Can cut extremely thick parts (5-10 inches possible) – Thickness achievable is a function of speed – Twice as thick will take more than twice as long Tight tolerances achievable – Current machines 0.002” (older machines much less capable 0.010” Jet will lag machine position .
