Book of Proof PDF Download – Richard Hammack (3rd Edition) – BS Math/BSCS

Students taking a Proof Writing, Foundations of Mathematics, or transition-to-proof course can download the complete textbook “Book of Proof” by Richard Hammack, free as a PDF from the author’s own Virginia Commonwealth University page. It is the standard first course in how mathematicians actually work — not computing answers, but proving that mathematical statements are true — built from 18 years of the author’s own lecture notes for VCU’s MATH 300 proofs course.

The book covers sets and logic, the three core proof techniques (direct, contrapositive, contradiction), how to prove non-conditional and set-theoretic statements, disproof, mathematical induction, and closes with relations, functions and the surprising mathematics of infinite cardinality. It assumes only basic algebra — no calculus is needed for the first twelve chapters — which makes it the natural entry point for BS Mathematics and BS Computer Science students starting their first proof-based course, whether that’s a dedicated Foundations course or the run-up to Discrete Structures.

Book Overview

Chapter List

Part I: Fundamentals

Chapter 1: Sets

Difficulty: Easy · Key topics: sets, elements, the Cartesian product, subsets, power sets, union/intersection/difference, complement, Venn diagrams, indexed sets, Russell’s Paradox

The book opens with the claim that all of mathematics can be described with sets, and spends the chapter making that literal. It defines a set as a collection of elements, covers how to write sets by listing elements or by set-builder notation, and introduces the reserved symbols N, Z, Q and R for the standard number systems. From there it builds every basic set operation — Cartesian product, subset, power set, union, intersection, difference, complement — and shows how Venn diagrams visualize each one. The chapter closes with indexed families of sets and Russell’s Paradox, the famous self-referential set that shows “the set of all sets” cannot itself be a set.

Key Points:

• Two sets are equal exactly when they contain the same elements — order and repetition in a listing never matter
• N, Z, Q, R denote the naturals, integers, rationals and reals — used without re-definition for the rest of the book
• The power set P(A) is the set of all subsets of A, including ∅ and A itself
• A − B (difference) and the complement A depend on a fixed universal set U being understood from context
• An indexed family of sets lets a single subscript variable stand for infinitely many sets at once
• Russell’s Paradox — does the set of all sets that do not contain themselves contain itself? — shows naive set theory is inconsistent without restrictions on what counts as a set

Memory Tip: Read A ⊆ B as a question, not a fact: “does every element of A also sit inside B?” Answering that question directly is the entire proof technique used in Chapter 8.

Common Mistake: Treating ∈ (element of) and ⊆ (subset of) as interchangeable. 2 ∈ {1,2,3} is true but 2 ⊆ {1,2,3} is meaningless — only a set can be a subset of another set, and a lone element is never automatically a set.

Important Questions:

• What is Russell’s Paradox, and what does it show? It asks whether the set of all sets that do not contain themselves contains itself — either answer produces a contradiction. It shows that allowing “the set of all sets with property P” without restriction leads to inconsistency, which is why set theory needs careful axioms.
• When are two sets equal, according to the book’s own definition? Two sets are equal exactly when they contain exactly the same elements — the order the elements are listed in, and whether any are repeated in the listing, makes no difference at all.

Chapter 2: Logic

Difficulty: Medium · Key topics: statements, and/or/not, conditional and biconditional statements, truth tables, logical equivalence, quantifiers, negating statements, logical inference

This chapter formalizes the everyday reasoning students already use — combining two known facts to deduce a third — into a system precise enough to build proofs on. It defines a statement as a sentence that is definitely true or definitely false, then builds compound statements with and/or/not, conditional (“if P then Q”) and biconditional (“P if and only if Q”) forms, verified mechanically with truth tables. Quantifiers (“for all,” “there exists”) and the precise rules for negating quantified and conditional statements follow, since disproof in Chapter 9 depends entirely on getting negation right. The chapter distinguishes correct logic from correct information: an argument can be logically valid while starting from a false premise, and that distinction matters throughout the rest of the book.

Key Points:

• A statement is a sentence that is definitely true or definitely false — “add 5 to both sides” is a command, not a statement
• The converse of P ⇒ Q is Q ⇒ P, and it is not logically equivalent to the original — only the contrapositive is
• Truth tables settle logical equivalence mechanically: if two statements’ columns agree on every row, they are equivalent
• The negation of ∀x ∈ S, P(x) is ∃x ∈ S, ∼P(x) — negating a universal statement always produces an existence statement
• Logical validity and factual correctness are different things — a proof can be perfectly logical while working from a false assumption

Memory Tip: Converse swaps the two halves of “if P then Q”; contrapositive swaps and negates both halves. Only the second move preserves truth — memorize it as “swap and negate travel together.”

Common Mistake: Assuming a conditional statement and its converse say the same thing. “If it rains, the ground is wet” does not mean “if the ground is wet, it rained” — sprinklers exist. This exact confusion invalidates a large share of first proof attempts.

Important Questions:

