Book of Proof

Citation

Hammack, R. (2018). Book of Proof (3rd ed.). Richard Hammack. Free official edition: https://richardhammack.github.io/BookOfProof/

Chapter Summary

Chapter 1: Sets

The book starts from the premise that all of mathematics can be described with sets, so the first chapter builds the vocabulary used everywhere afterwards: set-builder notation, Cartesian products, subsets, power sets, union, intersection, difference and complement, Venn diagrams and indexed collections of sets. It closes with the standard number systems viewed as sets and a short account of Russell's paradox, which shows why some care is needed about what counts as a set.

Chapter 2: Logic

This chapter explains the logic that holds proofs together. It defines statements, the connectives "and", "or" and "not", conditional and biconditional statements, and uses truth tables to establish logical equivalences such as De Morgan's laws and the equivalence of a conditional with its contrapositive. Quantifiers, translation between English and symbolic logic, negating quantified statements and rules of inference follow, and a closing note sets out why the logic matters: it fixes what words such as "if…then" and "for all" mean.

Chapter 3: Counting

Expanded for the third edition, this chapter answers "how many?" without listing objects one by one. It develops lists, the multiplication, addition and subtraction principles, factorials and permutations, binomial coefficients as counts of subsets, Pascal's triangle and the binomial theorem, inclusion–exclusion, counting multisets, and the division and pigeonhole principles. It ends with combinatorial proof—showing two expressions are equal because they count the same thing. The introduction marks the chapter as optional, but it supplies examples and exercises used later.

Chapter 4: Direct Proof

Part II begins with the meanings of "theorem", "proof" and "definition", and fixes precise definitions (even and odd integers, divisibility, primes, greatest common divisor) that the next chapters rely on. The direct proof of a statement "If P, then Q" is presented as an outline—assume P, reason to Q—and practised on facts about integers. The chapter then shows how to split a proof into cases and how to treat similar cases only once.

Chapter 5: Contrapositive Proof

Building on the logical equivalence from Chapter 2, this chapter proves "If P, then Q" by proving "If not Q, then not P", and shows examples where this is much easier than a direct argument. It introduces congruence of integers modulo n as a new source of propositions. A section on mathematical writing then lists practical rules, such as not starting a sentence with a symbol, punctuating displayed formulas, and separating symbols with words.

Chapter 6: Proof by Contradiction

The third main technique is to assume the statement is false and derive an absurdity. The chapter justifies this with logic and uses it for classical results, including the irrationality of √2 and the infinitude of primes, before adapting it to conditional statements and combining it with other techniques. Its closing advice is to try direct or contrapositive proof first, since a contradiction proof often hides a simpler contrapositive one.

Chapter 7: Proving Non-Conditional Statements

Part III extends the toolkit to statements that are not of the form "If P, then Q": if-and-only-if statements, lists of equivalent statements, existence proofs and existence-and-uniqueness proofs. It contrasts constructive proofs, which produce the object, with non-constructive proofs, which show that it must exist without naming it.

Chapter 8: Proofs Involving Sets

Here the earlier techniques are applied to the three basic set-theoretic tasks: proving that an element belongs to a set, that one set is a subset of another and that two sets are equal (by proving inclusion in both directions). An extended example on perfect numbers shows how set-equality arguments carry real number-theoretic content, following reasoning attributed to Euclid and Euler and touching on Mersenne primes.

Chapter 9: Disproof

The chapter separates statements into those known to be true, those known to be false, and open questions, and then explains how to show a statement is false. The main tool is the counterexample; the chapter also covers disproving existence statements (by proving the negation) and disproof by contradiction.

Chapter 10: Mathematical Induction

Motivated by the conjecture that the first n odd numbers add up to n², the chapter presents ordinary induction, strong induction and proof by smallest counterexample. It uses these methods to prove the fundamental theorem of arithmetic (existence and uniqueness of prime factorisation) and to establish identities for the Fibonacci numbers.

Chapter 11: Relations

Part IV opens with a general theory of relations, defined as sets of ordered pairs. The chapter studies the reflexive, symmetric and transitive properties, equivalence relations, and the correspondence between equivalence classes and partitions. It constructs the integers modulo n as a worked example and ends with relations between two different sets, which prepares the definition of a function.

Chapter 12: Functions

Functions are defined as special relations, which allows a general view that goes beyond formulas. The chapter covers injective, surjective and bijective functions, restates the pigeonhole principle in this language, and treats composition, inverse functions, and images and preimages of sets.

