Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.
Thanks in advance!
Suppose $\displaystyle P$ is a proposition appliable to the natural numbers, and suppose that:
(1) $\displaystyle P(n_1)$ is true for some $\displaystyle n_1\in\mathbb{N}$ ;
(2) It is true that $\displaystyle \forall\,k>n_1\,,\,P(n_1)\wedge P(n_1+2)\wedge\ldots\wedge P(k)\Longrightarrow P(k+1)$
Then we must prove that $\displaystyle P(n)$ is true for all $\displaystyle n\in\mathbb{N}-\{1,2,\ldots,n_1-1\}$.
Now, let $\displaystyle K:=\{n\in\mathbb{N}\;/\;n>n_1\wedge P(n)\,\, \mbox{isn't true}\}$ . If $\displaystyle K\neq\emptyset$ then, by the WOP there exists a first (in the natural ordering of the naturals) $\displaystyle n_0\in K$ . Well, now
look at $\displaystyle P(n_1+1),\ldots,P(n_0-1)$ , apply (2) above and get a contradiction which shows that $\displaystyle K$ cannot be non-empty and we're done.
Tonio
Yes, and it's not hard to prove.Try it, and then you can check here http://www.math.wustl.edu/~chi/310notesIV.pdf
Tonio