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"?
First, state the principle of transfinite induction in the case that $X = \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.