Book of Proof

Overview

Book of Proof introduces the language and methods needed to move from calculating answers to constructing mathematical arguments. Richard Hammack’s third edition, revision 3.4, contains fourteen chapters across sets, logic, counting, proof techniques, relations, functions, calculus proofs, and cardinality. The guide follows this exact author-hosted PDF rather than assuming the older thirteen-chapter organization. Its central lesson is that a proof must explain why a statement follows from definitions and established facts for every case claimed. Examples support exploration, but they do not replace a general argument.

How to study this book

Read definitions slowly and produce examples and nonexamples before attempting proofs. Translate the target statement into its logical form, identify assumptions and conclusions, and choose a method that fits. Draft the argument in full sentences, checking where each assertion comes from. Test conjectures with small cases, but separate that exploration from the final proof. Attempt exercises before consulting the supplied solutions and compare the structure of the reasoning. Keep a list of invalid moves, such as assuming the conclusion or reversing an implication. Rewrite one proof after feedback to practice mathematical communication.

Chapter and section study guide

Chapter 1 — Sets

Sets provide a language for collections, membership, inclusion, and operations. Cartesian products, power sets, indexed families, and familiar number systems extend that language. Distinguish an element from a subset and a set from its cardinality; many later errors begin by confusing these roles. Venn diagrams can guide intuition but a proof must rely on definitions. Russell’s paradox also shows why unrestricted descriptions of collections require care. Learn to move between notation and precise sentences while checking that every object has the intended type.

Study application: Give examples separating membership from inclusion, then prove a simple set identity by following an arbitrary element.

Chapter 2 — Logic

Statements, connectives, conditionals, equivalence, quantifiers, and inference organize mathematical reasoning. The meaning of an implication differs from its converse, and negating a quantified statement changes both the quantifier and the condition. Truth tables help with propositional structure, while quantified claims require attention to domains and order. Translation between English and symbols should clarify meaning rather than merely shorten a sentence. A logically valid form does not guarantee a true premise. The chapter supplies tools for recognizing exactly what must be proved or disproved.

Study application: Negate a statement containing both universal and existential quantifiers, then explain the result in ordinary language.

Chapter 3 — Counting

Counting develops lists, permutations, combinations, inclusion-exclusion, multisets, division, and pigeonhole reasoning. The key task is choosing a model that counts every intended object exactly once. Order, repetition, restrictions, and indistinguishability change the correct method. A numerical formula should follow from a construction or partition of possibilities rather than from a keyword in the question. Combinatorial proofs show how two counts of the same collection establish an identity. Use small cases to test an approach while recognizing that the general justification is what makes it reliable.

Study application: Solve one selection problem with and without order, explaining precisely why the counts differ.

Chapter 4 — Direct Proof

A direct proof begins with the assumptions and uses definitions and established results to reach the conclusion. Definitions are active tools: an assertion about evenness, divisibility, or a set becomes usable when translated into its precise meaning. Cases can organize an argument when the assumptions permit different possibilities. Avoid writing a chain of unexplained algebra or beginning with the desired conclusion as if it were known. The chapter develops the habit of making each step accountable and presenting a complete argument for the full claim.

Study application: Prove a divisibility or parity statement directly, labeling the definition or previous fact supporting each step.

Chapter 5 — Contrapositive Proof

An implication is equivalent to its contrapositive, which reverses and negates the relevant parts. This can make a proof easier when the negation of the conclusion provides a more useful starting point. The method is not the converse and should not be confused with a merely related statement. Congruence examples develop precise use of definitions, while writing guidance emphasizes readable structure. State the reformulated target before proving it so the reader understands why the new argument establishes the original claim.

Study application: Choose an implication suited to contraposition and write both its original and contrapositive forms before proving it.

Chapter 6 — Proof by Contradiction

Contradiction assumes the negation of the desired statement and derives an impossibility from that assumption and accepted facts. The contradiction must be explicit; an unexpected result is not automatically a logical impossibility. Conditional statements require careful identification of the assumptions being retained and the conclusion being negated. The chapter also discusses combining methods and choosing efficient approaches. A successful proof makes clear where the temporary assumption is used and why its failure establishes the claim. Compare with direct or contrapositive methods when those would be simpler.

Study application: Annotate a contradiction proof to identify its temporary assumption, the exact contradiction, and the conclusion discharged at the end.

Chapter 7 — Proving Non-conditional Statements

Biconditionals, equivalence chains, existence, and uniqueness require structures different from a single implication. An if-and-only-if claim needs both directions; existence can be constructive or nonconstructive; uniqueness requires excluding a second distinct possibility. The chapter helps match the logical target with the necessary proof tasks. Supplying one example can establish existence but not uniqueness or a universal statement. Organize the proof so the reader can see which part is being established and avoid assuming that one direction automatically supplies the other.

