Write Your Own Proofs: in Set Theory and Discrete Mathematics

by Amy Babich, Laura Person

Overview

Written by a pair of math teachers and based on their classroom notes and experiences, this introductory treatment of theory, proof techniques, and related concepts is designed for undergraduate courses. No knowledge of calculus is assumed, making it a useful text for students at many levels. The focus is on teaching students to prove theorems and write mathematical proofs so that others can read them.
Since proving theorems takes lots of practice, this text is designed to provide plenty of exercises. The authors break the theorems into pieces and walk readers through examples, encouraging them to use mathematical notation and write proofs themselves. Topics include propositional logic, set notation, basic set theory proofs, relations, functions, induction, countability, and some combinatorics, including a small amount of probability. The text is ideal for courses in discrete mathematics or logic and set theory, and its accessibility makes the book equally suitable for classes in mathematics for liberal arts students or courses geared toward proof writing in mathematics.

Product Details

ISBN-13:	9780486832814
Publisher:	Dover Publications
Publication date:	08/14/2019
Series:	Dover Books on Mathematics
Pages:	256
Sales rank:	1,049,390
Product dimensions:	5.90(w) x 8.80(h) x 0.60(d)

About the Author

Novelist and mathematician Amy Babich resides in Austin, Texas.
Laura Person is a Professor of Mathematics at SUNY Potsdam, a liberal arts university in northern New York.

Read an Excerpt

FOREWORD

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 we acknowledge the strong temptation to do so.

We have tried to include slightly more than enough material for a one- semester course in Set Theory and Logic or Discrete Mathematics. The focus is on teaching the student to prove theorems and to write down mathematical proofs so that other people can read them.

Proving theorems takes a lot of practice. This text is designed to give the student plenty of practice in writing proofs. In our own classrooms, we usually have the students write up the homework problems on the blackboard. This slows down the class to the students' level of understanding. In the early chapters (particularly Chapters 1 and 2) we often have students write a few proofs during class. We do this in order to forestall the statement that students didn't do the homework because they didn't know where to start. "Where to start" in writing a proof is at least half the content of this course. When students know where to start, they often write proofs correctly. A false start is the most common mistake.

Proving theorems used to be taught on a sink-or-swim basis. Those who swam were those with good mathematical habits — students who broke difficult propositions into pieces, played with new notation in order to learn it, constructed examples for themselves, and so on. Most students do not already have these habits. In our text we do some of this work for the student. We break theorems into pieces, and walk the student through examples and exercises. It is important to make sure that students get their hands dirty, use notation and write proofs themselves. Many students don't want to do this at first. They want to read, not write. They don't want to risk making mistakes. It's important to get them past this reluctance.

The material covered consists of prepositional logic, set notation, basic set theory proofs, relations, functions, induction, countability, and some combinatorics, including a very small amount of probability. In the last few chapters we give the student some practice in constructing functions on sets of sets and sets of functions. (Every new level of abstraction is confusing for beginners and must be practiced.) Working with such functions gets the student used to them. This whole course is really an exercise in becoming accustomed to working with mathematical notation and writing proofs based on definitions. For this reason, the instructor should not feel compelled to cover as much material as possible. The most important thing is that the students start to get comfortable with reading and writing mathematical proofs. In our own classrooms we have usually covered only four or five chapters in a semester, not all seven. But a fast-paced class of students with good backgrounds might cover all seven chapters.

We do not assume any knowledge of calculus on the part of the student. At some universities, successful completion of a calculus course is a prerequisite for entry into this class. This seems unnecessary. In the usual textbooks for this course, only two or three limits are computed in the course of the semester. We have omitted these limits, as we would like this course to be accessible to people who have not studied calculus.

We hope that you will find this book as effective and enjoyable to use as we have found it in trial versions.

Foreword B Words and Numbers: Mathematics, Writing, and the Two Cultures

A newspaper columnist recently wrote a rather facile article which divided educated human beings into "word people" and "number people." This is more or less the division that C. P. Snow called "the two cultures." On the one hand, we have language, literature, history, and philosophy; on the other hand, science and engineering. It is not generally recognized that mathematics sits squarely in the middle of this rather artificial division. Part of mathematics is computational, and involves manipulating numbers. And a very important part of mathematics, largely ignored by our pre-college educational system, involves words, reasoning, and proofs based on verbal definitions. This book is concerned primarily with the verbal side of mathematics.

