Exercises: Proof by Contradiction and Cases

DataField.Dev

Exercises: Proof by Contradiction and Cases

These run from mechanical warm-ups to full proofs, code, modeling, and a strategy-selection workout. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — attempt them before you peek. For every proof, the rubric rewards a clearly stated assumption-for-contradiction (or an exhaustive case split), explicit identification of which two statements clash, and a clean conclusion that the negation must fail.

Part A — Warm-ups (⭐)

5.1 † A proof by contradiction of "$P$" begins by assuming what, and ends by deriving what? Fill the two blanks in one sentence: "Assume ____, then derive ____."

5.2 For each claim, state in three words or fewer whether its surface shape screams "contradiction" — i.e., does it assert an absence/impossibility? (a) "There is no largest even number." (b) "$7 + 5 = 12$." (c) "$\sqrt{3}$ is irrational." (d) "Some integer is both even and a perfect square."

5.3 † In the infinitude-of-primes proof, we formed $N = (p_1 p_2 \cdots p_k) + 1$. Compute $N$ for the prime list $[2, 3, 5]$, and confirm by hand whether $N$ is itself prime. Does the proof claim $N$ is always prime?

5.4 State the two proof obligations of a uniqueness claim "$\exists! x\, P(x)$." Which one is vacuously satisfied when no $x$ exists at all?

5.5 † A claim is "for all integers $n$, $P(n)$." You suspect it is false. In one sentence, say how many counterexamples you must exhibit to disprove it, and why that number is enough (cite the Chapter 2 negation rule).

5.6 Every integer falls into exactly one of which two parity classes? Write the algebraic form of a member of each class (using an integer parameter), as the chapter does in §5.3.

Part B — Prove it (⭐⭐)

These are full proofs. For each, decide the strategy from the claim's shape before writing — most here want contradiction, cases, or existence/uniqueness — and open with one sentence naming it (the §5.6 habit). State the assumption-for-contradiction or the case split explicitly, and end with $\blacksquare$.

5.7 † (Scaffolded — fill the missing steps.) Prove by contradiction: $\sqrt{3}$ is irrational. Use the fact (provable as in Chapter 4) that if $3 \mid p^2$ then $3 \mid p$. Fill the blanks:

Assume for contradiction that $\sqrt 3 = \frac{p}{q}$ with $p, q$ integers, $q \ne 0$, in ________ terms.
Squaring and clearing denominators gives $p^2 = \underline{\hphantom{xxxx}}\, q^2$.
So $3 \mid p^2$, hence by the stated fact $3 \mid p$, so $p = 3a$ for some integer $a$. Substituting: $9a^2 = 3q^2$, i.e. $q^2 = \underline{\hphantom{xxxx}}$.
Therefore $3 \mid q^2$, so $3 \mid q$. But then $3$ divides ________, contradicting the assumption that the fraction was in lowest terms. $\blacksquare$

5.8 Prove by contradiction: there is no smallest positive rational number. (Hint: if $r$ were the smallest, consider $r/2$.)

5.9 † Prove by contradiction: if $n^2$ is even, then $n$ is even. (This is the parity fact the $\sqrt 2$ proof relied on; here you prove it standalone. Assume $n$ is odd and derive that $n^2$ is odd, contradicting the hypothesis.)

5.10 Prove by cases: for every integer $n$, $n^2$ leaves remainder $0$ or $1$ when divided by $4$ (equivalently, $n^2 \equiv 0$ or $1 \pmod 4$). Split on the parity of $n$.

5.11 † Prove by cases: for all integers $a$ and $b$, the product $ab$ is even if and only if at least one of $a, b$ is even. (Two directions; for the "$\Leftarrow$" direction, use WLOG to assume $a$ is the even one and justify that WLOG is legitimate here.)

5.12 Prove (existence, constructive): there exist two distinct irrational numbers whose sum is rational. Exhibit an explicit pair and verify both properties, citing §5.1 for the irrationality you use.

5.13 † Prove (uniqueness): for every real number $a \ne 0$, there is a unique real $x$ with $ax = 1$ (the multiplicative inverse). Give the existence half, then assume $x_1, x_2$ both work and force $x_1 = x_2$.

5.14 Prove by contradiction: if $r$ is rational and $r \ne 0$ and $x$ is irrational, then $rx$ is irrational. (Mirror the §5.6 proof for $r + x$; where does "$r \ne 0$" get used?)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions live in code/exercise-solutions.py.

5.15 † Write same_parity(a, b) returning True iff integers a and b have the same parity, using only %. Then write three lines that check, over all pairs a, b in range(-5, 6), the claim from Exercise 5.11 ("$ab$ even $\iff$ at least one of $a,b$ is even"). What output confirms the claim held on every tested pair, and why is that still not a proof?

