29-05 — Reading and Writing Proofs

Phase: 29 — Proof Techniques Subject: 29-05 Prerequisites: 29-01 through 29-04 (all proof techniques) Next subject: This is the final proof techniques subject. You have completed Phase 29. The full curriculum now spans 30 phases (00–29) with 298 subjects.

Learning Objectives

By the end of this subject, you will be able to:

1. Read and understand complete mathematical proofs at the undergraduate level
2. Structure your own proofs with clear hypotheses, logical flow, and conclusions
3. Choose the appropriate proof technique for a given statement
4. Identify common proof errors (circular reasoning, gaps, false dichotomies)
5. Write proofs that are rigorous, concise, and accessible

Core Content

1. Anatomy of a Proof

Every complete proof has:

1. Statement of theorem/proposition: What is being proven
2. Given/Assume: The hypotheses (conditions on the variables)
3. To prove: The conclusion (what follows from the hypotheses)
4. Proof: The logical argument
5. QED / ∎: The closure symbol

Example structure:

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

Proof: Let n be an arbitrary even integer. By definition, n = 2k for some integer k.
Then n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is even. ∎

2. Proof Writing Style

Good proof style: - Clear: Each step follows logically from previous steps or known theorems - Concise: No unnecessary words, but enough to make each step clear - Complete: No gaps — every claim is justified - Readable: Use standard notation and structure

Common style mistakes: - "Obviously..." or "It's clear that..." without justification - Skipping steps that require justification - Using the statement being proven as a justification (circular reasoning) - Mixing notation styles

3. Choosing the Right Technique

4. Common Proof Errors

Circular reasoning: Using the statement being proven as a justification. - Bad: "$n^2$ is even because $n$ is even, and $n$ is even because $n^2$ is even."

Gap: Skipping a step that isn't obviously true. - Bad: "Since $a^2 = 2b^2$, $a$ is even." (Missing: if $a^2$ is even then $a$ is even — needs proof)

False dichotomy: Assuming only two possibilities when more exist. - Bad: "Either $x$ is positive or negative" (ignoring $x = 0$)

Over-generalisation: Proving a specific case and claiming it holds generally. - Bad: Testing $n = 2, 3, 4$ and claiming "the pattern holds for all $n$"

Assuming what you prove: Using the conclusion in the proof. - Bad: To prove $a = b$, starting with "since $a = b$..."

5. Reading Proofs Critically

When reading a proof: 1. Identify the theorem statement and hypotheses 2. Check each step: does it follow from previous steps or known results? 3. Check the base cases (for induction) 4. Check the inductive step: does it actually use the hypothesis? 5. Look for hidden assumptions or gaps 6. Try to reconstruct the proof from scratch to check understanding

Worked Examples

Example 1: Reading and Evaluating a Proof

Theorem: The sum of two odd integers is even.

Student proof: "Let $m = 2k + 1$ and $n = 2j + 1$. Then $m + n = 2k + 2j + 2 = 2(k + j + 1)$. This is even because it's 2 times an integer."

Evaluation: ✓ Correct. Direct proof. Assumes both are odd, uses definition of odd, computes sum, recognises the form $2 \cdot \text{(integer)}$. Complete and clear.

Example 2: Identifying and Fixing a Gap

Gap claim: "If $n^2$ is even, then $n$ is even, because $n^2 = n \cdot n$ and even times anything is even."

Problem: The claim "even times anything is even" is used without proof. Also, the argument proves the CONVERSE (if $n$ is even then $n^2$ is even), not the stated direction.

Fix (contrapositive): Prove "if $n$ is odd, then $n^2$ is odd." If $n = 2k+1$: $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd.

Example 3: Choosing the Right Technique

Statement: There are infinitely many primes.

