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 propositional 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 requiement 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