الصفوف 9–12Foundationsمُخطَّط له
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
لم يُكتب درس هذا الموضوع بعد. المخطط أدناه جزء من خريطة المنهج ولم تجرِ مراجعته.
يعتمد على
عدد المتطلبات السابقة الإلزامية (حتى الأساس): 9
ستتعلّم
- 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.
تعريف
- 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.
مبرهنة
- 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).
مفاهيم خاطئة شائعة
- 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.
يقود إلى
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
اكتشافات اختيارية
- 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.
مسارات التعلّم
قراءات إضافية
- Daniel J. Velleman, How to Prove It: A Structured Approach (1994)
- Richard Hammack, Book of Proof
- George Pólya, How to Solve It (1945)