# Induction and Well Ordering Principle

#### meggnog

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

#### tonio

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

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

meggnog

#### wonderboy1953

Question for Tonio

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