Equivalence between "mathematical induction" and "transfinite induction" for natural numbers? The "principle of mathematical induction" says that for a subset $S$ of $\omega$ (where $\omega$ is the set of all natural numbers), if $0 \in S$ and $n \in S \implies n^+ \in S$, then $S = \omega$.
The "principle of transfinite induction" says that if $X$ is a well-ordered set, $S \subset X$, and $s(x) \subset S \implies x \in S$ (where $s(x)$ is the set of all predecessors of $x$ in $X$), then $S = X$.
Page 67 of Naive Set Theory (Halmos) says that "[the principle of transfinite induction] when applied to $\omega$ is easily proved to be equivalent to the principle of mathematical induction".
However, I had trouble proving this (possibly because I had trouble formulating this "equivalence" precisely).

How can I formulate and prove the statement that "the principle of transfinite induction, when applied to the natural numbers, is equivalent to the principle of mathematical induction"?

 A: First, state the principle of transfinite induction in the case that $X = \mathbb{N}$.

If $\mathbb{N}$ is a well-ordered set, $S \subset \mathbb{N}$, and $s(x) \subset S \implies x \in S$ (where $s(x)$ is the set of natural numbers less than $x$), then $S = \mathbb{N}$.

To show this is equivalent to standard induction, you need to show the conditions are the same.   I.e., you need to show that the following are equivalent:


*

*For all $x \in \mathbb{N}$, if $x \in S$, then $x^+ \in S$.

*For all $x \in \mathbb{N}$, if $s(x) \subset S$, then $x \in S$.
$1 \implies 2$ is straightforward.  For $2 \implies 1$, prove the contrapositive, and use the fact that $\mathbb{N}$ is well-ordered to find a minimum counterexample.
I am a little skeptical of this, however, because to prove two forms of induction are the same you would want to be working in a world where neither of them need be true.  That is, you can't use any form of induction in your proof.  I do not know how one proves the natural numbers are well-ordered but I would certainly think it uses induction.  And I wonder if one can even construct the natural numbers without some sort of induction.  I am no expert in set theory, so I don't know how to resolve this issue, but there is certainly something fishy going on.
