The proof establishes a bi-implication by showing each principle implies the other. The key technique in both directions is proof by contradiction: we assume one principle holds and the other fails, then derive a contradiction using an auxiliary property $Q(n) = \neg P(n)$.

**Step 1 (WOP implies Strong Induction).** Assume the well-ordering principle holds, and suppose conditions (i) and (ii) of strong induction are satisfied for some property $P$. We claim $P(n)$ holds for all $n \in \mathbb{N}$.

[claim:WOP Gives SPI] Under the assumptions (i) and (ii) of strong induction and the well-ordering principle, $P(n)$ holds for all $n \in \mathbb{N}$. [/claim]

[proof] Suppose, for contradiction, that $P(n)$ fails for some $n \in \mathbb{N}$. Then the set $C = \{n \in \mathbb{N} : P(n) \text{ is false}\}$ is non-empty. By the well-ordering principle, $C$ has a least element $m$. By minimality of $m$, we have $P(k)$ holds for all $k < m$. In particular, $P(k)$ holds for all $k \le m - 1$ (if $m = 1$, the condition is vacuous and hypothesis (i) gives $P(1)$ directly). By hypothesis (ii), $P(m)$ holds. This contradicts $m \in C$. [/proof]

**Step 2 (Strong Induction implies WOP).** Assume strong induction holds. Let $S \subseteq \mathbb{N}$ be non-empty. We claim $S$ has a least element.

[claim:SPI Gives WOP] Under the assumption of strong induction, every non-empty subset of $\mathbb{N}$ has a least element. [/claim]

[proof] Suppose, for contradiction, that $S$ has no least element. Define $Q(n)$ to be the property "$n \notin S$." We verify the hypotheses of strong induction for $Q$.

*Base case:* $Q(1)$ holds, because if $1 \in S$, then $1$ would be the least element of $S$ (since $1 \le n$ for all $n \in \mathbb{N}$), contradicting our assumption.

*Inductive step:* Suppose $Q(k)$ holds for all $k \le n$, meaning no element of $\{1, 2, \ldots, n\}$ belongs to $S$. If $n + 1 \in S$, then $n + 1$ would be the least element of $S$ (since every smaller natural number is not in $S$), contradicting our assumption. Hence $Q(n+1)$ holds.

By strong induction, $Q(n)$ holds for all $n \in \mathbb{N}$, so $S = \varnothing$. This contradicts the hypothesis that $S$ is non-empty. [/proof]

**Step 3 (Conclusion).** Steps 1 and 2 together establish that the well-ordering principle and the principle of strong induction are equivalent.