Page
1
(This page has no text content)
Page
2
A Transition to Advanced Mathematics
Page
3
This page intentionally left blank
Page
4
A Transition to Advanced Mathematics A Survey Course William Johnston Alex M. McAllister 3 2009
Page
5
3 Oxford University Press, Inc., publishes works that further Oxford University’s objective of excellence in research, scholarship, and education. Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto With offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Copyright © 2009 by Oxford University Press, Inc. Published by Oxford University Press, Inc. 198 Madison Avenue, New York, New York 10016 www.oup.com Oxford is a registered trademark of Oxford University Press All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior permission of Oxford University Press. Library of Congress Cataloging-in-Publication Data Johnston, William, 1960– A transition to advanced mathematics : a survey course / William Johnston, Alex M. McAllister. p. cm. Includes bibliographical references and index. ISBN 978-0-19-531076-4 1. Mathematics—Textbooks. I. McAllister, Alex M. II. Title. QA37.3.J65 2009 510—dc22 2009009644 9 8 7 6 5 4 3 2 1 Printed in the United States of America on acid-free paper
Page
6
For our teachers and our students
Page
7
This page intentionally left blank
Page
8
Preface A Transition to Advanced Mathematics: A Survey Course promotes the goals of a “transition” course in mathematics, helping to lead students from courses in the calculus sequence to theoretical upper-level mathematics courses. The text simultaneously promotes the goals of a “survey” course, describing the intriguing questions and insights fundamental to many diverse areas of mathematics. Its only prerequisite is single variable calculus, and there are many chapters, such as chapters 1, 2, 3, and 6, that do not even require calculus. A hallmark of the book is its flexibility—an instructor may choose to use the text in a variety of ways. The standard adoption would be for a transition course, but this text could also be used in other settings. A lack of diversity is perhaps the most noteworthy weakness in many institutions’ current introductory mathematics curricula. A significant number of students (indeed, most people in the general population) have little understanding of the broad scope of mathematics. Since many promising students never even complete the calculus sequence, they drop out of mathematics before having had the opportunity to study some mathematical field they would have loved. Calculus doesn’t stir everyone’s imagination. Could a potential coding theory wizard have missed out on the fun of public key cryptography? Has a potential complex analyst who could have proven the Riemann hypothesis turned to another major? Has a potential logician who might have followed in the footsteps of Gödel decided math was purely computational? In addition, without a survey course, most mathematics majors do not possess an appreciation for the multifaceted aspects of the study of mathematics—at least not until after they have declared their major and taken a variety of upper-level courses. This situation in mathematics stands in marked contrast to virtually every other area of academics, where a survey course is among the regular course offerings. Surely our standard undergraduate course offerings can do better? But how can we succeed in showing our students the expansive vista of mathematics without a significant restructuring of the curriculum? The answer can come in many forms, and this text can help. Combining the goals of a transition course with the desire to provide a survey of the subject, A Transition to Advanced Mathematics: A Survey Course teaches proof writing, reading, and understanding mathematics in the context of its many wonderful and interesting subfields. And so the text is written primarily for use in a one-semester transition course, enhancing that course by giving students a taste of the many areas of mathematics. Learning to read and write proofs is an important yet challenging
Page
9
viii Preface process; by embedding it in the study of interesting and diverse mathematics, this text is designed to motivate and inspire students in their further studies. Depending on how a department stresses theory at the junior-senior level, some instructors may also wish to use the text in a survey course at the upper level. Students who have seen only one or two advanced courses, such as differential equations or complex analysis, would benefit from this text’s approach, as it promotes a training in the abstract nature of the subject. The text would be terrific at a large university that might offer many curricular tracks toward mathematical science majors. It also serves small colleges well, including those institutions whose resources limit the possibility of offering the full breadth of courses common in larger programs. The book could also be used as a training tool in independent studies, where a bright student could work through the sections by reading, answering questions, and working through selected exercises. Or it would make an inspirational gift for a young person who has expressed an interest in mathematics but is not yet a student in a four-year undergraduate program—anyone who loves mathematics and wants to know more about mathematical thinking would benefit from working through this text. And so the main objective of the book is to bring about a deep change in the mathematical character of students—how they think and their fundamental perspectives on the world of mathematics. Instead of just calculating a derivative, we want students to enjoy the theory that Newton and Leibniz developed, especially as the theory leads to the techniques used in calculations. Instead of just knowing such facts as the first three primes are 2, 3, and 5, we want students to respond well to the variety of theoretical questions about primes, to formulate such questions on their own, and to be impressed by and to understand key elements of the mathematical theory of primes. In this way, we hope that working through the text will encourage students to become mathematicians in the fullest sense of the word. How can we bring about this change in our students? We believe this text promotes three major mathematical traits in a meaningful, transformative way: to develop an ability to communicate with precise language, to use mathematically sound reasoning, and to ask probing questions about mathematics. These skills are the hallmarks of a good mathematician. Mathematicians live in a unique world. Our language is the natural language of our culture (for most people in the United States and the United Kingdom this language is English), but a mathematician’s use of this natural language is refined and specific. Through the common consensus of professional researchers and teachers, mathematical words and phrases are given precise, unambiguous interpretations, making it crucial for a mathematician to be able to work carefully with formal, rigorous definitions. With years of experience and practice, most mathematicians naturally express themselves in this formal language, but at the same time, this ability is an acquired skill that sometimes runs counter to the fluidity and adaptability of our natural language. With care and practice, students can develop the ability to write and speak well using the formal, explicit language of mathematics— its terminology and symbols, its expression of deductive and inductive reasoning, and its insistence on clarity and organizational neatness. A Transition to Advanced Mathematics offers engagement in the necessary experience to develop a mathematical voice.
Page
10
Preface ix Similarly, a mathematician’s rational mode of thought is rooted in natural human reasoning, but it also differs from that of the mainstream, being uniquely refined and sophisticated. It searches for general truths that follow from deductive reasoning. The creation of new mathematics often follows from leaps of intuitive insight based on results gathered from examples. But examples are not enough. Centuries of experience and practice have led mathematicians to rely on logical deductive arguments as the litmus test for mathematical truth. These arguments are traditionally presented in formal mathematical proofs. The format of this text encourages students to develop the logical thought processes needed to reason through these proofs. The book introduces the fundamentals of mathematical thought by placing the study of logic (as a description of this formal deductive reasoning) up front. And it gives students practice in applying mathematical arguments and proofs in the context of the broad landscape of mathematical fields. A reviewer of this text recognized the strategy well and wrote, “The justification for axiomatic reasoning … is clearest when there are questions on the table that simply cannot be resolved in any way other than employing the logical precision of a mathematical argument.” The text also encourages students to learn to write proofs not for the sake of writing proofs, but because they see the value of applying sound reasoning to intriguing mathematical questions. In short, the book invites students to enter the ongoing mathematical dialogue with mentors and colleagues. Finally, mathematicians have an active curiosity and a constant desire to ask questions. Mathematicians perceive a world of ideas to be grappled with, research interests to be explored, and applications of theory to be determined. While much great mathematics is already known, students need to understand that there is so much more waiting to be discovered! Put succinctly, discovering patterns and forming conjectures are essential to the pursuit of mathematical truth. A Transition to Advanced Mathematics has many questions and exercises that promote the formulation of reasonable hypotheses; diverse examples throughout the text help students begin investigations of many different types of mathematical objects. A Transition Course A Transition to Advanced Mathematics nicely serves as a text for the “transition” course now so common in many institutions’ undergraduate mathematics curriculum. Usually offered at the sophomore level, a transition course bridges the gap between computationally oriented lower-level courses and theoretically oriented upper-level courses. Most mathematics students begin their college career in a calculus sequence that emphasizes computational problem-solving and applications of calculus methods. There are many good reasons for beginning the undergraduate curriculum with this sequence of courses. Students learn a lot of analysis and function theory by the end of their second year, which provides them with good depth in one area of mathematics and a great deal of experience in solving many problems at increasing levels of sophistication. In addition, calculus is the field of mathematics that is most useful as a
Page
11
x Preface prerequisite for the physical sciences, engineering, the social sciences, and business. Students majoring in these areas of study need to learn differential and integral calculus by the end of their first year of college, and mathematics teachers across the country do an excellent job of preparing these students for the rigors ahead. On the other hand, as budding mathematicians our students should seek more than just knowing what mathematical truths hold; they should want to understand why mathematical truths hold. The good news is that computations and algorithms learned in lower-level courses often contain the kernel of the ideas behind the truth of certain mathematical statements. Thus, by working through calculations, students can develop an insightful intuition about many mathematical truths. The next step for a student to mature into a fully developed mathematician is to gain an ability to articulate precisely reasoned arguments that explain and justify the mathematical idea under scrutiny. Unfortunately, as many in the mathematical community have recognized, a focus on the computational elements of calculus is not preparing students for this transition into theoretically oriented upper-level courses. Many students enter courses on abstract mathematics having minimal experience with either the deductive reasoning or the abstract thought processes that are characteristic of proofs. Furthermore, many have never been exposed to the experimentation and conjecture essential to the discovery and creation of mathematics. This text is designed to bridge the gap and improve the success of students in upper-level courses. By making mathematics enjoyable and manageable, and by serving the need to train students in mathematics well, this book is also intended to serve as the mathematical community’s much sought after “pump” to bring more students into the mathematical fold. As they work through the text, students hopefully will recognize that they are learning the art of mathematics, and, like an apprentice artist, hopefully they will enjoy the resulting creations as they use their “mathematical palette.” In summary, as a text for a transition course, A Transition to Advanced Mathematics encourages students to: • Develop careful reasoning skills as the student is transitioning from com- putationally oriented, algorithmic thinking to more sophisticated modes of reasoning; • Learn to read mathematics, specifically definitions, examples, proofs, and counterexamples; • Learn to write mathematics, primarily formal proofs, but also intuitive explana- tions and conjectures. A Survey Course More than just serving as a text for a transition course, A Transition to Advanced Mathematics is also designed to provide students with a broad survey of many fundamental areas of mathematics. Students completing a calculus sequence may not realize that mathematicians are a diverse lot with wide-ranging interests. Indeed, many different areas of mathematics suit individual skills and insights as well as personal
Page
12
Preface xi interests and temperaments. With the calculus sequence serving as the primary point of entry to the mathematics major, many students are unaware of the marvelous variety inherent in mathematics. A Transition to Advanced Mathematics responds in a positive way to the need to provide students with a broad survey of mathematical ideas and explorations, as it is intended to: • Provide students with a broad and comprehensive introduction to mathematics, including both continuous and discrete mathematics; • Introduce students to “upper-level” topics at an earlier stage in the mathematics major; • Create greater continuity and flow in the mathematics major, introducing various topics, mathematical objects, and proof techniques multiple times at increasing levels of sophistication. The text responds to the mathematical community’s ambitious desire to show students a vast array of mathematical ideas. In its writing, we had to decide which topics to include and which to omit. Two questions guided the decision process: (1) What fundamental ideas should all mathematics majors know when they complete their undergraduate degree? (2) What ideas do mathematicians experience as intriguing, exciting, and central to mathematics? In some ways, these questions may be highly personal with subjective answers; very reasonable people may give very different and equally compelling answers. This text offers an answer in a way that we believe represents a thoughtful response of the full mathematical community. The answers have naturally been guided by our own experiences, but they have also been informed by discussions with many colleagues and friends, presentations and panels at national and regional mathematics meetings, published statements of professional mathematical societies, and our personal understanding of the consensus of the contemporary mathematical culture. Some people may wish that we had included additional areas, but we feel the text promotes mathematics in general and intends that students be able to make the jump into areas not discussed in the book (such as general and algebraic topology, differential geometry, non-Euclidean geometry, or relativity theory) by having discussed the mathematics presented. The following general descriptions of the chapters, together with the detailed Table of Contents, present the balance we have struck between continuous and discrete mathematical topics in light of the “survey” aspect of the course. We hope that this panoramic view of the mathematics we know and love will intrigue, excite, and ultimately encourage students to take up a more thorough study of the topics in upper-level mathematics courses. Suggestions for the Instructor We wrote the text to give instructors options when using it in a one-semester course, although it is impossible to teach every topic from every section in such a short time. We intentionally provided plenty of material to allow for a follow-up study, such as an
Page
13
xii Preface independent project for a student who might be excited about a mathematical problem described in the readings. In this way, the book offers flexibility within a mathematical curriculum; it will usually be used in a one-semester course, but some institutions may have short terms where a follow-up course would fit in well. The one-semester offering is the standard fare, and the book is designed for this setting. An instructor can choose from the Contents in a variety of ways. Chapter 1 is required and needs to be discussed first, but then there are many options for the way this book can be used. Use will typically depend on the needs of the department and the curriculum, the interests of the instructor, the purpose of the course, and the backgrounds of the students.Areviewer for the text said it best, “The beauty of this type of text is that you can jump around, since … most of the chapters are self-contained.” The flowchart, though it does not have to be followed, gives some guidance as to the rough logical dependence of the chapters. We believe that the heart of the course is in chapters 1–4, and these four chapters could support a wonderful course in and of themselves. The first chapter is designed to teach students to think mathematically and to prove mathematical theorems in the context of mathematical logic. We chose to begin the book with symbolic logic because we have found that students’ proof-writing skills improve tremendously when their approaches are grounded in proper logical thought. The study of logic is rightfully approached for its own sake as an interesting field of mathematics, and in this text it doubles as an important tool to develop theorem-proving skills. Chapter 1 Mathematical Logic. Section 1.4 is optional Chapter 2 Abstract Algebra. Sections 2.5 and 2.6 are optional Chapter 3 Number Theory. Sections 3.2 and 3.3 are optional Chapter 5 Probability and Statistics. Sections 5.4 and 5.5 are optional Chapter 6 Graph Theory. Sections 6.3 and 6.4 are optional Chapter 7 Complex Analysis. Sections 7.4 and 7.5 are optional Chapter 4 Real Analysis. Sections 4.6, 4.7, and 4.8 are optional The last section of chapter 1 is the most important in the book, in the sense that it gathers the ideas from formal logic into a discussion of how to prove mathematical theorems. It sets the stage for proving mathematical results in all other chapters. Additional ideas introduced in chapter 1 include the sentential (or propositional) logic
Page
14
Preface xiii of connectives, truth tables, validity of arguments, Gödel’s incompleteness theorems, and predicate logic. Nearly all of these topics are directly connected to learning about the fundamental proof techniques of mathematics, and the text intends for students to be motivated by seeing the value of symbolic logic throughout the study. An application section explores the design of computer circuits via sentential logic and Karnaugh maps. Not all of these topics need to be explored, and an instructor may choose to omit many of the sections. A streamlined approach to chapter 1, for example, could examine only sections 1.1, 1.2, 1.6, and 1.7. In the flowchart, we have listed section 1.4 as optional because we often choose to omit it, but a quick review of any chapter will indicate that an instructor may pick and choose from the many topics found within sections in a variety of ways. Chapter 2 studies number systems as foundational to understanding mathematics. The chapter explores the integers and other basic number systems from the perspective of abstract algebraic properties and relations. These notions lead to important insights that are applied in later chapters, especially chapter 3. The fundamental ideas introduced in chapter 2 include a basic algebra of sets, Russell’s paradox, the division algorithm, modular arithmetic, congruence of integers modulo n, equivalence relations, proofs of the uniqueness of mathematical objects, dihedral groups, and the basic notions of group theory. An application section explores a variety of check digit schemes. Chapter 3 is meant to be a lot of fun. It expands on chapter 2’s study of number systems from the perspective of examining abstract algebraic properties, including the exploration of solutions to polynomials. This theme is picked up on in many later chapters, especially in the study of polynomials as functions. An instructor can pick and choose from the many interesting, accessible, and historic topics from number theory, including ideas on the infinitude of primes, the prime number theorem, Goldbach’s conjecture, the fundamental theorem of arithmetic, the Pythagorean theorem, solutions of basic Diophantine equations, fields, Fermat’s last theorem (the proof is given for n = 4), the irrationality of the square root of two, the classical fundamental theorem of algebra, Abel’s theorem, and the proof technique of mathematical induction. An application section explores public key encryption (via the RSA system) and Hamming codes, which require a short introduction to matrix multiplication. The mathematics developed during the Age of Enlightenment sets the stage for the development of both calculus and the theory of transfinite numbers. Chapter 4 introduces the basic notions of real analysis that underlie calculus. An instructor can choose to cover all of the topics in any section or simply focus on the basic definitions provided. The ideas introduced in this chapter include Descartes’ development of analytic geometry, the definition and properties of functions, the theory of inverse functions, the definition and basic properties of limits, derivatives, and Riemann integrals, the definitions of cardinality and countability, Cantor’s diagonalization arguments to prove the countability of the rationals and the uncountability of the reals, and a brief introduction to L2 spaces. An application section explores how differential equations can model physical processes such as the motion of a clock pendulum. The chapter assumes competency with topics found in a standard single-variable calculus course. As for any of the chapters from chapter 4 on, an instructor may
Page
15
xiv Preface choose to stop at any midway point through the list of sections. When we teach the one-semester course, we often decide to go on to chapter 5 after covering section 4.6. Chapters 5–7 are offered as sweet desserts. There are two distinct approaches to these last three chapters of the text. When we teach the course, we like to choose at least two or three sections from each of these chapters in order to give the students a taste of the many different disciplines in mathematics. Our students value this exposure—they say it helps them choose which courses they might later select from the upper-level offerings. Alternatively, each of the chapters is a completely independent module and can be studied in greater depth or omitted. Chapter 5 explores the mathematics of likelihood and the long-term patterns in discrete events. The section on hypothesis testing provides a mathematical approach to inductive thinking, parallel to the way in which chapter 1 provides a mathematical approach to deductive reasoning. The fundamental ideas introduced in this chapter include basic combinatorics, Pascal’s triangle, the binomial theorem, basic probability, hypothesis testing, and least squares regression. Many of the problems are computational, but the overriding framework of hypothesis testing and many of the abstract notions of probability theory are presented. This exposure is meant to assist greatly any student entering the corresponding upper level course. Chapter 6 introduces the study of graphs by indicating how they model and solve real-world questions, beginning with the Königsberg bridge problem. In this way, the chapter describes the mathematics of adjacency and the abstract descriptions of networks of “connected” points (or objects). This chapter’s fundamental ideas include the definition and basic properties of graphs, Eulerian and Hamiltonian circuits, trees and spanning trees, and weighted graphs. The chapter presents many algorithms for constructing shortest paths, spanning trees, Hamiltonian cycles, and minimum weight versions of these objects in a given graph. Chapter 7 presents an introduction to the theory of complex-valued functions, teaching students about the basic algebra of complex numbers, single- and multivalued functions such as nth roots, exponential, trigonometric, and logarithmic functions and their graphical representation, analytic functions, partial differentiation and the Cauchy–Riemann equations, power series representations of analytic functions, harmonic functions, and the Laplacian. An application section explores the use of streamlines and equipotentials to understand and model fluid flow. Key Elements of the Text We hope A Transition to Advanced Mathematics will be recognized as a clear and cogent text in support of a transition course surveying mathematics. It is designed to serve ideally in collaboration with mathematics professors helping students to explore new mathematical vistas, to grow into the perspectives of the mathematician, and to successfully practice mathematics. The following elements of the text are intended to help facilitate this partnership between professor and text in the creation of a dynamic and interesting learning experience.
Page
16
Preface xv Embedded questions. In each section, after reading through the text and examples that illustrate and explain fundamental concepts, students are invited to create and display their personal understanding of the mathematical idea at hand by answering questions. Many of these queries are straightforward and useful in providing good introductory experiences with the new ideas at hand; as such, they can be assigned as homework in preparation for class or used during class in the spirit of active learning and engaged discussion. Some of them lead to a main idea of an upcoming proof. An example is question 3.1.9 in section 3.1, which asks students about computations of the form p1 · p2 · · · pn + 1 where each pk is prime—are integers of that form always prime? (It is still an open question whether there are infinitely many primes in this sequence.) Reading questions. An effective pedagogical tool is to expect students to read the text before coming to class and to be able to answer a collection of basic questions. We always want our students to use a text more than as a reference for worked examples. Reading comprehension questions at the end of each section ask for definitions, examples, and the central ideas of the material, leading students to open the book and read. There are many ways for an instructor to use the reading questions. We assign them before every class meeting and expect students to write their responses in complete English sentences. Our hope is that students both learn the value of reading the book and get practice in expressing mathematical concepts well. They also come better prepared for class. In this way, teachers can respond to students’ questions and engage the mathematical ideas at a much deeper level during class, and the students develop the independent reading skills essential for more sophisticated mathematical studies. Exercises. Every section is accompanied by 70 exercises that allow the professor considerable flexibility in assigning homework and that give the reader practice. As with any exercise set, the ultimate goal is to provide students needed practice to deepen their understanding of the corresponding mathematical concepts. Instructors can pick and chose from many different types of problems. The exercises are grouped according to topic; if the instructor has focused on just part of the section’s material, it is easy to pick out corresponding problems to assign. The end of each exercise set always contains a variety of more challenging exercises. These questions sometimes anticipate ideas in upcoming sections, require the study and use of a new definition or idea, or ask students to make conjectures based on some pattern arising from a collection of computations. Instructors could occasionally use them to motivate students to pursue a topic in more detail, or as a staging point for further investigations that might lead to a short paper or presentation. An application section. Every chapter includes a section that explores an application of the theoretical ideas under study. All involve interesting “real-world” issues. Students are often surprised when theoretical notions find expression as a useful tool in life. The text intends to teach students, as they see a variety of applications, to view purely abstract, theoretical ideas as not antithetical to using mathematics to benefit society. The intent is for students to begin to perceive pure and applied mathematics as going hand in hand and strengthening one another in interplay: a search for applications often results in the development of new theoretical ideas, and theoretical mathematics often manifests itself as a critical underpinning of an applied tool.
Page
17
xvi Preface None of the application sections are required for the text’s other sections. When we teach the course, we sometimes treat a chapter’s applied section in the same way as the others in the chapter, but at other times we might simply ask our students to read the section outside of class and submit the reading questions, or have them work in teams to answer some of the exercises. Depending upon the instructor’s interests and the parameters of the course, any applied section may be skipped. Embedded reflections on the history, culture, and philosophy of mathematics. Mathematics is a timeless study that has been gradually developed through the corporate efforts of diverse individuals and cultures. The historical origins of mathematical ideas and the accompanying cultural standards for definitions, examples, and proofs are worthwhile and interesting and contribute to a student’s ability to understand and appreciate contemporary mathematics. Throughout the text, we tell stories about the struggles, the insights, and the people and events that helped shape mathematics. Our hope is for students to enjoy the drama, getting a sense of the eureka of mathematical breakthroughs and connecting proofs and mathematical statements (so often presented as devoid of human emotion), and relating to the human lives of the men and women who first presented them. Acknowledgments We thank our many friends and colleagues for supporting this work and our efforts. Through Faculty Development Committee grants, Centre College helped fund work during several summer months of writing. In 2001 we received a generous grant from the Associated Colleges of the South, funded by the Mellon Foundation, to assist with the incorporation of the technology-based portions of the text. Our colleagues in the mathematics departments at Centre College and at Randolph–Macon College supported our efforts by implementing a transitions course in the major curriculum and by allowing us to use early drafts of the work in the courses’ initial offerings. In short, our departments’ responses were universally supportive and meant a great deal to us. We are also grateful to Stan Perrine at Charleston Southern University, Deirdre Smeltzer at Eastern Mennonite University, and John Thompson at University of Pittsburgh at Johnstown for using an initial version of this text in their courses, and for their insightful suggestions that improved the text. Our students welcomed our requests for them to use early versions of the text, making suggestions, giving us positive feedback, and expressing their enthusiasm for both the project and the course. Josh Smith provided valuable assistance, giving feedback and working on solutions to exercises in chapters 1 and 2. Tyshaun Lang and Morgan Smith worked every exercise and question in a late version of the text, providing valuable feedback. Our families have sustained us with love, patience, and advice. We thank them, especially Susan and Julie, for being supportive as we worked and typed. Our work together has been greatly satisfying and enriching for both of us. A project of this magnitude would have been very difficult without a mutual respect and admiration between coauthors. Our friendship and professional esteem for each
Page
18
Preface xvii other’s efforts helped make this venture enjoyable throughout, and we each publicly acknowledge our thanks for the other’s contributions. We feel very blessed to have a collegial relationship with one another, and we hope and sense that this good fortune is reflected in our writing. We especially thank Phyllis Cohen, Edward Sears, Michael Penn, and those at Oxford University Press for their advice, support, and coordination of the book’s publication. The reviewers’ comments were extremely helpful. Any errors in the text are the responsibility of the authors, but a host of people around us should share in whatever compliments the text receives. There are too many to name individually, but we sincerely thank them all very much.
Page
19
This page intentionally left blank
Page
20
Contents 1 Mathematical Logic 3 1.1 The Formal Language of Sentential Logic 4 1.2 Truth and Sentential Logic 13 1.3 An Algebra for Sentential Logic 21 1.4 Application: Designing Computer Circuits 32 1.5 Natural Deductive Reasoning 46 1.6 The Formal Language of Predicate Logic 57 1.7 Fundamentals of Mathematical Proofs 69 Notes 80 2 Abstract Algebra 82 2.1 The Algebra of Sets 83 2.2 The Division Algorithm and Modular Addition 94 2.3 Modular Multiplication and Equivalence Relations 104 2.4 An Introduction to Groups 116 2.5 Dihedral Groups 129 2.6 Application: Check Digit Schemes 141 Notes 154 3 Number Theory 157 3.1 Prime Numbers 159 3.2 Application: Introduction to Coding Theory and Cryptography 169 3.3 From the Pythagorean Theorem to Fermat’s Last Theorem 185 3.4 Irrational Numbers and Fields 200 3.5 Polynomials and Transcendental Numbers 213 3.6 Mathematical Induction 227 Notes 238 4 Real Analysis 241 4.1 Analytic Geometry 242 4.2 Functions and Inverse Functions 256 4.3 Limits and Continuity 266