Write Your Own Proofs

in Set Theory and Discrete Mathematics

Amy Babich, Laura Person

• Publisher: Dover Publications
• Year: 2019
• Print ISBN: 9780486832814
• eBook ISBN: 9780486843575
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

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.

Chapter 1

Basic Logic

When I staggered out from sleep before dawn, I often found her studying calculus at the kitchen table, held in a cloud of Kool smoke like some radiant, unlikely Buddha.

“It’s a language,” she said of the math one morning, tapping her legal pad with the tip of a mechanical pencil. “I’ve never understood that. It’s a language that describes certain stuff very precisely.”

Mary Carr, Cherry

“I know what you’re thinking about,” said Tweedledum; “but it isn’t so, nohow.”

“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.”

Lewis Carroll, Through the Looking Glass

Introduction. Logic, or logical reasoning, is a system for drawing conclusions from premises. Premises are the input of a logical argument; the conclusion is the output. Whether the conclusion of an argument is true depends on the truth or falsity of the premises, and on whether or not the conclusion truly follows from the premises.

Since we propose to reason about mathematical objects, we will make use of a formal system of logical operators, called connectives. These connectives give us ways to combine statements to obtain other statements. They also give us rules for determining the truth or falsity of the new statements, based on that of the old statements.

Propositional logic concerns true and false statements and logical connectives. The connectives are as follows: not (¬), and (∧), or (∨), implies (⟶), and if and only if (⟷). Suppose that p is a statement. If p is true, then ¬p (not p) is false. If p is false, then ¬p is true. This tells us all we need to know about the lo...

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• 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!!!
• Credits
• Acknowledgments
• 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 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
• List of Symbols
• Bibliography
• Index
• About the Authors