Transfinite induction on class of ordinals.

Question

This was an exercise from Enderton's Text, Elements of Set Theory. I am unsure of my proof - and I wonder what other possible solutions there are.

[7,25] (Transfinite induction schema) Let $\phi(x)$ be a formula and show that the following holds: $$ \text{ If $\forall \alpha, \, ( \forall x \in \alpha) \phi(x) \Rightarrow \phi(\alpha) $. Then $\phi(\alpha)$ for any ordinal $\alpha$.}$$

My thoughts (proof): For ordinal $\alpha$, define set $$ B:= \{ x \in \alpha \, | \, \phi(x) \} $$ We apply transfinite induction principle (below) on the set $B \subseteq \alpha$, where $\alpha$ is well ordered by epsilon (by membership). If $\text{seg }x \subseteq B$, then $(\forall y \in x)\phi(y)$, hence, $\phi(x)$ by hypothesis of problem. So $x \in B$, and $B = \alpha$.

Consequently for any ordinal $\alpha$, $(\forall x \in \alpha)\phi(x)$ holds, and by hypothesis, $\phi(\alpha)$.

Transfinite induction princple: Transfinite Induction Principle: Assume that $<$ is a well ordering on $A$. Assume that $B$ is a subset of $A$ with the special property that for every $t \in A$, $$ \text{seg } t \subseteq B \Rightarrow t \in B$$ Then $B$ conincides with $A$.

Is this proof correct? Thank you so much!

---

Proof 2: (hinted by Clive Newstand)

Consider the class $$B := \{ \alpha \, | \, \alpha \text{ is an ordinal } \, \& \, \phi(\alpha) \text{ does not hold } \} $$ If $B$ is empty then we are done. Suppose $B$ is nonempty, there exist $\beta \in B$. Define the set, $$B' = \{ x \in \beta \, | \, \phi(x) \text{ does not hold } \} $$ since any set of ordinals is well ordered by epsilon, let $\alpha'$ be the least element of $B'$. So for all $x \in \alpha'$, $\phi(x)$ holds, meaning $\phi(\alpha')$ by hypothesis, contradiction.

@Clive Newstead, I wonder if the above proof is correct.

Answer 1

It seems odd that you mention 'transfinite induction' in your proof of the principle of transfinite induction; in fact, you seem to be assuming the result to prove the result.

A clearer approach might be to suppose that $\phi(\alpha)$ is false for some ordinal $\alpha$. Fix the least such $\alpha$, and derive a contradiction using the assumption that $\phi(\alpha)$ is false.

Answer 2

Theorem (Transfinite Induction). For each formula $\phi(\alpha)$, if for each ordinal $\beta$, if for each $\gamma\in\beta$, $\phi(\gamma)$ holds, then $\phi(\beta)$ holds, then for each ordinal $\alpha$, $\phi(\alpha)$ holds.

Proof. Let $\phi(\alpha)$ be an arbitrary formula. Assume for each ordinal $\beta$, if for each $\gamma\in\beta$, $\phi(\gamma)$ holds, then $\phi(\beta)$ holds. Let $\alpha$ be an arbitrary ordinal. Let $\gamma\in\alpha$ be arbitrary. By contradiction, suppose $\phi(\gamma)$ does not hold. Let $\eta$ be the least element of $\alpha$ such that $\phi(\eta)$ does not hold. Therefore for each $\delta\in_{\alpha} \eta$, $\phi(\delta)$ holds. Therefore for each $\delta\in\eta$, $\phi(\delta)$ holds. Therefore $\phi(\eta)$ holds---a contradiction. As a result, $\phi(\gamma)$ holds. Therefore for each $\gamma\in\alpha$, $\phi(\gamma)$ holds. Therefore $\phi(\alpha)$ holds.