Grades 9–12FoundationsPlanned
Proof: direct, contrapositive, contradiction and induction
How mathematicians establish general truths: direct proof, proof by cases, contrapositive, contradiction and mathematical induction, with attention to clear writing and hidden assumptions.
math.found.proof-techniques
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Required prerequisites, all the way down: 9
You will learn to
- Write direct and contrapositive proofs about integers, such as 'if n² is even then n is even'.
- Prove a statement by contradiction, for example that there are infinitely many primes.
- Prove statements about all natural numbers by ordinary and by strong induction.
- Find gaps, circular reasoning and unstated assumptions in a proposed proof.
Definition
- A proof is a finite chain of justified steps leading from accepted assumptions to a conclusion.
- Induction: if P(0) holds and P(n) implies P(n + 1) for every n, then P(n) holds for every natural number n.
- Strong induction: if, for every n, P(k) for all k < n implies P(n), then P(n) holds for every n.
Theorem
- Ordinary induction, strong induction and the well-ordering principle for ℕ are interderivable (given the basic properties of ℕ).
- 1 + 2 + ⋯ + n = n(n + 1)/2 for every natural number n.
- There are infinitely many prime numbers (Euclid).
Common misconceptions
- Proving the converse instead of the statement asked for.
- Checking the inductive step but forgetting the base case.
- Assuming what is to be proved.
- Reaching a contradiction from an extra, unjustified assumption and blaming the hypothesis.
Leads to
Countability and Cantor's diagonal argumentRussell's paradox and why sets need axiomsReal numbers and irrationalityDivisibility, Euclid's algorithm and unique factorisationEuclidean geometry and proofSequences and seriesCombinatoricsGraphsAlgorithms, correctness and efficiencyFirst steps in LeanOrders, lattices and well-ordersAlgebraic structures: monoids, groups and ringsMathematical writingReal analysisThe λ-calculus
Optional discoveries
- Formalising mathematics in Lean and Mathlib A proof assistant such as Lean checks every step of a proof mechanically, including the base case and inductive step.
- Proof theory Proofs can themselves be studied as mathematical objects; Gentzen's cut-elimination theorem is a central example.
Learning pathways
Further reading
- Daniel J. Velleman, How to Prove It: A Structured Approach (1994)
- Richard Hammack, Book of Proof
- George Pólya, How to Solve It (1945)