Chapter 13: Proofs in Calculus

New in the third edition and explicitly optional, this chapter introduces the style of proof used in analysis. It starts from the triangle inequality and the epsilon–delta definition of a limit, proves that certain limits do not exist, derives limit laws, and then treats continuity and derivatives, limits at infinity, and the convergence of sequences and series. It assumes a previous calculus course.

Chapter 14: Cardinality of Sets

The final chapter defines equal cardinality through bijections and shows that infinite sets come in different sizes: the integers and rationals are countably infinite, while the real numbers are not. It proves that every set is smaller than its power set, gives criteria for countability, and proves the Cantor–Bernstein–Schröder theorem, which it uses to show that the real numbers and the power set of the natural numbers have the same cardinality; the continuum hypothesis is mentioned at the end.

Key Concepts

Chapter 1: Sets

• Set-builder notation: describing a set by a rule its elements satisfy, such as {x ∈ ℤ : x is even}.
• Power set: the set of all subsets of a given set; a set with n elements has 2ⁿ subsets.
• Russell's paradox: the contradiction produced by the "set of all sets that are not members of themselves", which shows that not every description defines a set.

Chapter 2: Logic

• Conditional statement: P ⇒ Q is false only when P is true and Q is false.
• Logical equivalence: two statements with the same truth table, such as a conditional and its contrapositive.
• Negating quantifiers: the negation of "for all x, P(x)" is "there exists x with not P(x)", and vice versa.

Chapter 3: Counting

• Multiplication principle: if a list is built in stages with fixed numbers of choices at each stage, the number of lists is the product of those numbers.
• Binomial coefficient: the number of k-element subsets of an n-element set, which also gives the coefficients in the binomial theorem.
• Combinatorial proof: proving an identity by showing that both sides count the same collection.

Chapter 4: Direct Proof

• Definition as working tool: a precise statement of meaning (for example, n is even if n = 2a for some integer a) that a proof unpacks step by step.
• Direct proof: assume P and use definitions and known facts to deduce Q.
• Proof by cases: dividing the hypothesis into exhaustive cases and proving the conclusion in each.

Chapter 5: Contrapositive Proof

• Contrapositive: the statement "not Q implies not P", logically equivalent to "P implies Q".
• Congruence modulo n: a ≡ b (mod n) when n divides a − b.

Chapter 6: Proof by Contradiction

• Proof by contradiction: assuming the negation of a statement and deducing something of the form C and not C.
• Hidden contrapositive: the observation that many contradiction proofs can be rewritten as simpler contrapositive proofs.

Chapter 7: Proving Non-Conditional Statements

• If-and-only-if proof: proving both P ⇒ Q and its converse Q ⇒ P.
• Constructive versus non-constructive proof: exhibiting an object versus showing it must exist without identifying it.

Chapter 8: Proofs Involving Sets

• Subset proof: take an arbitrary element of A and show it lies in B.
• Set equality by double inclusion: prove A ⊆ B and B ⊆ A.
• Perfect number: a natural number equal to the sum of its positive divisors smaller than itself, such as 6 or 28.

Chapter 9: Disproof

• Counterexample: a single instance showing that a universally quantified statement is false.
• Disproving existence: showing that a "there exists" statement is false by proving its universal negation.

Chapter 10: Mathematical Induction

• Induction: prove a base case and that each case implies the next, so the statement holds for all natural numbers.
• Strong induction: in the inductive step, use all earlier cases rather than only the previous one.
• Smallest counterexample: assume a least failing case exists and derive a contradiction.

Chapter 11: Relations

• Equivalence relation: a relation that is reflexive, symmetric and transitive.
• Partition: a division of a set into disjoint non-empty pieces; the equivalence classes of an equivalence relation form one.
• Integers modulo n: the set of equivalence classes of integers under congruence mod n.

Chapter 12: Functions

• Injective and surjective: a function is injective if distinct inputs have distinct outputs, surjective if every element of the codomain is an output.
• Inverse function: exists exactly when the function is bijective.
• Image and preimage: the set of outputs of a subset of the domain, and the set of inputs that land in a subset of the codomain.

Chapter 13: Proofs in Calculus

• Epsilon–delta limit: f(x) → L as x → c if for every ε > 0 there is δ > 0 that keeps |f(x) − L| below ε whenever 0 < |x − c| < δ.
• Triangle inequality: |a + b| ≤ |a| + |b|, the basic estimate in limit proofs.

Chapter 14: Cardinality of Sets

