well ordering principle

This is what I read somewhere

"well-ordering principle for natural numbers is equivalent to the principle of mathematical induction"

Now using well-ordering principle (that every non empty subset of natural numbers has a minimum) I could prove mathematical induction (if P(1) is true and P(n) => P(n+1) then P(i) is true for all i in N)

This is rather trivial.


But using mathematical induction I could not derive well-ordering principle. So is 'well-ordering principle' more powerful assertion than induction? Or, there is a nice way to prove it.

Any help plz?

Hi

Take a subset of We want to show that if it does not have a minimum, then it is empty.

If 1 belongs to it has a minimum.

If 1 does not belong to 1 satisfies the property . And...

Quote:

---

Originally Posted by clic-clac

Hi

Take a subset of We want to show that if it does not have a minimum, then it is empty.

If 1 belongs to it has a minimum.

If 1 does not belong to 1 satisfies the property . And...

---

Thanks. Too stupid of me, this was actually not tough.


So let X be subset that has no minimum. i.e. for every n in X there exists m, where m < n and m i also in X

We need to prove X is empty

Let P(k) be true if for all i <= k; i doesn't belong to X

P(1) is obviously true

Assume P(n) is true
Then P(n+1) will be true as other wise this will imply that (n+1) is in X and by the way we define X it means there exists some i<(n+1) which is in X thus voilating assumption about P(n)

Hence P(n+1) is true

Thus by principle of induction P(n) is true for all n thus X is empty
Hence well ordering principle is proved.

I hope this proof is pretty rigorous. If you think there is any flaw please do high-light

Thanks

On Meggnog's posting of 6/8/2010 (Induction and Well Ordering Principle), we discussed this very question (with an answer) which you should check out further.