～～數學歸納法～～

可以從Well-Ordering Property (Axiom) 開始
Well-Ordering Property (Axiom):
If A is any nonempty subset of the set of positive integers, then among the elements of A there is a smallest one.
Theorem. (The Principle of Mathematical Induction)
Let M ⊆ N.
If (i) 1∈M
(ii) If k ∈M, then k +1∈M ,
then M = N.
Proof. Assume M ⊆ N, 1∈M and that if k ∈M, then k +1∈M .
By way of contradiction suppose that M ≠ N . Let us define the
following set,
S = N – M.
Since the set M is a proper subset of N, the set S is nonempty.
Since S is a subset of the N and nonempty, the Well-Ordering Axiom implies that there is a smallest integer x in S. By assumption 1∈M , which implies that 1/∈ S (/∈ means does not belongs to) . This in turn implies that the smallest integer x in S is greater that one, i.e. x > 1. Since x∈S , by definition of S, x/∈M . By the contrapositive of (ii), x/∈M implies that x -1∈M . By construction of S and x -1/∈M , we conclude that x -1∈S . But x – 1 is smaller than x, and thus we have contradicted that x is the smallest element of S. Hence, M = N.

2007-07-30 18:13:27 補充：
應是x/∈M implies that x -1/∈M因為否則的話由(ii)則知x -1∈M可以推到x∈M