There is reason to believe that people who study language, literature, philosophy, and suchlike things will be interested in the verbal side of mathematics. There is reason to expect that many "word people" actually have considerable talent for verbal mathematics. Mathematics has a history of significant contributions from "amateurs" — people who do something non-mathematical for a living. Leibniz was a diplomat; Fermat was a lawyer. Descartes, Leibniz, and Pascal are as famous for their philosophical writings as for their mathematics. The division of intellectuals into "two cultures" — the verbal and the numerical — is a twentieth-century phenomenon, and an unnecessary one. "Word people" have always made enormous contributions to mathematics. Unfortunately, under our current educational system, "word people" are unlikely ever to encounter the side of mathematics which will speak to them.

In the United States, the numerical/verbal, science/humanities division is also seen as a masculine/feminine division. Most women in the U.S. are classified as being on the verbal side. This is not an accident; it is, at least in part, the result of years of propaganda. "Girls can't do math," used to be a mantra in schools. When a girl did very well in mathematics, she was often told that, as she grew up and became womanly, she would be surpassed by boys in mathematics.

It is a very bad idea, in general, to promote the notion that women just can't do certain things. Since it is still primarily women who educate children, the result of such propaganda is that eventually neither men nor women are able to do the things in question. We used to hear, "Girls can't do math." Now we hear, "Americans can't do math."

There is another U.S. custom which has the unintended effect of frustrating the "verbal" student with an interest in mathematics. This is the convention that university mathematics education nearly always begins with the standard U.S. calculus class. The standard U.S. calculus class is not a proof class. The professor usually proves some theorems, and there are always proofs in the calculus book, but writing proofs is not the focus of the course. Since one cannot really understand proofs until one can write proofs correctly oneself, the more "verbal" student winds up feeling unsatisfied by the calculus class. There are many "verbal" students who take calculus, make a good grade, and then never look at mathematics again. They want something that the standard U.S. calculus class does not give them, although they are probably unable to say exactly what it is that they want. What they want, we believe, is an approach to mathematics through words, through definitions and proofs, through writing.

Thus, for "verbal people, it makes sense to begin the study of mathematics with an introduction to the language and conventions of proof. A student who has done the exercises in this book will be in a good position to study number theory, abstract algebra, or real analysis. A "verbal" student will probably be happier studying real analysis before calculus, rather than the other way around.

It is usual in U.S. mathematics departments to classify calculus as a freshman course and all proof classes as "advanced." This is primarily because the U.S. mathematics curriculum is designed for engineers and scientists. Calculus is taught early so that the student may start learning physics as soon as possible. Since many engineering and science students, in contrast to "verbal" students, are more comfortable with computations than with language, proof classes are relegated to junior or senior year. Moreover, successful completion of a calculus class is often a prerequisite for entry into a proof class. This requirement ignores the needs of the verbal student, because the verbal student is assumed to be uninterested in mathematics.

The authors of this book have taught this introductory proof class several times. We have found that the students who do best in the course are those who are most sensitive to language.

We would like to see an end to "the two cultures." We would like the language and conventions of mathematics to be part of the intellectual birthright of all students. We would like to stop reading in the newspaper that "Americans can't do math." And we would like to see a return to the notion that amateurs — novelists, diplomats, classicists, historians, lawyers, librarians and so forth — not only can enjoy mathematics, but can contribute significantly to it.

Mathematics belongs essentially not only to the numerical, but also to the verbal culture. Mathematics is free, and should belong to us all, not just to a privileged elite. We who speak the language of mathematics have no interest in being a privileged elite. One thing we like about mathematical notation is that it makes communication possible between mathematicians who have no other common language. Mathematical language is for letting people in, not for keeping people out. To learn mathematics is to love it. We would like more people to share this experience.

