Chapter 4: Proof Strategies I — Direct Proof and Contraposition

"A proof is a program that, when executed in the reader's head, terminates with the word 'convinced.'" — a working definition for programmers

Overview

Every time you write a function, you make a promise. The docstring says binary_search(arr, target) returns the index of target if it is present and -1 otherwise, provided arr is sorted. That promise is a contract: a precondition the caller must honor, and a postcondition you guarantee in return. How do you know your code actually keeps that promise? You run tests. The tests pass. You ship.

And then, three weeks later, an input you never tested crashes production.

This is the gap that proof closes. A test checks one input. A property-based testing tool might check ten thousand. But "for all sorted arrays and all targets" is a statement about infinitely many inputs, and no finite number of tests can ever cover them. A proof can. A proof is the argument that turns "it passed every test we tried" into "it is correct, always, with no input left unchecked." That is theme two of this book — proofs guarantee correctness, testing only suggests it — and this chapter is where you learn to write proofs that actually carry that guarantee.

We start small and concrete, with claims about even and odd numbers, because the logic of a proof is easier to see when the math is easy. By the end you will have two complete strategies in hand — direct proof and proof by contraposition — plus a reusable template, a checklist of the mistakes that sink beginner proofs, and the critical-reading skills to tell a real proof from a convincing-sounding fake. You will also meet divisibility for the first time, the single idea that, six chapters from now, becomes the engine of RSA encryption.

🔗 Connection. Chapters 1–3 built the machinery: propositions and truth tables (Chapter 1), quantifiers like $\forall$ and $\exists$ (Chapter 2), and valid inference rules such as modus ponens (Chapter 3). A proof is what you get when you chain those inference rules together to travel from premises to a conclusion. This chapter is where that machinery starts doing real work.

In this chapter you will learn to:

• Say precisely what a proof is, and why a million passing tests is still not one.
• Use the formal definitions of even, odd, and divides as the moves in a proof.
• Distinguish a theorem, a lemma, a corollary, and a conjecture, and structure a proof a reader can actually follow.
• Write a direct proof of a statement of the form "if $P$ then $Q$."
• Write a proof by contraposition, and know when to reach for it instead.
• Recognize vacuous and trivial proofs, avoid the classic mistakes, and read someone else's proof with a skeptic's eye.

Learning Paths

🏃 Fast Track: If you have written proofs before, skim 4.1–4.2 for our exact definitions (we use them verbatim later), then focus on 4.4 (contraposition) and 4.5 (the template and the mistake catalog). Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Cover each worked proof, then try to reproduce it on paper before reading ours. Do every 🔄 Check Your Understanding before moving on — proof-writing is a skill, and skills need reps.

🔬 Deep Dive: After the chapter, take three statements you proved directly and try to prove them by contraposition (and vice versa). Notice which direction is natural for each — that instinct is what separates fluent provers from formula-followers. The exercise set's interleaved section pushes this further.