• What is the negation of the universally quantified statement “∀x ∈ S, P(x)”, and why does that matter for disproof? Its negation is “∃x ∈ S, ∼P(x)” — an existence statement. It matters because Chapter 9 proves this negation is true by producing a single example, so disproving a universal statement only ever requires one counterexample.
• Why is a proof still logically valid even if one of its starting assumptions turns out to be false? Logic only guarantees that the conclusion follows correctly from the premises — it says nothing about whether the premises themselves are true. Correct reasoning from a false premise is still correct reasoning; it just does not guarantee a true conclusion.

Chapter 3: Counting

Difficulty: Medium · Key topics: lists, the multiplication principle, addition/subtraction principles, factorials and permutations, counting subsets, Pascal’s Triangle and the binomial theorem, inclusion-exclusion, multisets, pigeonhole principle, combinatorial proof

Counting looks trivial — point at objects and say “one, two, three” — but this chapter shows how subtle it becomes once objects can repeat, overlap or be arranged in order. It starts from the concept of a list (an ordered sequence, unlike a set) and the multiplication principle for sequential choices, then builds factorials, permutations and combinations, with Pascal’s Triangle and the binomial theorem tying counting subsets to algebra. The Inclusion-Exclusion Principle corrects for double-counted overlaps, the Pigeonhole Principle proves existence results from pure counting (if you place more pigeons than holes, some hole gets two), and the chapter closes by teaching combinatorial proof — proving an algebraic identity by counting the same collection two different ways. The book’s own dependency tree marks this chapter as optional; a course pitched toward analysis can skip it entirely.

Key Points:

• A list is an ordered sequence that can repeat entries; a set cannot repeat entries and has no order — (a,b,c) ≠ (b,a,c) but {a,b,c} = {b,a,c}
• The multiplication principle: if a first choice can be made m ways and, independently, a second choice n ways, the pair can be made m·n ways
• Permutations count ordered selections (n!/(n-r)!); combinations count unordered selections (n!/(r!(n-r)!))
• The Pigeonhole Principle proves existence without constructing an example — more objects than boxes forces some box to hold two
• The Inclusion-Exclusion Principle: |A ∪ B| = |A| + |B| − |A ∩ B|, correcting for elements counted twice
• A combinatorial proof establishes an identity by counting one collection two different, equally valid ways
• The book itself marks this chapter as skippable without loss of continuity for the core proof-writing sequence (Chapters 1, 2, 4–14)

Memory Tip: Before reaching for a formula, ask two yes/no questions out loud: does order matter (permutation vs. combination), and can an item repeat (multiset vs. not)? Naming both properties picks the right formula almost every time.

Common Mistake: Adding two counts that actually overlap. If a card can be both a face card and a heart, counting “face cards” and “hearts” separately and adding double-counts the overlap — Inclusion-Exclusion (subtract the intersection back out) is required, not a nicety.

Important Questions:

• State the Pigeonhole Principle and explain why it proves existence without ever exhibiting a specific example. If more than n objects are placed into n boxes, some box contains at least two objects. It proves existence purely by counting — it guarantees that a collision exists somewhere, without ever identifying which box or objects are involved.
• What is a combinatorial proof, and how does it differ from an algebraic proof of the same identity? A combinatorial proof shows an algebraic identity is true by counting one and the same collection of objects in two different ways and showing both counts must be equal — no algebraic manipulation of the formulas themselves is used at all.

Part II: How to Prove Conditional Statements

Chapter 4: Direct Proof

Difficulty: Medium · Key topics: theorems, definitions, direct proof, proof by cases, treating similar cases

This is where the book starts actually proving things, and it opens by pinning down three words used loosely until now: a theorem is a true, verified statement; a proof is a written verification that convinces any reader with the right background; a definition is an exact, unambiguous explanation with no wiggle room. Nearly every theorem the book will ask you to prove has (or can be rephrased into) the conditional form “if P, then Q,” and direct proof is the most straightforward technique for it: assume P is true, then use logic and definitions to deduce Q is also true. The chapter walks through worked examples on integers and divisibility, then covers proof by cases — splitting a proof into exhaustive scenarios — and how to shorten the writing when several cases are nearly identical.

Key Points:

• A theorem is true and has been proved true; a proof is a written verification convincing to any reader with the right background
• A definition must be exact and unambiguous — both writer and reader of a proof must agree on every term’s precise meaning
• Direct proof outline: assume P, then use logic and definitions to deduce Q, concluding P ⇒ Q
• “n is even” means n = 2a for some integer a; “n is odd” means n = 2a + 1 for some integer a — these two definitions drive most of the chapter’s examples
• Proof by cases requires the cases to be exhaustive — together they must cover every possibility, with no gap left unproved

Memory Tip: Every direct proof has the same shape: state the assumption in the first line, end with the conclusion in the last line, and every line in between is a logical consequence of what came before — nothing else is allowed to sneak in.

Common Mistake: Starting a direct proof by assuming the conclusion instead of the hypothesis. To prove “if P then Q” you assume P is true and work forward to Q — assuming Q and working backward proves nothing on its own, even when every step looks correct.

Important Questions:

