Dedicated to my wife Nancy, in appreciation of her love and support Ethan D. Bloch Proofs and Fundamentals A First Course in Abstract Mathematics Birkhauser Boston • Basel • Berlin Ethan D. Bloch Department of Mathematics and Computer Science Bard College Annandale-on-Hudson, NY 12504 USA Library of Congress Cataloging-in-PubJication Data Bloch, Ethan D., 1956- Proofs and fundamentals: a first course in abstract mathematics I Ethan D. Bloch. p. cm. Includes bibliographical references and index. ISBN-13: 978-1-4612-7426-1 e-ISBN-13: 978-1-4612-2130-2 DOT: 10.1007/978-1-4612-2130-2 1. Proof theory. 2. Set theory. I. Title. QA9.54.B57 2000 511.3--dc21 00-023309 CIP AMS Subject Classifications 2000: Primary OOA35; Secondary 00-01 Printed on acid-free paper Birkhiiuser @2000 Birkhliuser Boston 11:>2003 Birkhliuser Boston, 2nd printing All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Birkhliuser Boston, clo Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Reformatted from the author's files by TJY(niques, Inc., Cambridge, MA. Figures recreated by Marty Stock, Watertown, MA. Cover design by Jeff Cosloy, Portland, OR. 98765432 Birkhliuser Boston· Basel· Berlin A member of BertelsmannSpringer Science+Business Media GmbH Contents Introduction ix To the Student xiii To the Instructor xix Part I PROOFS 1 1 Informal Logic 3 1.1 Introduction 3 1.2 Statements. 4 1.3 Relations Between Statements 18 1.4 Valid Arguments 31 1.5 Quantifiers.... 41 2 Strategies for Proofs 55 2.1 Mathematical Proofs - What They Are and Why We Need Them . . . . . . . . . . . . 55 2.2 Direct Proofs ............... . 63 2.3 Proofs by Contrapositive and Contradiction 67 2.4 Cases, and If and Only If . . . . . . . . . . 74 vi Contents 2.5 Quantifiers in Theorems 81 2.6 Writing Mathematics .. 93 Part II FUNDAMENTALS 105 3 Sets 107 3.1 Introduction . . . . . . . 107 3.2 Sets - Basic Definitions 109 3.3 Set Operations. . . . . . 119 3.4 Indexed Families of Sets 129 4 Functions 135 4.1 Functions · ............. 135 4.2 Image and Inverse Image . . . . . . 145 4.3 Composition and Inverse Functions. 152 4.4 Injectivity, Surjectivity and Bijectivity 161 4.5 Sets of Functions ........... 170 5 Relations 177 5.1 Relations · ...... 177 5.2 Congruence . . . . . . 184 5.3 Equivalence Relations . 191 6 Infinite and Finite Sets 203 6.1 Cardinality of Sets · ........ 203 6.2 Cardinality of the Number Systems . 218 6.3 Mathematical Induction . 226 6.4 Recursion · ............. 236 Part III EXTRAS 249 7 Selected Topics 251 7.1 Binary Operations . · ........ 251 7.2 Groups ....... · ........ 258 7.3 Homomorphisms and Isomorphisms 267 7.4 Partially Ordered Sets . . . . . 273 ............... 7.5 Lattices 284 7.6 Counting: Products and Sums. . . . 294 7.7 Counting: Permutations and Combinations . 304 Contents vii 8 Number Systems 323 8.1 Back to the Beginning .......... . 323 8.2 The Natural Numbers . . . . . . . . . . . . 324 8.3 Further Properties of the Natural Numbers . 333 8.4 The Integers . . . . . . . . . . . . . . . . . 338 8.5 The Rational Numbers .. . . . . . . . . . 348 8.6 The Real Numbers and the Complex Numbers . 352 8.7 Appendix: Proof of Theorem 8.2.1 . . . . . . . 361 9 Explorations 363 9.1 Introduction 363 9.2 Greatest Common Divisors 364 9.3 Divisibility Tests ... 366 9.4 Real-Valued Functions .. 367 9.5 Iterations of Functions .. 368 9.6 Fibonacci Numbers and Lucas Numbers 369 9.7 Fuzzy Sets ............... . 371 Appendix: Properties of Numbers 375 Hints for Selected Exercises 379 References 405 Index 413 Introduction In an effort to make advanced mathematics accessible to a wide variety of students, and to give even the most mathematically inclined students a solid basis upon which to build their continuing study of mathematics, there has been a tendency in recent years to introduce students to the for mulation and writing of rigorous mathematical proofs, and to teach topics such as sets, functions, relations and countability, in a "transition" course, rather than in traditional courses such as linear algebra. A transition course functions as a bridge between computational courses such as Calculus, and more theoretical courses such as linear algebra and abstract algebra. This text contains core topics that I believe any transition course should cover, as well as some optional material intended to give the instructor some flexibility in designing a course. The presentation is straightforward and focuses on the essentials, without being too elementary, too exces sively pedagogical, and too full to distractions. Some of features of this text are the following: (1) Symbolic logic and the use of logical notation are kept to a minimum. We discuss only what is absolutely necessary - as is the case in most advanced mathematics courses that are not focused on logic per se. (2) We distinguish between truly general techniques (for example, direct proof and proof by contradiction) and specialized techniques, such as math ematical induction, which are particular mathematical tools rather than general proof techniques. x Introduction (3) We avoid an overemphasis on "fun" topics such as number theory, com binatorics or computer science related topics, since they are not as central as a thorough treatment of sets, functions and relations for core mathe matics courses such as linear algebra, abstract algebra and real analysis. Even the two sections on combinatorics in Chapter 7 were written with a focus on reinforcing the use of sets, functions and relations, rather than emphasizing clever counting arguments. (4) The material is presented in the way that mathematicians actually use it rather than in the most axiomatically direct way. For example, a function is a special type of a relation, and from a strictly axiomatic point of view, it would make sense to treat relations first, and then develop functions as a special case of relations. I believe most mathematicians do not think of functions in this way (except perhaps for some combinatorialists), and we cover functions before relations, offering clearer treatments of each topic. (5) A section devoted to the proper writing of mathematics has been in cluded, to help remind students and instructors of the importance of good writing. Outline of the text The book is divided into three parts: Proofs, Fundamentals and Extras, re spectively. At the end of the book is a brief appendix summarizing a few basic properties of the standard number systems (integers, rational num bers, real numbers) that we use, a section of hints for selected exercises, an index and a bibliography. The core material in this text, which should be included in any course, consists of Parts I and II (Chapters 1-6). A one semester course can comfortably include all the core material, together with a small amount of material from Part III, chosen according to the taste of the instructor. Part I, Proofs, consists of Chapters 1-2, covering informal logic and proof techniques, respectively. These two chapters discuss the"how" of modem mathematics, namely the methodology of rigorous proofs as is currently practiced by mathematicians. Chapter 1 is a precursor to rigorous proofs, and is not about mathematical proofs per se. The exercises in this chapter are all informal, in contrast to the rest of the book. Chapter 2, while including some real proofs, also has a good bit of informal discussion. Part II, Fundamentals, consists of Chapters 3-6, covering sets, functions, relations and cardinality. This material is basic to all of modem mathemat-