# Well-Ordering and Mathematical Induction

Here is my attempt to prove the Well-ordering principle, i.e. Any non-empty subset of $\Bbb N$, the set of natural numbers has a minimum element.

Proof: Suppose there exists a non-empty subset $S$ of $\Bbb N$ such that $S$ has NO minimum element. Define $A = \left\{n\in \Bbb N : (\forall s\in S)(n \leq s)\right\}$. It is obvious that $1\in A$. Suppose $n\in A$, then for each $s \in S$, there exists $q \in N$ such that $n + q = s$. Since $q \ge 1$, $n+1 \leq s$, for all $s\in S$. By Principle of mathematical induction, $A = \Bbb N$. Take any $s_0 ∈ S$, then $(\forall s\in S)(s_0 \leq s)$. (This contradicts that $S$ has no minimum element).

How do I prove the statement without invoking Mathematical Induction? Also, I read that the proof of Principle of Mathematical induction makes use of Well-ordering. Can it be proven independently of Well-ordering too?

Thank you.

-
A mistake in your reasoning is that when you say $n\in A$ you might have $n\in S$, in which case $q=0$. Regarding your second question, it all depends on what you take as your axioms. – Edvard Fagerholm Jun 29 '13 at 12:00

Induction implies well-ordering:

Suppose $S$ has no minimal element. Then $n = 1 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 2 \notin S$, because then $2$ would be minimal, since $n = 1$ is not in $S$. Suppose none of $1, 2, \cdots, n$ is in $S$. Then $n+1 \notin S$, because otherwise it would be minimal. Then by induction $S%$ is empty, a contradiction.

Well ordering implies induction:

Suppose $P(1)$ is true, and $P(n+1)$ is true whenever $P(n)$ is true. If $P(k)$ is not true for all integers, then let $S$ be the non-empty set of $k$ for which $P(k)$ is not true. By well-ordering $S$ has a least element, which cannot be $k = 1$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.

-

The principle of mathematical induction is equivalent to the priciniple of strong induction and both are equivalent to the well-ordering principle. At least if we assume the natural numbers are a structure which satisfies some basic axioms.

This means that if we assume one, we have the other. Of course if we assume a much stronger system of axioms, or have a much larger universe which can meaningfully make statements about the natural numbers, then we can prove each of them from those axioms, but their equivalence would remain.

Indeed this equivalence is one of the most fundamental things in modern mathematics: something is well-ordered if and only if we can perform an induction over it. This is why we often prove one from the other, and vice versa.

-