Metadata Card

• Prerequisites: Chapter 1 — Logic, Chapter 2 — Set Theory
• Estimated time: 50 minutes
• Core difficulty: Intermediate
• Completion marker: Able to distinguish four proof methods, construct counterexamples or inductive proofs for simple scenarios

Your Progress

Now you have two tools: logic and sets. The Librarian points to several theorems on the wall of the third floor: "These are all true — but how do you know they're always true?"

Your Task

You wrote a sorting algorithm and tested it a thousand times — it passes every time. Can you claim it is "always correct"? No — testing can only prove the presence of bugs, not their absence. Proof is the only reliable path to program correctness. This chapter aims to equip you with several general proof strategies, taking you from "I think it's right" to "I know it must hold."

Chapter Layers

• Required reading: Direct proof, proof by contradiction, mathematical induction
• Optional reading: Constructive vs. non-constructive proofs

Breakthrough · Origin Story

During a code review, a colleague writes an optimization: "This block can never be affected by a null pointer exception because it was already checked earlier." How do you determine whether his "can never" is true? Instinctively, you perform a mental logical deduction. What's needed here is exactly a formal proof approach — not intuition, but a chain of reasoning.

The core structure of a proof is: known true premises → logical reasoning → conclusion. This chapter doesn't involve proving deep theorems, but covers four fundamental paradigms.

1. Direct Proof

Starting from premises, go through a series of logical steps to reach the conclusion.

Theorem: If n is even, then n² is also even.

Proof: n is even, so n = 2k (k is an integer). n² = (2k)² = 4k² = 2(2k²). Therefore n² is even.

This is the simplest and most direct form of proof. You start from the premise that n is even, use the definition of even numbers (there exists integer k such that n = 2k), do algebra, and reach the conclusion.

2. Proof by Contradiction (Reductio ad Absurdum)

Assume the conclusion is false, then derive a contradiction with the known premises. The proof forces you to abandon the "conclusion is false" assumption.

Theorem: √2 is irrational.

The proof is a classic contradiction. Assume √2 is rational, i.e., √2 = p/q (where p, q are coprime integers). Square both sides to get 2 = p²/q², i.e., p² = 2q². So p² is even, meaning p is even. Let p = 2k. Substituting gives (2k)² = 2q², i.e., 4k² = 2q², so q² = 2k², and q is even. Both p and q are even, contradicting that p/q is in lowest terms (coprime). The assumption is false, and √2 is irrational.

Proof by contradiction is very useful in algorithm analysis — for example, proving "no comparison-based sorting algorithm can outperform O(n log n)" starts by assuming a better one exists and deriving a contradiction.

3. Counterexample

To prove a proposition false — just one counterexample suffices.

Proposition: "All prime numbers are odd." Counterexample: 2 is prime, but 2 is even. The proposition is false.

Constructing counterexamples is the most familiar form of "proof" for programmers — it's exactly what you do when finding bugs.

4. Mathematical Induction

Prove that a proposition about natural numbers holds for all n. Two steps:

1. Base case: Prove P(0) or P(1) holds.
2. Inductive step: Assume P(k) holds, prove P(k+1) holds.

This is the formal proof counterpart of recursive structures. If your code uses recursion, mathematical induction is the natural tool to prove its correctness.

Example: Prove 1 + 2 + ... + n = n(n+1)/2.

Base: n=1, left side = 1, right side = 1(2)/2 = 1. Holds. Inductive: Assume 1+...+k = k(k+1)/2. Then 1+...+k+(k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2(k+1))/2 = (k+1)(k+2)/2. Holds.

Induction works almost exactly like debugging a recursive function: first confirm the base case is correct, then assume the recursive call is correct (inductive hypothesis), and finally verify that the current layer combines correctly.

Common Pitfalls

• Forgetting to prove the base case in induction. Even if the inductive step is perfectly sound, if the base case doesn't hold, the entire proof collapses.
• Contradiction in proof by contradiction isn't a real contradiction. "This doesn't make sense" is not a mathematical contradiction — it must directly conflict with known premises or axioms.
• Circular reasoning: Using the conclusion to prove the conclusion. For example, "This number is divisible by 3 because it is a multiple of 3" — what you were supposed to prove is exactly that "it is a multiple of 3."

Challenge Questions

• Prove by direct proof: If m and n are even, then m + n is even.
• Prove by contradiction: There is no largest integer.
• Prove by induction: The sum of the first n odd numbers is n².

Traveler's Notes

Proof is the bridge from "I think it's right" to "I know it must hold." Four methods — direct, contradiction, counterexample, induction — cover 90% of proof scenarios in computer science.

→ Next stop: Proof gives you the framework for reasoning. But many program structures are recursive — functions calling themselves, data referencing itself. The next chapter clarifies this "self-referential" structure.