(See also

StackExchange.) The proof is by strong induction. Let B be a nonempty subset of $\displaystyle \mathbb{Z}^+$ and suppose B does not have the least element. Let $\displaystyle J=\mathbb{Z}^+\setminus B$. We will show that $\displaystyle J=\mathbb{Z}^+$. Indeed, $\displaystyle 1\in J$ because otherwise 1 would be the least element of B. Next, assume 1, ..., n ∈ J. If n+1 ∈ B, then n+1 is the least element of B (since 1, ..., n ∉ B), so n+1 ∈ J. Thus, $\displaystyle J=\mathbb{Z}^+$ and B is empty, a contradiction.

One can notice that the proof is by contradiction and we consider the complement of B. It can be shown that the contrapositive of strong induction for a predicate P is the well-ordering principle for the the set $\displaystyle \{n\in\mathbb{Z}^+\mid\neg P(n)\}$ (see

this post). Thus, strong induction and well-ordering principle are equivalent. Strong induction, in turn, can be proved from regular induction.