[proofplan]
The argument is a direct application of the defining property of a well-ordering. If $S$ fails to equal $X$, the complement $X \setminus S$ is non-empty and therefore has a least element $x_0$. By minimality, every predecessor of $x_0$ lies in $S$, so the hypothesis forces $x_0 \in S$. This contradicts $x_0 \in X \setminus S$, proving $S = X$. The proof is a single contradiction step, but each part — non-emptiness of the complement, existence of the minimum, use of the induction hypothesis — must be unpacked carefully.
[/proofplan]
[step:Suppose for contradiction that $S \neq X$ and extract the least counterexample $x_0 := \min(X \setminus S)$]
Assume for contradiction that $S \subsetneq X$. Then $X \setminus S \neq \varnothing$. Since $(X, <)$ is well-ordered, every non-empty subset of $X$ has a least element. Define
\begin{align*}
x_0 := \min(X \setminus S).
\end{align*}
Then $x_0 \in X$, $x_0 \notin S$, and for every $z \in X \setminus S$ we have $x_0 \leq z$.
[guided]
The proof is by contradiction. Assume $S \neq X$. Combined with the hypothesis $S \subseteq X$, this gives $S \subsetneq X$, hence $X \setminus S$ is non-empty.
Why do we focus on the minimum of the complement? The hypothesis on $S$ says: whenever $\{y : y < x\} \subseteq S$, then $x \in S$. To derive a contradiction, we want to exhibit an element $x_0 \notin S$ whose strict predecessors all lie in $S$ — then the hypothesis forces $x_0 \in S$, contradicting $x_0 \notin S$. The least element of $X \setminus S$ is exactly such an $x_0$: it is outside $S$, and everything strictly below it must be inside $S$ (else it would not be the *least* counterexample).
Because $(X, <)$ is well-ordered, the non-empty subset $X \setminus S$ has a minimum. Define
\begin{align*}
x_0 := \min(X \setminus S).
\end{align*}
By construction $x_0 \in X \setminus S$ (so $x_0 \notin S$), and $x_0$ is a lower bound of $X \setminus S$.
[/guided]
[/step]
[step:Verify that every predecessor of $x_0$ lies in $S$]
Let $y \in X$ with $y < x_0$. We show $y \in S$. Suppose for contradiction $y \notin S$; then $y \in X \setminus S$, so by minimality of $x_0$ we have $x_0 \leq y$. Combined with $y < x_0$, this yields $x_0 \leq y < x_0$, contradicting the irreflexivity of $<$. Hence $y \in S$.
Since $y \in X$ with $y < x_0$ was arbitrary, $\{y \in X : y < x_0\} \subseteq S$.
[/step]
[step:Apply the inductive hypothesis to derive $x_0 \in S$ and reach a contradiction]
The hypothesis on $S$ states: for every $x \in X$, if $\{y \in X : y < x\} \subseteq S$ then $x \in S$.
Applying this to $x = x_0$: we verified in the previous step that $\{y \in X : y < x_0\} \subseteq S$, so the hypothesis gives $x_0 \in S$. But $x_0 \notin S$ by construction. Contradiction.
Therefore the assumption $S \neq X$ was false, and $S = X$.
[guided]
We now have the two ingredients needed to trigger the hypothesis of the theorem at $x_0$:
1. $x_0 \in X$ (by construction).
2. $\{y \in X : y < x_0\} \subseteq S$ (by the previous step).
The hypothesis on $S$ reads: *for every $x \in X$, if $\{y \in X : y < x\} \subseteq S$ then $x \in S$*. Specialising to $x = x_0$, both the premise and the quantifier condition are satisfied, so the hypothesis concludes $x_0 \in S$.
However, we constructed $x_0$ as an element of $X \setminus S$, i.e. $x_0 \notin S$. The two statements $x_0 \in S$ and $x_0 \notin S$ are directly contradictory.
The contradiction arose from the assumption $S \neq X$. Hence $S = X$, completing the proof.
**Why does this argument fail for $(X, <) = (\mathbb{Z}, <)$?** The set $S = \{n : n \geq 0\}$ satisfies the inductive hypothesis vacuously at every $n$ (since $\{m : m < n\}$ is never contained in $S$ — there is always a sufficiently negative integer outside $S$... actually, this is subtle). The real failure is that $\mathbb{Z}$ is *not* well-ordered: the complement $\mathbb{Z} \setminus S$ has no least element, so no $x_0$ can be extracted. Without well-ordering, the minimum step collapses, and transfinite induction does not apply.
[/guided]
[/step]