5.16 Write euclid_witness(plist) that, given a list of primes, returns the pair (N, smallest_prime_factor(N)) where $N = \prod(\text{plist}) + 1$ — exactly the construction in §5.1. Run it in your head on [2, 3, 5, 7] and [2, 3, 5, 7, 11, 13] and give the expected output. Confirm the second $N$ is composite yet yields a prime missing from the list.

5.17 † Write first_witness(limit) that searches for the smallest denominator $q$ in $[1, \text{limit}]$ such that some integer $p$ makes $p^2 = 2q^2$ exactly (a rational square root of 2). What does it return for limit = 2000, and what is the relationship between that return value and the theorem of §5.1?

Part D — Find the error (⭐⭐)

Each "proof" below is wrong. State precisely which line fails and why — name the false step or the illegitimate move, don't just say "it's wrong."

5.18 † Claim: "For all reals $a, b$: $\lvert a + b \rvert = \lvert a \rvert + \lvert b \rvert$." "Proof": "Without loss of generality assume $a \ge 0$ and $b \ge 0$. Then $a + b \ge 0$, so $\lvert a + b\rvert = a + b = \lvert a\rvert + \lvert b\rvert$. By WLOG this holds for all $a, b$. ∎" Find the flaw, and give a specific $a, b$ where the claim itself is false.

5.19 Claim: "$\sqrt 2$ is irrational." "Proof": "Assume $\sqrt 2 = p/q$. Then $p^2 = 2q^2$, so $p^2$ is even, so $p$ is even, write $p = 2a$; then $q^2 = 2a^2$, so $q$ is even. Therefore $p$ and $q$ are both even. ∎" The algebra is correct — yet this is not a complete proof. What essential ingredient of the §5.1 argument is missing, and why does its absence break the contradiction?

5.20 † Claim: "If $a \mid bc$ then $a \mid b$ or $a \mid c$." "Proof": "Try $a = 6$, $b = 2$, $c = 3$: $6 \mid 6$, and indeed $6 \mid$ ... hmm, $6 \nmid 2$ and $6 \nmid 3$." The author is confused. Is the claim true or false? Diagnose the reasoning and settle the claim with a clean counterexample.

5.21 Claim (disproof attempt): "$n^2 + n + 41$ is not always prime, because I checked $n = 41$ and got $41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \cdot 43$, which is composite." The conclusion is correct, but a grader marks the work down. What is technically wrong with stopping at $n = 41$ when the chapter's disproof uses $n = 40$? (Hint: a counterexample must be a genuine failing case — is $n = 41$ the smallest, and does that matter for correctness versus credit?)

Part E — Model it & Conjecture and test (⭐⭐⭐)

The hard part of these is the translation: turning prose into a precise discrete-math statement (a function, an $\exists$/$\exists!$ claim, a predicate over a finite domain) before you reason. For the "conjecture and test" problems, search with code first to triage, then prove or disprove — and be explicit about which one the evidence actually licenses (theme four).

5.22 † (Model it.) A compiler vendor advertises a tool LoopGuard that, for any submitted program and input, prints "WILL HALT" or "WILL LOOP FOREVER" and is always correct and always terminates. Translate this advertisement into a precise existence claim about a function, in the style of §5.2. Then state — without writing the full proof — the shape of the argument that refutes it (name the strategy, name the self-referential gadget, and name the assumption the contradiction destroys). Cite the forward reference where this is made rigorous.

5.23 (Model it.) A dating app guarantees: "for every user, there is exactly one ideal match in our database." A skeptic says this guarantee makes two separate promises. Express the guarantee as an $\exists!$ statement about a predicate $\text{Match}(u, v)$, name the two proof obligations the app would owe, and explain which obligation fails if the database is empty — connecting to the §5.4 "vacuous uniqueness" pitfall.

5.24 † (Conjecture and test, then prove/disprove.) Consider the claim: "for every integer $n \ge 1$, the number $n^2 - n + 41$ is prime." Using find_counterexample from this chapter's Toolkit (or a hand search), test it for $n = 1, 2, \dots, 45$. Report the smallest counterexample if one exists. Then prove your verdict: if false, the counterexample is the proof; if you believe it true, explain why testing alone cannot establish it. (Compare carefully with Euler's $n^2 + n + 41$ from §5.5 — they are close cousins.)

5.25 (Conjecture and test.) Define $f(n) = 2^{2^n} + 1$ (the Fermat numbers). Fermat conjectured every $f(n)$ is prime, and verified $f(0), f(1), f(2), f(3), f(4)$. Compute those five values by hand (they grow fast) and confirm they are prime. Then look up or reason about $f(5)$ and state what Euler discovered. Write one paragraph using this episode to illustrate theme two of the book ("it passed the tests is not it is correct"), and explain what kind of proof object Euler's discovery is.

