Chapter 5 — Key Takeaways

Proof Strategies II: Contradiction and Cases. A one-page, exam-ready reference.

Strategy selector (read the claim's shape, then pick)

Claim shape Strategy First move
"$P$" with no / impossible / cannot / irrational / infinite / unsolvable Contradiction Assume $\neg P$; break it
"$P$" where objects come in types (parity, sign, prime/composite) Cases Split exhaustively; prove each
"$\exists x\, P(x)$" Existence Build a witness (constructive) or prove a search must succeed (non-constructive)
"$\exists!\, x\, P(x)$" Existence + Uniqueness Prove one exists; then $x_1,x_2$ both work $\Rightarrow x_1=x_2$
"$\forall x\, P(x)$" you suspect is false Counterexample Exhibit one $x$ with $\neg P(x)$
"$P \rightarrow Q$" (default) Direct / Contraposition (Ch. 4) Assume $P$; or prove $\neg Q \rightarrow \neg P$
"$\forall n$" over $\mathbb{N}$ you suspect is true Induction (Ch. 6) Next chapter

Two biggest tells: absence-words (no, impossible, irrational, infinite) → contradiction; a sweeping "for all" you distrust → counterexample hunt before proving.

Proof by contradiction

  • Form proved: $\neg P \rightarrow (q \land \neg q)$. Since $q \land \neg q$ is always false, $\neg P$ is false, so $P$ holds.
  • Why valid: law of the excluded middle ($P$ or $\neg P$, no third option).
  • Template: assume $\neg P$ → derive consequences → hit a statement that contradicts a known fact or an earlier line → conclude $P$.
  • Contradiction can be: internal (against your own setup — $\sqrt 2$'s "lowest terms") or external (against a known fact).
Result Assume for contradiction… The trap that springs
$\sqrt 2$ irrational $\sqrt 2 = p/q$ in lowest terms, $p^2 = 2q^2$ $p,q$ both even ⇒ not lowest terms
Infinitely many primes (Euclid) finitely many: $p_1,\dots,p_k$; set $N=p_1\cdots p_k+1$ a prime divisor of $N$ divides 1
$r$ rational + $x$ irrational ⇒ irrational sum $r+x$ rational $x=(r+x)-r$ would be rational

⚠️ Euclid pitfall: $N=p_1\cdots p_k+1$ need not be prime. $2\cdot3\cdot5\cdot7\cdot11\cdot13+1 = 30031 = 59\times509$. The proof yields a new prime factor, not a new prime.

Proof by cases & WLOG

  • Obligation #1: prove the claim in each case. Obligation #2 (often forgotten): prove the cases are exhaustive — the missing-default bug.
  • Cases may overlap; they may not leave a gap.
  • WLOG = handle one representative of a symmetric set of cases. Legal only under genuine symmetry. Test: swap the variables in the statement; if you get the identical statement, WLOG is fine.
Example Case split
$n^2+n$ even for all integer $n$ $n=2a$ (even) vs. $n=2a+1$ (odd)
Triangle inequality, same-sign $a,b$ both $\ge 0$ vs. both $\le 0$ (symmetric ⇒ WLOG $a,b\ge0$)

Existence & uniqueness

Kind What you must show Yields the object?
Constructive existence exhibit a specific $x$ (or an algorithm); verify $P(x)$ Yes — prized in CS
Non-constructive existence prove $x$ exists w/o producing it (often by contradiction or cases) No — only a guarantee
Uniqueness assume $x_1, x_2$ both satisfy $P$; derive $x_1=x_2$ —
  • $\exists$ needs one witness. $\exists!$ needs a witness AND a collapse argument.
  • "At most one solution" is vacuously true with zero solutions — so a uniqueness proof must include existence.
  • Classic non-constructive proof: irrationals $a,b$ with $a^b$ rational, via cases on whether $\sqrt 2^{\sqrt 2}$ is rational (never says which case is true).

Counterexample / disproof

  • $\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)$ (Ch. 2). One counterexample = complete disproof.
  • Asymmetry: proving "for all" is expensive (∞ cases); disproving it is cheap (1 case). (Popper: one black swan.)
  • Theme 2: passing tests ≠ correctness. $n^2+n+41$ is prime for $n=0..39$ (40 cases!) yet fails at $n=40$: $1681=41^2$.
  • "No counterexample found" = confidence, not proof. Test the boundaries (0, negatives, empty inputs) — that's where universals break (e.g. $a\mid b \land b\mid a \Rightarrow a=b$ fails at $a=3,b=-3$).

CS connection — contradiction is the engine of impossibility

To prove "no program does task $T$": (1) assume program $D$ does $T$; (2) feed $D$ a description of itself; (3) derive that some program must and must not behave a certain way; (4) conclude $D$ can't exist. → Halting problem unsolvable (Ch. 36); some infinities bigger than others (Ch. 10). Self-reference + contradiction.

Toolkit additions (dmtoolkit/logic.py)

def find_counterexample(pred, domain):
    for x in domain:
        if not pred(x):
            return x          # disproves "for all x in domain, pred(x)"
    return None               # no counterexample IN RANGE (not a proof)

def disprove_forall(pred, domain):
    return find_counterexample(pred, domain) is not None
  • The disproof arm of the book's discipline: use code to refute, use proof to certify.
  • Pairs with Ch. 6's recurrences.py: check_identity (the conjecture tester).

Common pitfalls checklist

  • ☐ Forgot to identify what the contradiction clashes with (state the two clashing lines).
  • ☐ Claimed Euclid's $N$ is itself prime (it's only guaranteed to have a new prime factor).
  • ☐ Proof by cases with a missing/un-justified case (not exhaustive).
  • ☐ Used WLOG without genuine symmetry between the variables.
  • ☐ Proved uniqueness but skipped existence (vacuous claim).
  • ☐ Treated "passed many tests" as a proof of a universal claim.