# Induction and Well Ordering Principle

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

• Jun 8th 2010, 04:02 PM
tonio
Quote:

Originally Posted by meggnog
Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

Suppose $P$ is a proposition appliable to the natural numbers, and suppose that:

(1) $P(n_1)$ is true for some $n_1\in\mathbb{N}$ ;

(2) It is true that $\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 $P(n)$ is true for all $n\in\mathbb{N}-\{1,2,\ldots,n_1-1\}$.

Now, let $K:=\{n\in\mathbb{N}\;/\;n>n_1\wedge P(n)\,\, \mbox{isn't true}\}$ . If $K\neq\emptyset$ then, by the WOP there exists a first (in the natural ordering of the naturals) $n_0\in K$ . Well, now

look at $P(n_1+1),\ldots,P(n_0-1)$ , apply (2) above and get a contradiction which shows that $K$ cannot be non-empty and we're done.

Tonio
• Jun 8th 2010, 04:32 PM
wonderboy1953
Question for Tonio
Does it work in reverse, namely that Complete Mathematical Induction implies the Well-Ordering Principle?
• Jun 8th 2010, 06:09 PM
tonio
Quote:

Originally Posted by wonderboy1953
Does it work in reverse, namely that Complete Mathematical Induction implies the Well-Ordering Principle?

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