## § 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:

$\text{$J_0$ inductive} \equiv \forall \alpha \in J, S(\alpha) \subseteq J_0 \implies \alpha \in J_0$

- 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$.