# Proving PMI with WOP

How in the world can one prove something as great as the principle of mathematical induction with the well ordering principle?

-

Suppose that both

$$P(1)\,\,\,\wedge\,\,\,\left(\,P(n)\longrightarrow P(n+1)\,\right)$$

are true. Let $\,K\subset\Bbb N\,$ the set of all natural numbers for which $\,P(k)\,$ is true.

Let $\,C=\Bbb N-K\,$ . If $\,C\neq \emptyset\,$ then the WOP tells us it has a first element (in the natural, usual order), say $\,c\,$ . By assumption, $\,c>1\,$ (why?), so we can say that

$$c-1\in\Bbb N-C=K\Longrightarrow P(c-1)\,\,\,\text{is true, so also }\,\,\,P(c-1+1)=P(c)\,\,\,\text{is true}$$

But this contradicts $\,c\notin K\,$ !

-