• What is the precise algebraic definition of an odd integer, and why does “doesn’t end in 0, 2, 4, 6 or 8” not count as a proof-ready definition? An integer n is odd if n = 2a + 1 for some integer a. The informal digit-based description is not usable inside a proof because a proof needs an algebraic form it can manipulate with equations — you cannot deduce new facts from “the last digit isn’t even.”
• Outline the three-word distinction the chapter draws between a theorem, a proof and a definition. A theorem is a true, verified mathematical statement; a proof is the written argument that verifies it, convincing to any reader who knows the relevant definitions; a definition is the exact, unambiguous meaning assigned to a mathematical term, agreed on by writer and reader alike.

Chapter 5: Contrapositive Proof

Difficulty: Medium · Key topics: the contrapositive form, contrapositive vs. converse, congruence of integers, mathematical writing style

Since P ⇒ Q is logically equivalent to its contrapositive ∼Q ⇒ ∼P (proved with a truth table), a proposition can be proved by assuming Q is false and deducing P is false instead of working forward from P. The chapter proves the same proposition both ways — direct and contrapositive — side by side, on the claim “if 7x + 9 is even, then x is odd,” to show contrapositive is often shorter when the direct approach forces awkward algebra. It then applies the technique to congruence of integers (a ≡ b (mod n) means n | (a − b)) and closes with a short section on mathematical writing conventions — complete sentences, no unexplained symbols, stating what’s being assumed before using it.

Key Points:

• Contrapositive proof outline: assume ∼Q, use logic and definitions to deduce ∼P, concluding P ⇒ Q by logical equivalence
• P ⇒ Q and ∼Q ⇒ ∼P are logically equivalent (verified by truth table); P ⇒ Q and its converse Q ⇒ P are not
• Contrapositive is often preferable when the direct approach starts from an inequality or awkward algebraic form — the contrapositive version frequently starts from a clean equation instead
• a ≡ b (mod n) is defined as n | (a − b) — a definition reused constantly in later chapters, especially Relations (Chapter 11)
• Good mathematical writing states assumptions explicitly and never leaves a reader to guess what a symbol refers to

Memory Tip: If direct proof forces you to solve an inequality involving the goal Q, try contrapositive first — assuming ∼Q and working toward ∼P usually turns that same step into a clean equation.

Common Mistake: Writing a contrapositive proof but calling it a direct proof, or vice versa, because the final conclusion looks the same. A grader checks the logical structure of the argument, not just its conclusion — starting from ∼Q and reaching ∼P is a fundamentally different chain of reasoning from starting at P and reaching Q.

Important Questions:

• Why does proving the contrapositive prove the original conditional statement? Because P ⇒ Q is logically equivalent to its contrapositive ∼Q ⇒ ∼P — a fact confirmed by comparing their truth tables column by column. Proving one statement true automatically proves the other true, since they are, logically, the very same statement in different words.
• Give the precise definition of a ≡ b (mod n) used throughout the rest of the book. a ≡ b (mod n) means n | (a − b), i.e. n divides a − b evenly. Equivalently, a and b leave the same remainder when divided by n.

Chapter 6: Proof by Contradiction

Difficulty: Medium · Key topics: proof by contradiction, proving conditional statements with contradiction, combining proof techniques, when to use each method

Unlike direct and contrapositive proof, contradiction can prove any kind of statement, not just conditional ones. The method: assume the statement to be proved is false, then deduce something that is unambiguously nonsense — a contradiction of the form C ∧ ∼C, which is false no matter what C stands for. Since that deduction was logically valid throughout, the only thing that could have been wrong is the starting assumption, so the original statement must be true. The book proves this logic is sound with a truth table showing P is logically equivalent to (∼P) ⇒ (C ∧ ∼C), then shows contradiction can also prove conditional statements (assume both P and ∼Q, derive a contradiction), and closes with guidance on when to reach for contradiction versus the two earlier techniques.

Key Points:

• Proof by contradiction outline: assume the statement is false, deduce a contradiction C ∧ ∼C, conclude the statement must be true
• A contradiction is any statement of the form C ∧ ∼C — false regardless of what C represents
• Contradiction is the most general technique in the book: it can prove conditional statements, non-conditional statements, and disproofs alike
• To prove P ⇒ Q by contradiction, assume both P is true and Q is false at once, then derive a contradiction from that combination
• The book’s own advice: try direct or contrapositive first; reach for contradiction when the statement’s negation gives you extra, usable information the original didn’t

Memory Tip: Contradiction proofs read backwards from every other technique in the book — you assume the thing you want to prove is false, so always double-check your very first line says “suppose [statement] is false,” not “suppose [statement] is true.”

Common Mistake: Reaching a false-looking equation and stopping without stating explicitly what contradiction was reached. A contradiction proof must name the two conflicting statements (e.g. “1 is even” and the known fact “1 is odd”) — simply arriving at an equation that feels wrong is not a completed proof.

Important Questions:

• Why can proof by contradiction be used on statements that direct and contrapositive proof cannot touch? Direct and contrapositive proof both require the statement to have (or be rephrased into) conditional form “if P then Q.” Contradiction needs no such form — it only requires assuming the statement’s negation and deriving nonsense, which works for any statement, conditional or not.
• How does a contradiction proof of a conditional statement “if P then Q” differ in setup from a direct proof of the same statement? Direct proof assumes only P and works toward Q. A contradiction proof assumes both P is true and Q is false simultaneously, then uses both assumptions together to derive a contradiction.

