1. Foundations of Proof

The language of analysis, from the ground up — propositions and quantifiers through direct proof, contrapositive, contradiction, strong induction, equivalence relations, and function proofs, following the arc of Hammack’s Book of Proof.

• Propositions and Truth Tables — Switch the connective and a new truth-table column fills in. All four cases sit side by side for comparison. Two statements with identical columns mean the same thing. If the true rows and false rows match completely, the statements are equivalent. A statement and its contrapositive always match. The converse does not. For example, 'if it rains, the ground gets wet' and 'if the ground is not wet, it did not rain' say the same thing. But 'if the ground is wet, it rained' can be false. A hose wets the ground too.
• Universal and Existential Quantifiers — A game on the number line teaches the quantifiers. Swap the order and watch the same game collapse. One side moves first and the other side answers. 'For all' demands an answer to every challenge. 'There exists' needs just one good answer. Swapping the order changes the claim itself. This pattern becomes the epsilon-delta definition later. For example, for every 🧑 classmate, someone taller exists. But one person taller than everybody does not exist. A single swap changes the whole meaning.
• Direct Proof — Place the sum of two rationals on the number line and follow the computation. It runs straight from hypothesis to conclusion. A direct proof walks straight ahead. Compute with what you are given and the conclusion falls out. Fractions combine over a common denominator into one fraction. So a sum of rationals is rational again. For example, take three quarters of a 🍰 cake and remove five sixths of one. Recut into twelfths: nine pieces minus ten pieces. One straight computation, no detours.
• Proof by Contrapositive — Lay out an even-odd table and set a statement beside its contrapositive. This is the detour for when the direct road is blocked. Some statements resist a frontal attack. Then flip and negate: prove the contrapositive instead. It always shares the original's truth value. Settle one side and the other comes free. For example, if a square is even, the number itself is even. Instead of studying squares, look only at odd numbers. Squaring an odd number always gives an odd number. So an even square never came from an odd number.
• Proof by Contradiction — Assume there are only finitely many primes and derive a contradiction. Watch a new prime slip outside the list. Proof by contradiction assumes the opposite side. Push the false side until it clashes with itself. Then the original claim must be true. Multiplying all the primes and adding one builds that clash. For example, suppose a biggest number exists. Add one and a bigger number appears. The assumption destroys itself. Euclid's prime proof uses exactly this move.
• Proof by Cases and Existence Proofs — Split the plane into four regions and handle one case at a time. Then meet a proof that shows existence without revealing which side holds. A case split must leave no gap. Each region's computation is easy. Miss one region and the whole proof collapses. Existence proofs are different: 'it exists' can be shown without producing it. For example, a 🧑 friend may stand east or west of your house. Either way, the distance home ignores the sign. Checking both directions is exactly a proof by cases.
• Counterexamples and If and Only If — Demolish false claims with a single counterexample. Four plausible claims go on trial, one by one. A 'for all' claim falls to one counterexample. A single failing case makes the whole claim false. An if-and-only-if claim is the opposite job. Each direction needs its own separate proof. For example, take 'every 🧑 classmate wears glasses'. One classmate without glasses ends the claim. One person is enough.
• Strong Induction — Draw the tree that splits a number into prime factors. It shows why the proof must assume everything before it. Ordinary induction uses only the step right before. But split-off pieces land far below, not one step down. Strong induction assumes every earlier step at once. Each piece counts as already settled on the way up. For example, climbing 🪜 stairs, some steps push off two or three steps below. Trusting only the step right beneath you is not always enough. Trust them all, and the next step holds.
• Equivalence Relations — Group numbers by equal remainders. Then test three promises on everything to certify an equivalence relation. An equivalence relation means 'on the same team'. Everyone is on their own team. Teaming is mutual, and it chains through teammates. When all three hold, the whole set splits into non-overlapping teams. For example, split twelve 🧑 classmates into three teams of four. Nobody belongs to two teams at once. Inside a team, everyone matches everyone. Remainder classes look exactly like this.
• Proofs about Composite Functions — Glue two functions together and inspect the composite with tables and arrows. See what the composite's properties force onto each part. If the composite is injective, the first function is injective too. If the composite is surjective, the second function is surjective. The converses fail, and the diagrams show why. Undoing a composite also reverses the order. For example, pack a 📦 box, close the lid, then tie it with string. To open it, the string comes off first. The last step done is the first step undone. That is why inverses of composites reverse the order.