How does one prove transfinite induction in ZFC?

Solution 1:

If $C$ is any well-ordered set, we have the

Principle of Transfinite Induction. Let $P$ be a property with $$ \tag1\forall \alpha\in C\colon (\forall \beta \in C\colon \beta<\alpha \to P(\beta))\to P(\alpha).$$ Then $$ \forall \alpha\in C\colon P(\alpha).$$

Proof: We can define the set $A=\{\,\alpha\in C\mid \neg P(\alpha)\,\}$. Assume $A\ne \emptyset$. As $C$ is well-ordered $A$ has a minimal element $\alpha$. By minimality we have $\forall \beta \in C\colon \beta<\alpha \to P(\beta)$, hence from $(1)$ we get $P(\alpha)$, contradicting $\neg P(\alpha)$. Therefore $A=\emptyset$, which is the claim. $\square$

Interestingly, the principle works also if $C$ is the well-ordered proper class $ \operatorname{On}$ of all ordinals (which also happens to be the most common application of transfinite induction), even though one might be discouraged by the fact that we deal with a proper class here:

Principle of Transfinite Induction for Ordinals. Let $P$ be a property with $$ \tag2\forall \alpha\in \operatorname{On}\colon (\forall \beta \in \operatorname{On}\colon \beta<\alpha \to P(\beta))\to P(\alpha).$$ Then $$ \forall \alpha\in \operatorname{On}\colon P(\alpha).$$

Proof. Let $\gamma\in \operatorname{On}$ be an arbitrary ordinal. Then $\gamma$ itself is a well-ordererd set of ordinals, so that we can apply the principle of Transfinite induction above to the well-ordered set $C=\gamma$. We conclude $\forall \beta\in\gamma\colon P(\beta)$ or more wordy $\forall \beta\in \operatorname{On}\colon\beta\in \gamma \to P(\beta)$. As $\beta\in\gamma$ is the same as $\beta<\gamma$, we learn from $(2)$ that $P(\gamma)$. As $\gamma$ was an arbitrary ordinal, we obtain the desired claim. $\square$

Solution 2:

It's simple to prove for any wellordered set. I suspect here (please correct me if I'm wrong) that what you're actually curious about is what lets you do transfinite induction over the class of all ordinals, rather than just a wellordered set.

It's true you can't use induction to show that some property $\phi$ holds by showing the set of all ordinals such that $\phi$ is equal to "the set of all ordinals", the way you would go about it with some wellordered set. What you can do, though, is prove that for every ordinal $\alpha$, the ordinals below $\alpha$ form a set (the von Neumann implementation sees to this very nicely), and then show that if the hypothesis of the transfinite induction holds, $\phi$ must hold of $\alpha$. You can then deduce, since $\alpha$ was an arbitrary ordinal, that the property of being an ordinal implies that $\phi$ holds of it.