Part III: More on Proof

Chapter 7: Proving Non-Conditional Statements

Difficulty: Medium · Key topics: if-and-only-if proof, equivalent statements, existence and uniqueness proofs, constructive vs. non-constructive proofs

The first three proof techniques all targeted conditional statements, but not every theorem has that form. This chapter covers three more shapes. An “if and only if” (biconditional) proof splits into two halves — prove P ⇒ Q, then prove the converse Q ⇒ P, each by whichever of direct, contrapositive or contradiction fits best — and the book insists on starting the second half with the word “Conversely” so the reader always knows which direction is being proved. Existence proofs show something with a property exists (sometimes by exhibiting it, sometimes not); uniqueness proofs additionally show there is only one such object, typically by assuming two exist and proving they must be equal. The chapter closes by distinguishing constructive proofs (which build the object explicitly) from non-constructive proofs (which prove existence without ever producing the object).

Key Points:

• “P if and only if Q” requires two separate proofs: P ⇒ Q and its converse Q ⇒ P
• Begin the second half of a biconditional proof with “Conversely” and restate exactly which direction is now being proved
• A uniqueness proof typically assumes two objects both satisfy the property, then proves they must actually be the same object
• A constructive proof explicitly builds or exhibits the object it claims exists; a non-constructive proof proves existence without ever producing it
• Each half of an if-and-only-if proof may use a different proof technique — direct for one direction, contrapositive for the other, for example

Memory Tip: Whenever you see “if and only if,” mentally split the page into two proofs before writing a single word — forgetting the second half (the converse) is the single most common way students lose credit on these problems.

Common Mistake: Proving only P ⇒ Q and treating an “if and only if” theorem as finished. Both directions are separate logical claims and both require their own complete proof — proving one direction says nothing at all about the other.

Important Questions:

• What two separate proofs does proving “P if and only if Q” actually require? It requires proving P ⇒ Q (if P then Q) and its converse Q ⇒ P (if Q then P) as two entirely separate arguments — either direction can use direct, contrapositive or contradiction proof, independently of the other.
• What is the difference between a constructive and a non-constructive existence proof? A constructive proof explicitly exhibits or builds the object claimed to exist, so you can point to it directly. A non-constructive proof establishes that such an object must exist — often via contradiction or the pigeonhole principle — without ever producing a specific example of it.

Chapter 8: Proofs Involving Sets

Difficulty: Medium · Key topics: proving a ∈ A, proving A ⊆ B, proving A = B, perfect numbers

Once students reach linear algebra and beyond, most proofs are actually proofs about sets, so this chapter builds that specific skill directly, reviewing set-builder notation and the Chapter 1 operations along the way. It gives an explicit outline for proving an object is an element of a set defined by a property, an outline for proving one set is a subset of another (pick an arbitrary element of the first set, show it must belong to the second), and an outline for proving two sets are equal (prove each is a subset of the other, using the two previous outlines back to back). The chapter’s extended running example is perfect numbers — numbers equal to the sum of their proper divisors, like 6 = 1+2+3 — used to show all three outlines working together on a genuinely interesting open problem in number theory.

Key Points:

• To prove a ∈ A where A = {x : P(x)}, show the specific object a satisfies the property P
• To prove A ⊆ B: let x be an arbitrary element of A, then show x must also be an element of B
• To prove A = B: prove A ⊆ B and prove B ⊆ A, as two separate subset arguments
• A perfect number equals the sum of its own proper divisors — 6 (1+2+3) and 28 (1+2+4+7+14) are the first two examples
• Whether an odd perfect number exists remains an unsolved problem in mathematics — the chapter uses this to show set-proof techniques applied to a genuinely open question

Memory Tip: “Prove A = B” almost never has a one-step trick — picture it as two separate subset proofs stapled together, A ⊆ B first, then B ⊆ A, and write them as two clearly labeled paragraphs.

Common Mistake: Proving A ⊆ B by checking a few specific elements of A instead of an arbitrary one. A subset proof must work for every element of A, so the proof has to start “let x be an arbitrary element of A” and use only the defining property of A, never a specific number.

Important Questions:

• Outline the standard technique for proving A ⊆ B. Let x be an arbitrary (unspecified) element of A. Using only the definition/property that makes x belong to A, show that x must also satisfy the property that defines B. Since x was arbitrary, this shows every element of A is in B.
• What is a perfect number, and what open question about perfect numbers does the chapter mention? A perfect number equals the sum of its own proper divisors (e.g. 6 = 1+2+3). Whether any odd perfect number exists is unsolved — every perfect number ever found is even, but no one has proved none can be odd.

Chapter 9: Disproof

Difficulty: Medium · Key topics: theorems vs. conjectures vs. false statements, counterexamples, disproving existence statements, disproof by contradiction

