Undergraduate Texts in Mathematics UTM Reading,Writing, and Proving A Closer Look at mathematics Second Edition Springer
Preface You are probably about to teach or take a"first course in proof techniques,"or maybe you just want to learn more about mathematics.No matter what the reason,a student who wishes to learn the material in this book likes mathematics and we hope to keep it that way.At this point,students have an intuitive sense of why things are true,but not the exposure to the detailed and critical thinking necessary to survive in the mathematical world.We have written this book to bridge this gap. In our experience,students beginning this course have little training in rigorous mathematical reasoning;they need guidance.At the end,they are where they should be;on their own.Our aim is to teach the students to read,write,and do mathematics independently,and to do it with clarity,precision,and care.If we can maintain the enthusiasm they have for the subject,or even create some along the way,our book has done what it was intended to do. Reading.This book was written for a course we teach to first-and second-year college students.The style is informal.A few problems require calculus,but these are identified as such.Students will also need to participate while reading proofs, prodded by questions (such as,"Why?").Many detailed examples are provided in each chapter.Since we encourage the students to draw pictures,we include many il- lustrations as well.Exercises,designed to teach certain concepts,are also included. These can be used as a basis for class discussion,or preparation for the class.Stu- dents are expected to solve the exercises before moving on to the problems.Com- plete solutions to all of the exercises are provided at the end of each chapter.Prob- lems of varying degrees of difficulty appear at the end of each chapter.Some prob- lems are simply proofs of theorems that students are asked to read and summarize; others supply details to statements in the text.Though many of the remaining prob- lems are standard,we hope that students will solve some of the unique problems presented in each chapter. Writing.The bad news is that it is not easy to write a proof well.The good news is that with proper instruction,students quickly learn the basics of writing.We try to write in a way that we hope is worthy of imitation,but we also provide students vii
Preface You are probably about to teach or take a “first course in proof techniques,” or maybe you just want to learn more about mathematics. No matter what the reason, a student who wishes to learn the material in this book likes mathematics and we hope to keep it that way. At this point, students have an intuitive sense of why things are true, but not the exposure to the detailed and critical thinking necessary to survive in the mathematical world. We have written this book to bridge this gap. In our experience, students beginning this course have little training in rigorous mathematical reasoning; they need guidance. At the end, they are where they should be; on their own. Our aim is to teach the students to read, write, and do mathematics independently, and to do it with clarity, precision, and care. If we can maintain the enthusiasm they have for the subject, or even create some along the way, our book has done what it was intended to do. Reading. This book was written for a course we teach to first- and second-year college students. The style is informal. A few problems require calculus, but these are identified as such. Students will also need to participate while reading proofs, prodded by questions (such as, “Why?”). Many detailed examples are provided in each chapter. Since we encourage the students to draw pictures, we include many illustrations as well. Exercises, designed to teach certain concepts, are also included. These can be used as a basis for class discussion, or preparation for the class. Students are expected to solve the exercises before moving on to the problems. Complete solutions to all of the exercises are provided at the end of each chapter. Problems of varying degrees of difficulty appear at the end of each chapter. Some problems are simply proofs of theorems that students are asked to read and summarize; others supply details to statements in the text. Though many of the remaining problems are standard, we hope that students will solve some of the unique problems presented in each chapter. Writing. The bad news is that it is not easy to write a proof well. The good news is that with proper instruction, students quickly learn the basics of writing. We try to write in a way that we hope is worthy of imitation, but we also provide students vii
viii Preface with "tips"on writing,ranging from the (what should be)obvious to the insider's preference ("Don't start a sentence with a symbol."). Proving.How can someone learn to prove mathematical results?There are many theories on this.We believe that learning mathematics is the same as learning to play an instrument or learning to succeed at a particular sport.Someone must provide the background:the tips,information on the basic skills,and the insider's"know-how." Then the student has to practice.Musicians and athletes practice hours a day,and it's not surprising that most mathematicians do,too.We will provide students with the background;the exercises and problems are there for practice.The instructor observes,guides,teaches and,if need be,corrects.As with anything else,the more a student practices,the better she or he will become at solving problems. Using this book.What should be in a book like this one?Even a quick glance at other texts on this subject will tell you that everyone agrees on certain topics:logic, quantifiers,basic set theoretic concepts,mathematical induction,and the definition and properties of functions.The depth of coverage is open to debate,of course.We try to cover logic and quantifiers fairly quickly,because we believe that students can only fully appreciate the fundamentals of mathematics when they are applied to interesting problems. What is also apparent is that after these essential concepts,everyone disagrees on what should be included.Even we prefer to vary our approach depending on our students.We have tried to provide enough material for a flexible approach. .The Minimal Approach.If you need only the basics,cover Chapters 1-18.(If you assume the well ordering principle,or decide to accept the principle of mathe- matical induction without proof,you can also omit Chapters 12 and 13.) .The Usual Approach.This approach includes Chapters 1-18 and Chapters 21- 24.(This is easily doable in a standard semester,if the class meets three hours per week.) .The Algebra Approach.For an algebraic slant to the course,cover Chapters 1-18, omitting Chapter 13 and including Chapters 27 and 28. The Analysis Approach.For a slant toward analysis,cover Chapters 1-23.(In- clude Chapter 24,if time allows.This is what we usually cover in our course.) Include as much material from Chapters 25 and 26 as time allows.Students usu- ally enjoy an introduction to metric spaces. Projects.We have included projects intended to let students demonstrate what they can do when they are on their own.We indicate prerequisites for each project,and have tried to vary them enough that they can be assigned throughout the semester.The results in these projects come from different areas that we find particularly interesting.Students can be guided to a project at their level.Since there are open-ended parts in each project,students can take these projects as far as they want.We usually encourage the students to work on these in groups. Notation.A word about some of our symbols is in order here.In an attempt to make this book user-friendly,we indicate the end of a proof with the well-known symbol The end of an example or exercise is designated by O.If a problem is used later in the text,we designate it by Problem".We also have a fair number
viii Preface with “tips” on writing, ranging from the (what should be) obvious to the insider’s preference (“Don’t start a sentence with a symbol.”). Proving. How can someone learn to prove mathematical results? There are many theories on this. We believe that learning mathematics is the same as learning to play an instrument or learning to succeed at a particular sport. Someone must provide the background: the tips, information on the basic skills, and the insider’s “know-how.” Then the student has to practice. Musicians and athletes practice hours a day, and it’s not surprising that most mathematicians do, too. We will provide students with the background; the exercises and problems are there for practice. The instructor observes, guides, teaches and, if need be, corrects. As with anything else, the more a student practices, the better she or he will become at solving problems. Using this book. What should be in a book like this one? Even a quick glance at other texts on this subject will tell you that everyone agrees on certain topics: logic, quantifiers, basic set theoretic concepts, mathematical induction, and the definition and properties of functions. The depth of coverage is open to debate, of course. We try to cover logic and quantifiers fairly quickly, because we believe that students can only fully appreciate the fundamentals of mathematics when they are applied to interesting problems. What is also apparent is that after these essential concepts, everyone disagrees on what should be included. Even we prefer to vary our approach depending on our students. We have tried to provide enough material for a flexible approach. • The Minimal Approach. If you need only the basics, cover Chapters 1–18. (If you assume the well ordering principle, or decide to accept the principle of mathematical induction without proof, you can also omit Chapters 12 and 13.) • The Usual Approach. This approach includes Chapters 1–18 and Chapters 21— 24. (This is easily doable in a standard semester, if the class meets three hours per week.) • The Algebra Approach. For an algebraic slant to the course, cover Chapters 1–18, omitting Chapter 13 and including Chapters 27 and 28. • The Analysis Approach. For a slant toward analysis, cover Chapters 1–23. (Include Chapter 24, if time allows. This is what we usually cover in our course.) Include as much material from Chapters 25 and 26 as time allows. Students usually enjoy an introduction to metric spaces. • Projects. We have included projects intended to let students demonstrate what they can do when they are on their own. We indicate prerequisites for each project, and have tried to vary them enough that they can be assigned throughout the semester. The results in these projects come from different areas that we find particularly interesting. Students can be guided to a project at their level. Since there are open-ended parts in each project, students can take these projects as far as they want. We usually encourage the students to work on these in groups. • Notation. A word about some of our symbols is in order here. In an attempt to make this book user-friendly, we indicate the end of a proof with the well-known symbol ut. The end of an example or exercise is designated by . If a problem is used later in the text, we designate it by Problem#. We also have a fair number
Preface ix of"nonproofs."These are "proofs"with errors,gaps,or both;the students are asked to find the flaw and to fix it.We conclude such "proofs"with the symbol Every other symbol will be defined when we introduce you to it.Definitions are incorporated in the text for ease of reading and the terms defined are given in boldface type. Presenting.We also hope that students will make the transition to thinking of themselves as members of a mathematical community.We encourage the students we have in this class to attend talks,give talks,go to conferences,read mathemat- ical books,watch mathematical movies,read journal articles,and talk with their colleagues about the things in this course that interest them.Our (incomplete,but lengthy)list of references should serve a student well as a starting point.Each of the projects works well as the basis of a talk for students,and we have included some background material in each section.We begin the chapter on projects with some tips on speaking about mathematics. What's new in this edition.We have made many changes to the first edition.First, all exercises now have solutions and every chapter,except for the first,has at least twenty problems of varying difficulty.As a result,the text has now roughly twice as many problems than before.As in the first edition,definitions are incorporated in the text.In this edition,all definitions newly introduced in a chapter appear again in a section with formal statements of the new definitions.We have included a detailed description of definitions by recursion and a recursion theorem.We've added axioms of set theory to the appendix.We have included new projects:one on the axiom of choice and one on complex numbers.We have added some interesting pieces to two projects,Picture Proofs and The Best Number of All(and Some Other Pretty Good Ones). Some chapters have been changed or added.The first edition's Chapter 12,which required more of students than previous chapters,has been broken into two chapters, now enumerated Chapters 12 and 13.If the instructor wishes,it is possible to simply assume the results in Chapter 13 and omit the chapter.We have also included a new chapter,Chapter 24,on the Cantor-Schroder-Bernstein theorem.We feel that this is the proper culmination to Chapters 21-23 and a wonderful way to end the course, but be forewarned that it is not an easy chapter. Thanks to many of you who used the text,we were able to pinpoint areas where we could improve many of our explanations,provide more motivation,or present a different perspective.Our goal was to find simpler,more precise explanations,and we hope that we have been successful.One new feature of this text that may interest instructors of the course:We have written solutions to every third problem.These are available on our website (see below). Of course,we have updated our reference list,made corrections to errors that appeared in the first version,and,most likely,introduced new errors in the second version.We hope you will send us corrections to errors that you find in the text,as well as any suggestions you have for improvement. We hope that through reading,writing,proving,and presenting mathematics,we can produce students who will make good colleagues in every sense of the word
Preface ix of “nonproofs.” These are “proofs” with errors, gaps, or both; the students are asked to find the flaw and to fix it. We conclude such “proofs” with the symbol ut? . Every other symbol will be defined when we introduce you to it. Definitions are incorporated in the text for ease of reading and the terms defined are given in boldface type. Presenting. We also hope that students will make the transition to thinking of themselves as members of a mathematical community. We encourage the students we have in this class to attend talks, give talks, go to conferences, read mathematical books, watch mathematical movies, read journal articles, and talk with their colleagues about the things in this course that interest them. Our (incomplete, but lengthy) list of references should serve a student well as a starting point. Each of the projects works well as the basis of a talk for students, and we have included some background material in each section. We begin the chapter on projects with some tips on speaking about mathematics. What’s new in this edition. We have made many changes to the first edition. First, all exercises now have solutions and every chapter, except for the first, has at least twenty problems of varying difficulty. As a result, the text has now roughly twice as many problems than before. As in the first edition, definitions are incorporated in the text. In this edition, all definitions newly introduced in a chapter appear again in a section with formal statements of the new definitions. We have included a detailed description of definitions by recursion and a recursion theorem. We’ve added axioms of set theory to the appendix. We have included new projects: one on the axiom of choice and one on complex numbers. We have added some interesting pieces to two projects, Picture Proofs and The Best Number of All (and Some Other Pretty Good Ones). Some chapters have been changed or added. The first edition’s Chapter 12, which required more of students than previous chapters, has been broken into two chapters, now enumerated Chapters 12 and 13. If the instructor wishes, it is possible to simply assume the results in Chapter 13 and omit the chapter. We have also included a new chapter, Chapter 24, on the Cantor–Schroder–Bernstein theorem. We feel that this ¨ is the proper culmination to Chapters 21–23 and a wonderful way to end the course, but be forewarned that it is not an easy chapter. Thanks to many of you who used the text, we were able to pinpoint areas where we could improve many of our explanations, provide more motivation, or present a different perspective. Our goal was to find simpler, more precise explanations, and we hope that we have been successful. One new feature of this text that may interest instructors of the course: We have written solutions to every third problem. These are available on our website (see below). Of course, we have updated our reference list, made corrections to errors that appeared in the first version, and, most likely, introduced new errors in the second version. We hope you will send us corrections to errors that you find in the text, as well as any suggestions you have for improvement. We hope that through reading, writing, proving, and presenting mathematics, we can produce students who will make good colleagues in every sense of the word
Preface 米米米 Acknowledgments.Writing a book is a long process,and we wish to express our gratitude to those who have helped us along the way.We are,of course,grateful to the students at Bucknell University who suffered through the early versions of the manuscript,as well as those who used later versions.Their comments,suggestions, and detection of errors are most appreciated.We thank Andrew Shaffer for help with the illustrations.We also wish to express our thanks to our colleagues and friends, Gregory Adams,Thomas Cassidy,David Farmer,and Paul McGuire,for helpful conversations.We are particularly grateful to Raymond Mortini for his willingness to carefully read (and criticize)the entire text.The book is surely better for it.We also wish to thank our(former)student editor,Brad Parker.We simply cannot over- state the value of Brad's careful reading,insightful comments,and his suggestions for better prose.We thank Universitat Bern,Switzerland for support provided dur- ing our sabbaticals.Finally,we thank Hannes and Madeleine Daepp for putting up with infinitely many dinner conversations about this text. For the second edition,we wish to thank professors Paul Stanford at The Univer- sity of Texas at Dallas,Matthew Daws at the University of Leeds,Raymond Boute at Ghent University,John M.Lee at the University of Washington,and Buster Thelen for many thoughtful suggestions.In addition to our colleagues who helped us with the first edition,we are grateful to John Bourke,Emily Dryden,and Allen Schweins- berg for their helpful comments.We wish to thank Peter McNamara,in particular, for spotting errors and inconsistencies,for suggestions for other references,and for pointing out sections that were potentially confusing for students.Again,we are grateful to all our colleagues and our students who have helped us to make this a better text. 米米* We thank Hannes Daepp for creating a website to accompany the text.This web- site contains complete solutions to all problems numbered 3n,where n is a positive integer.It also contains corrections to both editions of the text. http://www.facstaff.bucknell.edu/udaepp/readwriteprove/ Lewisburg,PA Ulrich Daepp December 2010 Pamela Gorkin Authors'e-mails:udaepp@bucknell.edu and pgorkin @bucknell.edu
x Preface *** Acknowledgments. Writing a book is a long process, and we wish to express our gratitude to those who have helped us along the way. We are, of course, grateful to the students at Bucknell University who suffered through the early versions of the manuscript, as well as those who used later versions. Their comments, suggestions, and detection of errors are most appreciated. We thank Andrew Shaffer for help with the illustrations. We also wish to express our thanks to our colleagues and friends, Gregory Adams, Thomas Cassidy, David Farmer, and Paul McGuire, for helpful conversations. We are particularly grateful to Raymond Mortini for his willingness to carefully read (and criticize) the entire text. The book is surely better for it. We also wish to thank our (former) student editor, Brad Parker. We simply cannot overstate the value of Brad’s careful reading, insightful comments, and his suggestions for better prose. We thank Universitat Bern, Switzerland for support provided dur- ¨ ing our sabbaticals. Finally, we thank Hannes and Madeleine Daepp for putting up with infinitely many dinner conversations about this text. For the second edition, we wish to thank professors Paul Stanford at The University of Texas at Dallas, Matthew Daws at the University of Leeds, Raymond Boute at Ghent University, John M. Lee at the University of Washington, and Buster Thelen for many thoughtful suggestions. In addition to our colleagues who helped us with the first edition, we are grateful to John Bourke, Emily Dryden, and Allen Schweinsberg for their helpful comments. We wish to thank Peter McNamara, in particular, for spotting errors and inconsistencies, for suggestions for other references, and for pointing out sections that were potentially confusing for students. Again, we are grateful to all our colleagues and our students who have helped us to make this a better text. *** We thank Hannes Daepp for creating a website to accompany the text. This website contains complete solutions to all problems numbered 3n, where n is a positive integer. It also contains corrections to both editions of the text. http://www.facstaff.bucknell.edu/udaepp/readwriteprove/ Lewisburg, PA Ulrich Daepp December 2010 Pamela Gorkin Authors’ e-mails: udaepp@bucknell.edu and pgorkin@bucknell.edu
Contents Preface............ vii 1 The How,When,and Why of Mathematics........................ Spotlight:George Polya.......................................... 8 Tips on Doing Homework..... 11 2 Logically Speaking........... 13 3 Introducing the Contrapositive and Converse..................... 25 4 Set Notation and Quantifiers 33 Tips on Quantification....... 45 5 Proof Techniques......... 47 Tips on Definitions........ 56 6 Sets..… 59 Spotlight:Paradoxes........ 67 7 perations on Sets............................................. 73 6 More on Operations on Sets..................................... 81 9 The Power Set and the Cartesian Product......................... 89 Tips on Writing Mathematics .................................... 98 10 Relations....……… 101 Tips on Reading Mathematics.......... 110 11 Partitions.......... .111 Tips on Putting It All Together 。。。 ..119 120 rder in the Reals.......................121 xi
Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 The How, When, and Why of Mathematics . . . . . . . . . . . . . . . . . . . . . . . . 1 Spotlight: George Polya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 ´ Tips on Doing Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Logically Speaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Introducing the Contrapositive and Converse . . . . . . . . . . . . . . . . . . . . . 25 4 Set Notation and Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Tips on Quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5 Proof Techniques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Tips on Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6 Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Spotlight: Paradoxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7 Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8 More on Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9 The Power Set and the Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . . . 89 Tips on Writing Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 10 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Tips on Reading Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 11 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Tips on Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 12 Order in the Reals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 xi
xii Contents 13 Consequences of the Completeness of R................. ...133 Tips:You Solved It.Now What?........................... ..140 14 Functions,Domain,and Range..................................143 Spotlight:The Definition of Function............................... 151 15 Functions,One-to-One,and Onto................................ 157 16 nverses.....167 17 Images and Inverse Images......................................181 Spotlight:Minimum or Infimum?.................................. 187 18 Mathematical Induction........................................193 19 Sequences.… 209 20 Convergence of Sequences of Real Numbers....................... 223 21 Equivalent Sets................................................ 235 22 Finite Sets and an Infinite Set....................................243 23 Countable and Uncountable Sets.................................251 24 The Cantor-Schroder-Bernstein Theorem........................ 261 Spotlight:The Continuum Hypothesis.............................. 270 25 Metric Spaces...............……… 277 26 Getting to Know Open and Closed Sets........................... 289 27 Modular Arithmetic............................................301 28Fermat's Little Theorem........................................315 Spotlight:Public and Secret Research..............................320 29 Projects.......................................................325 Tips on Talking about Mathematics................................325 29.1 Picture Proofs.............................................327 29.2 The Best Number of All (and Some Other Pretty Good Ones)......330 29.3 Set Constructions..................332 29.4 Rational and Irrational Numbers........... .334 29.5 rrationality of e andπ......… 336 29.6 A Complex Project................338 29.7 When Does f-l=1/f?..............342 29.8 Pascal's Triangle........................................... 343 29.9 The Cantor Set.......................346
xii Contents 13 Consequences of the Completeness of R. . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Tips: You Solved It. Now What? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 14 Functions, Domain, and Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Spotlight: The Definition of Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 15 Functions, One-to-One, and Onto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 16 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 17 Images and Inverse Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Spotlight: Minimum or Infimum? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 18 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 19 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 20 Convergence of Sequences of Real Numbers . . . . . . . . . . . . . . . . . . . . . . . 223 21 Equivalent Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 22 Finite Sets and an Infinite Set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 23 Countable and Uncountable Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 24 The Cantor–Schroder–Bernstein Theorem ¨ . . . . . . . . . . . . . . . . . . . . . . . . 261 Spotlight: The Continuum Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 25 Metric Spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 26 Getting to Know Open and Closed Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 27 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 28 Fermat’s Little Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Spotlight: Public and Secret Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 29 Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 Tips on Talking about Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 29.1 Picture Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 29.2 The Best Number of All (and Some Other Pretty Good Ones). . . . . . 330 29.3 Set Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 29.4 Rational and Irrational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 29.5 Irrationality of e and π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 29.6 A Complex Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 29.7 When Does f −1 = 1/ f ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 29.8 Pascal’s Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 29.9 The Cantor Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
Contents xi甜 29.10 The Cauchy-Bunyakovsky-Schwarz Inequality.................349 29.11 Algebraic Numbers........................................351 29.12 The Axiom of Choice...................................... .353 29.13 The RSACode............................................357 Spotlight:Hilbert's Seventh Problem...............................359 dix......................... Algebraic Properties of R 363 Order Properties of R.............. .364 Axioms of Set Theory 364 Polya's List ............ ,366 References................ 367 Index .371
Contents xiii 29.10 The Cauchy–Bunyakovsky–Schwarz Inequality . . . . . . . . . . . . . . . . . 349 29.11 Algebraic Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 29.12 The Axiom of Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 29.13 The RSA Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 Spotlight: Hilbert’s Seventh Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 Algebraic Properties of R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 Order Properties of R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Axioms of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Polya’s List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 ´ References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
Chapter 1 The How,When,and Why of Mathematics What is mathematics?Many people think of mathematics (incorrectly)as addition, subtraction,multiplication,and division of numbers.Those with more mathematical training may think of it as dealing with algorithms.But most professional mathe- maticians think of it as much more than that.While we certainly hope that our students will perform algorithms correctly,what we really want is for them to un- derstand three things:how you do something,why it works,and when it works The problems we present to you in this book concentrate on these three goals.If this is the first time you have been asked to prove theorems,you may find this to be quite a challenge.Not only will you be learning how to solve the problem,you will also be learning how to write up the solution.The necessary definitions and background to understand a problem,as well as a general plan of attack,will always be presented in the text.It's up to you to spend the time reading,trying various ap- proaches,rereading,and reapproaching.You will probably be spending more time on fewer exercises than you ever have before.While you are now beyond the stage of being given steps to follow and practice,there are general rules that can assist you in your transition to doing higher mathematics.Many people have written about this subject before.The classic text on how to approach a problem is a wonderful book called How to Solve It by George Polya,[84]. In his text,Polya gives a list of guidelines for solving mathematical problems.He calls his suggestions"the list."We have included the original in the Appendix on page 366.This list has served as a guide for several generations of mathematicians, and we suggest that you let it guide you as well.Here's a closer look at"the list" with some 21st-century modifications. First."Understanding the problem."Easier said than done,of course.What should you do?Make sure you know what all the words mean.You may need to look something up in this book,or you may need to use another book.Look at the statement to figure out carefully what you are given and what you are supposed to figure out.If a picture will help,draw it.Will you be proving something?What? Will you have to obtain an example?Of what?Check all conditions.Will you have to show that something is false?Once you understand what you have to do,you can move on to the next step. U.Daepp and P.Gorkin,Reading.Writing,and Proving:A Closer Look at Mathematics, Undergraduate Texts in Mathematics,DOI 10.1007/978-1-4419-9479-0_1, Springer Science+Business Media,LLC 2011
Chapter 1 The How, When, and Why of Mathematics What is mathematics? Many people think of mathematics (incorrectly) as addition, subtraction, multiplication, and division of numbers. Those with more mathematical training may think of it as dealing with algorithms. But most professional mathematicians think of it as much more than that. While we certainly hope that our students will perform algorithms correctly, what we really want is for them to understand three things: how you do something, why it works, and when it works. The problems we present to you in this book concentrate on these three goals. If this is the first time you have been asked to prove theorems, you may find this to be quite a challenge. Not only will you be learning how to solve the problem, you will also be learning how to write up the solution. The necessary definitions and background to understand a problem, as well as a general plan of attack, will always be presented in the text. It’s up to you to spend the time reading, trying various approaches, rereading, and reapproaching. You will probably be spending more time on fewer exercises than you ever have before. While you are now beyond the stage of being given steps to follow and practice, there are general rules that can assist you in your transition to doing higher mathematics. Many people have written about this subject before. The classic text on how to approach a problem is a wonderful book called How to Solve It by George Polya, [84]. ´ ´ calls his suggestions “the list.” We have included the original in the Appendix on and we suggest that you let it guide you as well. Here’s a closer look at “the list” First. “Understanding the problem.” Easier said than done, of course. What look something up in this book, or you may need to use another book. Look at the figure out. If a picture will help, draw it. Will you be proving something? What? Will you have to obtain an example? Of what? Check all conditions. Will you have to show that something is false? Once you understand what you have to do, you can move on to the next step. 1 should you do? Make sure you know what all the words mean. You may need to page 366. This list has served as a guide for several generations of mathematicians, statement to figure out carefully what you are given and what you are supposed to with some 21st-century modifications. © Springer Science+Business Media, LLC 2011 U. Daepp and P. Gorkin, Reading, Writing, and Proving: A Closer Look at Mathematics, In his text, Polya gives a list of guidelines for solving mathematical problems. He Undergraduate Texts in Mathematics, DOI 10.1007/978-1-4419-9479-0_1
2 I The How,When,and Why of Mathematics Second."Devising a plan."How will you attack the problem?At this point,you understand what must be done (because you have completed Step 1).Have you seen something like it before?If you haven't looked over class notes,haven't read the text,or haven't done the previous homework assignments,the odds are slim that you have seen anything that will be helpful.Do all that first.Look over the text with the problem in mind,read over your notes with the problem in your head,look at previous exercises and theorems that sound similar.Maybe you can use some of the ideas in the proof of a theorem,or maybe you can use a previous homework problem.Mathematics builds on itself and the problems in the text will also.If you are truly stuck,try to answer a simpler,similar question.Once you decide on a method of approach,try it out. Third."Carrying out the plan."Solve the problem.Look at your solution.Is each sentence true?Sometimes it is difficult to catch an error right after you have "found a solution."Put the problem down and come back to it a few hours later.Is each sentence still true? Fourth."Looking back."Polya suggests checking the result and the argument,or even looking for a different proof.If you are allowed(check with your teacher),one really good way to check a proof is to give it to someone else.You can present it to friends.Even if they don't understand a word you are saying,sometimes saying it out loud in a coherent manner will allow you to recognize an error you can't spot when you are reading.If you are permitted to work together,switch proofs and ask your partner for criticism of your proof. When you are convinced that your argument is correct,it is time to write up a correct and neat solution to the problem. Here is an example of the Polya method at work in mathematics;we will decipher a message.A cipher is a system that is used to hide the meaning of a message by replacing the letters of the alphabet by other letters or symbols. Exercise 1.1.The following message is encoded by a shift of the alphabet;that is, every letter is replaced by another one that has been shifted n places further down the alphabet.Once we reach the end of the alphabet,we start over.For instance,if n were7,we would make the replacements a→h,b→i,..,s→z,t→a,..Now the exercise:What does the message below say? PDEO AJYKZEJC WHCKNEPDI EO YWHHAZ W YWAOWN YELDAN. EP EO RANU AWOU PK XNAWG.NECDP? Let's use the ideas from Polya's list to solve this.If you have solved problems like this before,it might be a better exercise for you to try on your own to see how this fits Polya's method before you read on. 1."Understanding the problem."Each sequence of letters with no blank space be- tween the letters represents one word.Each letter is shifted by the same number of places:namely,n.So n is the unknown in this problem and it is what we need to find.Once we know the value of n,we can decipher the whole message.In addition,once we know the meaning of one letter,we can find the value for n
2 1 The How, When, and Why of Mathematics Second. “Devising a plan.” How will you attack the problem? At this point, you understand what must be done (because you have completed Step 1). Have you seen something like it before? If you haven’t looked over class notes, haven’t read the text, or haven’t done the previous homework assignments, the odds are slim that you have seen anything that will be helpful. Do all that first. Look over the text with the problem in mind, read over your notes with the problem in your head, look at previous exercises and theorems that sound similar. Maybe you can use some of the ideas in the proof of a theorem, or maybe you can use a previous homework problem. Mathematics builds on itself and the problems in the text will also. If you are truly stuck, try to answer a simpler, similar question. Once you decide on a method of approach, try it out. Third. “Carrying out the plan.” Solve the problem. Look at your solution. Is each sentence true? Sometimes it is difficult to catch an error right after you have “found a solution.” Put the problem down and come back to it a few hours later. Is each sentence still true? Fourth. “Looking back.” Polya suggests checking the result and the argument, or ´ even looking for a different proof. If you are allowed (check with your teacher), one really good way to check a proof is to give it to someone else. You can present it to friends. Even if they don’t understand a word you are saying, sometimes saying it out loud in a coherent manner will allow you to recognize an error you can’t spot when you are reading. If you are permitted to work together, switch proofs and ask your partner for criticism of your proof. When you are convinced that your argument is correct, it is time to write up a correct and neat solution to the problem. Here is an example of the Polya method at work in mathematics; we will decipher ´ a message. A cipher is a system that is used to hide the meaning of a message by replacing the letters of the alphabet by other letters or symbols. Exercise 1.1. The following message is encoded by a shift of the alphabet; that is, every letter is replaced by another one that has been shifted n places further down the alphabet. Once we reach the end of the alphabet, we start over. For instance, if n were 7, we would make the replacements a → h, b → i, ..., s → z, t → a, .... Now the exercise: What does the message below say? PDEO AJYKZEJC WHCKNEPDI EO YWHHAZ W YWAOWN YELDAN. EP EO RANU AWOU PK XNAWG, NECDP? Let’s use the ideas from Polya’s list to solve this. If you have solved problems ´ like this before, it might be a better exercise for you to try on your own to see how this fits Polya’s method before you read on. ´ 1. “Understanding the problem.” Each sequence of letters with no blank space between the letters represents one word. Each letter is shifted by the same number of places: namely, n. So n is the unknown in this problem and it is what we need to find. Once we know the value of n, we can decipher the whole message. In addition, once we know the meaning of one letter, we can find the value for n