§ Transfinite induction: Proof

• Let $(J, <)$ be a well-ordered set.
• Let $S(\alpha) \equiv J < \alpha$, or $S(\alpha) \equiv \{ j \in J: j < \alpha \}$. This is called as the section of $J$ by $\alpha$.
• Let a $J_0 \subseteq J$ be inductive iff for all $\alpha \in J$, $S(\alpha) \subseteq J_0$ implies $\alpha \in J_0$. That is:

• Then transfinite induction states that for any inductive set $J_0 \subseteq J$, we have $J_0 = J$.

• Proof by contradiction. Suppose that $J_0$ is an inductive set such that $J_0 \neq J$.
• Let $W$ (for wrong) be the set $J_0 - J$. That is, $W$ is elements that are not in $J_0$.
• $W$ is non-empty since $J_0 \neq J$. Thus, consider $w \equiv \min(W)$, which is possible since $J$ is well-ordered, thus the subset $W$ has a minimum element.
• $w$ is the smallest element that is not in $J_0$. So all elements smaller than $w$ are in $J_0$. This, $S(w) \subseteq J_0$. This implies $w \in J_0$ as $J_0$ is inductive.
• This is contradiction, as we start with $w$ is the smallest element not in $J_0$, and then concluded that $w$ is in $J_0$.
• Thus, the set $W \equiv J_0 - J$ must be empty, or $J_0 = J$.