Every example so far handed students a true statement to prove — this chapter asks what happens with a false one, where no correct proof could ever exist. It sorts mathematical statements into three categories: proved true (theorems), proved false, and conjectures whose truth is still unknown (like the Goldbach conjecture). To disprove a universally quantified statement ∀x ∈ S, P(x), the chapter shows that producing just one x that makes P(x) false — a counterexample — is sufficient, illustrated with the famous near-miss conjecture that n² − n + 11 is always prime (true for every integer from −3 through 10, false at n = 11). The chapter then covers disproving existence statements (prove the corresponding universal negation) and disproof by contradiction, for statements that resist a direct counterexample.

Key Points:

• Mathematical statements fall into three categories: proved true (theorem), proved false, or a conjecture (truth currently unknown)
• To disprove ∀x ∈ S, P(x), produce one example of x ∈ S that makes P(x) false — a single counterexample suffices
• The classic near-miss: f(n) = n² − n + 11 is prime for n = −3 through 10 (14 straight cases) but f(11) = 121 = 11², disproving “always prime” with one counterexample
• To disprove P(x) ⇒ Q(x), produce an example of x making P(x) true and Q(x) false simultaneously
• Disproving an existence statement ∃x, P(x) means proving its negation ∀x, ∼P(x) — every single case must be ruled out, not just one

Memory Tip: “One example proves it false; no finite number of examples proves it true” — the n²−n+11 example is worth memorizing whole as a warning against trusting a pattern that has only been checked, not proved.

Common Mistake: Believing a conjecture is a theorem because no counterexample has been found yet. A conjecture stays unproved no matter how many confirming examples pile up — the entire point of this chapter’s opening example is that fourteen straight confirming cases still weren’t a proof.

Important Questions:

• Walk through the classic n² − n + 11 example: why does checking many values not prove the conjecture, and what finally disproves it? f(n) = n²−n+11 is prime for every integer from −3 to 10, which might suggest it’s always prime — but checking finitely many cases can never prove a statement about all integers. The conjecture is disproved by the single counterexample n = 11, where f(11) = 121 = 11 × 11, which is not prime.
• How does disproving an existence statement “∃x, P(x)” differ from disproving a universal statement “∀x, P(x)”? Disproving a universal statement needs only one counterexample. Disproving an existence statement means proving its negation “∀x, ∼P(x)” is true — every single possible case must be ruled out, which is a fundamentally harder task than finding one example.

Chapter 10: Mathematical Induction

Difficulty: Hard · Key topics: proof by induction, proof by strong induction, proof by smallest counterexample, the Fundamental Theorem of Arithmetic, Fibonacci numbers

This chapter tackles statements S₁, S₂, S₃, … — an infinite list, one per natural number — that no finite proof by cases could ever fully cover. Induction proves them all at once with two steps: prove S₁ directly (the base case), then prove that S_k being true forces S_{k+1} to be true for every k (the inductive step). The book’s own analogy is dominoes: knock over the first one, prove any falling domino knocks over the next, and the whole infinite row falls. Strong induction extends this by allowing the inductive step to use any earlier true statement, not just the immediately preceding one — demonstrated on the classic “any postage of 8¢ or more can be made from 3¢ and 5¢ stamps” proof, which needs to reach back three steps. Proof by smallest counterexample, a hybrid with contradiction, assumes some S_n is false, lets k be the smallest such failure, and derives a contradiction from S_{k-1} being true while S_k is false. The chapter closes by applying all three techniques to the Fundamental Theorem of Arithmetic and Fibonacci numbers.

Key Points:

• Ordinary induction: prove S₁ (base case), then prove S_k ⇒ S_{k+1} for every k ≥ 1 (inductive step)
• Strong induction: the inductive step may assume S₁ ∧ S₂ ∧ ⋯ ∧ S_k (all previous statements), not just S_k alone, to prove S_{k+1}
• Smallest counterexample is a hybrid of induction and contradiction: assume a failure exists, take the smallest one, show S_{k-1} true and S_k false collide in a contradiction
• The 3¢/5¢ stamp proof needs strong induction because it must reach back three steps (from k+1 to k−2), which ordinary induction’s one-step-back rule cannot express
• The Fundamental Theorem of Arithmetic (every integer > 1 has a unique prime factorization) is proved by combining induction, cases and smallest counterexample together

Memory Tip: Keep the domino picture literal: base case = knock over domino 1; inductive step = prove any falling domino always knocks over the next one. If either half is missing, the row doesn’t fall — skipping the base case is the single most common way students lose credit here.

Common Mistake: Writing an inductive step that never actually uses the inductive hypothesis (the assumption that S_k is true). If the proof of S_{k+1} would work exactly the same way without ever mentioning S_k, it isn’t really an induction proof — it’s an incomplete, separate argument that happens to be repeated for each case.

Important Questions:

• State the two required steps of an ordinary induction proof, using the book’s own domino analogy. (1) The base case: prove S₁ directly — knock over the first domino. (2) The inductive step: prove that for every k ≥ 1, S_k being true forces S_{k+1} to be true — prove any falling domino always knocks over the next one. Together, these guarantee every S_n is true.
• How does strong induction differ from ordinary induction, and why does the 3¢/5¢ postage proof need it? Strong induction’s inductive step may use any (or all) of the previous statements S₁ through S_k, not just S_k itself. The postage proof needs this because reaching k+1 cents requires adding one 3¢ stamp to a postage of k−2 cents — a step back that ordinary induction’s “S_k alone” rule cannot reach.

