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?
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.
Originally Posted by clic-clac
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
History repeats itself
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.