9.º a 12.º gradoFoundationsPlanificado
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
La lección de este tema todavía no se ha escrito. El esquema siguiente forma parte del mapa del plan de estudios y no ha sido revisado.
Se basa en
Requisitos previos obligatorios, hasta el fondo: 9
Aprenderás a
- 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.
Definición
- 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.
Teorema
- 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).
Errores frecuentes
- 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.
Conduce a
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
Descubrimientos opcionales
- 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.
Itinerarios de aprendizaje
Lecturas complementarias
- Daniel J. Velleman, How to Prove It: A Structured Approach (1994)
- Richard Hammack, Book of Proof
- George Pólya, How to Solve It (1945)