[proofplan] We prove the equivalence by proving both implications separately. First, assuming the [well-ordering principle](/theorems/721), we show that any failure of [strong induction](/theorems/720) would produce a non-empty set of counterexamples with a least counterexample, contradicting the inductive hypothesis before it. Second, assuming the principle of strong induction, we show that a non-empty subset of $\mathbb{N}$ without a least element forces every natural number to lie outside the subset, contradicting non-emptiness. [/proofplan] [step:Derive strong induction from the least counterexample principle] Assume that every non-empty subset of $\mathbb{N}$ has a least element. Let $P$ be a property of natural numbers satisfying the hypotheses of the principle of strong induction: $P(1)$ holds, and for every $n \in \mathbb{N}$, if $P(k)$ holds for every $k \in \mathbb{N}$ with $k \le n$, then $P(n+1)$ holds. Define the counterexample [set](/pages/1142) $C \subseteq \mathbb{N}$ by \begin{align*} C := \{n \in \mathbb{N} : P(n) \text{ is false}\}. \end{align*} Suppose, for contradiction, that $C$ is non-empty. Since $C$ is a non-empty subset of $\mathbb{N}$, the well-ordering principle gives a least element $m \in C$. If $m = 1$, then $P(1)$ holds by the base hypothesis, contradicting $1 \in C$. Hence $m > 1$, so there exists $n \in \mathbb{N}$ with $m = n+1$. By minimality of $m$, no $k \in \mathbb{N}$ with $k < m$ lies in $C$, so $P(k)$ holds for every $k \le n$. The inductive hypothesis applied to this $n$ gives $P(n+1)$, hence $P(m)$, contradicting $m \in C$. Therefore $C = \varnothing$, so $P(n)$ holds for every $n \in \mathbb{N}$. This is the principle of strong induction. [guided] Assume that every non-empty subset of $\mathbb{N}$ has a least element. To prove the principle of strong induction, let $P$ be a property of natural numbers satisfying its two hypotheses: $P(1)$ holds, and whenever $n \in \mathbb{N}$ satisfies that $P(k)$ holds for every $k \le n$, then $P(n+1)$ holds. The natural contradiction strategy is to collect all possible failures of $P$. Define the set $C \subseteq \mathbb{N}$ by \begin{align*} C := \{n \in \mathbb{N} : P(n) \text{ is false}\}. \end{align*} If $C$ were non-empty, then the well-ordering principle would apply because $C$ is a non-empty subset of $\mathbb{N}$. Thus there would be a least element $m \in C$. We now use the fact that $m$ is the first possible failure. If $m = 1$, then $P(1)$ holds by the base hypothesis of strong induction, while $1 \in C$ says $P(1)$ is false. This contradiction rules out $m = 1$. Therefore $m > 1$. Since the natural numbers start at $1$, there exists $n \in \mathbb{N}$ such that $m = n+1$. By minimality of $m$, no smaller natural number belongs to $C$. Equivalently, $P(k)$ holds for every $k \in \mathbb{N}$ with $k < m$, and since $m = n+1$, this says $P(k)$ holds for every $k \le n$. The inductive step hypothesis therefore applies to this $n$ and gives $P(n+1)$. Since $m = n+1$, this gives $P(m)$, contradicting $m \in C$. The assumption that $C$ is non-empty is impossible. Hence $C = \varnothing$, meaning there is no natural number for which $P$ fails. Therefore $P(n)$ holds for every $n \in \mathbb{N}$, which is exactly strong induction. [/guided] [/step] [step:Derive the well-ordering principle from strong induction] Assume the principle of strong induction. Let $S \subseteq \mathbb{N}$ be non-empty. Suppose, for contradiction, that $S$ has no least element. Define a property $Q$ of natural numbers by \begin{align*} Q(n) \quad \text{means} \quad n \notin S. \end{align*} We verify the hypotheses of strong induction for $Q$. First, $Q(1)$ holds: if $1 \in S$, then $1$ would be the least element of $S$, since $1 \le s$ for every $s \in \mathbb{N}$. Now let $n \in \mathbb{N}$ and assume $Q(k)$ holds for every $k \le n$. This means no element of $S$ belongs to $\{1,\dots,n\}$. If $n+1 \in S$, then every $s \in S$ satisfies $s \ge n+1$, because every natural number smaller than $n+1$ is one of $1,\dots,n$ and is not in $S$. Hence $n+1$ would be the least element of $S$, contradicting the assumption that $S$ has no least element. Therefore $n+1 \notin S$, so $Q(n+1)$ holds. By strong induction, $Q(n)$ holds for every $n \in \mathbb{N}$. Thus no natural number belongs to $S$, so $S = \varnothing$, contradicting the hypothesis that $S$ is non-empty. Hence every non-empty subset of $\mathbb{N}$ has a least element. [guided] Assume the principle of strong induction. To prove the well-ordering principle, let $S \subseteq \mathbb{N}$ be non-empty. We argue by contradiction and suppose that $S$ has no least element. The key idea is to prove, by strong induction, that every natural number is outside $S$. Define the property $Q$ of natural numbers by \begin{align*} Q(n) \quad \text{means} \quad n \notin S. \end{align*} We must verify the base case and the strong inductive step. For the base case, suppose $1 \in S$. Since every natural number is at least $1$, the element $1$ would be the least element of $S$. This contradicts the assumption that $S$ has no least element. Therefore $1 \notin S$, so $Q(1)$ holds. For the inductive step, let $n \in \mathbb{N}$ and assume $Q(k)$ holds for every $k \in \mathbb{N}$ with $k \le n$. In concrete terms, this means \begin{align*} \{1,\dots,n\} \cap S = \varnothing. \end{align*} We prove $Q(n+1)$. Suppose instead that $n+1 \in S$. Every natural number smaller than $n+1$ lies in $\{1,\dots,n\}$, and the induction hypothesis says none of those numbers lies in $S$. Hence no element of $S$ is smaller than $n+1$. Since $n+1 \in S$, it follows that $n+1$ is the least element of $S$, contradicting the assumption that $S$ has no least element. Therefore $n+1 \notin S$, so $Q(n+1)$ holds. The hypotheses of strong induction are now verified for $Q$. Strong induction gives $Q(n)$ for every $n \in \mathbb{N}$, meaning every natural number lies outside $S$. Thus $S = \varnothing$, contradicting the original assumption that $S$ is non-empty. Therefore the supposition that $S$ has no least element is false, and every non-empty subset of $\mathbb{N}$ has a least element. [/guided] [/step] [step:Combine the two implications] The first step shows that the well-ordering principle implies the principle of strong induction. The second step shows that strong induction implies the well-ordering principle. Therefore the two principles are equivalent. [/step]