Part IV: Relations, Functions and Cardinality

Chapter 11: Relations

Difficulty: Hard · Key topics: relations as subsets of A×A, reflexive/symmetric/transitive properties, equivalence relations, equivalence classes and partitions, the integers modulo n, relations between sets

Familiar symbols like <, =, | and ≡ all express some relationship between two things, and this chapter builds one theory general enough to cover every relation at once, rather than studying each symbol separately. Its key move is definitional: a relation on a set A is simply a subset R ⊆ A×A, with xRy abbreviating (x,y) ∈ R. From there it defines three properties — reflexive (xRx always holds), symmetric (xRy implies yRx), transitive (xRy and yRz implies xRz) — and shows that a relation with all three is an equivalence relation, which partitions its set into equivalence classes that never overlap and together cover the whole set. The integers modulo n (built entirely from the congruence relation of Chapter 5) is the chapter’s central worked example, and the closing section extends relations to work between two different sets, not just within one.

Key Points:

• A relation on A is formally just a subset R ⊆ A×A — the abstraction that lets one theory cover <, =, |, ≡ and every other relation at once
• Reflexive: xRx for every x ∈ A. Symmetric: xRy ⇒ yRx. Transitive: (xRy ∧ yRz) ⇒ xRz
• An equivalence relation is reflexive, symmetric and transitive — ordinary equality (=) is the prototype example
• Every equivalence relation on A partitions A into equivalence classes: non-overlapping subsets whose union is all of A
• Z_n, the integers modulo n, is built directly from the congruence relation a ≡ b (mod n) as its set of equivalence classes

Memory Tip: Test the three equivalence-relation properties on ordinary = first, since it’s the relation every student already trusts completely — then check the same three properties, one at a time, on any new relation you’re asked about.

Common Mistake: Assuming any reflexive and transitive relation is automatically an equivalence relation. All three properties — reflexive, symmetric, and transitive — are required; ≤ is reflexive and transitive but not symmetric, so it is not an equivalence relation despite looking “well-behaved.”

Important Questions:

• Give the formal definition of a relation on a set A, and explain how it makes <, =, and | all instances of the same idea. A relation on A is a subset R ⊆ A×A; writing xRy just abbreviates (x,y) ∈ R. Every specific relation symbol — <, =, |, ≡ — is really just a particular subset of ordered pairs, so one general theory of subsets of A×A covers all of them.
• What three properties define an equivalence relation, and what does an equivalence relation do to its underlying set? An equivalence relation is reflexive, symmetric and transitive. It partitions the underlying set into equivalence classes — non-overlapping subsets that together cover the entire set, so every element belongs to exactly one class.

Chapter 12: Functions

Difficulty: Hard · Key topics: functions as special relations, injective and surjective functions, the pigeonhole principle revisited, composition, inverse functions, image and preimage

Having just defined relations, the chapter reframes the familiar idea of a function as a special kind of relation: a function f from A to B is a relation (a set of ordered pairs, its graph) in which every element of A is paired with exactly one element of B. From that definition it builds the two properties every later proof about functions depends on — injective (no two distinct inputs share an output, best proved via its contrapositive form) and surjective (every element of B is hit by some input) — and revisits the Pigeonhole Principle from Chapter 3 to show a function between finite sets of equal size is injective exactly when it’s surjective. The chapter then covers composing two functions, when and how a function can be inverted (only when it’s bijective — both injective and surjective), and closes by distinguishing a function’s image (the set of outputs it actually produces) from the preimage of a set (all inputs mapping into it).

Key Points:

• A function f : A → B is a relation (its graph, a subset of A×B) in which every a ∈ A appears in exactly one ordered pair
• Injective is usually proved by its contrapositive form: assume f(a) = f(a′), deduce a = a′ — easier than the direct form when f is an algebraic formula
• Surjective means: for every b ∈ B, there exists a ∈ A with f(a) = b — proved by producing or solving for such an a
• Between two finite sets of the same size, a function is injective if and only if it is surjective (the Pigeonhole Principle, revisited)
• Only a bijective function (both injective and surjective) has a genuine inverse function
• The image of f is the set of outputs actually produced; the preimage of a subset of B is the set of every input mapping into it

Memory Tip: To prove injective, try the contrapositive first: start from “f(a) = f(a′)” (an equation) rather than “a ≠ a′” (an inequality) — algebra is almost always easier starting from an equation.

Common Mistake: Assuming every function has an inverse. Only a bijective function — both injective and surjective — can be inverted as a genuine function; a merely injective or merely surjective function has no well-defined inverse on the full codomain.

Important Questions:

