# Thread: well-ordering <--> induction principle?

1. ## well-ordering <--> induction principle?

I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.

2. Originally Posted by eniuqvw
I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
If I understand your question correctly: you want to show (using the principle of mathematical induction) that every non-empty subset A of N has minimal element.
Suppose that A is a set not having the least element. Denote by B the complement of A.
Can you show (using induction) that every positive integer is in B? Clearly, B=N implies that A is empty.

3. Originally Posted by eniuqvw
I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
I think I know what you're getting at.

It appears that your question falls under order theory, and in particular, mathematical induction in its extended form requires a well-founded structure. Well-founded relations are more general than well-ordered ones, i.e., there exist well-founded relations that are not well-ordered.

4. Originally Posted by eniuqvw
I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
You're asking about the derivability relation between the well-ordering principle and the principle of mathematical induction?
They're interderivable (provably equivalent).

Proofs in both directions can be found on the Internet.
I think you'll see that, typically, both derivations are indirect (specifically, by RAA).

5. Kompik gave almost what you want.

What you need to do is first prove the "strong principal of induction":

If X is a set of positive integers containing 1 and such that if, for some k, all $i\le k$ are in X, then X is the set of all positive integers. That can be proved from the usual induction principal.