Why contradiction? A direct proof would require constructing infinitely many primes, which is possible (Euclid's construction) but the standard elegant proof uses contradiction: assume finitely many, construct $N = p_1...p_n + 1$, show it has a prime factor not in the list.

Statement: $\sqrt{2}$ is irrational.

Why contradiction? Proving irrationality directly means proving "for all rational representations $a/b$, $a/b \neq \sqrt{2}$" — hard to do directly. Contradiction: assume $\sqrt{2} = a/b$ and derive that both are even (contradicting lowest terms).

Statement: The sum of two even numbers is even.

Why direct? Assume $m = 2k, n = 2j$. Then $m + n = 2(k+j)$, clearly even. Direct proof is one line.

Practice Problems

Problem 1: Read the following "proof" and identify the error:

"Claim: All horses are the same color. Proof: By induction on $n$ (number of horses). Base: $n = 1$, trivially true. Inductive step: Assume any set of $k$ horses are the same color. Consider $k+1$ horses. Remove one — the remaining $k$ are the same color (by IH). Remove a different one — the remaining $k$ are the same color. Therefore all $k+1$ are the same color. ∎"

Problem 2: Prove that if $a^2$ is divisible by 3, then $a$ is divisible by 3. Choose the most appropriate technique and write a complete proof.

Problem 3: Evaluate this proof for clarity and completeness: "Claim: $\sqrt{6}$ is irrational. Proof: Assume $\sqrt{6} = a/b$. Then $6 = a^2/b^2$, so $a^2 = 6b^2$. So $a$ is even. Let $a = 2k$. Then $4k^2 = 6b^2$, so $b^2 = 2k^2/3$. Since $b^2$ must be an integer, $k$ is divisible by 3. Let $k = 3j$. Then $a = 6j$ and $b^2 = 6j^2$, so $b$ is even. Both $a$ and $b$ are even, contradiction. ∎"

Problem 4: Prove that between any two real numbers there is a rational number. Choose your technique.

Problem 5: Write a complete proof of the statement: "For all integers $n$, $n^3 - n$ is divisible by 6."

Summary

1. Proof anatomy: Statement → Hypotheses → Proof → QED. Every part is necessary.
2. Good style: Clear, concise, complete, readable. No "obviously" without justification.
3. Technique selection: Match the statement form to the proof technique (direct, contrapositive, contradiction, induction, cases, pigeonhole)
4. Common errors: Circular reasoning, gaps, false dichotomies, over-generalisation, hidden assumptions
5. Critical reading: Check each step, verify base cases, look for hidden assumptions

Key Terms

• Circular reasoning
• Complete proof
• Gap in proof
• Proof style
• QED
• Rigorous proof
• Theorem statement

Pitfalls

Quiz

1. Skipping 'trivial' steps. Every step needs justification, even 'obvious' ones. The reader may not find them obvious, and gaps make proofs hard to verify.
2. Using undefined terms. Before proving 'f is continuous', make sure you've stated the definition of continuity you're using (ε-δ, sequential, etc.).
3. Mixing proof styles. Don't start with a direct proof, switch to contradiction mid-way, and end with contrapositive. Pick one style and stick with it.
4. Ignoring quantifier order. 'For all x there exists y' (∀x∃y) is not the same as 'There exists y such that for all x' (∃y∀x). This is a classic reading error.
5. Writing proofs backward. Start with what you know (hypotheses, definitions, prior results), not with what you want to prove. Forward reasoning is clearer.
6. Leaving key steps as 'it follows that'. Vague transitions hide logic errors. Be explicit: 'By definition of X, we have ...', 'Applying theorem Y to ...'.
7. Not reading the theorem statement carefully. Prove exactly what's asked. 'If P then Q' is different from 'P if and only if Q', and different from 'There exists P such that Q'.

Q1: A complete proof must include:

A) Only the final answer B) Statement, hypotheses, logical argument, and conclusion C) At least 10 steps D) A contradiction

Correct: B)

• If you chose B: Correct. A complete proof has: what you're proving, what you assume, the argument, and how you conclude.
• If you chose A: Just the answer is not a proof. You need to show WHY it's true.
• If you chose C: Length doesn't determine completeness. Some proofs are one line.
• If you chose D: Contradiction is one technique among many. Not all proofs use it.

Q2: "Obviously, $x^2 \geq 0$ for all real $x$" is acceptable in a proof because:

A) It's actually obvious and needs no justification B) It should still be justified (e.g., "since $x^2 = x \cdot x$ and the product of two numbers with the same sign is non-negative") C) It's never acceptable in a proof D) Only if the reader agrees

Correct: B)

• If you chose B: Correct. Even "obvious" statements should be briefly justified in rigorous proofs. The justification makes the proof self-contained.
• If you chose A: "Obviously" is a red flag in proof writing. What's obvious to one reader may not be to another.
• If you chose C: That's too strict. Some facts are standard enough to cite without full proof (e.g., "by the distributive law").
• If you chose D: Proofs must stand on their own, not on the reader's agreement.

Q3: Circular reasoning occurs when:

