Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

Thanks in advance!

Printable View

- Jun 8th 2010, 03:09 PMmeggnogInduction and Well Ordering Principle
Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

Thanks in advance! - Jun 8th 2010, 04:02 PMtonio

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 - Jun 8th 2010, 04:32 PMwonderboy1953Question for Tonio
Does it work in reverse, namely that Complete Mathematical Induction implies the Well-Ordering Principle?

- Jun 8th 2010, 06:09 PMtonio

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