Further Reading: Proof by Contradiction and Cases

Annotated pointers for going deeper. Start with the textbook sections to shore up technique, then follow whichever thread pulls you — the famous proofs ($\sqrt 2$, infinitude of primes), the impossibility results that contradiction unlocks, or the discipline of disproof by counterexample.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §1.7–§1.8 The market-standard treatment of proof methods: direct proof, contraposition, contradiction, proof by cases, exhaustive proof, and existence/uniqueness, with a deep, well-graded exercise bank. §1.8 has the counterexample discipline and many "prove or disprove" problems — the best source if you want more drill than this chapter provides.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), "Proofs" chapters Freely available. The most CS-flavored development of proof technique in print. Its treatment of proof by contradiction (including the $\sqrt 2$ proof) and the "well ordering" companion method is written for exactly our audience, and it foreshadows the impossibility results of later CS courses with the same spirit as §5.2. Highly recommended as a companion.

Velleman, How to Prove It (3rd ed.), the chapters on proof strategies The gentlest careful treatment of proof-writing anywhere. If the form of a contradiction proof or a proof by cases still feels shaky — where exactly does the contradiction go? what must I argue to close the cases? — this is the standard recommendation, with line-by-line scaffolding.

The famous proofs, in their original spirit

Hardy, A Mathematician's Apology (Cambridge), §§12–14 Tier 2. The source of this chapter's epigraph. Hardy presents both showpiece proofs of the chapter — the irrationality of $\sqrt 2$ and Euclid's infinitude of primes — and argues, in beautiful prose, why they are beautiful. Short, non-technical, and the best motivation you will find for caring about elegance in proof. (A free public-domain PDF circulates online; any edition is fine.)

Aigner & Ziegler, Proofs from THE BOOK (Springer), opening chapters on primes and irrationality Tier 2. A celebrated collection of especially elegant proofs. Its first chapters give six proofs that there are infinitely many primes (Euclid's contradiction argument among them) and several proofs of irrationality — perfect for seeing that a single theorem can be reached by very different strategies, the §5.6 lesson taken to its extreme.

Where contradiction leads: impossibility in CS

Sipser, Introduction to the Theory of Computation (3rd ed.), Chapter 4 (§4.2, the halting problem) The rigorous version of the §5.2 preview. Sipser proves the undecidability of the halting problem by exactly the assume-it-exists-and-diagonalize contradiction we sketched, once a precise model of "program" (the Turing machine) is in hand. This is the destination Chapter 36 builds toward; reading §4.2 now shows you the shape you are aiming at.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), §8.1 (the $\Omega(n \log n)$ comparison-sort lower bound) A second impossibility result proved by a counting/contradiction argument in the same family as the compression bound in Case Study 1: there is no comparison sort faster than $n \log n$ in the worst case. The decision-tree counting here is the grown-up version of "$2^n$ inputs cannot fit in fewer slots."

On counterexamples and the limits of testing

Lakatos, Proofs and Refutations (Cambridge) Tier 2. A classic dialogue on how counterexamples drive mathematics — how a conjecture is refined by the very examples that break it. The perfect philosophical companion to §5.5's "disprove first, prove the survivors," and to the §5.5 Popper analogy about refutation versus confirmation.

"Nearly All Binary Searches and Mergesorts Are Broken" (Joshua Bloch, Google Research Blog, 2006) Free online. Tier 2. A real, long-lived bug that survived years of testing — a visceral argument for the §5.5 maxim that "it passed the tests" is not "it is correct," and for hunting boundary counterexamples (here, an integer overflow at large sizes).

Suggested order

  1. Read Rosen §§1.7–1.8 for technique and drill, alongside re-reading §§5.1–5.6 here.
  2. Read the MIT 6.042 proofs chapters for the CS framing of contradiction and well ordering.
  3. For pleasure and motivation, read Hardy §§12–14 and a couple of the prime proofs in Proofs from THE BOOK.
  4. To see where §5.2 is heading, skim Sipser §4.2 (halting) and CLRS §8.1 (sorting lower bound) — you are not expected to absorb every detail yet; just recognize the contradiction skeleton.
  5. Save Lakatos and the Bloch post for when you next have to disprove something — they will change how you test.