How does one prove transfinite induction in ZFC?

Question

If one is able to use classes, it seems to me that the proof of transfinite induction is a simple extension of the usual proof of induction (and equal to the proof of transfinite induction on sets). However, if one cannot argue on classes, how can one prove transfinite induction?

PS: I'm sorry if my question is confused. That would be because my knowledge on set theory is not thorough and barely enough for me to be confortable with it.

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

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

Answer 3

Here is one formulation of the principle of transfinite induction given in Paul Halmos' Naive Set Theory (page 66), along with an adaption of the proof given there.

Let $X$ be a well-ordered set. Suppose that $S \subset X$, and that whenever $x\in X$ and $s(x)\subset S$, it follows that $x\in S$. Then, $S=X$.

(Here, $s(x)$ denotes the weak initial segment determined by $a$, i.e. $\{a\in X:a\le x\}$.)

Proof: It suffices to prove the contrapositive, that if $S\subsetneq X$ then there is an $x\in X$ such that $x\not\in S$ and $s(x)\subset S$. In other words, there is an $x\in X$ with the property that all of its successors are in $S$, but $x$ is not in $S$.

If $S\subsetneq X$, then $X-S$ is non-empty. Since $X-S$ is a subset of a well-ordered set, it has a least element $x_0$. We claim that $x_0$ has the aforementioned property. For all $x$, if $x\in X-S$, then $x_0\le x$; equivalently, if $x<x_0$, then $x\not\in X-S$. This implies that $s(x_0)\subset S$, completing the proof.

I found this proof became more intuitive once I applied it to a specific example of a well-ordered set, e.g. $X=\{0,1,2,\dots,\omega,\omega+1,\omega+2\}$.