5.26 (Model it + prove.) A hash table stores keys in $m$ buckets. Prove by contradiction: if you insert $m + 1$ keys, then some bucket holds at least two keys (a hash collision is unavoidable). Assume the opposite — that every bucket holds at most one key — and count. (This is the Pigeonhole Principle, formalized in Chapter 17; you can prove this instance now by contradiction.)

Part F — Choosing a strategy & Interleaved

Mixing techniques — and picking the right one — is the real skill. Earlier-chapter problems keep your toolkit sharp.

5.27 † (Strategy selection.) For each claim, name the strategy you'd reach for first (do not prove them), and give the one-word tell that points you there: (a) "There is no integer between $0$ and $1$." (b) "For all integers $n$, $n^3 - n$ is divisible by $3$." (c) "There exists an even prime." (d) "Every graph with at least two vertices has two vertices of the same degree." (e) "$2^n > n^2$ for all $n \ge 5$." (f) "The function $\sin$ is not a polynomial."

5.28 (Ch. 4 + 5.) The $\sqrt 2$ proof used "if $p^2$ is even then $p$ is even," whose contrapositive is "if $p$ is odd then $p^2$ is odd." Prove the contrapositive directly (write $p = 2a + 1$ and expand), then explain in one sentence why a direct proof of the contrapositive is preferable to a direct proof of the original — connecting to the Chapter 4 lesson about choosing the concrete direction.

5.29 † (Ch. 1 + 5.) In "assume $\neg P$ and derive $q \land \neg q$," the formula $q \land \neg q$ is guaranteed false. Build its truth table (two rows) to show this, and name the truth-table category $q \land \neg q$ belongs to (Chapter 1's vocabulary). Then explain, in terms of the implication $\neg P \rightarrow (q \land \neg q)$, why deriving a contradiction forces $P$ true.

5.30 (Ch. 2 + 5.) Write the negation of each statement using the quantifier rules from Chapter 2, then say whether disproving the original is a job for "exhibit one counterexample" or "prove a universal": (a) "$\forall n,\ n^2 + n + 41$ is prime." (b) "$\exists x,\ x^2 = 2$ with $x$ rational." (c) "$\forall a\, \forall b,\ ab = ba$."

5.31 † (Ch. 4 + 5, contrast.) The statement "if $n$ is odd then $n^2$ is odd" can be proved directly; the statement "$\sqrt 2$ is irrational" essentially requires contradiction. In two or three sentences, explain what structural difference between these two claims makes one amenable to direct proof and the other not (the words absence and construct should appear).

5.32 (Deep Dive — constructive vs. non-constructive.) The §5.4 proof that irrationals $a, b$ exist with $a^b$ rational is non-constructive: it never tells you which of $\sqrt 2$ or $\sqrt 2^{\sqrt 2}$ to use as the base. Some logicians (the constructivists) reject such proofs. Write one paragraph explaining, for a programmer, the practical content of the objection: what can you not do with the conclusion of a non-constructive existence proof that you can do with a constructive one? Connect to the §5.4 "$\exists$ vs. return a value" remark.

5.33 (Deep Dive.) The halting-problem argument (§5.2) and the $\sqrt 2$ argument (§5.1) are both proofs by contradiction, but only one uses self-reference. Identify the self-referential step in the halting argument, explain why the $\sqrt 2$ proof needs no such step, and name the other place in the book (per the chapter's forward references) where contradiction-plus-self-reference recurs.

5.34 † (Cases.) Prove by cases: for every integer $n$, exactly one of $n$, $n+1$ is even (so their product $n(n+1)$ is always even). Split on the parity of $n$, and connect your result to the §5.3 "slicker" one-line argument that $n^2 + n$ is even.

5.35 (Model it + contradiction.) Prove: among any $1001$ distinct integers chosen from $\{1, 2, \dots, 2000\}$, there exist two whose difference is exactly $1$ — or show this particular claim is false and repair it. Model the situation by partitioning $\{1, \dots, 2000\}$ into adjacent pairs, then argue by contradiction. State precisely what is guaranteed. (This is a Pigeonhole instance, Chapter 17.)

5.36 (Ch. 3 + 5.) A teammate claims their access-control rules are consistent: there is an assignment of True/False to the propositions $a$ (admin), $g$ (guest), $b$ (banned) satisfying all three rules (i) $a \rightarrow \neg g$, (ii) $g \lor a$, (iii) $b \rightarrow \neg a$, together with the facts $b$ and $\neg g$. Decide whether the rules are jointly satisfiable. If they are, exhibit a satisfying assignment (a constructive existence proof); if not, derive a contradiction from the rules and facts (a proof by contradiction). This is a tiny instance of the satisfiability problem of Chapter 37.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. A complete contradiction proof must name the assumption it destroys; a complete case proof must argue its cases are exhaustive; a complete disproof must exhibit one genuine failing case.