4.1 What a proof is (and isn't)

Here is a claim. Read it and decide, right now, whether you believe it:

For every integer $n$, the number $n^2 + n$ is even.

How would you check? The natural first move — the programmer's move — is to try some values. Let's:

Seven for seven. You could write a loop and check the first million integers; it would report "all even." So the claim is probably true. But "probably" is not what mathematics — or a correctness guarantee — is about. The loop checks a finite prefix of an infinite set. The integers it skips are exactly where a counterexample could hide. (Recall from Chapter 2 that a single counterexample is all it takes to demolish a $\forall$ statement.)

A proof is a finite chain of logically valid steps that establishes a statement beyond any possible doubt, for every case at once. It does not sample. It does not estimate. It argues from things already known — definitions, axioms, previously proved results — using only the inference rules of Chapter 3, until the desired conclusion is forced. When a proof is correct, there is no input left to check, because the argument never depended on the input being any particular value.

Here is the proof of the claim above. Do not worry yet about how we found it; just watch what a proof does.

The strategy first. $n^2 + n$ factors as $n(n+1)$ — the product of two consecutive integers. Of any two consecutive integers, one must be even. An even number times anything is even. That is the whole idea; the rest is writing it carefully.

Proof. Let $n$ be an arbitrary integer. Then $n^2 + n = n(n+1)$, the product of the two consecutive integers $n$ and $n+1$. Among any two consecutive integers, exactly one is even. So either $n$ is even or $n+1$ is even; in either case the product $n(n+1)$ has an even factor and is therefore even. Since $n$ was arbitrary, $n^2 + n$ is even for every integer $n$. $\blacksquare$

Notice three things about that argument, because they are what every proof shares:

1. It begins with "let $n$ be an arbitrary integer." We never pick a specific $n$. Whatever we prove about this nameless, arbitrary $n$ holds for all of them. This is how a finite argument covers infinitely many cases — the engine behind universal generalization from Chapter 3.
2. Every step is justified by something already true — a factoring identity, the fact that consecutive integers alternate parity, the fact that an even factor makes a product even.
3. It ends. The little square $\blacksquare$ (or "QED," quod erat demonstrandum, "which was to be demonstrated") marks the point where the conclusion has been reached. A proof is not a vibe; it terminates.

💡 Intuition: Think of a proof as a transcript of a winning argument with an infinitely stubborn skeptic. The skeptic accepts only definitions, axioms, and prior theorems, and challenges every step with "why?" A proof answers every "why" in advance, in a fixed order, until the skeptic has no move left. Tests persuade a trusting reader; proofs defeat a hostile one.

The vocabulary of results

Mathematical claims come with labels that signal their role. You will see all four throughout this book, so let's fix them now.

A theorem is a statement that has been proved true. ("Theorem" is usually reserved for results of some importance; a minor true statement might just be called a "proposition" or a "fact.")

A lemma is a true statement proved mainly as a stepping stone toward a theorem — a helper result, the mathematical equivalent of a private utility function you factor out so the main proof reads cleanly.

A corollary is a true statement that follows quickly from a theorem already proved — a result you get "for free," or nearly so, once the heavy lifting is done.

A conjecture is a statement believed to be true but not yet proved. It is the mathematical analogue of "this passes all our tests, but we haven't proved it." Some conjectures stand for centuries. (Fermat's Last Theorem was a conjecture for 358 years before Andrew Wiles proved it in 1994; the Goldbach conjecture — that every even integer greater than 2 is a sum of two primes — has been verified by computer far past $10^{18}$ and is still unproved.)

⚠️ Common Pitfall: "I checked a lot of cases, so it's a theorem." No — checking cases, however many, leaves it a conjecture. Verification past $10^{18}$ did not turn Goldbach into a theorem. The line between conjecture and theorem is a proof, full stop. This is exactly the line between "our test suite is green" and "this function is correct."

🔄 Check Your Understanding 1. Your colleague runs a fuzz test on a parser overnight: 50 million random inputs, zero crashes. Is "the parser never crashes" now a theorem? What is it? 2. In the proof that $n^2+n$ is even, where exactly did we use the fact that the integers were consecutive? Would the argument survive if we dropped that? 3. Match each to theorem / lemma / corollary / conjecture: (a) "$P \neq NP$"; (b) a small fact about even numbers you prove only so a later proof reads cleanly; (c) "and therefore, since we just proved the general case, the case $n=2$ holds too."

Answers

1. No — it is (strong) evidence, so "the parser never crashes" remains a conjecture. A proof would have to cover all inputs, not 50 million of them. 2. We used it to claim "exactly one of them is even." Two arbitrary integers need not include an even one (e.g., $3$ and $5$), so consecutiveness is essential. 3. (a) conjecture; (b) lemma; (c) corollary.

4.2 Definitions as the raw material

If a proof is a chain of justified steps, definitions are the links you are allowed to use. A beginner's most common mistake is not bad logic — it is reasoning from a vague mental picture of a term instead of its precise definition. In a proof, you may only use what a term officially means. So before we can prove anything about even numbers, we must say, with no wiggle room, what "even" is.

Definition (even and odd). An integer $n$ is even if there exists an integer $k$ such that $n = 2k$. An integer $n$ is odd if there exists an integer $k$ such that $n = 2k + 1$.

Look at the shape of that definition. "Even" is secretly an existential statement (Chapter 2): "$n$ is even" means "$\exists k \in \mathbb{Z}$ such that $n = 2k$." This matters enormously for how proofs work, and it gives us two complementary moves:

• Using the definition (unpacking an existential): if you are told $n$ is even, you may introduce a name for the integer that exists — "since $n$ is even, write $n = 2k$ for some integer $k$." You now have an equation to compute with.
• Proving the definition (establishing an existential): to show some number $m$ is even, you must exhibit an integer that plays the role of $k$ — "let $k = \dots$; then $m = 2k$, so $m$ is even."

That two-way pattern — unpack a hypothesis into an equation, do algebra, repackage the result into a definition — is the most important single habit in this chapter. Watch for it in every proof that follows.

💡 Intuition: A definition is an interface. "Even" exposes exactly one method: "give me a witness $k$ with $n = 2k$." When you use an even number you call that method to get a $k$; when you prove something is even you implement the interface by supplying a concrete $k$. Reasoning from the mental image "even means... you know, divisible by two, like 4 and 6" is reasoning against an interface you haven't actually read.

Now the anchor of Part IV makes its first appearance. We will lean on this definition for the rest of the book, and especially when we build RSA in Chapter 25.

Definition (divides). Let $a$ and $b$ be integers with $a \neq 0$. We say $a$ divides $b$, written $a \mid b$, if there exists an integer $c$ such that $b = ac$. When $a \mid b$ we call $a$ a divisor (or factor) of $b$, and $b$ a multiple of $a$. If no such integer $c$ exists, we write $a \nmid b$.

Two warnings about notation, because they trip up nearly everyone the first week:

⚠️ Common Pitfall: $a \mid b$ is a statement, $a / b$ is a number. The vertical bar $\mid$ is a relation — "$a$ divides $b$" — and is either true or false. The slash $/$ is division — a number. "$3 \mid 12$" is the true statement "3 divides 12." "$3 / 12$" is the number $0.25$. Writing "$3 \mid 12 = 4$" is a type error: you are claiming a true/false statement equals the number 4.

Notice that "even" is just a special case: $n$ is even exactly when $2 \mid n$. And divisibility, like evenness, is an existential statement in disguise — "$a \mid b$" means "$\exists c \in \mathbb{Z}$ with $b = ac$." So the same unpack/repackage habit applies. Here is the habit in miniature, in a result small enough to call a lemma.

Lemma (divisibility is transitive). For all integers $a, b, c$ (with $a, b \neq 0$), if $a \mid b$ and $b \mid c$, then $a \mid c$.

The strategy first. We are given two divisibility facts and must produce a third. So we'll unpack each hypothesis into an equation (each gives us a witness integer), substitute one into the other, and then read off a single witness that proves $a \mid c$. Unpack, substitute, repackage.

Proof. Assume $a \mid b$ and $b \mid c$. By the definition of divides, $a \mid b$ means there is an integer $m$ with $b = am$, and $b \mid c$ means there is an integer $n$ with $c = bn$. Substituting the first equation into the second, $$c = bn = (am)n = a(mn).$$ Since $m$ and $n$ are integers, so is $mn$. Thus there exists an integer — namely $mn$ — that, multiplied by $a$, gives $c$. By the definition of divides, $a \mid c$. $\blacksquare$

That proof is a template you will reuse dozens of times. Every divisibility proof in this book is some variation of unpack each "$\mid$" into an equation, do algebra, exhibit the witness. Sit with it until the rhythm feels automatic.

🔄 Check Your Understanding 1. Rewrite "$7 \mid 56$" purely in terms of the definition (the existential statement), and give the witness. 2. True or false: $5 \mid 0$. Justify from the definition. 3. A student writes, to show $6$ is even, "$6$ is even because it's an even number." What's missing, and what's the one-line fix?

Answers

1. "$\exists c \in \mathbb{Z}$ with $56 = 7c$"; the witness is $c = 8$. 2. True. We need an integer $c$ with $0 = 5c$; take $c = 0$. (Every nonzero integer divides 0.) 3. The student never supplied a witness. Fix: "$6 = 2 \cdot 3$, so taking $k=3$ gives $6 = 2k$; hence $6$ is even." The proof must exhibit the $k$, not restate the claim.

4.3 Direct proof

Most theorems you will prove have the form of a conditional: "if $P$, then $Q$," written $P \rightarrow Q$. ("If $n$ is odd, then $n^2$ is odd." "If $a \mid b$ and $a \mid c$, then $a \mid (b+c)$.") Very often $P$ and $Q$ contain a $\forall$: "for all integers $n$, if $n$ is odd then $n^2$ is odd." The most fundamental strategy for proving such a statement is the direct proof.

Definition (direct proof). A direct proof of a conditional statement $P \rightarrow Q$ proceeds by assuming that $P$ is true and then deriving $Q$ through a chain of valid logical steps (using definitions, algebra, and previously established results). For a universally quantified conditional "$\forall x,\, P(x) \rightarrow Q(x)$," you first fix an arbitrary $x$, then run the direct argument for that $x$.

Why is it legitimate to just assume $P$? Because a conditional $P \rightarrow Q$ makes a claim only about the situation in which $P$ holds. Look back at the truth table for $\rightarrow$ from Chapter 1: when $P$ is false, $P \rightarrow Q$ is automatically true regardless of $Q$. So the only rows we have to worry about are the ones where $P$ is true — and in those, we need $Q$ to be true too. Assuming $P$ and deriving $Q$ handles exactly those rows. (We will return to the "$P$ false" rows in 4.5, where they produce vacuous proofs.)

💡 Intuition: A direct proof of $P \rightarrow Q$ is precisely modus ponens (Chapter 3) run in reverse, as a construction: you are building the machine that, fed a proof of $P$, outputs a proof of $Q$. In programming terms, you are implementing a function whose precondition is $P$ and whose postcondition is $Q$ — and the proof is the body that shows the postcondition always holds when the precondition does.

The direct-proof template

Direct proof of "$\forall x,\ P(x) \rightarrow Q(x)$": 1. "Let $x$ be arbitrary, and assume $P(x)$." (Fix the variable; assume the hypothesis.) 2. Unpack $P(x)$ using the relevant definitions (turn it into equations you can manipulate). 3. Do the algebra / reasoning to head toward $Q(x)$. 4. Repackage the result into the definition of $Q(x)$. 5. "Therefore $Q(x)$. Since $x$ was arbitrary, the statement holds for all $x$. $\blacksquare$"

Let's run it three times, with increasing subtlety.

Example 1: odd squared is odd

Theorem. For every integer $n$, if $n$ is odd, then $n^2$ is odd.

The strategy first. Assume $n$ is odd, so $n = 2k+1$ for some integer $k$ (unpack). Square it, and force the result into the shape $2(\text{something}) + 1$ — that "something" is the witness that proves $n^2$ is odd (repackage). The only craft is the algebra in between.

Proof. Let $n$ be an arbitrary integer and assume $n$ is odd. By definition, there is an integer $k$ with $n = 2k + 1$. Then $$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$$ Let $m = 2k^2 + 2k$. Since $k$ is an integer, $m$ is an integer, and $n^2 = 2m + 1$. By the definition of odd, $n^2$ is odd. Since $n$ was an arbitrary odd integer, the statement holds for all integers $n$. $\blacksquare$

The pivotal move is the regrouping $4k^2 + 4k + 1 = 2(2k^2+2k) + 1$. We manufactured the form $2m+1$ because that is exactly what "odd" requires. Always keep the target definition in view; it tells you what shape to aim the algebra toward.

Example 2: a divisibility theorem (the anchor at work)

Theorem. For all integers $a, b, c$ (with $a \neq 0$), if $a \mid b$ and $a \mid c$, then $a \mid (b + c)$.

The strategy first. Two hypotheses, each an existential — unpack both into equations, each giving a witness. Add the equations, factor out $a$, and read off a single witness for $a \mid (b+c)$. This is the "divisor of two things divides their sum" fact that underlies the Euclidean algorithm we'll build in Chapter 22.

Proof. Assume $a \mid b$ and $a \mid c$. By the definition of divides, there exist integers $s$ and $t$ with $b = as$ and $c = at$. Adding these equations, $$b + c = as + at = a(s + t).$$ Since $s$ and $t$ are integers, $s + t$ is an integer. Thus there is an integer — namely $s+t$ — with $b + c = a(s+t)$, so by the definition of divides, $a \mid (b + c)$. $\blacksquare$

🔗 Connection. This unassuming lemma is load-bearing. In Chapter 22 we prove the Euclidean algorithm correct, and its central step is exactly "any common divisor of $a$ and $b$ also divides their difference." That, in turn, is what makes computing $\gcd$ fast, which is what makes RSA key generation practical (Chapter 25). Small, carefully proved facts compose into large systems — theme three, abstraction, in action.

Example 3: a "both directions" theorem (proving an iff)

Some theorems are biconditionals: "$P$ if and only if $Q$," written $P \leftrightarrow Q$. A biconditional is two conditionals bundled together, $(P \rightarrow Q) \land (Q \rightarrow P)$, so you prove it by proving both directions. (We saw $\leftrightarrow$ unpack this way in Chapter 1.)

Theorem. An integer $n$ is odd if and only if $n^2$ is odd.

The strategy first. Two directions. The forward direction ($n$ odd $\Rightarrow n^2$ odd) is exactly Example 1 — done. The reverse direction ($n^2$ odd $\Rightarrow n$ odd) is awkward to attack directly: from "$n^2 = 2k+1$" there's no clean way to extract information about $n$ itself. Hold that thought — it is precisely the situation that contraposition, the next section, was made for. For now we prove the forward half and flag the reverse.

Proof (forward direction). If $n$ is odd then $n^2$ is odd: this is exactly Example 1. $\blacksquare$ (for this direction)

The reverse direction — if $n^2$ is odd then $n$ is odd — resists a direct attack, because assuming $n^2$ is odd gives us an equation about $n^2$, not about $n$, and there is no tidy algebra to "take a square root" inside the integers. This is the cue to switch strategies. Section 4.4 is built around finishing exactly this proof.

Direct proof, verified by computation

Theme four of this book is that computation and proof are complementary. A proof settles all cases; code lets you check a claim on many cases cheaply, which is what you do before investing in a proof (and which can catch a false conjecture before you waste an afternoon on it). Here is the parity claim from Example 1, exercised on a range of inputs:

def is_odd(n):
    return n % 2 == 1

# Conjecture: for every odd n, n*n is odd. Test it before trusting it.
counterexample = None
for n in range(-50, 51):
    if is_odd(n) and not is_odd(n * n):
        counterexample = n
        break

print(counterexample)
# Expected output:
# None

The output None means "no counterexample in $[-50, 50]$" — encouraging, but it checks 101 integers, not all of them. The proof in Example 1 is what upgrades that encouragement into certainty. Run the test to gain confidence and catch mistakes; write the proof to know.

🔄 Check Your Understanding 1. In Example 1, identify the exact step that is the "unpack" and the exact step that is the "repackage." 2. Prove directly: for every integer $n$, if $n$ is even then $n^2$ is even. (Mimic Example 1.) 3. Why can't we prove the biconditional in Example 3 just by proving the forward direction?

Answers

1. Unpack: "there is an integer $k$ with $n = 2k+1$." Repackage: "let $m = 2k^2+2k$; then $n^2 = 2m+1$, so $n^2$ is odd." 2. Assume $n = 2k$. Then $n^2 = 4k^2 = 2(2k^2)$; with $m = 2k^2$ (an integer), $n^2 = 2m$, so $n^2$ is even. $\blacksquare$ 3. A biconditional asserts both $P \rightarrow Q$ and $Q \rightarrow P$. Proving only $P \rightarrow Q$ leaves the converse unestablished, and the converse can fail even when the original holds.

4.4 Proof by contraposition

We left Example 3 stuck: we need "if $n^2$ is odd, then $n$ is odd," but the direct attack stalls. The fix is one of the most elegant moves in all of mathematics, and it rests on a logical equivalence you already proved in Chapter 1.

Recall the contrapositive of a conditional.

Definition (contrapositive). The contrapositive of the conditional $P \rightarrow Q$ is the conditional $\neg Q \rightarrow \neg P$ (negate both parts and swap their order). A conditional and its contrapositive are logically equivalent: $P \rightarrow Q \equiv \neg Q \rightarrow \neg P$.

You verified this equivalence with a truth table back in Chapter 1; here it is again, because the whole technique stands on it:

The two boxed columns, $P \rightarrow Q$ and $\neg Q \rightarrow \neg P$, are identical row for row. They are the same statement wearing different clothes. So if you want to prove $P \rightarrow Q$ but the direct route is painful, you are entirely free to prove $\neg Q \rightarrow \neg P$ instead — and a direct proof of that is a proof by contraposition of the original.

💡 Intuition: Contraposition is "prove it by ruling out the only way it could fail." The statement "$P \rightarrow Q$" can only be false in the world where $P$ holds but $Q$ fails. To rule that world out, assume $Q$ fails ($\neg Q$) and show that $P$ must fail too ($\neg P$) — so the dangerous world (P true, Q false) can never occur. Same destination as a direct proof, approached from behind.

⚠️ Common Pitfall: the contrapositive vs. the converse. The converse of $P \rightarrow Q$ is $Q \rightarrow P$ — and it is not equivalent to the original. ("If it rains, the ground is wet" does not give you "if the ground is wet, it rained" — a sprinkler also wets the ground.) The contrapositive $\neg Q \rightarrow \neg P$ is equivalent. Mixing them up is the single most common logic error in beginner proofs. Memorize: converse = swap; contrapositive = swap and negate both. Only the contrapositive is safe to prove in place of the original.

The contraposition template

Proof by contraposition of "$P \rightarrow Q$": 1. State the strategy: "We prove the contrapositive, $\neg Q \rightarrow \neg P$." 2. Write down $\neg Q$ and $\neg P$ explicitly (carefully negate each — Chapter 2's negation rules apply, especially for quantifiers). 3. Now give a direct proof of $\neg Q \rightarrow \neg P$: assume $\neg Q$, derive $\neg P$. 4. Conclude: "This proves the contrapositive, which is equivalent to the original statement. $\blacksquare$"

Example 4: finishing the iff from Example 3

Theorem. For every integer $n$, if $n^2$ is odd, then $n$ is odd.

The strategy first. Direct proof stalls because "$n^2$ odd" won't factor into information about $n$. So flip it. The contrapositive of "if $n^2$ is odd then $n$ is odd" is "if $n$ is not odd then $n^2$ is not odd," i.e., "if $n$ is even then $n^2$ is even" — which we already proved directly in the Check-Your-Understanding above. Contraposition converts a hard problem into one we've solved.

Proof (by contraposition). We prove the contrapositive: if $n$ is even, then $n^2$ is even. (Here $\neg Q$ is "$n$ is not odd," i.e. "$n$ is even," and $\neg P$ is "$n^2$ is not odd," i.e. "$n^2$ is even" — using that an integer is even exactly when it is not odd.) Assume $n$ is even, so $n = 2k$ for some integer $k$. Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Since $2k^2$ is an integer, $n^2$ is even. This proves the contrapositive, and therefore the original statement: if $n^2$ is odd, then $n$ is odd. $\blacksquare$

Combine Example 1 (forward) and Example 4 (reverse) and we have, at last, the full biconditional from Example 3: $n$ is odd if and only if $n^2$ is odd. Two directions, two strategies, one theorem.

🚪 Threshold Concept. Here is an idea that reshapes how you'll read every conditional from now on: a statement and its contrapositive are interchangeable, but a statement and its converse are not. Once this is reflex, you gain a second angle of attack on every "if–then" you ever try to prove — and you stop making the converse error that quietly wrecks so many arguments. When a direct proof stalls, your first instinct should become: "what does the contrapositive look like?" That single habit will carry you through the harder proofs in Chapters 5, 22, and beyond. (One step remains — assuming the conclusion is false and deriving an outright contradiction — and that is proof by contradiction, the headline technique of Chapter 5.)

Example 5: when the negation needs care

Contraposition's one hazard is step 2: negating $P$ and $Q$ correctly. When they contain "even/odd" or quantifiers, sloppiness here sinks the proof. Here is a case where the negation does the heavy lifting.

Theorem. For all integers $a$ and $b$, if $a + b$ is odd, then $a$ and $b$ have opposite parity (one even, one odd).

The strategy first. Proving "opposite parity" directly from "$a+b$ odd" means splitting into cases immediately. Cleaner: contrapose. The negation of "$a$ and $b$ have opposite parity" is "$a$ and $b$ have the same parity" (both even or both odd). The negation of "$a+b$ is odd" is "$a+b$ is even." So the contrapositive reads: if $a$ and $b$ have the same parity, then $a+b$ is even. That we can prove cleanly — though it still has two sub-cases.

Proof (by contraposition). We prove: if $a$ and $b$ have the same parity, then $a + b$ is even. Assume $a$ and $b$ have the same parity. There are two cases.

Case 1: both even. Write $a = 2j$ and $b = 2k$ for integers $j, k$. Then $a + b = 2j + 2k = 2(j+k)$, which is even.

Case 2: both odd. Write $a = 2j+1$ and $b = 2k+1$. Then $a + b = 2j + 2k + 2 = 2(j + k + 1)$, which is even.

In both cases $a + b$ is even, proving the contrapositive. Hence if $a + b$ is odd, then $a$ and $b$ have opposite parity. $\blacksquare$

(That two-case split inside the proof is a preview of proof by cases, which Chapter 5 develops in full. Here it is just the natural way to handle "same parity.")

🐛 Find the Error. A student tries to prove "if $n^2$ is even then $n$ is even" like this: "The contrapositive is: if $n$ is even then $n^2$ is even. Assume $n$ is even, $n=2k$, then $n^2 = 4k^2$ is even. Done." The algebra is correct — but the proof is broken. What went wrong?

Answer

The student wrote the converse, not the contrapositive, then negated nothing. The contrapositive of "if $n^2$ is even then $n$ is even" is "if $n$ is odd then $n^2$ is odd" (negate both parts). What the student actually proved — "if $n$ is even then $n^2$ is even" — is the converse-with-a-twist and does not establish the original. The correct contraposition: assume $n$ is odd, $n = 2k+1$, so $n^2 = 2(2k^2+2k)+1$ is odd; this is $\neg Q \rightarrow \neg P$ and finishes the proof. Lesson: write $\neg P$ and $\neg Q$ out explicitly before you start.

🔄 Check Your Understanding 1. Give the contrapositive and the converse of: "If $n$ is divisible by 6, then $n$ is divisible by 3." Which one is guaranteed true given the original? 2. You must prove "if $5n + 3$ is even, then $n$ is odd." Which direction (direct or contrapositive) looks easier, and what is the contrapositive? 3. The contrapositive of "$\forall x,\ P(x) \rightarrow Q(x)$" — does the $\forall$ stay or become an $\exists$?

Answers

1. Contrapositive: "if $n$ is not divisible by 3, then $n$ is not divisible by 6" — guaranteed true (equivalent to the original). Converse: "if $n$ is divisible by 3, then $n$ is divisible by 6" — not guaranteed (9 is divisible by 3, not by 6). 2. Contraposition is easier: assume $n$ is even ($\neg(n \text{ odd})$), $n = 2k$, then $5n + 3 = 10k + 3 = 2(5k+1) + 1$ is odd — i.e., not even. That proves the contrapositive "if $n$ is even then $5n+3$ is odd." 3. It stays $\forall$: the contrapositive is "$\forall x,\ \neg Q(x) \rightarrow \neg P(x)$." We negate the parts of the inner conditional, not the quantifier.

4.5 Proof template and common mistakes

You now have two strategies. Before adding more (Chapter 5 brings contradiction and cases), let's consolidate into one reusable template and catalog the mistakes that most often turn a proof attempt into a non-proof. Reading bad proofs is the fastest way to learn to write good ones.

The universal proof template

Almost every proof in Part I fits this skeleton. Internalize it and the blank page stops being scary.

The proof template. 1. Read the statement and name its form. Is it $P \rightarrow Q$? A $\forall$? A biconditional? An existential ("there exists")? The form dictates the strategy. 2. Choose a strategy and announce it. "We give a direct proof." / "We prove the contrapositive." / "We prove both directions." Tell the reader the plan. 3. Set up. Fix arbitrary variables ("let $n$ be an arbitrary integer"); assume the hypothesis (or, for contraposition, assume $\neg Q$). 4. Unpack definitions into equations or concrete statements you can manipulate. 5. Work toward the goal, keeping the target definition in view so you know what shape to aim for. Justify each nontrivial step. 6. Repackage the result into the goal's definition. 7. Conclude and close with a sentence tying back to the claim, and the $\blacksquare$.

Two special shapes: vacuous and trivial proofs

The truth table for $\rightarrow$ has two rows we set aside in 4.3 — the rows where the hypothesis is false, and the row where the conclusion is true. They give rise to two proofs that feel like cheating but are completely legitimate.

Definition (vacuous proof). A vacuous proof establishes $P \rightarrow Q$ by showing that the hypothesis $P$ is always false. Since a conditional with a false hypothesis is true (rows 3–4 of the table), the implication holds — vacuously — no matter what $Q$ says.

Definition (trivial proof). A trivial proof establishes $P \rightarrow Q$ by showing that the conclusion $Q$ is always true, without using $P$ at all. Since a conditional with a true conclusion is true (rows 1 and 3), the implication holds.

Vacuous example. "For every integer $n$, if $n^2 < 0$, then $n = n + 1$." The hypothesis $n^2 < 0$ is false for every integer (squares are never negative), so the conditional is vacuously true — the absurd conclusion never gets tested.

Trivial example. "For all integers $a, b$, if $a > b$, then $a^2 + b^2 \ge 0$." The conclusion holds for all integers regardless of the hypothesis (a sum of squares is never negative), so the implication is trivially true; we never needed $a > b$.

💡 Intuition: Vacuous and trivial proofs are not tricks — they are exactly the two "easy" rows of the implication truth table cashed out as proof strategies. They matter in CS more than they look: an algorithm's correctness claim is often vacuously true on inputs its precondition excludes (you don't owe any guarantee on an unsorted array if your contract requires a sorted one), and a base case in an induction proof (Chapter 6) is frequently trivial.

The mistake catalog

Here are the errors that most reliably break a beginner's proof. Each is paired with its fix.

⚠️ Common Pitfall: proving the converse. Assuming $Q$ and deriving $P$ proves $Q \rightarrow P$, not $P \rightarrow Q$. Fix: before writing, state $P$ and $Q$ explicitly; make sure you assume the right one.

⚠️ Common Pitfall: "proof by example." Verifying $P \rightarrow Q$ for $n = 1, 2, 3$ proves nothing about all $n$ (4.1). Fix: fix an arbitrary variable; never a specific number. (The one exception: to prove an existential "$\exists x,\ Q(x)$," a single well-chosen example is a complete proof — there, one witness is exactly what's required.)

⚠️ Common Pitfall: reusing a variable name as if it were the same number. Writing $a = 2k$ and $b = 2k$ forces $a = b$ — you've secretly assumed they're equal. Fix: fresh names for independent quantities: $a = 2j$, $b = 2k$.

⚠️ Common Pitfall: assuming what you want to prove ("begging the question"). Slipping the conclusion in as a step. Fix: every step must follow from definitions, hypotheses, or prior results — not from the goal.

⚠️ Common Pitfall: circular or backward algebra. "Proving" an equation by manipulating both sides until you reach "$0 = 0$" shows the steps are reversible only if you say so. Fix: start from one side (or from known facts) and reach the other; or explicitly note each step is an equivalence.

⚠️ Common Pitfall: division by something that might be zero. Dividing by a variable that could be 0 (or taking a "square root" inside the integers, as in 4.3) introduces unjustified steps. Fix: multiply instead of divide where possible; case-split on whether the quantity is zero.

🔄 Check Your Understanding 1. Is "for all integers $n$, if $n \neq n$, then $n = 7$" true? What kind of proof applies? 2. A proof of "if $a \mid b$ then $a \mid b^2$" begins: "Assume $a \mid b^2$." Spot the error before reading on. 3. Why is "to prove $\exists x,\ x^2 = 9$, take $x = 3$" a complete proof, even though it's a single example?

Answers

1. True, by a vacuous proof: the hypothesis $n \neq n$ is false for every integer, so the conditional holds regardless of the conclusion. 2. It assumed the converse's hypothesis: the theorem's hypothesis is $a \mid b$, but the proof assumed $a \mid b^2$. It should start "Assume $a \mid b$." 3. Because the claim is existential — it asserts that some $x$ works — and exhibiting one ($x=3$, with $3^2 = 9$) is precisely what "there exists" demands. The "no examples!" rule is about universal claims.

4.6 Reading proofs critically

Half of working with proofs is writing them; the other half is reading them — checking a textbook's proof, a paper's argument, or (most often, in a job) a colleague's reasoning in a design doc or a code review. A proof you cannot check is a proof you are taking on faith, which defeats the purpose. Reading critically is an active skill, and here is the routine.

How to read a proof: 1. Identify the claim and its form before reading the argument. Conditional? Universal? Existential? Know what must be established. 2. Find the strategy. Look for the announcement ("we prove the contrapositive," "by induction"). If none is stated, infer it from the first move: does the author assume $P$ (direct), assume $\neg Q$ (contraposition), or assume $\neg(\text{whole claim})$ (contradiction, Chapter 5)? 3. Check the setup. Are variables fixed as arbitrary, or did the author secretly pick a convenient value? Is the hypothesis assumed correctly (not the converse)? 4. Justify each step. For every line, ask "why does this follow?" Name the definition, prior result, or algebraic identity. A step you can't justify is a hole until proven otherwise. 5. Check the close. Does the last line actually state the claim — or a near-miss (the converse, a special case)?

Let's practice on a flawed proof. Critical reading shines brightest on arguments that are wrong, because the bug is the lesson.

🐛 Find the Error. A textbook-looking proof claims: "Claim. For all integers $a$ and $b$, if $a \mid b$ and $b \mid a$, then $a = b$." "Proof. Since $a \mid b$, write $b = ak$. Since $b \mid a$, write $a = bm$. Substituting, $a = bm = (ak)m = a(km)$, so $km = 1$. Since $k$ and $m$ are integers and $km = 1$, we get $k = m = 1$. Therefore $b = ak = a \cdot 1 = a$. $\blacksquare$" Run the reading routine. Where does it break — and is the claim even true?

Answer

Step 4 catches it. From $km = 1$ with $k, m$ integers, it does not follow that $k = m = 1$: the other integer solution is $k = m = -1$. The author silently dropped a case. With $k = m = -1$ we get $b = ak = -a$, so the correct conclusion is $a = b$ or $a = -b$ — equivalently $\lvert a\rvert = \lvert b\rvert$. The claim as stated is false: $a = 2,\ b = -2$ satisfy $a \mid b$ and $b \mid a$ but $a \neq b$. That pair is a counterexample (Chapter 2). Two lessons: (1) "$km = 1$ over the integers" has two solutions — always check for the negative case; (2) a slick-looking proof can still prove a false statement if it skips a case. Reading critically means hunting exactly for the dropped case.

💡 Intuition: Treat a proof the way you treat a pull request you're reviewing. You don't just read it top to bottom nodding along; you look for the off-by-one, the unhandled edge case, the assumption that holds "usually." The integer solutions of $km = 1$ are the proof-world version of an unhandled -1. The same suspicion that makes you a good code reviewer makes you a good proof reader.

🔄 Check Your Understanding 1. When a proof states no strategy, what three first-moves tell you whether it's direct, contrapositive, or (Chapter 5) contradiction? 2. In the flawed $a \mid b,\ b \mid a$ proof, which step of the reading routine surfaced the bug, and what is a one-line counterexample to the original claim?

Answers

1. Direct: the author assumes $P$ (the hypothesis). Contrapositive: the author assumes $\neg Q$. Contradiction: the author assumes the negation of the entire claim and aims for an absurdity.
2. Step 4 ("justify each step") — the jump from $km=1$ to $k=m=1$ is unjustified (it ignores $k=m=-1$). Counterexample: $a = 2,\ b = -2$.

Project Checkpoint: a conjecture-tester for the Toolkit

Theme four — computation and proof are complementary — is the heartbeat of this chapter. A proof settles a universal claim; running code tests it on many cases, which is what you do before you spend effort proving it (and what saves you from "proving" something false). The logic.py module you began in Chapters 1–3 already evaluates predicates over finite domains. Let's add the natural companion: a function that searches a domain for a counterexample to a universally quantified claim — exactly the object that, by Chapter 2, refutes a $\forall$ statement in one shot.

Add to dmtoolkit/logic.py:

def find_counterexample(predicate, domain):
    """Return the first x in domain with predicate(x) False, else None.
    A returned x DISPROVES 'for all x, predicate(x)'. Returning None is
    EVIDENCE the claim holds on this domain -- not a proof (see Chapter 4)."""
    for x in domain:
        if not predicate(x):
            return x
    return None

def holds_for_all(predicate, domain):
    """True iff predicate(x) holds for every x in domain (a finite check)."""
    return find_counterexample(predicate, domain) is None

if __name__ == "__main__":
    # Claim A (a theorem we PROVED in 4.3): for every odd n, n*n is odd.
    claimA = lambda n: (n % 2 == 0) or (n * n) % 2 == 1   # "n odd -> n*n odd"
    print(find_counterexample(claimA, range(-50, 51)))
    # Claim B (FALSE): every integer n>=2 satisfies n*n - n + 41 is prime.
    def primeish(n):
        m = n * n - n + 41
        return all(m % d for d in range(2, m))
    print(find_counterexample(primeish, range(2, 60)))
    # Expected output:
    # None
    # 41

The first call returns None: no counterexample to "odd squared is odd" in $[-50,50]$ — consistent with the proof in 4.3, which makes the guarantee total. The second call returns 41: the famous "prime-generating" expression $n^2 - n + 41$ produces primes for many $n$ but fails at $n = 41$, where $41^2 - 41 + 41 = 41^2$ is composite. That single returned value is a counterexample — and it is a crisp reminder that a long run of confirming cases is not a proof. Your Toolkit can now both flag a claim worth proving (no counterexample found) and kill a false one (a counterexample found) before you invest in the proof.

Toolkit so far: logic.py — truth tables and tautology/equivalence checking (Chapters 1–3), now extended with find_counterexample and holds_for_all. As the book proceeds you'll grow this into a full discrete-math library; the judgment you're building here — when "no counterexample found" is reassurance and when you need a proof — is the point of the whole project.

Summary

A proof is a finite chain of logically valid steps that establishes a statement for every case at once — the guarantee that testing can only approximate.

The vocabulary of results:

The two definitions this chapter runs on (both are existential statements in disguise):

The two strategies:

• The master habit: unpack each hypothesis (turn a definition into an equation), do algebra, then repackage the result into the goal's definition.
• A conditional and its contrapositive ($\neg Q \rightarrow \neg P$) are logically equivalent; a conditional and its converse ($Q \rightarrow P$) are not. Prove the contrapositive freely; never substitute the converse.
• A biconditional $P \leftrightarrow Q$ is proved in both directions ($P \rightarrow Q$ and $Q \rightarrow P$); the two directions may use different strategies.
• Vacuous proof: the hypothesis is always false. Trivial proof: the conclusion is always true. Both are legitimate (they are the "easy" rows of the $\rightarrow$ truth table).
• Top mistakes: proving the converse; proof by example (for a universal claim); reusing a variable name for two independent quantities; assuming the conclusion; dividing by a possibly-zero quantity. For an existential claim, by contrast, one witness is a full proof.
• Reading a proof: name the claim's form → find the strategy → check variables are arbitrary → justify every step → verify the last line states the actual claim. Hunt for the dropped case.

Spaced Review

Retrieval strengthens memory. Answer from memory before checking.

1. (Ch. 3) A direct proof of $P \rightarrow Q$ "constructs" which inference rule — and what does that rule let you conclude once you also have a proof of $P$?
2. (Ch. 3) Name the fallacy committed by someone who proves $Q \rightarrow P$ and claims to have proved $P \rightarrow Q$. How does it relate to the converse?
3. (Ch. 2) Write the negation of "$\forall n \in \mathbb{Z},\ P(n)$." Why is that negation the precise reason a single counterexample disproves a universal claim?
4. (Ch. 2) The statement "$a \mid b$" hides a quantifier. Which one, and over what variable? Write "$a \mid b$" as a fully quantified statement.

Answers

1. Modus ponens: from $P \rightarrow Q$ and $P$, conclude $Q$. A direct proof builds the $P \rightarrow Q$ half; combined with a proof of $P$, modus ponens delivers $Q$. 2. Affirming the consequent (Chapter 3). It is the converse error: $Q \rightarrow P$ is the converse of $P \rightarrow Q$, and the converse is not equivalent to the original. 3. The negation is "$\exists n \in \mathbb{Z},\ \neg P(n)$." A universal claim's negation is exactly "some case fails," so producing one failing case (a counterexample) is a proof of the negation, refuting the claim. 4. The existential quantifier $\exists$, over the integer $c$: "$\exists c \in \mathbb{Z},\ b = ac$" (with $a \neq 0$).

What's Next

You can now prove a conditional head-on (direct proof) or by attacking the only way it could fail (contraposition). But some statements resist both — most famously, negative claims like "$\sqrt{2}$ is irrational" or "there is no largest prime," where there is nothing concrete to construct and no clean contrapositive. For those you assume the statement is false and chase that assumption until it collapses into an absurdity: proof by contradiction. Chapter 5 develops it, alongside proof by cases (which we previewed in Example 5) and the techniques for existence and uniqueness proofs — and it shows how contradiction is the very strategy used to prove that some problems can never be solved by any program at all. The strategies compound from here.