Induction and Well Ordering Principle

Feb 2010
30
0
Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

Thanks in advance!
 
Oct 2009
4,261
1,836
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
 
  • Like
Reactions: meggnog
Oct 2009
769
87
Question for Tonio

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