Proof: direct, contrapositive, contradiction and induction

前置知识

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.

通向

可选发现

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

学习路径

• Accelerated secondary progression
• Adult beginner pathway
• Undergraduate mathematics major
• Computer science and formal methods

延伸阅读

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