(See also

StackExchange.) The proof is by strong induction. Let B be a nonempty subset of

and suppose B does not have the least element. Let

. We will show that

. Indeed,

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,

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

(see

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