Ruka hadi maudhui
The Lumenary
Darasa la 9–12FoundationsSomo linapatikana

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

Fungua somo Onyesha kila kinachohitajika kufikia mada hii

Inajengwa juu ya

Propositional logic and truth tablesIntegers

Masharti ya awali ya lazima 9 (hadi chini kabisa)

Utajifunza

  • 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.

Fasili

  • 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.

Nadharia

  • 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).

Mawazo potofu ya kawaida

  • 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.

Inaelekea kwa

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 ringsSurfaces, polyhedra and the Euler characteristicMathematical writingReal analysisThe λ-calculus

Ugunduzi wa hiari

  • 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.

Njia za kujifunza

Usomaji zaidi

  • Daniel J. Velleman, How to Prove It: A Structured Approach (1994)
  • Richard Hammack, Book of Proof
  • George Pólya, How to Solve It (1945)