For this reason, the authors of this book do not assume that the reader has studied calculus. We think that there are many people (especially verbal people) who can enjoy calculus only after completing an introductory class like this one and a first course in real analysis. In the U.S. at the present time, such people generally stop studying mathematics either before or just after calculus, and never see a proof class at all. We hope that this situation will change. Currently, it often turns out that only a few undergraduate mathematics students like or do well in proof classes. It may be that some of the best proof students — the verbal students — are inadvertently being excluded. It might even turn out that girls and Americans are good at mathematics after all.

Foreword C Mathematical Proof as a Form of Writing

Lucidity is nine-tenths of style. Elisha said to the boys: If you do that again I will tell a big bear to come and eat you up. And they did. And he did. And it did. (It could do with the odd tenth.)

J.E. Littlewood, Littlewood's Miscellany

This book is about the experience of writing and reading mathematical proofs. A mathematical proof is a peculiar and amusing sort of written document. The language is formal. It sounds solemn and grandiose and absurd. It can also sound very elegant.

Of course, the way the proof looks or sounds is not the point. The point of the proof is the theorem it proves and the way it proves the theorem. The shape of the logical argument is what makes a proof elegant.

Mathematical writing tries to be as clear as possible. This is much harder than it might seem. Our language of sets, quantifiers, relations and functions is a great help in writing proofs and in understanding one another's proofs.

Since the goal of a mathematical proof is to show as clearly as possible how a piece of deductive reasoning works, it is not a flaw in mathematical writing to use the same sentence structure several times in a row. Variation in language just for its own sake should, in general, be avoided, especially by beginners. (Of course, beginners love to play with language. This isn't really a bad thing, and, even if it were, could not be helped. But be warned that some professors may find it more annoying than amusing when you give all your variables funny names and salt your proofs with such phrases as mutatis mutandis or per impossible.) The focus should be on the argument.

In some ways, mathematical writing is like poetry. A mathematician, like a poet, gets stuck and requires inspiration. Of course, it does no good to wait around for inspiration to strike; the only thing to do is to attempt to write the proof or the poem, or at least go through the motions. Here the mathematician may have the advantage over the poet that there are several known strategies to try (But then, the poet also has a bag of tricks.) Often known strategies don't seem to work. Then the mathematician or poet goes out for a walk (or even just as far as the next room) and an idea starts to form. The person has an idea, but doesn't yet know what the idea is. The hope is to put the idea into language that will clearly reveal its lineaments to the writer as well as to readers.

In other ways, mathematical proofs are like plays. They are rather formal plays, in which each character must be introduced before it (mathematical objects seem genderless) can play its role in the drama.

As readers of fiction and poetry we often wish that writers in general knew more about mathematics. For us, mathematics is a part of life. But characters in books (especially female characters) usually seem untouched by it. As women, we are grieved when female writers we like seem to feel that mathematics is masculine, or boring, or "linear." Mathematics is none of these things.

While we think it inadvisable for the beginner to write proofs in the style, say, of S.J. Perelman, we would like to have read Perelman's mathematical pastiches, had he written any. We think that if more writers knew more verbal mathematics, some entertaining books might be written.

Writers of novels, poems, histories, and so on may find that they enjoy writing mathematical proofs. Writers may find that their mathematics and their nonmathematical writing enrich each other. But there are some people who hate to write, in some cases because their native language is not English and they make mistakes, forgetting articles, misspelling words, mixing up singular and plural. For these people, we have good news.

In many ways, mathematical English is much easier to write than conversational, journalistic, or literary English. Mathematical English uses a limited vocabulary. We introduce variables and write formally and redundantly. This means that a mathematician who knows no English may very well understand a talk in mathematical English, and even learn a few English phrases in the course of it. (It would be hard, for example, to avoid learning the phrase "such that.") It is very common for people to write mathematical papers in a language (often English) that is not their own. Therefore, nobody cares very much about small grammatical solecisms such as misuse of articles or omission of plural endings. All anybody really cares about is understanding the proof. If the specifically mathematical parts of the language are correct, the proof will be understood.

(Continues…)

---

Excerpted from "Write Your Own Proofs"
by .
Copyright © 2005 Amy Babich and Laura Person.
Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---

Table of 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!
1. Basic Logic
2. Proving Theorems About Sets
3. Cartesian Products and Relations
4. Functions
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 this 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
Bibliography
Index
List of Symbols