Proof Patterns

Equips students to recognise proof patterns across fields in pure mathematics Reinforces each technique with end of chapter problems Supports further research with extensive additional reading suggestions This innovative textbook introduces a new pattern-based approach to learning proof methods in the mathematical sciences. Readers will discover techniques that will enable them to learn new proofs across different areas of pure mathematics with ease. The patterns in proofs from diverse fields such as algebra, analysis, topology and number theory are explored. Specific topics examined include game theory, combinatorics, and Euclidean geometry, enabling a broad familiarity. The author, an experienced lecturer and researcher renowned for his innovative view and intuitive style, illuminates a wide range of techniques and examples from duplicating the cube to triangulating polygons to the infinitude of primes to the fundamental theorem of algebra. Intended as a companion for undergraduate students, this text is an essential addition to every aspiring mathematician’s toolkit. Content Level » Upper undergraduate Keywords » Combinatorics - Euclidean Geometry - Game Theory - Mathematics Education - Patterns - Proof - Pure Mathematics Related subjects » Analysis - Geometry & Topology - Mathematics Education - Number Theory and Discrete Mathematics Preface 5 Contents 8 1 Induction and Complete Induction 13 1.1 Introduction 13 1.2 Examples of Induction 14 1.3 Why Does Induction Hold? 15 1.4 Induction and Binomials 16 1.5 Triangulating Polygons 19 1.6 Problems 20 2 Double Counting 22 2.1 Introduction 22 2.2 Summing Numbers 22 2.3 Vandermonde's Identity 24 2.4 Fermat's Little Theorem 25 2.5 Icosahedra 26 2.6 Pythagoras's Theorem 27 2.7 Problems 28 3 The Pigeonhole Principle 29 3.1 Introduction 29 3.2 Rationals and Decimals 29 3.3 Lossless Compression 31 3.4 More Irrationality 32 3.5 Problems 33 4 Divisions 34 4.1 Introduction 34 4.2 Division and Well-Ordering 34 4.3 Algorithms and Highest Common Factors 35 4.4 Lowest Terms 37 4.5 Euclid's Lemma 38 4.6 The Uniqueness of Prime Decompositions 39 4.7 Problems 40 5 Contrapositive and Contradiction 41 5.1 Introduction 41 5.2 An Irrational Example 42 5.3 The Infinitude of Primes 44 5.4 More Irrationalities 45 5.5 The Irrationality of e 46 5.6 Which to Prefer 48 5.7 Contrapositives and Converses 48 5.8 The Law of the Excluded Middle 48 5.9 Problems 49 6 Intersection-Enclosure and Generation 50 6.1 Introduction 50 6.2 Examples of Problems 50 6.3 Advanced Example 51 6.4 The Pattern 52 6.5 Generation 53 6.6 Fields and Square Roots 55 6.7 Problems 58 7 Difference of Invariants 59 7.1 Introduction 59 7.2 Dominoes and Triminoes 59 7.3 Dimension 60 7.4 Cardinality 64 7.5 Order 67 7.6 Divisibility 69 7.7 Problems 70 8 Linear Dependence, Fields and Transcendence 71 8.1 Introduction 71 8.2 Linear Dependence 72 8.3 Linear Dependence and Algebraic Numbers 75 8.4 Square Roots and Algebraic Numbers 76 8.5 Transcendental Numbers 77 8.6 Problems 77 9 Formal Equivalence 78 9.1 Introduction 78 9.2 Ruler and Compass Constructions 78 9.3 Further Reading 85 9.4 Problems 85 10 Equivalence Extension 86 10.1 Introduction 86 10.2 Constructing the Integers 86 10.3 Constructing the Rationals 90 10.4 The Inadequacy of the Rationals 93 10.5 Constructing the Reals 95 10.6 Convergence of Monotone Sequences 98 10.7 Existence of Square Roots 99 10.8 Further Reading 99 10.9 Problems 100 11 Proof by Classification 101 11.1 Introduction 101 11.2 Co-prime Square 101 11.3 Classifying Pythagorean Triples 102 11.4 The Non-existence of Pythagorean Fourth Powers 105 11.5 Problems 107 12 Specific-generality 108 12.1 Introduction 108 12.2 Reducing the Fermat Theorem 108 12.3 The Four-Colour Theorem 109 12.4 Problems 111 13 Diagonal Tricks and Cardinality 112 13.1 Introduction 112 13.2 Definitions 112 13.3 Infinite Sets of the Same Size 113 13.4 Diagonals 115 13.5 Transcendentals 118 13.6 Proving the Schröder--Bernstein Theorem 119 13.7 Problems 121 14 Connectedness and the Jordan Curve Theorem 122 14.1 Definitions 122 14.2 Components 123 14.3 The Jordan Closed-Curve Theorem 125 14.4 Problems 128 15 The Euler Characteristic and the Classification of Regular Polyhedra 129 15.1 Introduction 129 15.2 The Euler Characteristic and Surgery 129 15.3 Transforming the Problem 131 15.4 The Result for Networks in the Plane 132 15.5 Counterexamples 135 15.6 Classifying Regular Polyhedra 137 15.7 Problems 138 16 Discharging 139 16.1 Introduction 139 16.2 The Euler Characteristic via Discharging 139 16.3 Maps and Double Counting 140 16.4 Inevitable Configurations 143 16.5 Problems 143 17 The Matching Problem 144 17.1 Introduction 144 17.2 Formulating the Problem 144 17.3 The Algorithm 145 17.4 Uniqueness 145 17.5 Further Reading 146 17.6 Problems 146 18 Games 147 18.1 Introduction 147 18.2 Defining a Game 147 18.3 Termination 148 18.4 Optimal Strategy 149 18.5 Second Player Never Wins 149 18.6 Problems 150 19 Analytical Patterns 151 19.1 Introduction 151 19.2 The Triangle Inequality 152 19.3 The Definition 152 19.4 Basic Results 154 19.5 Series 159 19.6 Continuity 162 19.7 Theorems About Continuous Functions 165 19.8 The Fundamental Theorem of Algebra 168 19.9 Further Reading 171 19.10 Problems 171 20 Counterexamples 173 20.1 Introduction 173 20.2 Matrix Algebra 173 20.3 Smooth Functions 175 20.4 Sequences 177 20.5 Ordinary Differential Equations 178 20.6 Characterisation 179 20.7 Problems 180 Appendix AGlossary 181 Appendix BEquivalence Relations 183 References 185 Index 186 Front Matter....Pages i-xiii Induction and Complete Induction....Pages 1-9 Double Counting....Pages 11-17 The Pigeonhole Principle....Pages 19-23 Divisions....Pages 25-31 Contrapositive and Contradiction....Pages 33-41 Intersection-Enclosure and Generation....Pages 43-51 Difference of Invariants....Pages 53-64 Linear Dependence, Fields and Transcendence....Pages 65-71 Formal Equivalence....Pages 73-80 Equivalence Extension....Pages 81-95 Proof by Classification....Pages 97-103 Specific-generality....Pages 105-108 Diagonal Tricks and Cardinality....Pages 109-118 Connectedness and the Jordan Curve Theorem....Pages 119-125 The Euler Characteristic and the Classification of Regular Polyhedra....Pages 127-136 Discharging....Pages 137-141 The Matching Problem....Pages 143-145 Games....Pages 147-150 Analytical Patterns....Pages 151-172 Counterexamples....Pages 173-180 Back Matter....Pages 181-190