How do you prove Well-Ordering without Mathematical Induction? (and vice-versa)

In a version of the natural numbers $\mathbb{N}$ where each number besides zero has a (unique) predecessor, such as the von Neumann ordinals, or any other model of the Peano Axioms (including the induction axiom), we have the following:

Induction implies well-ordering:

Suppose $S$ has no minimal element. Then $ n = 0 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 1 \notin S$, because then $1$ would be minimal, since $n = 0$ is not in $S$. Suppose none of $0, 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(0)$ 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 = 0$. 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.

Well ordering principle is equivalent to PMI.

We shall first prove that PMI $\implies$ WOP using strong induction. $P(n)$ Every subset of $\mathbb{N}$ containing n has a least element

Base: $1$ is certainly the least element of any subset of N containing $1$. Thus P(1) is true.

Induction: Consider any set S containing $k + 1$.

If S contains any element, say m, smaller than $k + 1$, then by strong induction, as $P(m)$ is true, we know that S contains a least element.

If S didn’t contain any element smaller than $k + 1$, then S contains a smallest element, namely $k + 1$. Thus $P(k + 1)$ is true. We shall now show the reverse direction namely WOP$\implies$PMI.

For contradiction, let us assume that there is a property P such that

$P(1)$ is true and whenever $P(k)$ is true, $P(k + 1)$ is also true.

There exists a number m such that $P(m)$ is false.

Let $S=\left \{x\in \mathbb{N}|P(x)\text{ is false} \right \}$.

Since $m\in S$, S is a non empty subset of N and thus has a least element say s.

$s\neq 1$ because $P(1)$ is true. Since s is the least element of S, $s − 1 \notin S$ .

∴ $P(s−1)$ is true. But then $P((s −1)+1)$ must also be true and thus $s \notin S$