WRITEYOUROWNPROOFS
WRITEYOUROWNPROOFS
IN SET THEORY AND
DISCRETE MATHEMATICS
AMY BABICH AND
LAURA PERSON
DOVER PUBLICATIONS, INC.
MINEOLA, NEW YORK
Credits appear on page xxxii, which should be considered
an extension of the copyright page.
Copyright
Copyright © 2005 by Amy Babich and Laura Person
All rights reserved.
Bibliographical Note
This Dover edition, first published in 2019, is a slightly corrected republication of the work originally published by Zinka Press, Wayne, Pennsylvania, in 2005.
Library of Congress Cataloging-in-Publication Data
Names: Babich, Amy, author. | Person, Laura (Laura J.), author.
Title: Write your own proofs in set theory and discrete mathematics / Amy Babich and Laura Person.
Description: Dover edition. | Mineola, New York : Dover Publications, 2019. | Slightly corrected republication of the work originally published: Wayne, Pennsylvania : Zinka Press, 2005.
Identifiers: LCCN 2018061317 | ISBN 9780486832814 | ISBN 0486832813
Subjects: LCSH: Set theory—Textbooks. | Proof theory—Textbooks. | Logic, Symbolic and mathematical—Textbooks. | Computer science—Mathematics—Textbooks.
Classification: LCC QA248.3 .B23 2019 | DDC 511.3/22—dc23
LC record available at https://lccn.loc.gov/2018061317
Manufactured in the United States by LSC Communications
83281301 2019
In memoriam
David Spellman
(1954—1997)
Contents
Foreword A This Book and How to Use It
Foreword B Words and Numbers: Mathematics, Writing, and the Two Cultures
Foreword C Mathematical Proof as a Form of Writing
Foreword D Amazing Secrets of Professional Mathematicians REVEALED!!!
3 Cartesian Products and Relations
5 Induction, Power Sets, and Cardinality
6 Introduction to Combinatorics
7 Derangements and Other Entertainments
Afterword A A Few Words on the History of Set Theory
Afterword B A Little Bit About Limits
Afterword C Why No Answers In The Back of the Book?
Afterword D: What next? Concise Synopses of Selected College Mathematics Courses
Dr. Spencer’s Mantra for the Relief of Anxiety that Accompanies Attempts to Create and Write Proofs
Foreword A
This Book and How to Use It
About twenty years ago, American universities began to offer a mathematics course (called variously Set Theory and Logic or Discrete Mathematics, at different institutions) designed to serve as an introduction to mathematical proof. The usual assigned textbook for this course is either Chapter Zero of a graduate mathematics text, or one of the recent textbooks on Discrete Mathematics (by Grimaldi, Epp, Rosen, et al.). Neither choice of textbook is ideal for the novice professor assigned to teach this course. Chapter Zero of a graduate textbook is mere outline, with very few exercises, and the Discrete Mathematics books are all much too large for a one-semester course. Nearly always, the rookie instructor for this course must make her/his own class notes and supplementary problem sets. This takes time and effort, and the first-time instructor is often short of both.
Like other instructors of this course, we made our own class notes. We also traded our notes back and forth, making use of each other’s ideas. We used the first half of Introduction to Set Theory and Logic by Lin and Lin, as a model, but we changed it to suit our purposes. We did not find that the section on deductive reasoning (featuring syllogisms, Modus Ponens, and Modus Tollens) helped our students to write proofs, so we jettisoned it. There is a great deal of material in this sort of course, and we move through it slowly, at the students’ pace. We omit whatever we don’t find helpful.
We used these class notes for several semesters, changing them as we went along. The main change that occurred with time and use was the addition of examples and exercises in sections that the students found difficult. The notes, even in their most rudimentary form, were noticeably more effective than our old textbooks for helping students to learn. Students said that they liked the notes, but wished that they were a real book.
So we set about turning the notes into a book. (This turned out to be a lot of trouble.) We tried to write down the explanations we gave orally in class. These appear as πRemarks” in the text. The Remarks are there to help whoever may find them helpful. If a Remark seems unhelpful or confusing, feel free to ignore it. The Remarks are optional aids to understanding.
We have been at some pains not to include all possible material in this text. When writing a book of this sort, one quickly comes to understand why the available books (by Epp, Grimaldi, Rosen, et al.) are so huge. The material here has very natural connections to number theory, probability, graph theory, complexity theory, transfinite arithmetic, and so on. But we do not wish to include an introductory course in each of these subjects, although