Equivalence between "mathematical induction" and "transfinite induction" for natural numbers?

Question

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"?

Answer 1

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:

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

2. 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.