• Why is proving a function injective by its contrapositive form usually easier than proving it directly? The direct form starts from the inequality a ≠ a′ and must reach the inequality f(a) ≠ f(a′). The contrapositive form starts from the equation f(a) = f(a′) and reaches the equation a = a′ instead — and algebraic manipulation of equations is almost always more tractable than manipulation of inequalities.
• What condition must a function satisfy to have a genuine inverse function, and why? The function must be bijective — both injective and surjective. Injective ensures each output corresponds to only one input (so the inverse rule is well-defined), and surjective ensures every element of the codomain actually has a preimage to map back to (so the inverse is defined on the whole set).

Chapter 13: Proofs in Calculus

Difficulty: Hard · Key topics: the triangle inequality, the formal ε-δ definition of a limit, limits that do not exist, limit laws, continuity and derivatives, limits at infinity, sequences, series

Every proof up to this point has concerned integers or structures built from them; this chapter shows how the same three core techniques (direct, contrapositive, contradiction) adapt to the real numbers R and the machinery of calculus. It opens with the triangle inequality (|x−y| ≤ |x−z| + |z−y|), needed for nearly everything that follows, then replaces the informal “f(x) gets close to L as x gets close to c” idea from first-year calculus with the precise ε-δ definition used in real analysis — the chapter is explicit that the informal version is too vague to build proofs on. From there it covers proving limits do not exist, the standard limit laws, continuity and differentiability defined in terms of limits, limits at infinity, and finally sequences and series as functions f : N → R. The book itself flags this chapter as entirely skippable without any loss of continuity in the rest of the text.

Key Points:

• Triangle inequality: for real x, y, z, |x−y| ≤ |x−z| + |z−y| — used repeatedly in the ε-δ proofs that follow
• Formal limit definition: lim_{x→c} f(x) = L means for every ε > 0 there exists δ > 0 such that 0 < |x−c| < δ implies |f(x)−L| < ε
• The informal “gets close to” definition of a limit, standard in first-year calculus, is explicitly called too vague for rigorous proof — the ε-δ version replaces “close” with a precise, checkable inequality
• Continuity and differentiability at a point are both defined directly in terms of the formal limit definition, not intuition about unbroken curves
• Sequences and series are treated as functions f : N → R, connecting this chapter’s material directly back to the function theory of Chapter 12
• The chapter is explicitly optional — the book’s own dependency tree shows nothing later requires it

Memory Tip: Read the ε-δ definition as a challenge-and-response game: someone hands you an ε (however small), and your job is to find a δ that works — the proof is a recipe for producing that δ from whatever ε you’re given.

Common Mistake: Treating the informal “gets arbitrarily close” phrasing as a usable definition inside a formal proof. It cannot be manipulated algebraically because “close” is never pinned down to a number — only the ε-δ version, with its explicit inequalities, can actually be used to derive anything.

Important Questions:

• State the formal ε-δ definition of lim_{x→c} f(x) = L, and explain why the book considers the informal calculus-class definition insufficient. For every ε > 0, there must exist a δ > 0 such that whenever 0 < |x−c| < δ, it follows that |f(x)−L| < ε. The informal version (“f(x) gets close to L as x gets close to c”) is insufficient because “close” is never given a precise numerical meaning, so no proof can manipulate it.
• State the triangle inequality for real numbers, and why is it named that? For real x, y, z: |x−y| ≤ |x−z| + |z−y|. It is named for the fact that, treating |a−b| as the distance between a and b on the number line, it says no side of a “triangle” with vertices x, y, z can exceed the sum of the other two sides.

Chapter 14: Cardinality of Sets

Difficulty: Hard · Key topics: sets with equal cardinality, bijections, countable and uncountable sets, aleph-null, comparing cardinalities, the Cantor-Bernstein-Schröder Theorem

Counting a finite set’s elements is trivial, but this closing chapter shows the idea becomes genuinely strange once sets are infinite — two infinite sets can have different sizes, even though both go on forever. It redefines “same size” without counting at all: |A| = |B| exactly when a bijective function f : A → B exists, matching every element of one set to exactly one element of the other with nothing left over on either side. This lets it prove |N| = |Z| (both countably infinite, cardinality ℵ₀, “aleph-null”) despite Z looking twice as large, while proving |N| ≠ |R| — the reals are strictly larger, an uncountable infinity. The chapter develops tools for comparing cardinalities when no bijection is obvious, and closes with the Cantor-Bernstein-Schröder Theorem, which proves |A| = |B| from two one-directional injections rather than requiring a single bijection to be constructed directly.

Key Points:

• |A| = |B| is defined by the existence of a bijective function f : A → B — no counting involved, works for finite and infinite sets alike
• |N| = |Z|: despite Z seeming twice as large as N, a bijection (listing integers as 0, 1, −1, 2, −2, …) matches them perfectly
• A set is countably infinite if it has the same cardinality as N; countable means finite or countably infinite; a set is uncountable if it’s infinite but not countable
• The cardinality of N is denoted ℵ₀ (“aleph-null”) — the smallest possible infinite cardinality
• |N| ≠ |R|: the real numbers form a strictly larger, uncountable infinity — the chapter’s central surprising result
• The Cantor-Bernstein-Schröder Theorem: if there is an injection A → B and an injection B → A, then |A| = |B|, even without ever constructing a direct bijection

