[Math] Rudin, Real Analysis, 3ed - Problem 2.1.4

2: Chapter 2 - The Real Number System
1: Section 1 - Axioms for the Real Numbers
4: Problem 4 - Show that the well-ordering principle implies the principle of mathematical induction. [Consider the set { n is a natural number : P(n) is false }.]



Proof:

Consider the set S = { n is a natural number : P(n) is false }, where P(n) is the proposition for n. S is a subset of the natural numbers.

((思路，逆否命題，若 (n)P(n) 為否，是否可以推出 P(1) & (P(n) => P(n+1)) 也為否？~(P(1) & (P(n) => P(n+1) for all n)) <=> ~P(1) or ~(P(n) => P(n+1) for all n)，所以就是分別找出兩個否定的或))

If S is nonempty, then S has a smallest element M. If M = 1, P(1) is false. If M > 1, then by the definition P(M-1) is true. (otherwise M-1 is in S and M is not a smallest element of S.) So (P(M-1) => P(M)) is false. So ~((n)P(n)) => ~P(1) or ~(P(n) => P(n+1)). or P(1) & (P(n) => P(n+1)) => (n)P(n).



逆否命題。