A) The proof goes in a circle (starts and ends at the same point) B) The statement being proven is used as a justification in the proof C) The proof has too many cases D) The proof uses induction

Correct: B)

• If you chose B: Correct. Circular reasoning: using the conclusion (or something equivalent to it) as a premise in the proof.
• If you chose A: A circular argument isn't literally circular — it's one that sneakily assumes the conclusion.
• If you chose C: Having many cases doesn't make it circular.
• If you chose D: Induction is a valid technique, not a logical error.

Q4: To prove "for all $n$, if $n^2$ is even then $n$ is even," the most natural technique is:

A) Direct proof B) Proof by contrapositive ("if $n$ is odd, then $n^2$ is odd") C) Proof by contradiction D) Pigeonhole principle

Correct: B)

• If you chose B: Correct. The contrapositive "if $n$ is odd then $n^2$ is odd" is easier to prove directly (substitute $n = 2k+1$).
• If you chose A: Direct proof of this statement is trickier — you'd need to prove "if $n^2$ is even, $n$ is even" without assuming $n$ is odd.
• If you chose C: Contradiction works (assume $n^2$ even and $n$ odd, derive $n$ even from $n^2$ even), but contrapositive is cleaner.
• If you chose D: Pigeonhole is for counting/existence, not implication statements.

Q5: A "gap" in a proof is:

A) A missing step that isn't justified B) A contradiction C) An extra case D) A well-written proof

Correct: A)

• If you chose A: Correct. A gap is when the proof jumps from one claim to another without showing the logical connection.
• If you chose B: A contradiction is a deliberate proof technique, not a gap.
• If you chose C: Extra cases don't create gaps — they just make the proof longer.
• If you chose D: A well-written proof has no gaps.

Q6: When reading a proof by induction, you should check:

A) Only the base case B) Only the inductive step C) Both the base case and that the inductive step actually uses the hypothesis D) The colour of the text

Correct: C)

• If you chose C: Correct. Common induction errors: wrong base case, inductive step that doesn't use the hypothesis (proving $P(k+1)$ independently of $P(k)$), or incorrect use of the hypothesis.
• If you chose A: The base case is necessary but not sufficient. A wrong inductive step invalidates the proof.
• If you chose B: The inductive step is essential but doesn't help if the base case is wrong.
• If you chose D: Style matters, but colour is irrelevant to correctness.

Q7: Which proof technique is best suited for "There exists a prime greater than $n$"?

A) Direct construction (exhibit the prime) B) Proof by contradiction C) Pigeonhole principle D) Induction

Correct: A)

• If you chose A: Correct. Euclid's proof CONSTRUCTS $N = p_1...p_n + 1$ and shows it has a prime factor $> n$. This is constructive existence.
• If you chose B: Contradiction also works (assume finitely many, construct $N$), but the construction is the key insight.
• If you chose C: Pigeonhole doesn't apply to existence of primes.
• If you chose D: Induction proves "for all $n$" statements, but the constructive proof is more direct here.

Q8: Over-generalisation in proofs means:

A) Making the proof too long B) Proving a specific case and claiming it holds for all cases without justification C) Using too many cases D) Writing proofs that are too general

Correct: B)

• If you chose B: Correct. Testing $n = 1, 2, 3$ and concluding "the pattern holds for all $n$" is over-generalisation. One counterexample refutes a universal claim.
• If you chose A: Length isn't over-generalisation. Verbose proofs are just long.
• If you chose C: Many cases don't imply over-generalisation. Exhaustive case analysis is a valid technique.
• If you chose D: Being too general is the opposite of over-generalisation. Over-generalisation is claiming too much from too little evidence.

Next Steps

Congratulations! You have completed Phase 29 — Proof Techniques. You now have a complete toolkit of proof methods: direct proof, contrapositive, contradiction, induction (standard, strong, structural), case analysis, pigeonhole principle, and the extremal principle.

You also now have the skills to read proofs critically and write proofs rigorously — these meta-skills are essential for all advanced mathematics.

The full LLM Researcher Mathematics Curriculum now spans 30 phases (00–29) with 298 subjects (241 original + 6 Phase 00 + 3 Phase 15 + 29 new domain subjects + 19 proof/crypto/ODE subjects), covering Year 8 arithmetic through to cryptography, combinatorics, differential equations, and proof techniques at the early university level.

What's next? This curriculum provides the mathematical foundation. The next step is application: implement algorithms, read research papers, and use these proof techniques in your own mathematical work.