Memory Tip: To show two infinite sets have equal cardinality, you never need to “count” either one — you only need one honest matching rule (a bijection) that pairs every element of one set with exactly one element of the other, with nothing left over.

Common Mistake: Assuming a proper subset must always be strictly smaller than the set containing it. That intuition, true for finite sets, fails for infinite ones — the even integers are a proper subset of Z, yet |Z| = |{even integers}|, both equal to ℵ₀.

Important Questions:

• How does the chapter define “|A| = |B|” without counting either set, and why does that definition still work for infinite sets? Two sets have equal cardinality exactly when a bijective function f : A → B exists between them. It works for infinite sets because a bijection never requires finishing a count — it only requires an unambiguous rule pairing every element of one set with exactly one element of the other.
• What does the Cantor-Bernstein-Schröder Theorem let you conclude, and why is that useful when a direct bijection is hard to construct? If injections exist in both directions (A → B and B → A), the theorem concludes |A| = |B|. It is useful because a one-directional injection is frequently much easier to construct than a full bijection, so the theorem gets the same conclusion from two easier pieces of work.

Download Book of Proof PDF (Free)

Book of Proof is free from its official source, author Richard Hammack’s own page at Virginia Commonwealth University. Click below to download the complete PDF — the same page also lists paperback and hardcover print editions if you’d rather own a physical copy.

How to Study This Book

Chapters 1 and 2 (Sets, Logic) are non-negotiable — every later chapter uses their vocabulary and notation without redefining it. Do not move past Chapter 2 until set notation and truth tables both feel automatic.

Chapter 3 (Counting) is explicitly marked skippable in the book’s own dependency tree. It is a rich source of exercises for the rest of the book, so a course covering it will move a little slower, but nothing in Chapters 4 through 14 requires it — if your syllabus omits it, you lose nothing.

Chapters 4, 5 and 6 (Direct, Contrapositive, Contradiction) are the core toolkit and should be read in order — each is easiest to appreciate once you’ve seen the one before it struggle with a proof it wasn’t built for.

Chapters 7 through 9 (Non-Conditional Statements, Proofs Involving Sets, Disproof) apply the three core techniques to new situations rather than introducing new logic. Chapter 8 in particular rewards a quick return to Chapter 1 if set notation has gone rusty.

Chapter 10 (Induction) can be treated as a self-contained unit — most proof courses include it, but the book’s own dependency tree marks it, like Chapter 3, as skippable without breaking continuity elsewhere.

Chapters 11 and 12 (Relations, Functions) build on each other directly — Chapter 12 opens by explicitly reframing functions as a special case of Chapter 11’s relations, so read them back to back rather than leaving a gap between them.

Chapter 13 (Proofs in Calculus) is, by the author’s own statement, not needed for the rest of the book and can be skipped entirely. It is the right chapter to assign only if your course specifically bridges into real analysis.

Chapter 14 (Cardinality) is the natural capstone and depends on Chapters 11 and 12’s function theory (especially bijections) — read it last, after both.

The current edition is revision 3.4 (February 2025), a minor typo-correction pass on the Third Edition (2018) with unchanged ISBNs and chapter numbering — there is nothing dated anywhere in the book, and no age caveat applies to any chapter.

Used In These Programs

This book is used for the Proof Writing / Foundations of Mathematics course in: BS Mathematics · BS Computer Science. Browse all Proof Writing books, all Discrete Mathematics books, or all Mathematics books.

Who Should Read This

Book of Proof is written for exactly the transition point most BS Math and BSCS students hit after a calculus-heavy first year: the moment mathematics stops being about computing answers and starts being about proving statements are true. The author developed it over 18 years of teaching proof-writing at Virginia Commonwealth University and Randolph-Macon College, and it assumes only basic algebra — no calculus is required for Chapters 1 through 12, and even Chapter 13’s calculus proofs assume just a first calculus course, not advanced material. It is not a reference for computational techniques (integration tricks, matrix algorithms and the like); it is entirely about how to read, write and verify a mathematical proof, which makes it the natural book to read before — or alongside — Discrete Mathematics: An Open Introduction, since both books teach direct, contrapositive and induction proofs on very similar material.

Applicable Universities

This book is useful for students at Pakistani universities offering BS Mathematics and BS Computer Science programs, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions, wherever a Proof Writing, Foundations of Mathematics, or transition-to-proof course is required.

FAQs

Related Books

• Discrete Mathematics: An Open Introduction – Oscar Levin (4th Edition)
• Calculus Volume 1 – Strang & Herman (OpenStax)
• Calculus Volume 2 – Strang & Herman (OpenStax)

Book of Proof is the foundation most BS Mathematics and BS Computer Science students need before their upper-level courses make sense — the proof techniques it teaches (direct, contrapositive, contradiction, induction) are assumed knowledge in every subsequent theory course. Browse more Mathematics books for the rest of your semester.

Book of Proof, Third Edition (revision 3.4), by Richard Hammack. Free under a Creative Commons Attribution-NonCommercial-NoDerivative 4.0 International licence. Access for free at https://richardhammack.github.io/BookOfProof/