About This Course

This book is a first course in mathematical proof, taught through the mathematics of finite and countable objects: statements, sets, integers, arrangements, networks, and sequences. It is written for a reader working alone who has school algebra and function notation and has never been asked to write a proof. Nothing from calculus is needed.

Two things are taught at once. The first is a body of results: the laws of logic, equivalence relations and partitions, induction, the Euclidean algorithm and modular arithmetic, the counting principles, trees and their characterizations, and the solution of recurrences. The second is the craft of proving such results: how to read a statement closely enough to know what would establish it, how to write an argument that another person can check line by line, and how to find the broken step in an argument that looks right. The second skill is the one that transfers. Every later proof-based course in this library, from Real Analysis to Abstract Algebra, assumes it.

The book has done its work when you can do the following six things unaided. Translate an English claim into quantified form, negate it, and say what a proof or a counterexample would have to supply. Write direct, contrapositive, contradiction, case, and induction proofs with every assumption stated. Decide whether a function is injective or surjective and whether a relation is an equivalence or an order, with proof. Compute greatest common divisors, inverses, and solutions of congruences, and justify each step. Count a finite set by a bijection, a product, a recurrence, or inclusion and exclusion, and explain why nothing was counted twice. Recognise which of these tools a new problem calls for, and what kind of evidence settles it.

Some conventions hold throughout. The natural numbers are \(\mathbb N=\{0,1,2,\dots\}\) , so zero is included; the positive integers are \(\mathbb Z^{+}=\{1,2,3,\dots\}\) ; and \(\mathbb Z\) , \(\mathbb Q\) , \(\mathbb R\) are the integers, the rationals, and the reals. For a positive integer \(n\) we write \([n]\) for the set \(\{1,2,\dots,n\}\) . The notation \(a\mid b\) means that the integer \(a\) divides the integer \(b\) . Definitions, theorems, and proofs are set off in blocks and numbered in one sequence within each chapter, so that Theorem 4.6 is the sixth numbered block of Chapter 4.

A proof in this book is always written out in sentences, and you should write yours the same way. When a proof is given, read it with a pencil: cover the next line, predict it, and check. When a proof is asked for, do the scratch work on one sheet and the final argument on another, because the order in which an argument is discovered is rarely the order in which it should be presented. Each chapter ends with exercises that range from recall to full written proofs, and several ask you to diagnose a flawed argument. The companion solutions give complete arguments for some, graduated hints for others, and bare answers for a few. The cumulative review at the end does not say which chapter each problem belongs to, because choosing the method is part of the problem. A discrete subject offers one further resource that you should use freely: small cases can be listed completely. Before you try to prove a claim, test it by brute force on every case small enough to enumerate. A proof is still required, but the enumeration tells you what is true.