• Equal cardinality: two sets have the same size if there is a bijection between them.
• Countable and uncountable sets: sets the same size as ℕ (or finite) versus larger infinite sets such as ℝ.
• Cantor–Bernstein–Schröder theorem: injections in both directions between two sets guarantee a bijection.

Critical Analysis

Strengths

• Technique-by-technique structure. Parts II and III each isolate one method—direct, contrapositive, contradiction, if-and-only-if, existence, disproof, induction—and give it its own outline before showing examples. This makes it easy for a beginner to recognise what kind of statement is being proved and which template to try.
• Attention to writing, not just logic. Section 5.3's guidelines on mathematical writing and Section 6.4's advice on preferring simpler methods treat proofs as texts to be read by others. Combined with careful worked proofs, this helps students produce readable arguments rather than just correct ones.
• Flexible, well-documented organisation. The introduction gives a dependency tree showing that Chapters 3, 10 and 13 can be omitted, and a fourteen-week timetable with optional sections marked. Instructors can steer the course toward discrete mathematics (Chapters 1–12) or toward analysis (everything except Chapter 3).
• Large exercise sets with partial solutions. Every section or chapter ends with exercises, and solutions to the odd-numbered ones are printed at the back, which suits self-study while leaving even-numbered problems for assessment.

Limitations

• Logic is treated informally. Chapter 2 covers truth tables, quantifiers and inference rules sufficient for writing proofs, but there is no formal proof system, no semantics of first-order languages and no axiomatic set theory; readers interested in logic as a subject need a separate text.
• Examples lean heavily on integers. Until Chapter 13, most examples concern parity, divisibility and congruences. This keeps prerequisites low, but students heading for linear algebra or analysis see relatively few proofs in those settings.
• The calculus chapter assumes more. Chapter 13 presupposes a prior calculus course and moves quickly through limits, continuity, sequences and series; it is an introduction to analysis-style proofs rather than a substitute for an analysis course.
• Licence constraints. The free PDF is under a non-commercial, no-derivatives Creative Commons licence, so instructors cannot adapt or remix the text itself.

Where It Fits in the Course

In this Mathematical Logic and Set Theory list, Book of Proof is a bridge text into proof-based mathematics, alongside Daniel Velleman's How to Prove It, which is generally described as a structured introduction to proof strategies; the two can be used interchangeably as a first text, or one as a source of extra exercises for the other. Peter Eccles's An Introduction to Mathematical Reasoning, Allenby's Numbers and Proofs and Liebeck's A Concise Introduction to Pure Mathematics are generally described as introductions to pure mathematics through numbers, sets and functions; they are natural follow-ups or companions once the techniques in Hammack's Parts I–III are comfortable.

For the logic side of the course, Hammack is preparation rather than a replacement. Leary and Kristiansen's A Friendly Introduction to Mathematical Logic and Enderton's A Mathematical Introduction to Logic study formal languages, deductions and completeness, which assumes exactly the fluency with quantifiers, induction and set notation that this book provides. Students should read Hammack first, then move to one of those logic texts.

How to Use This Book

The book is written for students moving from computational to proof-based mathematics—typically in a first "introduction to proofs" or transition course. School algebra is enough for nearly everything; Chapter 13 needs a previous calculus course, and some examples and exercises in other chapters draw on calculus or linear algebra and can be skipped.

A practical plan follows the author's own timetable: Chapters 1 and 2 quickly but carefully (logic is used everywhere), Chapters 4–6 as the core, then Chapters 7–10, and Chapters 11, 12 and 14 to finish. Chapter 3 is optional but supplies examples used in later exercises; Chapter 13 is valuable just before a first analysis course. Readers working alone should try each worked proof before reading it, follow the outlines given for each technique, write out several exercises per section in full sentences using the rules from Section 5.3, and check odd-numbered answers against the solutions at the back. The author's website also hosts the free PDF and information about the print version.

Edition and Sources

This guide is based on the third edition of Book of Proof (Edition 3.4, © 2018 Richard Hammack, CC BY-NC-ND 4.0), read in the free PDF from the author's official site, https://richardhammack.github.io/BookOfProof/. It draws on the preface to the third edition, the introduction (part structure, dependency tree and teaching timetable), the full table of contents, and for all fourteen chapters the opening pages, every section heading and key worked proofs (including Sections 5.3, 6.4, 8.4, 10.3–10.4, 12.3, 13.2 and 14.1–14.4), together with the conclusion and the layout of the solutions section.