Study application: Prove a simple existence-and-uniqueness claim using separate paragraphs for construction and exclusion of alternatives.

Chapter 8 — Proofs Involving Sets

Set proofs turn membership and inclusion into statements about arbitrary elements. To prove one set is contained in another, begin with an arbitrary member of the first and establish membership in the second. Equality usually requires both inclusions or an equivalent chain of membership conditions. The chapter applies this method to increasingly substantive examples, including perfect-number material. A diagram can suggest a relationship but does not justify every possible case. Keep the arbitrary element general and translate each operation through its definition.

Study application: Prove a distributive set identity using two inclusions and explain why a picture alone would be insufficient.

Chapter 9 — Disproof

Disproof targets the logical form of a claim. A universal assertion can fail through one counterexample, while an existence claim requires showing that no object satisfies the conditions. Examples that support a conjecture do not establish it, and a failed attempted proof does not establish falsity. The chapter develops deliberate searches for counterexamples and contradiction-based disproofs. Check that a proposed counterexample satisfies the assumptions while violating the conclusion. The aim is precision about what has failed, not merely finding an unusual case.

Study application: Disprove a false universal claim and explicitly verify both the counterexample’s admissibility and its failure of the conclusion.

Chapter 10 — Mathematical Induction

Induction establishes a sequence of claims through a base case and a justified transition. The inductive hypothesis is a temporary assumption about a specified case, not permission to assume the entire theorem. Strong induction and smallest-counterexample reasoning offer related structures for different problems. The chapter connects these methods with arithmetic and sequences, including Fibonacci examples. Choose the starting point carefully and ensure the transition covers every required later case. Explain why the logical chain reaches all claimed indices rather than presenting only a symbolic manipulation.

Study application: Write an induction proof and separately check the base case, exact hypothesis, transition, and range of indices covered.

Chapter 11 — Relations

Relations describe connections among elements and can be studied through properties such as reflexivity, symmetry, and transitivity. Equivalence relations organize sets into classes and correspond to partitions. Congruence provides an important example linking abstract definitions with integer arithmetic. Distinguish proving each property from checking a few pairs. Relations between different sets also require clear domains and codomains. The chapter shows how a precise relation can reveal structure, making later arguments about classes and functions possible without relying on informal similarity.

Study application: Verify an equivalence relation and describe its classes, then explain why those classes form a partition.

Chapter 12 — Functions

A function assigns each domain element exactly one output, and its domain and codomain are part of the mathematical object. Injectivity, surjectivity, composition, inverses, images, and preimages require different proof obligations. A formula alone may not determine whether a function has an inverse. The chapter connects function properties with counting and the pigeonhole principle. Draw examples to explore possibilities, then prove claims using arbitrary elements and definitions. Distinguish the inverse function from the preimage operation, which makes sense even when an inverse function does not exist.

Study application: Analyze one formula under two different domain-and-codomain choices and show how its injectivity or surjectivity changes.

Chapter 13 — Proofs in Calculus

The calculus chapter applies proof techniques to inequalities, limits, continuity, derivatives, sequences, and series. Familiar computational rules now require justification through definitions and estimates. Epsilon-style arguments demand attention to the order of choices and the dependence of one quantity on another. A graph can guide an idea but cannot replace control over all required values. The chapter is a bridge to analysis rather than a complete calculus course. Focus on how an inequality or definition provides the exact logical step needed.

Study application: Prove a simple limit from its definition, explicitly stating how the chosen bound depends on the requested accuracy.

Chapter 14 — Cardinality of Sets

Cardinality compares sets through functions and correspondences, extending counting beyond finite collections. Countable and uncountable sets challenge intuitions based on size, containment, or density. A bijection can establish equal cardinality even when one infinite set is a proper subset of another. Diagonal reasoning and the Cantor-Bernstein-Schröder theorem provide important comparison tools. State exactly which function is constructed and which properties are proved. The chapter synthesizes sets, relations, functions, and proof methods in arguments where a convincing picture is especially unreliable.

Study application: Construct a bijection between two familiar countably infinite sets and explain why inclusion alone does not settle their cardinalities.

Reflection and review

1. What logical form makes your chosen proof method appropriate?
2. Where did an example help you discover a proof without becoming the proof itself?
3. Which unsupported step disappeared when you rewrote an argument in complete sentences?

Source and edition notes

Third edition, revision 3.4; 2018 copyright; fourteen chapters, 380 PDF pages. The linked file identifies itself as edition 3.4 with a 2018 copyright. Its unmodified source-PDF title page is used as the original cover; the complete book remains externally hosted.

• Source record and online reading
• Complete source PDF
• Open Textbook Library catalog