Principle of Induction and Principle of Well-Ordering

[ninjagod123]

Can anyone prove that the Principle of Induction is a consequence of the Principle of Well-Ordering?

How bout that the Principle of Well-Ordering is a consequence of the Principle of Induction?

 

[JSuarez]

Assuming that you are referring to finite induction (that is, applied to $$\mathbb N$$ and its subsets) and the strongest form of the induction principle for this case:

Given a nonempty set $$X\subseteq \mathbb N$$, then:

$$0 \in X \wedge \forall n \in \mathbb N\left(n \in X \rightarrow n+1 \in X\right)\rightarrow X=\mathbb N$$

Then, as the usual ordering relation in $$\mathbb N$$ is a well-order implies the induction principle for, suppose $$X\neq \emptyset$$, $$X \subset \mathbb N$$ (with strict inclusion), then its complement $$X' = \mathbb N / X$$ is also nonempty and, by the well-ordering principle, has a minimum element, say $$a \in X'$$. But $$a \neq 0$$, so $$a-1 \in X$$; but then, $$a=\left(a-1\right)+1 \in X$$, which is a contradiction. Therefore, $$X = \mathbb N$$.

As for the reciprocal, the exact statement is: if a totally ordered set satisfies the induction principle (finite or transfinite), then it must be well-ordered.
In the case of $$\mathbb N$$, it suffices to prove that the usual ordering is also a well-order. Let $$X \subseteq \mathbb N$$, $$X \neq \emptyset$$; then we have:

(1)$$0 \in X$$. Then we are done: 0 is the minimum element of X.

(2)Otherwise, as 0 belongs to the complement of X, applying the induction principle to it, then either $$X' = \mathbb N$$, which means that X is empty, or

$$\forall n \in \mathbb N\left(n \in X' \rightarrow n+1 \in X'\right)$$

is false. Therefore, there must be an $$n$$, such that $$n+1 \notin X'\Leftrightarrow n+1 \in X$$ and this implies that either that n+1 is the minimum element of X, or that we have to check, at most, a finite number of cases $$\left\{0,...,n+1\right\}$$ to find it.

These statements carry to the transfinite case (in fact, it can be proved that $$\mathbb N$$ is well-ordered without induction and a little set theory, as this set is the smallest transitive one), where the proofs are basically the same, but they require a knowledge of ordinals (the main difference is that there are two distinct types of infinite ordinals).